Efektivní přibližně spravedlivé přidělování položek - Efficient approximately-fair item allocation

tento článek je sirotek, jako žádné další články odkaz na to. Prosím zavést odkazy na tuto stránku z související články; zkuste Najít odkaz nástroj pro návrhy. (Březen 2020)

Při přidělování objektů mezi lidi s různými preferencemi jsou dva hlavní cíle Paretova účinnost a spravedlnost. Protože objekty jsou nedělitelné, nemusí existovat žádné spravedlivé rozdělení. Například pokud je jeden dům a dva lidé, každé přidělení domu bude nespravedlivé vůči jedné osobě. Proto bylo studováno několik běžných aproximací, jako např maximální podíl spravedlnost (MMS), závistivost až na jednu položku (EF1), proporcionalita až na jednu položku (PROP1) a ekvitabilita až na jednu položku (EQ1). Problém efektivní přibližně spravedlivé rozdělení položek je najít alokaci, která je obojí Pareto-efektivní (PE) a splňuje jeden z těchto pojmů spravedlnosti. Problém byl poprvé představen v roce 2016^[1] a od té doby přitahuje značnou pozornost.

Nastavení

Existuje konečná sada objektů označená M. Existují n agenti. Každý agent i má hodnotovou funkci PROTI_i, který přiřadí hodnotu každé podskupině objektů. Cílem je rozdělení M do n podmnožiny, X₁,...,X_na uveďte každou podmnožinu X_i agentovi i, takže alokace je obojí Pareto-efektivní a přibližně spravedlivé. Existují různé představy o přibližné spravedlnosti.

Efektivní alokace bez závisti

Volá se alokace bez závisti (EF) pokud je pro každého agenta přesvědčen, že hodnota jeho podílu je minimálně stejně vysoká jako u jakéhokoli jiného agenta. To se nazývá bez závisti až na jednu položku (EF1) pokud pro každé dva agenty i a j, pokud je ze svazku j odstraněna nanejvýš jedna položka, pak j nezávidím j. Formálně:

• ${ displaystyle forall i, j: ~~~ existuje Y subseteq X_ {j}: ~~~ | Y | leq 1, ~~~ V_ {i} (X_ {i}) geq V_ {i } (X_ {j} setminus Y)}$

Některé rané algoritmy by mohly najít přibližně spravedlivou alokaci, která uspokojí slabou formu efektivity, ale ne PE.

• The každý s každým postup vrací kompletní alokaci EF1 s doplňkové nástroje. The graf závisti postup vrací kompletní alokaci EF1 pro libovolné monotónní preferenční vztahy.^[2] Oba zaručeně vrátí alokaci bez cyklů závisti. Není však zaručeno, že alokace bude Pareto-efektivní.
• The Přibližný mechanismus CEEI vrací částečnou alokaci EF1 pro libovolné preferenční vztahy. Je to PE w.r.t. přidělené objekty, ale ne PE w.r.t. všechny objekty (protože některé objekty mohou zůstat nepřidělené).^[3]

To vyvolalo otázku nalezení alokace, která je jak PE, tak EF1.

Maximum Nash Welfare pravidlo

Caragiannis, Kurokawa, Moulin, Procaccia, Shah a Wang^[1] jako první prokázali existenci alokace PE + EF1. Dokázali to, když to mají všichni agenti nástroje pro pozitivní aditiva, každá alokace, která maximalizuje produkt nástrojů (také známý jako Nash blahobyt) je EF1. Protože je zřejmé, že maximalizační alokace je PE, následuje existence PE + EF1 alokace.

Zatímco alokace max-produktu má žádoucí vlastnosti, nelze jej vypočítat v polynomiálním čase: nalezení alokace max-produktu je NP-tvrdé^[4] a dokonce APX-tvrdé.^[5] To vedlo k různým pracím, které se pokoušely přiblížit maximální produkt se zlepšením aproximačních faktorů:

