Procedura de „divizare unică”.

Procedura de " divizare unică " este o procedură de tăiere proporţională a turtei . Procedura este concepută pentru a aloca o resursă divizibilă eterogenă, cum ar fi un tort de ziua de naștere, și implică n participanți la diviziune cu preferințe diferite pentru diferite părți ale tortului. Procedura permite ca n persoane să împartă tortul între ei, astfel încât fiecare participant să primească cel puțin valoarea totală conform propriei evaluări (subiective).

Procedura a fost dezvoltată de Hugo Steinhaus pentru n =3 persoane [1] . Mai târziu a fost extins de Harold Kuhn pentru n >3 folosind teorema Frobenius-Koenig [2] . Cazurile n =3 și n =4 sunt descrise în articolul lui Brahms și Taylor [3] , iar cazul general este descris în articolul lui Robertson și Webb [4] .

Descriere

Pentru comoditate, normalizăm scorurile participanților, astfel încât valoarea scorului întregului tort să fie n pentru toți participanții. Scopul este de a oferi fiecărui participant o valoare care este de cel puțin 1.

Pasul 1 . Un jucător este selectat aleatoriu, pe care îl vom numi împărțire , iar el împarte tortul în n bucăți, fiecare valorând în ochii lui exact 1.

Pasul 2 . Fiecare dintre ceilalți n -1 participanți evaluează cele n piese rezultate și raportează pe care dintre ele le consideră „acceptabile”, adică valorează cel puțin 1.

Acum, în funcție de răspunsuri, jocul trece la pasul 3. Vom prezenta cazul n = 3 și apoi cazul general.

Procedura Steinhaus pentru n =3

Sunt două cazuri.

• Cazul A: Cel puțin unul dintre non-divizori marchează două sau mai multe bucăți ca fiind acceptabile. Apoi, al treilea participant ia o piesă acceptabilă ( după principiul Dirichlet trebuie să existe cel puțin una), al doilea participant ia o piesă acceptabilă (a marcat două, deci rămâne cel puțin una), iar împărțitorul ia piesa rămasă (pentru separator toate piesele sunt acceptabile).
• Cazul B: Ceilalți ambii participanți au marcat fiecare o singură piesă acceptabilă. Apoi, există cel puțin o piesă care este acceptabilă numai pentru separator. Despărțitorul ia această bucată și se duce acasă. Această piesă valorează mai puțin de 1 pentru cei doi participanți rămași, așa că celelalte două piese valorează cel puțin 2 împreună pentru ei. Ei împart restul utilizând procedura „ Divide and Choose ”.

Procedura pentru orice n

Există mai multe moduri de a descrie cazul general. Cea mai scurtă descriere este dată în articolul lui Segal-Halevi și Aiger-Khorev [5] . Se bazează pe conceptul de potrivire fără invidie , o potrivire în care niciun agent care nu se potrivește nu este adiacent unei piese de potrivire.

Pasul 3 Construim un grafic bipartit în care fiecare vârf al lui X este un agent, iar fiecare vârf al lui Y este o bucată de tort, iar o muchie conectează agentul X și piesa Y dacă și numai dacă X evaluează Y la cel puțin 1.

Pasul 4 Găsim cardinalitatea maximă (după numărul de combinații) potrivire fără invidie în G . Rețineți că divizorul este conectat la toate n piese, deci (unde este mulțimea vecinilor lui X în Y ). Prin urmare, există o potrivire non-vid, fără invidie.

Pasul 5 Dăm fiecare piesă din pereche agentului corespunzător (adică din aceeași pereche din potrivire). Rețineți că fiecare astfel de agent își evaluează valoarea la cel puțin 1, astfel încât să poată merge fericit acasă.

Pasul 6 Împărțim recursiv tortul rămas în agenții rămași. Rețineți că fiecare dintre agenții rămași a estimat piesele date ca fiind mai mici de 1, deci estimarea turtei rămase nu este mai mică decât numărul de agenți și, prin urmare, precondiția pentru recursivitate este îndeplinită.

Vezi și

• Alte proceduri de rezolvare a aceleiași probleme pot fi găsite în articolul „ Problema de tăiere proporțională a prăjiturii ”.
• Unul dintre avantajele procedurii de „single divider” este că poate fi modificată pentru a obține o procedură simetrică de tăiere corectă a tortului .

Note

1. ↑ Steinhaus, 1948 , p. 101–4.
2. ↑ Kuhn, 1967 , p. 29–37.
3. ↑ Brams și Taylor 1996 , p. 31-35.
4. ↑ Robertson, Webb, 1998 , p. 83-87.
5. ↑ Segal-Halevi, Aigner-Horev, 2019 .

Literatură

• Steven J. Brams, Alan D. Taylor. Împărțirea echitabilă: de la tăierea prăjiturii până la soluționarea disputelor . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .
• Hugo Steinhaus. Problema împărțirii echitabile // Econometrica. - 1948. - T. 16 , nr. 1 . — .
• Harold Kuhn. Despre jocurile diviziei corecte // Eseuri în economie matematică în onoarea lui Oskar Morgenstern . — Princeton University Press, 1967. Arhivat la 16 ianuarie 2019 la Wayback Machine
• Erel Segal-Halevi, Elad Aigner-Horev. Potriviri fără invidie în grafice bipartite și aplicațiile lor la diviziunea echitabilă  . — 2019.
• Jack Robertson, William Webb. Algoritmi de tăiere a prăjiturii: fiți corect dacă puteți. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .