Fink protokoll

Fink -protokollet (även känt som Successive Pairs eller Lone Chooser ) är ett protokoll för proportionell delning av en kaka .

Dess främsta fördel är att det kan fungera online utan att veta antalet partners i förväg. När en ny partner ansluter sig till partiet, justeras den befintliga uppdelningen för att ge en rättvis andel till nykomlingen, med minimal effekt på befintliga partners.

Dess största nackdel är att istället för att ge varje partner en enda ansluten del, ger det varje partner ett stort antal "smulor".

Protokoll

Vi beskriver protokollet induktivt för ett ökande antal partners.

När partner #1 kommer in på festen tar han bara hela tårtan. Hans värde är alltså 1.

När partner #2 kommer skär partner #1 kakan i två delar som är lika i hans ögon. Den nya partnern väljer den bit som är bättre i hans ögon. Värdet på varje partner är alltså minst 1/2 (precis som i dela och välj -protokollet).

När partner #3 går med, skär både partner #1 och #2 sin del till 3 stycken som är lika i deras ögon. Den nya partnern väljer en del från varje partner. Värdet för var och en av partner #1 och #2 är minst 2/3 av deras tidigare värde, vilket var 1/2. Därför är deras nya värde minst 1/3. Värdet på partner #3 är minst 1/3 från del av #1 och 1/3 från del av 2, vilket ger honom minst 1/3 av den totala kakan.

I allmänhet, när partner # i går in i festen, delar de tidigare i -1-partnerna sin andel till i lika delar och den nya partnern plockar en bit från varje hög. Återigen är det möjligt att bevisa att värdet av varje partner är minst 1/ n av det totala, så uppdelningen är proportionell.

Antal snitt

Enkel användning av algoritmen skulle generera $n!$ bitar, men faktiskt bara cirka $n^{3}/3$ behövs eftersom varje partner egentligen bara behöver göra $n-1$ snitt när den ${\displaystyle n}:$ ^e partnern kommer med.

Ansökningar

Finks protokoll används i en subrutin i andra kakskärningsprotokoll:

• Woodalls protokoll för superproportionell division för n spelare .
• Austin moving-knife procedure , som ger varje partner en bit som han värderar som exakt $1/n$ av totalen.