Suhteellisen kakun leikkaamisen ongelma

Suhteellisen kakun leikkaamisen ongelma on eräänlainen oikeudenmukaisen kakun leikkaamisen ongelma . Tämä on heterogeenisen resurssin ("kakun") osio, joka täyttää suhteellisuuskriteerin , nimittäin sen, että kuka tahansa osallistuja uskoo, että hänelle osoitettu kakun osuus ei ole huonompi kuin 1/ n kakun kokonaisarviosta.

Kun puhutaan suhteellisuudesta , tehdään yleensä kaksi oletusta:

Osallistujien arvosanat eivät ole atomaarisia , eli positiivisella arvosanalla ei ole jakamattomia elementtejä.
Osallistujien pisteet ovat additiivisia , eli kun pala jaetaan, kappaleen pistemäärä on yhtä suuri kuin sen osien summa.

Menettelyt

Delhi-and-Choose -menettely on kahdelle henkilölle klassinen ratkaisu. Toinen henkilö jakaa resurssin kahteen puolikkaaseen, joita hän pitää tasa-arvoisina, ja toinen valitsee itselleen mieluisimman "puolikkaan". Ei-atominen oletus takaa, että leikkuri voi leikata (kuten hän ajattelee) kahteen yhtä suureen osaan. Summaisuusoletus takaa, että molempien osallistujien arviot ovat vähintään 1/2 kappaleilleen.

On monia tapoja laajentaa tämä menettely koskemaan yli 2 henkilöä. Jokaisella näistä menetelmistä on omat etunsa ja haittansa.

Yksinkertaiset menettelyt

Viimeinen miinus on aikaisin n ihmiselle kehitetty suhteellinen jakomenettely

Yhtä osallistujaa pyydetään valitsemaan teos, jonka hän arvioi 1/ n .
Muilla osallistujilla puolestaan on mahdollisuus vastustaa ja ilmoittaa, että pala on suurempi kuin 1/ n . Tässä tapauksessa häntä pyydetään pienentämään palaa niin, että hänen arvionsa mukaan kappaleen jäljellä oleva osa on 1/ n .
Viimeinen osallistuja, joka pienentää palan, saa sen.
Loput osallistujat jakavat loput kakusta samalla tavalla jäljellä olevien ihmisten kesken. $n-1$

Induktiolla voidaan todistaa, että jokainen osallistuja, joka noudattaa sääntöjä, saa taatusti 1/ n kakusta riippumatta muiden osallistujien toimista. Tämä on erillinen toimenpide, joka voidaan suorittaa kierroksina. Pahimmassa tapauksessa vaaditaan toimenpiteitä - yksi toiminto jokaiselle osallistujalle kullakin kierroksella. Suurin osa näistä toimista voidaan kuitenkin tehdä paperilla. Vain viiltoja todella tarvitaan. Siksi, jos kakku on yhdistetty, voidaan taata, että jokainen pala yhdistetään. $n\times (n-1)/2=O(n^{2})$ $n-1$

Menettely "Moving Knife" Dubins - Spanieron jatkuva versio "Last Reducingista" [1] .

Veitsi liikkuu torusta pitkin rinnakkain päästä toiseen.
Kilpailija sanoo "stop", kun hän katsoo, että veitsen vasemmalla oleva arvo on saavutettu . Kakunpala leikataan pois ja annetaan osallistujalle, joka sanoi. ${\tfrac {1}{n))$
Tämä toimenpide toistetaan muun kakun ja muiden osallistujien kanssa. Viimeinen osallistuja saa loput kakusta.

Fink-protokolla on algoritmi, joka jakaa edelleen riittävän pieniksi "samansuuriksi" paloiksi.

Ensimmäinen osallistuja jakaa resurssin osiin, joita hän pitää yhtäläisinä;
Toinen osallistuja valitsee puolet jättäen loput ensimmäiselle osallistujalle;
Kukin näistä kahdesta osallistujasta jakaa osuutensa kolmasosiksi;
Kolmas osallistuja valitsee tuloksena olevista osista kaksi - yhden ensimmäiseltä ja toiselta osallistujalta;
Jos osallistujia on neljä, kukin kolmesta ensimmäisestä osallistujasta jakaa osansa neljään osaan ja prosessi jatkuu.

