Problém spravedlivého rozdělení objektů

Spravedlivé rozdělení objektů  je typem problému spravedlivého rozdělení , ve kterém jsou předměty, které je třeba rozdělit mezi účastníky, nedělitelné . Předměty by měly být rozděleny mezi partnery, kteří předměty hodnotí různě, a každý předmět by měl být předán jako celek jednomu účastníkovi. Tato situace nastává v několika scénářích reálného života:

Z nedělitelnosti předmětů vyplývá, že spravedlivé rozdělení nemusí být možné. Extrémním příkladem je případ, kdy existuje pouze jeden předmět (řekněme: dům), který je třeba předat jednomu účastníkovi, ale ostatní účastníci nebudou takové rozhodnutí považovat za spravedlivé. To je v kontrastu s problémem krájení dortu , kde lze objekt rozdělit a existuje spravedlivé řešení problému. V některých případech může být problém nedělitelnosti zmírněn zavedením hotovostních plateb , rotací nebo odmítnutím některých objektů, [1] ale taková řešení nejsou vždy možná.

Úloha distribuce objektů má několik složek:

  1. Účastníci musí vyjádřit své preference pro různé sady objektů.
  2. Skupina se musí rozhodnout, jaké bude kritérium spravedlnosti .
  3. Na základě preferencí a kritéria spravedlnosti by měl být implementován algoritmus spravedlivého rozdělení, aby se určilo nejspravedlivější řešení problému.

Tyto komponenty jsou podrobně vysvětleny níže.

Předvolby

Kombinatorické preference

Přirozeným způsobem, jak určit preference, je požádat každého účastníka, aby přiřadil číslo každé možné sadě položek, to znamená, aby uvedl její hodnotu v číselném vyjádření. Pokud jsou například předměty k distribuci auto a motocykl, mohou účastníci ocenit auto na 800, motocykl na 200 a sadu {auto, motocykl} na 900 (viz článek Užitkové funkce o nedělitelném zboží pro více příkladů). S těmito přístupy jsou dva problémy:

  1. Pro účastníka může být obtížné vypočítat přesnou číselnou hodnotu sady položek.
  2. Počet možných sad může být obrovský – pokud existují položky, pak jsou možné sady. Pokud je například 16 položek, každý účastník by musel zadat své preference zadáním 65536 čísel.

První problém podporuje použití ordinálního užitku spíše než kvantitativního užitku . V ordinálním modelu musí každý účastník pouze ukázat pořadí v různých sadách, tj. říci, která sada objektů je nejlepší, která je na druhém místě atd. To může být snazší vypočítat přesná čísla, ale zůstává obtížné, pokud počet objektů je velký.

Druhý problém se často řeší prací s jednotlivými objekty spíše než s kolekcemi objektů:

Za určitých předpokladů je možné zvýšit preference objektů na preference sady objektů [2] . Poté agenti nahlásí své skóre/umístění na jednotlivých objektech a algoritmus vypočítá skóre/pořadí na souborech objektů pro objekty.

Předvolby aditiv

Pro usnadnění úkolu alokace objektů se často předpokládá, že všechny objekty jsou nezávislé (nejsou tedy ani zaměnitelné , ani komplementární ) [3] . Pak

Aditivita znamená, že každý účastník si může vždy vybrat „preferovaný objekt“ ze sady objektů na stole a tato volba je nezávislá na jiných objektech, které již účastník může mít. Tato vlastnost se používá v některých algoritmech spravedlivého dělení, které budou popsány níže [6] .

Kompaktní reprezentace preferenčních jazyků

Kompaktní jazyky reprezentace preferencí byly navrženy jako kompromis mezi plnou expresivitou kombinatorických preferencí a jednoduchostí aditivních preferencí. Poskytují stručnou reprezentaci některých přirozených tříd funkcí užitku, které jsou obecnější než aditivní užitek (ale ne tak obecné jako kombinatorický užitek). Některé příklady jsou [7]

Kritérium spravedlnosti

