Prețul justiției

Prețul echității ( ing. Price of fairness , POF) în problemele unei împărțiri echitabile este raportul dintre beneficiul economic maxim obținut după împărțire și beneficiul economic maxim obținut în condiția unei împărțiri corecte . POF este o măsură cantitativă a pierderii unui bun pe care societatea trebuie să-l plătească pentru a garanta corectitudinea.

În general, POF este definit prin următoarea formulă:

POF={\frac {\max _{D\in Divisions}{(bunăstare(D))))}{\max _{D\in FairDivisions}{(bunăstare (D))))))

Aici bunăstare (D) = beneficiu sub diviziunea D, Diviziuni = set de toate diviziile, FairDivisions = set de diviziuni echitabile.

Prețul exact variază foarte mult în funcție de tipul de diviziune, de tipul de capital și de tipul de bun public pe care îl luăm în considerare.

Cel mai studiat tip de bun social este bunul social utilitar , definit ca suma utilităților (normalizate) ale tuturor agenților. Un alt tip este bunul public egalitar , definit ca utilitatea minimă (normalizată) per agent.

Exemplu numeric

În acest exemplu, ne concentrăm pe prețul utilitar al proporționalității ( UPOP) .

Luați în considerare o proprietate de teren eterogenă care trebuie împărțită între 100 de participanți, fiecare dintre aceștia evaluând întregul teren la 100 de unități (sau o valoare normalizată la 100). Luați în considerare mai întâi câteva cazuri extreme.

Bunul utilitar maxim posibil este de 10 000. Această valoare este realizabilă doar în cazuri extrem de rare când toți participanții doresc să primească diferite loturi de teren.
În partajarea proporțională, fiecare participant primește o valoare de cel puțin 1, deci bunul de utilitate nu va fi mai mic de 100.

Limită superioară

Cazurile extreme descrise mai sus dau deja o margine superioară banală: . Cu toate acestea, putem da o limită superioară mai precisă. $UPOP\leqslant 10000/100=100$

Să presupunem că avem o împărțire eficientă a proprietății terenului în 100 de participanți cu un bun utilitar U . Vrem să o transformăm într-o împărțire proporțională. Pentru a face acest lucru, grupăm participanții în funcție de valorile lor actuale:

Participanții a căror valoare actuală este de cel puțin 10 vor fi numiți norocoși .
Restul participanților vor fi numiți perdanți .

Există două cazuri:

Dacă există mai puțin de 10 norocoși, pur și simplu aruncăm diviziunea existentă și efectuăm o nouă împărțire proporțională (de exemplu, folosind protocolul „ultimul care trebuie redus” ). Într-o împărțire proporțională, fiecare participant primește o valoare care este de cel puțin 1, deci valoarea totală este de cel puțin 100. Valoarea împărțirii inițiale a fost mai mică decât (10*100+90*10)=1900, deci UPOP nu depășește 19.
Dacă există cel puțin 10 norocoși, atunci creăm o împărțire proporțională conform următoarei variante a protocolului „ultimul care se reduce” :
- Fiecare norocos alocă 0,1 din cota sa și permite unuia dintre învinși să ia această parte alocată.
- Aceasta continuă până când fiecare dintre cei 90 de perdanți (dar nu mai mult de) și-a primit acțiunile. Acum fiecare dintre cei (cel puțin) 10 norocoși are cel puțin 0,1 din valoarea lor inițială, iar fiecare dintre învinși are cel puțin valoarea anterioară, deci UPOP nu depășește 10.

În concluzie, UPOP este întotdeauna mai mic de 20, indiferent de măsurile de rating ale participanților.

Limită inferioară

UPOP poate fi egal cu 1. De exemplu, dacă toți participanții au aceleași măsuri de evaluare, atunci pentru orice diviziune, indiferent de conceptul de justiție, bunul utilitar va fi egal cu 100 și, prin urmare, UPOP=100/100=1.

Suntem, totuși, interesați de cel mai rău caz de UPOP, de exemplu, o combinație de măsuri de măsură în care UPOP este mare. Mai jos este un exemplu de astfel de caz.

Imaginați-vă că există două tipuri de parteneri:

90 de parteneri indiferenți pentru care valoarea întregului teren este uniformă (de exemplu, când valoarea unei bucăți de teren este proporțională cu dimensiunea acestuia).
10 parteneri vizați , fiecare dintre care evaluează doar o bucată de teren, adică 0,1 din întregul teren.

Luați în considerare următoarele două partiții:

Împărțire corectă : Împărțiți terenul în mod egal, oferind fiecărui participant 0,01 din teren, iar partenerii vizați primesc 0,01 din terenul dorit. Împărțirea este corectă, valoarea pentru fiecare participant indiferent este 1, în timp ce valoarea fiecărui participant vizat este 10, deci bunul de utilitate este 190.
Împărțire eficientă : Împărțiți întregul teren între participanții vizați, oferindu-le fiecăruia întreaga suprafață dorită. Bunul utilitar este 100*10=1000.

În acest exemplu, UPOP este . Astfel, 5.26 este o limită inferioară a UPOP din cel mai rău caz (unde „cel mai rău caz” este ales dintre toate combinațiile posibile de măsuri de evaluare). ${\tfrac {1000}{190}}\cong 5,26$

Combinând

Combinând toate aceste rezultate, obținem că în cel mai rău caz UPOP este între 5 și 20.

Acest exemplu este tipic pentru argumentele limită POF. Pentru a demonstra limita inferioară, este suficient să dam un singur exemplu, iar pentru a demonstra limita superioară, este necesar să propunem un algoritm sau alt argument sofisticat.

Croiala corectă cu piese generice

Prețul de utilitate al proporționalității

Exemplul numeric descris mai sus poate fi generalizat de la 100 la n participanți, dând următoarele limite UPOP pentru cel mai rău caz:

{\tfrac {\sqrt {n}}{2}}\leqslant UPOP\leqslant 2{\sqrt {n}}-1

UPOP=\Theta ({\sqrt {n))}

Pentru doi participanți, calcule mai detaliate dau o limită [1] . $8-4{\sqrt {3}}\cong 1,07$

Prețul de utilitate al invidiei

Când întregul tort este împărțit, tăierea fără invidie este întotdeauna proporțională. Prin urmare, limita inferioară din cel mai rău caz se aplică și aici. Pe de altă parte, de sus avem doar o limită slabă [1] . Prin urmare, $UPOP({\tfrac {\sqrt {n}}{2}})$ $n-{\tfrac {1}{2)}$

{\tfrac {\sqrt {n}}{2}}\leqslant UPOV\leqslant n-{\tfrac {1}{2}}

\Omega ({\sqrt {n)})\leqslant UPOV\leqslant O(n)

Aici UPOV înseamnă engleză. Prețul utilitar al invidiei , adică prețul utilitar al invidiei.

Pentru doi participanți, calcule mai atente dau o limită [1] . $8-4{\sqrt {3}}\cong 1,07$

Prețul de utilitate al imparțialității

{\tfrac {(n+1)^{2}}{4n}}\leqslant UPOQ\leqslant n

UPOQ=\Theta (n)

Aici UPOQ înseamnă engleză. Prețul utilitar al eQuitității , adică prețul utilitar al imparțialității.

Pentru doi participanți, calcule mai atente oferă o limită de 9/8=1,125 [1] .

Scopul obiectelor indivizibile

Pentru obiectele indivizibile, o distribuție care să satisfacă proporționalitatea, lipsa de invidie sau imparțialitatea nu există întotdeauna (ca exemplu simplu, imaginați-vă doi participanți la diviziune care încearcă să împartă un obiect valoros indivizibil). Prin urmare, la calcularea prețului justiției, nu luăm în considerare cazurile în care nicio împărțire nu satisface conceptul ales de justiție. Scurt rezumat al rezultatelor [1] :

UPOP=n-1+{\tfrac {1}{n)}

, pentru două persoane: 3/2.

(3n+7)/9-O({\tfrac {1}{/}}{n})\leqslant UPOV\leqslant n-{\tfrac {1}{2}}

, pentru două persoane: 3/2

UPOQ=\infty

, pentru două persoane: 2

Împărțirea treburilor divizibile

Pentru problema împărțirii prăjiturii, când „tortul” este nedorit (de exemplu, tunderea gazonului), avem următoarele rezultate [1] :

(n+1)^{\tfrac {2}{4n}}\leqslant UPOP\leqslant n

, pentru două persoane: 9/8

(n+1)^{\tfrac {2}{4n}}\leqslant UPOV\leqslant \infty

, pentru două persoane: 9/8

UPOQ=n

Atribuirea treburilor indivizibile

UPOP=n

UPOV=\infty

UPOQ=\infty

Tăierea prăjiturii în bucăți conectate

