Závistivé rozmístění předmětů

Distribuce objektů bez závisti (bez závisti, KB, anglicky Envy-free , EF distribution [1] ) je problém spravedlivé distribuce objektů , ve kterém je kritériem spravedlnosti absence závisti ve výsledné distribuci - každý agent musí obdržet soubor předmětů, jejichž hodnota (jak se domnívá) není menší než akcie obdržené jinými agenty [2] .

Vzhledem k tomu, že objekty jsou nedělitelné, distribuce KB nemusí existovat. Nejjednodušším případem takového rozdělení je jeden objekt, který by měl být rozdělen mezi alespoň dva agenty: pokud jeden agent objekt získá, druhý mu bude závidět. Postupy dělení tedy zahrnují různé druhy zmírnění požadavku nezávist .

Hledání distribuce bez závisti, pokud existuje

Předvolby objednání sad: Žádná žárlivost

Procedura prořezávání najde kompletní distribuci KB pro dva agenty, pouze pokud taková distribuce existuje. Postup vyžaduje, aby agenti seřadili sady objektů, ale nevyžaduje kvantitativní informace o užitku . Algoritmus funguje, pokud jsou preference agentů přísně monotónní a není třeba předpokládat, že se jedná o adaptivní preference . V nejhorším případě mohou mít agenti několik možných sad, takže doba běhu může exponenciálně záviset

Přednostní řazení pro objekty: Notorious/Possible Envy-Free

Pro lidi je obvykle jednodušší objednávat jednotlivé objekty než objednávat sady objektů. Předpokládejme, že všichni agenti mají adaptivní preference , pak je možné povýšit řazení objektů na částečné řazení množin. Pokud jsou například objekty seřazeny w>x>y>z, znamená to, že {w, x}>{y, z} a {w, y}>{x, z}, ale neznamená to žádnou preferenci mezi { w, z} a {x, y}, mezi {x} a {y, z} a tak dále.

Vzhledem k pořadí objektů:

Je známo, že distribuce je nezávislá ( nezbytně závistivá , NEF), pokud není nezávislá pro všechna adaptivní uspořádání množin konzistentní s uspořádáním objektů;
Distribuce je možná nezávislá (možná závist , PEF), pokud není nezávislá pro alespoň jedno adaptivní uspořádání množin konzistentní s uspořádáním objektů;
Distribuce je jistě Pareto - optimální ( NPE ), pokud je Pareto - optimální pro všechna adaptivní uspořádání množin konzistentní s uspořádáním objektů;
Distribuce je možná Pareto -optimální (PPE), pokud je Pareto-optimální pro alespoň jedno adaptivní uspořádání množin konzistentní s uspořádáním objektů.

Bouvre, Endriss a Leng [3] studovali algoritmické problémy hledání distribuce ZBZ/WBZ s další podmínkou účinnosti, parciality, úplnosti, COP nebo COP. Obecně je případ WBZ výpočetně jednodušší, zatímco případ ZBZ je obtížnější.

Existuje distribuce KB

Prázdná distribuce je vždy KB, ale pokud chceme kromě KB požadovat i efektivitu, řešení problému se stává výpočetně obtížným [4] :

Rozhodování, zda existuje úplná distribuce KB, je NP-úplný problém. To platí i v případě, že existují pouze dva agenti, a dokonce i tehdy, když jsou funkce utility aditivní a identické , protože v tomto případě je hledání distribuce KB ekvivalentní řešení problému rozdělení množiny čísel [5] .
Rozhodnout, zda existuje Paretova efektivní distribuce KB, je obtížnější než NP - je -úplné i s dichotomickými preferenčními funkcemi [6] a dokonce i s aditivními funkcemi užitku [7] . $\Sigma _{2}^{\textrm {P))$

Vyhledávání distribuce s omezenou úrovní závisti

Některé procedury nacházejí distribuci, která nemá závist kromě jednoho objektu (BZ1) - pro libovolné dva agenty A a B existuje jeden objekt, po jehož odstranění z množiny agenta B již agent A nebude závidět agentovi B [8] .

Kruhové řízení

Pokud mají všichni agenti slabě aditivní obslužné programy , následující protokol (který je podobný kruhovému plánování ) poskytuje úplnou distribuci KB1:

Uspořádejte agenty libovolným způsobem.
Dokud existují nepřidělené objekty
- Umožňujeme agentům s čísly od 1 vybrat si objekt. $n$

Důkaz [9] : Pro každého agenta rozdělíme volby provedené agenty do podsekvencí — první podsekvence začíná agentem 1 a končí agentem . Poslední podsekvence začíná a končí . Ve druhé sekvenci si agent vybírá jako první, tedy vybírá ten nejlepší objekt, a proto nezávidí druhému agentovi. Agent může závidět pouze jednomu z agentů a jakákoli závist pochází pouze od objektu, který byl vybrán v první podsekvenci. Pokud je tento předmět odstraněn, agent nebude žárlit.

i

i-1

i

i-1

i

i

1,...,i-1

i

Okružní protokol vyžaduje slabou aditivitu , protože vyžaduje, aby si každý agent vybral „nejlepší objekt“, aniž by věděl, které objekty si následně vybere. Jinými slovy to předpokládá, že předměty jsou nezávislé statky .

Postup cyklu Envy

Procedura cyklů závisti vrací kompletní rozdělení BZ1 pro libovolné preferenční vztahy. Jediným požadavkem je schopnost agentů objednávat své sady objektů.

Pokud jsou preference agentů reprezentovány funkcí kardinálního užitku , pak má záruka BZ1 další výklad: číselná úroveň závisti každého agenta nepřekračuje maximální mezní užitek , tedy maximální mezní užitek jednotlivého objektu pro tohoto agenta.

Přibližný postup P-CRRD

Přibližná konkurenční rovnováha ze stejného příjmu ( A- CEEI ) vrací částečné rozdělení B31 pro libovolné preference. Jediným požadavkem je, aby agent mohl objednávat kolekce objektů.

Malý počet objektů může zůstat nepřidělen. Distribuce je Pareto efektivní pro distribuované objekty. Navíc je mechanismus P-CRRD přibližně strategicky nezranitelný , pokud je počet agentů velký.

Maximální Nashova pohoda

Algoritmus Maximum-Nash-Welfare ( MNW) volí úplnou distribuci, která maximalizuje produkt utilit. Vyžaduje, aby každý agent poskytl číselnou hodnotu pro každý objekt, a předpokládá, že nástroje pro agenty jsou aditivní. Výsledné rozdělení bude také BZ1 a Pareto efektivní [9] .

Pokud nejsou preference agentů aditivní, řešení MNB nemusí být nutně BZ1, ale pokud jsou preference agentů alespoň submodulární , řešení MNB uspokojuje slabší vlastnost zvanou mezní distribuce bez závisti kromě 1 objektu ( Marginal-Envy-Freeness ) , MEF1).

BZ1 / BZd

Existuje alternativní kritérium nazvané Žádná závist kromě nejlevnějšího (BZd) pro libovolné dva agenty A a B. Pokud odstraníme jakýkoli objekt ze sady objektů agenta B, pak A nebude B závidět. BZd je přísnější než BZ1. Stále však není známo, zda vždy existují distribuce BZd [9] .

Minimalizace vztahu závisti

Vzhledem k distribuci X definujte poměr závisti i k j (EnvyRatio) jako:

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

takže poměr je 1, pokud i nežárlí na j , a větší než 1, pokud i nežárlí na j . Vztah závisti distribuce definujeme jako:

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

Problémem minimalizace poměru závisti je problém najít distribuci X s nejmenším poměrem závisti.

Obecné odhady

Podle obecných preferencí vyžaduje jakýkoli deterministický algoritmus , který počítá distribuci s minimálním poměrem závisti, množství dotazů, které v nejhorším případě exponenciálně závisí na počtu objektů [5] .

Aditivní stejné skóre

S aditivním a identickým skóre preferencí [5] :

Následující chamtivý algoritmus najde distribuci, jejíž poměr závisti je maximálně 1,4násobek minima [10] ;
1. Uspořádáme předměty v sestupném pořadí podle hodnoty;
2. Zatímco existují nepřidělené objekty, dáme agentovi další objekt s minimální celkovou hodnotou;
Existuje schéma PTAS pro minimalizaci vztahu závisti. Navíc, pokud je počet hráčů konstantní, existuje schéma FPTAS .

