Esineiden kateellinen jakelu

Esineiden kateudeton jakelu (ilman kateutta, KB, englanniksi Envy-free , EF-jakelu [1] ) on esineiden oikeudenmukaisen jakautumisen ongelma, jossa oikeudenmukaisuuden kriteeri on kateuden puuttuminen tuloksena olevasta jakelusta - jokainen agentti on saatava joukko esineitä, joiden arvo (hänen mukaan) ei ole pienempi kuin muiden agenttien saamat osakkeet [2] .

Koska objektit ovat jakamattomia, KB-jakaumaa ei ehkä ole olemassa. Yksinkertaisin tapaus tällaisesta jaosta on yksi esine, joka tulisi jakaa vähintään kahden agentin kesken: jos toinen agentti saa kohteen, toinen kadehtii häntä. Siten jakomenettelyihin sisältyy erilaisia kateuden vaatimuksen lieventämistä .

Kadehdittoman jakelun löytäminen, jos se on olemassa

Sarjojen tilausasetukset: No Jealousy

Karsiminen löytää täydellisen KB-jakauman kahdelle agentille, jos ja vain jos tällainen jakauma on olemassa. Menettely edellyttää agenttien järjestelevän objektijoukkoja , mutta se ei vaadi kvantitatiivisia hyödyllisyystietoja . Algoritmi toimii, jos agenttien mieltymykset ovat tiukasti monotonisia , eikä niiden tarvitse olettaa olevan mukautuvia . Pahimmassa tapauksessa agenteilla voi olla useita mahdollisia joukkoja, joten ajoaika voiriippua eksponentiaalisesti objektien määrästä.

Objektien etusijajärjestys: pahamaineinen / mahdollinen kateudeton

Ihmisten on yleensä helpompi tilata yksittäisiä esineitä kuin esinesarjoja. Oletetaan, että kaikilla agenteilla on adaptiiviset mieltymykset , silloin on mahdollista nostaa objektien järjestys joukkojen osittaiseksi järjestykseen. Jos objektit ovat esimerkiksi järjestyksessä w>x>y>z, tämä tarkoittaa, että {w, x}>{y, z} ja {w, y}>{x, z}, mutta se ei tarkoita mitään etusijaa { w, z} ja {x, y}, välillä {x} ja {y, z} ja niin edelleen.

Annettu objektien järjestys:

Jakelun tiedetään olevan kateudeton ( välttämättä kateusvapaa , NEF ), jos se ei ole kateudeton kaikille objektijärjestyksen mukaisille mukautuville joukkojärjestyksille;
Jakelu on mahdollisesti kateudeton (mahdollisesti kateudeton , PEF), jos se ei ole kateudeton vähintään yhden objektijärjestyksen mukaisen mukautuvan sarjajärjestyksen osalta;
Jakauma on varmasti Pareto -optimaalinen ( NPE), jos se on Pareto-optimaalinen kaikille adaptiivisille joukkojärjestyksille , jotka ovat yhdenmukaisia objektijärjestyksen kanssa;
Jakauma on mahdollisesti Pareto -optimaalinen (PPE), jos se on Pareto-optimaalinen ainakin yhdelle adaptiiviselle joukkojärjestykselle, joka on yhdenmukainen objektijärjestyksen kanssa.

Bouvre, Endriss ja Leng [3] tutkivat algoritmisia kysymyksiä ZBZ/WBZ-jakauman löytämiseksi tehokkuuden, osittaisuuden, täydellisyyden, COP:n tai COP:n lisäehdon kanssa. Yleisesti ottaen WBZ-tapaus on laskennallisesti yksinkertaisempi, kun taas ZBZ-tapaus on vaikeampi.

Onko KB-jakelua

Tyhjä jakauma on aina KB, mutta jos halutaan vaatia tehokkuutta KB:n lisäksi, ongelman ratkaisu tulee laskennallisesti vaikeaksi [4] :