Problema tăierii corecte a prăjiturii are variații, atunci când piesele selectate trebuie conectate (singure, nu constau din părți separate). În acest caz, atât numărătorul, cât și numitorul din formula POF sunt mai mici (din cauza luării maximului pe un set mai mic), așa că nu este clar a priori dacă POF va fi mai mic sau mai mare decât în cazul deconectat.

Prețul de utilitate al justiției

Exista urmatoarele rezultate privind bunul utilitar [2] :

UPOP=\Theta ({\sqrt {n))}

UPOV=\Theta ({\sqrt {n))}

n-1+{\tfrac {1}{n}}\leqslant EPOQ\leqslant n

EPOQ=\Theta (''n'')

Prețul egalitar al justiției

Cu împărțirea proporțională , valoarea pentru fiecare participant nu este mai mică de 1/ n din totalul resurselor estimate. În special, valoarea pentru agentul cel mai puțin fericit (care se numește binele egalitar al împărtășirii) este de cel puțin 1/ n . Aceasta înseamnă că într-o diviziune optimă egalitară, bunul egalitar este cel puțin 1/ n și, prin urmare, diviziunea optimă egalitară este întotdeauna proporțională. Prin urmare, prețul egalitar al proporționalității ( EPOP ) este egal cu 1:

EPOP=1

Argumente similare se aplică prețului egalitar al echității ( EPOQ ):

EPOQ=1

Costul egalitar al neinvidiei este mult mai mare [2] :

EPOV={\tfrac {n}{2)}

Acesta este un rezultat interesant, deoarece de aici rezultă că criteriul obligatoriu al absenței invidiei crește prăpastia socială și dăunează majorității locuitorilor nefericiți. Criteriul proporționalității este mult mai puțin nociv.

Prețul maximizării unui bun

În loc să calculăm pierderea de bun pentru a asigura corectitudinea, putem calcula pierderea de corectitudine atunci când optimizăm bunul. Obținem următoarele rezultate [2] :

prețul proporționalității prin egalitarism = 1 costul nu invidiei conform egalitarismului = n -1 preţul proporţionalităţii după utilitate

=\infty

preţul lipsei de invidie pentru utilitate

=\infty

Atribuirea obiectelor indivizibile la părțile conectate

Ca și în cazul tăierii tortului pentru a atribui obiecte indivizibile, există variații în care obiectele se află pe o linie și fiecare piesă de selectat trebuie să fie un segment de linie. Scurt rezumat al rezultatelor [3] :

UPOP=n-1+{\tfrac {1}{n)}

UPOV=\Theta ({\sqrt {n))}

UPOQ=\infty

; pentru două persoane: 3/2

EPOP=1

EPOV={\tfrac {n}{2)}

EPOQ=\infty

; pentru două persoane: 1

Repartizarea taxelor cu piese conexe

Scurt rezumat al rezultatelor [4] :

{\tfrac {n}{2}}\leqslant UPOP\leqslant n

UPOV=\infty

UPOQ=n

EPOP=1

EPOV=\infty

EPOQ=1

Alte rezultate

Costul capitalului propriu a fost studiat și în contextul alocării resurselor [5] [6] .

Vezi și

Note

↑ 1 2 3 4 5 6 Caragiannis, Kaklamanis et al., 2011 , p. 589.
↑ 1 2 3 Aumann, Dombb, 2010 , p. 26.
↑ Suksompong, 2019 , p. 227–236.
↑ Heydrich, van Stee, 2015 , p. 51–61.
↑ Bertsimas, Farias, Trichakis, 2011 , p. 17–31.
↑ Bertsimas, Farias, Trichakis, 2012 , p. 2234.

Literatură

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. Internet și economia rețelelor . - 2010. - T. 6484. - (Note de curs în Informatică). — ISBN 978-3-642-17571-8 . - doi : 10.1007/978-3-642-17572-5_3 .
Suksompong W. Fairly Allocating Contiguous Blocks of Indivisible Items // Matematică aplicată discretă. - 2019. - T. 260 . - doi : 10.1016/j.dam.2019.01.036 . - arXiv : 1707.00345 .
Heydrich S., van Stee R. Dividing Connected Chores Fairly // Informatică teoretică. - 2015. - T. 593 . - doi : 10.1016/j.tcs.2015.05.041 .
Bertsimas D., Farias VF, Trichakis N. The Price of Fairness // Operations Research. - 2011. - T. 59 . doi : 10.1287 / opre.1100.0865 .
Bertsimas D., Farias VF, Trichakis N. On the Efficiency-Fairness Trade-off // Management Science. - 2012. - T. 58 , nr. 12 . - doi : 10.1287/mnsc.1120.1549 .