Maximizarea distribuirii

Maximizarea cotelor (MMD, ing.  Maximin share , MMS) este un criteriu pentru o distribuție corectă a obiectelor . Având în vedere un set de obiecte cu valori diferite, 1-out-n maximin-share înseamnă cea mai mare valoare care poate fi obținută prin împărțirea obiectelor în n părți și alegerea părții cu valoarea minimă.

Distribuția obiectelor între n agenți cu scoruri diferite se numește MMD-echitabil dacă fiecare agent obține un set care este cel puțin la fel de bun ca cota sa de 1 din n maximin. MDM-justice a fost propus de Eric Budisch [1] ca o slăbire a criteriului de proporționalitate — fiecare agent primește un set cu o valoare nu mai mică decât distribuția egală (1/ n din fiecare resursă). Proporționalitatepoate fi garantat dacă obiectele sunt divizibile, dar nu și dacă sunt indivizibile, chiar dacă toți agenții au estimări identice. În schimb, corectitudinea MMD poate fi întotdeauna garantată pentru agenți identici, deci aceasta este o alternativă naturală la proporționalitate, chiar dacă agenții sunt diferiți.

Motive și exemple

Aceleași obiecte. Să presupunem mai întâi că m obiecte identice ar trebui să fie distribuite corect între n oameni. În mod ideal, fiecare persoană ar trebui să primească m / n obiecte, dar se poate dovedi că dacă m nu este divizibil cu n , acest lucru este imposibil, deoarece obiectele sunt indivizibile. Un criteriu natural de al doilea nivel este de a rotunji m / n în jos la cel mai apropiat număr întreg și de a oferi fiecărei persoane cel puțin obiecte de la etaj ( m / n ). Obținerea mai puțin de obiecte de podea( m / n ) ar fi „prea nedreaptă” - această nedreptate nu mai poate fi acoperită de indivizibilitatea obiectelor.

Obiecte distinse. Acum să presupunem că obiectele sunt distincte și fiecare are o valoare diferită. Acum rotunjirea în jos la cel mai apropiat număr întreg poate să nu dea soluția dorită. De exemplu, să presupunem n = 3 și m = 5 și valoarea obiectelor este 1, 3, 5, 6, 9. Suma valorilor este 24 și acest număr este divizibil cu 3, așa că în mod ideal ați da fiecare participant un articol, evaluat cel puțin 8, dar asta nu este posibil. Cea mai mare valoare pe care o putem garanta tuturor agenților este 7, care rezultă din distribuția {1,6},{3,5},{9}.

Setul {1,6} la care se atinge valoarea maximinului se numește „1-out-3 maximin-parts” - acesta este cel mai bun subset de obiecte care poate fi creat prin împărțirea setului original în 3 părți și alegând set cel mai puțin semnificativ. Prin urmare, în acest exemplu, distribuția este corectă MMD dacă și numai dacă valoarea pe care o primește fiecare agent este de cel puțin 7.

Evaluări variate. Să presupunem acum că fiecare agent evaluează fiecare obiect diferit , de exemplu

Acum fiecare agent are un set diferit de MMD-uri:

Aici, distribuția este MMD-just dacă îi dă lui Alice o valoare de cel puțin 7, George cel puțin 8 și Dina o valoare de cel puțin 3. De exemplu, o distribuție în care George primește primele două obiecte {1,7 }, Alice primește următoarele două {5,6} și Daina obține obiectul {17} este MMD-just.

Interpretare . MMD 1-out- n al unui agent poate fi interpretat ca utilitatea maximă pe care un agent poate spera să o câștige dintr-o distribuție dacă alți agenți au aceleași preferințe, dacă el primește întotdeauna cea mai slabă cotă. Aceasta este utilitatea minimă la care are dreptul agentul (în opinia sa), pe baza următoarelor argumente: dacă alți agenți vor avea aceleași preferințe ca mine, există cel puțin o distribuție care îmi va oferi o astfel de utilitate și care oferă alți agenți nu mai puțin, prin urmare, nu au de ce să-mi dea mai puțin.

