Symetrické krájení dortu - Symmetric fair cake-cutting

Symetrické krájení dortu je varianta spravedlivé krájení dortu problém, ve kterém se nestrannost uplatňuje nejen na konečný výsledek, ale také na přiřazení rolí v dělícím řízení.

Jako příklad zvažte narozeninový dort, který musí být rozdělen mezi dvě děti s odlišným vkusem, takže každé dítě má pocit, že jeho podíl je „spravedlivý“, tj. V hodnotě alespoň 1/2 celého dortu. Mohou použít klasiku rozdělit a vybrat postup: Alice nakrájí dort na dva kousky v hodnotě přesně 1/2 v očích a George si vybere kousek, který považuje za cennější. Výsledek je vždy spravedlivý. Postup však není symetrický: zatímco Alice vždy dostane hodnotu přesně 1/2 její hodnoty, George může získat mnohem více než 1/2 jeho hodnoty. Zatímco tedy Alice nezávidí Georgeův podíl, závidí Georgeovu roli v řízení.

Naproti tomu zvažte alternativní postup, při kterém Alice i George udělají na dortu poloviční značky, tj. Každý z nich označí místo, ve kterém by měl být dort krájen, aby si tyto dva kusy byly v jeho očích stejné. Potom je dort krájen přesně mezi těmito řezy - pokud je řez Alice A a Georgeův řez je G, pak se koláč krájí na (a + g) / 2. Li A<G, Alice dostane kousek úplně vlevo a George kousek úplně vpravo; jinak Alice dostane kousek úplně vpravo a George kousek úplně vlevo. Konečný výsledek je stále spravedlivý. A tady jsou role symetrické: jediným případem, kdy role ovlivní konečný výsledek, je kdy A=G, ale v tomto případě mají obě části hodnotu přesně 1/2 pro obě děti, takže role ve výsledné hodnotě nezmění. Alternativní postup je tedy spravedlivý i symetrický.

Myšlenku poprvé představili Manabe a Okamoto,[1] kdo to nazval bez meta-závisti.

Bylo navrženo několik variant symetrického krájení dortu:

  • Anonymní krájení dortu vyžaduje, aby byly stejné nejen hodnoty, ale i samotné části.[2] To znamená symmerickou férovost, ale je to silnější. Například není uspokojen výše uvedeným způsobem symetrického dělení a výběru, protože v tomto případě A=G, první agent dostane vždy kousek úplně vlevo a druhý agent vždy dostane kousek úplně vpravo.
  • Aristotelské poctivé krájení dortu vyžaduje pouze to, aby agenti se stejnými hodnotami hodnot dostali stejnou hodnotu.[3] To naznačuje symetrická spravedlnost, ale je to slabší. Například je uspokojena asymetrickou verzí rozdělení a výběru: pokud jsou ocenění agentů identická, pak oba dostanou hodnotu přesně 1/2.

Definice

Tady je dort C, obvykle se předpokládá, že je jednorozměrný interval. Existují n lidé. Každý i má hodnotovou funkci PROTIi který mapuje podmnožiny C na slabě kladná čísla.

A postup dělení je funkce F že mapy n funkce hodnot do oddílu C. Kus přidělený uživatelem F agentovi i je označen F(PROTI1,...,PROTIn; i).

Symetrický postup

Postup dělení F je nazýván symetrický pokud pro jakoukoli permutaci p z (1, ...,n) a pro všechny i:

PROTIi(F(PROTI1,...,PROTIn; i)) = PROTIi(F(PROTIp (1),...,PROTIp (n); p−1(i)))

Zejména když n= 2, postup je symetrický, pokud:

PROTI1(F(PROTI1,PROTI2; 1)) = PROTI1(F(PROTI2,PROTI1; 2)) a PROTI2(F(PROTI1,PROTI2; 2)) = PROTI2(F(PROTI2,PROTI1; 1))

To znamená, že agent 1 získá stejnou hodnotu, ať už hraje první nebo druhý, a totéž platí pro agenta 2. Jako další příklad, když n= 3, požadavek na symetrii znamená (mimo jiné):

PROTI1(F(PROTI1,PROTI2,PROTI3; 1)) = PROTI1(F(PROTI2,PROTI3,PROTI1; 3)) = PROTI1(F(PROTI3,PROTI1,PROTI2; 2)).

Anonymní postup

