Az arányos tortavágás probléma

Az arányos tortavágási probléma egyfajta tisztességes tortavágási probléma . Ez egy heterogén erőforrás ("torta") felosztása, amely megfelel az arányosság kritériumának , nevezetesen, hogy bármely résztvevő úgy gondolja, hogy a tortából kiosztott rész nem rosszabb, mint a torta teljes értékelésének 1/ n -a.

Amikor az arányosságról beszélünk , általában két feltételezés merül fel:

A résztvevők értékelései nem atomi , vagyis nincsenek oszthatatlan elemek pozitív értékeléssel.
A résztvevők pontszámai additívak , vagyis ha egy darabot felosztanak, akkor a darab pontszáma egyenlő a részek összegével.

Eljárások

Két személy számára a Delhi-and-Choose eljárás klasszikus megoldás. Az egyik személy két részre osztja az erőforrást, amelyet egyenlőnek tekint, a másik pedig azt a „felet”, amelyik a legjobban tetszik. A nem atomos feltételezés garantálja, hogy a vágó (ahogy gondolja) két egyenlő részre tudjon vágni. Az additív feltételezés garantálja, hogy mindkét résztvevő becslése legalább 1/2 lesz a darabjaikra.

Sokféleképpen lehet kiterjeszteni ezt az eljárást 2 főnél több személyre. Ezen módszerek mindegyikének megvannak a maga előnyei és hátrányai.

Egyszerű eljárások

Az utolsó mínusz a legkorábbi arányos osztási eljárás, amelyet n emberre fejlesztettek ki:

Az egyik résztvevőt megkérik, hogy válasszon ki egy darabot, amelyet 1/ n -re értékel .
A többi résztvevőnek pedig lehetősége van kifogást emelni és kijelenteni, hogy a darab nagyobb, mint 1/ n . Ebben az esetben arra kérik, hogy csökkentse a darabot úgy, hogy becslése szerint a darab maradék része 1/ n .
Az utolsó résztvevő kapja meg, aki csökkenti a darabot.
A többi résztvevő ugyanúgy elosztja a torta többi részét a megmaradt emberek között. $n-1$

Indukcióval igazolható, hogy minden résztvevő, aki betartja a szabályokat, garantáltan megkapja a torta 1/ n részét, függetlenül a többi résztvevő tevékenységétől. Ez egy diszkrét eljárás, amely körökben is végrehajtható. A legrosszabb esetben cselekvésre lesz szükség – minden résztvevő számára egy akció minden körben. A legtöbb ilyen művelet azonban papíron is elvégezhető. Tényleg csak bemetszésekre van szükség. Ezért ha a torta össze van kötve, akkor garantálható, hogy minden darab össze lesz kötve. $n\times (n-1)/2=O(n^{2})$ $n-1$

A "Moving Knife" Dubins - Spaniereljárás a "Last Reducing" [1] folyamatos változata .

A kés a tórusz mentén párhuzamosan mozog egyik végétől a másikig.
A versenyző azt mondja, hogy "stop", ha úgy ítéli meg, hogy a késtől balra lévő értéket elérte . Egy szelet tortát levágnak, és odaadják annak a résztvevőnek, aki mondta. ${\tfrac {1}{n))$
Ezt az eljárást megismételjük a torta többi részével és a többi résztvevővel. Az utolsó résztvevő kapja a torta többi részét.

A Fink-protokoll egy olyan algoritmus, amely továbbra is kellően kicsi, "egyenlő" darabokra oszlik.

Az első résztvevő az erőforrást olyan darabokra osztja, amelyeket egyenlőnek tart;
A második résztvevő választja a felét, a többit az első résztvevőre bízza;
E két résztvevő mindegyike harmadára osztja a részét;
A harmadik résztvevő választ kettőt a kapott részből – egyet-egyet az első és a második résztvevőtől;
Ha négy résztvevő van, az első három résztvevő mindegyike negyedekre osztja a részét, és a folyamat folytatódik.