• Cole a Gkatzelis^[6] představil 2,89-faktorovou aproximaci.
• Amari, Gharan, Saberi a Singh^[7] představil aproximaci e-faktoru.
• Cole, Devanur, Gkatelis, Jain, Mai, Vazirani a Yazdanbod^[8] představil 2-faktorovou aproximaci.

Tyto aproximace však nezaručují ani PE, ani EF1. Naproti tomu algoritmus zvyšování cen (viz níže) zaručuje PE, EF1 a přibližnou hodnotu 1,45 k maximálnímu produktu.

Řešení max-product je obzvláště přitažlivé, když jsou ocenění binární (hodnota každé položky je buď 0 nebo 1):

• Amanatidis, Birmpas, Filos-Ratsikas, Hollender a Voudouris^[9] dokázat, že s binárními oceněními je max-produktovým řešením nejen EF1, ale také EFX (bez závisti až k dobrému). To platí vždy, když hodnota každé položky může nabývat jedné ze dvou hodnot - ne nutně 0 nebo 1. S obecnými hodnotami aditiv max-product neznamená EFX, ale implikuje jeho přirozené zobecnění.
• Halpern, Procaccia, Psomas a Shah^[10] dokázat, že s binárními hodnotami lze pravidlo max-produktu s lexikograficky tie-breaking vypočítat v polynomiálním čase a je také odolný vůči skupinové strategii.

Neaditivní ocenění

Pokud nástroje agentů nejsou aditivní, řešení maximálního produktu nemusí být nutně EF1; ale pokud jsou nástroje agentů alespoň submodulární, řešení max-product splňuje slabší vlastnost zvanou Marginal-Envy-Freeness except-1-item (MEF1): to znamená, že každý agent i si váží svého svazku minimálně stejně jako mezní užitečnost of (svazek j, z kterého byla odstraněna nejlepší položka). Formálně:^[1]

• ${ displaystyle forall i, j: ~~~ existuje Y subseteq X_ {j}: ~~~ | Y | leq 1, ~~~ V_ {i} (X_ {i}) geq V_ {i } (X_ {i} cup (X_ {j} setminus Y)) - V_ {i} (X_ {i})}$

Podobné aproximace byly nalezeny pro obecnější obslužné funkce:

• Bei, Garg, Hoefer a Mehlhorn^[11] a Anari, Mai, Gharan a Vazirani^[12] studujte trhy s více jednotkami každého druhu zboží, kde jsou ocenění oddělitelná po částech lineární konkávní. To znamená, že užitečnost svazku s různými druhy položek je součtem nástrojů pro každý jednotlivý druh položky (to je význam „oddělitelné“), ale pro každý druh položky má ocenění klesající mezní pomůcky (toto je význam „po částech lineární konkávní“). Dávají 2-přiblížení k max-produktu.
• Ortega^[13] studuje trh s více jednotkami s binárními oceněními. Dokazuje, že rovnostářské pravidlo je Lorenz dominantní (vlastnost silnější než leximin-optimality), jedinečná v nástrojích a odolný vůči skupinové strategii.
• Garg, Hoefer a Mehlhorn^[14] studie ocenění aditivní k rozpočtu - podtřída submodulárních utilit. Dávají (2,404 + ε) - přiblížení k maximálnímu produktu v časovém polynomu ve velikosti vstupu a 1 /ε.
• Benabbou, Chakraborty, Igarashi a Zick^[15] studie submodulární nástroje s binárními marginálními zisky (tj. každá položka přidává k hodnotě každého balíčku buď 0 nebo 1). Dokazují, že s takovými oceněními jsou alokace maximálního produktu i leximinu EF1 a maximalizují utilitární blahobyt (součet utilit).
• Babaioff, Ezra a Feige^[16] také studovat submodulární nástroje s binárními („dichotomickými“) mezními zisky. Představují deterministický pravdivý mechanismus který vydává a Lorenz dominantní alokace, což je tedy EFX a max-product.

Smíšená ocenění

