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

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

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

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

Протокол

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

Когда участник №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$ полного торта.