Ennek a protokollnak az az előnye, hogy online is megtehető – új partnerek belépésekor a meglévő divízió hozzá lesz igazítva anélkül, hogy a teljes felosztási folyamatot elölről kellene kezdeni. Ennek az algoritmusnak az a hátránya, hogy minden résztvevő nagyszámú leválasztott darabot kap, nem pedig egy csatlakoztatott darabot.

Az egyszeri osztás egy egyenlő felosztáson alapuló eljárás, amelyet egyetlen ügynök hajt végre. Az eljárás előnye, hogya torta szimmetrikus tisztességes vágására.

Lásd még: [2] .

Rekurzív felezés

Az oszd meg és uralkodj stratégiával időben arányos osztás érhető el [3] . Az egyszerűség kedvéért az itt leírt eljárás páros számú résztvevőre vonatkozik, de könnyen adaptálható tetszőleges számú résztvevőhöz: $O(n\log n)$

Minden résztvevőnek húznia kell egy vonalat, amely a tortát két, általa egyenértékűnek ítélt részre osztja. Szükséges, hogy a vágások ne keresztezzék egymást. Ezt a legegyszerűbb úgy garantálni, ha csak vízszintes vagy csak függőleges vonalakat engedélyez.
Az algoritmus az n sort növekvő sorrendbe rendezi, és a tortát a vonalak mediánján vágja el . Például, ha 4 résztvevő van, akik vonalakat húznak a pontokban és , az algoritmus függőlegesen vágja el a tortát a pontban . $x=1,x=3,x=5$ $x=9$ $x=4$
Az algoritmus mind a két félhez n /2 résztvevőt rendel – olyan partnereket, akiknek vonalai a felében vannak. Például azok a tagok, akik vonalakat húztak a pontokhoz , a nyugati, míg a többi tagot a keleti feléhez rendelik. Mindegyik fél rekurzív módon felosztásra kerül az adott félhez rendelt n /2 résztvevő között. $x=1$ $x=3$

Indukcióval kimutatható, hogy minden játékosnak, aki a szabályok szerint játszik, garantált egy legalább 1/ n értékű bábu , függetlenül attól, hogy a többi játékos hogyan viselkedik.

Az oszd meg és uralkodj stratégiának köszönhetően az iterációk száma csak O(log n ) lesz, szemben a Last Decreasing eljárásban szereplő O( n ) értékkel. Minden iterációnál minden résztvevőnek egy jegyzetet kell készítenie. Ezért a pontok teljes száma egyenlő lesz . $O(n\log n)$

Az algoritmusnak van egy véletlenszerű változata, amellyel csökkenthető a kullancsok száma. Lásd az " Even-Paz algoritmus " című cikket.

Kiválasztási eljárások

A torta felvágásának másik módja az, hogy hagyjuk, hogy minden résztvevő a résztvevők számától, p ( n ) függően bizonyos számú darabot szedjen ki , és minden résztvevőnek adjon egy-egy kiválasztott darabot, hogy a darabok ne fedjék egymást.

A kiválasztási eljárás egyszerű példájaként képzeljünk el egy tortát egydimenziós szegmensként, és minden résztvevő külön összefüggő szegmenst szeretne kapni. A következő protokollt használjuk:

Minden résztvevő magántulajdonban n intervallumra osztja a tortát , amelyeket egyenlő értékűnek tart, nevezzük ezeket a darabokat jelölteknek .
A jegyzőkönyv a jelölteket keleti határaik sorrendjében (nyugatról keletre) rendezi, és kiválasztja a legnyugatibb keleti végű szakaszt. Ezt a szakaszt utolsó darabnak nevezzük . $n^{2}$
A protokoll átadja a végdarabot a tulajdonosának, és eltávolítja az összes jelöltet, amely metszi azt. A 2. lépést ezután megismételjük a többi résztvevő többi szegmensére. $n-1$