Martin a Walsh^[17] ukázat, že u „smíšené manny“ (- aditivní ocenění, která mohou být pozitivní i negativní), maximalizace produktu utilit (nebo minimalizace produktu minus utilities) nezaručuje EF1. Rovněž dokazují, že přidělení EFX3 nemusí existovat ani u identických obslužných programů. S terciárními nástroji však vždy existují přidělení EFX a PO nebo přidělení EFX3 a PO; a se stejnými obslužnými programy vždy existují přidělení EFX a PO. Pro tyto případy existují algoritmy polynomiálního času.

Algoritmus zvyšování cen

Barman, Krishanmurthy a Vaish^[18] představil a pseudo-polynomiální čas algoritmus pro zjištění alokací PE + EF1 pro pozitivní aditivní ocenění. Dokázali následující výsledky.

• Algoritmus najde alokaci PE + EF1 v čase O (poly (m,n,proti_max)), kde m je počet objektů, n počet agentů, a proti_max největší hodnota položky (všechna ocenění jsou celá čísla).
• Stejný algoritmus poskytuje aproximaci 1,45 k maximálnímu blahu Nash.
• Algoritmus také dokazuje existenci alokace, která je EF1 i částečně Paretova optima.

Základní pojmy

Jejich algoritmus je založen na pojmu konkurenční rovnováha v Fisherův trh. Využívá následující koncepty.

• Přibližná alokace EF1: Vzhledem k konstantní E > 0, přidělení je E-EF1, pokud splňuje podmínku EF1 až do multiplikativní konstanty (1+E). Formálně:
  • ${ displaystyle forall i, j: ~~~ existuje Y subseteq X_ {j}: ~~~ | Y | leq 1, ~~~ (1 + e) ​​ cdot V_ {i} (X_ {i }) geq V_ {i} (X_ {j} setminus Y)}$
• Cenový vektor: vektor přiřazující cenu (skutečné číslo) každé položce.
• Poměr Bang-for-Buck: pro agenta i a objekt Ó, jedná se o poměr ocenění agenta položky k ceně položky: proti_ij / p_j.
• Nastavena maximální cena za dolar (MBB): pro agenta i, je to sada objektů maximalizujících jeho poměr bang-for-buck (vzhledem k cenovému vektoru p).
• Přidělení MBB: přidělení, ve kterém každý agent přijímá pouze objekty ze své sady MBB. V alokaci MBB každý agent maximalizuje svou užitečnost vzhledem k jeho rozpočtu (ale alokace MBB je silnější podmínkou). The první věta o blahobytu znamená, že přidělení MBB je částečně Paretova optima.
• Přidělování bez závisti (pEF): alokace X, ve které pro každé dva agenty i.j, cena X_i (nazývaný „příjem“ i) je přinejmenším stejně velký jako cena X_j. To znamená, že všechny příjmy jsou totožné. Navíc je to alokace, která je MBB i pEF bez závisti, protože každý agent maximalizuje svou užitečnost vzhledem k jeho příjmu a všichni ostatní agenti mají stejný příjem.
• Přidělení ceny bez závisti bez výjimky (pEF1): alokace, ve které pro každé dva agenty i.j, cena p (X_i) je přinejmenším stejně velká jako cena Xj bez jeho nejdražší položky. To ano ne znamenat, že příjmy jsou totožné. Alokace, která je MBB i pEF1, je však také EF1.^{[18]:Lem. 4.1}
• E- alokace pEF1, pro nějakou konstantu E > 0: alokace, ve které pro každé dva agenty i.j, produkt (1+E) · P (X_i) je přinejmenším stejně velký jako p (Xj) bez jeho nejdražší položky. Všimněte si, že E-pEF1 podmínka je slabší, když E je větší. Zejména je alokace pEF1 E-pEF1 pro každého E > 0, ale opak není pravdou. Alokace, která je MBB i E-pEF1 je také E-EF1.^{[18]:Lem. 4.1}
• Nejméně: Vzhledem k alokaci a cenovému vektoru je to agent i takový, že p (X_i) je nejmenší (vazby jsou přerušeny na základě nějakého předem stanoveného pořadí agentů). Všimněte si, že alokace je E-pEF1, pokud E-pEF1 podmínka je splněna pro nejméně výdaje (jako agent i).
• Hierarchie MBB agenta i (vzhledem k umístění X a cenový vektor p): stromová struktura postavená následujícím způsobem.
  • Dejte agenta i v kořenovém adresáři (tomu se říká úroveň 0).
  • Připojte se k agentovi i všechny objekty v jeho sadě MBB (vzhledem k cenovému vektoru p).
  • Připojte se ke každému objektu Ó agent, který to vlastní X, pokud ještě není ve stromu (nazývá se to úroveň 1)
  • Připojte se ke každému agentovi na úrovni 1, ke všem objektům v jeho sadě MBB, které jsou ještě ve stromu.
  • Pokračujte v přidávání agentů a objektů střídavě podobným způsobem: pro každého agenta přidejte jeho objekty MBB; pro každou položku přidejte vlastnícího agenta.
