Potrivire fără invidie

Potrivirea fără invidie ( EFM ) este o  potrivire între oameni și „obiecte” în care nu există invidie în sensul că niciunul dintre oameni nu are dorința de a trece la un „obiect” care aparține altei persoane. Termenul este folosit în mai multe contexte diferite. Mai jos, abrevierea OZ înseamnă Fără invidie , iar PbZ înseamnă Potrivire fără invidie .

În piața cu bani

Luați în considerare o piață în care există mai mulți cumpărători și mai multe obiecte, iar fiecare obiect poate avea un preț. Având în vedere un vector de preț, fiecare client are un set de cereri — setul de seturi care maximizează utilitatea clientului față de alte seturi (acest set poate include un set gol dacă clientul consideră că toate seturile sunt prea scumpe).

O potrivire fără invidie (având în vedere un vector de preț) este o potrivire în care fiecare agent primește un set din setul său de seturi. Aceasta înseamnă că niciun agent nu dorește să primească pachetul altui agent la același preț [1] . Un exemplu de astfel de condiții este problema chiriei echitabile — potrivirea chiriașilor (agenților) cu locuințe (obiecte) în prezența unui preț pentru fiecare locuință.

Prețurile fără invidie sunt vectorul prețurilor pentru care există o potrivire fără invidie. Aceasta este o slăbire a echilibrului Walrasian — echilibrul Walrasian constă din costul PV și din CV-ul de potrivire și, în plus, fiecare obiect trebuie fie să fie inclus în potrivire, fie să aibă un preț zero. Se știe că în echilibrul walrasian, potrivirea maximizează suma valorilor, adică aceasta este potrivirea greutății maxime . Cu toate acestea, venitul vânzătorului poate fi scăzut. Acest lucru induce o relaxare a prețurilor în OZ, în care vânzătorul poate folosi prețurile minime acceptabile pentru a crește veniturile [2] [3] [4] [5] [6] [7] .

Într-o piață fără bani

Luați în considerare problema combinării medicilor pentru a lucra în clinici. Fiecare medic are o preferință pentru clinici (are o părere comparativă despre clinici de la rău la bun), iar fiecare clinică are o preferință pentru medici (clasând medicii de la cel mai bun la cel mai rău). Fiecare medic trebuie să lucreze în cel mult o clinică, iar fiecare clinică poate angaja un număr fix de medici (numit capacitatea clinicii ). Trebuie să aranjam medici pentru clinici. Schimburile de bani nu sunt permise. Există două cazuri în care un astfel de aranjament poate fi „rău”:

  1. O potrivire are invidie rezonabilă dacă există un medic d și o clinică h astfel încât d preferă h locului de muncă actual și clinica h preferă medicul d față de unul dintre angajații actuali.
  2. O potrivire este goală dacă există un medic d și o clinică h astfel încât d preferă clinica h locului de muncă actual, iar clinica h are unele posturi vacante și h preferă să angajeze d decât să lase locul gol.

O potrivire fără invidie este o potrivire fără invidie justificată. O astfel de potrivire este o slăbire a condiției de stabilitate a potrivirii - o potrivire stabilă este atât lipsită de invidie, cât și nu are goluri.

Structura lattice

În problema potrivirii multi-la-unu, potriviri stabile există și pot fi găsite folosind algoritmul Gale-Shapley . Prin urmare, și OZ există. În general, pot exista multe potriviri OD diferite. Setul tuturor potrivirilor OD este o rețea . Setul de potriviri stabile (care este un subset de potriviri OD) este un punct fix al operatorului Tarski pe această rețea [8] .

Cote superioare și inferioare

Adesea, clinicile au nu doar cote superioare (capacități), ci și cote mai mici - fiecare clinică trebuie să angajeze un anumit număr minim de medici [9] . În astfel de probleme este posibil să nu existe potriviri stabile (deși este ușor de verificat dacă există o potrivire stabilă prin teorema clinicilor rurale , conform căreia numărul de medici alocați fiecărei clinici este același în toate potrivirile stabile). În astfel de condiții, este firesc să verificăm dacă există o potrivire OD. O condiție necesară este ca suma tuturor cotelor mai mici să nu fie mai mare decât numărul de medici (altfel nu există deloc o soluție fezabilă). În acest caz, dacă toate perechile medic-clinic sunt acceptabile (fiecare medic preferă să lucreze undeva și să nu fie șomer, iar fiecare clinică preferă să angajeze un medic pentru a nu lipsi de personal), atunci potrivirea OD există întotdeauna [9] ] .