A 2. lépésben szereplő kiválasztási szabály biztosítja, hogy minden iterációnál minden résztvevőből legfeljebb egy szegmens kerüljön eltávolításra. Ezért minden iteráció után a résztvevőnkénti szegmensek száma egyenlő marad a résztvevők számával, és a folyamat addig folytatódhat, amíg minden résztvevő nem kap egy szegmenst [4] .

Ez a protokoll megköveteli, hogy minden fél n lekérdezésre válaszoljon , így a lekérdezés összetettsége hasonló a Last Decrease eljáráshoz. $O(n^{2})$

Véletlenszerű változatok

A véletlenszerűsítés segítségével csökkentheti a lekérdezések számát. Az ötlet az, hogy minden résztvevő nem a teljes n számú jelöltet jelenti, hanem csak a véletlenszerűen kiválasztott d állandó számú jelöltet. A lekérdezés összetettsége O( n ), ami nyilvánvalóan a lehető legjobb lesz. Sok esetben továbbra is lehetséges, hogy minden résztvevőnek egyetlen jelöltet adjunk, amely nem fedi át másokkal. Vannak azonban olyan forgatókönyvek, amikor ez a terjesztés nem lehetséges.

Ha kompromisszumot kötünk, O( n ) lekérdezésekkel megvághatjuk a tortát :

A teljes arányosság szavatolása helyett a részarányosságot garantáljuk , azaz minden résztvevő az összérték bizonyos f ( n ) állandó hányadát kapja, ahol . $f(n)<{\tfrac {1}{n))$
Ahelyett, hogy minden résztvevőnek külön összefüggő darabot adnánk át, egy vagy több nem metsző darab egyesülését adjuk át a résztvevőnek.

Az általános séma a következő [5] :

Minden résztvevő saját szubjektív értékelése szerint egyenlő darabokra osztja a tortát . Ezeket a darabokat jelölteknek nevezzük . $n\cdot an$
Minden résztvevő véletlenszerűen választ 2 d jelöltet, visszaküldéssel. A jelöltek d párba vannak csoportosítva , amelyeket a résztvevő jelent az algoritmusnak. Ezeket a párokat negyeddöntős sorozatoknak nevezzük . $n\cdot d$
Az algoritmus minden negyeddöntős sorozatból kiválaszt egy darabot, azt, amelyik a legkevesebb jelöltet metszi. Ezeket a darabokat elődöntőnek nevezzük . $n\cdot d$
Az algoritmus minden résztvevő számára kiválaszt egy darabot, nevezzük véglegesnek . Az utolsó darabokat úgy kell kiválasztani, hogy a torta minden pontját legfeljebb két utolsó darab fedje le (lásd alább). Ha ez sikerült, folytassa az 5. lépéssel. Ha nem sikerül, térjen vissza az 1. lépéshez.
A torta minden darabját, amely csak egy utolsó darabhoz tartozik, a tulajdonosa kapja. A torta minden részét, amely az utolsó két darabhoz tartozik, arányosan elosztjuk bármely determinisztikus arányos osztási algoritmussal.

Az algoritmus garantálja, hogy minden résztvevő legalább a felét megkapja valamelyik jelölt darabjából, ami azt jelenti (ha a becslések összeadódnak), hogy a becslés nem lesz kisebb, mint 1/2 an . Az 5. lépésben O( n ) jelölt darab és O( n ) extra osztás található, mindegyik O(1) időt vesz igénybe. Ezért az algoritmus teljes futási ideje O( n ). $O(1a^{2})$

A fő probléma ebben a sémában az utolsó darabok kiválasztása a 4. lépésben. Lásd az Edmonds-Prus protokollt a részletekért .

Eredmények nehézség szerint

A komplexitásra vonatkozó eredményeket a "standard Robertson-Webb modell" szerint fogalmazzák meg, vagyis kétféle műveletet használó eljárásokra vonatkoznak: "Becslés" és "Vágás".

