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

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

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

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

Приложения

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

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

Ссылки

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

[1] Финк, AM (1964). «Заметка о проблеме справедливого дележа». Журнал «Математика» . 37 (5): 341–342. дои : 10.2307/2689255 . JSTOR 2689255 .

[2] Оптимизация в целых числах и связанные с ней экстремальные задачи. ТЛСаати. МакГроу-Хилл 1970 г.

[3] Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Ярмарка: от разрезания торта до разрешения споров . п. 40. ИСБН 0521556449 .

[1]

[2]

[3]