Přidělení položek bez závisti - Envy-free item allocation - Wikipedia

Přidělení položky bez závisti (EF) je spravedlivé rozdělení položek problém, ve kterém je kritérium spravedlnosti závistlivost - každý agent by měl dostat balíček, o kterém se domnívají, že je alespoň stejně dobrý jako balíček jiného agenta.^{[1]:296–297}

Protože položky jsou nedělitelné, přiřazení EF nemusí existovat. Nejjednodušší případ je, když existuje jedna položka a alespoň dva agenti: pokud je položka přiřazena jednomu agentovi, druhý bude závidět. Postupy dělení proto poskytují různé druhy relaxace.

Hledání alokace bez závisti, kdykoli existuje

Uspořádání preferencí na svazcích: závistivost

The postup podříznutí najde kompletní EF alokaci pro dva agenty, pokud a pouze - pokud takové přidělení existuje. Vyžaduje, aby agenti hodnotili svazky položek, ale nevyžaduje základní informace o nástroji. Funguje vždy, když jsou preferenční vztahy agentů přísně monotónní, ale nemusí předpokládat, že jsou responzivní preference. V nejhorším případě budou muset agenti řadit všechny možné balíčky, takže doba běhu může být v počtu položek exponenciální.

Přednostní uspořádání položek: nutné / možná závistivost

Pro lidi je obvykle snazší hodnotit jednotlivé položky než hodnotit balíčky. Za předpokladu, že to mají všichni agenti responzivní preference, je možné pozvednout hodnocení položek na částečné hodnocení svazků. Pokud je například pořadí položek w> x> y> z, pak odezva znamená, že {w, x}> {y, z} a {w, y}> {x, z}, ale nic neznamenají o vztahu mezi {w, z} a {x, y}, mezi {x} a {y, z} atd.

Vzhledem k pořadí položek:

• Přidělení je nutně bez závisti (NEF), pokud je podle závisti bez závisti Všechno responzivní hodnocení balíčků v souladu s hodnocením položek;
• Přidělení je možná bez závisti (PEF), pokud je podle závisti bez závisti aspoň jeden responzivní hodnocení balíků v souladu s hodnocením položek;
• Přidělení je nutně Pareto-optimální (NPE), pokud je Pareto-optimální podle Všechno responzivní hodnocení balíčků v souladu s hodnocením položek;
• Přidělení je možná Pareto-optimální (PPE), pokud je Pareto-optimální podle aspoň jeden responzivní hodnocení balíků v souladu s hodnocením položek.

Bouveret a Endriss a Lang^[2] prostudujte si algoritmické otázky hledání alokace NEF / PEF s další podmínkou účinnosti, zejména úplnosti nebo NPE nebo PPE. Obecně je PEF výpočetně snadná, zatímco NEF výpočetně náročná.

Rozhodování, zda existuje alokace EF

Prázdná alokace je vždy EF. Pokud ale chceme kromě EF ještě nějakou efektivitu, pak se problém s rozhodnutím stane výpočetně těžkým:^{[1]:300–310}

• Rozhodování, zda EF a kompletní alokace existuje NP kompletní. To platí, i když existují pouze dva agenti, a to i v případě, že jsou jejich nástroje aditivní a identické, protože v tomto případě je zjištění přidělení EF ekvivalentní řešení problém s oddílem.^[3]
• Rozhodnutí, zda existuje spravedlivá alokace, vyžaduje exponenciální komunikaci (v počtu zboží), pokud existují více než dva agenti. Pokud existují dva agenti, komunikační komplex závisí na konkrétních kombinacích parametrů.^[4]
• Rozhodování, zda EF a Pareto efektivní alokace existuje nad NP: je ${ displaystyle Sigma _ {2} ^ { textrm {P}}}$-kompletní dokonce s dichotomické nástroje^[5] a dokonce s doplňkové nástroje.^[6] (${ displaystyle Sigma _ {2} ^ { textrm {P}}}$ je třída problémů, které lze vyřešit v nedeterministickém čase vzhledem k věštbě, která dokáže vyřešit jakýkoli problém v NP).

Rozhodovací problém se může stát přijatelným, když jsou některé parametry problému považovány za pevné malé konstanty:^[7]

