Féltékeny tortavágás

Az irigy tortavágás [1] egyfajta tisztességes tortavágás . Ez egy heterogén erőforrás ("torta") felvágása az irigység hiányának kritériumának kielégítésével , nevezetesen, hogy bármely résztvevőnek az az érzése, hogy a számára kiosztott rész (saját szubjektív értékelése szerint) nem kevesebb. mint a többi résztvevőnek adott darabok.

Ha csak két résztvevő van, a probléma egyszerű, és a bibliai időkben a Szabadítsd meg és válassz protokollt megoldották . Ha három vagy több résztvevő van, a feladat lényegesen nehezebbé válik.

A probléma két fő változatát tanulmányozták:

összefüggő darabok, például egydimenziós szegmens esetén minden résztvevőnek külön részintervallumot kell kapnia. Ha három résztvevő van, akkor teljes vágásra van szükség. $n$ $n-1$
általános formájú darabok, például egydimenziós szegmens esetén minden résztvevőnek meg kell szereznie nem metsző részszegmensek unióját.

Rövid előzmények

A méltányos tortavágás problémájának modern kutatása az 1940-es években kezdődött. A méltányosság első kritériuma az arányos osztás volt , és hamarosan megszületett az eljárás n résztvevőre .

Az irigység hiányának szigorúbb kritériumát Georgy Gamow és Marvin Stern vezette be a tortavágás problémájába az 1950-es években [2] .

A három résztvevős eljárást és a darabok általános megjelenését 1960-ban találták meg. A három résztvevőre és az összefüggő darabokra vonatkozó eljárást csak 1980-ban találták meg.

A négy vagy több személyre való irigy felosztás nyitott probléma volt egészen az 1990-es évekig, amikor is megjelent három eljárás a darabok általános formájára és egy eljárás a kapcsolódó darabokra. Mindezek az eljárások korlátlanok – számos lépést igényelhetnek, amelyek előre nem korlátozottak. Az összekapcsolt darabok eljárása akár végtelen számú lépést is igényelhet .

A 2000-es években két alsó határt tettek közzé az irigy felosztási probléma futási időbeli összetettségére vonatkozóan:

általános alakú daraboknál az alsó korlát egyenlő ; $\Omega (n^{2})$
összekapcsolt daraboknál az alsó korlát egyenlő a végtelennel – három vagy több résztvevő esetében talán nincs végleges protokoll.

A 2010-es években néhány közelítési eljárást és különleges esetekre vonatkozó eljárást tettek közzé. Az a kérdés, hogy vannak-e korlátozott futási idejű eljárások az általános formájú darabokra, sokáig nyitott maradt. A probléma végül 2016-ban megoldódott. Haris Aziz és Simon McKenzie egy diszkrét irigy felosztási protokollt javasoltak, amelyhez nincs szükség több kérésre. Az alsó határ és az eljárás által megadott érték között még mindig óriási a szakadék. 2016 augusztusára az irigy megosztási probléma pontos időbeli összetettsége ismeretlen maradt. ${\displaystyle n^{n^{n^{n^{n^{n))))))))$

Az összekapcsolt darabok esetében megfigyelhető, hogy a nehézségi eredmény azt jelenti, hogy az egész darabot fel kell osztani. Ha ezt a követelményt felváltja az a gyengébb követelmény, hogy bármely résztvevő kapjon arányos értéket (saját becslése szerint legalább a teljes részt), akkor ismert a korlátozott eljárás három résztvevőre, de továbbra is nyitott kérdés, hogy van-e korlátozott futási idővel négy vagy több tag számára. ${\tfrac {1}{n))$

Összekapcsolt darabok

Létezési bizonyíték

A következő feltevések mellett mindig létezik n ügynök irigy felosztása összekapcsolt darabokkal [3] .

egyetlen ügynök sem részesíti előnyben az üres darabot (üres pontkészletet) a nem üres darabokkal szemben;
Az ügynökök preferenciái folyamatosak.

Nem szükséges, hogy az ügynökök preferenciáit additív függvény képviselje .

A bizonyítás fő koncepciója a particionáló szimplex . Tegyük fel, hogy a torta egy szegmens [0;1]. Minden egyes összefüggő részekkel rendelkező partíció egyedileg ábrázolható n − 1 számmal a [0;1] intervallumban, minden szám a vágás helyét jelöli. Az összes partíció uniója szimplex.

Bármely partícióhoz minden ügynöknek van egy vagy több darabja, amelyet preferál. Például a "0.3;0.5" számokkal jelzett partíciónál az egyik ügyintéző az 1. darabot ([0;0.3] szegmens), míg egy másik ügynök a 2. darabot (szegmens [0, 3;0.5]) részesítheti előnyben. , a harmadik ügynök pedig az 1-es és a 2-es darabot preferálja (ami szerinte azt jelenti, hogy nincs köztük különbség, de jobbak, mint a 3. darab).

Bármely ügynök esetében a particionáló szimplexet n rész fedi le, amelyek esetleg átfedik egymást a határaik mentén, így az i rész összes partíciója esetén az ügynök az i darabot részesíti előnyben . Az i rész belsejében az ügynök csak az i darabot részesíti előnyben, bár az i rész határán más darabokat is előnyben részesít. Így bármely i esetén van egy bizonyos régió a partíció szimplexben, amelyben legalább egy ügynök csak az i darabot részesíti előnyben . Nevezzük ezt a területet . Néhány topológiai lemma segítségével (amely hasonló a Knaster-Kuratowski-Mazurkiewicz lemmához) bebizonyíthatjuk, hogy az összes U i metszéspontja nem üres. Ezért van egy partíció, amelyben minden egyes darab az egyetlen, amelyet az ügynök preferál. Mivel a darabok száma megegyezik az ügynökök számával, minden darabot kioszthatunk az azt preferáló ügynöknek, és irigységmentes elosztást kapunk. $U_{i}$

