Problema tăierii corecte a plăcintei

Problema tăierii echitabile a plăcintei este o variantă a problemei împărțirii echitabile a prăjiturii în care elementul care trebuie împărțit este un cerc .

Ca exemplu, luați în considerare un tort de ziua de naștere sub formă de cerc . Tortul trebuie împărțit între mai mulți copii în așa fel încât niciunul să nu fie gelos pe celălalt (ca în problema standard a împărțirii prăjiturii). O condiție suplimentară este ca tăieturile să fie radiale astfel încât fiecare copil să primească un sector de cerc . Termenul „tort” este doar o metaforă pentru o procedură de tăiere a tortului care poate fi folosită pentru a partaja diferite tipuri de resurse. De exemplu: proprietatea terenului, spațiul publicitar sau timpul de difuzare.

Sarcina de a tăia tortul a fost propusă de Hugo Steinhaus după al Doilea Război Mondial . De atunci, a rămas subiectul unui studiu intens în matematică, informatică, economie și științe politice.

Modelul de plăcintă de divizare poate fi aplicat pentru a împărți linia de coastă a unei insule în secțiuni adiacente. O altă aplicație posibilă este împărțirea timpului periodic - împărțirea ciclului zilnic în perioade de „serviciu”.

Model

Placinta este de obicei modelată ca un interval unidimensional [0,2π] (sau [0,1]) în care sunt identificate cele două puncte finale.

Acest model a fost propus în 1985 și mai târziu în 1993 [1] [2] .

Orice procedură de împărțire corectă a prăjiturii poate fi aplicată la tăierea plăcintei, ignorând faptul că cele două puncte finale pot fi identificate. De exemplu, dacă Alice obține [0,1/3] și George obține [1/3,1] ca urmare a procedurii de tăiere a tortului, atunci îi vom da lui Alice un sector circular de 120 de grade , în timp ce George va obține restul de 240 de grade. sector.

Tăierea plăcintei devine mai interesantă atunci când luăm în considerare problemele de eficiență , deoarece sunt posibile mai multe tăieturi la împărțirea plăcintei.

Doi parteneri

Împărțire fără invidie

O diviziune se numește diviziune fără invidie ( EF ) dacă fiecare partener crede că piesa lui este cel puțin la același preț ca toți ceilalți.

Împărțirea plăcintei din PO se poate face folosind procedura de împărțire și alegere - un partener taie plăcinta în două sectoare pe care le consideră egale, iar celălalt partener alege sectorul pe care îl consideră cel mai bun. Dar pentru o plăcintă, poate exista o împărțire mai bună.

Diviziunea fără invidie și Pareto eficientă

Împărțirea se numește Pareto eficient (EP, în engleză Pareto eficient , PE) dacă nicio altă diviziune a plăcintei nu este cea mai bună pentru un partener și cea mai proastă pentru celălalt. Adesea , eficiența Pareto este determinată numai pentru submulțimile tuturor diviziunilor posibile. Și anume doar pentru tăierea în două sectoare continue (tăiere cu un număr minim de tăieturi).

Divizia se numește EPOS dacă este atât EP, cât și OZ.

Dacă scorurile partenerilor sunt măsuri ( aditive ), următoarea procedură „Moving Knife” garantează o împărțire care este OC și EP atunci când este împărțită în sectoare învecinate [3] .

Un partener (Rotator) ține peste plăcintă două cuțite radiale în așa fel încât din punctul său de vedere, cele două sectoare definite de aceste cuțite au aceeași valoare. El rotește aceste cuțite continuu tot timpul, păstrând același număr de sectoare, până când cuțitele ajung în poziția de pornire.

Celălalt partener (Alegetorul) observă acest proces pe tot parcursul ciclului. Apoi, pe ciclul următor, determină poziția la care, din punctul său de vedere, se obține valoarea maximă pentru unul dintre cele două sectoare. Alegătorul primește acest sector, iar Rotatorul primește sectorul rămas.

Această diviziune este evident EP, deoarece Rotatorului nu îi pasă ce cadrane alege Selectorul. Acesta este EP, deoarece nu există nicio diviziune care să ofere Selectorului o valoare mai mare și să lase o valoare de 1/2 pentru Rotire.

Restricții de aditivitate

Procedura de mai sus funcționează numai dacă funcția de valoare a Rotirii este aditivă , astfel încât părțile egale au întotdeauna aceeași valoare 1/2. Dacă nu este aditivă, atunci diviziunea ar rămâne fără invidie, dar nu neapărat eficientă Pareto .

