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

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

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

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

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

Эта страница в последний раз была отредактирована 10 января 2021 в 10:36.