Täydellisen KB-jakauman olemassaolosta päättäminen on NP-täydellinen ongelma. Tämä pätee myös silloin, kun agentteja on vain kaksi ja vaikka apufunktiot ovat additiivisia ja identtisiä , koska tässä tapauksessa KB-jakauman etsiminen vastaa numerojoukon osiointiongelman ratkaisemista [5] .
Pareto-tehokkaan KB-jakauman olemassaolon päättäminen on vaikeampaa kuin NP - se on -täydellinen jopa dikotomisilla preferenssifunktioilla [6] ja jopa additiivisilla hyödyllisyysfunktioilla [7] . $\Sigma _{2}^{\textrm {P))$

Hakujakelu rajoitetulla kateudella

Jotkut menettelyt löytävät jakauman, jossa ei ole kateutta paitsi yksi kohde (BZ1) - kahdelle agentille A ja B on yksi objekti, jonka poistamisen jälkeen agentin B joukosta agentti A ei enää kadehdi agenttia B [8] .

Kiertomenettely

Jos kaikilla agenteilla on heikosti additiivisia apuohjelmia , seuraava protokolla (joka on samanlainen kuin round robin -suunnittelu ) antaa täyden KB1-jakauman:

Järjestä agentit mielivaltaisella tavalla.
Niin kauan kuin on kohdentamattomia kohteita
- Sallimme agenttien, joiden numerot ovat 1, valita kohteen. $n$

Todistus [9] : Jokaiselle agentille jaamme agenttien tekemät valinnat alasarjoiksi – ensimmäinen osasarja alkaa agentilla 1 ja päättyy agenttiin . Viimeinen osasarja alkaa ja päättyy . Toisessa sarjassa agentti valitsee ensin, joten hän valitsee parhaan kohteen, eikä siksi kadehdi toista agenttia. Agentti voi kadehtia vain yhtä agenteista , ja kaikki kateus tulee vain siitä kohteesta, joka valittiin ensimmäisessä osajaksossa. Jos tämä esine poistetaan, agentti ei ole mustasukkainen.

i

i-1

i

i-1

i

i

1,...,i-1

i

Round robin -protokolla vaatii heikkoa additiivisuutta , koska se vaatii jokaisen agentin valitsemaan "paras objektin" tietämättä mitkä kohteet hän valitsee myöhemmin. Toisin sanoen tämä olettaa, että objektit ovat itsenäisiä tavaroita .

Envy Cycle Procedure

Kateuden syklien proseduuri palauttaa täydellisen BZ1-jakauman mielivaltaisille preferenssisuhteille. Ainoa vaatimus on agenttien mahdollisuus tilata objektijoukkojaan.

Jos agenttien mieltymyksiä edustaa kardinaalihyötyfunktio , niin BZ1 -takuulla on lisätulkinta: kunkin agentin kateuden numeerinen taso ei ylitä maksimirajahyötysuhdetta eli yksittäisen kohteen enimmäisrajahyötysuhdetta. tämä agentti.

Likimääräinen P-CRRD-menettely

Approximate Competitive Equilibrium from Equal Income ( A -CEEI ) palauttaa osittaisen B31-jakauman mielivaltaisille mieltymyksille. Ainoa vaatimus on, että agentti voi tilata esinekokoelmia.

Pieni määrä objekteja voi jäädä kohdentamatta. Hajauttaminen on Pareto-tehokasta hajautetuille objekteille. Lisäksi P-CRRD-mekanismi on suunnilleen strategisesti haavoittumaton , jos tekijöiden määrä on suuri.

Maximum Nash Wellbeing

Maximum - Nash-Welfare (MNW) -algoritmi valitsee täyden jakauman, joka maksimoi apuohjelmien tuoton. Se edellyttää, että jokainen agentti antaa numeerisen arvon jokaiselle objektille, ja oletetaan, että agenttien apuohjelmat ovat additiivisia. Tuloksena oleva jakauma on myös BZ1- ja Pareto-tehokas [9] .