Tämän protokollan etuna on, että se voidaan tehdä verkossa - kun uusia kumppaneita tulee peliin, olemassa oleva divisioona mukautetaan siihen ilman, että koko jakoprosessia tarvitsee aloittaa alusta. Tämän algoritmin haittana on, että jokainen osallistuja saa suuren määrän irrotettuja paloja yhden yhdistetyn palan sijaan.

Yksittäinen jako on yhden agentin suorittama yhtäläiseen jakoon perustuva menettely. Menetelmän etuna on, että se voidaan yleistääkakun symmetriseen tasaiseen leikkaamiseen.

Katso myös: [2] .

Rekursiivinen puolittaminen

Jaa ja hallitse -strategiaa käyttämällä voidaan saavuttaa suhteellinen jako ajassa [3] . Yksinkertaisuuden vuoksi tässä kuvattu menettely on annettu parilliselle osallistujamäärälle, mutta se voidaan helposti mukauttaa mihin tahansa osallistujamäärään: $O(n\log n)$

Jokaista osallistujaa pyydetään piirtämään viiva, joka jakaa kakun kahteen hänen mielestään vastaavaan osaan. Vaaditaan, että leikkaukset eivät leikkaa toisiaan. Helpoin tapa varmistaa tämä on sallia vain vaakaviivat tai vain pystysuorat viivat.
Algoritmi lajittelee n riviä nousevaan järjestykseen ja leikkaa kakun viivojen mediaanista . Jos esimerkiksi 4 osallistujaa piirtää viivoja pisteisiin ja , algoritmi leikkaa kakun pystysuunnassa kohdassa . $x=1,x=3,x=5$ $x=9$ $x=4$
Algoritmi määrittää kummallekin puolikkaalle n /2 osallistujaa - kumppaneita, joiden viivat ovat puolikkaan sisällä. Esimerkiksi jäsenet, jotka piirsivät viivoja pisteisiin , määrätään läntiseen puoliskoon, kun taas loput jäsenet määrätään itäiseen puoliskoon. Kukin puolisko jaetaan rekursiivisesti n /2 osallistujan kesken, jotka on määritetty kyseiselle puolikkaalle. $x=1$ $x=3$

Induktiolla voidaan osoittaa, että jokaiselle pelaajalle, joka pelaa sääntöjen mukaan, taataan nappula, jonka arvo on vähintään 1/ n , riippumatta siitä, miten muut pelaajat käyttäytyvät.

Jaa ja hallitse -strategian ansiosta iteraatioiden määrä on vain O(log n ), toisin kuin O( n ) -arvo Last Decreasing -proseduurissa. Jokaisella iteraatiolla jokaista osallistujaa veloitetaan yhden muistiinpanon tekemisestä. Siksi pisteiden kokonaismäärä on yhtä suuri kuin . $O(n\log n)$

Algoritmista on satunnaistettu versio, jonka avulla voidaan vähentää punkkien määrää. Katso artikkeli " Even-Paz Algorithm ".

Valintamenettelyt

Toinen lähestymistapa kakun leikkaamiseen on antaa kunkin osallistujan poimia tietty määrä palasia osallistujien lukumäärästä p ( n ) riippuen ja antaa kullekin osallistujalle yksi hänen valitsemistaan palasista, jotta palat eivät mene päällekkäin.

Yksinkertaisena esimerkkinä valintamenettelystä kuvittele kakku yksiulotteiseksi segmentiksi, ja jokainen osallistuja haluaa saada erillisen yhdistetyn segmentin. Käytämme seuraavaa protokollaa:

Jokainen osallistuja jakaa kakun yksityisesti n väliin, jotka hän pitää arvoltaan yhtäläisinä, kutsutaan näitä paloja ehdokkaiksi .
Pöytäkirja järjestää ehdokkaat itärajojen mukaiseen järjestykseen (lännestä itään) ja valitsee segmentin, jolla on läntisin itäpää. Tätä segmenttiä kutsutaan viimeiseksi kappaleeksi . $n^{2}$
Protokolla antaa päätekappaleen omistajalleen ja poistaa kaikki ehdokkaat, jotka leikkaavat sen kanssa. Vaihe 2 toistetaan sitten muiden osallistujien jäljellä oleville segmenteille . $n-1$

