Menettely "viimeksi alennettu"

Viimeinen laskeva menettely on reilu kakun leikkaaminen . Menettely on suunniteltu allokoimaan heterogeeninen jaettavissa oleva resurssi, kuten syntymäpäiväkakku, ja siihen osallistuu jaossa n osallistujaa, joilla on erilaiset mieltymykset kakun eri osiin. Menettelyn avulla n henkilöä saa suhteellisen jaon eli jakaa kakun heidän kesken siten, että jokainen osallistuja saa vähintään ${\tfrac {1}{n))$ täyden arvon oman (subjektiivisen) arvionsa mukaan. Esimerkiksi, jos Alicen arvio koko kakusta on 100 dollaria ja osallistujia on 5, niin Alice voi saada palan, jonka hän arvostaa vähintään 20 dollaria, riippumatta siitä, mitä muut osallistujat ajattelevat tai tekevät.

Historia

Toisen maailmansodan aikana natseilta piiloutunut puolalainen juutalainen matemaatikko Hugo Steinhaus kiinnostui resurssien oikeudenmukaisesta jakamisesta. Delhi-and-Choose- menettelyn innoittamana kakun jakamisesta kahden veljen kesken hän pyysi oppilaitaan Stefan Banachia ja Bronisław Knasteria löytämään menetelmän, joka voisi toimia useammille ihmisille, ja julkaisi ratkaisunsa [1] .

Tämä julkaisu käynnisti uuden tutkimuksen haaran, jota nyt tekevät monet tutkijat useilla tieteenaloilla. Katso artikkeli Reilu jako .

Kuvaus

Alla on kirjoittajan kuvaus jakamisprotokollasta:

”On osallistujia A, B, C, .. N. Osallistuja A leikkaa mielivaltaisen palan kakusta. Jäsenellä B on nyt oikeus, mutta ei velvollisuutta, pienentää palaa leikkaamalla pala pois. Kun hän on tehnyt tämän, C:llä on oikeus (mutta ei velvollisuutta) pienentää jo alennettua (tai ei-alennettua) palaa ja niin edelleen osallistujalle N. Sääntö velvoittaa viimeisen vähentäneen (katkaisun) ottamaan omansa. osa. Tämä osallistuja poistuu divisioonasta ja loput n − 1 osallistujaa aloittavat saman pelin muun kakun kanssa. Kun osallistujien määrä on vähennetty kahteen, he soveltavat klassista puolittamissääntöä.

Jokaisella jäsenellä on menetelmä, joka varmistaa, että se vastaanottaa palan, jonka arvo on suurempi tai yhtä suuri kuin . Menetelmä on seuraava: leikkaa aina nykyinen kappale niin, että jäljellä oleva arvo on sinulle. Vaihtoehtoja on kaksi - joko saat sen palan, jonka leikkaat pois, tai toinen henkilö saa pienemmän palan, jonka arvo on pienempi kuin . Jälkimmäisessä tapauksessa osallistujia on jäljellä n − 1 ja jäljellä olevan kakun arvio on suurempi kuin . Induktiolla voimme todistaa, että tuloksena oleva arvo on vähintään . ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {n-1}{n))$ ${\tfrac {1}{n))$

Yleisen asetusfunktion rappeutunut tapaus

Algoritmi yksinkertaistuu rappeutuneessa tapauksessa, kun kaikilla osallistujilla on samat preferenssifunktiot, koska ensimmäisen optimaalisen leikkauksen tehneestä osallistujasta tulee viimeinen vähentäjä. Vastaavasti jokainen osallistuja 1, 2, ..., n − 1 leikkaa vuorollaan palan jäljellä olevasta kakusta. Sitten käänteisessä järjestyksessä jokainen osallistuja n , n − 1, ..., 1 valitsee palan, jota ei ole vielä lunastanut.

Analyysi

Last Diminisher -protokolla on erillinen ja se voidaan tehdä kierroksina. Pahimmassa tapauksessa tarvitset toimia - yhden toiminnon per kierros. ${\tfrac {n\times (n-1)}{2}}=O(n^{2})$

Suurin osa näistä toiminnoista ei kuitenkaan ole oikeita leikkauksia, eli Alice voi merkitä halutun palan paperille ja toinen osallistuja pienentää sen samalle paperille ja niin edelleen. Vain "viimeinen leikkuri" saa leikata kakun. Tarvitaan siis vain n − 1 leikkausta. $O(n^{2})$

Menettely on erittäin vapaa viiltojen suhteen. Osallistujien tekemät viillot voivat olla minkä muotoisia tahansa. Ne voivat olla jopa epäjohdonmukaisia. Toisaalta leikkauksia voidaan rajoittaa sen varmistamiseksi, että kappaleilla on hyväksyttävä muoto. Erityisesti:

Jos alkuperäinen kakku on yhdistetty, jokainen pala voidaan taata liitetyksi (jatkuva).
Jos alkuperäinen kakku on kupera sarja , jokainen pala voidaan taata kuperaksi.
Jos alkuperäinen kakku on suorakulmio , jokainen pala voidaan taata suorakaiteen muotoiseksi.
Jos alkuperäinen kakku on kolmio , jokainen pala voidaan taata kolmio.

Jatkuva versio

Protokollan aikajatkuva versio voidaan suorittaa käyttämällä Dubins-Spanierin [2] Moving Knife -menettelyä ] . Tämä oli ensimmäinen esimerkki jatkuvasta oikeudenmukaisesta jakomenettelystä. Veitsi liikkuu kakun päällä vasemmalta oikealle. Jokainen osallistuja voi sanoa "stop", jos hän uskoo, että veitsen vasemmalla puolella olevan palan arvo on . Kakku leikataan ja "stop" sanonut osallistuja saa tämän palan. Toista jäljellä olevan kakun ja osallistujien kanssa. Viimeinen osallistuja saa loput kakusta. Viimeisen pienennysmenettelyn tapaan tätä menettelyä voidaan käyttää vierekkäisten palasten saamiseksi jokaiselle osallistujalle. $1/n$

Likimääräinen versio ilman kateutta

Jos osallistujia on 3 tai enemmän, viimeinen vähennys -protokollalla saatu osio ei ole aina vapaa kateudesta . Oletetaan esimerkiksi, että ensimmäinen pelaaja Alice saa nappulan (jonka hän arvostaa 1/3). Sitten kaksi muuta, Bob ja Charlie, jakavat loput reilusti heidän mielestään, mutta Alicen mielestä Bobin osuus on 2/3, kun taas Charlien osuus on 0. Osoittautuu, että Alice on kateellinen Bobille.

Yksinkertainen ratkaisu [3] on sallia palautus . Eli osallistuja, joka voitti nappulan pöytäkirjan "viimeinen vähentäjä" mukaan, ei poistu pelistä, vaan voi jäädä peliin ja osallistua seuraaviin vaiheisiin. Jos hän voittaa uudelleen, hänen on palautettava nykyinen palansa kakkuun. Varmistaaksemme protokollan päättymisen valitsemme jonkin vakion ja lisäämme säännön, jonka mukaan jokainen osallistuja voi palata peliin enintään kerran. $\varepsilon$ ${\tfrac {1}{\varepsilon }}$

Paluuversiossa jokaisella jäsenellä on menetelmä varmistaakseen, että se vastaanottaa palan, jonka arvo on vähintään yhtä suuri kuin suurin pala miinus . Menetelmä on seuraava: leikkaa aina nykyinen kappale pois niin, että jäljellä olevalla osalla on arvo plus nykyinen kappale. Tämä varmistaa, että palasi arvo kasvaa joka kerta kun voitat, ja kun et voita, voittajan arvo ei ylitä omaa arvoasi. Siten kateuden taso ei ylitä . $\varepsilon$ $\varepsilon$ $\varepsilon$ $\varepsilon$

Algoritmin ajoaika ei ylitä , koska vaiheita on enintään ja jokaisessa vaiheessa kyselyitä osallistujilta. ${\tfrac {n^{2}}{\varepsilon }}$ ${\tfrac {n}{\varepsilon ))$ $n$

Kateettoman approksimoinnin haittana on, että palat eivät välttämättä liity toisiinsa, koska palat palaavat jatkuvasti takaisin kakkuun ja jakautuvat uudelleen. Katso Jealous Cake Cutting#Connected Pieces muita ratkaisuja tähän ongelmaan.

Parannukset

Last Reducer -menettelyä parannettiin myöhemmin eri tavoin. Katso lisätietoja Suhteellinen jako - artikkelista .

Muistiinpanot

↑ Steinhaus, 1948 , s. 101-4.
↑ Dubins ja Spanier, 1961 , s. yksi.
↑ Brams ja Taylor 1996 , s. 130-131.

Kirjallisuus

Steven J. Brams, Alan D. Taylor. Reilu jako: kakun leikkaamisesta riitojen ratkaisuun . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .
Lester Eli Dubins, Edwin Henry Spanier. Kuinka leikata kakku reilusti // The American Mathematical Monthly. - 1961. - T. 68 , no. 1 . - doi : 10.2307/2311357 . — .
Hugo Steinhaus. Oikeudenmukaisen jaon ongelma // Econometrica. - 1948. - T. 16 , no. 1 . — .