Přibližná konkurenční rovnováha ze stejných příjmů - Approximate Competitive Equilibrium from Equal Incomes - Wikipedia

Přibližný Konkurenční rovnováha ze stejných příjmů (A-CEEI) je postup pro spravedlivé přiřazení položky. Byl vyvinut Ericem Budishem.^[1]

Pozadí

CEEI (Konkurenční rovnováha ze stejných příjmů) je základním pravidlem spravedlivé rozdělení dělitelných zdrojů. Rozděluje zdroje podle výsledku následujícího hypotetického procesu:

Každý agent obdrží jednu jednotku fiat peníze. Toto je část rovných příjmů CEEI.
Agenti obchodují volně, dokud trh nedosáhne a Konkurenční rovnováha. Jedná se o cenový vektor a alokaci, takže (a) každý přidělený balíček je pro svého agenta optimální vzhledem k jeho / jejímu příjmu - agent si nemůže koupit lepší balíček se stejným příjmem a (b) trh zúčtuje - součet všech alokací se přesně rovná počáteční dotaci.

Rovnovážná alokace je prokazatelně závist zdarma a Pareto efektivní. Navíc, když mají agenti lineární obslužné funkce, lze alokaci CEEI vypočítat efektivně.

Bohužel, pokud existují nedělitelnosti, CEEI nemusí vždy existovat, takže jej nelze přímo použít spravedlivé přiřazení položky. Lze jej však aproximovat a aproximace má dobrou spravedlnost, účinnost a strategické vlastnosti.

Předpoklady

A-CEEI pouze předpokládá, že agenti vědí, jak řadit balíčky položek. Pořadí nemusí být slabě aditivní ani monotónní.

Postup

A-CEEI s parametry ${ displaystyle alpha, beta}$ rozdělí zdroje podle výsledku následujícího hypotetického procesu:

Přibližný EI: každý agent obdrží příjem mezi 1 a ${ displaystyle 1+ beta}$ . Přesný příjem každého agenta lze určit náhodně nebo podle seniority (senioři mohou získat mírně vyšší příjem).
Přibližná CE: cenový vektor a alokace se počítají tak, že (a) každý přidělený balíček je vzhledem ke svému rozpočtu optimální pro svého agenta a (b) trh se „téměř“ vyčistí: euklidovská vzdálenost mezi součtem všech alokace a počáteční dotace je nanejvýš ${ displaystyle alpha}$ .

Budish to dokazuje pro všechny ${ displaystyle beta> 0}$ , tady existuje ${ displaystyle alpha, beta}$ -CEEI kde ${ displaystyle alpha}$ závisí na minimu mezi počtem různých typů položek a počtem různých položek, které může agent obdržet.

Záruky

Alokace splňuje následující vlastnosti:

Bez závisti - kromě 1 položky (viz přiřazení položky bez závisti ).
${ displaystyle (n + 1)}$ -maximální-záruka podílu.
Paretova účinnost s ohledem na přidělené položky. Mezi agenty tedy neexistuje žádný obchod zlepšující Pareto, ale mezi agentem a tvůrcem trhu mohou existovat obchodníci zlepšující Pareto.

Mechanismus A-CEEI navíc je odolný vůči strategii „ve velkém“: když je mnoho agentů, každý agent má jen malý vliv na cenu, takže agenti jednají jako příjemci cen. Poté je optimální pro každého agenta hlásit své skutečné ocenění, protože to umožňuje mechanismu poskytnout mu optimální balíček vzhledem k cenám.

Výpočet

Alokaci A-CEEI je těžké vypočítat: je PPAD kompletní.^[2]

V případě problémů s realistickou velikostí však lze A-CEEI vypočítat pomocí procesu vyhledávání na dvou úrovních:

Hlavní úroveň: centrum používá tabu vyhledávání navrhovat ceny;
Úroveň agenta: smíšené celočíselné programy jsou řešeny k vyhledání požadavků agentů za aktuální ceny.

Program na úrovni agenta lze provést paralelně pro všechny agenty, takže tato metoda se v počtu procesorů přizpůsobuje téměř optimálně.^[3]

Tento mechanismus byl zvážen pro úkol přiřadit studenty ke kurzům na VŠE Wharton School of University of Pennsylvania.^[4]

Srovnání s maximálním blahobytem Nash

The Maximum-Nash-Welfare Algoritmus (MNW) najde alokaci, která maximalizuje produkt obslužných programů agentů. Je to podobné jako A-CEEI v několika ohledech:^[5]

Oba algoritmy najdou přidělení EF kromě 1.
Oba algoritmy aproximují záruku maximinového podílu.

A-CEEI má však několik výhod:

Pracuje s libovolnými užitečnými funkcemi - nejen submodulární ty. Nevyžaduje ani monotónnost preferencí.
Funguje to s řadovým vstupem - agenti jsou povinni hlásit pouze své pořadí podle balíčků - nikoli jejich číselné hodnocení položek.
Je to důkaz strategie „ve velkém“.