Vaiheen #2 valintasääntö varmistaa, että jokaisessa iteraatiossa enintään yksi segmentti kustakin osallistujasta poistetaan. Siksi jokaisen iteroinnin jälkeen segmenttien lukumäärä osallistujaa kohti pysyy yhtä suurena kuin osallistujien lukumäärä, ja prosessia voidaan jatkaa, kunnes kaikki osallistujat saavat segmentin [4] .

Tämä protokolla edellyttää, että jokainen osapuoli vastaa n kyselyyn, joten kyselyn monimutkaisuus on samanlainen kuin Last Decrease -menettelyssä. $O(n^{2})$

Satunnaistetut versiot

Voit käyttää satunnaistamista vähentääksesi pyyntöjen määrää. Ajatuksena on, että jokainen osallistuja ei raportoi koko joukkoa n ehdokasta, vaan vain vakiomäärän d satunnaisesti valittuja ehdokkaita. Kyselyn monimutkaisuus on O( n ), mikä on tietysti paras mahdollinen. Monissa tapauksissa on edelleen mahdollista antaa jokaiselle osallistujalle yksi ehdokas, joka ei mene päällekkäin muiden kanssa. On kuitenkin skenaarioita, joissa tällainen jakelu ei ole mahdollista.

Voimme leikata kakun O( n )-kyselyillä, jos teemme kompromissin:

Täyden suhteellisuuden takaamisen sijaan takaamme osittaisen suhteellisuuden , eli jokainen osallistuja saa tietyn vakio-osuuden f ( n ) kokonaisarvosta, missä . $f(n)<{\tfrac {1}{n))$
Sen sijaan, että välittäisimme kullekin osallistujalle erillisen yhdistetyn palan, välitämme osallistujalle yhden tai useamman ei-leikkaavan palan liitoksen.

Yleinen kaavio on seuraava [5] :

Jokainen osallistuja jakaa kakun yksityisesti samansuuruisiin osiin subjektiivisen arvionsa mukaan. Näitä kappaleita kutsutaan ehdokkaiksi . $n\cdot an$
Jokainen osallistuja valitsee 2 d ehdokasta tasaisesti satunnaisesti palautuksella. Ehdokkaat ryhmitellään d -pareihin, jotka osallistuja raportoi algoritmille. Näitä pareja kutsutaan neljännesvälieriksi . $n\cdot d$
Algoritmi valitsee jokaisesta neljännesfinaalisarjasta yhden kappaleen, sen, joka leikkaa vähiten muita ehdokkaita. Näitä kappaleita kutsutaan semifinaaliksi . $n\cdot d$
Algoritmi valitsee jokaiselle osallistujalle yhden kappaleen, kutsutaan sitä lopulliseksi . Lopulliset palat valitaan siten, että kakun jokainen kohta peittyy enintään kahdella loppupalalla (katso alla). Jos tämä onnistuu, siirry vaiheeseen 5. Jos se epäonnistuu, palaa vaiheeseen 1.
Jokainen kakun pala, joka kuuluu vain yhteen viimeiseen palaan, annetaan kyseisen palan omistajalle. Jokainen kakun osa, joka kuuluu kahteen viimeiseen palaan, jaetaan suhteellisesti millä tahansa deterministisellä suhteellisella jakoalgoritmilla.

Algoritmi takaa, että jokainen osallistuja saa todennäköisyydellä vähintään puolet yhdestä ehdokaskappaleestaan, mikä tarkoittaa (jos estimaatit ovat additiivisia), että arvio ei ole pienempi kuin 1/2 an . Vaiheessa #5 on O( n ) ehdokaspalaa ja O( n ) lisäjakoa, joista kukin vie O(1) aikaa. Siksi algoritmin kokonaisajoaika on O( n ). $O(1a^{2})$

Suurin ongelma tässä mallissa on viimeisten kappaleiden valinta vaiheessa #4. Katso tarkemmat tiedot Edmonds-Prus-protokollasta .

Tulokset vaikeusasteittain

Monimutkaisuuden tulokset on muotoiltu "standardin Robertson-Webb-mallin" mukaisesti, eli ne viittaavat menettelyihin, joissa käytetään kahden tyyppisiä toimia: "Arvio" ja "Leikkaus".

