Fink-protokolla

Fink-protokolla [ 1] (tunnetaan myös nimellä Consecutive Pairs [2] tai Single Chooser [3] ) on suhteellinen kakun jakamisprotokolla .

Protokollan tärkein etu on, että se toimii verkossa, vaikka divisioonan osallistujamäärää ei tiedetä etukäteen. Kun uusi jäsen liittyy divisioonaan, olemassa oleva divisioona rakennetaan uudelleen siten, että uudelle tulokkaalle saadaan oikeudenmukainen jakautuminen minimaalisella vaikutuksella olemassa oleviin jäseniin.

Protokollan suurin haittapuoli on, että yhden yhtenäisen kappaleen sijasta protokolla osoittaa osallistujalle suuren määrän "muruja".

Protokolla

Kuvaamme protokollaa induktiivisesti lisäämällä osallistujamäärää.

Kun kilpailija #1 liittyy juhliin, hän vain ottaa kaiken kakun. Hänen osakkeensa arvo on 1.

Kun kilpailija #2 saapuu, kilpailija #1 leikkaa kakun kahteen osaan, jotka ovat samanarvoisia heidän silmissään. Uusi osallistuja valitsee teoksen, joka on hänen silmissään parempi. Jokaisen osallistujan arvo on nyt vähintään 1/2 (kuten jaa ja valitse -protokollassa ).

Kun osallistuja #3 liittyy, molemmat osallistujat #1 ja #2 leikkaavat osuutensa kolmeen yhtä suureen osaan heidän silmissään. Uusi osallistuja valitsee yhden palan jokaiselta osallistujalta. Osallistujien 1 ja 2 arvot ovat vähintään 2/3 edellisestä arvostaan, joka oli 1/2. Siksi niiden uusi arvo ei ole pienempi kuin 1/3. Kilpailijan #3 arvo on vähintään 1/3 viipaleesta #1 ja 1/3 viipaleesta 2, mikä antaa hänelle vähintään 1/3 täydestä kakusta.

Yleensä kun osallistuja #i liittyy seurueeseen, edelliset i -1 osallistujat jakavat osuutensa i yhtä suuriin osiin ja uusi osallistuja valitsee palan jokaisesta pinosta. Jälleen voidaan osoittaa, että kunkin osallistujan arvo on vähintään 1/ n kokonaisarvosta, joten leikkaus on verrannollinen.

Leikkausten määrä

Algoritmin suoraviivainen soveltaminen antaa palasia, vaikkakin itse asiassa vain noin , koska jokainen osallistuja tarvitsee leikkauksia, kun -. osallistuja saapuu.

Sovellukset

Fink-protokollaa käytetään apualgoritmina muissa protokollissa kakun oikeudenmukaiseen jakamiseen:

• Woodallin protokolla supersuhteellisesta jaosta n osallistujalle .
• Austinin "Moving Knife" -menettelyt , joissa jokaiselle osallistujalle jaetaan pala, jonka arvo on täsmälleen yhtä suuri kuin täysi kakku.

Muistiinpanot

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

Kirjallisuus

• Fink AM Huomautus reilun jaon ongelmasta // Mathematics Magazine. - 1964. - T. 37 , no. 5 . - doi : 10.2307/2689255 . — .
• Saaty TL -optimointi kokonaisluvuissa ja niihin liittyvissä äärimmäisissä ongelmissa. - McGraw-Hill, 1970. - ISBN 0070543690 .
• Steven J. Brams, Alan D. Taylor. Reilu osasto: kakun leikkaamisesta riitojen ratkaisemiseen. - 1996. - ISBN 0521556449 .