• Rušitel (vzhledem k umístění X a cenový vektor p): agent h který porušuje podmínku pEF1 w.r.t. nejméně utrácející i. Takže cena X_h, i když je z něj odstraněna nejdražší položka, je vyšší než p(X_i). Podobně, E-rušitel je agent, který porušuje E-pEF1 podmínka w.r.t. nejméně utrácející.
• Porušovatel cesty (dané přidělení X a cenový vektor pa hierarchie MBB): agent h který se objeví na MBB hierarchii nejméně vynaložených prostředků i, a částečně porušuje podmínku pEF1 w.r.t. i. Podrobněji: Předpokládejme, že na okraji hierarchie MBB existuje cesta z nejméně vynaložených prostředků i namítat Ó, a pak hrana od objektu Ó agentovi h (tohle znamená tamto X_h obsahuje Ó). Pokud p (X_h \ {Ó}) > p(X_i), pak h je narušovatel cesty. Všimněte si, že každý porušovatel je narušovatel cesty, ale opak není pravdou. Podobně, pokud p (X_h \ {Ó}) > (1+E)·p(X_i), pak h je Eporušovatel cesty.

Algoritmus

Vzhledem k parametru ECílem algoritmu je najít alokaci, která je fPO i 3E-pEF1. Probíhá v několika fázích.

Fáze 1: Vytvoření počáteční alokace MBB + cena (X, p).

• Jedním ze způsobů, jak to udělat, je dát každému objektu Ó agentovi i kdo si toho váží nejvíce (svévolně přetrhává vazby) a určuje cenu Ó na proti_{já, o}. Tím je zaručeno, že pro každého agenta je cena za všechny objekty v jeho balíčku přesně 1 a cena za všechny objekty v ostatních balících je maximálně 1. Proto je alokace MBB, tedy je také fPO.
• Pokud je alokace 3E-pEF1, vraťte jej; jinak pokračujte fází 2.

Fáze 2: Odstraňte závislost na ceně v hierarchii MBB:

• Vytvořte hierarchii MBB s nejnižší spotřebou, vzhledem k aktuální (X, p).
• Pro L = 1,2,...:
  • Pro každého agenta h v úrovni L stromu:
    • Li h je E-path-violator podél cesty: i → ... → h ' → Ó → h, poté přeneste objekt Ó od agenta h agentovi h ' (Všimněte si, že alokace zůstává MBB). Restartujte fázi 2.
• Jakmile už žádné nejsou E-cesta-narušitelé:
  • Pokud je alokace 3E-pEF1, vraťte jej; jinak pokračujte fází 3.

Fáze 3: Zvyšte ceny. Zvyšte ceny všech objektů v hierarchii MBB o stejný multiplikativní faktor, dokud nenastane jedna z následujících tří věcí:

1. Změní se identita nejméně vynaložených prostředků. K tomu může dojít, pokud se některý agent mimo hierarchii (jehož položky nezvyšují cenu) stane nejméně utráceným. V tomto případě restartujeme ve fázi 2.
2. Do hierarchie MBB bude přidán nový objekt. K tomu může dojít, protože, když se ceny objektů v hierarchii zvýší o faktor r, poměr BB objektů v hierarchii se sníží o r, zatímco poměr BB objektů mimo hierarchii zůstává stejný. Proto kdy r je dostatečně velký, stane se některý vnější objekt MBB pro některého agenta hierarchie. I v tomto případě restartujeme ve fázi 2.
3. Aktuální alokace X se stává 3E-pEF1. To se může stát, protože když se zvýší ceny objektů v hierarchii, zvýší se příjem nejméně vynaložených prostředků, zatímco příjem agentů mimo hierarchii zůstane konstantní. Proto kdy r je dostatečně velký, je možné, že 3E-pEF1 podmínka je splněna w.r.t. nejméně utrácející. V tomto případě vrátíme alokaci X a nová cena p.

Důkaz správnosti

Nejprve předpokládejme, že výše uvedený algoritmus je spuštěn v instanci, ve které jsou všechny hodnoty mocninami (1+E), pro některé pevné E>0.