Jokaisessa osallistujien deterministisessä suhteellisessa jakomenettelyssä on käytettävä vähintään n toimintoa, vaikka kaikki pisteytysfunktiot olisivat identtisiä [3] . $n\geqslant 3$

Lisäksi minkä tahansa deterministisen tai satunnaistetun (todennäköisyyspohjaisen) suhteellisen jakoproseduurin, joka määrittää kullekin osallistujalle yhdistetyn kappaleen, on käytettävä toimintoja [6] . $\Omega (n\log n)$

Lisäksi minkä tahansa deterministisen suhteellisen jakoproseduurin on suoritettava toimenpiteitä, vaikka menettelyn sallittaisiin osoittaa kullekin osallistujalle pala, joka on segmenttien liitto, ja vaikka menettelyn sallitaan taata vain likimääräinen oikeudenmukaisuus . Todistus perustuu alarajaan, jonka mukaan on vaikea löytää yksittäisille pelaajille arvokas ja ohut kakkupala [7] [8] . $\Omega (n\log n)$

Näistä vaikeustuloksista seuraa, että rekursiivinen puolittaminen on nopein algoritmi täyden suhteellisuuden saavuttamiseksi yhdistettyjen kappaleiden kanssa, ja se on nopein mahdollinen deterministinen algoritmi osittaisen suhteellisuuden saavuttamiseksi myös irrotetuilla kappaleilla. Ainoa tapaus, jossa sitä voidaan parantaa, ovat satunnaistetut algoritmit, jotka takaavat osittaisen suhteellisuuden irrotettujen kappaleiden kanssa.

Jos pelaajat pystyvät leikkaamaan vain rajallisella tarkkuudella, niin alaraja sisältää myös satunnaistetut protokollat [7] [8] . $\Omega (n\log n)$

Seuraava taulukko sisältää tunnetut tulokset [5] :

Suhteellisuus ( täysi / osittainen)	Kappaleet (yhdistetty/ irrotettu)	Protokollatyyppi (deterministinen / satunnaistettu )	Kyselyt (tarkka/ likimääräinen)	Pyyntöjen määrä
saattaa loppuun	lähettiläitä	deterministinen	tarkka	$O(n\log n)$ [3] [6] $\Omega (n\log n)$
saattaa loppuun	lähettiläitä	deterministinen	lähentää	$\Omega (n\log n)$ [6]
saattaa loppuun	lähettiläitä	satunnaistettu	tarkka	$O(n\log n)$ [3] [6] $\Omega (n\log n)$
saattaa loppuun	lähettiläitä	satunnaistettu	lähentää	$\Omega (n\log n)$ [6]
saattaa loppuun	sekava	deterministinen	tarkka	$O(n\log n)$ [3] [7] [8] $\Omega (n\log n)$
saattaa loppuun	sekava	deterministinen	lähentää	$\Omega (n\log n)$ [7] [8]
saattaa loppuun	sekava	satunnaistettu	tarkka	$O(n\log n)$ [3]
saattaa loppuun	sekava	satunnaistettu	lähentää	$\Omega (n\log n)$ [7] [8]
osittainen	lähettiläitä	deterministinen	tarkka	$\Omega (n\log n)$ [3] [7] [8] $\Omega (n\log n)$
osittainen	lähettiläitä	deterministinen	lähentää	$\Omega (n\log n)$ [7] [8]
osittainen	lähettiläitä	satunnaistettu	tarkka	$\Omega (n\log n)$ [3]
osittainen	lähettiläitä	satunnaistettu	lähentää	$\Omega (n\log n)$ [7] [8]
osittainen	sekava	deterministinen	tarkka	$O(n\log n)$ [3] [7] [8] $\Omega (n\log n)$
osittainen	sekava	deterministinen	lähentää	$\Omega (n\log n)$ [7] [8]
osittainen	sekava	satunnaistettu	tarkka	O( n ) [5]
osittainen	sekava	satunnaistettu	heikosti likimääräinen ( arviointivirheestä riippumaton )	O( n ) [5]
osittainen	sekava	satunnaistettu	lähentää	$\Omega (n\log n)$ [7] [8]