Jos agenttien mieltymykset eivät ole additiivisia, MNB-ratkaisu ei välttämättä ole BZ1, mutta jos agenttien preferenssit ovat vähintään submodulaarisia , MNB-ratkaisu tyydyttää heikomman ominaisuuden, jota kutsutaan marginaalijakaumaksi ilman kateutta, paitsi 1 objekti ( Marginal-Envy-Freeness) . , MEF1).

BZ1 / BZd

On olemassa vaihtoehtoinen kriteeri nimeltä Ei kateutta paitsi halvin (BZd) kahdelle agentille A ja B. Jos poistamme minkä tahansa kohteen agentin B esinejoukosta, A ei kadehdi B:tä. BZd on ehdottomasti vahvempi kuin BZ1. Mutta edelleenkään ei tiedetä, onko aina olemassa BZd-jakaumia [9] .

Minimizing the Envy Relationship

Kun X : n jakauma on annettu , määritä i :n ja j :n kateussuhde (EnvyRatio) seuraavasti:

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

joten suhde on 1, jos i ei ole kateellinen j :lle , ja suurempi kuin 1, jos i on mustasukkainen j :lle . Määrittelemme jakelun kateussuhteen seuraavasti:

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

Kateussuhteen minimointiongelma on ongelma löytää jakauma X pienimmällä kateussuhteella.

Yleiset arviot

Yleisten mieltymysten mukaan mikä tahansa deterministinen algoritmi , joka laskee jakauman pienimmällä kateussuhteella, vaatii useita kyselyjä, jotka pahimmassa tapauksessa riippuvat eksponentiaalisesti objektien lukumäärästä [5] .

Additiiviset yhtä suuret pisteet

Additiivisilla ja identtisillä mieltymyspisteillä [5] :

Seuraava ahne algoritmi löytää jakauman, jonka kateussuhde on enintään 1,4 kertaa minimi [10] ;
1. Järjestämme esineet arvon laskevaan järjestykseen;
2. Vaikka allokoimattomia objekteja on, annamme agentille seuraavan objektin, jolla on pienin kokonaisarvo;
On olemassa PTAS -järjestelmä kateussuhteen minimoimiseksi. Lisäksi, jos pelaajien määrä on vakio, on olemassa FPTAS - järjestelmä.

Erilaisia lisäarvioita

Additiivisilla ja erilaisilla mieltymysarvioilla [11]

Jos tekijöiden lukumäärä sisältyy syöttötietoihin, niin polynomiajassa on mahdotonta saada parempaa approksimaatiokerrointa kuin 1,5 . Ellei P = NP.
Jos agenttien määrä on vakio, on olemassa FPTAS-malli .
Jos agenttien lukumäärä on yhtä suuri kuin objektien lukumäärä, on olemassa polynominen aikajakauma-algoritmi.

Etsi osittaista jakelua ilman kateutta

AL-proseduuri etsii KB-jakauman kahdelle agentille. Se voi hylätä osan objekteista, mutta lopullinen jakauma on Pareto-tehokas siinä mielessä, että mikään muu KB-jakauma ei ole parempi yhdelle ja heikosti parempi toiselle. AL-menettely edellyttää, että objektit on järjestettävä arvon mukaan vain agenteista. Proseduuri olettaa, että agenteilla on adaptiiviset mieltymykset , ja se antaa jakauman, jonka tiedetään olevan ilman kateutta ( varmasti ilman kateutta, ZBZ).

" Muokkaa voittaja " -menettely palauttaa täyden ja tehokkaan jakelun KB:n kahdelle agentille, mutta saattaa edellyttää toisen objektin leikkaamista (tai toinen objekteista jää yleiseen käyttöön). Menettely edellyttää, että jokainen agentti raportoi numeerisen hyödyllisyysarvon jokaiselle objektille, ja oletetaan, että agenteilla on additiivisia aputoimintoja .