Eljárások

Három ügynök esetében több különböző eljárással irigységmentes partíció található:

Stromkvist „Moving Knife” eljárása négy egyidejűleg mozgó kést használ – az egyik kést a játékvezető mozgatja, a másik hármat pedig minden ügynöknek egyet;
Barbanel-Brahms Moving Knife eljárása két, egyidejűleg mozgó kést használ;
Robertson-Webb „Moving Knife” eljárása akkor használható, ha a torta kétdimenziós, és csak egy mozgó kést használunk.

Vannak folyamatos eljárások - ezek a kések folyamatos és egyidejű mozgásán alapulnak. Ezek az eljárások nem hajthatók végre véges számú különálló lépésben.

Az n résztvevő esetében az irigység nélküli szétválást találhatja meg a Simmons-Su tortavágási protokoll . A protokoll particionáló szimplexet használ , hasonlóan ahhoz, amit Stromquist létezésének bizonyítása használ. A protokoll partíciók sorozatát alkotja, amely irigység nélkül konvergál partícióvá. A konvergencia végtelenül sok lépést igényelhet.

Nem véletlen, hogy mindezen algoritmusok végtelen számú kérést igényelnek. Ahogy a következő alfejezetben látni fogjuk, nem biztos, hogy véges számú lekérdezéssel találhatunk irigységmentes tortadarabokat egymáshoz kapcsolódó darabokkal.

Eredmények nehézség szerint

A véges protokoll nem talál egy irigységmentes partíciót 3 vagy több ügynök összekapcsolt darabjaival [4] . Ennek az eredménynek az oka nem mond ellent a fent említett algoritmusoknak, mivel azok matematikai értelemben nem végesek [5] .

A lehetetlenség bizonyítása merev mértékrendszert ( RMS) használ – egy n mérési mérőszámból álló rendszert , amelynél az irigység nélküli felosztásnak nagyon meghatározott helyeken kell megvágnia a tortát. Ezután az irigység nélküli megosztottság keresése e konkrét helyek keresésére redukálódik. Feltételezve, hogy a torta egy valós intervallum [0;1], egy partíció keresése irigység nélkül a résztvevők lekérdezésével egyenlő a valós számok keresésével a [0;1] intervallumban igen/nem kérdésekkel. Ehhez végtelen számú kérdésre lehet szükség.

Az RMS három résztvevő számára a következőképpen építhető fel. Legyen x , y , s és t a feltételeket kielégítő paraméterek

$0<x<y<1,$
$0<s<{\tfrac {1}{3}}<t<{\tfrac {1}{2)),$
$s+2t=1.$

Készítsünk három mértékhalmazt két tulajdonsággal:

az egyes mértékek sűrűsége szigorúan és között van (úgy, hogy egy adott darab esetében az ágensek becslései legfeljebb kétszeresével térjenek el); ${\tfrac {\sqrt {2}}{2}}$ ${\sqrt {2}}$
az x és y számokkal meghatározott darabok értékeit a táblázat tartalmazza:

Ügynök	[0; x ]	[ x ; y ]	[ y ;1]
A	t	t	s
B	s	t	t
C	t	s	t

Ezután az Alice, Bob és Carl közötti irigységmentes partíción x -en és y -n kell vágni (pontosan két ilyen partíció van), mivel minden más hely irigységhez vezet:

ha az x -től balra és y - tól jobbra vágunk , akkor Alice és Bob ragaszkodik a középső darabhoz;
ha a vágásokat x -től jobbra és y - tól balra végezzük , akkor egyik résztvevő sem akarja elvenni a középső darabot;
ha x -től jobbra és y -tól jobbra vágunk (mondjuk x* > x és y* > y ), akkor Alice és Carl is a bal oldali darabokat részesíti előnyben a jobb oldaliak helyett, így Bobnak bele kell egyeznie, hogy a jobb oldali darabot vegye el. Ez azt jelenti, hogy Bobnak értékelnie kell a darabot [ x ; x* ] legalább kétszer akkora, mint [ y ; y* ]. De az ár sűrűségének korlátozása miatt ez azt jelenti, hogy Alice és Carl is rendelkezik a becsléssel [ x ; x* ] nagyobb, mint [ y ; y* ], tehát ragaszkodni fognak a bal oldali darabokhoz;
a negyedik eset (az x -től balra és az y -tól balra lévő vágás ) hasonló az előzőhöz.

Bármely RMS, bármely i ügynök és bármely konstans esetén létezik egy kissé eltérő RMS a következő tulajdonságokkal: $\varepsilon >0$

az i ügynök becsléseinek új mértéke teljesen megegyezik a becsléseinek régi mértékével;
a másik két ágens becsléseinek új mértéke mindenhol megegyezik a régi mértékével, kivéve az x és y pontok környezetét . $\varepsilon$

Ez azt jelenti, hogy ha egy lekérdezés válaszol valamire az x és y környéken kívül, az i ügynök nem tudja megtudni, hogy a régi RMS vagy az új RMS volt-e.

Ezzel a tudással bármilyen irigy felosztási protokollt el lehet homályosítani, hogy az a végtelenségig tartson:

Kezdjük bármelyik RMS-sel, például a paraméterekkel ; $x={\tfrac {1}{3));y={\tfrac {2}{3));s=0.3;t=0.35$
ha a protokoll x -en és y -n kívül vág , csak folytassa;
amikor a protokoll megkéri az i résztvevőt , hogy végezzen vágást x vagy y pontban , váltson át másik RMS-re a és gombbal , ügyelve arra, hogy az értékek megegyezzenek az előző vágások értékével. $x'\neq x$ $y'\neq y$