Individuální záruční kritéria

Kritérium individuální záruky  je kritérium, které musí splnit každý jednotlivý účastník, pokud účastník čestně uvede své preference. Pět takových kritérií je uvedeno níže. Jsou seřazeny od nejslabšího po nejsilnější (za předpokladu, že jsou odhady aditivní) [8] :

1. Max-min fair-share ( anglicky  Max-min fair-share , MFS ): Max-min fair share (také nazývaný max-min garantovaný podíl) agenta je nejpreferovanější soubor, který si agent může zaručit, pokud je dělící strana v protokolu Dillí a vyber si . O přidělení se říká , že je MFS spravedlivé , pokud jakýkoli agent obdrží sadu, která je o něco výhodnější než jeho MFS [9] . MFS agenta lze interpretovat jako maximální užitek, který agent může získat z distribuce, když všichni ostatní agenti mají stejné preference, pokud agent vždy dostane nejhorší podíl. To lze považovat za minimální množství užitku, který může agent očekávat na základě následující úvahy: pokud mají všichni ostatní agenti stejné preference jako já, existuje alespoň jedna distribuce, která mi tento užitek poskytuje a umožňuje všem ostatním agentům ( mírně) bohatší. Proto není důvod mi dávat méně. To je také maximální užitek, kterým si může být agent jistý ve hře o distribuci „řežu, vybírám poslední“ – agent nabízí nejlepší distribuci a nechává zbytek účastníků, aby si vybrali své akcie, zatímco on sám obdrží zbývající podíl [8] . Férovost MFS lze také popsat jako výsledek následujícího procesu vyjednávání. Navrhuje se určitá distribuce. Každý agent může vznést námitku tím, že navrhne jiný oddíl položek. Přitom však musí umožnit všem ostatním agentům, aby si vybrali své akcie, než si vezmou jeho vlastní. Proto bude agent namítat proti distribuci pouze tehdy, pokud může nabídnout rozdělení do sad, které jsou všechny lepší než aktuální sada. Distribuce je spravedlivá pro MFS tehdy a jen tehdy, pokud žádný z agentů nevznese námitku, to znamená, že pro kteréhokoli agenta v libovolném oddílu existuje sada, která je o něco horší než jeho aktuální podíl.

2. Proporcionální spravedlivý podíl ( anglicky  proporcionální rozdělení fair-share , PFS) : Poměrný spravedlivý podíl agenta se rovná 1/ n užitku z celého souboru položek. O rozdělení se říká , že je poměrné , pokud všichni agenti obdrží soubory, které agenti oceňují alespoň spravedlivým poměrným podílem.

3. Fair Min-max-share ( angl.  min-max-fair-share , mFS): Spravedlivý Min-max-share agenta se rovná minimálnímu užitku, který agent doufá získat z distribuce, pokud ostatní agenti mít stejné preference jako tento agent a pokud agent vždy dostane nejlepší podíl. Tento podíl se také rovná minimálnímu užitku, který může agent získat v distribuční hře „Někdo jiný řeže, já volím první“. Distribuce je mFS-spravedlivá , pokud všichni agenti obdrží sadu objektů, které trochu preferují jejich mFS [8] . Spravedlnost mFS lze popsat jako výsledek následujícího procesu vyjednávání. Navrhuje se určitá distribuce. Každý agent může při řešení vyžadovat, aby jiný agent provedl jinou alokaci tak, aby si namítající agent vybral jako první. Proto by agent vznesl námitky proti distribuci pouze v případě, že ve všech oddílech existuje sada , kterou silně preferuje před aktuální sadou. Alokace je mFS-spravedlivá tehdy a pouze tehdy, pokud proti ní žádný z agentů nevznese námitky, tj. pro jakéhokoli agenta existuje oddíl, ve kterém jsou všechny sady o něco horší než jeho aktuální podíl.