Vaihtoehdot

Eräänlaisia jakoja

Suhteellisuustesti voidaan yleistää tilanteeseen, jossa osallistujien erääntyvät osuudet eivät ole yhtä suuret. Esimerkiksi resurssin voi omistaa kaksi osakkeenomistajaa, Alice omistaa osakkeita ja George omistaa . Tämä johtaa painotettuun suhteellisuuskriteeriin (WPR) - on joitain painoja w i , joiden summa on 1, ja jokaisen osallistujan i on saatava oman arvionsa mukaan vähintään osuus w i resurssista. WPR-jaon löytämiseen voidaan käyttää useita algoritmeja. Suurin ongelma on, että leikkausten määrä voi olla suuri, vaikka osallistujia olisi vain kaksi. Katso Kakun oikeasuhteinen leikkaaminen eri osuuksilla . ${\tfrac {8}{13}}$ ${\tfrac {5}{13}}$

Supersuhteellinen jako

Supersuhteellinen jako on jako, jossa kukin osallistuja saa tiukasti enemmän kuin 1/ n resurssista oman subjektiivisen arvionsa mukaan.

Tällaista jakoa ei tietenkään aina ole olemassa – jos kaikilla osallistujilla on täsmälleen samat arviointitoiminnot, paras, mitä voimme tehdä, on antaa kaikille tasan 1/ n . Näin ollen supersuhteellisen jaon olemassaolon välttämätön edellytys on vaatimus, että kaikilla osapuolilla ei ole samaa arvostusta.

Yllättäen tämäkin ehto riittää, jos arviointifunktiot ovat additiivisia eivätkä atomisia. Eli jos osallistujia on vähintään kaksi , joiden arviointifunktiot eroavat vain hieman, on olemassa supersuhteellinen jako, jossa kaikki osallistujat saavat enemmän kuin 1/ n . Katso Super Proportational Division lisätietoja varten.

Naapuruston rajoitukset

Tavanomaisen rajoituksen lisäksi, että kaikki osat on yhdistettävä, on joissakin tapauksissa lisärajoituksia. Erityisesti silloin, kun jaettava kakku on kiistanalainen alue, joka sijaitsee useiden maiden välillä, jokaisen maalle annettavan palan voidaan vaatia olevan maan nykyisen rajan vieressä. Suhteellinen jako on tässä tapauksessa aina olemassa ja se voidaan löytää yhdistämällä Last Decrease - protokolla geometrisiin tekniikoihin , joissa käytetään konformisia kartoituksia . Katso artikkeli " Hill-Beckin maanjakoongelma ".

2D geometriset rajoitukset

Kun "kakku" jaetaan kaksiulotteiseen tilaan (tasoon), kuten jaettaessa tontteja tai mainostilaa painetussa tai sähköisessä mediassa, vaaditaan usein, että palat täyttävät liitettävyyden lisäksi joitain geometrisia rajoituksia. Voidaan esimerkiksi vaatia, että jokainen pala on neliö, paksu suorakaide (eli pituus ja leveys eivät eroa useita kertoja) tai yleismuotoinen paksu kuvio . Tällaisten lukurajoitusten ollessa kyseessä suhteellinen jako ei yleensä ole olemassa, mutta osittain suhteellinen jako on yleensä olemassa ja se voidaan löytää tehokkailla algoritmeilla [9] .

Taloudellisesti tehokas jako

Suhteellisuuden lisäksi usein edellytetään, että jako on taloudellisesti tehokas , eli maksimoimaan kokonaishyödyn (määriteltynä kaikkien toimijoiden hyötyjen summana).

Ajatellaan esimerkiksi kakkua, joka sisältää 500 grammaa suklaata ja 500 grammaa vaniljaa ja jonka jakaa kaksi osallistujaa, joista toinen haluaa vain suklaata ja toinen vaniljaa. Monet kakunleikkausprotokollat antavat kullekin agentille 250 grammaa suklaata ja 250 grammaa vaniljaa. Tämä jako on suhteellinen, koska jokainen osallistuja saa 0,5 kokonaisarvosta, joten normalisoitu kokonaishyöty on 1. Tämä jako on kuitenkin erittäin tehoton, koska voimme antaa koko suklaaosan ensimmäiselle osallistujalle ja koko vaniljaosan. toiselle osallistujalle normalisoidun kokonaisedun 2.

