Szimmetrikus tisztességes tortavágás

A szimmetrikus tisztességes tortavágás a méltányos tortavágás problémájának egy olyan változata, amelyben a méltányosságot nemcsak a torta részei, hanem a vágásban való részvétel is értékeli.

Essence

Vegyünk egy példát: adjunk egy tortát, és fel kell osztani Alice és George között, akiknek az ízlése különbözik, hogy mindegyikük úgy érezze, hogy az ő részét tisztességesen vágják és választják meg, azaz mindegyiknek értéke legyen az egész torta értékének legalább a felét. Használhatnánk a klasszikus „ oszd meg és válassz ” megoldást: Alice két olyan darabra vágja a tortát, amelyek egyenértékűek vele, George pedig kiválaszt egy általa értékesebbnek tartott darabot. Ennek a megoldásnak azonban van egy hibája: Alice mindig 1/2 értékű részesedést kap, de George kaphat 1/2-nél nagyobb részesedést is. Ezért ezt a vágást tisztességesnek , de aszimmetrikusnak nevezik , vagyis Alice nem lát semmi rosszat abban, hogy George melyik részvényt választotta, de igazságtalannak érzi, hogy George választotta a részesedést, és ő vágta fel a tortát.

Vegyünk egy másik megoldást: Alice és George mindketten kijelölik a határukat (legegyszerűbb esetben párhuzamos vagy egybeeső szakaszokat), amelyek mindegyikük szempontjából egyenlő felére osztják a tortát. Ezután a tortát pontosan középre vágjuk e határok között: jelöljük a-ként a torta bal lebenyének térfogati részét, amelyre Alice osztott, és g -ként - a torta bal lebenyének térfogati részét, amelybe George felosztotta, - majd a tortát ketté kell vágni két részre, amelyből a megmaradt térfogati rész egyenlő . Ha < g , akkor Alice kapja a bal oldali bábuját (amelynek értéke nagyobb, mint Alice részesedése), George pedig a jobb oldali bábuját (amelynek értéke szintén nagyobb). Ha a > g , akkor Alice, ellenkezőleg, a megfelelő darabot kapja, George pedig a bal. Ezért ezt a problémamegoldást igazságosnak és szimmetrikusnak nevezzük . ${\megjelenítési stílus (a+g)/2}$

Ezt az ötletet először Monabe és Okamoto [1] javasolta , akik meta-irigységmentesnek nevezték .

A torta szimmetrikus tisztességes vágására több lehetőséget is javasoltak:

A sütemény anonim tisztességes felvágásához nem csak az értékeknek kell megegyezniük, hanem maguknak a daraboknak is egyenlőnek kell lenniük [2] . Ez szimmetrikus érvényességet jelent, de a feltétel szigorúbb. Ilyen vágást például nem biztosít a fenti szimmetrikus oszd meg-válaszol eljárás, mert a = g esetén mindig az első ügynök kapja a bal szélső darabot, a második pedig mindig a jobb szélső darabot.
Arisztotelész tisztességes tortavágása csak azt követeli meg, hogy az azonos mértékû ügynökök azonos értékelési értékű darabokat kapjanak [3] . Ez szimmetrikus érvényességet jelent, de a feltétel gyengébb. Például az oszd meg és válassz eljárás aszimmetrikus változatával teljesül – ha az ügynökök pontszámai azonosak, akkor mindkét játékos pontosan 1/2.

Definíciók

Van egy C torta , amelyet általában egydimenziós szegmensként ábrázolnak. n ember van , és minden i érintettnek van egy V i kiértékelő függvénye , amely leképezi C részhalmazait nem negatív számokra.

Az osztási eljárás egy F függvény, amely n kiértékelő függvényt képez le a C intervallum egy partíciójára . Azt a darabot, amelyet F függvény az i ügynökhöz rendel, a következővel jelöljük . $F(V_{1},\dots ,V_{n};i)$