• Prvním úkolem je dokázat, že algoritmus končí. Lze prokázat, že když jsou všechna ocenění pravomocí (1+E), algoritmus končí v čase Ó(poly (m, n, 1 /E, ln (PROTI_max)), kde PROTI_max je největší hodnota objektu pro agenta.^[19]:23–29
• Počáteční alokace je alokace MBB a všechny operace tuto podmínku udržují. Proto je vrácená alokace MBB, takže je také fPO.
• Podle podmínek ukončení, kdykoli se algoritmus ukončí, je vrácená alokace 3E-pEF1, takže je také 3E-EF1.

Nyní předpokládejme, že máme instanci s obecnými oceněními. Výše uvedený algoritmus spustíme na a zaoblená instance, kde je každé ocenění zaokrouhleno nahoru na nejbližší mocninu (1+E). Všimněte si, že pro každého agenta i a namítat Ó, zaokrouhlená hodnota PROTI_i'(Ó) je mezi PROTI_i(Ó) a (1+E)PROTI_i(Ó).

• V předchozím odstavci je výsledná alokace fPO a 3E-EF1 s ohledem na zaoblenou instanci.
• Pro každého E dostatečně malý (zejména méně než 1/6 m³ PROTI_max⁴), alokace, která je fPO pro zaoblenou instanci, je PO pro původní instanci.^[19]:29–34
• Kombinací 3E-EF1 záruka pro zaokrouhlenou instanci, s hranicí pro zaokrouhlování získáme, že vrácená alokace splňuje následující přibližnou podmínku EF1:
  • ${ displaystyle forall i, j: ~~~ existuje C subseteq X_ {j}: ~~~ | C | leq 1, ~~~ (1 + e) ​​ cdot (1 + 3e) cdot V_ {i} (X_ {i}) geq V_ {i} (X_ {j} setminus C)}$
• Pro dostatečně malé E, produkt (1+E)(1+3E) je maximálně (1 + 7E). Proto je alokace 3E-EF1 pro zaoblenou instanci je 7E-EF1 pro původní instanci.
• Protože původní ocenění jsou celá čísla, je-li e dostatečně malé, 7E-EF1 alokace je také EF1.
• Výsledná alokace je tedy PO + EF1 pro původní instanci.

Zobecněný upravený vítěz

Aziz, Caragiannis, Igarashi a Walsh^[20]:4 rozšířil podmínku EF1 na smíšené ocenění (objekty mohou mít pozitivní i negativní obslužnost). Představili zevšeobecnění upravený postup výherce, pro zjištění alokace PO + EF1 pro dva agenty v čase O (m²).

Efektivní přibližně proporcionální alokace

Přidělení objektů je úměrný^{[nutná disambiguation ]}(PODPĚRA) pokud si každý agent ocení svůj podíl alespoň 1 /n hodnoty všech položek. To se nazývá úměrný až jedna položka (PROP1) pokud pro každého agenta i, pokud je do balíčku přidána maximálně jedna položka i, pak i oceňuje balíček alespoň 1 /n z celkového počtu. Formálně pro všechny i (kde M je sada veškerého zboží):

• ${ displaystyle existuje Y subseteq M setminus X_ {i}: ~~~ | Y | leq 1, ~~~ V_ {i} (X_ {i} cup Y) geq V_ {i} (M ) / n}$.

Podmínku PROP1 zavedl Conitzer, Freeman a Shah^[21] v kontextu spravedlivého veřejného rozhodování. Dokázali, že v tomto případě vždy existuje alokace PE + PROP1.

Protože každá alokace EF1 je PROP1, existuje i PE + PROP1 alokace v nedělitelné alokaci položek; otázkou je, zda lze takové alokace najít rychlejšími algoritmy než pro PE + EF1.

Barman a Krishnamurthy^[22] představil algoritmus strongy-polynomial-time, který našel alokaci PE + PROP1 pro zboží (objekty s pozitivním užitkem).

Branzei a Sandomirskiy^[23] rozšířil podmínku PROP1 na práce (objekty se zápornou užitečností). Formálně pro všechny i:

• ${ displaystyle existuje Y subseteq X_ {i}: ~~~ | Y | leq 1, ~~~ V_ {i} (X_ {i} setminus Y) geq V_ {i} (M) / n }$.

Představili algoritmus, který našel přidělení prací PE + PROP1. Algoritmus je silně polynomiálního času, pokud je buď počet objektů, nebo počet agentů (nebo obojí) pevný.

Aziz, Caragiannis, Igarashi a Walsh^[20] rozšířil podmínku PROP1 na smíšené ocenění (objekty mohou mít pozitivní i negativní obslužnost). V tomto nastavení se přidělení nazývá PROP1, pokud pro každého agenta i, pokud odstraníme jednu zápornou položku ze svazku i nebo přidáme jednu kladnou položku do svazku i, pak je i pomůcka alespoň 1 /n z celkového počtu. Jejich algoritmus Generalized Adjusted Winner najde alokaci PE + EF1 pro dva agenty; taková alokace je také PROP1.

Aziz, Moulin a Sandomirskiy^[24] představil algoritmus silně polynomiálního času pro nalezení alokace, která je zlomkově PE (silnější než PE) a PROP1, s obecnými smíšenými oceněními, i když počet agentů nebo objektů není pevný, a to i v případě, že agenti mají různá oprávnění .

Efektivní přibližně spravedlivá alokace

Alokace objektů se nazývá spravedlivý (EQ) pokud je subjektivní hodnota všech agentů stejná. Motivace ke studiu tohoto pojmu pochází z experimentů, které ukazují, že lidské subjekty upřednostňují spravedlivé alokace před závidějícími.^[25] Volá se alokace spravedlivé až pro jednu položku (EQ1) pokud je pro každé dva agenty i a j odstraněna maximálně jedna položka ze svazku j, potom je subjektivní hodnota i alespoň ta z j. Formálně pro všechny i, j:

• ${ displaystyle existuje Y subseteq X_ {j}: ~~~ | Y | leq 1, ~~~ V_ {i} (X_ {i}) geq V_ {j} (X_ {j} setminus Y )}$.

Silnější představa je spravedlivé až k jakékoli položce (EQx): pro každé dva agenty i a j, pokud žádný jedna položka je odstraněna ze svazku j, pak subjektivní hodnota i je alespoň ta z j:

• ${ displaystyle forall y in X_ {j}: ~~~ V_ {i} (X_ {i}) geq V_ {j} (X_ {j} setminus {y })}$.

Alokace EQx byly nejprve studovány Gourves, Monnot a Tlilane, kdo použil jiný výraz: „téměř bez žárlivosti“.^[26]:3 Dokázali, že vždy existuje částečná alokace EQx, a to i při dalším požadavku, že sjednocení veškerého alokovaného zboží je a základ daného matroidu. Použili podobný algoritmus postup grafu závisti. Suksompong^[27] prokázal, že alokace EQ1 existuje i při dalším požadavku, že všechna alokace musí být sousedící podmnožiny řádku.

Freeman, Sidkar, Vaish a Xia^[28] prokázal následující silnější výsledky:

• Pokud jsou všechna ocenění přísně kladná, vždy existuje alokace PE + EQx a existuje algoritmus pseudopolynomiálního času který najde alokaci PE + EQ1.
• Když mohou být některá ocenění nulová, nemusí dokonce existovat alokace PE + EQ1 a rozhodnutí, zda PE + EQ / EQ1 / EQx existuje, je silně NP-tvrdé.
• Alokace PE + EQ1 + EF1 nemusí existovat. Rozhodování o tom, zda existuje, je silně NP-tvrdé obecně, ale polynomiálně-časově řešitelný s binárními (0 nebo 1) oceněními.

Algoritmy pro malý počet agentů

Bredereck, Kaczmarcyk, Knop a Niedermeier^[29] prostudujte prostředí, kde je málo agentů (malých n) a několik typů položek (malé m), je obslužný program pro každý typ položky horně ohraničen (pomocí PROTI), ale u každého typu může být mnoho položek. Pro toto nastavení dokazují následující meta-teorém (Věta 2): Vzhledem k kritériu účinnosti E a kritériu spravedlnosti F, pokud ${ displaystyle n + u _ { max} + m}$ je pevná, pak je možné v polynomiálním čase rozhodnout, zda existuje alokace, která je E-efektivní i F-fér, pokud E a F splňují následující vlastnosti:

• Spravedlnost: Otázku, zda existuje alokace F-fair, lze modelovat pomocí celočíselný lineární program s pevným rozměrem.
• Účinnost: Otázku, zda existuje alokace, která E dominuje jiné dané alokaci, lze modelovat pomocí celočíselný program jehož dvojí hloubka stromu, a absolutní hodnota největšího koeficientu, jsou horní hranicí určité funkce ${ displaystyle f (n, u _ { max})}$.

Poté dokazují, že tyto vlastnosti splňuje několik společných kritérií spravedlnosti a účinnosti, včetně:

• Pojmy spravedlnosti: envy-freeness, EF1, EFx, graph-EF (when the agents envy only their Neighbors on a fixed graph), egalitarian, maximin-share, and average-group-envy-freeness (where each group of agents runs its share as aritmetický průměr utilit členů).
• Pojmy účinnosti: Pareto-účinnost, graf Pareto-účinnost (kde Pareto-nadvláda uvažuje pouze výměny mezi sousedy na pevném grafu) a skupinová-Pareto-účinnost. Přidělení X tak jako k-skupina-Pareto-efektivní (GPE_k) pokud neexistuje žádná jiná alokace Y to je přinejmenším stejně dobré (aritmetickým průměrem nástrojů) pro všechny skupiny velikostí ka přísně lepší pro alespoň jednu skupinu velikostí k. Všimněte si, že GPE₁ je ekvivalentní Paretově efektivitě. GPE_n je ekvivalentní utilitární-maximální alokaci, protože pro velkou skupinu G velikosti n, aritmeticko-průměrná utilita je ekvivalentní součtu utilit všech agentů. Pro všechny k, GPE_{k + 1} znamená GPE_k.

Runtime jejich algoritmu je polynomiální v časech velikosti vstupu (v bitech) ${ displaystyle d ^ {2.5d}}$, kde d je počet proměnných ve výsledném ILP, což je ${ Displaystyle d = m (n + 1) + m (n + 1) cdot (4 cdot (4n cdot V + 1) ^ {n}) ^ {m (n + 1)}}$.^[29]:sub.4.3

Reference

Viz také

• Efektivní rozdělení bez závisti - za dělitelné zdroje. Přibližování není nutné, protože je možná přesná spravedlnost.
• Přidělení položek bez závisti - bez požadavku na PE.
• Harmonie pronájmu - s dalším omezením, že každý agent musí dostat jednu položku.