Distribuția invidioasă a obiectelor

Distribuția fără invidie a obiectelor (fără invidie, KB, engleză Envy-free , distribuție EF [1] ) este o problemă de distribuție corectă a obiectelor , în care criteriul justiției este absența invidiei în distribuția rezultată - fiecare agent trebuie să primească un set de obiecte, a căror valoare (după cum consideră) nu mai mică decât acțiunile primite de alți agenți [2] .

Deoarece obiectele sunt indivizibile, este posibil ca distribuția KB să nu existe. Cel mai simplu caz al unei astfel de împărțiri este un singur obiect, care ar trebui distribuit între cel puțin doi agenți: dacă un agent primește obiectul, al doilea îl va invidia. Astfel, procedurile de divizare presupun diferite tipuri de relaxare a cerinței de non- invidie .

Găsirea unei distribuții fără invidie dacă există

Preferințe de comandă pentru seturi: Fără gelozie

Procedura de tăiere găsește o distribuție KB completă pentru doi agenți dacă și numai dacă există o astfel de distribuție. Procedura cere agenților să clasifice seturi de obiecte, dar nu necesită informații de utilitate cantitativă . Algoritmul funcționează dacă preferințele agenților sunt strict monotone și nu este nevoie să presupunem că sunt preferințe adaptive . În cel mai rău caz, agenții pot avea un număr de seturi posibile, astfel încât timpul de rulare poatedepinde exponențial de numărul de obiecte.

Comandarea preferințelor pentru obiecte: notoriu/posibil fără invidie

De obicei, este mai ușor pentru oameni să comande obiecte individuale decât să comande seturi de obiecte. Să presupunem că toți agenții au preferințe adaptive , atunci este posibil să ridicăm ordonarea obiectelor la o ordonare parțială a mulțimilor. De exemplu, dacă obiectele sunt ordonate w>x>y>z, aceasta implică faptul că {w, x}>{y, z} și {w, y}>{x, z}, dar nu implică nicio preferință între { w, z} și {x, y}, între {x} și {y, z} și așa mai departe.

Având în vedere o ordonare a obiectelor:

Se știe că o distribuție este lipsită de invidie ( neapărat fără invidie , NEF) dacă nu este lipsită de invidie pentru toate ordonările de set adaptive în concordanță cu ordonarea obiectelor;
O distribuție este posibil fără invidie (posibil fără invidie , PEF) dacă nu este lipsită de invidie pentru cel puțin o ordonare adaptivă a seturilor în concordanță cu ordonarea obiectelor;
O distribuție este cu siguranță Pareto - optimală ( NPE) dacă este Pareto-optimă pentru toate ordonările adaptive de mulțime compatibile cu ordonarea obiectelor;
O distribuție este posibil Pareto-optimă (PPE) dacă este Pareto-optimă pentru cel puțin o ordonare adaptivă a mulțimii în concordanță cu ordonarea obiectului.

Bouvre, Endriss și Leng [3] au studiat problemele algoritmice ale găsirii unei distribuții ZBZ/WBZ cu o condiție suplimentară de eficiență, parțialitate, completitudine, COP sau COP. În general, cazul WBZ este mai simplu din punct de vedere computațional, în timp ce cazul ZBZ este mai dificil.

Există o distribuție KB

Distribuția goală este întotdeauna KB, dar dacă dorim să cerem eficiență în plus față de KB, soluția problemei devine dificilă din punct de vedere computațional [4] :

Decizia dacă există o distribuție KB completă este o problemă NP-completă . Acest lucru este adevărat chiar și atunci când există doar doi agenți și chiar și atunci când funcțiile de utilitate sunt aditive și identice , deoarece în acest caz căutarea unei distribuții KB este echivalentă cu rezolvarea problemei partiționării unui set de numere [5] .
Decizia dacă există o distribuție KB Pareto eficientă este mai dificilă decât NP - este completă chiar și cu funcții de preferință dihotomice [6] și chiar cu funcții de utilitate aditivă [7] . $\Sigma _{2}^{\textrm {P)}$

Distribuție de căutare cu un nivel limitat de invidie

Unele proceduri găsesc o distribuție care nu are invidie cu excepția unui singur obiect (BZ1) - pentru oricare doi agenți A și B, există un singur obiect, la eliminarea căruia din setul de agent B, agentul A nu îl va mai invidia pe agentul B [8] .

Procedura circulară