Interpretare alternativă: setul cel mai preferat pentru agent, garantat de divizor în protocolul de împărțire și alegere între adversarii rivali - agentul propune cea mai bună alocare și lasă altora regula de selecție a setului, în timp ce el ia setul rămas [2] ] .

Echitatea MMD poate fi descrisă și ca rezultat al următorului proces de negociere. S-a sugerat o anumită distribuție. Fiecare agent se poate plânge de o astfel de distribuție și poate oferi a lui. Cu toate acestea, după ce a făcut acest lucru, el trebuie să permită celorlalți să le ia părțile, în timp ce el însuși ia setul rămas. Prin urmare, un agent se va plânge de o distribuție doar dacă poate oferi o distribuție în care toate seturile sunt mai bune decât cea actuală. O alocare este MMD-echitabilă dacă și numai dacă niciunul dintre agenți nu se plânge de aceasta, adică pentru orice agent din orice alocare există un set care nu este mai bun decât cota pe care o va primi în alocarea curentă.

Existența distribuțiilor MMD-echitabile

Dacă toți cei n agenți au evaluări identice, o distribuție corectă MMD există întotdeauna prin definiție.

Dacă doar n -1 agenți au scoruri identice, distribuția corectă a MMD există încă și poate fi găsită utilizând protocolul de împărțire și alegere - n -1 agenți identici împart obiectele în n seturi, fiecare dintre ele nu este mai rău decât MMD, apoi al n -lea agent alege multimea cu cel mai mare scor, iar agentii identici sorteaza restul de n -1 seturi.

În special, pentru doi agenți, o distribuție echitabil MMD există întotdeauna.

Bouvre și Lemaitre [2] au efectuat simulări intensive pe date aleatorii pentru mai mult de 2 agenți și au descoperit că distribuțiile corecte ale MMD au existat în fiecare studiu. Ei au dovedit că distribuțiile MMD-echitabile există în următoarele cazuri:

Procaccia și Won [3] , precum și Kurokawa [4] , au construit un exemplu cu n= 3 agenți și m = 12 obiecte, în care distribuția garantează fiecărui agent un MMD 1-out-3. Mai mult, ei au arătat că pentru orice există un exemplu cu obiecte.

Aproximare multiplicativă

Pentru cazul inexistenței distribuțiilor MMD, Procaccia și Vaughn au propus o aproximare multiplicativă pentru MMD — distribuția se numește MMD r-share pentru o fracție r din [0,1] dacă valoarea oricărui agent nu este mai mică decât fracția r a valorii MMD-ului său.

Ei au prezentat un algoritm care găsește întotdeauna MMD -shared, unde , și oddfloor( n ) este cel mai mare număr întreg impar care nu depășește n . În special, , scade pe măsură ce n crește și este întotdeauna mai mare decât . Algoritmul lor rulează în timp polinomial în m dacă n este constant.

Amanatidis, Markakis, Nikzad și Saberi [5] au demonstrat că în problemele generate aleator există distribuții corecte MMD cu mare probabilitate . Ei au propus câțiva algoritmi îmbunătățiți

Barman și Krishnamurti [6] au prezentat

Godsi, Hadzhigoyi, Sedigin și Yami [7] au propus

Garg, McGlaflin și Taki [8] au propus un algoritm simplu pentru MMD în 2/3 părți, a cărui analiză este simplă.

În prezent, nu se știe care este cea mai mare valoare a lui r pentru care există întotdeauna o distribuție MMD r -parțială. Poate fi un număr între 3/4 și 1 (fără a include 1).

Amanatidis, Burmpas și Markakis [9] au propus strategii invulnerabile pentru distribuții aproximative MMD-echitabile (vezi și Divizia strategică corectă ):

Xin și Pingyang [10] au studiat distribuția corectă a sarcinilor MMD (obiecte cu evaluări negative) și au arătat că o distribuție MMD parțială de 11 septembrie există întotdeauna.

Aproximare ordinală