Sijoittamisen olemassaolo ilman kateutta satunnaisilla arvioinneilla

Jos agenteilla on additiivisia hyödyllisyysfunktioita , jotka on otettu joitain kriteerejä täyttävistä todennäköisyysjakaumista ja objektien määrä on riittävän suuri suhteessa agenttien määrään, niin KB-jakauma on olemassa suurella todennäköisyydellä . Erityisesti [12]

Jos objektien määrä on riittävän suuri , niin suurella todennäköisyydellä KB-jakauma on olemassa (eli todennäköisyys on 1, kun m pyrkii äärettömyyteen). $m=\Omega (n\log n)$
Jos objektien määrä ei ole tarpeeksi suuri, eli , niin suurella todennäköisyydellä KB-jakaumaa ei ole olemassa. $m=n+o(n)$

Kateuden puute ja muut oikeudenmukaisuuden kriteerit

Mikä tahansa KB-jakelu on min-max reilu . Tämä seuraa suoraan tavallisista määritelmistä eikä riipu additiivisuudesta.
Jos agenteilla on additiivinen hyödyllisyysfunktio , niin KB-jakauma on myös suhteellinen ja max-min-fair . Muuten KB-jakauma ei ehkä ole suhteellinen eikä edes maksimi-min-reilu.
Millään jakelulla, jolla on kilpailutasapaino ja yhtäläiset tulot, ei ole kateutta. Tämä pätee additiivisuudesta riippumatta [8] .
Mikä tahansa Nashin optimaalinen jakauma (jakauma, joka maksimoi apuohjelmien tuotteen) on KB1 [9] .

Katso artikkeli Esineiden oikeudenmukaisen jakautumisen ongelma yksityiskohtaisella kuvauksella ja viittauksilla kirjallisuuteen.

Finaalipöytä

Alla käytetään seuraavia merkintöjä:

$n$ = jakamiseen osallistuvien agenttien lukumäärä;
$m$ = jaettavien esineiden (esineiden) lukumäärä;
BE = ei kateutta, BE1 = ei kateutta, kun yksi aihe jätetään pois (heikompi vaatimus kuin BE), BE1 = ei kateutta enintään yhden aiheen poissulkeminen (heikompi vaatimus kuin BE1).
EP = Pareto efficient (PE = englanniksi Pareto-efektiivinen ).

Nimi	Osallistujien määrä	Sisäänkäynti	Asetukset	Pyyntöjen määrä	Oikeudenmukaisuus	Tehokkuus	Kommentit
Leikkaaminen	2	Tilatut setit	Tiukasti monotoninen	$2^{m}$	BZ	Saattaa loppuun	Jos ja vain jos täydellinen KB-jakelu on olemassa
AL-menettely	2	Tilatut esineet	Heikosti lisäaine	$Poly(m)$	Ilmeisesti BZ	Osittainen, mutta jakelu ei ole Pareton hallitsema toinen ZBZ
Säädettävä Voittaja	2	Kohteen arvostus	Lisäaine	$Poly(m)$	asiantunteva ja puolueeton	EP	Yksi kohde voidaan jakaa
pyöreä suunnittelu	$n$	Tilatut esineet	Heikosti lisäaine	$m$	Ilmeisesti BZ1	Saattaa loppuun
Kateuden kierteet	$n$	Tilatut setit	yksitoikkoinen	$O(mn^{3})$	BZ1	Saattaa loppuun
P-CRRD-mekanismi	$n$	Tilatut setit	Minkä tahansa	?	BZ1 ja - osakkeiden maksimointi $(n+1)$	Osittainen, mutta ES suhteessa hajautettuihin objekteihin	Suunnilleen strategisesti haavoittumaton , jos agentteja on monia.
Maksimaalinen Nash-hyvinvointi [9]	$n$	Kohteen arvostus	Lisäaine	NP-kova (mutta olemassa erityisissä approksimaatiotapauksissa)	BZ1 ja noin -osakkeiden maksimointi $n$	EP	Submodulaarisilla aputoiminnoilla jakelu on EF ja PBZ1.

