Symetrické poctivé krájení dortu

Symetrické poctivé krájení dortu je variantou problému krájení poctivého dortu, ve kterém se poctivost hodnotí nejen podle částí dortu, ale také podle účasti na krájení.

Esence

Vezměme si příklad: ať se dá dort a ten se musí rozdělit mezi Alici a George, jejichž vkus se liší, aby každý z nich měl pocit, že jeho podíl je ukrojen a vybrán spravedlivě, tedy aby každý z nich měl hodnotu podíl alespoň poloviny hodnoty celého dortu. Dalo by se použít klasické řešení „ rozděl a vyber “: Alice rozkrojí dort na dva takové kusy, které jsou jí ekvivalentní, a George si vybere kousek, který považuje za hodnotnější. V tomto řešení je však chyba: Alice vždy dostane podíl s hodnotou 1/2, ale George může získat podíl s hodnotou větší než 1/2. Proto se toto krájení nazývá spravedlivé , ale asymetrické , to znamená, že Alice nevidí nic špatného na tom, jaký podíl si George vybral, ale cítí se nespravedlivé, že to byl George, kdo si vybral podíl, a dort rozkrojila.

Zvažte jiné řešení: Alice a George si oba označí svou hranici (v nejjednodušším případě rovnoběžné nebo shodné segmenty), které z pohledu každého z nich rozdělují dort na stejné poloviny. Poté se dort rozřízne přesně uprostřed mezi těmito hranicemi: označme jako a objemovou část levého laloku dortu, na kterou se Alice rozdělila, a jako g - objemovou část levého laloku dortu, do které Jiří rozdělen, - pak se dort musí rozpůlit na dvě části, objemová část, která zbyla, se rovná . Pokud a < g , pak Alice získá figurku nalevo (jejíž hodnota je větší než Alicin podíl) a George si vezme figurku napravo (jejíž hodnota je také větší). Pokud a > g , pak Alice naopak dostane pravou figurku a George levou. Proto se toto řešení problému nazývá spravedlivé a symetrické . $(a+g)/2$

Tuto myšlenku jako první navrhli Monabe a Okamoto [1] , kteří ji nazvali meta-envy-free .

Bylo navrženo několik možností pro symetrické spravedlivé řezání dortu:

Anonymní poctivé krájení dortu vyžaduje, aby byly nejen stejné hodnoty, ale i samotné kousky [2] . To implikuje symetrickou platnost, ale podmínka je přísnější. Takový řez například neposkytuje výše uvedená symetrická procedura rozděl a vyber, protože v případě a = g dostane první agent vždy kus nejvíce vlevo a druhý vždy dostane kus nejvíce vpravo.
Aristotelovo spravedlivé krájení koláče vyžaduje pouze to, aby agenti s identickými mírami obdrželi kusy se stejnou hodnotou hodnocení [3] . To implikuje symetrickou platnost, ale podmínka je slabší. Vyhovuje mu například asymetrická verze postupu rozděl a vyber – pokud jsou skóre agentů shodné, oba hráči mají přesně 1/2.

Definice

Existuje koláč C , obvykle reprezentovaný jako jednorozměrný segment. Existuje n lidí a každý účastník i má vyhodnocovací funkci VI , která mapuje podmnožiny C na nezáporná čísla.

Procedura dělení je funkce F , která mapuje n vyhodnocovacích funkcí na dělení intervalu C . Část, kterou funkce F přidělí agentu i , bude označena jako . $F(V_{1},\tečky ,V_{n};i)$

Symetrický postup

Procedura dělení F se nazývá symetrická , jestliže pro libovolnou permutaci p indexů (1,…, n ) a libovolné i

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

Konkrétně pro n = 2 je postup symetrický, jestliže

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

a .

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

To znamená, že agent 1 získá stejnou hodnotu, ať hraje první nebo druhý, a totéž platí pro agenta 2.

V dalším příkladu, když n = 3, požadavek na symetrii implikuje (mimo jiné):

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))

Anonymní postup

Procedura dělení F se nazývá anonymní , pokud pro jakoukoli permutaci p indexů (1,…, n ) a pro jakoukoli $i$

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

Jakýkoli anonymní postup je symetrický, protože pokud jsou kusy stejné, jejich odhady jsou jistě stejné.

