Bez závisti - Envy-free matching

v ekonomika a teorie sociální volby, an záviděníhodné shody (EFM) je shoda mezi lidmi s „věcmi“, což je bez závisti v tom smyslu, že žádná osoba by nechtěla změnit svou „věc“ s věcí jiné osoby. Tento termín byl použit v několika různých kontextech.

Na trzích s penězi

Zvažte trh, na kterém je několik kupujících a několik zboží, a každý zboží může mít svou cenu. Vzhledem k cenovému vektoru má každý kupující a sada poptávky - sada balíčků, které maximalizují užitek kupujícího přes všechny balíčky (tato sada může obsahovat prázdný balíček, pokud kupující považuje všechny balíčky za příliš drahé).

An záviděníhodné shody (vzhledem k cenovému vektoru) je shoda, ve které každý agent obdrží balíček ze své sady poptávky. To znamená, že žádný agent by nechtěl získat balíček jiného agenta se stejnými cenami.[1] Příkladem tohoto nastavení je harmonie pronájmu problém - přiřazení nájemníků (agentů) k místnostem (položkám) při stanovení ceny pro každou místnost.

An cena bez závisti je cenový vektor, pro který existuje shoda bez závisti. Je to relaxace a Walrasianská rovnováha: a Walrasianská rovnováha sestává z EF ceny a EF shody a navíc musí být každá položka buď spárována, nebo mít nulovou cenu. Je známo, že ve valrasiánské rovnováze shoda maximalizuje součet hodnot, tj. Je shoda maximální hmotnosti. Tržby prodejce však mohou být nízké. To motivuje uvolnění k cenám EF, ve kterých může prodejce použít rezervní ceny ke zvýšení výnosů.[2][3][4][5][6][7]

Na trzích bez peněz

Zvažte problém přiřazování lékařů k pobytu v nemocnicích. Každý lékař má preferenční vztah o nemocnicích (hodnocení nemocnic od nejhorších po nejhorší) a každá nemocnice má preferenční vztah k lékařům (hodnocení lékařů od nejhorších po nejhorší). Každý lékař může pracovat maximálně v jedné nemocnici a každá nemocnice může zaměstnávat maximálně stálý počet lékařů (tzv kapacita nemocnice). Chceme spojit lékaře s nemocnicemi. Peněžní převody nejsou povoleny. Existují dva způsoby, jak může být taková shoda „špatná“:

  1. Odpovídající má oprávněná závist pokud existuje lékař d a nemocnice h, takový, že d preferuje h - nad jeho současným zaměstnavatelem a - h preferuje d přes jednoho ze svých současných zaměstnanců.
  2. Odpovídající má odpad pokud existuje lékař d a nemocnice h, takže d preferuje h před svým současným zaměstnavatelem, h má několik volných míst a h preferuje d na volné místo.

An záviděníhodné shody je shoda bez oprávněné závisti. Je to relaxace stabilní shoda: a stabilní shoda je shoda, která je jak bez závisti, tak bez odpadu.

Příhradová struktura

V problému s párováním typu jedna ku jedné existují stabilní párování a lze je najít Algoritmus Gale – Shapley. Proto existují i ​​EF shody. Obecně může existovat mnoho různých EF shody. Sada všech EF shody je a mříž. Sada stabilních shody (které jsou podmnožinou EF shody) je a pevný bod a Operátor Tarsky na té mříži.[8]

Horní i dolní kvóta

Nemocnice často mají nejen vyšší kvóty (kapacity), ale také nižší kvóty - každé nemocnici musí být přiřazen alespoň určitý minimální počet lékařů.[9] V takových problémech nemusí stabilní párování existovat (ačkoli je snadné zkontrolovat, zda stabilní párování existuje, protože pomocí věta o venkovských nemocnicích, ve všech stabilních shodách je počet lékařů přidělených každé nemocnici stejný). V takových případech je přirozené zkontrolovat, zda existuje EF shoda. Nutnou podmínkou je, že součet všech nižších kvót je nanejvýš počet lékařů (jinak vůbec neexistuje proveditelná shoda). V tomto případě, pokud jsou přijatelné všechny páry lékař - nemocnice (každý lékař upřednostňuje jakoukoli nemocnici před nezaměstnaností a kterákoli nemocnice dává přednost kterémukoli lékaři před volným místem), pak vždy existuje EF shoda.[9]

