Протокол 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 /п от общей суммы, поэтому деление будет пропорциональным.

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

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

Приложения

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

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

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