Протокол Финка

Протокол Финка[1] (известный также как Последовательные пары[2] или Одиночный выбирающий[3]) — это протокол пропорционального дележа торта.

Основное преимущество протокола заключается в том, что он работает в онлайн-варианте, даже если заранее не известно число участников дележа. Когда к дележу присоединяется новый участник, существующее деление перестраивается для получения справедливого дележа для вновь пришедшего с минимальным эффектом для существующих участников.

Основной недостаток протокола в том, что вместо одного связного куска протокол выделяет участнику большое число «крошек».

Протокол

Мы опишем протокол индуктивно по увеличению числа участников.

Когда участник №1 присоединяется к вечеринке, он просто забирает весь торт. Его оценка своей доли равна 1.

Когда приходит участник №2, участник №1 разрезает торт на две части, равные в его глазах. Новый участник выбирает кусок, который в его глазах лучше. Значение для каждого участника теперь не меньше 1/2 (как в протоколе дели-и-выбирай).

Когда присоединяется участник #3, оба участника #1 и #2 режут свои доли на 3 части, равные в их глазах. Новый участник выбирает по одному куску от каждого участника. Значения для участников №1 и №2 не менее 2/3 их предыдущего значения, которое было равно 1/2. Следовательно, их новое значение не меньше 1/3. Значение для участника №3 не меньше 1/3 от куска №1 и 1/3 от куска 2, что даёт ему по меньшей мере 1/3 от полного торта.

В общем случае, когда участник №i присоединяется к вечеринке, предыдущие i-1 участников делят свои доли на i равных частей и новый участник выбирает по куску из каждой кучки. Снова можно показать, что значение для каждого участника по меньшей мере 1/n полной величины, так что разрезание является пропорциональным.

Число разрезов

Прямолинейное применение алгоритма даст $n!$ кусков, хотя, фактически, только около $n^{3}/3$ , поскольку каждому участнику нужно $n-1$ разрезаний, когда приходит $n$ -ый участник.

Приложения

Протокол Финка используется как вспомогательный алгоритм в других протоколах справедливого дележа торта:

Протокол Вудала суперпропорционального дележа для n участников.
Процедуры «Движущийся нож» Остина, выделяющий каждому участнику кусок, значение которого равно в точности $1/n$ полного торта.

Примечания

Fink, 1964, с. 341.
Saaty, 1970.
Brams, Taylor, 1996, с. 40.

Литература

Fink A. M. A Note on the Fair Division Problem // Mathematics Magazine. — 1964. — Т. 37, вып. 5. — doi:10.2307/2689255. — .
Saaty T.L. Optimization in Integers and Related Extremal Problems. — McGraw-Hill, 1970. — ISBN 0070543690.
Steven J. Brams, Alan D. Taylor. Fair Division: From cake-cutting to dispute resolution. — 1996. — ISBN 0521556449.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_e42e342634aedd63-1] Fink, 1964, с. 341.

[_b71ce724e4f6647c-2] Saaty, 1970.

[_325f998e84bbb5b0-3] Brams, Taylor, 1996, с. 40.