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

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

Число разрезовПравить

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

ПриложенияПравить

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

Протокол Вудала суперпропорционального дележа для n участников.
Процедуры «Движущийся нож» Остина, выделяющий каждому участнику кусок, значение которого равно в точности $\text{[math]}$ $\text{[math]}$ $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. — 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.

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

[_b71ce724e4f6647c-2] Saaty, 1970.

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

[1]

[2]

[3]