Ez a protokoll soha nem tud a megfelelő x és y pontokon vágni, amelyek az irigységmentes felosztáshoz szükségesek.

Közelítések

Mivel az összefüggő darabokkal irigységmentes tortavágást nem lehet véges idő alatt elvégezni, a pogácsaszaggatóknak valahogy meg kell próbálniuk megkerülni ezt a problémát.

Az egyik megközelítés az, hogy olyan megosztottságokat keresünk, amelyek csak megközelítőleg mentesek az irigységtől . A közelítés kétféleképpen definiálható – hosszegységben vagy értékelési egységben .

A hossz alapú közelítés a következő definíciókat használja.

A tortafelosztást a felosztás által létrehozott n hosszúságú szegmens képviseli. Így (0,2; 0,5; 0,3) az egységszegmens felosztása három részintervallumra, amelyek hossza 0,2, 0,5 és 0,3 (a partíciót az egységszegmens 0,2 és 0, 7 pontokban történő levágásával alakítjuk ki).
A többpartíció több különböző partíció halmaza. X többpartícióját irigységmentesnek mondjuk, ha létezik a résztvevők olyan permutációja, hogy bármely i -hez létezik olyan X-elem, hogy az i - edik résztvevő az i - edik szegmenst preferálja. A -multipartition olyan többpartíció, amelyben az egyes partíciópárok koordinátái közötti különbség nem haladja meg a -t . Például: {(0.2+ ;0.5;0.3), (0.2;0.5+ ;0.3), (0.2;0.5;0.3+ )}. $\delta$ $\delta$ $\delta$ $\delta$ $\delta$

A paraméter a résztvevők tűréshatárát jelöli hosszegységekben. Például, ha egy földdarabot felosztanak, és a résztvevők egyetértenek abban, hogy a 0,01 méteres határeltérés nem számít számukra, akkor érdemes egy irigységmentes 0,01-es partíciót nézni. Deng, Key és Sabery [6] a Simmons tortavágási protokoll módosítását javasolta , amely egy irigységmentes lekérdezés -alapú többpartíciót tartalmaz . Sőt, bebizonyították a lekérdezések alsó határát. Még akkor is, ha a hasznossági függvényeket kifejezetten polinomiális idő algoritmusok adják meg, az irigységmentes tortavágás PPAD- kemény . $\delta$ $\delta$ $O[(1/\delta )^{n-2}]$ $\Omega [{\tfrac {(1/\delta )^{n-2}}{2^{(n-1)(n-2)))}]$

Az értékalapú közelítés a következő jelölést használja:

az X partíciót irigységmentesnek nevezzük, ha a résztvevők olyan permutációja van, hogy bármely i -re az i - edik darab plusz értéke nem kisebb, mint bármely másik darab értéke: ; $\varepsilon$ $\varepsilon$ $\forall i,j:V_{i}(X_{i})+\varepsilon \geqslant V_{i}(X_{j})$
egy kiértékelő mértéket Lipschitz folytonosnak mondunk, ha létezik olyan K állandó , hogy bármely szegmenspárnál az értékkülönbség nem haladja meg a szimmetrikus különbségük K -szeres hosszát . $\exists K:\forall j:|V_{i}(X_{i})-V_{i}(X_{j})|\leqslant K\cdot \mathrm {length} (X_{i}\ setminus X_{j}\cup X_{j}\setminus X_{i})$

Ha minden becslési mérték Lipschitz folytonos, akkor a közelítés két definíciója összefügg. Hadd . Ekkor bármely irigység nélküli partíció a -multipartícióban -mentes az irigységtől [6] . Ezért Deng, Key és Sabury eredményei azt bizonyítják, hogy ha minden résztvevőnek Lipschitz folytonos korlátja van, akkor lekérdezések segítségével irigységmentes partíciót lehet találni . $\varepsilon =2K\delta$ $\delta$ $\varepsilon$ $\varepsilon$ $\Theta [(1/\varepsilon )^{n-2}]$

Az offline számítástechnika a második megoldás, amely teljesen irigység nélkül találja meg az elosztást, de csak a becslések korlátozott osztályára. Ha minden kiértékelési mérték legfeljebb d fokú polinom , akkor van olyan algoritmus, amely polinom n -ben és d -ben [7] . Ha d adott, az algoritmus d + 1 értékelési kérelmet kér az ügynököktől, ami d + 1 pontot ad az értékelési mérődiagramon. Ismeretes, hogy d +1 pont elég egy d fokú polinom interpolálásához . Ezért az algoritmus képes interpolálni az összes ágens becslésének összes mértékét, és autonóm módon találni egy irigységmentes eloszlást. A szükséges kérelmek száma . $O(n^{2}d)$

A leejtés egy harmadik megoldás, amely megtartja azt a követelményt, hogy a kapott vágás teljesen irigységmentes legyen, és minden értékelési intézkedésnél működik, de az a követelmény, hogy az egész tortát fel kell osztani, ebben az esetben kimarad. Vagyis megengedett a torta egy részhalmazának felosztása és a maradék eldobása. További követelmények nélkül a probléma triviális, mivel úgy oldják meg, hogy a teljes tórusz kidobják anélkül, hogy a darabokat ügynökökhöz osztanák. Így az igazi cél az, hogy minden ügynök szigorúan pozitív értéket adjon. Minden tortaelosztás jellemezhető egy arányossági szinttel , amely a legkevésbé szerencsés ügynök értéke. Az egész torta irigység nélküli megtörése szintén arányos felosztás , és az arányosság mértéke ebben az esetben nem kevesebb, mint , a lehető legjobb érték. De abban az esetben, ha az eldobás engedélyezve van, az irigységmentes kiosztás alacsonyabb arányú lehet, és a cél az irigységmentes felosztás megtalálása a lehető legmagasabb arányban. Jelenleg ismert határok: $1/n$