Optimaalinen suhteellinen jakoongelma on ongelma löytää suhteellinen osio, joka maksimoi kokonaishyödyn kaikista mahdollisista suhteellisista jakaumista. Tällä hetkellä ongelmalla on ratkaisu vain hyvin erikoisiin kakkuihin, kun kyseessä on yksiulotteinen segmentti ja hyötytiheysfunktiot ovat lineaarisia (eli ). Yleensä ongelma on NP - vaikea . Jos hyödyllisyysfunktioita ei ole normalisoitu (eli annamme jokaiselle osallistujalle eri estimaatit kakun kokonaismerkittävyydestä), ongelma on NP-kova jopa kertoimella [10] . $u(x)=Ax+B$ ${\displaystyle {\tfrac {1}{\sqrt {n))))$

Reilu jako

Reiluus ei ole jaon ominaisuus, vaan pikemminkin protokollan ominaisuus. Kaikki suhteelliset jakoprotokollat ovat heikosti oikeudenmukaisia siinä mielessä, että jokainen todellisen arvonsa mukaan toimiva osallistuja saa taatusti vähintään 1/ n (tai 1/ an , jos kyseessä on osittain suhteellinen protokolla) riippumatta siitä, miten muut osallistujat käyttäytyvät. Vaikka muut jäsenet muodostaisivat liittouman vain vahingoittaakseen häntä, hän saa silti taatun osuutensa [11] .

Useimmat protokollat eivät kuitenkaan ole täysin oikeudenmukaisia siinä mielessä, että joillakin osallistujilla saattaa olla kannustimia valehdella saadakseen jopa enemmän kuin hänelle on taattu. Tämä pätee jopa yksinkertaiseen jakaa ja valitse -protokollaan – jos leikkuri tietää valitsijan mieltymykset, hän voi leikata pois palan, jonka valitsija arvostaa hieman alle 1/2, mutta jonka leikkuri itse arvostaa reilusti yli. 1/2.

On olemassa oikeudenmukaisia mekanismeja täydellisen osion saamiseksi . Koska täydellinen jako on suhteellinen, nämä mekanismit ovat myös oikeudenmukaisia suhteellisia jakomekanismeja.

Näitä mekanismeja voidaan laajentaa supersuhteellisen jaon saamiseksi , jos sellainen on olemassa [12] :

Pyydämme jokaista osallistujaa toimittamaan täydellisen arvioinnin.
Valitsemme satunnaisen osion (katso lisätietoja Mosselin ja Tamuzin artikkelista [12] ).
Jos satunnaisosio osoittautuu raportoitujen mittojen mukaan supersuhteelliseksi, suoritamme sen. Muussa tapauksessa käytämme oikeudenmukaista mekanismia varmistaaksemme täydellisen jaon.

Jos supersuhteellinen jako on olemassa, on positiivinen mahdollisuus, että se saadaan vaiheessa 2. Siksi minkä tahansa rehellisen osallistujan odotusarvo on ehdottomasti suurempi kuin 1/ n . Ymmärtääksesi, että mekanismi on oikeudenmukainen, harkitse kolmea tapausta: (a) Jos valittu osio on todellakin supersuhteellinen, niin ainoa mahdollinen seuraus valehtelusta on huijata mekanismi ajattelemaan, että osio ei ole supersuhteellinen. Tämä pakottaa mekanismin soveltamaan täydellistä jakoa, mikä on pahempaa kaikille mukana oleville, mukaan lukien roistolle. (b) Jos valittu osio ei ole supersuhteellinen vain siksi, että valehtelija määrittelee 1/ n tai vähemmän, valehtelun ainoa vaikutus on saada kone ajattelemaan osion olevan supersuhteellinen ja käyttämään sitä, mikä vahingoittaa vain valehtelijaa itseään. (c) Jos valittu jako ei todellakaan ole supersuhteellinen, mikä antaa toiselle osapuolelle arvon 1/ n tai vähemmän, väärällä ei ole vaikutusta, koska jakoa ei käytetä ollenkaan.

Suhteellinen työnjako