Aditivní různé odhady

S aditivními a různými preferenčními odhady [11]

Pokud je počet agentů zahrnut ve vstupních datech, pak v polynomiálním čase nelze získat aproximační koeficient lepší než 1,5. Pokud P=NP.
Pokud je počet agentů konstantní, existuje schéma FPTAS .
Pokud je počet agentů roven počtu objektů, existuje polynomiální algoritmus rozdělení času.

Hledat částečnou distribuci bez závisti

Procedura AL najde distribuci KB pro dva agenty. Může zahodit některé objekty, ale konečná distribuce je Pareto efektivní v tom smyslu, že žádná jiná distribuce KB není lepší pro jednu a slabě lepší pro druhou. Procedura AL vyžaduje seřadit podle hodnoty samostatné objekty pouze od agentů. Procedura předpokládá, že agenti mají adaptivní preference , a dává distribuci, o které je známo, že je bez závisti ( určitě bez závisti, ZBZ).

Procedura " úprava vítěze " vrací plnou a efektivní distribuční KB pro dva agenty, ale může vyžadovat vyříznutí jednoho z objektů (nebo jeden z objektů zůstane běžně používán). Procedura vyžaduje, aby každý agent hlásil číselnou užitnou hodnotu pro každý objekt, a předpokládá, že agenti mají aditivní užitné funkce .

Existence umístění bez závisti s náhodnými hodnoceními

Pokud mají agenti aditivní funkce užitku , které jsou převzaty z rozdělení pravděpodobnosti splňujících některá kritéria, a počet objektů je vzhledem k počtu agentů dostatečně velký, pak rozdělení KB s vysokou pravděpodobností existuje . Zejména [12]

Pokud je počet objektů dostatečně velký , pak s vysokou pravděpodobností existuje rozdělení KB (to znamená, že pravděpodobnost má tendenci k 1, zatímco m má tendenci k nekonečnu). $m=\Omega (n\log n)$
Pokud počet objektů není dostatečně velký, tedy , pak s vysokou pravděpodobností distribuce KB neexistuje. $m=n+o(n)$

Nedostatek závisti a další kritéria spravedlnosti

Jakákoli distribuce KB je min-max spravedlivá . To vyplývá přímo z obvyklých definic a nezávisí na aditivitě.
Pokud mají agenti aditivní funkce užitku , pak je rozdělení KB také proporcionální a max-min-spravedlivé . V opačném případě nemusí být rozdělení KB proporcionální a nemusí být ani max-min-spravedlivé.
Jakákoli distribuce, která má konkurenční rovnováhu se stejnými příjmy , nemá žádnou závist. To platí bez ohledu na aditivitu [8] .
Jakákoli Nashova optimální distribuce (distribuce, která maximalizuje produkt utilit) je KB1 [9] .

Viz článek Problém spravedlivého rozdělení objektů s podrobným popisem a odkazy na literaturu.

Finální tabulka

Níže jsou použity následující zápisy:

$n$ = počet agentů účastnících se sdílení;
$m$ = počet položek (předmětů) k distribuci;
BE = žádná závist, BE1 = žádná závist s vyloučením jednoho předmětu (slabší požadavek než BE), BE1 = maximálně žádná závist s vyloučením jednoho předmětu (slabší požadavek než BE1).
EP = Pareto efektivní (PE = anglicky Pareto-efficient ).

název	Počet účastníků	Vchod	Předvolby	Počet žádostí	Spravedlnost	Účinnost	Komentáře
Prořezávání	2	Objednané sady	Přísně monotónní	$2^{m}$	B Z	Kompletní	Pokud a pouze v případě, že existuje kompletní distribuce KB
AL postup	2	Objednané předměty	Slabé aditivum	$Poly(m)$	Pochopitelně - BZ	Částečná, ale distribuce není Pareto ovládána jiným ZBZ
Nastavitelný vítěz	2	Oceňování objektů	Přísada	$Poly(m)$	znalý a nestranný	EP	Jeden objekt lze sdílet
kruhové plánování	$n$	Objednané předměty	Slabé aditivum	$m$	Pochopitelně - BZ1	Kompletní
Cykly závisti	$n$	Objednané sady	monotónní	$O(mn^{3})$	BZ1	Kompletní
mechanismus P-CRRD	$n$	Objednané sady	Žádný	?	BZ1, a - maximalizace podílů $(n+1)$	Částečné, ale ES ve vztahu k distribuovaným objektům	Přibližně strategicky nezranitelný , pokud je tam mnoho agentů.
Maximální Nashova pohoda [9]	$n$	Oceňování objektů	Přísada	NP-tvrdé (ale existují ve speciálních případech aproximace)	BZ1 a přibližně -maximalizace podílů $n$	EP	Se submodulárními užitkovými funkcemi je rozvod EF a PBZ1.

