Tăiere simetrică de tort echitabil

Tăierea simetrică a tortului este o variantă a problemei de tăiere a prăjiturii în care corectitudinea este evaluată nu numai de părțile tortului, ci și de participarea la tăiere.

Esență

Luați în considerare un exemplu: să se dea o prăjitură și să fie împărțită între Alice și George, ale căror gusturi diferă, astfel încât fiecare dintre ei să simtă că partea lui este tăiată și aleasă corect, adică astfel încât fiecare dintre ei să aibă valoarea de cota de cel puțin jumătate din valoarea întregului tort. S-ar putea folosi soluția clasică „ împărți și alege ”: Alice taie tortul în două astfel de bucăți care sunt echivalente cu ea, iar George alege o bucată pe care o consideră mai valoroasă. Cu toate acestea, există un defect în această soluție: Alice primește întotdeauna o acțiune cu o valoare de 1/2, dar George poate primi o acțiune cu o valoare mai mare de 1/2. Prin urmare, această tăiere se numește corectă , dar asimetrică , adică Alice nu vede nimic în neregulă cu care cota a ales George, dar se simte nedreaptă că George a fost cel care a ales cota și ea a tăiat tortul.

Luați în considerare o altă soluție: Alice și George își marchează amândoi granița (în cel mai simplu caz, segmente paralele sau coincidente), care, din punctul de vedere al fiecăruia dintre ei, împarte tortul în jumătăți egale. Apoi tortul este tăiat exact la mijloc între aceste limite: să notăm ca parte volumetrică a lobului stâng al tortului, în care Alice s-a împărțit și ca g - partea volumetrică a lobului stâng al tortului, în care George a împărțit, - apoi tortul trebuie tăiat în jumătate în două părți, partea volumetrică rămasă din care este egală cu . Dacă a < g , atunci Alice primește piesa din stânga (a cărei valoare este mai mare decât cota lui Alice), iar George ia piesa din dreapta (a cărei valoare este și ea mai mare). Dacă a > g , atunci Alice, dimpotrivă, primește piesa dreaptă, iar George cea stângă. Prin urmare, această soluție a problemei se numește corectă și simetrică . $(a+g)/2$

Această idee a fost propusă pentru prima dată de Monabe și Okamoto [1] , care au numit-o meta-envy-free .

Au fost propuse mai multe opțiuni pentru tăierea corectă simetrică a tortului:

Tăierea corectă anonimă a tortului necesită nu numai că valorile sunt aceleași, dar piesele în sine sunt egale [2] . Aceasta implică valabilitate simetrică, dar condiția este mai strictă. De exemplu, o astfel de tăiere nu este furnizată de procedura simetrică de împărțire și alegere de mai sus, deoarece în cazul a = g , primul agent primește întotdeauna piesa cea mai din stânga, iar al doilea întotdeauna obține piesa cea mai din dreapta.
Tăiatul echitabil al lui Aristotel cere doar ca agenții cu măsuri identice să primească bucăți cu aceeași valoare de evaluare [3] . Aceasta implică validitate simetrică, dar condiția este mai slabă. De exemplu, este satisfăcut de o versiune asimetrică a procedurii de împărțire și alegere - dacă scorurile agenților sunt identice, ambii jucători sunt exact 1/2.

Definiții

Există un tort C , reprezentat de obicei ca un segment unidimensional. Există n oameni și fiecare parte interesată i are o funcție de evaluare V i care mapează submulțimile lui C la numere nenegative.

Procedura de împărțire este o funcție F care mapează n funcții de evaluare la o partiție a intervalului C . Piesa pe care funcția F o alocă agentului i va fi notată ca . $F(V_{1},\dots, V_{n};i)$

Procedura simetrică

Procedura de împărțire F se numește simetrică dacă pentru orice permutare p a indicilor (1,…, n ) și orice i

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

În special, pentru n = 2 procedura este simetrică dacă

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

și .

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

Aceasta înseamnă că agentul 1 primește aceeași valoare indiferent dacă joacă primul sau al doilea, și același lucru este valabil și pentru agentul 2.

Într-un alt exemplu, când n = 3, cerința de simetrie implică (printre altele):

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

