Provocarea de tăiere a prăjiturii

Tăierea corectă a tortului este un fel de problemă de împărțire corectă . Problema implică o resursă eterogenă, cum ar fi un tort cu diverse decorațiuni (de la smântână , fructe de pădure, ciocolată ), care se presupune că sunt divizibile - adică o bucată arbitrar mică poate fi tăiată din ea fără a distruge întreaga valoare. Resursa trebuie împărțită între mai mulți parteneri care au preferințe diferite pentru diferite părți ale tortului. De exemplu, unii preferă decorațiunile din ciocolată, alții preferă cireșele, în timp ce alții vor doar o bucată mai mare. Împărțirea trebuie să fie subiectiv corectă, fiecare participant trebuie să primească o piesă pe care o consideră o cotă echitabilă.

Termenul „tort” este doar o metaforă , procedurile de tăiere a tortului pot fi folosite pentru a separa diferite tipuri de resurse, cum ar fi proprietatea asupra terenului , spațiul publicitar sau timpul de difuzare.

Problema tăierii prăjiturii a fost propusă de Hugo Steinhaus după al Doilea Război Mondial [1] și a rămas un subiect de studiu intens în matematică , informatică , economie și științe politice [2] .

Ipoteze

Există o prăjitură , care se presupune de obicei a fi un segment finit unidimensional, un poligon bidimensional sau o submulțime finită a unui spațiu euclidian de dimensiuni mai mari . $C$ $\mathbb{R}^d$

Există o persoană cu drepturi egale la [3] . $n$ $C$

$C$ trebuie tăiate în astfel de subseturi disjunse încât fiecare participant să primească un subset separat. Piesa destinată participantului este desemnată ca și . $n$ $i$ $X_{i}$ $C=X_{1}\sqcup \cdots \sqcup X_{n)$

Fiecare participant trebuie să primească o piesă cu o valoare „justă”. Corectitudinea este determinată pe baza funcțiilor subiective de valoare . Fiecare față are o funcție de valoare subiectivă care mapează subseturile la numere. $i$ $V_i$ $C$

Se presupune că funcțiile sunt absolut continue ca lungime, suprafață sau (în general) măsura Lebesgue [4] . Aceasta înseamnă că nu există „atomi”, adică puncte singulare cărora li se atribuie o valoare pozitivă de către unul sau mai mulți agenți. Astfel, toate părțile tortului sunt divizibile.

De asemenea, în unele cazuri, se presupune că funcțiile de evaluare sunt sigma-aditive .

Un exemplu de tort

Vom folosi următorul tort ca exemplu:

Tortul este format din două părți - ciocolată și vanilie.
Sunt doi participanți - Alice și George.
Alice evaluează porția de ciocolată la 9 unități și porția de vanilie la 1 unitate.
George notează porția de ciocolată la 6 unități și porția de vanilie la 4.

Cereri pentru dreptate

Criteriul original și cel mai general al justiției este proporționalitatea (PR, proporționalitate în engleză , PR). În împărțirea proporțională a tortului , fiecare participant primește o bucată, a cărei valoare o estimează cel puțin în valoarea totală a întregului tort. În exemplul de mai sus, o împărțire proporțională poate fi obținută dând toată porția de vanilie și 4/9 din porția de ciocolată lui George (cu un scor total de 6,66), iar restul de 5/9 din porția de ciocolată este dat lui Alice (cu un scor total de 5). Simbolic: $1/n$

\forall {i}:\ V_{i}(X_{i})\geqslant 1/n

Criteriul proporționalității poate fi generalizat la situații în care drepturile oamenilor nu sunt egale. De exemplu, la împărțirea proporțională a unui tort cu cote diferite , tortul aparține acționarilor, deci unul dintre ei deține 20%, iar celălalt 80% din tort. Aceasta conduce la un criteriu de proporționalitate ponderată :

\forall i:V_{i}(X_{i})\geqslant w_{i}

unde w i sunt greutăți a căror sumă este 1.

Un alt criteriu tipic este absența invidiei (OZ, engleză envy-freeness , EF). Cu o împărțire invidioasă [5] , fiecare persoană primește o piesă, a cărei valoare, după această persoană, nu este mai mică decât valoarea celorlalte piese. Limbaj formal:

\forall i,j:\V_{i}(X_{i})\geqslant V_{i}(X_{j})

În unele cazuri, există o relație de implicație (consecință) între proporționalitate și lipsa de invidie, reflectată în următorul tabel:

Agenți	Evaluări	din OZ urmează PR?	din PR urmează OZ?
2	aditiv	da	da
2	general	Nu	da
3+	aditiv	da	Nu
3+	general	Nu	Nu

Al treilea criteriu, mai puțin utilizat este imparțialitatea ( echitabilitatea engleză , EQ). Într -o împărțire imparțială , fiecare persoană mănâncă o bucată cu exact aceeași valoare de evaluare. În exemplul de tort, tăierea imparțială poate fi obținută oferind fiecărui participant jumătate din ciocolată și jumătate din bucățile de vanilie, astfel încât fiecare participant să se bucure de o valoare de 5. În mod simbolic:

\forall i,j:\V_{i}(X_{i})=V_{j}(X_{j})

Al patrulea criteriu este acuratețea . Dacă ponderea fiecărui partener i este egală cu w i , atunci o diviziune exactă este o diviziune în care:

\forall {i,j}:\ V_{i}(X_{j})=w_{j}

Dacă toate greutățile sunt egale (1/ n ), atunci tăietura se numește perfectă și

\forall i,j:\V_{i}(X_{j})=1/n

Cerințe geometrice

În unele cazuri, piesele destinate participanților trebuie să îndeplinească unele constrângeri geometrice pe lângă corectitudine.

Cea mai comună limitare este conectivitatea . În cazul unui tort unidimensional, această cerință se traduce printr-o cerință ca piesele să fie intervale. În cazul în care tortul este un cerc unidimensional („plăcintă”), acest lucru se traduce prin cerința ca fiecare piesă să fie un arc. Vezi articolul „ Problema tăierii corecte a plăcintei ”.
O altă limitare este adiacența . Această limitare se aplică în cazul în care „tortul” este un teritoriu disputat care trebuie împărțit între țările limitrofe. În acest caz, se poate cere ca piesele date la granița țării să se întâlnească pe teritoriul actual al țării. Această constrângere este gestionată de problema împărțirii terenurilor Hill-Beck .
La împărțirea terenului, există adesea constrângeri bidimensionale, cum ar fi fiecare piesă fiind un pătrat sau (mai general) un obiect gras [6] [7] .

Cerințe suplimentare

În jurisprudență, este adesea luată în considerare rentabilitatea compartimentării. Vezi articolul „ Tăierea eficientă a prăjiturii ”.

Pe lângă proprietățile dezirabile ale tăierilor finite, există și proprietăți dezirabile ale procesului de divizare. O astfel de proprietate este veridicitatea (cunoscută și sub numele de compatibilitate cu stimulul ), care poate avea două niveluri.

Adevarul slab înseamnă că, dacă un partener își dezvăluie adevărata valoare algoritmului, i se garantează că va primi o cotă echitabilă (de exemplu, valorile întregului tort în cazul împărțirii proporționale), indiferent de ceea ce fac ceilalți parteneri. . Chiar dacă toți ceilalți parteneri formează o coaliție pentru a-i provoca un rău maxim, el va primi totuși cota garantată. Majoritatea algoritmilor de tăiere a prăjiturii sunt adevărate în acest sens [1] . $1/n$
Adevărul puternic înseamnă că niciunul dintre parteneri nu poate câștiga un avantaj mințind. Adică, comportamentul sincer este strategia dominantă . Majoritatea protocoalelor de tăiere a prăjiturii nu sunt strict adevărate. Construirea unui protocol de divizare strict veridic este o sarcină dificilă [8] .

Rezultate

2 persoane - o împărțire proporțională și fără invidie

Pentru oameni, diviziunea OD există întotdeauna și poate fi găsită folosind protocolul împărțire și alegere . Dacă funcțiile de evaluare sunt aditive, această reducere va fi și PR, în caz contrar proporționalitatea nu este garantată. $n=2$

Împărțire proporțională

Pentru n persoane cu scoruri aditive, există întotdeauna o reducere proporțională. Cele mai utilizate protocoale:

Last-Minimum Procedure , un protocol care poate asigura că bucățile sunt conectate (adică niciun participant nu primește două sau mai multe bucăți separate). În special, dacă tortul este un interval unidimensional, fiecare participant va primi un interval. Protocolul este discret și poate fi efectuat în runde. Este nevoie de acțiune. $n$ $O(n^{2})$
Procedura Dubins-Spenier Moving Knife este o versiune continuă în timp a protocolului Ultima Descreștere [9] .
Protocolul Fink (cunoscut și ca perechi consecutive sau alegere unică ) este un protocol discret care poate fi folosit pentru a tăia online - dacă se cunoaște tăierea proporțională pentru parteneri, atunci când un nou partener intră în joc, protocolul modifică tăierea existentă astfel încât participantul care vine și deja participanții la partajare primesc . Dezavantajul protocolului este că fiecare partener primește un număr mare de piese individuale. $n-1$ $1/n$
Protocolul Even-Paz , bazat pe bisecția continuă a unei prăjituri și a unui grup de agenți și care necesită toateacțiunile. Acesta este cel mai rapid protocol determinist posibil pentru diviziunea proporțională și cel mai rapid protocol posibil pentru diviziunea proporțională, care garantează că toate piesele sunt conectate. $O(n\log n)$
Protocolul Edmonds-Prus este un protocol randomizat care necesită toate acțiunile, dar garantează doar tăierea parțial proporțională (fiecare participant primește cel puțin , unde este o constantă) și poate oferi fiecărui participant un set de firimituri în loc de o bucată coerentă. $Pe)$ $1/an$ $A$
Protocolul de împărțire a terenurilor Beck poate oferi o împărțire proporțională a teritoriului în litigiu între mai multe țări vecine. În acest caz, fiecare țară primește o cotă care este atât conectată, cât și se învecinează cu teritoriul actual al țării.
Protocolul de împărțire super-proporțională al lui Woodall dă o diviziune în care fiecare participant primește strict mai mult de , având în vedere că cel puțin doi participanți au opinii diferite despre valoarea a cel puțin unei piese. $1/n$

Vezi articolul „ Împărțirea proporțională a unui tort cu diferite proporții ” pentru detalii și o bibliografie completă.

Algoritmii de mai sus se concentrează în principal pe agenți cu o cotă egală de cerințe de resurse. Cu toate acestea, le puteți generaliza și obține Împărțirea proporțională a tortului cu cote diferite .

Diviziune invidioasă

Diviziunea PO pentru o persoană există chiar dacă evaluările nu sunt aditive, atâta timp cât sunt reprezentate de seturi de preferințe consistente. Diviziunea OD a fost studiată separat pentru cazul în care piesele trebuie conectate și pentru cazul în care piesele pot consta din părți separate deconectate. $n$

Pentru piesele conectate, principalele rezultate sunt:

Procedura „Moving Knife” a lui Stromquist produce o împărțire fără invidie pentru 3 persoane, atribuindu-le fiecăruia un cuțit și cerându-le să-și miște continuu cuțitele peste tort, conform procedurii prescrise.
Protocolul Simmons poate oferi o aproximare de feliere fără invidie pentru oameni cu o precizie arbitrară. Dacă funcțiile de evaluare sunt aditive, împărțirea va fi și proporțională. În rest, împărțirea rămâne lipsită de invidie, dar nu neapărat proporțională. Algoritmul oferă o modalitate rapidă și practică de a rezolva unele probleme de împărțire corectă [10] [11] . $n$

Ambii acești algoritmi sunt infiniti: primul este continuu, în timp ce al doilea poate dura o perioadă infinită de timp pentru a converge. De fapt, tăierile fără invidie în intervale conectate pentru 3 sau mai multe persoane nu pot fi găsite prin niciun protocol finit.

Pentru (eventual) bucăți deconectate, principalele rezultate sunt:

Procedura discretă Selfridge-Conway produce o tăietură fără invidie pentru trei participanți în cel mult 5 tăieturi.
Procedura Brahms-Taylor-Zwicker „Moving Knife” produce o tăietură fără invidie pentru patru participanți în cel mult 11 tăieturi.
O variantă a protocolului „ Last Reducer ” cu reutilizare găsește o aproximare aditivă la tăierea fără invidie într-un timp limitat. În mod specific, pentru orice constantă , protocolul produce o porțiune în care valoarea pentru fiecare membru este cel puțin mai mare decât cea mai mare valoare minus în timp . $\epsilon >0$ $\epsilon$ $O(n^{2}/\epsilon )$
Trei proceduri diferite, una de Brahms și Taylor (1995) , alta de Robertson și Webb (1998) și încă o alta, procedura Pikurko (2000) asigură tăierea fără invidie pentru oameni. Ambii algoritmi necesită un număr finit, dar nelimitat de tăieturi. $n$
Procedura lui Aziz și McKenzie (2016) găsește o tăiere fără invidie pentru oameni pentru un număr limitat de interogări. $n$

Rezultatul negativ în cazul general este mult mai slab decât în cazul conexiunii. Tot ce știm este că orice algoritm de tăiere fără invidie trebuie să folosească cel puțin interogări. Există un decalaj mare între acest rezultat și complexitatea de calcul a procedurilor cunoscute. $\Omega (n^{2})$

Consultați tăierea prăjiturii fără invidie [ 5 ] pentru detalii și o bibliografie completă .

Diviziune eficientă

Când funcțiile de evaluare sunt aditive, există o reducere de utilitate ( Utilitar-maximal , UM) . Intuitiv, pentru a crea o tăietură RP, trebuie să dăm fiecărui participant o bucată de tort cu o valoare care este maximă pentru el. În exemplul prăjiturii RP, tăierea îi va oferi Alicei toată ciocolata și a lui George toată vanilia, obținând utilitate . $9+4=13$

Acest proces este ușor de implementat dacă funcțiile de evaluare sunt constante pe bucăți, adică tortul poate fi împărțit în bucăți astfel încât densitatea prețului pe fiecare bucată să fie constantă pentru toți participanții. Când funcțiile de estimare nu sunt constante pe bucăți, existența tăierilor RP se bazează pe o generalizare a acestei proceduri pentru funcțiile de estimator folosind teorema Radon-Nikodim , vezi Teorema 2 în Dubins și Spanier [9] .

Când tortul este unidimensional și piesele trebuie conectate (adică segmente continue), algoritmul simplu de atribuire a piesei agentului cel mai semnificativ nu funcționează. În acest caz, sarcina de a găsi RP-ul tăieturii este NP-hard și, în plus, nicio schemă FPTAS nu este posibilă decât dacă P = NP. Există un algoritm de aproximare de 8 ori și un algoritm de complexitate parametrizată care este exponențial în numărul de jucători [12] .

Pentru orice set de ponderi pozitive, partiția RP ponderată poate fi găsită prin metode similare. Prin urmare, partițiile Pareto eficiente ( PE) există întotdeauna .

Justiția procesuală

Recent, a existat interes nu numai pentru corectitudinea diviziunii finale, ci și pentru corectitudinea procedurii de divizare - nu ar trebui să existe nicio diferență între diferitele roluri în procedură. A fost studiată o anumită corectitudine procedurală:

Anonimatul cere ca în cazul permutării agenților și repetarea procedurii, fiecare agent să primească exact aceeași piesă ca în diviziunea inițială. Aceasta este o condiție strictă. În prezent, procedura anonimă este cunoscută doar pentru 2 agenți.
Simetria cere ca în cazul în care agenții sunt permuți și procedura se repetă pentru agenții permuți, fiecare agent să primească aceeași valoare ca în diviziunea inițială. Aceasta este o condiție mai slabă decât anonimatul. În prezent, procedurile simetrice și proporționale sunt cunoscute pentru orice număr de agenți și necesită interogări. O procedură simetrică și fără invidie este cunoscută pentru orice număr de agenți, dar necesită un timp de execuție mult mai lung - necesită execuții ale procedurii existente fără invidie. $O(n^{3})$ $n!$
Aristotelismul cere ca, dacă doi agenți au măsuri identice de semnificație, ei vor primi aceeași valoare. Acest lucru este mai slab decât simetria și este satisfăcut de orice procedură fără invidie. Mai mult, procedurile aristotelice și proporționale sunt cunoscute pentru orice număr de agenți și necesită interogări. $O(n^{3})$

Consultați articolul „ Tăiere simetrică a prăjiturii ” pentru detalii și link-uri.

Diviziune eficientă a târgului

Pentru n persoane cu funcții de valoare aditivă, există întotdeauna o diviziune EPOS [13] .

Dacă tortul este un interval unidimensional și fiecare participant trebuie să obțină un interval conectat, atunci următorul rezultat general este valabil: dacă funcțiile de evaluare sunt strict monotone (fiecare participant preferă cu putere o piesă și nu oricare dintre propriile sale subseturi), atunci orice divizie OZ va fi, de asemenea, un EP [14] . Prin urmare, protocolul Simons în acest caz oferă diviziunea EPOS.

Dacă tortul este un cerc unidimensional (de exemplu, un interval în care două puncte finale sunt identificate topologic) și fiecare față trebuie să primească un arc conectat, atunci rezultatul anterior nu este corect - diviziunea OD nu va fi neapărat un EP. În plus, există perechi de funcții de estimare (neaditive) pentru care nu există partajare EPOS. Totuși, dacă există 2 agenți și cel puțin unul dintre ei are o funcție de evaluare aditivă, atunci divizia EPOS există [15] .

Dacă tortul este unidimensional, dar orice persoană poate obține un subset discontinuu al acestuia, diviziunea OD nu va fi neapărat EP. În acest caz, sunt necesari algoritmi mai complexi pentru a găsi EPOS-ul diviziei.

Dacă funcțiile de evaluare sunt aditive și constante pe bucăți, atunci există un algoritm care găsește diviziunea EPOS [16] . Dacă funcțiile de densitate estimatorului sunt aditive și Lipschitz-continue , atunci ele pot fi aproximate prin funcții constante pe bucăți „atât de aproape dorim”, astfel încât acest algoritm aproximează diviziunea EPOS „atât de aproape dorim” [16] .

Diviziunea OD nu este neapărat RP [17] [18] . Una dintre abordările pentru a face față acestei dificultăți este căutarea diviziunii cu valoarea maximă de utilitate între toate OC posibile ale OC. Această problemă a fost studiată pentru o prăjitură, care este un interval unidimensional, din care fiecare persoană poate obține părți discontinue, iar funcțiile de evaluare sunt aditive [19] .

Proceduri non-aditive

Majoritatea procedurilor de partajare echitabilă existente prezentate mai sus presupun utilitate suplimentară pentru jucători. Cu alte cuvinte, dacă un jucător câștigă o anumită utilitate din 25 g de prăjitură de ciocolată, atunci se presupune că va obține exact dublu utilitate de la 50 g din aceeași prăjitură de ciocolată.

În 2013, Rishi S. Mirchandani a arătat că majoritatea algoritmilor de diviziune corectă existenți sunt incompatibili cu funcțiile de utilitate non-aditive [20] . El a mai demonstrat că cazul special al problemei împărțirii echitabile, în care jucătorii au funcții de utilitate non-aditive, nu poate avea soluții proporționale.

Mirchandani a sugerat că problema împărțirii corecte ar putea fi rezolvată folosind tehnici de optimizare neliniară. Cu toate acestea, rămâne întrebarea dacă există algoritmi mai buni pentru anumite subseturi de funcții utilitare non-aditive.

Vezi și

Problema repartizării echitabile a obiectelor este o problemă similară, în care obiectele împărțirii sunt indivizibile.

Note