Opak však není pravdou - je možné, že permutace dá agentovi různé kusy se stejnými hodnotami.

Aristotelský postup

Postup dělení F se nazývá aristotelský , pokud pro : $V_{i}=V_{k}$

V_{i}(F(V_{1},\tečky ,V_{n};i))=V_{k}(F(V_{1},\tečky ,V_{n};k))

Kritérium je pojmenováno po Aristotelovi , který ve své knize o etice napsal: „...když jsou uděleny nerovné podíly se stejným vlastnictvím, nebo když jsou osoby nerovné s rovnými podíly, počet sporů a stížností se zvyšuje.“

Jakýkoli symetrický postup je aristotelský. Nechť p je permutace zaměňující i a k . Ze symetrie to vyplývá

V_{i}(F(V_{1},\tečky ,V_{i},\tečky ,V_{k},\tečky ,V_{n};i))=V_{i}(F( V_{1},\tečky ,V_{k},\tečky ,V_{i},\tečky ,V_{n};k))

Ale protože V i = V k , jsou tyto dvě posloupnosti měr totožné, odtud aristotelovská definice.

Navíc každý závistivý postup krájení dortu je aristotelský - z absence závisti to vyplývá

V_{i}(F(V_{1},\tečky ,V_{n};i))\geqslant V_{i}(F(V_{1},\tečky ,V_{n};k) )V_{k}(F(V_{1},\tečky ,V_{n};k))\geqslant V_{k}(F(V_{1},\tečky ,V_{n};i))

Protože však ze dvou opačných nerovností vyplývá, že obě hodnoty jsou stejné. $V_{i}=V_{k}$

Postup, který vyhovuje slabší podmínce proporcionálního krájení dortu , však nemusí být nutně aristotelský. Sýr [3] uvedl příklad se 4 činidly, ve kterém Even-Paz postup pro proporcionální krájení koláče může poskytnout různé hodnoty pro prostředky se stejnými vyhodnocovacími mírami.

Následuje shrnutí vztahů mezi kritérii:

Anonymní symetrický Aristoteles $\na$ $\na$
Bez závisti Aristoteles $\na$
Bez závisti proporcionální $\na$

Postupy

Jakýkoli postup může být proveden " a priori symetricky" pomocí randomizace. Například v asymetrickém postupu rozděl a vyber lze oddělovač vybrat hozením mince. Takový postup by však ve skutečnosti nebyl symetrický. Proto se výzkum týkající se symetrického poctivého krájení dortů zaměřuje na deterministické algoritmy .

Monabe a Okamoto [1] navrhli pro dva a tři agenty symetrické deterministické procedury bez závisti (“envy-free meta”).

Nicolo a Yu [2] navrhli protokol pro anonymní a Pareto efektivní dělení bez závisti pro dva agenty. Protokol implementuje dokonalou rovnováhu podhry za předpokladu, že každý agent má kompletní informace o odhadech ostatních agentů.

Postup pro symetrické řezání a výběr pro dva prostředky byl studován empiricky v laboratorních experimentech [4] . Alternativní postupy pro symetrické spravedlivé krájení dortu pro dva účastníky jsou značka nejvíce vpravo [5] a zbytek nejvíce vlevo [6] .

Sýr [3] navrhl několik postupů:

Obecné schéma pro transformaci jakékoli závistivé procedury dělení na symetrickou deterministickou proceduru: provedeme původní proceduru n ! krát, jednou pro každou permutaci agentů, a výsledek zvolte podle topologického kritéria (tj. podle minima řezů). Pro velké n se tento postup stává prakticky nepoužitelným .
Aristotelova proporcionální procedura pro n agentů, která vyžaduje dotazy a polynomiální počet aritmetických operací. $O(n^{3})$
Symetrická proporcionální procedura pro n agentů, která vyžaduje dotazy, ale může vyžadovat exponenciální počet aritmetických operací. $O(n^{3})$

Aristotelova proporční procedura

Aristotelský postup sýra [3] pro proporcionální krájení dortu rozšiřuje postup „ jednoho rozdělovače “. Pro usnadnění normalizujeme vyhodnocovací funkce tak, aby hodnota celého koláče pro všechny agenty byla rovna n . Cílem je přidělit každému agentovi podíl, který je alespoň 1.

