Pontos felosztás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. január 9-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A pontos felosztás , más néven egyenlő felosztás vagy megállapodás szerinti felosztás egy heterogén erőforrás (például torta ) több részhalmazra való felosztása úgy, hogy a különböző ízlésű emberek mindegyike megegyezik a darabok értékelésében [1 ] .

Vegyünk egy olyan tortát, amely félig csokoládé és félig vanília. Alice-nek csak a csokoládé része, George-nak pedig csak a vanília. A torta három részre oszlik: az egyik rész 20% csokoládé és 20% vanília, a második rész 50% csokoládé és 50% vanília, a harmadik rész pedig a torta többi részét tartalmazza. Ez a felosztás következetes, mivel Alice és George is 20%-ra, 50%-ra és 30%-ra értékeli a három részt.

Ahogy a példa is mutatja, a megállapodás szerinti felosztás nem feltétlenül igazságos. Például, ha egy darab 20%-ot adnak Alice-nek, és egy 50%-ot George-nak, ez nyilvánvalóan nem fair Alice-szel szemben. A tortavágás elméletében a következetes felosztásokat gyakran használják aleljárásokként a tisztességes felosztások létrehozására.

Az egyeztetett felosztások mindig léteznek, de diszkrét protokollokkal (véges számú kéréssel) nem találhatók meg. Egyes esetekben a pontos felosztást a kések mozgatási protokolljaival lehet megtalálni. A diszkrét protokollok segítségével szinte pontos felosztásokat találhatunk.

Definíciók

Legyen k súlyozás , amelyek összege 1. Tegyük fel, hogy minden résztvevő 1-re értékeli a teljes C tortát . ${\displaystyle w_{1},w_{2},\ldots ,w_{k))$

A pontos felosztás (vagy következetes felosztás ) egy kapcsolatban azt jelenti, hogy a tortát k darabra osztják: , tehát bármely i tagra és bármely j darabra : ${\displaystyle w_{1},w_{2},\ldots ,w_{k))$ ${\displaystyle C=X_{1}\sqcup \cdots \sqcup X_{k))$

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

Ez azt jelenti, hogy minden résztvevő egyetért abban, hogy a j darab értéke pontosan [1] . ${\displaystyle w_{j))$

Majdnem pontos felosztás

Bármely -majdnem pontos megosztottság egy kapcsolatban olyan megosztottság, amelyben $\varepsilon >0$ $\varepsilon$ ${\displaystyle w_{1},w_{2},\ldots ,w_{k))$

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

Ez azt jelenti, hogy minden résztvevő egyetért abban, hogy a j darab értéke majdnem pontosan egyenlő , a különbség pedig kisebb, mint [1] . ${\displaystyle w_{j))$ $\varepsilon$

Tökéletes felosztás

A tökéletes felosztás az a felosztás, amelyben egy erőforrást n résztvevő között osztanak fel szubjektív becslésekkel, így minden résztvevőnek pontosan az erőforrás 1/ n -ét kapja az összes résztvevő becslése szerint. Ez az egzakt osztás speciális esete, amelyben minden súly 1/ n .

Pontos osztás tetszőleges számú vágással

Darabosan homogén torta, sok résztvevő, bármilyen súlyú

Egy tortát darabonként homogénnek nevezünk, ha R régiókra osztható úgy, hogy minden résztvevő egyetért abban, hogy az értékmérő sűrűségértéke minden régióban homogén. Vegyünk például egy kerek tortát, amelynek 4 negyedét különféle díszítések (tejszín, cukormáz, gyümölcs és csokoládé) díszítik. A versenyzők az egyes díszítéseket eltérően értékelhetik, de nem tesznek különbséget az azonos díszítésű tortadarabok között. Ez azt jelenti, hogy az egyes darabok értéke minden résztvevő számára csak attól függ, hogy mennyit kapnak az egyes területekről.

Az az állítás, hogy a torta darabonként homogén, egyenértékű azzal az állítással, hogy a felosztás különböző résztvevőinek becslései darabonként állandóak – a torta minden darabja akkor és csak akkor homogén, ha n résztvevő n darabjának metszéspontja.

