Протокол Финка (Hjkmktkl Snutg)

Перейти к навигации Перейти к поиску

Протокол Финка[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 полной величины, так что разрезание является пропорциональным.

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

[править | править код]

Прямолинейное применение алгоритма даст кусков, хотя, фактически, только около , поскольку каждому участнику нужно разрезаний, когда приходит -ый участник.

Приложения

[править | править код]

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

Примечания

[править | править код]

Литература

[править | править код]
  • Fink A. M. A Note on the Fair Division Problem // Mathematics Magazine. — 1964. — Т. 37, вып. 5. — doi:10.2307/2689255. — JSTOR 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.