Katso myös

Osakkeiden maksimointi on toinen oikeudenmukaisuuden kriteeri.

Muistiinpanot

↑ Kirjaimellisesti - esineiden jakautuminen ilman kateutta, mikä yleensä on hämmentävää - pelkkä kateus on päätekijä sellaisessa jakelussa.
↑ Brandt, Conitzer, Endriss et ai., 2016 , s. 296-297.
↑ Bouveret, Endriss, Lang, 2010 , s. 387-392.
↑ Brandt, Conitzer, Endriss et ai., 2016 , s. 300-310.
↑ 1 2 3 Lipton, Markakis, Mossel, Saberi, 2004 , s. 125.
↑ Bouveret, Lang, 2008 , s. 525–564.
↑ De Keijzer, Bouveret, Klos, Zhang, 2009 , s. 98.
↑ 1 2 Budish, 2011 , s. 1061–1103.
↑ 1 2 3 4 5 Caragiannis, Kurokawa et al., 2016 , s. 305.
↑ Graham, 1969 , s. 416–429.
↑ Nguyen, Rothe, 2014 , s. 54–68.
↑ Dickerson, Goldman et ai., 2014 , s. 1405-1411.

Kirjallisuus

Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Laskennallisen sosiaalisen valinnan käsikirja . - Cambridge University Press, 2016. - ISBN 9781107060432 .
Sylvain Bouveret, Ulle Endriss, Jérôme Lang. Fair Division Under Ordinal Preferences: Computing Envy-Free Allokations of Invisible Goods // ECAI 2010. - 2010. - s. 387–392.
Bouveret S., Lang J. Tehokkuus ja kateudettomuus jakamattomien tavaroiden oikeudenmukaisessa jaossa: Looginen esitys ja monimutkaisuus // JAIR. - 2008. - T. 32 . - doi : 10.1613/jair.2467 .
Bart De Keijzer, Sylvain Bouveret, Tomas Klos, Yingqian Zhang. Tehokkuuden ja kateudettomuuden monimutkaisuudesta jakamattomien tavaroiden oikeudenmukaisessa jaossa lisäaineetujen kanssa // Algoritminen päätösteoria. - 2009. - T. 5783. - (Luentomuistiinpanot tietojenkäsittelytieteestä). - ISBN 978-3-642-04427-4 . - doi : 10.1007/978-3-642-04428-1_9 .
Eric buddhalainen. Kombinatorinen tehtävän ongelma: likimääräinen kilpailutasapaino yhtäläisistä tuloista // Journal of Political Economy. - 2011. - T. 119 , no. 6 . - doi : 10.1086/664613 .
Ioannis Caragiannis, David Kurokawa, Herve Moulin, Ariel D. Procaccia, Nisarg Shah, Junxing Wang. Maksimaalisen Nash-hyvinvoinnin kohtuuton oikeudenmukaisuus // Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16 . - 2016. - S. 305. - ISBN 9781450339360 . - doi : 10.1145/2940716.2940726 .
Lipton RJ, Markakis E., Mossel E., Saberi A. Jakamattomien tavaroiden suunnilleen oikeudenmukaisesta jaosta // 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 , no. 2 . - doi : 10.1137/0117039 .
Trung Thanh Nguyen, Jörg Rothe. Kateuden minimoiminen ja Nashin keskimääräisen sosiaalisen hyvinvoinnin maksimoiminen jakamattomien tavaroiden allokoinnissa // 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 // Tekoälyä käsittelevän 28. AAAI-konferenssin julkaisussa (2014). — 2014. ACM-linkki