Tarkka jako

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9. tammikuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Täsmällinen jako , jota kutsutaan myös tasajaoksi tai sovituksi jakoksi , on heterogeenisen resurssin (esimerkiksi kakun ) jakaminen useisiin osajoukkoihin siten, että jokainen eri makuista ihmisistä on samaa mieltä kappaleiden arvioinnista [1 ] .

Harkitse kakkua, joka on puoliksi suklaata ja puoliksi vaniljaa. Alice haluaa vain suklaaosan, ja George tarvitsee vain vaniljaa. Kakku on jaettu kolmeen osaan: yksi pala on 20 % suklaata ja 20 % vaniljaa, toinen osa on 50 % suklaata ja 50 % vanilja ja kolmas osa sisältää loput kakusta. Tämä jako on johdonmukainen, koska sekä Alice että George arvostavat kolme osaa 20%, 50% ja 30%.

Kuten esimerkki osoittaa, sovittu jako ei välttämättä ole oikeudenmukainen. Jos esimerkiksi 20 prosentin pala annetaan Alicelle ja 50 prosentin pala Georgelle, tämä ei selvästikään ole reilua Alicea kohtaan. Kakkuleikkausteoriassa johdonmukaisia jakoja käytetään usein osamenettelyinä oikeudenmukaisten jakojen luomiseksi.

Sovitut jaot ovat aina olemassa, mutta niitä ei voida löytää erillisillä protokollilla (äärisellä määrällä pyyntöjä). Joissakin tapauksissa tarkat jaot voidaan löytää siirtämällä veitsiä koskevia protokollia. Melkein tarkat jaot voidaan löytää erillisillä protokollilla.

Määritelmät

Olkoon k painoa, joiden summa on 1. Oletetaan, että kaikki osallistujat arvostavat koko kakun C arvolla 1. ${\displaystyle w_{1},w_{2},\ldots ,w_{k))$

Suhteen tarkka jako (tai johdonmukainen jako ) tarkoittaa kakun jakamista k osaan: , joten mille tahansa jäsenelle i ja mille tahansa kappaleelle j : ${\displaystyle w_{1},w_{2},\ldots ,w_{k))$ ${\displaystyle C=X_{1}\sqcup \cdots \sqcup X_{k))$

V_{i}(X_{j})=w_{j}

Eli kaikki osallistujat ovat yhtä mieltä siitä, että palan j arvo on täsmälleen [1] . ${\displaystyle w_{j))$

Melkein tarkka jako

Minkä tahansa suhteen -lähes tarkka jako on jako, jossa $\varepsilon >0$ $\varepsilon$ ${\displaystyle w_{1},w_{2},\ldots ,w_{k))$

|V_{i}(X_{j})-w_{j}|<\varepsilon

Eli kaikki osallistujat ovat yhtä mieltä siitä, että palan j arvo on lähes täsmälleen sama ja ero on pienempi kuin [1] . ${\displaystyle w_{j))$ $\varepsilon$

Täydellinen jako

Täydellinen jako on jako, jossa resurssi jaetaan n osallistujan kesken subjektiivisilla arvioilla, jolloin kullekin osallistujalle annetaan tasan 1/ n resurssista kaikkien osallistujien arvioiden mukaan. Tämä on tarkan jaon erikoistapaus, jossa kaikki painot ovat 1/ n .

Tarkka jako mielivaltaisella määrällä leikkauksia

Palloittain homogeeninen kakku, paljon osallistujia, mikä tahansa paino

Kakkua kutsutaan paloittain homogeeniseksi , jos se voidaan jakaa R - alueisiin siten, että kaikki osallistujat ovat yhtä mieltä siitä, että arvomitan tiheysarvo kullakin alueella on homogeeninen. Harkitse esimerkiksi pyöreää kakkua, jonka neljässä neljäsosassa on erilaisia koristeita (kerma, kuorrutus, hedelmät ja suklaa). Kilpailijat voivat arvioida jokaista koristelutyyppiä eri tavalla, mutta he eivät erottele eri kakkupaloja, joissa on sama koriste. Tämä tarkoittaa, että kunkin palan arvo kullekin osallistujalle riippuu vain summasta , jonka he saavat kultakin alueelta.