Mai mult, dacă scorurile ambilor jucători sunt non-aditive (astfel încât niciunul dintre ei nu poate acționa ca Rotator), divizarea EPOS nu există întotdeauna [4] .

Împărțirea consecventă și împărțirea proporțională ponderată

Împărțirea se numește exactă (sau consistentă ) dacă valoarea piesei este exact egală în funcție de toți partenerii, unde sunt greutăți predefinite. $i$ $w_{i}$ $w_{i}$

Să presupunem că suma tuturor greutăților este egală cu 1, iar valoarea plăcintei pentru toți agenții este, de asemenea, normalizată la 1. Conform teoremei Stromquist-Woodall , pentru orice greutate există o submulțime , care este uniunea dintre sectoarele maxime , a căror valoare toți partenerii o estimează exact la . În cazul agenților, rezultă că există întotdeauna o împărțire consecventă a plăcintei cu sectoarele conectate, unde agentului 1 îi este dat un sector care costă exact pentru ambii agenți, iar agentului 2 i se oferă sectorul rămas care costă pentru ambii agenți ( vezi articolul lui Brahms, Jos și Klumler [5] pentru o demonstrație alternativă). $w\in [0,1]$ $C_{w}$ $n-1$ $w$ $n=2$ $w_{1}$ $1-w_{1}=w_{2)$

Acest lucru poate fi generalizat la orice număr de agenți - fiecare piesă, cu excepția ultimei, necesită cel mult tăieturi, deci numărul total de tăieturi necesare este de . $2(n-1)$ $2(n-1)^{2)$

Se spune că o împărțire este proporțională dacă fiecare dintre cei doi parteneri primește o valoare de cel puțin 1/2. Împărțirea se numește diviziune proporțională ponderată ( WPR ) dacă partenerul primește o valoare de cel puțin , unde este o pondere predefinită reprezentând diferitele părți ale partenerilor din tort. Procedura descrisă mai sus arată că în plăcintă, împărțirea VPD-ului cu piesele conectate există întotdeauna. Acest lucru contrastează cu un tort (interval) necircular, în care o diviziune proporțională ponderată (WPR, ing. Diviziune proporțională ponderată , WPR) cu părțile conectate poate să nu existe. $i$ $w_{i}$ $w_{i}$

Împărțire ponderată fără infracțiune

Dacă evaluările partenerilor sunt absolut continue unul față de celălalt, atunci există o divizie VPD care este și OMS (ponderat în absența invidiei, ing. ponderat-fără invidie , WEF) și Pareto eficient (EP, ing . . Pareto eficient , PE), iar raportul dintre valorile partenerului este exact w 1 / w 2 [5] .

Dovada . Pentru orice unghi t , fie unghiul la care raportul . $YT)$ ${\tfrac {v_{1}(t,y(t))}{v_{2}(t,y(t))))={\tfrac {w_{1}}{w_{2} }}$

Funcția este continuă în t și atinge maximul la unele . Tăiem plăcinta cu tăieturi radiale în puncte și , dăm o bucată partenerului nr. 1 și un adaos la partenerul și principalul nr. 2. Împărțirea este OMS, deoarece valoarea fiecărui partener este exact egală cu estimarea sa. Este, de asemenea, EP, deoarece cota partenerului #1 este maximizată, deci nu există nicio modalitate de a oferi mai mult partenerului #2 fără a pierde partenerul #1. $v_{1}([t,y(t)])$ $t^{\ast )$ $t^{\ast )$ $y(t^{\ast })$ $[t^{\ast },y(t^{\ast })]$

Împărțire echitabilă

O diviziune imparțială este o diviziune în care valoarea subiectivă a ambilor parteneri este aceeași (adică, fiecare partener este mulțumit în mod egal).

Există întotdeauna o împărțire a plăcintei pentru doi parteneri care este atât lipsită de invidie, cât și imparțială. Cu toate acestea, în prezent nu se cunoaște nicio procedură pentru găsirea unei astfel de separări [3] .

Dacă valorile măsurilor partenerilor sunt absolut continue unul față de celălalt (adică orice piesă care are o valoare pozitivă pentru un partener are și o valoare pozitivă pentru celălalt partener), atunci există o piesă fără invidie. partiţionare care este, de asemenea, imparţială şi Pareto eficientă . Din nou, nu se cunoaște nicio procedură pentru o astfel de împărțire [3] .

Împărțirea corectă

Se spune că o regulă de împărțire este corectă dacă afișarea funcțiilor de valoare adevărată este o strategie slab dominantă în această regulă. Adică, nu este posibil să se obțină vreo valoare prin denaturarea valorilor.

