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 ( ).
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 .
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 .
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.Ensimmäinen julkaistu todiste supersuhteellisen jaon olemassaolosta oli seurausta Dubins-Spanierin konveksisuuslauseesta . Tämä oli puhtaasti teoreettinen olemassaolotodistus , joka perustui kuperuuteen.
Protokolla supersuhteellisen jaon saamiseksi otettiin käyttöön vuonna 1986 [2] .
Olkoon C täysi kakku. Protokolla alkaa tietyllä kakunpalalla, esimerkiksi , jonka arvostelee kaksi osallistujaa. Oletetaan, että se on Alice ja Bob.
Olkoon a=V Alice (X) ja b=V Bob (X) ja oletetaan yleisyyden menettämättä, että b>a .
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)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.
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.
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ä
Pyydetään osallistujaa #1 jakamaan osuutensa samanarvoisiksi katsomiinsa osiin, ja annetaan uuden osallistujan valita itselleen arvokkaimmat palat.
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.
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.
Tämä osoittaa, että uusi jako on myös supersuhteellinen.