Postup dělení F je nazýván anonymní pokud pro jakoukoli permutaci p z (1, ...,n) a pro všechny i:

F(PROTI1,...,PROTIn; i) = F(PROTIp (1),...,PROTIp (n); p−1(i))

Jakýkoli anonymní postup je symetrický, protože pokud jsou části stejné - jejich hodnoty jsou jistě stejné.

Opak ale není pravdou: je možné, že permutace dává agentovi různé kousky se stejnou hodnotou.

Aristotelský postup

Postup dělení F je nazýván aristotelský pokud, kdykoli PROTIi=PROTIk:

PROTIi(F(PROTI1,...,PROTIn; i)) = PROTIk(F(PROTI1,...,PROTIn; k))

Kritérium je pojmenováno po Aristoteles, který ve své knize o etice napsal: „... právě tehdy, když rovní mají nebo jim jsou přiděleny nerovné podíly nebo osoby, které se nerovnají rovným dílům, vznikají spory a stížnosti.“ Každý symetrický postup je aristotelický. Nechat p být obměnou, která si vyměňuje i a k. Symetrie znamená, že:

PROTIi(F(PROTI1,....PROTIi,...,PROTIk,...,PROTIn; i)) = PROTIi(F(PROTI1,....PROTIk,...,PROTIjá, ...,PROTIn; k))

Ale od PROTIi=PROTIk, dvě posloupnosti hodnotových měr jsou identické, takže z toho vyplývá definice aristoteliánu. Navíc každý postup řezání dortů bez závisti is aristotelian: envy-freeness implies that that:

PROTIi(F(PROTI1,...,PROTIn; i)) ≥ PROTIi(F(PROTI1,...,PROTIn; k))PROTIk(F(PROTI1,...,PROTIn; k)) ≥ PROTIk(F(PROTI1,...,PROTIn; i))

Ale od PROTIi=PROTIk, dvě nerovnosti znamenají, že obě hodnoty jsou stejné.

Postup, který splňuje slabší podmínku Proporcionální krájení dortu není nutně aristotelský. Cheze[3] ukazuje příklad se 4 agenty, ve kterých Procedura even-Paz pro proporcionální krájení dortu může agentům se stejnými hodnotami dávat různé hodnoty.

Následující tabulka shrnuje vztahy mezi kritérii:

  • Anonymní → Symetrické → Aristotelian
  • Bez závisti → Aristotelian
  • Bez závisti → Proporcionální

Postupy

Každý postup lze provést „symetricky předem“ randomizací. Například v asymetrickém rozdělování a výběru lze rozdělovač vybrat hozením mince. Takový postup však není symetrický ex post. Proto se výzkum týkající se symetrického férového krájení dortů zaměřuje na deterministické algoritmy.

Manabe a Okamoto[1] představil symetrické a závistivé („bez závisti“) deterministické postupy pro dva a tři agenty.

Nicolo a Yu[2] představil anonymní, závistivý a Pareto-efektivní divizní protokol pro dva agenty. Protokol implementuje alokaci v subgame dokonalá rovnováha, za předpokladu, že každý agent má úplné informace o ocenění druhého agenta.

Symetrický postup cut and choose pro dvě látky byl studován empiricky v laboratorním experimentu.[4] Alternativní symetrické postupy pro dělení dortu pro dva agenty jsou značka zcela vpravo[5] a listy úplně vlevo.[6]

Cheze[3] představil několik postupů:

  • Obecné schéma pro převod libovolného postupu bez závisti na symetrický deterministický postup: spusťte původní postup n! jednou, pro každou permutaci agentů, a vyberte jeden z výsledků podle nějakého topologického kritéria (např. minimalizace počtu řezů). Tento postup není praktický, když n je velký.
  • Aristotelský poměrný postup pro n agenti, což vyžaduje O (n3) dotazy a polynomický počet aritmetických operací rozhodčím.
  • Symetrický proporcionální postup pro n agenti, což vyžaduje O (n3) dotazy, ale může vyžadovat exponenciální počet aritmetických operací ze strany rozhodčího.

Aristotelovský poměrný postup