Jeden hráč je vybrán libovolně, čemuž se říká dělení , rozkrájí dort na n dílů, které vyhodnotí přesně 1.
Je zkonstruován bipartitní graf , ve kterém každý vrchol X je agent, každý vrchol Y je kus koláče a mezi činitelem x a kusem koláče y existuje hrana právě tehdy, když x vyhodnotí kus y alespoň 1. . $G=(X+Y,E)$
Hledáme maximální velikost závistivé párování (PBZ) v G (spárování, ve kterém není žádný agent, který nepatří do párování, ale sousedí, patří k párování). Všimněte si, že dělitel sousedí se všemi n kousky koláče, takže (kde je množina sousedů X v Y ). Proto existuje neprázdná shoda bez závisti [7] . Předpokládejme bez ztráty obecnosti, že PBZ spáruje agenty 1,…, k na kusy , ponecháme agenty a kusy od k +1 dr n bez párování . $|N_{G}(X)|=n\geqslant |X|$ $N_{G}(X)$ ${\displaystyle X_{1},\dots ,X_{k))$
Pro libovolné i z 1,…, k , pro které dáme X i agentu i . Nyní jsou děliči a všem agentům, jejichž vyhodnocovací funkce jsou totožné s funkcí děliče, přiřazeny bloky, které mají stejné hodnoty. $V_{i}(X_{i})=1$
Uvažujme nyní činitele i z 1,…, k pro které . Rozdělme je na podmnožiny se stejnými vektory hodnocení kusů . Pro každou podmnožinu mezi ně rekurzivně rozdělíme jejich dílky (např. pokud se agenti 1, 3, 4 shodují na hodnotách všech dílků 1,…, k , pak mezi ně dílky rekurzivně rozdělíme ). Nyní jsou všichni agenti, jejichž vyhodnocovací funkce jsou identické, přiřazeny do stejných podmnožin a sdílejí podkoláč, jehož hodnota mezi nimi je větší než jejich počet, takže je splněna podmínka rekurze. $V_{i}(X_{i})>1$ $X_{1},\dots ,X_{n}$ ${\displaystyle X_{1},X_{3},X_{4))$
Rekurzivně rozdělujeme nepřidělené části mezi nepřidělené agenty. Všimněte si, že kvůli nedostatku závisti při párování každý nedistribuovaný agent vyhodnotí každý distribuovaný blok na méně než 1, takže hodnoty zbývajících bloků jsou alespoň tak velké jako počet agentů, takže předpoklad pro rekurzi je zachována. ${\displaystyle X_{k+1},\tečky ,X_{k))$

Poznámky

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

Literatura

Yoshifumi Manabe, Tatsuaki Okamoto. Meta-envy-free Cake-cutting Protocols // Sborník příspěvků z 35. mezinárodní konference o matematických základech informatiky. - Berlin, Heidelberg: Springer-Verlag, 2010. - ISBN 9783642151545 .
Antonio Nicolo, Yan Yu. Strategická rozdělení a volba // Hry a ekonomické chování. - 2008. - T. 64 , č. 1 . — ISSN 0899-8256 . - doi : 10.1016/j.geb.2008.01.006 .
Guillaume Cheze. Neplač, abys byl první! Existují symetrické algoritmy spravedlivého dělení. - 2018. - arXiv : 1804.03833v1 .
Maria Kyropoulou, Josué Ortega, Erel Segal-Halevi. Férové krájení dortů v praxi // Sborník příspěvků z konference ACM 2019 o ekonomii a výpočtech. — New York, NY, USA: ACM, 2019. — ISBN 9781450367929 . - doi : 10.1145/3328526.3329592 . - arXiv : 1810.08243 .
Erel Segal-Halevi, Balazs R. Sziklai. Monotonie zdrojů a populační monotonie v propojeném krájení koláčů // Matematické sociální vědy. - 2018. - Sv. 95. - ISSN 0165-4896 . - doi : 10.1016/j.mathsocsci.2018.07.001 . — arXiv : 1703.08928 .
Josue Ortega. Zjevné manipulace při krájení dortů. - 2019. - arXiv : 1908.02988v1 .
Erel Segal-Halevi, Elad Aigner-Horev. Shody bez závisti v bipartitních grafech a jejich aplikace na Fair Division. - 2019. - arXiv : 1901.09527v2 .