3 ügynök esetében az arányosság , azaz az irigy osztás és arányos felosztás korlátozott időn belül elérhető [8] ; $1/3$
4 ügynök esetén az arányosság [8] ; $1/7$
n ágens esetén az arányosság [9] . $1/(3n)$

Nem tudni, hogy az összefüggő darabok esetében van-e időkorlátos arányos osztási eljárás, irigység nélkül négy vagy több résztvevőre.

Opciók

Az összekapcsolt darabokból álló torta vágására vonatkozó legtöbb eljárás azt feltételezi, hogy a torta egydimenziós szegmens, a darabok pedig részintervallumok. Gyakran kívánatos, hogy a darabok egy bizonyos geometriai alakkal rendelkezzenek, például négyzet alakúak. Egy ilyen megszorítás mellett előfordulhat, hogy nem lehet felosztani az egész tortát (például egy négyzet nem osztható két négyzetre), ezért kell, hogy legyenek el nem osztott darabok. A fentebb kifejtetteknek megfelelően, amikor a fel nem osztott darabok megengedettek, az eljárásokat arányossági szintjük alapján mérik – az az érték, amelyet minden résztvevő számára garantálnak. Jelenleg a következők ismertek [10] :

két résztvevőnél egy négyzet alakú torta felosztásakor és négyzet alakú darabokat szeretnének kapni, az arányosság egyenlő , és ez a legjobb, amit irigység nélkül is lehet garantálni; $1/4$
három résztvevő esetében, ha egy négyzet alakú tortát osztunk fel, és négyzet alakú darabokat szeretnénk kapni, az arányosság . A legjobb, amit az irigység hiányában garantálni lehet . $1/10$ $1/6$

Leválasztott darabok

Eljárások

Három résztvevő esetében a diszkrét Selfridge-Conway eljárás irigy osztást hajt végre, legfeljebb 5 vágással. A mozgó késeket használó egyéb eljárások kevesebb bemetszést igényelnek:

Levmore Moving Knife eljárása – A főzéshez maximum 4 bemetszés szükséges;
a Brahms-Taylor-Zwicker kések forgatásának eljárása a torta vágásához legfeljebb 3 vágást igényel (ez az eredmény három összefüggő darabnál, ha a torta kör, de egy szelet alakú torta esetén ott négy darab lesz);
Az Austin-féle „Moving Knife” eljárást használva két résztvevőnél irigységmentesen el lehet választani 3 résztvevőt legfeljebb 3 vágással. Ezt az elképzelést William Webbnek tulajdonítják [11] .

Négy résztvevő esetében a Brahms-Taylor-Zwicker eljárás nem több, mint 11 vágást végez irigység nélkül [12] . Öt résztvevő esetében Sabery és Wang eljárása korlátozott számú vágást tesz lehetővé irigység nélkül [13] . Mindkét eljárás az austini eljárást használja két résztvevő és közös felosztás esetén kezdeti lépésként. Ezért ezeket az eljárásokat végtelennek kell tekinteni – nem hajthatók végre véges számú lépésben.

Négy vagy több résztvevő esetében három véges, de nem korlátozott algoritmus létezik – a szükséges vágások számának nincs fix korlátja [14] . Három ilyen algoritmus létezik:

a Brahms-Taylor eljárás , amelyet először egy 1995-ös, majd egy 1996-os könyvben tettek közzé;
a Robertson-Webb Protokoll , amely először egy 1997-es cikkben, majd egy 1998-as könyvben jelent meg;
Pikhurko jegyzőkönyvét [15] 2000-ben tették közzé.

Bár a protokollok különböznek, a fő gondolatuk hasonló marad - a tortát véges, de nem korlátozott számú "morzsára" osztjuk, amelyek mindegyike olyan kicsi, hogy minden résztvevő figyelmen kívül hagyja az értékét. Ezután a morzsákat kifinomultan összedolgozzuk, hogy megkapjuk a kívánt felosztást. William Gassar három korlátlan algoritmust hasonlított össze sorszámok segítségével [16] .

Az a kérdés, hogy négy vagy több résztvevő esetében irigység nélkül elvégezhető-e a tortavágás, hosszú évek óta nyitott probléma maradt. Végül 2016-ban Hariz Aziz és Simon McKenzie oldotta meg. Kezdetben egy korlátozott időre szóló algoritmust dolgoztak ki négy résztvevő számára [17] . Ezután kiterjesztették algoritmusukat, hogy tetszőleges számú résztvevővel dolgozzanak [9] . Az algoritmusuk nem igényel több kérést. Bár a szám korlátozott, nagyon messze van az alsó korláttól . Tehát nyitva marad az a kérdés, hogy hány kérdésre van szükség a torta irigység nélküli felvágásához. ${\displaystyle n^{n^{n^{n^{n^{n))))))))$ $\Omega (n^{2})$

Közelítések és részmegoldások

A last-down protokoll zárt változata korlátozott időn belül irigységmentes additív közelítést talál a partícióról. Konstans esetén az algoritmus egy olyan partíciót ad vissza, amelyben az egyes tagok értéke legalább a legnagyobb mínusz érték az időben . $\varepsilon >0$ $\varepsilon$ $n^{2}/\varepsilon$