Procedura anonimă

Procedura de împărțire F se numește anonimă dacă pentru orice permutare p a indicilor (1,…, n ) și pentru orice $i$

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

Orice procedură anonimă este simetrică, deoarece dacă piesele sunt egale, estimările lor sunt cu siguranță egale.

Invers, însă, nu este adevărat - este posibil ca permutarea să dea agentului piese diferite cu aceleași valori.

Procedura aristotelică

Procedura de împărțire F se numește aristotelic , dacă pentru : $V_{i}=V_{k}$

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

Criteriul este numit după Aristotel , care a scris în cartea sa despre etică: „...când se acordă cote inegale cu drepturi de proprietate egale, sau când persoanele sunt inegale cu cote egale, numărul de dispute și plângeri crește”.

Orice procedeu simetric este aristotelic. Fie p o permutare care schimbă i și k . Din simetrie rezultă că

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

Dar din moment ce V i = V k , aceste două secvențe de măsuri sunt identice, de unde și definiția lui aristotelic.

Mai mult, orice procedură invidioasă de tăiere a prăjiturii este aristotelică - din absența invidiei rezultă că

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

Cu toate acestea, deoarece , din două inegalități opuse rezultă că ambele valori sunt egale. $V_{i}=V_{k}$

Cu toate acestea, o procedură care satisface condiția mai slabă a tăierii proporțional a tortului nu este neapărat aristotelică. Cheese [3] a dat un exemplu cu 4 agenți, în care procedura Even-Paz pentru tăierea proporțională a turtei poate da valori diferite pentru agenți cu măsuri de evaluare identice.

Următoarele rezumă relațiile dintre criterii:

Aristotel simetric anonim $\la$ $\la$
Fără invidie Aristotel $\la$
Fără Invidie Proporțională $\la$

Proceduri

Orice procedură poate fi făcută „ a priori simetrică” prin randomizare. De exemplu, într-o procedură asimetrică de împărțire și alegere, divizorul poate fi ales prin aruncarea unei monede. Cu toate acestea, o astfel de procedură nu ar fi de fapt simetrică. Prin urmare, cercetările privind tăierea simetrică a prăjiturii se concentrează pe algoritmi determiniști .

Monabe și Okamoto [1] au propus proceduri deterministe simetrice fără invidie („meta fără invidie”) pentru doi și trei agenți.

Nicolo și Yu [2] au propus un protocol pentru împărțirea anonimă și Pareto eficientă fără invidie pentru doi agenți. Protocolul implementează un echilibru perfect sub-joc în ipoteza că fiecare agent are informații complete despre estimările altor agenți.

Procedura de tăiere simetrică și selecție pentru doi agenți a fost studiată empiric în experimente de laborator [4] . Procedurile alternative pentru tăierea corectă simetrică a tortului pentru doi participanți sunt marcajul din dreapta [5] și restul din stânga [6] .

Cheese [3] a sugerat mai multe procedee:

Schema generală de transformare a oricărei proceduri de divizare invidioase într-o procedură deterministă simetrică: efectuăm procedura inițială n ! de ori, o dată pentru fiecare permutare a agenților, și alegeți rezultatul în funcție de criteriul topologic (adică după minimul de tăieturi). Această procedură devine practic inaplicabilă pentru n mare .
O procedură proporțională aristotelică pentru n agenți care necesită interogări și un număr polinomial de operații aritmetice. $O(n^{3})$
O procedură proporțională simetrică pentru n agenți care necesită interogări, dar poate necesita un număr exponențial de operații aritmetice. $O(n^{3})$

Procedura proporțională a lui Aristotel

Procedura aristotelică a Brânzei [3] pentru tăierea proporțională a prăjiturii extinde procedura „ single divider ”. Pentru comoditate, normalizăm funcțiile de evaluare astfel încât valoarea întregului tort pentru toți agenții să fie egală cu n . Scopul este de a aloca fiecărui agent o cotă de cel puțin 1.