Bármilyen determinisztikus arányos osztási eljárásnak legalább n műveletet kell használnia a résztvevők számára, még akkor is, ha az összes pontozási függvény azonos [3] . $n\geqslant 3$

Ezenkívül minden determinisztikus vagy véletlenszerű (valószínűségi) arányos osztási eljárásnak, amely minden résztvevőhöz kapcsolt darabot rendel, műveleteket kell alkalmaznia [6] . $\Omega (n\log n)$

Ezenkívül minden determinisztikus arányos felosztási eljárásnak műveleteket kell végrehajtania , még akkor is, ha az eljárás minden résztvevőhöz hozzárendelhet egy darabot, amely a szegmensek egyesülése, és akkor is, ha az eljárás csak hozzávetőleges igazságosságot garantál . A bizonyítás azon az alsó határon alapul, hogy az egyes játékosok számára egy nagy értékű és vékony szelet tortát kell találni [7] [8] . $\Omega (n\log n)$

Ezekből a nehézségi eredményekből az következik, hogy a rekurzív felezés a leggyorsabb algoritmus az összefüggő darabokkal való teljes arányosság elérésére, és ez a lehető leggyorsabb determinisztikus algoritmus a részarányosság elérésére szétválasztott darabokkal is. Az egyetlen eset, ahol javítható, a véletlenszerű algoritmusok, amelyek garantálják a részleges arányosságot a szétkapcsolt darabokkal.

Ha a játékosok csak véges pontossággal tudnak vágni, akkor az alsó korlát a randomizált protokollokat is tartalmazza [7] [8] . $\Omega (n\log n)$

Az alábbi táblázat az ismert eredményeket tartalmazza [5] :

Arányosság ( teljes / részleges)	Darabok (csatlakoztatva / leválasztva)	Protokoll típusa (determinisztikus / randomizált )	Lekérdezések (pontos/ hozzávetőleges)	Kérelmek száma
teljes	hírnökök	meghatározó	pontos	$O(n\log n)$ [3] [6] $\Omega (n\log n)$
teljes	hírnökök	meghatározó	hozzávetőleges	$\Omega (n\log n)$ [6]
teljes	hírnökök	véletlenszerűsített	pontos	$O(n\log n)$ [3] [6] $\Omega (n\log n)$
teljes	hírnökök	véletlenszerűsített	hozzávetőleges	$\Omega (n\log n)$ [6]
teljes	összefüggéstelen	meghatározó	pontos	$O(n\log n)$ [3] [7] [8] $\Omega (n\log n)$
teljes	összefüggéstelen	meghatározó	hozzávetőleges	$\Omega (n\log n)$ [7] [8]
teljes	összefüggéstelen	véletlenszerűsített	pontos	$O(n\log n)$ [3]
teljes	összefüggéstelen	véletlenszerűsített	hozzávetőleges	$\Omega (n\log n)$ [7] [8]
részleges	hírnökök	meghatározó	pontos	$\Omega (n\log n)$ [3] [7] [8] $\Omega (n\log n)$
részleges	hírnökök	meghatározó	hozzávetőleges	$\Omega (n\log n)$ [7] [8]
részleges	hírnökök	véletlenszerűsített	pontos	$\Omega (n\log n)$ [3]
részleges	hírnökök	véletlenszerűsített	hozzávetőleges	$\Omega (n\log n)$ [7] [8]
részleges	összefüggéstelen	meghatározó	pontos	$O(n\log n)$ [3] [7] [8] $\Omega (n\log n)$
részleges	összefüggéstelen	meghatározó	hozzávetőleges	$\Omega (n\log n)$ [7] [8]
részleges	összefüggéstelen	véletlenszerűsített	pontos	O( n ) [5]
részleges	összefüggéstelen	véletlenszerűsített	gyengén közelítő ( a becslési hibától független)	O( n ) [5]
részleges	összefüggéstelen	véletlenszerűsített	hozzávetőleges	$\Omega (n\log n)$ [7] [8]

