Fink-protokollet

Fink-protokollet [1] (även känt som konsekutiva par [2] eller singelväljare [3] ) är ett proportionellt kakdelningsprotokoll .

Den största fördelen med protokollet är att det fungerar online, även om antalet deltagare i divisionen inte är känt i förväg. När en ny medlem går med i en division byggs den befintliga divisionen om för att ge en rättvis uppdelning för nykomlingen med minimal effekt på de befintliga medlemmarna.

Den största nackdelen med protokollet är att istället för en sammanhängande del, tilldelar protokollet ett stort antal "smulor" till deltagaren.

Protokoll

Vi beskriver protokollet induktivt genom att öka antalet deltagare.

När tävlande #1 ansluter sig till festen tar han bara hela tårtan. Hans aktievärde är 1.

När tävlande #2 anländer skär tävlande #1 kakan i två delar som är lika i deras ögon. Den nya deltagaren väljer det stycke som är bättre i hans ögon. Värdet för varje deltagare är nu minst 1/2 (som i dela-och-välj- protokollet ).

När deltagare #3 går med skär både deltagare #1 och #2 sina andelar i 3 lika delar i deras ögon. Den nya deltagaren väljer en del från varje deltagare. Värdena för deltagare #1 och #2 är minst 2/3 av deras tidigare värde, vilket var 1/2. Därför är deras nya värde inte mindre än 1/3. Värdet för tävlande #3 är minst 1/3 av skiva #1 och 1/3 av skiva 2, vilket ger honom minst 1/3 av hela kakan.

I allmänhet, när deltagare #i går med i festen delar de tidigare i -1-deltagarna sina andelar i i lika delar och den nya deltagaren väljer en bit från varje hög. Återigen kan det visas att värdet för varje deltagare är minst 1/ n av det totala värdet, så att snittet är proportionellt.

Antal klipp

Enkel tillämpning av algoritmen kommer att ge bitar, men i själva verket bara ca , eftersom varje deltagare behöver skärningar när den -: e deltagaren anländer. $n!$ $n^{3}/3$ $n-1$ $n$

Applikationer

Fink-protokollet används som en hjälpalgoritm i andra protokoll för en rättvis uppdelning av kakan:

Woodalls protokoll för superproportionell uppdelning för n deltagare .
Austins "Moving Knife"-procedurer , tilldelar varje deltagare en bit vars värde är exakt lika med en hel kaka. $1/n$

Anteckningar

↑ Fink, 1964 , sid. 341.
↑ Saaty, 1970 .
↑ Brams och Taylor 1996 , sid. 40.

Litteratur

Fink AM A Note on the Fair Division Problem // Mathematics Magazine. - 1964. - T. 37 , nr. 5 . - doi : 10.2307/2689255 . — .
Saaty TL- optimering i heltal och relaterade extrema problem. - McGraw-Hill, 1970. - ISBN 0070543690 .
Steven J. Brams, Alan D. Taylor. Fair Division: Från kakskärning till tvistlösning. - 1996. - ISBN 0521556449 .