Väite, että kakku on paloittain homogeeninen, vastaa väitettä, että jaon eri osallistujien estimaatit ovat paloittain vakioita - jokainen kakun pala on homogeeninen silloin ja vain, jos se on n kappaleen leikkauskohta n osallistujasta.

Kun kakku on palasittain homogeeninen (ja arviot ovat paloittain vakioita), voidaan saada johdonmukainen jako seuraavasti:

Jaetaan kukin alue k ala-alueeseen siten, että osa-alue j sisältää täsmälleen kyseiset alueet. ${\displaystyle w_{j))$
Olkoon pala j kaikkien R - alueiden j :nnen osa-alueen liitto . Tämä määrittää johdonmukaisen jaon annetuille painoille.

Tämä algoritmi voidaan yleistää hieman yleisempään arvomittareiden perheeseen, kuten paloittain lineaarisiin mittauksiin [2] .

Vaadittujen leikkausten määrä on , jossa R on yhtä suuri kuin alueiden lukumäärä. $kR$

Yleinen kakku, paljon osallistujia, mikä tahansa paino

Jos kustannusmitat ovat laskettavasti additiivisia ja atomittomat , niin johdonmukainen osio on olemassa jokaiselle painojoukolle, jonka summa on 1. Tämä on seurausta Dubins-Spanierin konveksiteettilauseesta .

Woodall [3] osoitti, että on mahdollista rakentaa tällainen osio intervallikakulle laskettavaksi intervalliliitoksi.

Piirros: Harkitse yllä kuvattua jakomenettelyä homogeenisille paloille. Yleensä kakku ei ole paloittain homogeeninen. Koska hintamittaukset ovat kuitenkin jatkuvia, kakku on mahdollista jakaa yhä pienemmiksi alueiksi siten, että alueet muuttuvat yhä yhtenäisemmiksi. Kun tämä prosessi konvergoi sovittuun jakoon. $R\to \infty$

Fremlin osoitti, että on mahdollista rakentaa tällainen jako intervallien äärelliseksi liitoksiksi.

Stromquist ja Woodall [4] ovat osoittaneet, että tämä on mahdollista minimimäärällä intervalleja, katso Stromquist-Woodallin lause .

Tarkka jako vähimmäismäärällä leikkauksia

Oletetaan, että kakku on intervalli, joka koostuu n :stä eri osavälistä, ja jokainen n osallistujasta arvioi vain yhden alueen. Sitten kakun johdonmukainen jakaminen k osajoukkoon vaatii leikkauksia, koska jokainen alue on leikattava k kappaleeseen, jotka ovat yhtä suuret tätä aluetta arvioivan osallistujan silmissä. Siksi on mielenkiintoinen kysymys siitä , onko aina mahdollista saada johdonmukainen jako tällä tarkalla leikkausmäärällä. $n\cdot (k-1)$

Välikakku, kaksi osallistujaa, monia osajoukkoja, mitkä tahansa painot

Kaksi osallistujaa voi saavuttaa sovitun jaon käyttämällä Austinin Moving Knife -menettelyä .

Yksinkertaisin tapaus on painot 1/2, mikä tarkoittaa, että he haluavat leikata kakun niin, että molemmat sopivat saavansa puolet kakun arvosta. Tämä tehdään seuraavalla tavalla. Toinen osallistujista siirtää kahta veistä kakun päällä vasemmalta oikealle pitäen aina veitsien välisen arvon täsmälleen yhtä suurena kuin 1/2. Voidaan todistaa ( väliarvolauseella ), että jossain vaiheessa veitsien välinen arvo on myös toiselle osallistujalle tasan 1/2. Toinen osallistuja huutaa "seis!" tässä vaiheessa pala leikataan pois.