Aristotelský postup Cheze[3] pro proporcionální krájení dortu rozšiřuje osamělý dělič postup. Z důvodu pohodlí normalizujeme ocenění tak, aby hodnota celého dortu byla n pro všechny agenty. Cílem je dát každému agentovi figurku v hodnotě alespoň 1.

  1. Jeden hráč zvolený libovolně, nazvaný dělič, krájí dort na n kousky, jejichž hodnota v jeho očích je přesně 1.
  2. Postavte a bipartitní graf G = (X + Y, E), ve kterém každý vrchol v X je agent, každý vrchol v Y je kus a mezi agentem je hrana X a kousek y iff X hodnoty y alespoň 1.
  3. Najděte maximální mohutnost záviděníhodné shody v G (shoda, ve které k uzavřenému kousku nesousedí žádný nepřidělený agent). Všimněte si, že dělič sousedí se všemi n kousky, takže |NG(X)|= n ≥ | X | (kde NG(X) je množina sousedů X v Y). Proto existuje neprázdná shoda bez závisti.[7] Předpokládejme, že w.l.o.g. že EFM odpovídá agentům 1, ...,k na kousky X1,...,Xk, a ponechává bezkonkurenční agenty a kousky z k+1 až n.
  4. Pro každého i v 1,...,k pro který PROTIi(Xi) = 1 - dát Xi agentovi i. Nyní je rozdělovači a všem agentům, jejichž hodnotová funkce je stejná jako u rozdělovačů, přidělen kus a mají stejnou hodnotu.
  5. Zvažte nyní agenty i v 1,...,k pro který PROTIi(Xi)> 1. Rozdělte je na podmnožiny se stejným vektorem hodnot pro jednotlivé díly X1,...,Xk. Pro každou podmnožinu rekurzivně rozdělte jejich části mezi ně (například pokud se agenti 1, 3, 4 dohodnou na hodnotách všech částí 1, ...,k, poté rozdělte kusy X1,X3,X4 rekurzivně mezi nimi). Nyní jsou všichni agenti, jejichž hodnotová funkce je identická, přiřazeni ke stejné podmnožině a rozdělují subcake, jehož hodnota pro ně je větší než jejich počet, takže je splněna podmínka rekurze.
  6. Rekurzivně rozdělte nesrovnatelné kousky Xk+1, ..., Xn mezi nepřekonatelnými agenty. Všimněte si, že díky závisti-volnosti shody hodnotí každý nepřizpůsobený agent každý shodný kousek na méně než 1, takže si váží zbývajících kousků na více než na počtu agentů, takže je splněna podmínka rekurze.

Reference

  1. ^ A b Manabe, Yoshifumi; Okamoto, Tatsuaki (2010). „Protokoly na krájení dortů bez meta závisti“. Sborník z 35. mezinárodní konference o matematických základech informatiky. MFCS'10. Berlin, Heidelberg: Springer-Verlag: 501–512. ISBN  9783642151545.
  2. ^ A b Nicolò, Antonio; Yu, Yan (01.09.2008). „Strategické rozdělení a výběr“ (PDF). Hry a ekonomické chování. 64 (1): 268–289. doi:10.1016 / j.geb.2008.01.006. ISSN  0899-8256.
  3. ^ A b C d Chèze, Guillaume (11.04.2018). „Neplač, buď první! Symetrické algoritmy spravedlivého dělení existují“. arXiv:1804.03833v1. Citovat deník vyžaduje | deník = (Pomoc)
  4. ^ Kyropoulou, Maria; Ortega, Josué; Segal-Halevi, Erel (2019). „Férové ​​krájení dortů v praxi“. Sborník konferencí ACM o ekonomii a výpočtu z roku 2019. ES19. New York, NY, USA: ACM: 547–548. arXiv:1810.08243. doi:10.1145/3328526.3329592. ISBN  9781450367929. S2CID  53041563.
  5. ^ Segal-Halevi, Erel; Sziklai, Balázs R. (01.09.2018). "Zdrojová monotónnost a populační monotónnost při spojeném krájení koláčů". Matematické sociální vědy. 95: 19–30. arXiv:1703.08928. doi:10.1016 / j.mathsocsci.2018.07.001. ISSN  0165-4896. S2CID  16282641.
  6. ^ Ortega, Josue (08.08.2019). „Zjevná manipulace při krájení dortu“. arXiv:1908.02988v1. Citovat deník vyžaduje | deník = (Pomoc)
  7. ^ Segal-Halevi, Erel; Aigner-Horev, Elad (2019-01-28). „Bezzávidné shody v bipartitních grafech a jejich aplikace na spravedlivé rozdělení“. arXiv:1901.09527v2. Citovat deník vyžaduje | deník = (Pomoc)