• Vzhledem k počtu objektů m jako parametr lze rozhodnout o existenci alokace PE + EF včas ${ displaystyle O ^ {*} (m ^ {2m})}$ pro aditivní nebo dichotomické nástroje. Pokud jsou obslužné programy binární a / nebo identické, runtime klesne na ${ displaystyle O ^ {*} (m ^ {m})}$. Tady notace ${ displaystyle O ^ {*}}$ skryje výrazy, které jsou polynomické v ostatních parametrech (např. počet agentů).
• Vzhledem k počtu agentů n jako parametr zůstává existence PE + EF alokace tvrdá. S dichotomickými nástroji je to NP dokonce těžké n=2.^[5] Nyní je však v NP a lze jej efektivně vyřešit pomocí NP Oracle (např. A SAT solver ). S ${ displaystyle n geq 5}$ agenti, to lze udělat s ${ displaystyle 2 ^ {n + 1}}$takové věštby, a přinejmenším ${ displaystyle 2 ^ {n-4}}$ věštby jsou potřeba, pokud P = NP. Díky doplňkovým nástrojům je to NP dokonce těžké n=2.^[5] Navíc je W [1] - kompletní w.r.t. počet agentů, i když jsou všechny obslužné programy identické a unárně zakódované.
• Vzhledem k počtu agentů n a největší nástroj PROTI jako parametry lze o existenci přidělení PE + EF rozhodnout včas ${ displaystyle O ^ {*} ((m cdot V + 1) ^ {n ^ {2}} cdot mn ^ {2})}$ pro použití doplňkových utilit dynamické programování.
• Vzhledem k počtu agentů n a počet úrovní služeb z jako parametry lze o existenci přidělení PE + EF pro identické pomocné nástroje rozhodnout pomocí celočíselný lineární program s ${ displaystyle d = n cdot z ^ {n}}$ proměnné; Lenstraův algoritmus umožňuje řešení takových ILP v čase ${ displaystyle O ^ {*} (d ^ {2.5d})}$.

Nalezení alokace s omezenou úrovní závisti

Mnoho postupů najde alokaci, která je „téměř“ bez závisti, tj. Úroveň závisti je omezená. Existují různé představy o „téměř“ závistivosti:

EF1 - bez závisti až na maximálně jednu položku

Volá se alokace EF1 pokud pro každé dva agenty A a B, pokud odstraníme maximálně jednu položku ze svazku B, pak A nezávidí B.^[8] Alokace EF1 vždy existuje a lze ji efektivně najít různými postupy, zejména:

• Když mají všichni agenti slabě aditivní inženýrské sítě, protokol každý s každým najde úplnou alokaci EF1. Slabá aditivita je nutná, protože každý agent by měl být schopen vybrat v každé situaci „nejlepší položku“.
• V obecnějším případě, když mají všichni agenti monotónně rostoucí pomůcky, postup grafu závisti najde kompletní alokaci EF1. Jediným požadavkem je, aby agenti mohli řadit balíčky položek. Pokud jsou ocenění agentů reprezentována a hlavní nástroj funkce, pak má záruka EF1 další výklad: číselná úroveň závisti každého agenta je nanejvýš maximální-mezní-užitečnost - největší mezní užitečnost jedné položky pro tohoto agenta.
• Pokud mají agenti libovolné nástroje (ne nutně aditivní nebo monotónní), Mechanismus A-CEEI vrací částečnou alokaci EF1. Jediným požadavkem je, aby agenti mohli řadit balíčky položek. Malý počet položek může zůstat nepřidělen a může být nutné přidat malý počet položek. Alokace je Pareto-efektivní s ohledem na alokované položky.
• The Maximum Nash Welfare Algoritmus vybírá úplnou alokaci, která maximalizuje produkt obslužných programů. Vyžaduje, aby každý agent poskytl číselné ocenění každé položky a předpokládá, že obslužné programy agentů jsou aditivní. Výsledná alokace je EF1 i Pareto-efektivní.^[9]
• Různé další algoritmy vracejí přidělení EF1, která jsou také Pareto-efektivní; vidět Efektivní přibližně spravedlivé přidělování položek.
• U dvou agentů s libovolným monotónním hodnocením nebo tří agentů s aditivním hodnocením lze alokaci EF1 vypočítat pomocí počtu logaritmických dotazů v počtu položek.^[10]
• U dvou agentů s libovolnými obslužnými funkcemi (ne nutně monotónními) lze alokaci EF1 nalézt v polynomiálním čase.^[11]
• Pro maximálně 4 agenty s libovolným monotónním oceněním, nebo n agenti se shodnými monotónními oceněními, vždy existuje přidělení EF1, které také je připojeno (když jsou položky předobjednány na lince, například domy na ulici). Důkaz používá podobný algoritmus jako Simmons – Su protokoly. Když tam jsou n > 4 agenti, není známo, zda existuje přidělená alokace EF1, ale připojená EF2 alokace vždy existuje.^[12]

EFx - bez závisti až na maximum jakékoli položky

Volá se alokace EFx pokud pro každé dva agenty A a B, pokud odstraníme žádný předmět ze svazku B, pak A nezávidí B.^[13] EFx je přísně silnější než EF1: EF1 nám umožňuje odstranit závist odstraněním položky nejcennější (pro A) ze svazku B; EFx vyžaduje, abychom odstranili závist odstraněním položky nejméně cenné (pro). Je známo, že v některých zvláštních případech existuje alokace EFx:

• Když tam jsou dva agenti, nebo když existují n agenti s stejná ocenění. V tomto případě leximin -optimální alokace je EFx a Pareto-optimální. K výpočtu však vyžaduje exponenciálně mnoho dotazů.^[14][11]
• Když tam jsou n agenti s aditivní ocenění, ale pro zboží existují nejvýše dvě různé hodnoty. V tomto případě je jakákoli alokace max-Nash-welfare EFx. Kromě toho existuje efektivní algoritmus pro výpočet alokace EFx (i když ne nutně max-Nash-welfare).^[15]
• Když tam jsou n agenti s aditivní ocenění, ale existují maximálně dva různé druhy ocenění.^[16]
• Když tam jsou tři agenti s aditivní ocenění. V tomto případě existuje algoritmus polynomiálního času.^[17]

Některé aproximace jsou známy:

• Přibližná alokace EFx 1/2 (která také splňuje jinou volanou koncepci přibližné spravedlnosti Maximin vědom) lze nalézt v polynomiálním čase.^[18]
• Přidělení EFx přibližné 0,618 (to je také EF1 a přibližné další volané pojmy spravedlnosti skupinový maximální podíl a párový maximální podíl ) lze nalézt v polynomiálním čase.^[19]
• Vždy existuje částečný Přidělení EFx, kde sociální péče Nash je alespoň polovina maximálního možného blahobytu Nash. Jinými slovy, po darování některých položek charitě lze zbývající položky přidělit způsobem EFx. Tato vazba je nejlepší možná. Na velkých trzích, kde je ocenění agenta pro každou položku relativně malé, dosahuje algoritmus EFx s téměř optimálním blahobytem Nash.^[20] Stačí darovat n-1 položek a žádný dar nezávidí sadu darovaných položek.^[21]

Je otevřenou otázkou, zda přidělení EFx existuje obecně. Nejmenší otevřený případ jsou 4 agenti s aditivním oceněním.

Na rozdíl od EF1, který vyžaduje počet logaritmických dotazů v počtu položek, může výpočet přidělení EFx vyžadovat lineární počet dotazů, i když existují dva agenti se stejnými hodnotami aditiv.^[10]

Další rozdíl mezi EF1 a EFx spočívá v tom, že počet přidělení EFX může být až 2 (pro libovolný počet položek), zatímco počet přidělení EF1 je vždy exponenciální v počtu položek.^[22]

EFm - přibližně bez závisti pro směs dělitelných a nedělitelných položek

Některé scénáře dělení zahrnují jak dělitelné, tak nedělitelné položky, jako jsou dělitelné pozemky a nedělitelné domy. Volá se alokace EFm pokud pro každé dva agenty A a B:^[23]

• Pokud svazek B obsahuje nějaké dělitelné zboží, pak A nezávidí B (jako při přidělení EF).
• Pokud svazek B obsahuje pouze nedělitelné zboží, pak A nezávidí B po odebrání maximálně jedné položky ze svazku B (jako v alokaci EF1).

Alokace EFm existuje pro libovolný počet agentů. Jeho nalezení však vyžaduje věštbu pro přesné rozdělení dortu. Bez tohoto věštce lze alokaci EFm vypočítat v polynomiálním čase ve dvou zvláštních případech: dva agenti s obecnými hodnotami aditiv nebo libovolný počet agentů s po částech lineárními hodnotami.

Na rozdíl od EF1, který je kompatibilní s Pareto-optimality, EFm může být s ním nekompatibilní.

Minimalizace poměru závisti

Vzhledem k přidělení X, definujte poměr závisti i v j tak jako:

${ displaystyle EnvyRatio (X, i, j): = max (1, {u_ {i} (X_ {j}) nad u_ {i} (X_ {i})})}$

takže poměr je 1, pokud i nezávidí j, a je větší, když i závidí jDefinujte poměr závisti úkolu jako:

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

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

Obecná ocenění

U obecných ocenění vyžaduje jakýkoli deterministický algoritmus, který počítá alokaci s minimálním poměrem závisti, řadu dotazů, které jsou v nejhorším případě exponenciální v počtu zboží.^[3]:3

Aditivní a identická ocenění

S aditivním a identickým oceněním:^[3]:4–6

• Následující chamtivý algoritmus najde alokaci, jejíž poměr závisti je maximálně 1,4násobek minima:^[24]
  1. Seřadit položky podle sestupné hodnoty;
  2. I když existuje více položek, dejte další položku agentovi s nejmenší celkovou hodnotou.
• Tady je PTAS pro minimalizaci poměru závisti. Navíc, když je počet hráčů konstantní, je zde FPTAS.

Aditivní a různá ocenění

S přísadou a různými oceněními:^[25]