Jos jaettava resurssi on ei-toivottu (samanlainen kuin työnjako ), suhteellinen jako määritellään jaoksi, joka antaa kullekin henkilölle enintään 1/ n resurssista (eli eriarvoisuusmerkki toiseen suuntaan).

Useimmat suhteelliset jakoalgoritmit voidaan mukauttaa tehtävien jakamiseen ilman vaikeuksia.

Katso myös

Tarkka jako . Katso myös "Täydellinen jako"

Muistiinpanot

↑ Dubins ja Spanier, 1961 , s. 1–17.
↑ Tasnadi, Attila. Uusi menetelmä, joka on verrannollinen n-henkilön kakunleikkausongelmaan . tutkimusportti. Haettu: 24.9.2015. (määrätön)
↑ 1 2 3 4 5 6 7 8 9 Even, Paz, 1984 , s. 285.
↑ Tämä menettelyn osa on samanlainen kuin ahne polynomiratkaisu )
↑ 1 2 3 4 Edmonds, Pruhs, 2006 , s. 623–634.
↑ 1 2 3 4 5 Woeginger, 2007 , s. 213-220.
↑ 1 2 3 4 5 6 7 8 9 10 11 Edmonds, 2006 , s. 271-278.
↑ 1 2 3 4 5 6 7 8 9 10 11 Edmonds, 2011 , s. 1–12.
↑ Segal-Halevi, Nitzan, Hassidim, Aumann, 2017 , s. 1–28.
↑ Bei, Chen, Hua ym., 2012 .
↑ Steinhaus, 1948 , s. 101-4.
↑ 1 2 Mossel, Tamuz, 2010 , s. 288–299.

Kirjallisuus

Yleiskatsaus suhteellisista ja muista jaoista ilmestyi artikkelissa:
Austin AK jakaa kakun // The Mathematical Gazette. - 1982. - T. 66 , no. 437 . — S. 212–215 . - doi : 10.2307/3616548 . — .
Lester Eli Dubins, Edwin Henry Spanier. Kuinka leikata kakku reilusti // The American Mathematical Monthly. - 1961. - T. 68 , no. 1 . - doi : 10.2307/2311357 . — .
Even S., Paz A. Huomautus kakun leikkaamisesta // Discrete Applied Mathematics. - 1984. - T. 7 , no. 3 . - doi : 10.1016/0166-218x(84)90005-2 .
Jeff Edmonds, Kirk Pruhs. Balanced Allocations of Cake // 2006 47. vuotuinen IEEE-symposium tietojenkäsittelytieteen perusteista (FOCS'06). - 2006. - ISBN 978-0-7695-2720-8 . - doi : 10.1109/focs.2006.17 .
Gerhard J. Woeginger. Kakun leikkaamisen monimutkaisuudesta // Discrete Optimization. - 2007. - T. 4 , no. 2 . - doi : 10.1016/j.disopt.2006.07.003 .
Jeff Edmonds. Kakun leikkaaminen ei todellakaan ole pala kakkua // Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm - SODA '06. - 2006. - ISBN 978-0898716054 . doi : 10.1145 / 1109557.1109588 .
Jeff Edmonds. Kakun leikkaaminen ei todellakaan ole pala kakkua // ACM Transactions on Algorithms. - 2011. - T. 7 , no. 4 . - doi : 10.1145/2000807.2000819 .
Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, Yonatan Aumann. Reilu ja tasainen: Kakun leikkaaminen kahdessa ulottuvuudessa // Journal of Mathematical Economics. - 2017. - T. 70 . - doi : 10.1016/j.jmateco.2017.01.007 . - arXiv : 1409.4511 .
Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, Endong Yang. Optimaalinen suhteellinen kakun leikkaaminen yhdistetyillä paloilla // AAAI Conference Proceedings. – 2012.
Hugo Steinhaus. Oikeudenmukaisen jaon ongelma // Econometrica. - 1948. - T. 16 , no. 1 . — .
Elchanan Mossel, Omer Tamuz. Truthful Fair Division // . - 2010. - T. 6386. - (Luentomuistiinpanot tietojenkäsittelytieteestä). - ISBN 978-3-642-16169-8 . - doi : 10.1007/978-3-642-16170-4_25 .