Szimmetrikus eljárás

Az F osztási eljárást szimmetrikusnak nevezzük, ha az (1,…, n ) indexek és bármely i bármely p permutációjára

V_{i}(F(V_{1},\pontok ,V_{n};i))=V_{i}(F(V_{p(1)},\pontok ,V_{p(n) )};p^{-1}(i)))

Konkrétan n = 2 esetén az eljárás szimmetrikus, ha

V_{1}(F(V_{1},V_{2};1))=V_{1}(F(V_{2},V_{1};2))

és .

V_{2}(F(V_{1},V_{2};2))=V_{2}(F(V_{2},V_{1};1))

Ez azt jelenti, hogy az 1. ügynök ugyanazt az értéket kapja, függetlenül attól, hogy elsőként vagy másodikként játszik, és ugyanez igaz a 2. ügynökre is.

Egy másik példában, amikor n = 3, akkor a szimmetriakövetelmény (többek között):

V_{1}(F(V_{1},V_{2},V_{3};1))=V_{1}(F(V_{2},V_{3},V_{1} ;3))=V_{1}(F(V_{3},V_{1},V_{2};2))

Névtelen eljárás

Az F osztási eljárást anonimnak nevezzük , ha az (1,…, n ) indexek bármely p permutációjára és bármely $én$

F(V_{1},\dots ,V_{n};i)=F(V_{p(1)},\dots ,V_{p(n)};p^{-1}(i ))

Bármely névtelen eljárás szimmetrikus, mert ha a darabok egyenlőek, akkor a becsléseik minden bizonnyal egyenlők.

Ennek az ellenkezője azonban nem igaz - lehetséges, hogy a permutáció különböző, azonos értékű darabokat ad az ügynöknek.

Arisztotelészi eljárás

Az F osztási eljárást arisztotelészinek nevezzük , ha : $V_{i}=V_{k}$

V_{i}(F(V_{1},\pontok ,V_{n};i))=V_{k}(F(V_{1},\pontok ,V_{n};k))

A kritérium Arisztotelész nevéhez fűződik , aki etikával foglalkozó könyvében ezt írta: "...amikor egyenlőtlen részeket osztanak ki egyenlő tulajdoni hányaddal, vagy ha a személyek egyenlőtlenül egyenlő részesedéssel, megnő a viták és panaszok száma."

Minden szimmetrikus eljárás arisztotelészi. Legyen p egy i -t és k - t felcserélő permutáció . A szimmetriából az következik

V_{i}(F(V_{1},\pontok ,V_{i},\pontok ,V_{k},\pontok ,V_{n};i))=V_{i}(F( V_{1},\pontok ,V_{k},\pontok ,V_{i},\pontok ,V_{n};k))

De mivel V i = V k , ez a két mértéksorozat azonos, innen ered az arisztotelészi definíció.

Ráadásul minden irigy tortavágási eljárás arisztotelészi – az irigység hiányából következik, hogy

V_{i}(F(V_{1},\pontok ,V_{n};i))\geqslant V_{i}(F(V_{1},\dots ,V_{n};k) )V_{k}(F(V_{1},\pontok ,V_{n};k))\geqslant V_{k}(F(V_{1},\pontok ,V_{n};i))

Mivel azonban két ellentétes egyenlőtlenségből az következik, hogy mindkét érték egyenlő. $V_{i}=V_{k}$

A torta arányos felvágásának gyengébb feltételét kielégítő eljárás azonban nem feltétlenül arisztotelészi. Cheese [3] adott egy példát 4 szerrel, amelyben az Even-Paz eljárás az arányos tortavágásra különböző értékeket adhat az azonos értékelési mérőszámú szereknél.

Az alábbiakban összefoglaljuk a kritériumok közötti kapcsolatokat:

Névtelen szimmetrikus Arisztotelész $\nak nek$ $\nak nek$
Arisztotelész irigység nélkül $\nak nek$
Irigység nélkül arányos $\nak nek$