Pokud nejsou přijatelné všechny páry, pak EF shoda nemusí existovat. O existenci EFM je možné rozhodnout následujícím způsobem. Vytvořte novou instanci problému, ve které jsou horní kvóty nižšími kvótami původního problému a nižší kvóty 0. V novém problému vždy existuje stabilní shoda, kterou lze efektivně najít. Původní problém má EF odpovídající if-and-only-if, při stabilním párování nového problému je každá nemocnice plná.[10]

Algoritmus lze vylepšit tak, aby našel maximální EF shodu.[11]

Minimalizace závisti

Jak je definováno výše, shoda bez závisti pouze eliminuje oprávněná závist, kde lékař d závidí jinému lékaři, který je uzavřen do nemocnice h který dává přednost d. I v EFM však může být lékař d a nemocnice h takhle d preferuje h nad jeho současným zaměstnavatelem, ale h nedává přednost d nad kterýmkoli ze svých současných zaměstnanců. Lze to nazvat „neoprávněnou závistí“. Shoda bez závisti vůbec existuje pouze ve výjimečných případech, kdy lze každého lékaře porovnat s jeho první volbou. Pokud takové „zcela záviděníhodné shody“ neexistují, je stále rozumné najít shody, které minimalizují „závistivé množství“. Existuje několik způsobů, jak lze částku závisti měřit, například: celkové množství případů závisti nad všemi lékaři nebo maximální množství případů závisti na jednoho lékaře.[12]

V bipartitních grafech

V neváženém bipartitní graf G = (X+Y, E), an záviděníhodné shody je vhodný ve kterém žádný nepřekonatelný vrchol v X sousedí se shodným vrcholem v Y.[13] Předpokládejme vrcholy X představují lidi, vrcholy Y představují domy a okraj mezi osobou X a dům y představuje skutečnost, že X je ochoten žít y. EFM je pak částečné přidělení domů lidem, takže každý člověk bez domu nezávidí žádnému člověku dům, protože se mu žádný přidělený dům stejně nelíbí.

Každá shoda, která nasycuje X je bez závisti a každá prázdná shoda je bez závisti.

Navíc, pokud |NG(X) | ≥ | X | ≥ 1 (kde NG(X) je množina sousedů X v Y), pak G připouští neprázdnou EFM.