Viz také

Dalším kritériem spravedlnosti je maximalizace podílů .

Poznámky

↑ Doslova - distribuce objektů bez závisti, což je obecně matoucí - právě závist je hlavním faktorem takového rozložení.
↑ Brandt, Conitzer, Endriss et al., 2016 , str. 296–297.
↑ Bouveret, Endriss, Lang, 2010 , str. 387–392.
↑ Brandt, Conitzer, Endriss et al., 2016 , str. 300–310.
↑ 1 2 3 Lipton, Markakis, Mossel, Saberi, 2004 , str. 125.
↑ Bouveret, Lang, 2008 , str. 525–564.
↑ De Keijzer, Bouveret, Klos, Zhang, 2009 , str. 98.
↑ 1 2 Budish, 2011 , str. 1061–1103.
↑ 1 2 3 4 5 Caragiannis, Kurokawa et al., 2016 , str. 305.
↑ Graham, 1969 , s. 416–429.
↑ Nguyen, Rothe, 2014 , str. 54–68.
↑ Dickerson, Goldman a kol., 2014 , s. 1405–1411.

Literatura

Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Handbook of Computational Social Choice . - Cambridge University Press, 2016. - ISBN 9781107060432 .
Sylvain Bouveret, Ulle Endriss, Jérôme Lang. Fair Division Under Ordinal Preferences: Computing Envy-Free Allocations of Invisible Goods // ECAI 2010. - 2010. - pp. 387–392.
Bouveret S., Lang J. Efektivita a nezávist ve spravedlivém rozdělení nedělitelného zboží: Logická reprezentace a složitost // JAIR. - 2008. - T. 32 . - doi : 10.1613/jair.2467 .
Bart De Keijzer, Sylvain Bouveret, Tomas Klos, Yingqian Zhang. O komplexnosti efektivity a nezávisti při spravedlivém dělení nedělitelného zboží s aditivními preferencemi // Algorithmic Decision Theory. - 2009. - T. 5783. - (Poznámky z přednášek z informatiky). - ISBN 978-3-642-04427-4 . - doi : 10.1007/978-3-642-04428-1_9 .
Eric buddhista. Problém kombinatorického přiřazení: Přibližná konkurenční rovnováha ze stejných příjmů // Journal of Political Economy. - 2011. - T. 119 , č. 6 . - doi : 10.1086/664613 .
Ioannis Caragiannis, David Kurokawa, Herve Moulin, Ariel D. Procaccia, Nisarg Shah, Junxing Wang. Unreasonable Fairness of Maximum Nash Welfare // Sborník z konference ACM o ekonomii a počítání v roce 2016 - EC '16 . - 2016. - S. 305. - ISBN 9781450339360 . - doi : 10.1145/2940716.2940726 .
Lipton RJ, Markakis E., Mossel E., Saberi A. O přibližně spravedlivých alokacích nedělitelného zboží // Sborník příspěvků z 5. konference ACM o elektronickém obchodování - EC '04. - 2004. - ISBN 1-58113-771-0 . doi : 10.1145 / 988772.988792 .
Graham RL Bounds on Multiprocessing Timing Anomálie // SIAM Journal on Applied Mathematics. - 1969. - T. 17 , no. 2 . - doi : 10.1137/0117039 .
Trung Thanh Nguyen, Jörg Rothe. Minimalizace závisti a maximalizace průměrného Nashova sociálního blahobytu při přidělování nedělitelných statků // Diskrétní aplikovaná matematika. - 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 // In Proceedings of the Twenty-8th AAAI Conference on Artificial Intelligence (2014). — 2014. Odkaz ACM