Opciók

Különféle megosztások esedékes

Az arányossági teszt általánosítható olyan helyzetre, amelyben a résztvevők esedékes részesedése nem egyenlő. Például egy erőforrás két részvényes tulajdonában lehet, Alice részvényekkel, George pedig . Ez egy súlyozott arányossági (WPR) kritériumhoz vezet – vannak w i súlyok , amelyek összege 1, és minden i résztvevőnek meg kell kapnia legalább w i részt az erőforrásból saját értékelése szerint. Számos algoritmus használható a WPR-felosztás megtalálásához. A fő probléma az, hogy a vágások száma akkor is nagy lehet, ha csak két résztvevő van. Lásd: A torta arányos felvágása különböző esedékes megosztásokkal . ${\tfrac {8}{13}}$ ${\tfrac {5}{13}}$

Szuperarányos osztás

Szuperarányos felosztásnak nevezzük azt a felosztást, amelyben minden résztvevő saját szubjektív értékelése szerint szigorúan több mint 1/ n -ben részesül az erőforrásból.

Természetesen ilyen felosztás nem mindig létezik – ha minden résztvevőnek pontosan ugyanazok az értékelési funkciói vannak, akkor a legjobb, amit tehetünk, ha mindenkinek pontosan 1/ n -t adunk . A szuperarányos felosztás fennállásának tehát szükséges feltétele az a követelmény, hogy ne legyen minden partner azonos értékmérővel.

Meglepő módon, ha az értékelési függvények additívak és nem atomiak, ez a feltétel is elegendő. Vagyis ha van legalább két résztvevő, akiknek az értékelési funkciói csak kis mértékben különböznek, akkor van egy szuperarányos felosztás, amelyben minden résztvevő 1/ n - nél többet kap . A részletekért lásd a Szuperarányos felosztást .

A környék korlátozásai

A szokásos korlátozáson túl, hogy minden darabot össze kell kötni, bizonyos esetekben további korlátozások is vonatkoznak. Különösen, ha a felosztandó torta egy vitatott terület, amely több ország között fekszik, minden egyes országnak adott darabnak az ország jelenlegi határával szomszédosnak kell lennie. Az arányos felosztás ebben az esetben mindig létezik, és a Last Decrease protokoll és a konform leképezéseket használó geometriai technikák kombinálásával érhető el . Lásd " A Hill-Beck földosztási probléma " című cikket.

2D geometriai kényszerek

Amikor egy "tortát" kétdimenziós térben (síkban) osztanak fel, például ha telkeket vagy reklámfelületeket osztanak fel nyomtatott vagy elektronikus médiában, akkor gyakran megkövetelik, hogy a daraboknak az összekapcsolhatóságon kívül bizonyos geometriai korlátoknak is eleget kell tenniük. Például megkövetelhető, hogy minden darab legyen négyzet, vastag téglalap (vagyis a hosszúság és a szélesség nem tér el többszörösen), vagy egy általános formájú vastag figura Az ábrákra vonatkozó ilyen megszorítások esetén az arányos osztás általában nem létezik, de a részleges arányos osztás általában létezik, és hatékony algoritmusok segítségével megtalálható [9] .

Gazdaságilag hatékony felosztás

Az arányosság mellett gyakran megkövetelik, hogy a felosztás gazdaságilag hatékony legyen , azaz maximalizálja a teljes hasznot (az összes ügynök hasznosságának összegeként definiálva).

Vegyünk például egy 500 gramm csokoládét és 500 gramm vaníliát tartalmazó tortát, amelyen két résztvevő osztozik, akik közül az egyik csak csokoládét, a másik pedig a vaníliát szereti. Sok süteményvágási protokoll minden ügynöknek 250 gramm csokoládét és 250 gramm vaníliát ad. Ez a felosztás arányos, hiszen minden résztvevő az összérték 0,5-ét kapja, így a normalizált összhaszon 1. Ez a felosztás azonban nagyon hatástalan lesz, hiszen a csokoládé teljes részét odaadhatjuk az első résztvevőnek, és az összes vaníliás részt. a másik résztvevőnek normalizált teljes juttatásban részesül 2.