Ha minden mérték darabonként lineáris , akkor létezik egy algoritmus [18] , amely polinomiális a kiértékelő függvények reprezentációjának méretében . Kérésének száma , ahol egyenlő a becslési sűrűségfüggvények deriváltjaiban lévő rések számával. $O(n^{6}k\ln {k})$ $k$

Eredmények nehézség szerint

Bármilyen irigy n emberre vonatkozó felosztási eljáráshoz legalább kérésekre van szükség [19] . A bizonyítás az algoritmus által az egyes résztvevőktől kapott információmennyiség gondos elemzésén alapul. $\Omega (n^{2})$

Tegyük fel, hogy a torta egy egydimenziós intervallum [0;1], és a teljes torta értéke minden résztvevő esetében 1-re van normalizálva. Az algoritmus minden lépésben megkér egy adott résztvevőt, hogy értékeljen ki egy bizonyos intervallumot. a [0;1]-ben, Vagy jelölje meg az intervallumot egy adott értékkel. Az algoritmus mindkét esetben csak azokról az intervallumokról gyűjt információt, amelyek végpontjait a kérés vagy a válasz megemlítette. Nevezzük ezeket a végpontokat mérföldköveknek . Kezdetben az i mérföldkövek csak 0 és 1, mivel az algoritmus csak annyit tud az i résztvevőről . Ha az algoritmus megkéri az i résztvevőt , hogy értékelje [0,2;1], akkor a válasz után az i mérföldkövek {0;0,2;1}. Az algoritmus képes kiszámítani , de nem olyan intervallumot, amelynek végpontja eltér 0,2-től. A mérföldkövek száma minden kérdésnél maximum 2-vel növekszik. Különösen a [0;0,2] szegmens értéke koncentrálódhat 0 közelébe vagy 0,2 közelébe, vagy valahol ezen értékek közé. $v_{i}([0;1])=1$ $v_{i}([0;0,2])$

Az i tag két egymást követő mérföldköve közötti intervallumot az i tag mérföldkő intervallumának nevezzük . Amikor az algoritmus úgy dönt, hogy egy darab tortát rendel az i taghoz, akkor ki kell osztania egy darabot, amelynek i összpontszáma nem kisebb, mint az i tagok bármelyike mérföldkő intervallum . Ellentmondásos bizonyítás – tegyük fel, hogy van egy bizonyos J mérföldkövek intervalluma, amelynek i értéke nagyobb, mint az i taghoz rendelt tényleges érték . Egy másik résztvevő, mondjuk j , szükségszerűen megkapja a J mérföldkő intervallum egy részét . Az A pont szerint fennáll annak a lehetősége, hogy a J intervallum teljes értéke a j résztvevőhöz rendelt csonkon belül koncentrálódik . Akkor irigylem j-t , és a partíció nem lesz mentes az irigységtől.

Tegyük fel, hogy minden résztvevő úgy válaszolt minden kérdésre , mintha pontszáma homogén lenne (azaz az intervallum értéke megegyezik a hosszával). A B pont szerint az algoritmus csak akkor tud egy darabot hozzárendelni az i résztvevőhöz, ha az hosszabb, mint az i résztvevő összes mérföldkövei . A résztvevőknek legalább 2/ n -nél nem hosszabb intervallumot kell kapniuk . Ezért az összes mérföldkő-intervallum hossza nem haladhatja meg a 2/ n -t . Ezért legalább mérföldkövek intervallumokkal kell rendelkezniük, és ezért a mérföldkövek számának legalább . ${\tfrac {n}{2))$ ${\tfrac {n}{2))$ ${\tfrac {n}{2))$

Minden i résztvevő által megválaszolt kérdés legfeljebb két új végpontot vezet be, így az i résztvevő mérföldkövek száma legfeljebb 2-vel nő. Ezért a C pontban leírt esetben az algoritmusnak minden résztvevőt le kell kérnie, megadva legalább legalább n /4 kérdés. A kérdések teljes száma ekkor nem lesz kevesebb, mint . ${\tfrac {n}{2))$ ${\tfrac {n^{2}}{8}}=\Omega (n^{2})$

Nyitott kérdés marad, hogy létezik-e korlátozott algoritmus tetszőleges kiértékelési függvényekre. Így óriási szakadék tátong az alsó korlát és a jelenleg ismert legjobb algoritmus között, amely véges, de nem korlátozott. $\Omega (n^{2})$

Létbizonyítások és változatok

A fent leírt algoritmusokból következő általános formájú létezési bizonyításokon kívül további tulajdonságokkal rendelkező irigységmentes partíciók létezésére is vannak bizonyítékok:

létezik egy pontos felosztás , amely különösen mentes az irigységtől ( Dubins-Spanier tételek );
létezik egy irigységmentes eloszlás, amely szintén Pareto-hatékony ( Weller tétele ).

Mindkét bizonyítás csak az additív, nem atomi értékelési mérőszámok esetében működik, és arra a képességre támaszkodik, hogy nagyszámú szétválasztott darabot ki lehet osztani az egyes résztvevők között.

Irigy megosztás különböző megosztásokkal

A nem irigység kritériumának általánosítása az, hogy minden résztvevőnek különböző részesedést kell biztosítania. Ez azt jelenti, hogy bármely i résztvevő esetében van egy súlyozás, amely leírja a torta azon részét, amelyet biztosítani kell (az összes w i megosztás összege egyenlő 1-gyel). Ezután a súlyozott irigységmentes partíciót a következőképpen határozzuk meg. Bármely i ügynökre becslések mértékével és bármely más k ügynökre : $w_{i}$ $V_i$

${\displaystyle V_{i}(X_{i})/w_{i}\geqslant V_{i}(X_{j})/w_{j))$

Ez azt jelenti, hogy bármely résztvevő úgy véli, hogy az általa kiosztott részesedés, amely az ő várható részesedésének felel meg, nem kisebb, mint a többi résztvevő várható részesedésének megfelelő kiosztott részesedés.

Ha az összes súly még mindig ugyanaz (és egyenlő ), ez a definíció a nem irigység szokásos definíciójára redukálódik. ${\tfrac {1}{n))$

Ha a darabok szétválaszthatók, mindig létezik egy súlyozott irigységmentes partíció, amely a Robertson-Webb protokoll használatával bármely súlykészlethez megtalálható. Zeng egy alternatív algoritmust javasolt az irigységmentes közelítő súlyozott particionáláshoz, amely kis számú vágást igényel [20] .

De amikor a darabokat össze kell kötni, előfordulhat, hogy nem létezik súlyozott irigységmentes partíció. Ennek megértéséhez vegye figyelembe, hogy minden irigységmentes súlyozott partíció súlyozása is arányos ugyanazzal a súlyvektorral. Ez azt jelenti, hogy bármely i ügynök V i becsléssel :

$V_{i}(X_{i})/w_{i}\geqslant V_{i}(C)$

Ismeretes, hogy nem létezik súlyozott arányos eloszlás összekapcsolt darabokkal: lásd például egy torta arányos felosztását különböző részekkel .

Ne feledje, hogy létezik egy alternatív definíció az irigység nélküli súlyozott eloszlásra, ahol a súlyok a darabokhoz vannak rendelve, nem az ügynökökhöz. Ennél a definíciónál ismert, hogy súlyozott irigységmentes eloszlás létezik a következő esetekben (minden eset általánosítja az előző esetet):

additív kiértékelési függvények, egydimenziós torta (szegmens), darabokat össze kell kötni szegmensekkel [21] ;
additív kiértékelési függvények, többdimenziós torta szimplexként , a daraboknak egyszerűnek kell lenniük [22] . A bizonyítás a Sperner-tételt , a Knaster-Kuratowski-Mazurkiewicz lemmát , a Gale lefedő lemmát és a Ki Fan egybeeső pontokat lemma ;
nem additív kiértékelési függvények, többdimenziós szimplex torta , a daraboknak poliédereknek kell lenniük [23] .

A "rossz" torta felosztása

Egyes esetekben a megosztható "torta" negatív értékű. Ez lehet például egy darab pázsit, amelyet le kell nyírni, vagy egy darab puszta, amelyet ki kell takarítani. Ebben az esetben a torta "heterogén rossz" és nem "heterogén jó".

Néhány irigységmentes tortavágási eljárás adaptálható az ilyen vékony süteményekhez, de az adaptáció gyakran nem triviális.

Döntő táblázatok

Eljárások eredmények szerint

Név	Típusú	Torta	darabok	Résztvevők száma ( n )	Kérelmek száma	Vágások száma	irigység	Arányosság [24]	Hozzászólások
Delhi-és válassz	diszkrét eljárás	Bármi	hírnökök	2	2	1 (optimális)	Nem	1/2
Stromquist	Mozgó kés eljárás	Vonalszakasz	hírnökök	3	$\infty$	2 (optimális)	Nem	1/3
Selfridge-Conway	diszkrét eljárás	Bármi	Szétkapcsolt	3	9	5	Nem	1/3
Brahms-Taylor-Zwicker	Mozgó kés eljárás	Bármi	Szétkapcsolt	négy	$\infty$	tizenegy	Nem	1/4
Sabury-Wonga [13]	diszkrét eljárás	Bármi	Szétkapcsolt	négy	Korlátozott	Korlátozott	Nem	1/4	esetleges kiselejtezett darab
Aziza – Mackenzie [17]	diszkrét eljárás	Bármi	Szétkapcsolt	négy	203	584	Nem	1/4
Sabury-Wonga [13]	Mozgó kés eljárás	Bármi	Szétkapcsolt	5	$\infty$	Korlátozott	Nem	1/5
Stromquist	Létezés	Vonalszakasz	hírnökök	n	—	n −1	Nem	1/ n
Simmons	diszkrét eljárás	Vonalszakasz	hírnökök	n	$\infty$	n −1	Nem	1/ n
Denga - Key - Sabury	diszkrét eljárás	Vonalszakasz	hírnökök	n	$\left({\frac {1}{\varepsilon }}\right)^{n-2}$	n −1	$\varepsilon$	$\left({\tfrac {1}{n}}\right)-\varepsilon$	Csak akkor, ha a határok Lipschitz folytonosak
Branzei [7]	diszkrét eljárás	Vonalszakasz	hírnökök	n	$n^{2}d$	ismeretlen	Nem	1/ n	Csak akkor, ha a becslősűrűségek polinomiálisak, maximális d fokozattal .
" Siess - nevettesd meg az embereket "	diszkrét eljárás	Vonalszakasz	hírnökök	3	9	négy	Nem	1/3	Lehetséges kiselejtezett darab
" Siess - nevettesd meg az embereket "	diszkrét eljárás	Bármi	hírnökök	négy	16	6	Nem	1/7	Lehetséges kiselejtezett darab
" Siess - nevettesd meg az embereket "	diszkrét eljárás	Bármi	hírnökök	n	$2^{n}$	$2^{n-1}-1$	Nem	${\displaystyle {\frac {1}{2^{n-1))))$	Lehetséges kiselejtezett darab
Aziza – Mackenzie ConnectedPieces [9]	diszkrét eljárás	Bármi	hírnökök	n	$n^{n+1}$	$n^{n+1}$	Nem	${\frac {1}{3n))$	Lehetséges kiselejtezett darab
Brahms – Taylor	diszkrét eljárás	Bármi	Szétkapcsolt	n	Nincs korlátozva	Nincs korlátozva	Nem	1/ n
Robertson-Webb	diszkrét eljárás	Bármi	Szétkapcsolt	n	Nincs korlátozva	Nincs korlátozva	Nem	1/ n	Súlyozott irigységmentes partíció
Pikhurko [15]	diszkrét eljárás	Bármi	Szétkapcsolt	n	Nincs korlátozva	Nincs korlátozva	Nem	1/ n
Aziza – Mackenzie [9]	diszkrét eljárás	Bármi	Szétkapcsolt	n	${\displaystyle n^{n^{n^{n^{n^{n))))))))$	${\displaystyle n^{n^{n^{n^{n^{n))))))))$	Nem	1/ n
Az utoljára redukált protokoll zárt hurkú változata	diszkrét eljárás	Vonalszakasz	Szétkapcsolt	n	$n^{2}/\varepsilon$	ismeretlen	$\varepsilon$	1/ n
Kurokawa – Leia – Prokachi [18]	diszkrét eljárás	Vonalszakasz	Szétkapcsolt	n	$n^{6}k\ln k$	ismeretlen	Nem	1/ n	Csak akkor, ha a sűrűségek értéke darabonként lineáris, legfeljebb k folytonossággal.
Weller	Létezés	Bármi	Szétkapcsolt	n	—	$\infty$	Nem	1/ n	Pareto hatékony .
2D	diszkrét eljárás	Négyzet	Összekötött és négyzet alakú	2	2	2	Nem	1/4	Lehetséges kiselejtezett darab
2D	Mozgó kés eljárás	Négyzet	Összekötött és négyzet alakú	3	$\infty$	6	Nem	1/10	Lehetséges kiselejtezett darab

