A tárgyak irigy elosztása

A tárgyak irigységmentes elosztása (irigység nélkül, KB, angolul Envy-free , EF disztribúció [1] ) a tárgyak igazságos elosztásának problémája , amelyben az igazságosság kritériuma az irigység hiánya a kapott elosztásban - minden ügynök objektumok halmazát kell kapnia, amelynek értéke (a szerint) nem kevesebb, mint a többi ügynök által kapott részesedés [2] .

Mivel az objektumok oszthatatlanok, előfordulhat, hogy a KB-eloszlás nem létezik. Az ilyen felosztás legegyszerűbb esete egy tárgy, amelyet legalább két ügynök között kell elosztani: ha az egyik ügynök megkapja a tárgyat, a másik irigyelni fogja őt. Így a felosztási eljárások magukban foglalják az irigység -mentesség követelményének különféle enyhítését .

Irigységmentes terjesztés keresése, ha létezik

Szettek rendelési beállításai: Nincs féltékenység

A vágási eljárás akkor és csak akkor talál teljes KB-eloszlást két ügynök számára, ha létezik ilyen eloszlás. Az eljárás megköveteli az ügynököktől, hogy rangsorolják az objektumkészleteket, de nem igényel mennyiségi segédinformációkat . Az algoritmus akkor működik, ha az ágensek preferenciái szigorúan monotonok , és nem kell azt feltételezni, hogy adaptív preferenciák . A legrosszabb esetben az ügynököknek számos lehetséges halmaza lehet, így a futási idő exponenciálisan függhet

Objektumok preferált rendezése: hírhedt/lehetséges irigységmentes

Az emberek általában könnyebben rendelhetnek egyedi objektumokat, mint tárgyak halmazait. Tételezzük fel, hogy minden ügynök adaptív preferenciákkal rendelkezik , akkor lehetséges az objektumok sorrendjét a halmazok részleges rendezésére emelni. Például, ha az objektumok sorrendje w>x>y>z, ez azt jelenti, hogy {w, x}>{y, z} és {w, y}>{x, z}, de semmiféle preferenciát nem tartalmaz {w, z} és {x, y}, {x} és {y, z} között, és így tovább.

Adott az objektumok sorrendje:

Egy disztribúcióról ismert, hogy irigységmentes ( szükségszerűen irigységmentes , NEF ), ha nem irigységmentes minden adaptív halmazsorrendre vonatkozóan, amely összhangban van az objektumrenddel;
Egy disztribúció esetleg irigységmentes (esetleg irigységmentes , PEF), ha nem irigységmentes legalább egy , az objektumrenddel összhangban lévő adaptív halmazsorrend tekintetében ;
Egy eloszlás minden bizonnyal Pareto -optimális ( NPE ), ha Pareto-optimális minden adaptív halmazrendezéshez, amely összhangban van az objektumrenddel;
Egy eloszlás valószínűleg Pareto-optimális (PPE), ha Pareto-optimális legalább egy , az objektumrenddel összhangban lévő adaptív halmazrendezéshez.

Bouvre, Endriss és Leng [3] a hatékonyság, részlegesség, teljesség, COP vagy COP további feltételével egy ZBZ/WBZ eloszlás megtalálásának algoritmusaival foglalkozott. Általában a WBZ eset számításilag egyszerűbb, míg a ZBZ eset nehezebb.

Van-e KB disztribúció

Az üres eloszlás mindig KB, de ha a KB mellett hatékonyságot akarunk megkövetelni, akkor a probléma megoldása számításilag nehézkessé válik [4] :

Annak eldöntése, hogy létezik-e teljes KB-eloszlás, NP-teljes probléma. Ez akkor is igaz, ha csak két ügynök van, és akkor is, ha a segédfüggvények additívek és azonosak , mivel ebben az esetben a KB-eloszlás keresése egyenértékű egy számhalmaz particionálási problémájának megoldásával [5] .
Nehezebb eldönteni, hogy létezik-e Pareto-hatékony KB-eloszlás, mint az NP - ez még dichotóm preferenciafüggvények [6] és additív hasznossági függvények [7] esetén is teljes . $\Sigma _{2}^{\textrm {P}}$

Keresési terjesztés korlátozott mértékű irigységgel

Egyes eljárások olyan disztribúciót találnak, amelyben nincs irigység, kivéve egy objektumot (BZ1) – bármely két A és B ügynök esetében van egy objektum, amelyet a B ügynök halmazából eltávolítva az A ügynök többé nem irigyeli a B ügynököt. [8] .

Körkörös eljárás

Ha minden ügynök gyengén additív segédprogramokkal rendelkezik , a következő protokoll (ami hasonló a körmérkőzéses tervezéshez ) megadja a teljes KB1-eloszlást:

Az ügynököket tetszőleges módon rendezze el.
Amíg vannak kiosztatlan objektumok
- Az 1-től kezdődő számokkal rendelkező ügynökök számára engedélyezzük az objektum kiválasztását. $n$

Bizonyítás [9] : Bármely ügynök esetén az ágensek által meghozott döntéseket részsorozatokra osztjuk – az első részsorozat az 1. ügynökkel kezdődik és az ügynökkel végződik . Az utolsó részsorozat karakterrel kezdődik és ezzel végződik . A második sorozatban az ügynök választ először, tehát a legjobb tárgyat választja, ezért nem irigyli a másik ügynököt. Egy ügynök csak az egyik ügynökre irigyelhet , és minden irigység csak az első lépésben kiválasztott objektumtól származik. Ha ezt a tárgyat eltávolítják, az ügynök nem lesz féltékeny.

én

i-1

én

i-1

én

én

1,...,i-1

én

A körmérkőzéses protokoll gyenge additivitást igényel , mivel minden ügynöknek meg kell választania a "legjobb objektumot", anélkül, hogy tudná, hogy a későbbiekben melyik objektumokat fogja kiválasztani. Más szavakkal, ez azt feltételezi, hogy az objektumok független áruk .

Envy Cycle Procedure

Az irigység ciklusainak eljárása visszaadja a teljes BZ1 eloszlást tetszőleges preferencia relációkra. Az egyetlen követelmény az, hogy az ügynökök rendelhessék objektumkészleteiket.

Ha az ágensek preferenciáit egy kardinális hasznossági függvény képviseli , akkor a BZ1 garanciának van egy további értelmezése: az egyes ügynökök irigységének számszerű szintje nem haladja meg a maximális határhasznot , azaz egy egyedi objektum maximális határhasznát. ezt az ügynököt.

Hozzávetőleges P-CRRD eljárás

Az egyenlő jövedelemből származó közelítő versenyegyensúly ( A -CEEI ) részleges B31 eloszlást ad vissza tetszőleges preferenciákhoz. Az egyetlen követelmény az, hogy az ügynök képes legyen objektumgyűjtemények megrendelésére.

Előfordulhat, hogy néhány objektum kiosztás nélkül marad. Az elosztás Pareto-hatékony elosztott objektumok esetén. Ráadásul a P-CRRD mechanizmus megközelítőleg stratégiailag sebezhetetlen , ha nagy az ágensek száma.

Maximum Nash Wellbeing

A Maximum-Nash-Welfare (MNW) algoritmus a teljes eloszlást választja ki, amely maximalizálja a közművek szorzatát. Minden ügynöknek meg kell adnia egy számértéket minden objektumhoz, és feltételezi, hogy az ügynökök segédprogramjai összeadódnak. A kapott eloszlás szintén BZ1 és Pareto-hatékony lesz [9] .

Ha az ágensek preferenciái nem additívak, az MNB-megoldás nem feltétlenül BZ1, de ha az ágensek preferenciái legalább szubmodulárisak , akkor az MNB-megoldás 1 objektum kivételével kielégít egy gyengébb tulajdonságot, amit marginális eloszlásnak nevezünk. ( Marginal-Envy-Freeness) . , MEF1).

BZ1 / BZd

Bármely két A és B ügynök esetében létezik egy alternatív kritérium, az irigység nélkül, kivéve a legolcsóbbat (BZd) . Ha eltávolítunk egy tárgyat B ügynök objektumkészletéből, akkor A nem irigyli B-t. A BZd szigorúan erősebb, mint a BZ1. De még mindig nem ismert, hogy mindig vannak-e BZd eloszlások [9] .

Az irigységi kapcsolat minimalizálása

Ha adott X eloszlása , definiálja az i és j irigységarányt (EnvyRatio):

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

tehát az arány 1, ha i nem irigy j -re , és nagyobb, mint 1, ha i féltékeny j -re . Az elosztási irigység relációt a következőképpen határozzuk meg:

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

Az irigységi arány minimalizálásának problémája az X eloszlás megtalálásának problémája a legkisebb irigységi aránnyal.

Általános becslések

Az általános preferenciák szerint minden olyan determinisztikus algoritmus , amely minimális irigységi arány mellett számítja ki az eloszlást, számos lekérdezést igényel, amelyek a legrosszabb esetben exponenciálisan függnek az objektumok számától [5] .

Additív egyenlő pontszámok

Additív és azonos preferencia pontszámokkal [5] :