Samaa protokollaa voidaan käyttää nappulan katkaisemiseen, josta molemmat pelaajat ovat yhtä mieltä siitä, että sen arvo on täsmälleen . $1/n$

Yhdistämällä useita tällaisia kappaleita saat johdonmukaisen jaon kaikille suhteille, jotka ovat rationaalilukuja . Tämä voi kuitenkin vaatia suuren määrän viiltoja.

Parempi tapa saada johdonmukainen jako on tunnistaa kakun kaksi päätepistettä, jotta sitä voidaan pitää ympyränä. Eli kun oikea veitsi saavuttaa oikean pään, se menee välittömästi vasempaan päähän ja veitsien välistä kappaletta pidetään nyt oikean veitsen oikealla puolella olevan kappaleen liitoksena (joka oli vasen veitsi ennen) ja vasemman veitsen vasemmalla puolella oleva pala (joka oli oikea veitsi ennen). ). Sitten voimme löytää johdonmukaisen jaon mille tahansa . Yksi osallistuja liikuttaa veitsiä syklisesti kakun ympärillä pitäen niiden välisen arvon aina täsmälleen yhtä suurena kuin p . Voidaan todistaa, että jossain vaiheessa veitsien välinen arvo toiselle osallistujalle tulee täsmälleen yhtä suureksi kuin p [5] . Toinen osallistuja huutaa "seis!" tässä vaiheessa pala leikataan pois. Se vaatii vain kaksi leikkausta. $p\in [0,1]$

Toistamalla yllä oleva menettely voidaan saavuttaa johdonmukainen jako kahdelle osallistujalle mille tahansa alajoukolle. Leikkausten määrä on , jossa on yhtä suuri kuin osajoukkojen määrä. $2(k-1)$ $k$

Vuodesta 2015 lähtien ei ollut tiedossa tämän liikkuvan veitsen menettelyn yleistämistä yli 2 osallistujalle [6] .

Välikakku, monta osallistujaa, kaksi alajoukkoa, yhtä suuret painot

Oletetaan, että kakku on väli, jonka kokonaisarvo on 1. Se tulisi jakaa osajoukkoon, joista jokaisen arvo on tasan 1/2 kaikille n osallistujalle. Haluamme käyttää vähimmäismäärää leikkauksia, joka on . $k = 2$ $n(k-1)=n$

Tällainen jako on aina olemassa [7] . Tämä on suora seuraus Hobby-Rice-lauseesta . Tämä voidaan osoittaa myös Borsuk-Ulam-lauseen [8] perusteella :