To je relaxace Hallův stav manželství, který říká, že pokud |NG(X') | ≥ | X '| pro každá podmnožina X'z X, pak X-saturující shoda existuje.

Při krájení dortu

Termín záviděníhodné shody byl také použit v jiném kontextu: algoritmus pro zlepšení efektivity řezání dortů bez závisti.[14]

Viz také

Reference

  1. ^ Alaei, Saeed; Jain, Kamal; Malekian, Azarakhsh (24. června 2010). „Konkurenční rovnováha na dvoustranných srovnávacích trzích s nepřenosnými nástroji“. arXiv:1006.4696 [cs.GT ].
  2. ^ Guruwami, Venkatesan; Hartline, Jason D .; Karlin, Anna R .; Kempe, David; Kenyon, Claire; McSherry, Frank (2005). Na maximalizaci zisku Závislé ceny bez závisti. Sborník šestnáctého výročního sympozia ACM-SIAM o diskrétních algoritmech. SODA '05. Philadelphia, PA, USA: Společnost pro průmyslovou a aplikovanou matematiku. str. 1164–1173. ISBN  9780898715859.
  3. ^ Briest, Patrick (2008). „Jednotné rozpočty a problém s cenami závisti“. V Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M .; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). Automaty, jazyky a programování. Přednášky z informatiky. 5125. Springer Berlin Heidelberg. 808–819. CiteSeerX  10.1.1.205.433. doi:10.1007/978-3-540-70575-8_66. ISBN  9783540705758. Chybějící nebo prázdný | název = (Pomoc)
  4. ^ Chen, Ning; Ghosh, Arpita; Vassilvitskii, Sergei (2011). "SIAM (společnost pro průmyslovou a aplikovanou matematiku)". SIAM Journal on Computing. 40 (3): 623–645. CiteSeerX  10.1.1.193.6235. doi:10.1137/080740970.
  5. ^ Wang, Yajun; Lu, Pinyan; Im, Sungjin (13. prosince 2010). Ceny bez závisti s obecnými omezeními nabídky. Ekonomika internetu a sítí. Přednášky z informatiky. 6484. Springer, Berlín, Heidelberg. str.483–491. doi:10.1007/978-3-642-17572-5_41. ISBN  978-3-642-17571-8.
  6. ^ Feldman, Michal; Fiat, Amos; Leonardi, Stefano; Sankowski, Piotr (2012). Výnosy Maximalizace vícezlokových aukcí bez závisti s rozpočty. Sborník z 13. konference ACM o elektronickém obchodu. ES '12. New York, NY, USA: ACM. 532–549. doi:10.1145/2229012.2229052. ISBN  9781450314152. S2CID  15639601.
  7. ^ Chen, Ning; Deng, Xiaotie (1. února 2014). „Ceny bez závisti na trzích s více položkami“. Transakce ACM na algoritmech. 10 (2): 7:1–7:15. CiteSeerX  10.1.1.297.784. doi:10.1145/2567923. ISSN  1549-6325. S2CID  15309106.
  8. ^ Wu, Qingyun; Roth, Alvin E. (1. května 2018). „Mřížka zápasů bez závisti“. Hry a ekonomické chování. 109: 201–211. doi:10.1016 / j.geb.2017.12.016. ISSN  0899-8256.
  9. ^ A b Fragiadakis, Daniel; Iwasaki, Atsushi; Troyan, Peter; Ueda, Suguru; Yokoo, Makoto (1. ledna 2016). "Strategické shody s minimálními kvótami". Transakce ACM v oblasti ekonomiky a výpočtu. 4 (1): 6:1–6:40. doi:10.1145/2841226. ISSN  2167-8375. S2CID  1287011.
  10. ^ Yokoi, Yu (17. dubna 2017). „Bez závisti shody s nižšími kvótami“. arXiv:1704.04888 [cs.GT ].
  11. ^ „Jak dobré jsou oblíbené zápasy?“ (PDF). www.cse.iitm.ac.in. Archivovány od originál (PDF) dne 17. ledna 2019. Citováno 16. ledna 2019.
  12. ^ Tadenuma, Koichi (2011), „Partnerství, solidarita a minimální závist při řešení problémů“, Fleurbaey, Marc; Salles, Maurice; Weymark, John A. (eds.), Sociální etika a normativní ekonomie„Studies in Choice and Welfare, Springer Berlin Heidelberg, str. 155–167, doi:10.1007/978-3-642-17807-8_6, ISBN  9783642178078
  13. ^ Segal-Halevi, Erel; Aigner-Horev, Elad (28. ledna 2019). „Bezzávidné shody v bipartitních grafech a jejich aplikace na spravedlivé rozdělení“. arXiv:1901.09527 [cs.DS ].
  14. ^ Sen, Sandip; Nuchia, Stephen W. (1. srpna 2001). Zlepšení optimality divizí bez závisti agentů. Inteligentní agenti VIII. Přednášky z informatiky. 2333. Springer, Berlín, Heidelberg. str.277–289. doi:10.1007/3-540-45448-9_20. ISBN  978-3-540-43858-8.