Na druhé straně má A-CEEI několik nevýhod:

U položek, které jsou alokovány, došlo k chybě aproximace - některé položky mohou být nadměrné poptávce nebo nadměrné nabídce.^[6]
Zejména vrácená alokace není Pareto-efektivní - některé položky zůstávají nepřidělené (je Pareto-efektivní pouze s ohledem na alokované položky).

Chyba aproximace A-CEEI roste s počtem odlišných položek, ale ne s počtem hráčů nebo počtem kopií jednotlivých položek. Proto je A-CEEI lepší, když existuje mnoho agentů a mnoho kopií každé položky. Typická aplikace je, když agenti jsou studenti a položky jsou pozice v kurzech.^[6]

Naproti tomu MNW je lepší, když existuje několik agentů a mnoho odlišných položek, například v dědění dědičnosti.

Srovnání s konkurenční rovnováhou

A-CEEI (a CEEI obecně) souvisí, ale ne identicky, s konceptem konkurenční rovnováha.

Konkurenční rovnováha (CE) je popisný koncept: popisuje situaci na volném trhu, kdy se cena stabilizuje a poptávka se rovná nabídce.
CEEI je normativní koncept: popisuje pravidlo pro dělení komodit mezi lidi.

Viz také

Kombinatorická aukce

Reference

^ Budish, Eric (2011). „Problém kombinovaného přiřazení: Přibližná konkurenční rovnováha ze stejných příjmů“. Journal of Political Economy. 119 (6): 1061–1103. doi:10.1086/664613.
^ Othman, Abraham; Papadimitriou, Christos; Rubinstein, Aviad (2016). "Složitost spravedlnosti prostřednictvím rovnováhy". Transakce ACM v oblasti ekonomiky a výpočtu. 4 (4): 1. arXiv:1312.6249. doi:10.1145/2956583.
^ Abraham Othman; Tuomas Sandholm a Eric Budish (2010). Nalezení přibližné konkurenční rovnováhy: efektivní a spravedlivé rozdělení kurzu (PDF). AAMAS '10. acm.org
^ Budish, Eric; Kessler, Judd B. (2016). „Uvedení skutečných preferencí účastníků reálného trhu do laboratoře: experiment, který změnil mechanismus přidělování kurzů ve Whartonu“ (PDF). Archivovány od originál (PDF) dne 03.03.2017. Citováno 2017-03-06.
^ Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D .; Shah, Nisarg; Wang, Junxing (2016). Nerozumná spravedlnost maximálního blahobytu Nash (PDF). Sborník konferencí ACM o ekonomii a výpočtu z roku 2016 - EK '16. str. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360.
^ ^A ^b Kurokawa, David; Procaccia, Ariel D .; Wang, Junxing (01.02.2018). "Dost spravedlivé: Záruka přibližného maximálního počtu akcií". J. ACM. 65 (2): 8:1–8:27. doi:10.1145/3140756. ISSN 0004-5411.

[b11-1] Budish, Eric (2011). „Problém kombinovaného přiřazení: Přibližná konkurenční rovnováha ze stejných příjmů“. Journal of Political Economy. 119 (6): 1061–1103. doi:10.1086/664613.

[2] Othman, Abraham; Papadimitriou, Christos; Rubinstein, Aviad (2016). "Složitost spravedlnosti prostřednictvím rovnováhy". Transakce ACM v oblasti ekonomiky a výpočtu. 4 (4): 1. arXiv:1312.6249. doi:10.1145/2956583.

[osb10-3] Abraham Othman; Tuomas Sandholm a Eric Budish (2010). Nalezení přibližné konkurenční rovnováhy: efektivní a spravedlivé rozdělení kurzu (PDF). AAMAS '10. acm.org

[bk16-4] Budish, Eric; Kessler, Judd B. (2016). „Uvedení skutečných preferencí účastníků reálného trhu do laboratoře: experiment, který změnil mechanismus přidělování kurzů ve Whartonu“ (PDF). Archivovány od originál (PDF) dne 03.03.2017. Citováno 2017-03-06.

[ckmpsw16-5] Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D .; Shah, Nisarg; Wang, Junxing (2016). Nerozumná spravedlnost maximálního blahobytu Nash (PDF). Sborník konferencí ACM o ekonomii a výpočtu z roku 2016 - EK '16. str. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360.

[:0-6] A ^b Kurokawa, David; Procaccia, Ariel D .; Wang, Junxing (01.02.2018). "Dost spravedlivé: Záruka přibližného maximálního počtu akcií". J. ACM. 65 (2): 8:1–8:27. doi:10.1145/3140756. ISSN 0004-5411.

[1]

[2]

[3]

[4]

[5]

[6]