Pro každého agenta s doplňkovou užitečností stojí mFS nejméně . Proto je jakékoli mFS spravedlivé rozdělení proporcionální. Pro každého agenta se superaditivní utilitou MFS představuje v nejlepším případě . Jakékoli rozdělení je tedy spravedlivé podle MFS. Oba důsledky jsou silné, i když má jakýkoli prostředek aditivní užitečnost . To je znázorněno na následujícím příkladu [8] :

K dispozici jsou 3 agenti a 3 položky: Možná distribuce je následující:

Výše uvedené závěry nejsou pravdivé, pokud odhady agentů nejsou sub/superaditivní [10] .

4. Envy -freeness ( EF) :  každý agent preferuje svou vlastní sadu před jakoukoli jinou. Jakákoli distribuce všech položek bez závisti je mFS-fér. To vyplývá přímo z ordinálních definic a nezávisí na aditivitě. Pokud jsou odhady aditivní, pak je rozdělení EF také proporcionální a MFS-spravedlivé. V opačném případě nemusí být rozdělení EF proporcionální nebo dokonce MFS [10] . Podrobnou diskuzi najdete v části Envious Item Distribution .

5. Konkurenční rovnováha z rovných příjmů ( ) :  Kritérium je založeno na následujících argumentech: distribuční proces by měl být chápán jako hledání rovnováhy mezi nabídkou (soubor objektů, z nichž každý má veřejně dostupný odhad) a poptávka (touhy agentů, každý agent má stejný rozpočet na nákup předmětů). Konkurenční rovnováhy je dosaženo, když nabídka odpovídá poptávce. Argument spravedlnosti je jednoduchý: ceny a rozpočty jsou pro všechny stejné. Z CEEI následuje EF bez ohledu na aditivitu. Pokud jsou preference agentů aditivní a striktní (každý soubor má jinou hodnotu), CEEI implikuje Paretovu efektivitu [8] .

Nedávno byla navržena některá kritéria pro spravedlnost [11] :

6. Envy -freeness-except-1 , EF1 :  Pro libovolné dva agenty A a B, pokud odstraníme z množiny B položku nejdůležitější pro A, pak A nezávidí B ( jinými slovy „úroveň závisti“ agent A k účastníkovi B leží nejvýše v jednom samostatném objektu). Při monotónnosti distribuce EF1 vždy existuje.

7. Bez závisti -kromě nejlevnějších ( EFx ) :  Pokud pro libovolné dva agenty A a B odstraníme z agenta B položku, která je pro agenta A nejméně cenná, pak A nezávidí B. EFx je přísně silnější než EF1. Není známo, zda distribuce EFx vždy existuje.

Globální kritérium optimality

Kritérium globální optimality provádí rozdělení na základě dané funkce sociálního blahobytu :

Výhodou globálních optimalizačních kritérií oproti individuálním kritériím je, že alokace maximalizující blahobyt jsou Pareto efektivní .

Distribuční algoritmy

Vlastní kapitál Max-min-share

Problém výpočtu MFS pro agenta je NP-úplný  - to lze ukázat snížením problému z problému rozdělení množiny čísel [8] .

Alokace MFS existují ve většině případů, ale ne vždy. Existují velmi vzácné případy, kdy takové rozdělení neexistuje [12] .

Problém určování, zda existuje distribuce MFS, je , to znamená, že jej lze vyřešit v nedeterministickém polynomiálním čase pomocí prediktoru pro NP-těžký problém (prediktor je potřebný k výpočtu maximálního a minimálního podílu agenta). Přesná výpočetní složitost tohoto problému však zůstává neznámá [8] .

Vždy existují alokace, které zaručují každému účastníkovi 2/3 výše uvedené hodnoty [12] . Postup distribuce byl implementován ve webové službě spliddit [13] .

Proporcionalita

1. Předpokládejme, že agenti mají na objektech numerickou užitečnou funkci. Pak problém, zda existuje proporcionální rozdělení, je NP-úplný problém  - lze jej získat redukcí z problému rozdělení množiny čísel [8] .