Dacă nu toate perechile sunt acceptabile, atunci este posibil să nu existe o potrivire OD. Puteți afla despre existența PbZ în felul următor. Să creăm o nouă problemă în care cotele superioare sunt egale cu cotele inferioare ale problemei inițiale, iar cotele inferioare sunt egale cu 0. În această nouă problemă, o potrivire stabilă există întotdeauna și poate fi găsită eficient. Problema originală are o potrivire OD dacă și numai dacă orice clinică este completată în noua problemă [10] .

Algoritmul poate fi îmbunătățit pentru a găsi EP maxim al potrivirii [11] .

Minimizarea invidiei

După cum s-a definit mai sus, potrivirea fără invidie exclude invidia justificată , unde medicul d este gelos pe un alt medic care a fost repartizat la clinica h pe care d o preferă. Cu toate acestea, chiar și în PbZ poate exista un medic d și o clinică h astfel încât d preferă h , deși i se atribuie un alt medic, dar h nu îl vede pe doctorul d ca înlocuitor pentru unii dintre angajații săi existenți. Aceasta poate fi numită „invidie nerezonabilă”. Potrivirea fără invidie există doar în cazuri rare, când fiecare medic poate fi desemnat în locul pe care îl preferă cel mai mult. Când o astfel de „potrivire complet fără invidie” nu există, este rezonabil să găsim potriviri care să minimizeze „cantitatea de invidie”. Există mai multe moduri de a măsura magnitudinea invidiei, cum ar fi suma invidiei tuturor medicilor sau invidia maximă [12] .

În graficele bipartite

Într-un graf bipartit neponderat , o potrivire fără invidie este o potrivire în care niciunul dintre vârfurile de potrivire din X nu este adiacent unui vârf de potrivire din Y [13] . Imaginați-vă că vârfurile X reprezintă oameni, iar vârfurile Y reprezintă case, iar marginea dintre persoana x și casa y reprezintă faptul că x ar dori să locuiască în y . Atunci PbZ este o distribuție parțială a caselor pentru oameni, astfel încât fiecare persoană fără adăpost să nu-l invidieze pe persoana cu casa, pentru că nu vrea să locuiască în niciuna dintre casele oferite.

Orice potrivire care saturează X nu are invidie, iar orice potrivire goală nu are invidie.

Mai mult, dacă (unde este mulțimea vecinilor lui X în Y ), atunci G admite un PbZ nevid.

Aceasta este o slăbire a condiției lui Hall , care spune că dacă pentru orice submulțime X ' a unei mulțimi X , atunci există o partițiune completă a lui X în perechi.

În tăierea tortului

Termenul de potrivire fără invidie a fost folosit și în alt context, într-un algoritm de îmbunătățire a eficienței unei tăieturi invidioase de tort [14] .

Vezi și

Note

  1. ↑ Alaei, Jain, Malekian, 2010 .
  2. ↑ Guruswami, Hartline, Karlin et al., 2005 , p. 1164–1173.
  3. ↑ Briest, 2008 , p. 808–819.
  4. ↑ Chen, Ghosh, Vassilvitskii, 2011 , p. 623–645.
  5. ↑ Wang, Lu, Im, 2010 , p. 483–491.
  6. ↑ Feldman, Fiat, Leonardi, Sankowski, 2012 , p. 532–549.
  7. ↑ Chen, Deng, 2014 , p. 7:1–7:15.
  8. ↑ Wu, Roth, 2018 , p. 201–211.
  9. ↑ 1 2 Fragiadakis, Iwasaki, Troyan et al., 2016 , p. 6:1–6:40.
  10. ↑ Yokoi, 2017 .
  11. ↑ Cât de bune sunt potrivirile populare? . www.cse.iitm.ac.in. _ Preluat la 16 ianuarie 2019. Arhivat din original la 17 ianuarie 2019.
  12. ↑ Tadenuma, 2011 , p. 155–167.
  13. ↑ Segal-Halevi, Aigner-Horev, 2019 .
  14. ↑ Sen, Nuchia, 2001 , p. 277–289.

Literatură