Eljárások

Bármely eljárás " eleve szimmetrikussá" tehető randomizálással. Például egy aszimmetrikus oszd meg és válassz eljárásban az elválasztó egy érme feldobásával választható ki. Egy ilyen eljárás azonban valójában nem lenne szimmetrikus. Ezért a szimmetrikus méltányos tortavágással kapcsolatos kutatások a determinisztikus algoritmusokra összpontosítanak .

Monabe és Okamoto [1] irigységmentes szimmetrikus determinisztikus eljárásokat ("irigységmentes meta") javasolt két és három ágensre.

Nicolo és Yu [2] egy protokollt javasolt az anonim és Pareto hatékony felosztáshoz, anélkül, hogy irigykedne két ügynökre. A protokoll tökéletes részjáték-egyensúlyt valósít meg azzal a feltételezéssel, hogy minden ügynök teljes információval rendelkezik a többi ágens becsléseiről.

A szimmetrikus vágási és szelekciós eljárást két ágens esetén empirikusan tanulmányozták laboratóriumi kísérletekben [4] . Alternatív eljárások a torta szimmetrikus tisztességes vágására két résztvevő számára a jobb szélső jel [5] és a bal szélső maradék [6] .

Cheese [3] számos eljárást javasolt:

Az irigy osztási eljárás szimmetrikus determinisztikus eljárássá alakításának általános sémája: végrehajtjuk az eredeti n eljárást ! alkalommal, az ágensek minden permutációjához egyszer, és válassza ki az eredményt a topológiai kritérium szerint (vagyis a vágások minimális értékével). Ez az eljárás gyakorlatilag alkalmatlanná válik nagy n esetén .
Arisztotelészi arányos eljárás n ügynökre, amely lekérdezéseket és polinomiális számú aritmetikai műveletet igényel. $O(n^{3})$
Egy szimmetrikus arányos eljárás n ügynökhöz, amely lekérdezést igényel , de exponenciális számú aritmetikai műveletet igényelhet. $O(n^{3})$

Arisztotelész arányos eljárása

A Cheese arisztotelészi eljárása [3] az arányos tortavágásra kiterjeszti az „ egy osztó ” eljárást. A kényelem kedvéért normalizáljuk a kiértékelési függvényeket úgy, hogy a teljes torta értéke minden ágensre egyenlő legyen n -nel . A cél az, hogy minden ügynökhöz legalább 1-es részesedést rendeljenek.

