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

Протокол Финка ^[1] (также известный как «Последовательные пары» [ ^2] или «Одинокий выбирающий» ^[3] ) — это протокол пропорционального дележа торта .

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

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

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

Когда партнер №1 приходит на вечеринку, он просто забирает весь торт. Таким образом, его ценность равна 1.

Когда приходит партнер №2, партнер №1 разрезает торт на две равные в его глазах части. Новый партнер выбирает ту часть, которая в его глазах лучше. Таким образом, ценность каждого партнера составляет не менее 1/2 (как в протоколе «раздели и выбери »).

Когда присоединяется партнер №3, оба партнера №1 и №2 делят свою долю на 3 равные по их мнению части. Новый партнер выбирает по одной части от каждого партнера. Стоимость каждого из партнеров №1 и №2 составляет не менее 2/3 от их предыдущей стоимости, которая была 1/2. Следовательно, их новая стоимость составляет не менее 1/3. Партнер №3 оценивает доли партнеров №1 и №2 в , , где . Стоимость партнера №3 составляет не менее части №1 и не менее части №2, что дает ему не менее 1/3 от общего пирога.${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{1}+v_{2}=1}$${\displaystyle {\frac {v_{1}}{3}}}$${\displaystyle {\frac {v_{2}}{3}}}$

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

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

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

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