• Pokud je počet agentů součástí vstupu, je nemožné získat v polynomiálním čase aproximační faktor lepší než 1,5, pokud P = NP.
• Když je počet agentů konstantní, je zde FPTAS.
• Když se počet agentů rovná počtu položek, existuje algoritmus polynomiálního času.

Nalezení částečné závisti bez přidělení

The AL postup najde přidělení EF pro dva agenty. Může se zbavit některých položek, ale konečná alokace je Pareto efektivní v následujícím smyslu: žádná jiná alokace EF není lepší pro jednu a slabě lepší pro druhou. Procedura AL vyžaduje, aby agenti hodnotili pouze jednotlivé položky. Předpokládá, že agenti mají responzivní preference a vrátí alokaci, která je nezbytně bez závisti (NEF).

The Upravený postup výherce vrátí kompletní a efektivní alokaci EF pro dva agenty, ale možná bude muset vyjmout jednu položku (alternativně jedna položka zůstane ve sdíleném vlastnictví). Vyžaduje, aby agenti hlásili číselnou hodnotu pro každou položku a předpokládá, že mají doplňkové nástroje

Existence alokací EF s náhodným hodnocením

Pokud agenti mají aditivní utilita funkce, které jsou čerpány z rozdělení pravděpodobnosti splňující některá kritéria nezávislosti, a počet položek je dostatečně velký vzhledem k počtu agentů, pak existuje EF alokace s vysokou pravděpodobností. Zejména:^[26]

• Pokud je počet položek dostatečně velký: ${ displaystyle m = Omega (n log n)}$, pak w.h.p. existuje EF alokace (pravděpodobnost jde na 1, zatímco m jde do nekonečna).
• Pokud počet položek není dostatečně velký, tj. ${ displaystyle m = n + o (n)}$, pak w.h.p. alokace EF neexistuje.

Závistivost a jiná kritéria spravedlnosti

• Každá alokace EF je min-max-fér. To vyplývá přímo z ordinálních definic a nezávisí to na aditivitě.
• Pokud mají všichni agenti aditivní utilita funkce, pak je také přidělení EF úměrný a max-min-veletrh. Jinak nemusí být alokace EF proporcionální a dokonce ani max-min spravedlivá.
• Každá alokace a konkurenční rovnováha ze stejných příjmů je také bez závisti. To platí bez ohledu na aditivitu.^[8]
• Každá Nash-optimální alokace (alokace, která maximalizuje produkt nástrojů) je EF1.^[13]
• Skupinová závist-bezstarostnost je posílení závisti-volnosti, které je použitelné jak na dělitelné, tak na nedělitelné předměty.

Vidět Spravedlivé přidělování položek pro podrobnosti a reference.

Souhrnná tabulka

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

• ${ displaystyle n}$ = počet agentů účastnících se rozdělení;
• ${ displaystyle m}$ = počet položek k rozdělení;
• EF = bez závisti, EF1 = bez závisti kromě 1 položky (slabší než EF), MEF1 = bez závisti bez kromě 1 položky (slabší než EF1).
• PE = Pareto-efektivní.

název	#partneri	Vstup	Předvolby	# dotazy	Spravedlnost	Účinnost	Komentáře
Podříznutí	2	Pořadí svazků	Přísně monotónní	${ displaystyle 2 ^ {m}}$	EF	Kompletní	Pokud a pouze - pokud existuje úplné přidělení EF
AL	2	Pořadí položek	Slabě aditivní	${ displaystyle Poly (m)}$	Nutně-EF	Částečné, ale ne Pareto ovládané jiným NEF
Upravený vítěz	2	Oceňování položek	Přísada	${ displaystyle Poly (m)}$	EF a spravedlivé	PE	Možná rozdělit jednu položku.
Každý s každým	${ displaystyle n}$	Pořadí položek	Slabě aditivní	${ displaystyle m}$	Nezbytně - EF1	Kompletní
Graf závisti	${ displaystyle n}$	Pořadí svazků	Monotónní	${ displaystyle O (mn ^ {3})}$	EF1	Kompletní
A-CEEI	${ displaystyle n}$	Pořadí svazků	Žádný	?	EF1 a ${ displaystyle (n + 1)}$-maximální podíl	Částečné, ale PE w.r.t. přidělené položky	Také přibližně odolný vůči strategii když je mnoho agentů.
Maximum-Nash-Welfare[13]	${ displaystyle n}$	Oceňování položek	Přísada	NP-tvrdý (ale ve zvláštních případech existují aproximace)	EF1 a přibližně -${ displaystyle n}$-maximální podíl	PE	U submodulárních utilit je alokace PE a MEF1.

Viz také

• Alokace položky na maximální podíl - jiné kritérium spravedlnosti.
• Harmonie pronájmu a Ceny bez závisti - dvě varianty, ve kterých je závistivosti dosaženo peněžními platbami.

Reference