2. Předpokládejme, že agenti mají pořadové pořadí objektů s přítomností nebo nepřítomností identických (podle preference) objektů. Pak problém, zda nutně existuje proporcionální rozdělení, lze vyřešit v polynomiálním čase - lze jej získat redukcí z problému kontroly, zda bipartitní graf připouští přijatelné b-matching ( párování , ve kterém mají hrany kapacity) [14] .

Pro dva agenty existuje jednodušší algoritmus [15] .

3. Předpokládejme, že agenti mají pořadové pořadí objektů bez identických (podle preference) položek. Pak problém, zda existuje nutně proporcionální rozdělení, lze vyřešit v polynomiálním čase. Není známo, zda je to pravda, pokud je agentům dovoleno vyjádřit neutralitu (tedy ukázat, že pro něj mají dvě položky stejnou hodnotu) [14] .

Spravedlnost Min-max-share

Úkolem výpočtu agenta mFS je coNP-complete .

Problém, zda existuje distribuce mFS, je , ale jeho přesná výpočetní složitost zůstává neznámá [8] .

Žádná závist (žádné peníze)

Nedostatek závisti (s penězi)

Bez závisti je snazší dosáhnout, pokud se předpokládá, že ocenění agentů je v peněžním vyjádření kvazilineární, a proto umožňuje převod kompenzace mezi agenty.

Demange, Gale a Sotomayor ukázali přirozenou aukci zdola nahoru, která přináší alokaci bez závisti pomocí hotovostních plateb zájemci o předmět (kde každý zájemce má zájem maximálně o jeden předmět) [16] .

Fair by Design je  obecný návrh pro problémy optimalizace bez závisti, který přirozeně rozšiřuje spravedlivou distribuci objektů s peněžními výnosy [17] .

Cavallo [18] zobecnil tradiční binární kritéria nedostatku závisti, proporcionality a efektivity (blahobytu) na míry stupně, které jsou v rozsahu od 0 do 1. Za podmínek kanonického spravedlivého rozdělení pro jakýkoli účinný distribuční mechanismus , stupeň blahobytu je v nejhorším případě 0 a stupeň disproporcionality je 1. Jinými slovy, výsledky v nejhorším případě jsou co nejhorší. To silně motivuje analýzu průměrného případu. Hledal mechanismus, který by dosáhl vysokého blahobytu, nízké žárlivosti a nízké disproporcionality v očekávání napříč spektrem nastavení spravedlivého sdílení. Ukázal, že mechanismus Vickrey-Clark-Groves není uspokojivým kandidátem, ale mechanismus přerozdělování Bailey [19] a Cavallo [20] ano .

Rovnostářská-optimální distribuce

S numerickými odhady obecné formy je nalezení rovnostářského optimálního rozdělení, nebo dokonce přibližně optimálního rozdělení, NP-těžký problém. To lze dokázat snížením problému rozdělení množiny čísel . Čím omezenější jsou odhady, tím lepší aproximace lze získat [21] :

V článku Nguyena, Ruuse a Rotea [22] a článku N.-T. Nguyen, TT Nguyen, Ruus a Rote [23] prezentují některé silnější výsledky.

Zvláštní případ rovnostářské optimalizace sociálního blahobytu s aditivní užitečností se nazývá „problém Santa Clause“ [24] . Problém zůstává NP-obtížný a nelze jej aproximovat faktorem > 1/2, ale existuje aproximace [25] a složitější aproximace [26] . Viz také článek Dal'Aglio a Mosca [27] pro větvený a vázaný algoritmus pro dva partnery.

Procedura klesající potřeby vrací rovnostářské optimální dělení v obvyklém smyslu — maximalizuje hodnost, když jsou pakety agenta s nejnižší hodností lineárně seřazeny. To funguje s libovolným počtem agentů a libovolným pořadím balíčků.

Distribuce, které jsou Nashově optimální

V článku Nguyena, Ruuse a Rotea [22] a v článku N.-T. Nguyen, TT Nguyen, Ruus a Rote [23] prokázali obtížnost výpočtu utilitárních a Nashových optimálních distribucí.