Dacă toți agenții au utilități slab aditive , următorul protocol (care este similar cu planificarea round robin ) oferă distribuția completă KB1:

Aranjați agenții într-un mod arbitrar.
Atâta timp cât există obiecte nealocate
- Permitem agenților cu numere de la 1 să aleagă un obiect. $n$

Dovada [9] : Pentru orice agent , împărțim alegerile făcute de agenți în subsecvențe — prima subsecvență începe cu agentul 1 și se termină cu agentul . Ultima subsecvență începe cu și se termină cu . În a doua secvență, agentul alege primul, deci alege cel mai bun obiect și, prin urmare, nu îl invidiază pe celălalt agent. Un agent nu poate invidia decât pe unul dintre agenți , iar orice invidie vine doar de la obiectul care a fost ales în prima subsecvență. Dacă acest obiect este îndepărtat, agentul nu va fi gelos.

i

i-1

i

i-1

i

i

1,...,i-1

i

Protocolul round robin necesită o aditivitate slabă , deoarece cere fiecărui agent să aleagă „cel mai bun obiect” fără a ști ce obiecte vor fi alese de el ulterior. Cu alte cuvinte, aceasta presupune că obiectele sunt bunuri independente .

Procedura Ciclului Invidiei

Procedura ciclurilor de invidie returnează distribuția completă BZ1 pentru relații de preferințe arbitrare. Singura cerință este capacitatea agenților de a-și ordona seturile de obiecte.

Dacă preferințele agenților sunt reprezentate de o funcție de utilitate cardinală , atunci garanția BZ1 are o interpretare suplimentară: nivelul numeric de invidie al fiecărui agent nu depășește utilitatea marginală maximă , adică utilitatea marginală maximă a unui obiect individual pentru acest agent.

Procedura P-CRRD aproximativă

Echilibrul competitiv aproximativ din venit egal ( A- CEEI ) returnează o distribuție parțială B31 pentru preferințe arbitrare. Singura cerință este ca agentul să poată comanda colecții de obiecte.

Un număr mic de obiecte pot rămâne nealocate. Distribuția este Pareto eficientă pentru obiectele distribuite. Mai mult, mecanismul P-CRRD este aproximativ invulnerabil strategic dacă numărul de agenți este mare.

Maximum Nash Wellbeing

Algoritmul Maximum - Nash-Welfare (MNW) alege distribuția completă care maximizează produsul utilităților. Este necesar ca fiecare agent să furnizeze o valoare numerică pentru fiecare obiect și presupune că utilitățile pentru agenți sunt aditive. Distribuția rezultată va fi, de asemenea, BZ1 și Pareto eficientă [9] .

Dacă preferințele agenților nu sunt aditive, soluția MNB nu este neapărat BZ1, dar dacă preferințele agenților sunt cel puțin submodulare , soluția MNB satisface o proprietate mai slabă numită distribuție marginală fără invidie cu excepția unui obiect. ( Marginal-Invidie-Freeness ) , MEF1).

BZ1 / BZd

Există un criteriu alternativ numit Fără invidie, cu excepția celui mai ieftin (BZd) pentru oricare doi agenți A și B. Dacă eliminăm orice obiect din setul de obiecte al agentului B, atunci A nu îl va invidia pe B. BZd este strict mai puternic decât BZ1. Dar, încă nu se știe dacă există întotdeauna distribuții BZd [9] .

Minimizarea relației de invidie

Având în vedere o distribuție a lui X , definiți raportul de invidie dintre i și j (EnvyRatio) ca:

EnvyRatio(X,i,j):=\max(1,{u_{i}(X_{j}) \over u_{i}(X_{i})})

deci raportul este 1 dacă i nu este gelos pe j și mai mare decât 1 dacă i este gelos pe j . Definim relația de invidie de distribuție ca:

EnvyRatio(X):=\max _{i,j}(EnvyRatio(X,i,j)

Problema de minimizare a raportului de invidie este problema găsirii distribuției X cu cel mai mic raport de invidie.

Estimări generale

Sub preferințe generale, orice algoritm determinist care calculează o distribuție cu un raport minim de invidie necesită un număr de interogări care, în cel mai rău caz, depinde exponențial de numărul de obiecte [5] .

Scoruri egale aditive

Cu scoruri de preferință aditive și identice [5] :

Următorul algoritm lacom găsește o distribuție al cărei raport de invidie este de cel mult 1,4 ori minim [10] ;
1. Aranjam obiectele in ordinea descrescatoare a valorii;
2. În timp ce există obiecte nealocate, dăm următorul obiect agentului cu valoarea totală minimă;
Există o schemă PTAS pentru minimizarea relației de invidie. Mai mult, dacă numărul de jucători este constant, există o schemă FPTAS .

Aditiv diverse estimări

Cu estimări de preferințe aditive și diferite [11]

Dacă numărul de agenți este inclus în datele de intrare, atunci în timp polinomial este imposibil să se obțină un coeficient de aproximare mai bun de 1,5. Cu excepția cazului în care P=NP.
Dacă numărul de agenți este constant, există o schemă FPTAS .
Dacă numărul de agenți este egal cu numărul de obiecte, există un algoritm de distribuție a timpului polinomial.

Caută distribuție parțială fără invidie

Procedura AL găsește distribuția KB pentru doi agenți. Poate elimina unele dintre obiecte, dar distribuția finală este Pareto eficientă, în sensul că nicio altă distribuție KB nu este mai bună pentru unul și puțin mai bună pentru cealaltă. Procedura AL necesită ordonarea după valoare a obiectelor separate doar de agenți. Procedura presupune că agenții au preferințe adaptive și oferă o distribuție despre care se știe că este fără invidie ( cu siguranță fără invidie, ZBZ).

Procedura „ ajustarea câștigătorului ” returnează KB de distribuție completă și eficientă pentru cei doi agenți, dar poate necesita tăierea unuia dintre obiecte (sau unul dintre obiecte rămâne în uz comun). Procedura cere fiecărui agent să raporteze o valoare de utilitate numerică pentru fiecare obiect și presupune că agenții au funcții de utilitate aditive .

Existența plasamentului fără invidie cu evaluări aleatorii

Dacă agenții au funcții de utilitate aditive , care sunt preluate din distribuțiile de probabilitate care îndeplinesc anumite criterii, iar numărul de obiecte este suficient de mare în raport cu numărul de agenți, atunci distribuția KB există cu probabilitate mare . În special [12]

Dacă numărul de obiecte este suficient de mare , atunci cu o probabilitate mare există distribuția KB (adică, probabilitatea tinde la 1 pe măsură ce m tinde spre infinit). $m=\Omega (n\log n)$
Dacă numărul de obiecte nu este suficient de mare, adică , atunci cu o probabilitate mare distribuția KB nu există. $m=n+o(n)$

Lipsa invidiei și alte criterii de justiție

Orice distribuție KB este corectă min-max . Aceasta rezultă direct din definițiile obișnuite și nu depinde de aditivitate.
Dacă agenții au funcții de utilitate aditive , atunci distribuția KB este, de asemenea, proporțională și max-min-just . În caz contrar, distribuția KB poate să nu fie proporțională și poate să nu fie nici măcar max-min-just.
Orice distribuție care are un echilibru competitiv cu venituri egale nu are invidie. Acest lucru este adevărat indiferent de aditivitate [8] .
Orice distribuție optimă Nash (distribuție care maximizează produsul utilităților) este un KB1 [9] .

Vezi articolul Problema unei distribuții corecte a obiectelor cu o descriere detaliată și referințe la literatură.

Tabel final

Următoarele notații sunt utilizate mai jos:

$n$ = numărul de agenți care participă la partajare;
$m$ = numărul de articole (obiecte) de distribuit;
BE = fără invidie, BE1 = fără invidie cu excluderea unui subiect (cerință mai slabă decât BE), BE1 = maxim fără invidie cu excluderea unui subiect (cerință mai slabă decât BE1).
EP = Pareto eficient (PE = în engleză Pareto-eficient ).

Nume	Numărul de participanți	Intrare	Preferințe	Numărul de cereri	Justiţie	Eficienţă	Comentarii
Tunderea	2	Seturi comandate	Strict monoton	$2^{m}$	BZ	Complet	Dacă și numai dacă există o distribuție KB completă
procedura AL	2	Obiecte ordonate	Puțin aditiv	$Poly(m)$	Evident-BZ	Parțial, dar distribuția nu este dominată în Pareto de un alt ZBZ
Câștigător ajustabil	2	Evaluarea obiectelor	Aditiv	$Poly(m)$	informat și imparțial	EP	Un obiect poate fi partajat
planificare circulară	$n$	Obiecte ordonate	Puțin aditiv	$m$	Evident-BZ1	Complet
Cicluri ale invidiei	$n$	Seturi comandate	monoton	$O(mn^{3})$	BZ1	Complet
mecanism P-CRRD	$n$	Seturi comandate	Orice	?	BZ1 și - maximizarea acțiunilor $(n+1)$	Parțial, dar ES în raport cu obiectele distribuite	Aproximativ strategic invulnerabil dacă sunt mulți agenți.
Bunăstare maximă Nash [9]	$n$	Evaluarea obiectelor	Aditiv	NP-hard (dar există în cazuri speciale de aproximare)	BZ1 si aproximativ -maximizarea actiunilor $n$	EP	Cu funcții de utilitate submodulare, distribuția este EF și PBZ1.

Vezi și

Maximizarea acțiunilor este un alt criteriu de corectitudine.

Note

↑ Literal - distribuția obiectelor fără invidie, care, în general, este confuză - doar invidia este factorul principal într-o astfel de distribuție.
↑ Brandt, Conitzer, Endriss et al., 2016 , p. 296–297.
↑ Bouveret, Endriss, Lang, 2010 , p. 387–392.
↑ Brandt, Conitzer, Endriss et al., 2016 , p. 300–310.
↑ 1 2 3 Lipton, Markakis, Mossel, Saberi, 2004 , p. 125.
↑ Bouveret, Lang, 2008 , p. 525–564.
↑ De Keijzer, Bouveret, Klos, Zhang, 2009 , p. 98.
↑ 1 2 Budish, 2011 , p. 1061–1103.
↑ 1 2 3 4 5 Caragiannis, Kurokawa et al., 2016 , p. 305.
↑ Graham, 1969 , p. 416–429.
↑ Nguyen, Rothe, 2014 , p. 54–68.
↑ Dickerson, Goldman et al., 2014 , p. 1405–1411.

Literatură

Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Manual de alegere socială computațională . - Cambridge University Press, 2016. - ISBN 9781107060432 .
Sylvain Bouveret, Ulle Endriss, Jérôme Lang. Divizarea echitabilă în cadrul preferințelor ordinale: Calcularea alocărilor fără invidie a bunurilor indivizibile // ECAI 2010. - 2010. - pp. 387–392.
Bouveret S., Lang J. Eficiența și lipsa de invidie în diviziunea echitabilă a bunurilor indivizibile: reprezentare logică și complexitate // JAIR. - 2008. - T. 32 . - doi : 10.1613/jair.2467 .
Bart De Keijzer, Sylvain Bouveret, Tomas Klos, Yingqian Zhang. Despre complexitatea eficienței și lipsei de invidie în împărțirea corectă a bunurilor indivizibile cu preferințe aditive // Teoria deciziei algoritmice. - 2009. - T. 5783. - (Note de curs în Informatică). - ISBN 978-3-642-04427-4 . - doi : 10.1007/978-3-642-04428-1_9 .
Eric budist. Problema de atribuire combinatorie: echilibru competitiv aproximativ din venituri egale // Journal of Political Economy. - 2011. - T. 119 , nr. 6 . - doi : 10.1086/664613 .
Ioannis Caragiannis, David Kurokawa, Herve Moulin, Ariel D. Procaccia, Nisarg Shah, Junxing Wang. The Unreasonable Fairness of Maximum Nash Welfare // Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16 . - 2016. - S. 305. - ISBN 9781450339360 . - doi : 10.1145/2940716.2940726 .
Lipton RJ, Markakis E., Mossel E., Saberi A. Despre alocări aproximativ echitabile de bunuri indivizibile // Proceedings of the 5th ACM Conference on Electronic commerce - EC '04. - 2004. - ISBN 1-58113-771-0 . doi : 10.1145 / 988772.988792 .
Graham RL Bounds on Multiprocessing Timing Anomalies // SIAM Journal on Applied Mathematics. - 1969. - T. 17 , nr. 2 . - doi : 10.1137/0117039 .
Trung Thanh Nguyen, Jörg Rothe. Minimizarea invidiei și maximizarea bunăstării sociale medii Nash în alocarea bunurilor indivizibile // Matematică aplicată discretă. - 2014. - T. 179 . - doi : 10.1016/j.dam.2014.09.010 .
John P. Dickerson, Jonathan Goldman, Jeremy Karp, Ariel D. Procaccia, Tuomas Sandholm. The Computational Rise and Fall of Fairness // În Proceedings of the Twenty-8th AAAI Conference on Artificial Intelligence (2014). — 2014. Legătura ACM