Ha a torta darabonként homogén (és a becslések darabonként állandóak), következetes felosztást kaphatunk a következőképpen:

Osszuk fel az egyes régiókat k alrégióra úgy, hogy a j alrégió pontosan tartalmazza a régiókat. ${\displaystyle w_{j))$
Legyen j darab az összes R régió j -edik alrégióinak uniója . Ez meghatározza az adott súlyok konzisztens felosztását.

Ez az algoritmus általánosítható egy kicsit általánosabb értékmértékcsaládra, például a darabonkénti lineáris mértékekre [2] .

A szükséges vágások száma , ahol R egyenlő a régiók számával. $kR$

Általános torta, sok résztvevő, bármilyen súlyú

Ha a költségmértékek megszámlálhatóan additívak és atommentesek , akkor konzisztens partíció létezik minden olyan súlyhalmazhoz, amelynek összege 1. Ez a Dubins-Spanier konvexitástétel következménye .

Woodall [3] megmutatta, hogy lehetséges egy ilyen partíció felépítése egy intervallum tortán intervallumok megszámlálható uniójaként.

Vázlat: Tekintsük a fent leírt, darabonkénti homogén sütemények felosztási eljárását. Általában a sütemény nem darabonként homogén. Mivel azonban az árintézkedések folyamatosak, lehetőség van arra, hogy a tortát egyre kisebb területekre bontsák úgy, hogy a területek egyre egységesebbek legyenek. Amikor ez a folyamat egy megállapodott felosztáshoz konvergál. $R\to \infty$

Fremlin megmutatta, hogy lehetséges egy ilyen felosztást intervallumok véges uniójaként felépíteni.

Stromquist és Woodall [4] kimutatta, hogy ez minimális számú intervallum mellett lehetséges, lásd a Stromquist-Woodall tételt .

Pontos osztás minimális vágásszámmal

Tegyük fel, hogy a torta egy n különböző részintervallumból álló intervallum, és az n résztvevő mindegyike csak egy területet értékel. Ekkor a torta következetes k részhalmazra osztása vágást igényel, hiszen mindegyik területet k darabra kell vágni , amelyek egyenlőek a területet értékelő résztvevő szemében. Ezért van egy érdekes kérdés, hogy mindig lehetséges-e konzisztens felosztást elérni ezzel a pontos vágásszámmal. $n\cdot (k-1)$

Intervallum torta, két résztvevő, sok részhalmaz, bármilyen súlyozás

Két résztvevő elérheti az egyeztetett felosztást az Austin's Moving Knife eljárással .

A legegyszerűbb eset a súlyok 1/2, vagyis úgy akarják felvágni a tortát, hogy mindketten megegyezzenek a torta értékének feléért. Ez a következő módon történik. Az egyik résztvevő két kést mozgat a tortán balról jobbra úgy, hogy a kések közötti érték mindig pontosan 1/2 legyen. Bizonyítható ( a köztes érték tétellel ), hogy valamikor a kések közötti érték a másik résztvevő számára is pontosan 1/2 lesz. Egy másik résztvevő felkiált: "állj!" ezen a ponton a darabot levágjuk.

Ugyanez a protokoll használható egy olyan darab levágására, amelynél mindkét játékos egyetért abban, hogy az értéke pontosan . $1/n$

Több ilyen darab kombinálásával konzisztens osztást kaphat minden olyan arányra, amely racionális szám . Ehhez azonban nagyszámú bemetszésre lehet szükség.

A következetes felosztás jobb módja, ha azonosítjuk a torta két végpontját, hogy azt körnek lehessen tekinteni. Ez azt jelenti, hogy amikor a jobb kés eléri a jobb végét, azonnal a bal végéhez megy, és a kések közötti darabot a jobb késtől jobbra lévő darab egyesülésének tekintjük (ami korábban a bal kés volt). és a bal késtől balra lévő darabot (ami korábban a jobb kés volt). ). Akkor találhatunk konzisztens felosztást bármely . Az egyik résztvevő ciklikusan mozgatja a késeket a torta körül, mindig úgy, hogy a köztük lévő érték pontosan egyenlő p -vel . Bizonyítható, hogy egy ponton a kések közötti érték a másik résztvevő számára pontosan egyenlő lesz p -vel [5] . Egy másik résztvevő felkiált: "állj!" ezen a ponton a darabot levágjuk. Csak két vágás szükséges hozzá. $p\in [0,1]$