A következő mohó algoritmus olyan eloszlást talál, amelynek irigységi aránya legfeljebb 1,4-szerese a minimumnak [10] ;
1. A tárgyakat csökkenő értékrendbe rendezzük;
2. Míg vannak kiosztatlan objektumok, a következő objektumot a minimális összértékkel rendelkező ügynöknek adjuk;
Létezik egy PTAS- séma az irigységi kapcsolat minimalizálására. Sőt, ha a játékosok száma állandó, van egy FPTAS séma.

Összeadás különböző becslések

Additív és eltérő preferenciabecslésekkel [11]

Ha az ágensek száma benne van a bemenő adatokban, akkor polinomiális időben lehetetlen 1,5-nél jobb közelítési együtthatót kapni. Hacsak nem P=NP.
Ha az ügynökök száma állandó, van egy FPTAS-séma .
Ha az ügynökök száma megegyezik az objektumok számával, akkor létezik egy polinomiális időeloszlási algoritmus.

Részleges terjesztés keresése irigység nélkül

Az AL eljárás megkeresi két ügynök KB eloszlását. Eldobhat néhány objektumot, de a végső eloszlás Pareto-hatékony abban az értelemben, hogy nincs más KB-eloszlás jobb az egyik számára, és gyengén jobb a másik számára. Az AL eljárás megköveteli, hogy az objektumokat érték szerint különítse el az ügynököktől. Az eljárás feltételezi, hogy az ágensek adaptív preferenciái vannak , és olyan eloszlást ad, amelyről ismert, hogy nem irigység ( mindenképpen irigység nélkül, ZBZ).

A " kiigazító győztes " eljárás visszaadja a teljes és hatékony disztribúciós KB-t a két ügynök számára, de előfordulhat, hogy az egyik objektumot le kell vágni (vagy az egyik objektum közös használatban marad). Az eljárás megköveteli, hogy minden ügynök jelentsen egy számszerű segédprogramot minden objektumhoz, és feltételezi, hogy az ügynökök additív segédfunkciókkal rendelkeznek .

Az irigység nélküli elhelyezés megléte véletlenszerű értékelésekkel

Ha az ágensek additív hasznossági függvényekkel rendelkeznek , amelyek bizonyos kritériumokat kielégítő valószínűségi eloszlásokból származnak, és az objektumok száma kellően nagy az ágensek számához képest, akkor a KB-eloszlás nagy valószínűséggel létezik . Különösen [12]

Ha az objektumok száma elég nagy , akkor nagy valószínűséggel létezik a KB-eloszlás (vagyis a valószínűség 1-re hajlik, míg m a végtelenbe). $m=\Omega (n\log n)$
Ha az objektumok száma nem elég nagy, azaz , akkor nagy valószínűséggel nem létezik KB eloszlás. $m=n+o(n)$

Az irigység hiánya és az igazságosság egyéb kritériumai

Bármely KB-elosztás min-max igazságos . Ez közvetlenül következik a szokásos definíciókból, és nem függ az additivitástól.
Ha az ágensek additív hasznossági függvényekkel rendelkeznek , akkor a KB eloszlás is arányos és max-min-fair . Ellenkező esetben előfordulhat, hogy a KB-eloszlás nem arányos, és nem is max-min-méltányos.
Minden olyan disztribúció, amely versenyegyensúlyban egyenlő jövedelmekkel , nem irigykedik. Ez az additivitástól függetlenül igaz [8] .
Bármely optimális Nash-eloszlás (olyan eloszlás, amely maximalizálja a segédprogramok szorzatát) KB1 [9] .

Lásd A tárgyak igazságos elosztásának problémája című cikket részletes leírással és szakirodalmi hivatkozásokkal.

Döntő táblázat

Az alábbiakban a következő jelöléseket használjuk:

$n$ = a megosztásban részt vevő ügynökök száma;
$m$ = a kiosztandó tételek (objektumok) száma;
BE = nincs irigység, BE1 = nincs irigység egy tantárgy kizárásával (gyengébb követelmény, mint a BE), BE1 = maximum nincs irigység egy tárgy kizárásával (gyengébb követelmény, mint a BE1).
EP = Pareto-effektív (PE = angolul Pareto-efektív ).

