Fink-protokollen

Fink-protokollen [1] (også kendt som konsekutive par [2] eller enkeltvælger [3] ) er en proportional kagedelingsprotokol .

Den største fordel ved protokollen er, at den fungerer online, selvom antallet af deltagere i divisionen ikke er kendt på forhånd. Når et nyt medlem tiltræder en division, genopbygges den eksisterende division for at give en retfærdig opdeling for den nye med minimal effekt på de eksisterende medlemmer.

Den største ulempe ved protokollen er, at i stedet for ét sammenhængende stykke, tildeler protokollen et stort antal "krummer" til deltageren.

Protokol

Vi beskriver protokollen induktivt ved at øge antallet af deltagere.

Når deltager #1 slutter sig til festen, tager han bare hele kagen. Hans aktieværdi er 1.

Når deltager #2 ankommer, skærer deltager #1 kagen i to stykker, der er lige store i deres øjne. Den nye deltager vælger det stykke, der er bedre i hans øjne. Værdien for hver deltager er nu mindst 1/2 (som i del-og-vælg- protokollen ).

Når deltager #3 tilslutter sig, skærer både deltager #1 og #2 deres andele i 3 lige store dele i deres øjne. Den nye deltager vælger et stykke fra hver deltager. Værdierne for deltager #1 og #2 er mindst 2/3 af deres tidligere værdi, som var 1/2. Derfor er deres nye værdi ikke mindre end 1/3. Værdien for deltager #3 er mindst 1/3 af skive #1 og 1/3 af skive 2, hvilket giver ham mindst 1/3 af den fulde kage.

Generelt, når deltager #i melder sig ind i festen, deler de tidligere i -1 deltagere deres andele i i lige store dele, og den nye deltager vælger et stykke fra hver bunke. Igen kan det påvises, at værdien for hver deltager er mindst 1/ n af den samlede værdi, således at cuttet er proportionalt.

Antal klip

Ligetil anvendelse af algoritmen vil give stykker, men faktisk kun omkring , da hver deltager har brug for klip, når den -th deltager ankommer.

Ansøgninger

Fink-protokollen bruges som en hjælpealgoritme i andre protokoller til en retfærdig opdeling af kagen:

• Woodalls protokol for superproportional division for n deltagere .
• Austins "Moving Knife"-procedurer , der tildeler hver deltager et stykke, hvis værdi er nøjagtigt lig med en hel kage.

Noter

1. ↑ Fink, 1964 , s. 341.
2. ↑ Saaty, 1970 .
3. ↑ Brams og Taylor 1996 , s. 40.

Litteratur

• Fink AM A Note on the Fair Division Problem // Mathematics Magazine. - 1964. - T. 37 , no. 5 . - doi : 10.2307/2689255 . — .
• Saaty TL- optimering i heltal og relaterede ekstreme problemer. - McGraw-Hill, 1970. - ISBN 0070543690 .
• Steven J. Brams, Alan D. Taylor. Fair Division: Fra kageskæring til konfliktløsning. - 1996. - ISBN 0521556449 .