A fenti eljárás megismétlésével tetszőleges számú részhalmazra konzisztens felosztás érhető el a két résztvevő között. A vágások száma , ahol egyenlő a részhalmazok számával. $2(k-1)$ $k$

2015-ig nem volt ismert, hogy ezt a mozgó késes eljárást 2-nél több résztvevőre általánosították volna [6] .

Intervallum torta, sok résztvevő, két részhalmaz, egyenlő súlyok

Tegyük fel, hogy a torta egy intervallum, amelynek összértéke 1. Fel kell osztani részhalmazokra, amelyek mindegyikének értéke pontosan 1/2 az összes n résztvevő esetében. A minimális számú vágást szeretnénk használni, ami . $k=2$ $n(k-1)=n$

Ilyen felosztás mindig létezik [7] . Ez egyenes következménye a Hobby-Rice tételnek . Ez a Borsuk-Ulam tétel [8] alapján is kimutatható :

Egy intervallum vágásokat használó bármely partíciója ábrázolható hosszvektorként , ahol az elemek a részintervallumok hosszai. $n$ $n+1$
A vektor bármely eleme lehet pozitív (ha az 1. darabhoz tartozik) vagy negatív (ha a 2. darabhoz tartozik).
Az összes partíció halmaza egy gömb . $S^{n}$
Határozzuk meg a következőképpen: bármely partíció esetén x olyan vektor lesz, amelynek i -edik eleme az i -es résztvevő 1/2-e szerinti #1 darab értéke ebben a partícióban. $V:S^{n}\to \mathbb {R} ^{n}$ $V(x)$
A V függvény folytonos. Ráadásul minden x -re . $V(x)+V(-x)=0$
Ezért a Borsuk-Ulam tétel szerint létezik olyan x , hogy . Ebben a felosztásban minden résztvevő az 1. darabot (és a 2. darabot) pontosan 1/2-re értékeli. $V(x)=0$

Konzisztens két részhalmazra való felosztás található Tucker lemmája alapján, amely a Borsuk-Ulam tétel diszkrét változata [9] .

Bár a résztvevők preferenciáit mérőszámok modellezik, a bizonyítások nem követelik meg, hogy az értékelések mérőszámai részhalmazok additívak legyenek. A becslések mérőszámai lehetnek folytonos függvények is a Borel komplett algebrákon definiált halmazokon, amelyek kielégítik a mértékek összes tulajdonságát, kivéve a megszámlálható additivitást. Ekkor nem szükséges, hogy a torta részhalmazai tagjainak pontszámai additívan elválaszthatók legyenek [9] .

Intervallum torta, sok résztvevő, sok részhalmaz, egyenlő súlyok

Az előző szakasz létezési tétele darabokról tetszőleges számú darabra általánosítható. Ezt Noga Alon is bebizonyította a nyaklánc felosztásáról szóló 1987-es tanulmányában . $k=2$

Különféle mértékek vannak egy intervallumon, amelyek mindegyike abszolút folyamatos a hossz tekintetében. A teljes nyaklánc mértéke a mérték szerint egyenlő . Ekkor lehetőség van az intervallum részekre (nem feltétlenül folytonos) felosztására úgy, hogy az egyes részek értéke a mérték szerint pontosan egyenlő legyen a -val . Nincs szükség több vágásra, és ez az érték optimális. $n$ $én$ $k\cdot a_{i}$ $k$ $én$ $a_{i}$ $(k-1)n$

Intervallum torta, sok résztvevő, két részhalmaz, tetszőleges súlyok

Az előző szakasz létezési tételét a Stromquist-Woodall tétel általánosítja tetszőleges súlyokra .

Többdimenziós torta, sok résztvevő, sok részhalmaz, egyenlő súlyok

A Stone-Tukey tétel kimondja, hogy adott n mérhető "objektum" az n - dimenziós térben, mindegyiket fel lehet osztani (mértékük , azaz térfogatuk szerint) egyetlen ( n − 1) dimenziós hipersíkkal .

Más szóval: ha a torta egy szóköz , és a résztvevők értékelésének mértéke véges és nullával egyenlő bármely -dimenziós hipersíkon, akkor van egy féltér , amelynek értéke minden résztvevőre pontosan 1/2. Ezért következetesen osztják az egységnyi vágást. $\mathbb {R} ^{n}$ $n-1$

Ennek a tételnek az eredeti változata csak akkor működik, ha a torta száma megegyezik a résztvevők számával. Például ezt a tételt nem lehet alkalmazni egy 3-dimenziós szendvics négy résztvevőre való felosztására.

Vannak azonban olyan általánosítások, amelyek lehetővé teszik az ilyen felosztást. Nem hipersík kést használnak, hanem bonyolultabb polinomiális felületeket [10] .

Szinte pontos felosztási eljárások

A morzsa-csomagolás eljárás

Egy adott egynél minden résztvevőnek megadhat egy darabot úgy, hogy minden résztvevő azt higgye, hogy minden érték kisebb, mint , azaz bármely i és bármely j esetén [1] : $\varepsilon >0$ $\varepsilon$

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

A szinte pontos felosztási eljárás két lépésből áll: morzsolás és csomagolás .

Morzsolási lépés : A cél az, hogy a tortát apró darabokra ("morzsára") vágják úgy, hogy minden versenyző elég kis értéket rendeljen minden egyes morzsához. Ez a következő módon történik. Legyen k valamilyen állandó. Kérjük meg az 1. résztvevőt, hogy a tortát vágja k darabra úgy, hogy minden darab ára 1/ k . Kérjük meg a 2. résztvevőt, hogy ossza szét a darabokat (legfeljebb k -1 vágást használva), hogy minden darab ára ne legyen több 1/ k -nál . Ezek az új darabok természetesen továbbra is nem haladják meg az 1/ k értéket az 1. résztvevő számára. Az eljárást a 3., 4., ..., n . számú partnerekkel folytatjuk . Végül az egyes morzsa n résztvevőjének ára nem haladja meg az 1/ k -t .

Csomagolási lépés : Itt az a cél, hogy a morzsákat n részhalmazra ossza fel úgy, hogy az egyes j részhalmazok értékeinek összege közel legyen w j -hez . Az alábbiakban két résztvevő (Alice és George) csomagolási lépésének nem szigorú magyarázata található, ha a súlyok 1/2 [1] .

Veszünk egy üres poharat.
Az egyik morzsát egy tálba tesszük.
Ha valamelyik résztvevőnél a pohár mérete meghaladja az 1/2-t, a poharat ennek a résztvevőnek adjuk, a maradék morzsát pedig egy másik résztvevőnek.
Ellenkező esetben (a kupában lévő érték mindkét résztvevőnél kisebb, mint 1/2), ha a kupában lévő érték Alice-nél nagyobb, mint George-nál, akkor találunk egy morzsát, amely George-nak értékesebb, mint Alice-nek (egy ilyen morzsát kell léteznek, mivel a morzsák értékeinek összege Alice és George esetében is 1). Adjuk hozzá ezt a morzsát a csészéhez, és folytassuk az algoritmus 2. lépésével.

Indukcióval igazolható, hogy Alice és George kupaértéke közötti különbség soha nem nagyobb 1/ k -nál . Ezért amikor az egyik partner kap egy poharat, mindkét résztvevő 1/2-1/ k és 1/2+1/ k közé értékeli .