Név	Résztvevők száma	Bejárat	preferenciák	Kérelmek száma	Igazságszolgáltatás	Hatékonyság	Hozzászólások
Metszés	2	Rendelt készletek	Szigorúan monoton	$2^{m}$	BZ	teljes	Akkor és csak akkor, ha létezik egy teljes KB disztribúció
AL eljárás	2	Rendezett objektumok	Gyengén adalékanyag	$Poly(m)$	Nyilvánvalóan-BZ	Részleges, de a forgalmazást nem a Pareto uralja egy másik ZBZ
Állítható nyertes	2	Tárgyértékelés	Adalékanyag	$Poly(m)$	hozzáértő és pártatlan	EP	Egy objektum megosztható
körkörös tervezés	$n$	Rendezett objektumok	Gyengén adalékanyag	$m$	Nyilvánvalóan BZ1	teljes
Az irigység ciklusai	$n$	Rendelt készletek	monoton	$O(mn^{3})$	BZ1	teljes
P-CRRD mechanizmus	$n$	Rendelt készletek	Bármi	?	BZ1, és - a részvények maximalizálása $(n+1)$	Részleges, de ES az elosztott objektumokhoz képest	Körülbelül stratégiailag sebezhetetlen , ha sok ügynök van.
Maximális Nash-jólét [9]	$n$	Tárgyértékelés	Adalékanyag	NP-kemény (de létezik a közelítés speciális eseteiben)	BZ1 és hozzávetőlegesen a részvények maximalizálása $n$	EP	A szubmoduláris segédfunkciók esetén az elosztás EF és PBZ1.

Lásd még

A részvények maximalizálása a méltányosság másik kritériuma.

Jegyzetek

↑ Szó szerint - a tárgyak irigység nélküli elosztása, ami általában zavaró - csak az irigység a fő tényező egy ilyen elosztásban.
↑ Brandt, Conitzer, Endriss et al., 2016 , p. 296–297.
↑ Bouveret, Endriss, Lang, 2010 , p. 387–392.
↑ Brandt, Conitzer, Endriss et al., 2016 , p. 300–310.
↑ 1 2 3 Lipton, Markakis, Mossel, Saberi, 2004 , p. 125.
↑ Bouveret, Lang, 2008 , p. 525–564.
↑ De Keijzer, Bouveret, Klos, Zhang, 2009 , p. 98.
↑ 1 2 Budish, 2011 , p. 1061–1103.
↑ 1 2 3 4 5 Caragiannis, Kurokawa et al., 2016 , p. 305.
↑ Graham, 1969 , p. 416–429.
↑ Nguyen, Rothe, 2014 , p. 54–68.
↑ Dickerson, Goldman et al., 2014 , p. 1405–1411.

Irodalom

Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. A számítógépes társadalmi választás kézikönyve . - Cambridge University Press, 2016. - ISBN 9781107060432 .
Sylvain Bouveret, Ulle Endriss, Jérôme Lang. Fair Division Under Ordinal Preferences: Computing Envy-Free Allokations of Oszthatatlan javak // ECAI 2010. - 2010. - 387–392.
Bouveret S., Lang J. Hatékonyság és irigységmentesség az oszthatatlan javak igazságos felosztásában: Logikai ábrázolás és komplexitás // JAIR. - 2008. - T. 32 . - doi : 10.1613/jair.2467 .
Bart De Keijzer, Sylvain Bouveret, Tomas Klos, Yingqian Zhang. A hatékonyság és az irigység-mentesség összetettségéről az oszthatatlan áruk méltányos felosztásában additív preferenciákkal // Algoritmikus döntéselmélet. - 2009. - T. 5783. - (Számítástechnikai előadásjegyzetek). - ISBN 978-3-642-04427-4 . - doi : 10.1007/978-3-642-04428-1_9 .
Eric buddhista. A kombinatorikus hozzárendelési probléma: Közelítő versenyegyensúly egyenlő jövedelmekből // Journal of Political Economy. - 2011. - T. 119 , sz. 6 . - doi : 10.1086/664613 .
Ioannis Caragiannis, David Kurokawa, Herve Moulin, Ariel D. Procaccia, Nisarg Shah, Junxing Wang. A maximális Nash-jólét indokolatlan igazságossága // A 2016-os ACM Gazdasági és Számítási Konferencia - EC '16 anyaga . - 2016. - S. 305. - ISBN 9781450339360 . - doi : 10.1145/2940716.2940726 .
Lipton RJ, Markakis E., Mossel E., Saberi A. Az oszthatatlan áruk megközelítőleg igazságos elosztásáról // Proceedings of the 5th ACM Conference on Electronic commerce - EC '04. - 2004. - ISBN 1-58113-771-0 . doi : 10.1145 / 988772.988792 .
Graham RL Bounds on Multiprocessing Timing Anomalies // SIAM Journal on Applied Mathematics. - 1969. - T. 17 , sz. 2 . - doi : 10.1137/0117039 .
Trung Thanh Nguyen, Jörg Rothe. Az irigység minimalizálása és az átlagos Nash társadalmi jólét maximalizálása az oszthatatlan javak elosztásában // Discrete Applied Mathematics. - 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. ACM link