Super suhteellinen jako

Reilun kakkuleikkauksen yhteydessä supersuhteellinen jako on jako, jossa kukin osallistuja saa osuuden, joka on ehdottomasti suurempi kuin 1/ n (kokonais)resurssista hänen oman subjektiivisen arvionsa mukaan ( ). $V>1/n$

Supersuhteellinen jako vs suhteellinen jako

Supersuhteellinen jako on parempi kuin suhteellinen jako , jossa jokaiselle osallistujalle taataan vähintään 1/ n ( ). Toisin kuin suhteellinen jako, supersuhteellista jakoa ei kuitenkaan aina ole olemassa. Kun kaikilla jaoston osallistujilla on täsmälleen samat arviointitoiminnot, paras, jonka voimme antaa kullekin osallistujalle, on täsmälleen 1/ n . $V\geqslant 1/n$

Supersuhteellisen jaon olemassaolon välttämätön edellytys on, että kaikilla osallistujilla ei ole samaa arvoa.

Yllättävä tosiasia on, että jos arviot ovat additiivisia eivätkä atomisia, tämä ehto on myös riittävä. Eli jos osallistujia on vähintään kaksi , joiden arviointitoiminnot ovat vaikkakin hieman erilaisia, on olemassa supersuhteellinen jako, jossa kaikki osallistujat saavat enemmän kuin 1/ n .

Hypoteesi

Supersuhteellisen jaon olemassaolo ehdotettiin olettamukseksi vuonna 1948 [1] .

On ohimennen sanottu, että jos on kaksi (tai useampia) osallistujia, joilla on erilaiset arvopisteet, syntyy jako, joka antaa jokaiselle enemmän kuin vain oman osuutensa ( Knaster ), ja tämä tosiasia kumoaa yleisen käsityksen, että pisteerojen ero oikeudenmukainen jako vaikeampaa.

Olemassaolotodistus

Ensimmäinen julkaistu todiste supersuhteellisen jaon olemassaolosta oli seurausta Dubins-Spanierin konveksisuuslauseesta . Tämä oli puhtaasti teoreettinen olemassaolotodistus , joka perustui kuperuuteen.

Protokolla

Protokolla supersuhteellisen jaon saamiseksi otettiin käyttöön vuonna 1986 [2] .

Yksi kappale eri luokituksilla

Olkoon C täysi kakku. Protokolla alkaa tietyllä kakunpalalla, esimerkiksi , jonka arvostelee kaksi osallistujaa. Oletetaan, että se on Alice ja Bob. $X\subseteq C$

Olkoon a=V Alice (X) ja b=V Bob (X) ja oletetaan yleisyyden menettämättä, että b>a .

Kaksi kappaletta eri luokituksilla

Etsi rationaalinen luku b :n ja a :n väliltä , sano p/q siten, että b > p/q > a . Pyydämme Bobia leikkaamaan X p yhtä suureen osaan ja leikkaa C \ X qp yhtä suureen osaan.

Oletuksemme mukaan Bobin arvot kullekin kappaleelle X ovat suurempia kuin 1/ q ja jokaiselle kappaleelle C \ X ovat pienempiä kuin 1/ q . Alicelle kuitenkin vähintään yhden palan X :n (sanotaan, Y ) arvon on oltava pienempi kuin 1/ q ja vähintään yhden palan C\X (sanotaan, Z ) arvo on suurempi kuin 1/ q .

Siten meillä on kaksi kappaletta Y ja Z siten, että:

V Bob (Y)>V Bob (Z) V Alice (Y) <V Alice (Z)

Supersuhteellinen jako kahdelle osallistujalle

Anna Alice ja Bob jakaa loput C \ Y \ Z keskenään suhteellisesti (esimerkiksi käyttämällä jaa ja valitse -protokollaa ). Lisätään Z Alicen palaan ja Y Bobin palaan.

Nyt jokainen osallistuja ajattelee, että hänen jakaumansa on ehdottomasti suurempi kuin mikään muu jakauma, joten arvo on ehdottomasti suurempi kuin 1/2.

Supersuhteellinen jako n osallistujalle

Tämän protokollan n -jäseninen laajennus perustuu Finkin "Single Chooser" -protokollaan .

Oletetaan, että meillä on jo supersuhteellinen jako i -1 osallistujille (for ). Uusi osallistuja #i tulee peliin ja meidän pitäisi antaa hänelle osakkeita ensimmäisistä i -1 osallistujista, jotta uusi divisioona pysyy supersuhteellisena. $i\geqslant 3$

Harkitse esimerkiksi kumppania #1. Olkoon d kumppanin #1 nykyisen arvon ja (1/( i -1)) erotus . Koska nykyinen jako on supersuhteellinen, tiedämme, että d>0 .

Valitsemme positiivisen kokonaisluvun q siten, että $d>{\frac {1}{(i-1)i(q(i-1)-1)))$

Pyydetään osallistujaa #1 jakamaan osuutensa samanarvoisiksi katsomiinsa osiin, ja annetaan uuden osallistujan valita itselleen arvokkaimmat palat. $qi-1$ $q$

Osallistujalle #1 jää edellisen arvonsa arvo, joka oli yhtä suuri kuin (määritelmän mukaan d ). Ensimmäisestä elementistä tulee , ja d : stä tulee . Niiden summaus antaa, että uusi arvo ylittää koko kakun. ${\frac {(qi-1)-q}{qi-1}}={\frac {q(i-1)-1}{qi-1}}$ ${\frac {1}{i-1}}+d$ ${\frac {q(i-1)-1}{(i-1)(qi-1)))$ ${\frac {1}{i(i-1)(qi-1)))$ ${\frac {(qi-1)(i-1)}{(i-1)i(qi-1)}}={\frac {1}{i}}$

Sen jälkeen kun uusi osallistuja, saatuaan q osaa jokaiselta ensimmäiseltä i -1 osallistujalta, hänellä on kokonaisarvo vähintään koko kakun arvo. ${\frac {q}{qi-1}}>{\frac {1}{i}}$

Tämä osoittaa, että uusi jako on myös supersuhteellinen.

Muistiinpanot

↑ Steinhaus, 1948 , s. 101-4.
↑ Woodall, 1986 , s. 300.

Kirjallisuus

Hugo Steinhaus. Oikeudenmukaisen jaon ongelma // Econometrica. - 1948. - T. 16 , no. 1 . — .
Woodall DR Huomautus kakkujakoongelmasta // Journal of Combinatorial Theory, Series A. - 1986. - V. 42 , no. 2 . - S. 300 . - doi : 10.1016/0097-3165(86)90101-9 .