Se spune că o regulă de divizare este dictatorială dacă dă întregul tort unui singur partener predeterminat.

Regula diviziunii PE este corectă dacă și numai dacă este dictatorială [4] .

Trei sau mai mulți parteneri

Împărțire fără invidie pentru 3 parteneri

Procedura Stromquist Moving Knife poate fi folosită pentru a tăia la dimensiunea 1, deci evident că poate fi folosită pentru a tăia o plăcintă.

Dar există un algoritm mai simplu care profită de forma rotundă a plăcintei [6] [3] .

Partenerul A rotește continuu trei cuțite radiale în jurul plăcintei, asigurându-se că sectoarele au (după estimarea sa) 1/3-1/3-1/3 în dimensiune.

Partenerul B evaluează valoarea acestor trei cadrane. De obicei, toate au valori diferite, dar la un moment dat cele două sectoare vor avea aceeași valoare. Acest lucru se datorează faptului că, după o rotație de 120 de grade , cadranul anterior cel mai important va fi acum de mai puțină importanță, iar celălalt cadran va fi acum cel mai semnificativ. Prin urmare, după teorema valorii intermediare , trebuie să existe o poziție rotativă atunci când utilizatorul B vede două sectoare identice. În acest moment, partenerul B spune „stop”.

Partenerii aleg apoi sectoare în ordinea C - B - A. Partenerul C, desigur, nu simte nicio gelozie, deoarece alege primul. Partenerul B are cel puțin un sector mai mare din care să aleagă, iar partenerul A consideră că toate piesele au aceeași valoare.

Versiuni fără invidie și eficiente Pareto ale diviziunii

Pentru 3 parteneri, există o plăcintă și măsuri corespunzătoare pentru care nicio reducere nu va fi EPOS [7] .

Acest lucru este valabil și pentru mai mult de 3 parteneri. Acest lucru este adevărat chiar dacă toate funcțiile de valoare sunt aditive și strict pozitive (adică orice partener valorează orice bucată din plăcintă) [3] .

Ambele exemple folosesc măsuri care sunt aproape identice, dar cu un rafinament foarte subtil. Deoarece măsurile sunt aproape uniforme, este ușor să găsești tăieturi de plăcinte aproape fără invidie și aproape nedominate. Nu se știe dacă este posibil să găsim exemple în care dezacordurile sunt mult mai mari.

Împărțire proporțională cu cote diferite

Când există 3 sau mai mulți parteneri cu acțiuni diferite, este necesară o divizare proporțională ponderată (WPA). Diviziunea VPD cu piese conectate nu există întotdeauna [5] .

Acest lucru este analog cu imposibilitatea pentru un tort cu interval 1-dimensional și 2 parteneri (a se vedea secțiunea Diviziune proporțională ponderată a articolului The Fair Cake Cutting Problem ).

Note

↑ Stromquist, Woodall, 1985 , p. 241–248.
↑ Gale, 2009 , p. 48–52.
↑ 1 2 3 4 5 Barbanel, Brams, Stromquist, 2009 , p. 496.
↑ 12 Thomson , 2006 , p. 501–521.
↑ 1 2 3 Brams, Jones, Klamler, 2007 , p. 353.
↑ Brams, Taylor, Zwicker, 1997 , p. 547–554.
↑ Stromquist, 2007 .

Literatură

Stromquist W., Woodall DR Seturi asupra cărora sunt de acord mai multe măsuri // Journal of Mathematical Analysis and Applications. - 1985. - T. 108 . - doi : 10.1016/0022-247x(85)90021-6 .
Gale D. Mathematical entertainments // The Mathematical Intelligencer. - 2009. - T. 15 . - doi : 10.1007/BF03025257 .
Barbanel JB, Brams SJ, Stromquist W. Cutting a Pie is Not a Piece of Cake // American Mathematical Monthly. - 2009. - T. 116 , nr. 6 . - doi : 10.4169/193009709X470407 .
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 .
Brams SJ, Jones MA, Klamler C. Proportional pie-cutting // International Journal of Game Theory. - 2007. - T. 36 , nr. 3–4 . - doi : 10.1007/s00182-007-0108-z .
Steven J. Brams, Alan D. Taylor, William S. Zwicker. O soluție de cuțit în mișcare pentru divizia de prăjituri fără invidie pentru patru persoane // Proceedings of the American Mathematical Society. - 1997. - T. 125 , nr. 2 . - doi : 10.1090/s0002-9939-97-03614-9 .
Walter Stromquist. O plăcintă care nu poate fi tăiată corect // Dagstuhl Seminar Proceedings 07261 . — 2007.