Formálisan minden darab értékvektorként ábrázolható, tagonként egy. Az egyes vektorok hossza korlátozott, azaz minden ilyen v : vektorra . Célunk, hogy minden j résztvevő számára létrehozzunk egy vektort, amelynek minden eleme közel áll w j -hoz . Ehhez a vektorokat részhalmazokra kell felosztanunk úgy, hogy a vektorok összege minden j részhalmazhoz kellően közel legyen egy olyan vektorhoz, amelynek minden eleme egyenlő w j -vel . Ez W. Bergström [11] [12] tételével lehetséges . $||v||\leqslant {\sqrt {n}}/k$

A morzsa és csomagoló eljárás a Robertson-Webb protokoll egyik aleljárása . Ez a protokoll egy olyan felosztást hoz létre, amely közel pontos és irigységmentes .

A morzsa-pakolj eljárás másik magyarázatát Brahms és Taylor [13] adta meg .

Az őszinteség mechanizmusai

Bármilyen konszenzusos megosztási algoritmus a résztvevők által biztosított értékelési mérőszámokra támaszkodik. Ha a résztvevő ismeri az algoritmus működését, akkor lehet oka hazudni, hogy többet kapjon, mint egy igazságos felosztásban. Ennek megakadályozására (igazságokkal) kompatibilis ösztönző mechanizmusok [2] [14] használhatók .

Az igazságos felosztás legegyszerűbb mechanizmusa: véletlenszerűen kiválasztunk egy résztvevőt (súlyokkal meghatározott valószínűséggel), és neki adjuk az egész tortát. Ez a mechanizmus triviálisan igaz, mert nem tesz fel kérdéseket. Azonban elvárás-konzisztens: minden résztvevő várható értéke pontosan megegyezik a súllyal, és ez minden értékmérőre igaz. Az így kapott partíció azonban semmiképpen sem konzisztens felosztás.

Jobb egy igaz osztási mechanizmus, amely olyan tortáknál működik, ahol minden súly 1/ n , és bármely létező algoritmusból (vagy orákulumból) fel lehet építeni a következetes felosztás megtalálására:

Kérünk minden résztvevőt, hogy számoljon be a pontszámáról.
Egy meglévő algoritmus/oracle segítségével generáljunk egy partíciót, amelyben mind az n darab pontosan 1/ n -be kerül a résztvevők által közölt függvények szerint.
Véletlenszerű permutációt hajtunk végre egy konzisztens partíción, és minden résztvevőnek adunk egy darabot.

Itt minden résztvevő várható értéke továbbra is 1/ n , függetlenül a jelentett értékelési függvénytől, így a mechanizmus igaz marad – egyetlen résztvevő sem profitálhat a hazudozásból. Ráadásul egy igaz résztvevő 1-es valószínűséggel garantálja az 1/ n -nel pontosan megegyező értéket (nem csak a várakozás alapján). Ezért a résztvevőket arra ösztönzik, hogy megmutassák a minősítések valódi funkcióit.

Lehetetlenség

Lehetetlen pontos felosztást elérni véges számú kérésben, még két résztvevő és pontosan 1/2 súllyal [15] . Ez azt jelenti, hogy a legjobb, amit egy diszkrét algoritmussal el lehet érni, a szinte pontos felosztás.

Bizonyítás : Ha a protokoll a k lépésben van, akkor legfeljebb k darabból állhat. A pontos osztás végrehajtásához a protokollnak meg kell találnia egy pontos részhalmazt – a darabok azon részhalmazát, amelyet mindkét partner pontosan 1/2-re értékel. Be fogjuk bizonyítani, hogy bármely k esetén vannak olyan helyzetek, amelyekben nincs pontos részhalmaz a k lépésben , és ezért a protokoll a végtelenségig folytatódik.

Kezdetben csak egy darab van, amelyet mindkét résztvevő 1-re értékel, így nyilvánvalóan nincs pontos részhalmaz. Egy lépés után az egyik résztvevő (mondjuk Alice) feladata a torta felvágása. Még ha Alice fel is vágja a tortát két, szerinte egyforma részre, George szerint ezek különbözhetnek, így megint nincs pontos részhalmaz.