Az optimális arányos osztás problémája egy olyan arányos felosztás megtalálásának problémája, amely maximalizálja a teljes hasznot az összes lehetséges arányos eloszlás között. A problémára jelenleg csak nagyon speciális torták esetében van megoldás, ha egydimenziós szegmensről van szó, és a hasznosságsűrűség függvények lineárisak (vagyis ). Általában véve a probléma NP-nehéz . Ha a hasznossági függvények nincsenek normalizálva (vagyis megengedjük, hogy minden résztvevő más-más becsléssel rendelkezzen a torta teljes jelentőségét illetően), a probléma NP-nehéz még a [10] tényezővel való közelítésnél is . $u(x)=Ax+B$ ${\displaystyle {\tfrac {1}{\sqrt {n))))$

Fair divízió

A méltányosság nem a felosztás, hanem inkább a protokoll tulajdonsága. Valamennyi arányos osztási protokoll gyengén igazságos abban az értelemben, hogy minden valódi értéke szerint cselekvő résztvevő garantáltan legalább 1/ n -t (vagy részarányos protokoll esetén 1/ an -t) kap, függetlenül attól, hogy a többi résztvevő hogyan viselkedik. Még ha a többi tag koalíciót köt is csak azért, hogy kárt okozzon neki, akkor is megkapja garantált arányát [11] .

A legtöbb protokoll azonban nem szigorúan tisztességes abban az értelemben, hogy egyes résztvevők hazudni akarnak, hogy még többet kapjanak, mint amennyit garantáltak. Ez még egy egyszerű oszd meg és válassz protokollra is igaz – ha a vágó ismeri a választó preferenciáit, akkor le tud vágni egy olyan darabot, amelyet a választó 1/2 alá értékel, de amit maga a vágó jóval többre értékel. 1/2.

Vannak igazságos mechanizmusok a tökéletes partíció elérésére . Mivel a tökéletes osztás arányos, ezek a mechanizmusok egyben igazságos arányos osztási mechanizmusok is.

Ezek a mechanizmusok kiterjeszthetők szuperarányos felosztás elérésére , ha létezik [12] :

Minden résztvevőtől teljes körű értékelést kérünk.
Véletlenszerű partíciót választunk (a részletekért lásd Mossel és Tamuz [12] cikkét ).
Ha a véletlenszerű felosztás szuperarányosnak bizonyul a közölt mértékek szerint, akkor azt végrehajtjuk. Ellenkező esetben igazságos mechanizmust alkalmazunk a tökéletes felosztás érdekében.

Ha létezik szuperarányos felosztás, akkor pozitív esély van arra, hogy a 2. lépésben megkapjuk. Ezért bármely becsületes résztvevő esetében a várható érték szigorúan nagyobb, mint 1/ n . Annak megértéséhez, hogy a mechanizmus igazságos, tekintsünk három esetet: (a) Ha a kiválasztott partíció valóban szuperarányos, akkor a hazugság egyetlen lehetséges eredménye az, hogy a mechanizmust becsapja azzal a gondolattal, hogy a partíció nem szuperarányos. Ez arra kényszeríti a mechanizmust, hogy tökéletes felosztást alkalmazzon, ami minden érintett számára rosszabb, beleértve a kést is. (b) Ha a kiválasztott partíció csak azért nem szuperarányos, mert a hazug 1/ n -t vagy kevesebbet ad meg, akkor a hazugság egyetlen hatása az, hogy a motor azt gondolja, hogy a partíció szuperarányos , és használja azt, ami csak a hazudozónak fog fájni. (c) Ha a kiválasztott felosztás valóban nem szuperarányos, ami 1/ n vagy annál kisebb értéket ad a másik félnek, akkor a false-nak nincs hatása, mivel a felosztás egyáltalán nem kerül felhasználásra.