Budish [1] a propus o altă aproximare a distribuției 1-out- n MMD - 1-out-( ) MMD (fiecare agent primește cel puțin cât ar putea obține împărțind în n + 1 seturi și alegând cel mai rău dintre ele) . El a arătat că un echilibru competitiv aproximativ cu venit egal garantează întotdeauna 1 din ( ) MMD. Cu toate acestea, această distribuție poate depăși numărul de obiecte disponibile și, mai important, depășește nevoile - suma seturilor distribuite tuturor agenților poate fi puțin mai mare decât suma tuturor obiectelor. O astfel de eroare este acceptabilă în alocarea de locuri studenților de la curs, deoarece un mic deficit poate fi corectat prin adăugarea unui număr mic de scaune. Dar problema clasică a împărțirii echitabile presupune că articolele nu pot fi adăugate.

Pentru orice număr de agenți cu estimatori aditivi, orice distribuție echitabilă fără invidie , cu  excepția unuia ( EF1), dă fiecărui agent cel puțin 1-out-(2 n -1) MMD [11 ] . Distribuția BZ1 poate fi găsită, de exemplu, folosind distribuția ciclică a obiectelor sau procedura ciclurilor invidiei .

Mai mult, distribuția MMD 1-out-(2 n -2) poate fi găsită folosind potrivirea fără invidie [12] .

În prezent, nu se știe care este minimul N pentru care există întotdeauna o distribuție MMD 1-out- N . Poate fi orice număr între n +1 și 2 n -2. Cea mai mică valoare a lui n pentru care un astfel de N nu mai este cunoscut este 4.

Condiția inițială MDM poate fi utilizată pentru agenți asimetrici (agenți cu ponderi diferite datorită acestora) [13] .

Alte probleme algoritmice

Câțiva algoritmi de bază legați de MMD:

MMD-echitate pentru grupuri

O alocare se numește pairwise -maximin-share-fair ( PMMS -fair ) dacă, pentru orice pereche de agenți i  și j , agentul i primește cel puțin 1-out-2 maximin- cota limitată de obiecte din setul total de obiectele i și j [16] .

Distribuția se numește grup - wise-maximin-share-fair ( GMMS -fair  ) dacă, pentru orice subgrup de agenți de mărimea k , fiecare membru al subgrupului primește 1- din k maximin-share, limitat. la obiectele obţinute de acest subgrup [17] .

Diverse noțiuni de justiție sunt legate de evaluările aditive în felul următor.

Distribuțiile HMMD sunt garantate să existe atunci când estimările agenților sunt fie binare, fie identice. Cu estimări aditive generale, distribuțiile 1/2-HMMD există și pot fi găsite în timp polinomial [17] .

Vezi și

Note

  1. ↑ 1 2 Budish, 2011 , p. 1061–1103.
  2. ↑ 1 2 3 Bouveret, Lemaître, 2015 , p. 259.
  3. ↑ Procaccia, Wang, 2014 , p. 675–692.
  4. ↑ Copie arhivată . Preluat la 26 februarie 2020. Arhivat din original la 28 iulie 2019.
  5. ↑ Amanatidis, Markakis, Nikzad, Saberi, 2017 , p. 1–28.
  6. ↑ Barman, Krishnamurthy, 2017 , p. 647-664.
  7. ↑ Ghodsi, Hajiaghayi et al., 2018 , p. 539-556.
  8. ↑ Garg, McGlaughlin, Taki, 2018 , p. 20:1–20:11.
  9. ↑ Amanatidis, Birmpas, Markakis, 2016 , p. 31-37.
  10. ↑ Huang, Lu, 2019 .
  11. ↑ Segal-Halevi, Suksompong, 2019 , p. 103167.
  12. ↑ Aigner-Horev, Segal-Halevi, 2019 .
  13. ↑ Segal-Halevi, 2019 .
  14. ↑ Woenger, 1997 , p. 149–154.
  15. ↑ Lang, Rothe, 2016 , p. 493–550.
  16. ↑ 1 2 Caragiannis, Kurokawa et al., 2019 , p. 12:1–12:32.
  17. ↑ 1 2 3 Barman, Biswas, Krishnamurthy, Narahari, 2018 .
  18. ↑ Libertatea invidiei până la bunul cel mai puțin prețuit .  Vezi Caragiannis, Kurokawa et al.

Literatură