Tegyük fel, hogy a k lépésnél vagyunk, és van k darab. Az általánosság elvesztése nélkül feltételezhetjük, hogy minden darab mindkét résztvevő számára nullától eltérő értékkel rendelkezik. Ez azért van így, mert ha Alice (például) levág egy darabot, amelyet 0-ra értékel, George is értékelheti azt 0-ra, így eldobhatjuk azt a darabot, és folytathatjuk a többi darabbal.

A különböző részhalmazok teljes száma most 2k , és az indukciós hipotézis szerint egyikük sem pontos partíció. A k lépésben a protokoll megkérheti Alice-t vagy George-ot, hogy vágjon két részre egy darabot. Tegyük fel, az általánosság elvesztése nélkül, hogy George volt a vágó, és az X darabot két részre vágja: X1 és X2. Most a részhalmazok teljes száma 2k +1 : fele már létezik, és feltételezhetően nem egzakt, így az egyetlen esély a pontos részhalmaz megtalálására, ha új részhalmazokat keresünk. Minden új részhalmaz egy régi részhalmazból készül, amelyben az X darabot X1 vagy X2 helyettesíti. Mivel George vágó, tud úgy vágni, hogy az egyik részhalmaz saját maga pontos részhalmazává tegye (például ha egy X darabot tartalmazó részhalmaz értéke 3/4, akkor George levághatja X-et úgy, hogy X1 véleménye szerint értéke 1/4, így az új részhalmaz értéke pontosan 1/2). George azonban nem ismeri Alice pontszámait, és nem tudja figyelembe venni a vágásnál. Ezért megszámlálhatatlanul sok különböző érték létezik, amelyek az X1 és X2 darabok értékelései Alice számára lehetnek. Mivel az új részhalmazok száma véges, végtelen számú olyan eset van, amikor egyetlen új részhalmaznak sem az értéke 1/2 Alice esetében, ezért az új részhalmaz sem pontos.

Összehasonlítás más kritériumokkal

A pontos osztás egyenlő súllyal ( ) különösen arányos , irigységtől mentes és elfogulatlan . $1/n$

Ez azonban nem feltétlenül Pareto-hatékony , mivel sok esetben lehetséges a szubjektív becslések javulása, és az erőforrások úgy oszthatók fel, hogy minden résztvevő többet kapjon, mint a méltányos részesedése . $1/n$

A pontos felosztás sokkal könnyebb, ha a résztvevők együttműködnek a részesedések meghatározásában , ahelyett, hogy versenyeznének, mint egy igazságos felosztásban . Egyes szerzők következetes felosztásnak nevezik [16] .

Döntő táblázat

Név	Típusú	Torta	Becslések [17]	résztvevők száma ( n )	részhalmazok száma ( k )	vágások száma	súly
Austin	Mozgó kés eljárás	Intervallum	Con	2	Sok	$2(k-1)$ (optimális)	Bármi
Darabosan homogén	diszkrét eljárás	Darabosan homogén	Con+Add+Pwl	Sok	Sok	Régiók száma	Bármi
Dubinsa – Spaniera	A létezés igazolása	Bármi	Con+Add	Sok	Bármi	Korlátlan	Bármi
Következetes felosztás	Végtelen eljárás	Intervallum	Con	Bármi	2	n (optimális)	Egyenlő
a nyaklánc elvágása	A létezés igazolása	Intervallum	Con(+Hozzáadás?)	Bármi	Bármi	$n(k-1)$ (optimális)	Egyenlő
Stromkvist – Woodall	A létezés igazolása	Kerek	Con+Add	Bármi	2	$2n-2$ (optimális bizonyos mérlegekhez)	Bármi
Stone – Tukey	A létezés igazolása	n -dimenziós	Con(+Hozzáadás?)	n	2	1 félsík	Egyenlő
morzsa-pakol	Majdnem pontos eljárás	Bármi	Con+Add	Bármi	Sok	Korlátlan	Bármi

Lásd még

Fair Cake Cutting Challenge

Jegyzetek

↑ 1 2 3 4 5 Robertson, Webb, 1998 , p. 127.
↑ 1 2 Chen, Lai, Parkes, Procaccia, 2013 , p. 284–297.
↑ Woodall, 1980 , p. 233–247.
↑ Stromquist, Woodall, 1985 , p. 241–248.
↑ Fischer, Daniel. Egy torta konszenzusos felosztása két emberre tetszőleges arányban . Math.SE. Letöltve: 2015. június 23. (határozatlan)
↑ Létezik egy általánosítás, amely az n résztvevő mindegyikének ad egy darabot, amelynek ára pontosan a becslése szerint van. De ez nem megállapodás szerinti felosztás, mivel a résztvevők nem állapodhatnak meg más, nem hozzá tartozó darabok árában. Tekintse meg a „Sok résztvevő” részt az Austin's Moving Knife Procedures című könyvben . $1/n$
↑ Goldberg, West, 1985 , p. 93–106.
↑ Alon, West, 1986 , p. 623.
↑ 12 Simmons , Su, 2003 , p. 15–25.
↑ Grünbaum, 1960 , p. 1257–1261.
↑ Bergström, 1930 , p. 205–219.
↑ Robertson, Webb, 1998 , p. 126-128.
↑ Brams és Taylor 1996 , p. 131–133.
↑ Mossel és Tamuz, 2010 , p. 288–299.
↑ Robertson, Webb, 1998 , p. 103-104.
↑ de Longueville, Živaljević, 2008 , p. 926–939.
↑ A résztvevők értékelésének funkcióira vonatkozó követelmények. A kevesebb követelmény általánosabb eredményeket jelent. Con=Continuous; Con+Add=Additivitás; Con+Add+Pwl=Részenkénti lineáris függvények.

Irodalom

Jack Robertson, William Webb. Tortavágási algoritmusok: Legyen igazságos, ha tud. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .
Yiling Chen, John K. Lai, David C. Parkes, Ariel D. Procaccia. Igazság, igazságosság és tortavágás // Játékok és gazdasági viselkedés. - 2013. - T. 77 , sz. 1 . - doi : 10.1016/j.geb.2012.10.009 .
Woodall DR Egy torta igazságos felosztása // Journal of Mathematical Analysis and Applications. - 1980. - T. 78 . - doi : 10.1016/0022-247x(80)90225-5 .
Walter Stromquist, D. R. Woodall. Olyan halmazok, amelyekben több mérték megegyezik // Journal of Mathematical Analysis and Applications. - 1985. - T. 108 . - doi : 10.1016/0022-247x(85)90021-6 .
Charles H. Goldberg, Douglas B. West. Körszínezések felezése // SIAM Journal on Algebraic and Discrete Methods. - 1985. - T. 6 . - doi : 10.1137/0606010 .
Noga Alon, Douglas B. West. A Borsuk-Ulam tétel és a nyakláncok felezése // Proceedings of the American Mathematical Society. - 1986. - T. 98 , sz. 4 . - doi : 10.1090/s0002-9939-1986-0861764-9 .
Elchanan Mossel, Omer Tamuz. Igazságos tisztességes osztály. - 2010. - T. 6386. - (Számítástechnikai előadásjegyzetek). - ISBN 978-3-642-16169-8 . - doi : 10.1007/978-3-642-16170-4_25 .
Forest W. Simmons, Francis Edward Su. Konszenzus-felezés Borsuk-Ulam és Tucker tételein keresztül // Mathematical Social Sciences. - 2003. - T. 45 . - doi : 10.1016/S0165-4896(02)00087-2 .
Branko Grunbaum. Tömegeloszlások és konvex testek válaszfalai hipersíkok által // Pacific J. Math .. - 1960. - 10. kötet , 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. Fair Division: A tortavágástól a vitarendezésig. - 1996. - ISBN 978-0-521-55644-6 .
Mark de Longueville, Rade T. Zivaljević. Többdimenziós nyakláncok felosztása // Előrelépések a matematikában. - 2008. - T. 218 , sz. 3 . - doi : 10.1016/j.aim.2008.02.003 . - arXiv : math/0610800 .