"yksittäinen jako" -menettely

" Yksittäinen jakaminen " on suhteellinen 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. Toimenpide sallii n henkilön jakaa kakun keskenään niin, että jokainen osallistuja saa vähintään täyden arvon oman (subjektiivisen) arvionsa mukaan.

Menetelmän on kehittänyt Hugo Steinhaus n = 3 henkilölle [1] . Harold Kuhn laajensi sitä myöhemmin arvolla n > 3 käyttämällä Frobenius-Koenigin lausetta [2] . Tapaukset n =3 ja n =4 on kuvattu Brahmsin ja Taylorin artikkelissa [3] , ja yleinen tapaus on kuvattu Robertsonin ja Webbin artikkelissa [4] .

Kuvaus

Mukavuuden vuoksi normalisoimme osallistujien pisteet siten, että koko kakun pistemäärän arvo on n kaikille osallistujille. Tavoitteena on antaa jokaiselle osallistujalle arvo, joka on vähintään 1.

Vaihe 1 . Yksi pelaaja valitaan satunnaisesti, jota kutsumme jakamiseksi , ja hän jakaa kakun n osaan, joista jokainen on hänen silmissään täsmälleen yhden arvoinen.

Vaihe 2 . Jokainen muu n -1 osallistuja arvioi tuloksena saadut n kappaletta ja raportoi, mitä niistä hän pitää "hyväksyttävänä", eli vähintään 1:n arvoisena.

Nyt vastauksista riippuen peli siirtyy vaiheeseen 3. Esitetään tapaus n = 3 ja sitten yleinen tapaus.

Steinhaus-proseduuri kohteelle n =3

Tapauksia on kaksi.

• Tapaus A: Ainakin yksi ei-jakajista merkitsee kaksi tai useampia paloja hyväksyttäviksi. Sitten kolmas osallistuja ottaa hyväksyttävän palan ( Dirichlet-periaatteen mukaan tulee olla vähintään yksi), toinen osallistuja ottaa hyväksyttävän palan (hän ​​merkitsi kaksi, joten vähintään yksi jää jäljelle) ja jakaja ottaa jäljellä olevan palan ( jakaja kaikki palat ovat hyväksyttäviä).
• Tapaus B: Molemmat muut osallistujat merkitsivät vain yhden hyväksyttävän kappaleen. Sitten on ainakin yksi kappale, joka on hyväksyttävä vain jakajalle. Jakaja ottaa tämän palan ja menee kotiin. Tämä pala on alle 1 arvoinen kahdelle jäljellä olevalle osallistujalle, joten loput kaksi kappaletta ovat vähintään 2 arvoisia yhdessä heille. He jakavat loppuosan käyttämällä " Jaa ja valitse " -menettelyä.

Menettely mille tahansa n

On olemassa useita tapoja kuvata yleistä tapausta. Lyhin kuvaus on annettu Segal-Halevin ja Aiger-Khorevin artikkelissa [5] . Se perustuu kateudettoman sovituksen konseptiin, jossa yhteensopimatonta ainetta ei ole yhteensopivan kappaleen vieressä.

Vaihe 3 Rakennamme kaksiosaisen graafin , jossa jokainen X :n kärki on agentti, ja jokainen Y :n kärki on kakkupala, ja reuna yhdistää agentin X ja palan Y jos ja vain jos X arvioi Y :n vähintään 1:ksi.

Vaihe 4 Löydämme suurimman kardinalisuuden (yhdistelmien lukumäärän mukaan) sopivan ilman kateutta G :ssä . Huomaa, että jakaja on kytketty kaikkiin n kappaleeseen, joten (missä on X : n naapurijoukko Y :ssä ). Siksi on olemassa ei-tyhjä kateudeton vastaavuus.

Vaihe 5 Annamme jokaisen palan parista vastaavalle agentille (eli samasta parista sovituksessa). Huomaa, että jokainen tällainen agentti arvioi arvonsa vähintään 1:ksi, joten se voi mennä kotiin onnellisena.

Vaihe 6 Jaamme rekursiivisesti jäljellä olevan kakun jäljellä oleviin aineisiin. Huomaa, että kukin jäljellä olevista agenteista arvioi annetut palat pienemmiksi kuin 1, joten jäljellä olevan kakun estimaatti ei ole pienempi kuin agenttien lukumäärä, ja siksi rekursion ehto täyttyy.

Katso myös

• Muita menetelmiä saman ongelman ratkaisemiseksi löytyy artikkelista " Suhteellisen kakun leikkaamisen ongelma ".
• Yksi "yksittäisjako"-menettelyn eduista on, että sitä voidaan muokata symmetrisen reilun kakunleikkausmenetelmän saamiseksi .

Muistiinpanot

1. ↑ Steinhaus, 1948 , s. 101-4.
2. ↑ Kuhn, 1967 , s. 29–37.
3. ↑ Brams ja Taylor 1996 , s. 31-35.
4. ↑ Robertson, Webb, 1998 , s. 83-87.
5. ↑ Segal-Halevi, Aigner-Horev, 2019 .

Kirjallisuus

• Steven J. Brams, Alan D. Taylor. Reilu jako: kakun leikkaamisesta riitojen ratkaisuun . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .
• Hugo Steinhaus. Oikeudenmukaisen jaon ongelma // Econometrica. - 1948. - T. 16 , no. 1 . — .
• Harold Kuhn. Reilun jaon peleistä // Essays in Mathematical Economics in Honor of Oskar Morgenstern . — Princeton University Press, 1967. Arkistoitu 16. tammikuuta 2019 Wayback Machinessa
• Erel Segal-Halevi, Elad Aigner-Horev. Kadeteettomat vastaavuudet kaksiosaisissa kaavioissa ja niiden sovellukset oikeudenmukaiseen jakoon  . — 2019.
• Jack Robertson, William Webb. Kakunleikkausalgoritmit: Ole reilu, jos voit. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .