Протокол Fink - Fink protocol

В Протокол Fink^[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 от общей суммы торта.

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

Количество разрезов

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

Приложения

Протокол Fink используется в подпрограмме в других протоколах резки торта:

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

Рекомендации

1. Финк, А. М. (1964). «Заметка о проблеме справедливого разделения». Математический журнал. 37 (5): 341. Дои:10.2307/2689255. JSTOR  2689255.
2. Оптимизация в целых числах и связанных с ними экстремальных задачах. Т.Л. Саати. Макгроу-Хилл 1970
3. Брамс, Стивен Дж .; Тейлор, Алан Д. (1996). Ярмарка дел: от нарезки торта до разрешения споров. п. 40. ISBN  0521556449.