Mikä tahansa leikkauksia käyttävä intervallin osio voidaan esittää pituusvektorina , jossa elementit ovat osavälien pituuksia. $n$ $n+1$
Mikä tahansa vektorin elementti voi olla joko positiivinen (jos se kuuluu osaan #1) tai negatiivinen (jos se kuuluu osaan #2).
Kaikkien osioiden joukko on pallo . $S^{n}$
Määrittele seuraavasti: mille tahansa osiolle x on vektori , jonka i . elementti on tämän osion kappaleen #1 arvo osallistujan i mukaan miinus 1/2. $V:S^{n}\to \mathbb {R} ^{n}$ $V(x)$
Funktio V on jatkuva. Lisäksi kaikille x . $V(x)+V(-x)=0$
Siksi Borsuk-Ulam-lauseen mukaan on olemassa x sellainen, että . Tässä jaossa kaikki osallistujat arvostavat palan #1 (ja kappaleen #2) tasan 1/2. $V(x)=0$

Johdonmukainen jako kahteen osajoukkoon löytyy Tuckerin lemman perusteella, joka on Borsuk-Ulam-lauseen diskreetti versio [9] .

Vaikka osallistujien mieltymykset mallinnetaan mitoilla, todistukset eivät edellytä, että arvostusmitat ovat osajoukon additiivisia. Arvioiden suuret voivat olla myös jatkuvia funktioita joukoissa, jotka on määritelty Borelin täydellisillä algebroilla ja jotka täyttävät kaikki mittojen ominaisuudet lukuun ottamatta laskettavaa additiivisuutta. Tällöin ei vaadita, että kakun osajoukkojen jäsenten pisteet ovat additiivisesti erotettavissa [9] .

Välikakku, monta osallistujaa, monia osajoukkoja, yhtä suuret painot

Edellisen osan olemassaololause voidaan yleistää kappaleista mielivaltaiseen määrään kappaleita. Tämän todisti Noga Alon vuoden 1987 paperissaan kaulakorun jakautumisesta . $k = 2$

Välillä on useita mittauksia, jotka kaikki ovat pituuden suhteen ehdottoman jatkuvia. Koko kaulakorun mitta mitatun mukaan on yhtä suuri kuin . Sitten on mahdollista jakaa väli osiin (ei välttämättä jatkuviin) siten, että kunkin osan arvo mittauksen mukaan on täsmälleen yhtä suuri kuin . Leikkauksia ei tarvita enempää ja tämä arvo on optimaalinen. $n$ $i$ ${\displaystyle k\cdot a_{i))$ $k$ $i$ $a_{i}$ ${\näyttötyyli (k-1)n}$

Intervallikakku, monta osallistujaa, kaksi osajoukkoa, mielivaltaiset painot

Edellisen osan olemassaololause on yleistetty mielivaltaisiin painoihin Stromquist-Woodallin lauseella .

Moniulotteinen kakku, paljon osallistujia, monia osajoukkoja, yhtäläiset painot

Stone-Tukey- lauseessa sanotaan, että kun n - ulotteisessa avaruudessa on n mitattavissa olevaa "objektia" , ne voidaan puolittaa kaikki (niiden mittojen eli tilavuuden mukaan) yhdellä ( n − 1) -ulotteisella hypertasolla .

Toisin sanoen: jos kakku on välilyönti ja osallistujien arviot ovat äärelliset ja yhtä suuret kuin nolla millä tahansa -ulotteisella hypertasolla, niin on olemassa puoliavaruus , jonka arvo on tasan 1/2 jokaiselle osallistujalle. Siksi on olemassa johdonmukainen jako yksikköleikkauksella . $\mathbb {R} ^{n}$ $n-1$

Tämän lauseen alkuperäinen versio toimii vain, jos kakun lukumäärä on yhtä suuri kuin osallistujien lukumäärä. Esimerkiksi tätä lausetta ei voida soveltaa kolmiulotteisen voileivän jakamiseen neljään osanottajaan.

On kuitenkin yleistyksiä, jotka sallivat tällaisen jaon. He eivät käytä hypertasoveistä, vaan käyttävät monimutkaisempia polynomipintoja [10] .

Melkein tarkat jakomenettelyt

Muru ja pakkaa -menettely

Tietystä kohdasta voit antaa kullekin osallistujalle palan siten, että kaikki osallistujat uskovat, että kaikki arvot eroavat vähemmän kuin , eli mille tahansa i :lle ja mille tahansa j :lle [1] : $\varepsilon >0$ $\varepsilon$

|V_{i}(X_{j})-w_{j}|<\varepsilon

Lähes tarkassa jakomenettelyssä on kaksi vaihetta: murskaus ja pakkaus .

Murenemisvaihe : Tavoitteena on leikata kakku pieniksi paloiksi ("muruiksi") siten, että jokainen kilpailija antaa jokaiselle murulle riittävän pienen arvon. Tämä tehdään seuraavalla tavalla. Olkoon k jokin vakio. Pyydetään osallistujaa 1 leikkaamaan kakku k osaan niin, että kunkin palan hinta on 1/ k . Pyydetään osallistujaa nro 2 jakamaan palat (enintään k -1 leikkauksella) niin, että kunkin palan hinta on enintään 1/ k . Näiden uusien kappaleiden arvo on tietysti edelleen enintään 1/ k osallistujalle #1. Jatkamme menettelyä kumppaneiden nro 3, nro 4, ..., nro n kanssa . Lopuksi, kunkin murun kaikkien n osallistujan hinnat eivät ylitä 1/ k .

Pakkausvaihe : Tavoitteena on jakaa murut n osajoukkoon niin, että kunkin osajoukon j arvojen summa on lähellä w j . Alla on ei-tiukka selitys kahden osallistujan (Alice ja George) pakkausvaiheesta, kun painot ovat 1/2 [1] .

Otamme tyhjän kupin.
Laita yksi muruista kulhoon.
Jos kupin koko on yli 1/2 jollekin osallistujalle, annamme kupin tälle osallistujalle ja loput murut toiselle osallistujalle.
Muussa tapauksessa (kukin arvo on alle 1/2 molemmille osallistujille), jos kupin arvo on suurempi Alicelle kuin Georgelle, löydämme murun, joka on arvokkaampi Georgelle kuin Alicelle (sellaisen murun täytyy olla olemassa, koska murusien arvojen summa on 1 sekä Alicelle että Georgelle). Lisätään tämä muru kuppiin ja siirrytään algoritmin vaiheeseen 2.

Induktiolla voidaan todistaa, että ero Alicen ja Georgen kupin arvon välillä ei ole koskaan suurempi kuin 1/ k . Siksi, kun toinen kumppani saa kupin, molemmat osallistujat arvostavat sen välillä 1/2-1/ k ja 1/2+1/ k .

Muodollisesti jokainen pala voidaan esittää arvojen vektorina, yksi per jäsen. Jokaisen vektorin pituus on rajoitettu, eli jokaiselle sellaiselle vektorille v : . Tavoitteenamme on luoda jokaiselle osallistujalle j vektori, jonka kaikki elementit ovat lähellä w j :tä . Tätä varten meidän on jaettava vektorit osajoukkoihin siten, että kunkin osajoukon j vektorien summa on riittävän lähellä vektoria, jonka kaikki alkiot ovat yhtä suuria kuin w j . Tämä on mahdollista W. Bergströmin lauseen [11] [12] avulla . $||v||\leqslant {\sqrt {n}}/k$

Murskaa ja pakkaa -menettely on Robertson-Webb-protokollan alimenettely . Tämä protokolla tuottaa jaon, joka on sekä lähes tarkka että kateudeton .

Toisen selityksen murskaa ja pakkaa -menettelylle antoivat Brahms ja Taylor [13] .

Rehellisyyden mekanismit

Kaikki konsensuksen jakamisalgoritmi luottaa osallistujien toimittamiin arvostusmittauksiin. Jos osallistuja tietää, miten algoritmi toimii, hänellä voi olla syytä valehdella saadakseen enemmän kuin reilussa jaossa. Tämän estämiseksi voidaan käyttää (totuudenmukaisten) yhteensopivien kannustinten [2] [14] mekanismeja .

Yksinkertaisin mekanismi totuudenmukaiseen jakoon on: valitsemme satunnaisesti yhden osallistujan (painojen määräämällä todennäköisyydellä) ja annamme hänelle koko kakun. Tämä mekanismi on triviaalisti totta, koska se ei kysy mitään. Se on kuitenkin odotetun johdonmukainen: kunkin osallistujan odotusarvo on täsmälleen sama kuin paino, ja tämä pätee kaikkiin arvomittauksiin. Tuloksena oleva osio ei kuitenkaan ole missään nimessä johdonmukainen jako.

Parempi on totuudenmukainen jakomekanismi, joka toimii kakussa, jossa kaikki painot ovat 1/ n , ja se voidaan rakentaa mistä tahansa olemassa olevasta algoritmista (tai oraakkelista) johdonmukaisen jaon löytämiseksi:

Pyydämme jokaista osallistujaa raportoimaan tuloksensa.
Käytä olemassa olevaa algoritmia/oraakkelia luodaksesi osion, jossa kaikki n kappaletta maksavat täsmälleen 1/ n osallistujien raportoimien toimintojen mukaan.
Suoritamme satunnaisen permutoinnin johdonmukaiselle osiolle ja annamme jokaiselle osallistujalle yhden palasista.

Tässä kunkin osallistujan odotusarvo on edelleen 1/ n raportoidusta luokitusfunktiosta riippumatta, joten mekanismi pysyy totta – kukaan osallistuja ei voi hyötyä valehtelusta. Lisäksi totuudenmukainen osallistuja takaa arvon, joka on täsmälleen yhtä suuri kuin 1/ n todennäköisyydellä 1 (ei pelkästään odotusten perusteella). Siksi osallistujilla on kannustin näyttää luokituksen todelliset toiminnot.

Mahdottomuus

On mahdotonta saavuttaa tarkkaa jakoa rajalliseen määrään pyyntöjä, edes kahdelle osallistujalle ja painoarvot täsmälleen 1/2 [15] . Tämä tarkoittaa, että paras, mitä diskreetillä algoritmilla voidaan saavuttaa, on lähes tarkka jako.

Todistus : Jos protokolla on vaiheessa k , siinä on enintään k kappaleen kokoelma. Tarkan jaon suorittamiseksi protokollan on löydettävä tarkka osajoukko – osajoukko paloista, jotka molemmat osapuolet arvioivat tarkalleen 1/2. Aiomme todistaa, että mille tahansa k :lle on tilanteita, joissa vaiheessa k ei ole tarkkaa osajoukkoa , ja siten protokolla jatkuu loputtomiin.

Aluksi on vain yksi pala, jonka molemmat osallistujat arvioivat 1:ksi, joten selvää osajoukkoa ei ole. Yhden vaiheen jälkeen yksi osallistuja (eli Alice) saa tehtäväkseen leikkaamaan kakun. Vaikka Alice leikkaa kakun kahteen osaan, jotka hänen mielestään ovat samanarvoisia, ne voivat Georgen mukaan olla erilaisia, joten tarkkaa osajoukkoa ei taaskaan ole.

Oletetaan nyt, että olemme vaiheessa k ja kappaleita on k . Yleisyyttä menettämättä voimme olettaa, että kullakin kappaleella on nollasta poikkeava arvo molemmille osallistujille. Tämä johtuu siitä, että jos Alice (esimerkiksi) leikkaa palan, jonka hän arvioi 0:ksi, George voi myös arvioida palan 0:ksi, joten voimme hylätä palan ja jatkaa muilla nappuloilla.

Erillisten osajoukkojen kokonaismäärä on nyt 2k , ja induktiohypoteesin mukaan mikään niistä ei ole tarkka osio. Vaiheessa k protokolla voi pyytää Alicea tai Georgea leikkaamaan osan kahteen osaan. Oletetaan yleisyyden menettämättä, että George oli leikkuri ja että hän leikkaa kappaleen X kahteen osaan: X1 ja X2. Nyt osajoukkojen kokonaismäärä on 2k +1 : puolet niistä on jo olemassa eivätkä ole oletettavasti tarkkoja, joten ainoa mahdollisuus löytää tarkka osajoukko on etsiä uusia osajoukkoja. Jokainen uusi osajoukko on tehty vanhasta osajoukosta, jossa pala X on korvattu joko X1:llä tai X2:lla. Koska George on leikkuri, hän voi leikata tavalla, joka tekee yhdestä näistä osajoukoista hänen tarkan osajoukon (esimerkiksi jos jollakin X:n palan sisältävällä osajoukolla on arvo 3/4, George voi leikata X:n niin, että X1 sen arvo on hänen mielestään 1/4, joten uuden osajoukon arvo on täsmälleen 1/2). George ei kuitenkaan tiedä Alicen pisteitä eikä voi ottaa niitä huomioon leikkaaessaan. Siksi on olemassa lukematon määrä erilaisia arvoja, joita Alice-kappaleiden X1 ja X2 arvioinneilla voi olla. Koska uusien osajoukkojen määrä on äärellinen, on ääretön määrä tapauksia, joissa millään uudella osajoukolla ei ole Liisa-arvoa 1/2, joten mikään uusi osajoukko ei ole tarkka.

Vertailu muihin kriteereihin

Tarkka jako yhtäläisin painoin ( ) on erityisesti myös suhteellinen , kateudesta vapaa ja puolueeton . $1/n$

Se ei kuitenkaan välttämättä ole Pareto-tehokasta , koska monissa tapauksissa on mahdollista saada parannus subjektiivisiin arvioihin ja jakaa resurssit niin, että kaikki osallistujat saavat enemmän kuin heidän kohtuullisen osuutensa . $1/n$

Tarkat jaot on paljon helpompaa, jos osallistujat tekevät yhteistyötä määrittäessään osuuksia sen sijaan, että kilpailevat kuten reilussa jaossa . Jotkut kirjoittajat kutsuvat sitä johdonmukaiseksi jakoksi [16] .

Finaalipöytä

Nimi	Tyyppi	Kakku	Arviot [17]	osallistujien määrä ( n )	osajoukkojen määrä ( k )	leikkausten määrä	paino
Austin	Veitsen siirtäminen	Intervalli	Con	2	Paljon	$2(k-1)$ (optimaalinen)	Minkä tahansa
Palloittain homogeeninen	erillinen menettely	Palloittain homogeeninen	Con+Add+Pwl	Paljon	Paljon	Alueiden lukumäärä	Minkä tahansa
Dubinsa - Spaniera	Todiste olemassaolosta	Minkä tahansa	Con+Add	Paljon	Minkä tahansa	Rajoittamaton	Minkä tahansa
Johdonmukainen jako	Loputon menettely	Intervalli	Con	Minkä tahansa	2	n (optimaalinen)	Yhtä suuri
kaulakorun leikkaaminen	Todiste olemassaolosta	Intervalli	Con(+lisää?)	Minkä tahansa	Minkä tahansa	$n(k-1)$ (optimaalinen)	Yhtä suuri
Stromkvist - Woodall	Todiste olemassaolosta	Pyöristää	Con+Add	Minkä tahansa	2	$2n-2$ (optimaalinen joillekin vaakoille)	Minkä tahansa
Kivi - Tukey	Todiste olemassaolosta	n -ulotteinen	Con(+lisää?)	n	2	1 puolitaso	Yhtä suuri
murskaa ja pakkaa	Melkein tarkka menettely	Minkä tahansa	Con+Add	Minkä tahansa	Paljon	Rajoittamaton	Minkä tahansa

Katso myös

Reilun kakun leikkaamisen haaste

Muistiinpanot

↑ 1 2 3 4 5 Robertson, Webb, 1998 , s. 127.
↑ 1 2 Chen, Lai, Parkes, Procaccia, 2013 , s. 284-297.
↑ Woodall, 1980 , s. 233-247.
↑ Stromquist, Woodall, 1985 , s. 241-248.
↑ Fischer, Daniel. Konsensuskakun jako kahdelle ihmiselle mielivaltaisissa suhteissa . Math.SE. Haettu: 23.6.2015. (määrätön)
↑ On olemassa yleistys, joka antaa jokaiselle n osallistujalle kappaleen, jonka hinta on täsmälleen hänen arvionsa mukainen. Mutta tämä ei ole sovittu jako, koska osallistujat eivät välttämättä sovi muiden kuin hänelle kuuluvien kappaleiden hinnasta. Katso kohta "Monet osallistujat" Austinin liikkuvan veitsen menettelyissä . $1/n$
↑ Goldberg, West, 1985 , s. 93–106.
↑ Alon, West, 1986 , s. 623.
↑ 12 Simmons , Su, 2003 , s. 15-25.
↑ Grünbaum, 1960 , s. 1257–1261.
↑ Bergström, 1930 , s. 205–219.
↑ Robertson, Webb, 1998 , s. 126-128.
↑ Brams ja Taylor 1996 , s. 131-133.
↑ Mossel ja Tamuz, 2010 , s. 288–299.
↑ Robertson, Webb, 1998 , s. 103-104.
↑ de Longueville, Živaljević, 2008 , s. 926–939.
↑ Osallistujien arvioinnin toimintojen vaatimukset. Vähemmän vaatimuksia tarkoittaa yleisempiä tuloksia. Con=Continuous; Con+Add=Additiivisuus; Con+Add+Pwl=Palittainen lineaarifunktio.

Kirjallisuus

Jack Robertson, William Webb. Kakunleikkausalgoritmit: Ole reilu, jos voit. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .
Yiling Chen, John K. Lai, David C. Parkes, Ariel D. Procaccia. Totuus, oikeudenmukaisuus ja kakun leikkaaminen // Pelit ja taloudellinen käyttäytyminen. - 2013. - T. 77 , no. 1 . - doi : 10.1016/j.geb.2012.10.009 .
Woodall DR Kakun reilu jakaminen // Journal of Mathematical Analysis and Applications. - 1980. - T. 78 . - doi : 10.1016/0022-247x(80)90225-5 .
Walter Stromquist, D. R. Woodall. Sarjat, joista useat mitat ovat yhtä mieltä // Journal of Mathematical Analysis and Applications. - 1985. - T. 108 . - doi : 10.1016/0022-247x(85)90021-6 .
Charles H. Goldberg, Douglas B. West. Ympyrän väritysten puolittaminen // SIAM Journal on Algebraic and Discrete Methods. - 1985. - T. 6 . - doi : 10.1137/0606010 .
Noga Alon, Douglas B. West. Borsuk-Ulam-lause ja kaulakorujen puolittaminen // Proceedings of the American Mathematical Society. - 1986. - T. 98 , no. 4 . - doi : 10.1090/s0002-9939-1986-0861764-9 .
Elchanan Mossel, Omer Tamuz. Totuudenmukainen Fair-jaosto. - 2010. - T. 6386. - (Luentomuistiinpanot tietojenkäsittelytieteestä). - ISBN 978-3-642-16169-8 . - doi : 10.1007/978-3-642-16170-4_25 .
Forest W. Simmons, Francis Edward Su. Konsensuksen puolittaminen Borsuk-Ulamin ja Tuckerin lauseiden kautta // Mathematical Social Sciences. - 2003. - T. 45 . - doi : 10.1016/S0165-4896(02)00087-2 .
Branko Grunbaum. Massajakaumien ja kupera kappaleiden väliseinät hypertasoilla // Pacific J. Math .. - 1960. - Vol. 10 , no. 4 . - doi : 10.2140/pjm.1960.10.1257 .
Zwei Sätze über ebene Vectorpolygone // Hamburgische Abhandlungen. - 1930. - T. 8 .
Steven J. Brams, Alan D. Taylor. Reilu osasto: kakun leikkaamisesta riitojen ratkaisemiseen. - 1996. - ISBN 978-0-521-55644-6 .
Mark de Longueville, Rade T. Zivaljević. Moniulotteisten kaulakorujen halkaisu // Matematiikan edistysaskel. - 2008. - T. 218 , no. 3 . - doi : 10.1016/j.aim.2008.02.003 . - arXiv : math/0610800 .