A döntő asztal a résztvevők száma és a darabok típusa szerint:

ügynökök száma	Összekötött darabok	Általános darabok
2	Delhi-és válassz
3	Stromkvist „Moving Knife” eljárása (végtelen idő); " Siess - nevettess meg az embereket " (korlátozott idő, korlátozott számú vágás, eldobható darab, arányos)	Diszkrét Selfridge-Conway eljárás (korlátozott ideig, legfeljebb 5 bemetszés).
négy	„ Ha sietsz, megnevetteted az embereket ” (korlátozott idő, korlátozott számú vágás, eldobható darab, arányosság 1/7).	Brahms-Taylor-Zwicker eljárás (végtelen idő, legfeljebb 11 vágás). Diszkrét Sabery-Wong eljárás [13] (korlátozott idő, korlátozott számú vágás, eldobható darab, arányos). Aziz-Mackenzie diszkrét eljárás [17] (korlátozott idő, korlátozott számú vágás, arányos).
5		Sabury-Wong „Moving Knife” eljárásai [13] (végtelen idő, korlátozott számú vágás).
n	Simmons protokoll (végtelen idő) Deng-Ki-Sabury (körülbelül irigységmentes, exponenciális idő). „ Siess – tegyük nevettessen az embereket ” (teljesen mentes az irigységtől, az exponenciális idő, az elejtés lehetséges, az exponenciális arányosság) ConnectedPieces Aziz - Mackenzie [9] (teljesen mentes az irigységtől, exponenciális idő, lehetséges az elejtés, lineáris arányosság)	Brahms és Taylor (1995) ; Robertson és Webb (1998) . Mindkét algoritmus véges, de nem korlátozott számú vágást igényel. Diszkrét Aziz-Mackenzie eljárás [9] (korlátozott idő, korlátozott számú vágás, arányos osztás).
Nehézség	Minden algoritmusnak végtelennek kell lennie (Stromquist, 2008). $n\geqslant 3$	Minden algoritmusnak legalább lépést kell használnia (Procaccia, 2009). $\Omega (n^{2})$
Lehetőségek	Súlyozott irigységmentes partíció létezik tetszőleges súlyozáshoz (Idzik, 1995), még akkor is, ha a torta és a darabok egyszerűek (Idzik, Ichiishi, 1996), és még akkor is, ha nem adalékot választanak (Dall'Aglio és Maccheroni, 2009).	A Robertson-Webb protokoll találhat egy súlyozott irigységmentes partíciót tetszőleges súlyokhoz. Létezik tökéletes felosztás (Dubins & Spanier, 1961). Van egy irigységmentes és hatékony tortavágás ( Weller tétele ).

Lásd még

Jegyzetek

↑ Gyakran szó szerint fordítják angolból: Irigységmentes tortavágás , bár ebben a felosztásban az irigység játszik kulcsszerepet. A cikk az "irigy felosztás" kifejezést használja, de ennek a felosztásnak az irigységmentes terjesztésnek kell lennie .
↑ Gamow, Stern, 1958 .
↑ Stromquist, 1980 , p. 640–644.
↑ Stromquist, 2008 .
↑ Stromkvist „Moving Knife” eljárása megköveteli, hogy az ügynökök mozgassák a késeiket, miközben a játékvezető a kardját mozgatja. Mivel a kard mozgása folyamatos, a szükséges lépések száma megszámlálhatatlan (és ezért természetesen végtelen). Simmons tortavágási protokollja egy irigységmentes partícióhoz konvergál, de végtelen számú lépést igényelhet.
↑ 1 2 Deng, Qi, Saberi, 2012 , p. 1461–1476
↑ Brânzei 12. , 2015 , p. 93–95.
↑ 1 2 Segal-Halevi, Hassidim, Aumann, 2016 , p. 1–32.
↑ 1 2 3 4 5 6 Aziz, MacKenzie, 2016 .
↑ Segal-Halevi, Hassidim, Aumann, 2015 , p. 1021–1028.
↑ Brams és Taylor 1996 , p. 124–125.
↑ Brams, Taylor, Zwicker, 1997 , p. 547–555.
↑ 1 2 3 4 5 Saberi, Wang, 2009 .
↑ SJ Brams, MA Jones, C. Klamler, "Better way to cut a cake", Notices of the AMS, 2005. [Online]. Elérhető: http://www.ams.org/notices/200611/fea-brams.pdf Archiválva : 2019. szeptember 30. a Wayback Machine -nél
↑ 1 2 Pikhurko, 2000 , p. 736–738.
↑ Gasarch, William, Melyik Unbounded Protocol for Envy Free Cake Cutting is Better?, arΧiv : 1507.08497 [math.LO].
↑ 1 2 3 Aziz, MacKenzie, 2016 , p. 454.
↑ 1 2 Kurokawa, Lai, Procaccia, 2013 .
↑ Procaccia, 2009 , p. 239–244.
↑ Zeng, 2000 , p. 259–271.
↑ Idzik, 1995 .
↑ Ichiishi, Idzik, 1999 , p. 389–400.
↑ Dall'Aglio, MacCheroni, 2009 , p. 57–77.
↑ Az az érték (a teljes torta részarányaként), amelyet minden egyes szernek garantálnak az additív becslések alapján. Ha nincs irigység, és az egész torta fel van osztva, az arányosság mindig a lehető legjobb. ${\tfrac {1}{n))$

Irodalom

George Gamow, Marvin Stern. Rejtvény-matematika . - 1958. - ISBN 978-0670583355 .
Walter Stromquist. Hogyan vágjunk tisztességesen egy tortát // Az amerikai matematikai havilap. - 1980. - T. 87 , sz. 8 . - doi : 10.2307/2320951 . — .
Walter Stromquist. Az irigységmentes tortafelosztásokat véges protokollok nem találják // Electronic Journal of Combinatorics. - 2008. Archiválva : 2016. március 11.
Deng X., Qi Q., Saberi A. Algoritmikus megoldások irigységmentes tortavágáshoz // Operációkutatás. - 2012. - T. 60 , sz. 6 . doi : 10.1287 / opre.1120.1116 .
Brânzei S. Megjegyzés az irigységmentes tortavágásról polinomiális értékelésekkel // Information Processing Letters. - 2015. - T. 115 , sz. 2 . - doi : 10.1016/j.ipl.2014.07.005 .
Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann. Irigységmentes tortavágás két dimenzióban // The 29. AAAI Conference on Artificial Intelligence (AAAI-15). - Austin, Texas, 2015. - doi : 10.13140/RG.2.1.5047.7923 .
Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann. A pazarlás sietni kezd // ACM-tranzakciók algoritmusokon. - 2016. - T. 13 . - doi : 10.1145/2988232 . - arXiv : 1511.02599 .
Steven J. Brams, Alan D. Taylor, William S. Zwicker. Mozgókés megoldás a négyszemélyes irigységmentes torták részlegéhez // Proceedings of the American Mathematical Society. - 1997. - T. 125 , sz. 2 . - doi : 10.1090/S0002-9939-97-03614-9 .
Amin Saberi, Ying Wang. Tortavágás öt embernek // Algoritmikus szempontok az információban és a menedzsmentben. - 2009. - doi : 10.1007/978-3-642-02158-9_25 .
Pikhurko O. Az irigységmentes tortaosztályról // The American Mathematical Monthly. - 2000. - T. 107 , sz. 8 . - doi : 10.2307/2695471 . — .
Haris Aziz, Simon MacKenzie. Diszkrét és korlátos irigységmentes tortavágási protokoll négy ügynök számára // Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016. - 2016. - ISBN 9781450341325 . - doi : 10.1145/2897518.2897522 .
Haris Aziz, Simon MacKenzie. Diszkrét és korlátos irigységmentes tortavágási protokoll tetszőleges számú ügynökhöz // FOCS 2016. - 2016.
David Kurokawa, John K. Lai, Ariel D. Procaccia. Hogyan vágjunk tortát a buli vége előtt // AAAI. — 2013.
Ariel Procaccia. Thou Shalt Covet Thy Neighbor's Cake // IJCAI'09 Proceedings of the 21st International Joint Conference on Artificial Intelligence. – 2009.
Dao Zhi Zeng. Hozzávetőleges irigységmentes eljárások // Game Practice: Contributions from Applied Game Theory . - Springer, 2000. - Vol. 23. - (Elmélet és döntéstár). — ISBN 9781461546276 . - doi : 10.1007/978-1-4615-4627-6_17 .
Idzik Ádám. Az egységintervallum optimális felosztása // Nemzetközi konferencia Robert J. Aumann tiszteletére 65. születésnapján. – Jeruzsálem, 1995.
Ichiishi T., Idzik A. Osztható javak méltányos elosztása // Journal of Mathematical Economics. - 1999. - T. 32 , sz. 4 . - doi : 10.1016/s0304-4068(98)00053-6 .
Dall'Aglio M., MacCheroni F. Vitatott földek // Games and Economic Behavior. - 2009. - T. 66 . - doi : 10.1016/j.geb.2008.04.006 .
Steven J. Brams, Alan D. Taylor. Tisztességes felosztás: a tortavágástól a vitarendezésig . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .

Linkek

Fair Division Calculator – Irigységmentes osztásszámító kisalkalmazás süteményekhez, kötelességekhez, takarításhoz és bérbeadáshoz.