Egy játékost tetszőlegesen választanak ki, amit felosztásnak neveznek , ő n részre vágja a tortát , amit pontosan 1-re értékel.
Létrehozunk egy kétrészes gráfot , amelyben X minden csúcsa egy ügynök, Y minden csúcsa egy darab torta, és akkor és csak akkor van él az x ügynök és az y tortadarab között , ha x az y darabot legalább 1-re értékeli . . $G=(X+Y,E)$
G - ben keressük a maximális méretű irigységmentes párosítást (PBZ) (olyan párosítást, amelyben nincs olyan szer, amely nem tartozik az egyezéshez, de szomszédos, az egyező tortadarabhoz tartozik). Figyeljük meg, hogy az osztó a torta mind az n darabjával szomszédos, tehát (hol van X szomszédjainak halmaza Y -ben ). Ezért létezik irigység nélküli nem üres egyezés [7] . Tételezzük fel az általánosság elvesztése nélkül, hogy a PBZ az 1,…, k ágenseket darabokra illeszti, a k +1 dr n ágenseket és darabokat pedig párosítás nélkül hagyja el . $|N_{G}(X)|=n\geqslant |X|$ $N_{G}(X)$ ${\displaystyle X_{1},\dots ,X_{k))$
Bármely i -re 1,…, k -ből , amelyre , X i -t adunk az i ügynöknek . Most az osztóhoz és minden olyan ügynökhöz, amelyek kiértékelési funkciói megegyeznek az osztó funkciójával, azonos értékű darabokat rendelnek hozzá. $V_{i}(X_{i})=1$
Tekintsük most 1,…, k i ügynökeit, amelyekre . Osszuk fel részhalmazokra a darabok kiértékelésének egyenlő vektoraival . Minden részhalmazhoz rekurzívan felosztjuk a darabjaikat (például ha az 1, 3, 4 ügynökök megegyeznek az összes 1,…, k darab értékében , akkor a darabokat rekurzívan elosztjuk közöttük). Most minden ügynök, amelynek kiértékelési funkciói azonosak, ugyanahhoz a részhalmazhoz vannak hozzárendelve, és megosztják azt a részhalmazt, amelynek értéke közöttük nagyobb, mint a számuk, így a rekurziós előfeltétel teljesül. $V_{i}(X_{i})>1$ $X_{1},\dots ,X_{n}$ ${\displaystyle X_{1},X_{3},X_{4))$
Rekurzív módon felosztjuk az allokálatlan darabokat a nem allokált ügynökök között. Vegye figyelembe, hogy az illesztésben az irigység hiánya miatt minden elosztott ágens minden elosztott darabot 1-nél kisebbre értékel, így a fennmaradó darabok értéke legalább akkora, mint az ágensek száma, tehát a rekurzió előfeltétele meg van őrizve. ${\displaystyle X_{k+1},\dots ,X_{k))$

Jegyzetek

↑ 1 2 Manabe, Okamoto, 2010 , p. 501–512.
↑ 1 2 Nicolò, Yu, 2008 , p. 268–289.
↑ 1 2 3 4 Chez, 2018 .
↑ Kyropoulou, Ortega, Segal-Halevi, 2019 , p. 547–548.
↑ Segal-Halevi, Sziklai, 2018 , p. 19-30.
↑ Ortega, 2019 .
↑ Segal-Halevi, Aigner-Horev, 2019 .

Irodalom

Yoshifumi Manabe, Tatsuaki Okamoto. Meta irigységmentes tortavágási jegyzőkönyvek // A számítástechnika matematikai alapjairól szóló 35. nemzetközi konferencia előadásai. - Berlin, Heidelberg: Springer-Verlag, 2010. - ISBN 9783642151545 .
Antonio Nicolo, Yan Yu. Stratégiai oszd meg és válassz // Játékok és gazdasági viselkedés. - 2008. - T. 64 , sz. 1 . — ISSN 0899-8256 . - doi : 10.1016/j.geb.2008.01.006 .
Guillaume Chez. Ne sírj, hogy te legyél az első! Léteznek szimmetrikus igazságos felosztási algoritmusok. - 2018. - arXiv : 1804.03833v1 .
Maria Kyropoulou, Josué Ortega, Erel Segal-Halevi. Fair Cake Cutting in Practice // A 2019-es ACM Gazdasági és Számítási Konferencia előadásai. — New York, NY, USA: ACM, 2019. — ISBN 9781450367929 . - doi : 10.1145/3328526.3329592 . - arXiv : 1810.08243 .
Segal-Halevi Erel, Sziklai R. Balázs. Erőforrás-monotonitás és populáció-monotonitás az összekapcsolt tortavágásban // Mathematical Social Sciences. - 2018. - Kt. 95. - ISSN 0165-4896 . - doi : 10.1016/j.mathsocsci.2018.07.001 . — arXiv : 1703.08928 .
Josue Ortega. Nyilvánvaló manipulációk a tortavágásban. - 2019. - arXiv : 1908.02988v1 .
Erel Segal-Halevi, Elad Aigner-Horev. Irigységmentes egyezések kétoldalú grafikonokon és alkalmazásaik a tisztességes felosztásban. - 2019. - arXiv : 1901.09527v2 .