Arányos feladatmegosztás

Ha a megosztandó erőforrás nem kívánatos (hasonlóan a feladatmegosztáshoz ), akkor az arányos felosztást úgy határozzuk meg, hogy az egyes személyeknek legfeljebb az erőforrás 1/ n -ét adják (azaz az egyenlőtlenség jelét a másik irányba).

A legtöbb arányos felosztási algoritmus nehézség nélkül adaptálható a feladatok megosztására.

Lásd még

Pontos felosztás . Lásd még "Tökéletes felosztás"

Jegyzetek

↑ Dubins és Spanier, 1961 , p. 1–17.
↑ Tasnádi Attila. Az n-személyes tortavágás problémájával arányos új eljárás . kutatókapu. Letöltve: 2015. szeptember 24. (határozatlan)
↑ 1 2 3 4 5 6 7 8 9 Even, Paz, 1984 , p. 285.
↑ Az eljárás ezen része hasonló a mohó polinom megoldáshoz )
↑ 1 2 3 4 Edmonds, Pruhs, 2006 , p. 623–634.
↑ 1 2 3 4 5 Woeginger, 2007 , p. 213–220.
↑ 1 2 3 4 5 6 7 8 9 10 11 Edmonds, 2006 , p. 271–278.
↑ 1 2 3 4 5 6 7 8 9 10 11 Edmonds, 2011 , p. 1–12.
↑ Segal-Halevi, Nitzan, Hassidim, Aumann, 2017 , p. 1–28.
↑ Bei, Chen, Hua et al., 2012 .
↑ Steinhaus, 1948 , p. 101–4.
↑ 1 2 Mossel, Tamuz, 2010 , p. 288–299.

Irodalom

Az arányos és egyéb felosztások áttekintése jelent meg a cikkben:
Austin AK Sharing a Cake // The Mathematical Gazette. - 1982. - T. 66 , sz. 437 . — S. 212–215 . - doi : 10.2307/3616548 . — .
Lester Eli Dubins, Edwin Henry Spanier. Hogyan vágjunk tisztességesen egy tortát // Az amerikai matematikai havilap. - 1961. - T. 68 , sz. 1 . - doi : 10.2307/2311357 . — .
Even S., Paz A. Megjegyzés a tortavágásról // Discrete Applied Mathematics. - 1984. - T. 7 , sz. 3 . - doi : 10.1016/0166-218x(84)90005-2 .
Jeff Edmonds, Kirk Pruhs. Balanced Allocations of Cake // 2006 47. éves IEEE szimpózium a számítástechnika alapjairól (FOCS'06). - 2006. - ISBN 978-0-7695-2720-8 . - doi : 10.1109/focs.2006.17 .
Gerhard J. Woeginger. A tortavágás összetettségéről // Discrete Optimization. - 2007. - T. 4 , sz. 2 . - doi : 10.1016/j.disopt.2006.07.003 .
Jeff Edmonds. A tortavágás valóban nem egy torta // A tizenhetedik éves ACM-SIAM szimpózium a diszkrét algoritmusról - SODA '06 anyaga. - 2006. - ISBN 978-0898716054 . doi : 10.1145 / 1109557.1109588 .
Jeff Edmonds. A tortavágás valóban nem egy darab torta // ACM Transactions on Algorithms. - 2011. - T. 7 , sz. 4 . - doi : 10.1145/2000807.2000819 .
Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, Yonatan Aumann. Fair and square: Tortavágás két dimenzióban // 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. Optimális arányos tortavágás összekapcsolt darabokkal // AAAI konferencia előadások. — 2012.
Hugo Steinhaus. Az igazságos felosztás problémája // Econometrica. - 1948. - T. 16 , sz. 1 . — .
Elchanan Mossel, Omer Tamuz. Truthful Fair Division // . - 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 .