Fink protokoll

A Fink Protokoll [1] (más néven Consecutive Pairs [2] vagy Single Chooser [3] ) egy arányos tortamegosztási protokoll .

A protokoll fő előnye, hogy online működik, még akkor is, ha a felosztásban résztvevők száma nem ismert előre. Amikor egy új tag csatlakozik egy részleghez, a meglévő divíziót átépítik, hogy igazságos felosztást biztosítsanak az újonnan érkezőknek, minimális hatással a meglévő tagokra.

A protokoll fő hátránya, hogy egy koherens darab helyett a protokoll nagyszámú "morzsát" rendel a résztvevőhöz.

Protokoll

A protokollt induktív módon írjuk le a résztvevők számának növelésével.

Amikor az 1. versenyző csatlakozik a bulihoz, elviszi az összes tortát. Részvényértéke 1.

Amikor a 2. versenyző megérkezik, az 1. versenyző két darabra vágja a tortát, amelyek a szemükben egyenlőek. Az új résztvevő azt a darabot választja, amelyik jobb a szemében. Az egyes résztvevők értéke most legalább 1/2 (mint az oszd meg és válassz protokollban ).

Amikor a 3-as résztvevő csatlakozik, mind az 1-es, mind a 2-es résztvevő 3 egyenlő részre vágja a részesedését a szemében. Az új résztvevő minden résztvevő közül választ egy darabot. Az 1-es és a 2-es résztvevő értékei legalább 2/3-a a korábbi értéküknek, amely 1/2 volt. Ezért új értékük nem kevesebb, mint 1/3. A 3. versenyző értéke legalább az 1. szelet 1/3-a és a 2. szelet 1/3-a, így a teljes torta legalább 1/3-át adja neki.

Általában, amikor #i résztvevő csatlakozik a partihoz, az előző i -1 résztvevők i egyenlő részekre osztják a részesedéseiket, és az új résztvevő mindegyik kupacból választ egy darabot. Ismét kimutatható, hogy az egyes résztvevők értéke a teljes érték legalább 1/ n -e , tehát a vágás arányos.

Vágások száma

Az algoritmus egyszerű alkalmazása darabokat ad, bár valójában csak kb . , mivel minden résztvevőnek szüksége van vágásokra, amikor a -edik résztvevő megérkezik.

Alkalmazások

A Fink protokollt segédalgoritmusként használják más protokollokban a torta igazságos felosztása érdekében:

• Woodall szuperarányos osztási protokollja n résztvevőre .
• Austin „Moving Knife” eljárása , amely minden résztvevőnek kioszt egy darabot, amelynek értéke pontosan megegyezik egy teljes tortával.

Jegyzetek

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

Irodalom

• Fink AM Megjegyzés a tisztességes osztás problémájához // Mathematics Magazine. - 1964. - T. 37 , sz. 5 . - doi : 10.2307/2689255 . — .
• Saaty TL optimalizálás egész számokban és a kapcsolódó extrém problémákban. - McGraw-Hill, 1970. - ISBN 0070543690 .
• Steven J. Brams, Alan D. Taylor. Fair Division: A tortavágástól a vitarendezésig. - 1996. - ISBN 0521556449 .