Un jucător este ales în mod arbitrar, ceea ce se numește împărțire , el taie tortul în n părți, pe care le evaluează la exact 1.
Se construiește un grafic bipartit în care fiecare vârf al lui X este un agent, fiecare vârf al lui Y este o bucată de tort și există o margine între agentul x și bucata de tort y dacă și numai dacă x evaluează piesa y la cel puțin 1. . $G=(X+Y,E)$
Căutăm potrivirea fără invidie de dimensiune maximă (PBZ) în G (o potrivire în care nu există agent care să nu aparțină potrivirii, dar să fie adiacent, să aparțină piesei de tort potrivite). Rețineți că divizorul este adiacent tuturor n bucăți ale tortului, deci (unde este mulțimea vecinilor lui X în Y ). Prin urmare, o potrivire nevidă fără invidie există [7] . Să presupunem, fără pierderi de generalitate, că PBZ potrivește agenții 1,…, k la bucăți , lăsând agenți și piese din k +1 dr n fără potrivire . $|N_{G}(X)|=n\geqslant |X|$ $N_{G}(X)$ $X_{1},\dots, X_{k)$
Pentru orice i din 1,…, k , pentru care , dăm X i agentului i . Acum, divizorului și tuturor agenților ale căror funcții de evaluare sunt identice cu funcția divizorului li se atribuie bucăți care au aceleași valori. $V_{i}(X_{i})=1$
Luați în considerare acum agenții i din 1,…, k pentru care . Să le împărțim în submulțimi cu vectori egali de evaluări ale pieselor . Pentru fiecare submulțime , împărțim recursiv piesele lor între ele (de exemplu, dacă agenții 1, 3, 4 sunt de acord cu valorile tuturor pieselor 1,..., k , atunci împărțim piesele recursiv între ele). Acum toți agenții ale căror funcții de evaluare sunt identice sunt alocați acelorași submulțimi și împărtășesc subcake-ul a cărui valoare între ei este mai mare decât numărul lor, astfel încât precondiția recursiei este satisfăcută. $V_{i}(X_{i})>1$ $X_{1},\dots ,X_{n}$ ${\displaystyle X_{1},X_{3},X_{4))$
Împărțim recursiv bucățile nealocate între agenții nealocați. Rețineți că, din cauza lipsei de invidie în potrivire, fiecare agent nedistribuit evaluează fiecare bucată distribuită la mai puțin de 1, astfel încât valorile bucăților rămase sunt cel puțin la fel de mari ca numărul de agenți, deci precondiția pentru recursivitate se păstrează. $X_{k+1},\dots, X_{k)$

Note

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

Literatură

Yoshifumi Manabe, Tatsuaki Okamoto. Protocoale de tăiere a prăjiturii fără meta-invidie // Proceedings of the 35th International Conference on Mathematical Foundations of Computer Science. - Berlin, Heidelberg: Springer-Verlag, 2010. - ISBN 9783642151545 .
Antonio Nicolo, Yan Yu. Împărțiți strategic și alegeți // Jocuri și Comportament Economic. - 2008. - T. 64 , nr. 1 . — ISSN 0899-8256 . - doi : 10.1016/j.geb.2008.01.006 .
Guillaume Cheze. Nu plânge să fii primul! Există algoritmi simetrici de împărțire corectă. - 2018. - arXiv : 1804.03833v1 .
Maria Kyropoulou, Josué Ortega, Erel Segal-Halevi. Fair Cake-Cutting în practică // Proceedings of the 2019 ACM Conference on Economics and Computation. — New York, NY, SUA: ACM, 2019. — ISBN 9781450367929 . - doi : 10.1145/3328526.3329592 . - arXiv : 1810.08243 .
Erel Segal-Halevi, Balazs R. Sziklai. Monotonitatea resurselor și monotonitatea populației în tăierea prăjiturii conectate // Științe sociale matematice. - 2018. - Vol. 95. - ISSN 0165-4896 . - doi : 10.1016/j.mathsocsci.2018.07.001 . — arXiv : 1703,08928 .
Josue Ortega. Manipulări evidente în tăierea prăjiturii. - 2019. - arXiv : 1908.02988v1 .
Erel Segal-Halevi, Elad Aigner-Horev. Potriviri fără invidie în grafice bipartite și aplicațiile lor la diviziunea echitabilă. - 2019. - arXiv : 1901.09527v2 .