Protocolul Fink

Protocolul Fink [1] (cunoscut și sub numele de Perechi consecutive [2] sau Single Chooser [3] ) este un protocol proporțional de partajare a tortului .

Principalul avantaj al protocolului este că funcționează online, chiar dacă numărul de participanți la divizie nu este cunoscut dinainte. Când un nou membru se alătură unei divizii, divizia existentă este reconstruită pentru a oferi noului venit o împărțire corectă, cu un efect minim asupra membrilor existenți.

Principalul dezavantaj al protocolului este că, în loc de o singură piesă coerentă, protocolul alocă un număr mare de „fărâmituri” participantului.

Protocol

Descriem protocolul în mod inductiv prin creșterea numărului de participanți.

Când concurentul #1 se alătură petrecerii, el doar ia tot tortul. Valoarea cotei sale este 1.

Când sosește concurentul #2, concurentul #1 taie tortul în două bucăți care sunt egale în ochii lor. Noul participant alege piesa care este mai bună în ochii lui. Valoarea pentru fiecare participant este acum de cel puțin 1/2 (ca în protocolul împărțiți și alegeți ).

Când participantul #3 se alătură, ambii participanți #1 și #2 își taie părțile în 3 părți egale în ochii lor. Noul participant alege o piesă din fiecare participant. Valorile pentru participanții #1 și #2 sunt cel puțin 2/3 din valoarea lor anterioară, care a fost 1/2. Prin urmare, noua lor valoare nu este mai mică de 1/3. Valoarea pentru concurentul #3 este de cel puțin 1/3 din felia #1 și 1/3 din felia 2, oferindu-i cel puțin 1/3 din tortul plin.

În general, când participantul #i se alătură petrecerii, participanții anteriori i -1 își împart părțile în i părți egale, iar noul participant alege o piesă din fiecare grămadă. Din nou, se poate demonstra că valoarea pentru fiecare participant este de cel puțin 1/ n din valoarea totală, astfel încât reducerea este proporțională.

Numărul de tăieturi

Aplicarea simplă a algoritmului va da bucăți, deși de fapt doar aproximativ , deoarece fiecare participant are nevoie de tăieturi când sosește al-lea participant. $n!$ $n^{3}/3$ $n-1$ $n$

Aplicații

Protocolul Fink este folosit ca algoritm auxiliar în alte protocoale pentru o împărțire corectă a tortului:

Protocolul Woodall de împărțire superproporțională pentru n participanți .
Procedurile „Moving Knife” ale lui Austin , alocând fiecărui participant o bucată a cărei valoare este exact egală cu o prăjitură plină. $1/n$

Note

↑ Fink, 1964 , p. 341.
↑ Saaty, 1970 .
↑ Brams și Taylor 1996 , p. 40.

Literatură

Fink AM O notă despre problema diviziunii echitabile // Revista de matematică. - 1964. - T. 37 , nr. 5 . - doi : 10.2307/2689255 . — .
Optimizare Saaty TL în numere întregi și probleme extreme conexe. - McGraw-Hill, 1970. - ISBN 0070543690 .
Steven J. Brams, Alan D. Taylor. Divizia echitabilă: de la tăierea prăjiturii la soluționarea disputelor. - 1996. - ISBN 0521556449 .