Nguyen a Rote [28] představili postup aproximace Nashových optimálních rozdělení.

Ukázková sekvence

Sekvenční vychystávání je jednoduchý protokol, kde se agenti střídají ve vybírání položek na základě předem stanoveného pořadí. Cílem je navrhnout sekvenci vzorkování, aby se maximalizovala očekávaná hodnota funkce sociálního blahobytu (např. rovnostářské nebo utilitářské) za určitých pravděpodobnostních předpokladů o odhadech agentů.

Různé podíly

Většina výzkumů přidělování položek předpokládá, že všichni agenti mají stejné podíly. V mnoha případech však existují agenti s různými podíly. Jedním z takových případů je rozdělení kabinetu ministrů podle stran. Často se předpokládá, že každá strana by měla dostat počet ministerstev v poměru k počtu křesel v parlamentu. Viz článek Brahmse a Kaplana [29] , Azize [30] a článek Segala-Helevyho [31] pro diskuzi o tomto problému a některých jeho řešeních.

Poznámky

  1. ↑ Bouveret, Chevaleyre, Maudet, 2016 , str. 285.
  2. ↑ Barbera, Bossert, Pattanaik, 2004 , str. 44–48.
  3. ↑ Bouveret, Endriss, Lang, 2010 .
  4. ↑ Brams, Edelman, Fishburn, 2003 , str. 147.
  5. ↑ Brams, 2005 , str. 387–421.
  6. ↑ Bouveret, Chevaleyre, Maudet, 2016 , str. 287-288.
  7. ↑ Bouveret, Chevaleyre, Maudet, 2016 , str. 289-294.
  8. ↑ 1 2 3 4 5 6 7 8 9 Bouveret, Lemaître, 2015 , str. 259.
  9. ↑ Budish, 2011 , str. 1061–1103.
  10. ↑ 1 2 Heinen, Nguyen, Rothe, 2015 , str. 521.
  11. ↑ 1 2 Caragiannis, Kurokawa a Moulin, 2016 , s. 305.
  12. ↑ 1 2 Procaccia, Wang, 2014 , str. 675–692.
  13. ↑ Rozdělit zboží - Spliddit . Získáno 15. října 2019. Archivováno z originálu 19. října 2019.
  14. ↑ 1 2 Aziz, Gaspers, MacKenzie, Walsh, 2015 , str. 71–92.
  15. ↑ Pruhs, Woeginger, 2012 , str. 305.
  16. ↑ Demange, Gale, Sotomayor, 1986 , s. 863–872.
  17. ↑ Mu'alem, 2014 , str. 29–46.
  18. ↑ Cavallo, 2012 .
  19. ↑ Bailey, 1997 , s. 107–126.
  20. ↑ Cavallo, 2006 , str. 882.
  21. ↑ Daniel Golovin. Max-min spravedlivé rozdělení nedělitelného zboží . CMU (2005). Získáno 27. srpna 2016. Archivováno z originálu 2. února 2017.
  22. ↑ 1 2 Nguyen, Roos, Rothe, 2013 , str. 65–90.
  23. ↑ 1 2 Nguyen, Nguyen, Roos, Rothe, 2013 .
  24. ↑ Bansal, Sviridenko, 2006 , str. 31.
  25. ↑ Bezaková, Dani, 2005 , str. jedenáct.
  26. ↑ Asadpour, Saberi, 2010 , str. 2970.
  27. ↑ Dall'Aglio, Mosca, 2007 , str. 218.
  28. ↑ Nguyen, Rothe, 2013 .
  29. ↑ Brams, Kaplan, 2004 , str. 143.
  30. ↑ Aziz, Haris; Gaspers, Serge; Mackenzie, Simon & Walsh, Toby (2017), Konkurenční rovnováha s nedělitelným zbožím a generickými rozpočty, arΧiv : 1703.08150 [cs.GT]. 
  31. ↑ Segal-Halevi, 2018 , str. 1267–1275.

Literatura