↑ 1 2 Steinhaus, 1948 , p. 101–4.
↑ Procaccia, 2016 .
↑ Drepturile omului nu sunt discutate aici, sarcina este să împărțiți tortul astfel încât fiecare persoană să primească o cotă echitabilă.
↑ Hill, Morrison, 2010 , p. 281.
↑ 1 2 Adesea tradus „diviziune fără invidie” (hârtie de calc din engleză), deși prezența invidiei este cea care joacă rolul principal în această împărțire.
↑ Adică, astfel încât lungimea și lățimea lui să fie apropiate.
↑ Segal-Halevi, Nitzan, Hassidim, Aumann, 2017 , p. 1–28.
↑ Chen, Lai, Parkes, Procaccia, 2013 , p. 284–297.
↑ 1 2 Dubins, Spanier, 1961 , p. 1–17.
↑ Calculatorul diviziei echitabile (downlink) . Consultat la 12 octombrie 2019. Arhivat din original la 28 februarie 2010. (nedefinit)
↑ Ivars Peterson. O ofertă corectă pentru colegii de casă . MathTrek (13 martie 2000). Consultat la 12 octombrie 2019. Arhivat din original la 20 septembrie 2012. (nedefinit)
↑ Aumann, Dombb, Hassidim, 2013 .
↑ Weller, 1985 , p. 5–17.
↑ Berliant, Thomson, Dunz, 1992 , p. 201.
↑ Thomson, 2006 , p. 501–521.
↑ 1 2 Reijnierse, Olari, 1998 , p. 291–311.
↑ Caragiannis, Kaklamanis, Kanellopoulos, Kyropoulou, 2011 , p. 589.
↑ Aumann, Dombb, 2010 , p. 26.
↑ Cohler, Lai, Parkes, Procaccia, 2011 .
↑ Mirchandani, 2013 , p. 78–91.

Literatură

Ariel Procaccia. Capitolul 13: Cake Cutting Algorithms // Manual de alegere socială computațională / Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. - Cambridge University Press, 2016. - ISBN 9781107060432 .
Hugo Steinhaus. Problema împărțirii echitabile // Econometrica. - 1948. - T. 16 , nr. 1 . — .
Hill TP, Morrison KE Cutting Cakes Carefully // The College Mathematics Journal. - 2010. - T. 41 , nr. 4 . doi : 10.4169 / 074683410x510272 .
Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, Yonatan Aumann. Târg și pătrat: Tăierea prăjiturii în două dimensiuni // Journal of Mathematical Economics. - 2017. - T. 70 . - doi : 10.1016/j.jmateco.2017.01.007 . - arXiv : 1409.4511 .
Yiling Chen, John K. Lai, David C. Parkes, Ariel D. Procaccia. Adevărul, dreptatea și tăierea prăjiturii // Jocuri și comportament economic. - 2013. - T. 77 , nr. 1 . - doi : 10.1016/j.geb.2012.10.009 .
Lester Dubins. Cum să tăiați o prăjitură în mod corect // The American Mathematical Monthly. - 1961. - T. 68 , nr. 1 . - doi : 10.2307/2311357 . — .
Yonatan Aumann, Yair Dombb, Avinatan Hassidim. Calcularea diviziilor de tort eficiente din punct de vedere social . — 2013.
Weller D. Împărțirea echitabilă a unui spațiu măsurabil // Journal of Mathematical Economics. - 1985. - T. 14 . - doi : 10.1016/0304-4068(85)90023-0 .
Berliant M., Thomson W., Dunz K. Despre împărțirea corectă a unei mărfuri eterogene // Journal of Mathematical Economics. - 1992. - T. 21 , nr. 3 . - doi : 10.1016/0304-4068(92)90001-n .
Thomson W. Copii care plâng la petrecerile de naștere. De ce? // Teoria economică. - 2006. - T. 31 , nr. 3 . - doi : 10.1007/s00199-006-0109-3 .
Reijnierse JH, Potters JAM Despre găsirea unei diviziuni Pareto optime fără invidie // Programare matematică. - 1998. - T. 83 , nr. 1–3 . - doi : 10.1007/bf02680564 .
Caragiannis I., Kaklamanis C., Kanellopoulos P., Kyropoulou M. The Efficiency of Fair Division // Teoria sistemelor de calcul. - 2011. - T. 50 , nr. 4 . - doi : 10.1007/s00224-011-9359-y .
Aumann Y., Dombb Y. The Efficiency of Fair Division with Connected Pieces // Internet și economie de rețea . - 2010. - T. 6484. - (Note de curs în Informatică). — ISBN 978-3-642-17571-8 . - doi : 10.1007/978-3-642-17572-5_3 . Este necesară înregistrarea pentru descărcare
Yuga Julian Cohler, John Kwang Lai, David C. Parkes, Ariel Procaccia. Tăiere optimă de tort fără invidie, conferință AAAI . — 2011.
Rishi Mirchandani. Superaditivitatea și subaditivitatea în Divizia Târgului // Journal of Mathematics Research. - 2013. - august ( vol. 5 , numărul 3 ). doi : 10.5539 / jmr.v5n3p78 .