A tárgyak igazságos elosztásának problémája

Az objektumok igazságos elosztása a méltányos felosztási probléma  egyik fajtája , amelyben a résztvevők között elosztandó tárgyak oszthatatlanok . Az objektumokat el kell osztani azon partnerek között, akik eltérően értékelik az objektumokat, és minden elemet egy egészben kell átadni egy résztvevőnek. Ez a helyzet több valós élethelyzetben is előfordul:

• több örökös szeretné megosztani az örökséget , amely például egy házat, egy autót, egy zongorát és több festményt foglal magában;
• több oktató úgy dönt, hogy megosztja a karán tartott kurzusokat. Minden oktató taníthat egy vagy több kurzust, de csak a teljes kurzust; több oktató nem tud egy kurzust elolvasni.

A tárgyak oszthatatlanságából következik, hogy az igazságos felosztás nem biztos, hogy lehetséges. Szélsőséges példa az az eset, amikor csak egy tárgy (mondjuk: ház) van, azt az egyik résztvevőnek át kell adni, de a többi résztvevő nem tartja tisztességesnek az ilyen döntést. Ez ellentétben áll a méltányos tortavágás problémájával , ahol a tárgy felosztható, és van igazságos megoldás a problémára. Egyes esetekben az oszthatatlanság problémája enyhíthető készpénzes fizetés bevezetésével , rotációval vagy egyes tárgyak elutasításával, [1] azonban ilyen megoldások nem mindig lehetségesek.

Az objektumok elosztásának feladata több összetevőből áll:

1. A résztvevőknek ki kell fejezniük preferenciáikat a különböző tárgykészletekkel kapcsolatban.
2. A csoportnak el kell döntenie, hogy mi legyen a méltányossági kritérium .
3. A preferenciák és a méltányosság kritériuma alapján igazságos elosztási algoritmust kell megvalósítani a probléma legigazságosabb megoldásának meghatározásához.

Ezeket az összetevőket az alábbiakban részletesen ismertetjük.

Beállítások

Kombinatorikus beállítások

A preferenciák meghatározásának természetes módja az, hogy minden résztvevőt megkérünk, hogy rendeljen hozzá egy számot minden lehetséges elemkészlethez, azaz adja meg annak értékét számszerűen. Például, ha a kiosztandó tárgyak egy autó és egy motorkerékpár, a résztvevők egy autót 800-ra, egy motorkerékpárt 200-ra és egy {car, motorcycle} készletet 900-ra értékelhetnek (lásd az oszthatatlan áruk használati funkciói című cikket további példák). Két probléma van ezekkel a megközelítésekkel:

1. A résztvevők számára nehéz lehet egy tételkészlet pontos számértékének kiszámítása.
2. A lehetséges készletek száma óriási lehet - ha vannak tételek, akkor vannak lehetséges készletek. Például, ha 16 elem van, akkor minden résztvevőnek 65536 szám megadásával kell megadnia a preferenciáit.

Az első probléma a mennyiségi hasznosság helyett a sorszámú hasznosság használatát ösztönzi . Az ordinális modellben minden résztvevőnek csak egy rangsort kell felmutatnia a különböző halmazok között, azaz meg kell mondania, hogy melyik objektumkészlet a legjobb, melyik a második helyen, és így tovább. Lehet, hogy egyszerűbb a pontos számok kiszámítása, de nehéz marad, ha az objektumok száma nagy.

A második probléma gyakran úgy oldható meg, hogy egyedi objektumokkal dolgozunk, nem pedig objektumgyűjteményekkel:

• Numerikus megközelítéssel minden résztvevőnek be kell számolnia az egyes objektumok számszerű értékeléséről;
• Sorrendi megközelítéssel minden résztvevőnek be kell jelentenie az objektumok rangsorolását (érték szerinti rendezés), vagyis meg kell mondani, hogy melyik tárgy a legértékesebb, melyik a második, stb.

Egyes feltételezések szerint lehetséges az objektumpreferenciákat objektumkészlet-preferenciákká emelni [2] . Ezután az ügynökök jelentik pontszámaikat/rangsoraikat az egyes objektumokon, és az algoritmus pontszámokat/rangsorokat számít ki az objektumok objektumkészletein.

Additive Preferences

Az objektumok kiosztásának megkönnyítése érdekében gyakran feltételezik, hogy minden objektum független (tehát nem felcserélhető és nem is komplementer ) [3] . Akkor

• Numerikus megközelítésben minden résztvevőnek van egy additív hasznossági függvénye (más néven moduláris hasznossági függvény ). Amikor egy ügynök minden egyes objektum értékét jelenti, könnyen kiszámítható egy halmaz értéke az azt alkotó objektumok értékeinek összegzésével.
• Sorrendi megközelítéssel az additív módszer lehetővé teszi a halmazok rangsorolását. Például, ha egy résztvevő a w > x > y > z sorrendben lévő objektumokat részesíti előnyben, akkor szükségszerűen előnyben részesíti a {w, x} elemet a {w, y} halmazzal, vagy az {x, y} és {w halmazokkal szemben, y} az {x} halmazhoz. Ezek a következtetések csak részlegesek, például nem tudhatjuk, hogy az ügynök a {w} halmazt preferálja-e az {x, y} halmazzal szemben, vagy akár a {w, z} halmazt az {x, y} halmazzal szemben [4] [5] .

Az additivitás azt jelenti, hogy minden résztvevő mindig választhat egy "preferált objektumot" az asztalon lévő objektumok közül, és ez a választás független a résztvevő által esetleg már meglévő objektumoktól. Ezt a tulajdonságot használják néhány igazságos osztási algoritmusban, amelyeket az alábbiakban ismertetünk [6] .

Kompakt preferenciális megjelenítési nyelvek

A kompakt preferencia-reprezentációs nyelveket a kombinatorikus preferenciák teljes kifejezőképessége és az additív preferenciák egyszerűsége közötti kompromisszumként tervezték. Tömören ábrázolják a hasznossági függvények néhány természetes osztályát, amelyek általánosabbak, mint az additív hasznosság (de nem annyira általánosak, mint a kombinatorikus hasznosság). Néhány példa: [7]

• 2-Additive Preferences  – Minden résztvevő jelent egy értéket minden 1-es vagy 2-es méretű készlethez. A készlet értékét a rendszer a készletben lévő egyedi objektumok értékeinek és a készletben lévő párok értékeinek összegeként számítja ki. a készlet. Általában, ha vannak helyettesítő objektumok, a párértékek negatívak, és amikor vannak kiegészítő objektumok, akkor a párértékek pozitívak. Ez az elképzelés általánosítható k-additív preferenciákra bármely k pozitív egész számra .
• Grafikus modellek  – minden résztvevő számára van egy grafikon, amely a különböző objektumok közötti függőséget ábrázolja. Numerikus megközelítéssel a szokásos eszköz a GAI net ( Generalized Additive Independence ) .  Ordinális megközelítéssel a szokásos eszköz a CP net (feltételes preferenciák, eng. Conditional Preferences ) és ennek kiterjesztései : TCP net , UCP net , CP theory , CI net (feltételes fontosság, angol feltételes fontosság ) és SCI net (a CI egyszerűsítése). net eng. a CI net egyszerűsítése ).   
• Logikai alapú nyelvek – minden résztvevő elsőrendű logikai képletekkel  ír le néhány halmazt, és mindegyik képlethez értéket rendelhet. Például egy résztvevő azt mondhatja: "(x vagy (y és z)) esetén az értékem 5 lenne." Ez azt jelenti, hogy az ügynök 5 értéket rendel az x, xy, xz, yz, xyz bármely halmazához.
• Licitálási nyelvek  – Sok nyelvet tanulmányoztak a kombinatorikus preferenciák megjelenítésére a kombinatorikus aukciókon . Ezen nyelvek egy része hozzáigazítható az objektumok terjesztésének feltételeihez.

Az igazságosság kritériuma

Egyedi garanciális feltételek

Az egyedi garanciális feltétel  az a feltétel, amelyet minden egyes résztvevőnek teljesítenie kell, ha a résztvevő őszintén megadja preferenciáit. Az alábbiakban öt ilyen kritériumot mutatunk be. A leggyengébbtől a legerősebbig vannak rendezve (feltéve, hogy a becslések összeadódnak) [8] :

1. Max-min fair share ( angolul  Max-min fair-share , MFS ): Az ügynök Max-min fair share (más néven max-min garantált részesedés) a legelőnyösebb halmaz, amelyet az ügynök garantálhat magának, ha megosztó fél a Delhi-és válassz . Egy kiosztás MFS-tisztességesnek mondható, ha bármely ügynök olyan halmazt kap, amely valamivel előnyösebb az MFS -jénél [9] . Az ügynök MFS-e úgy értelmezhető, mint az a maximális hasznosság, amelyet az ügynök remélhet elérni egy disztribúcióból, ha az összes többi ügynöknek ugyanazok a preferenciái, ha mindig az ügynök kapja a legrosszabb részesedést. Ez felfogható a minimális hasznosságnak, amelyre egy ügynök számíthat a következő érvelés alapján: ha az összes többi ágensnek ugyanazok a preferenciái, mint nekem, akkor van legalább egy eloszlás, amely megadja ezt a segédprogramot, és az összes többi ügynököt ( valamivel) gazdagabb. Ezért nincs okom kevesebbet adni. Ez egyben a maximális hasznosság is, amiben az ügynök biztos lehet az "én vágom, utoljára választom" elosztási játékban - az ügynök kínálja a legjobb disztribúciót, és a többi résztvevőre bízza a részvények kiválasztását, míg ő maga kapja meg az osztalékot. fennmaradó részesedés [8] . Az MFS méltányossága az alábbi tárgyalási folyamat eredményeként is leírható. Valamilyen elosztás javasolt. Minden ügynök tiltakozhat az elemek eltérő partíciójának javaslatával. Ennek során azonban lehetővé kell tennie az összes többi ügynök számára, hogy megválassza a részvényeit, mielőtt elvenné a sajátját. Ezért egy ügynök csak akkor tiltakozik egy disztribúció ellen, ha olyan partíciót tud felkínálni, amely mind jobb, mint az aktuális halmaz. Az eloszlás akkor és csak akkor MFS-tisztességes, ha az ügynökök egyike sem objektumot, azaz bármely partíció egyik ügynöke esetében van egy halmaz, amely valamivel rosszabb, mint a jelenlegi megosztása.

2. Proportional fair share ( angol  arányos fair-share , PFS) : Az ügynök arányos fair részesedése egyenlő 1/ n hasznossággal a teljes tételkészletből. Az eloszlást arányosnak mondjuk, ha minden ügynök olyan halmazt kap, amelyet az ügynökök legalább egy igazságos arányos részesedésre értékelnek.

3. Fair Min-max-share ( eng.  min-max-fair-share , mFS): Egy ügynök méltányos Min-max-részesedése egyenlő azzal a minimális hasznossággal, amelyet az ügynök más ügynökök esetén az elosztástól remél kapni. ugyanazok a preferenciák, mint ennek az ügynöknek, és ha mindig az ügynök kapja a legjobb részesedést. Ez a részesedés megegyezik azzal a minimális hasznossággal is, amelyet az ügynök a „Valaki más vág, én választok először” terjesztési játékban kaphat. Egy disztribúció mFS-tisztességes , ha minden ügynök olyan objektumkészletet kap, amelyet kissé preferál az mFS-jére [8] . Az mFS méltányossága a következő tárgyalási folyamat eredményeként írható le. Valamilyen elosztás javasolt. Mindegyik ügynök megkövetelheti, hogy egy másik ügynök eltérő kiosztást végezzen a megoldás során, így a kifogásoló ügynök választ először. Ezért az ügynök csak akkor tiltakozik a disztribúció ellen, ha minden partícióban van egy halmaz, amelyet határozottan előnyben részesít az aktuális halmazzal szemben. Egy kiosztás akkor és csak akkor mFS-fair, ha egyik ügynök sem tiltakozik ellene, azaz egyetlen ügynök esetében sem létezik olyan partíció, amelyben minden halmaz valamivel rosszabb, mint az aktuális részesedése.

Minden szubaditív segédprogramot használó ügynök esetében az mFS legalább . Ezért minden mFS-méltányos eloszlás arányos. Minden szuperadditív segédprogramot az MFS a legjobb esetben jelent . Ezért minden felosztás MFS-méltányos. Mindkét következmény akkor is erős, ha bármely ágens additív módon használható . Ezt szemlélteti a következő példa [8] :

• Alice az elemeket 2, 2, 2-re értékeli. Nála MFS=PFS=mFS=2.
• Bob a tételeket 3, 2, 1 értékre értékeli. Számára MFS=1, PFS=2 és mFS=3.
• Karl 3, 2, 1-re értékeli az elemeket. Számára MFS=1, PFS=2 és mFS=3.

• Minden olyan disztribúció, amely tárgyat ad minden résztvevőnek, MFS-méltányosság.
• Minden olyan elosztás, amely az első és a második elemet Bobnak és Carlnak, a harmadikat pedig Alice-nek adja, arányos.
• A kiosztás nem lesz mFS-méltányos.

A fenti következtetések nem igazak, ha az ágensek becslései nem szub/szuperaditívak [10] .

4. Irigység -mentesség ( EF) :  bármely ügynök a saját készletét részesíti előnyben bármely más készlettel szemben. Az összes tétel irigységmentes terjesztése mFS-tisztességes. Ez közvetlenül következik az ordinális definíciókból, és nem függ az additivitástól. Ha a becslések additívak, akkor az EF-eloszlás is arányos és MFS-méltányos. Ellenkező esetben előfordulhat, hogy az EF-eloszlás nem arányos, sőt nem is MFS [10] . A részletes vitához lásd az Irigy cikkek elosztását .

5. Versenyegyensúly az egyenlő jövedelmekből ( ) :  A kritérium a következő érveken alapul: az elosztási folyamatot úgy kell tekinteni, mint az egyensúly keresését a kínálat (egy olyan objektumok halmaza, amelyek mindegyike rendelkezik nyilvánosan elérhető becsléssel) és igény (az ügynökök vágyai, minden ügynöknek azonos költségvetése van az objektumok vásárlására). A versenyegyensúly akkor jön létre, ha a kínálat megfelel a keresletnek. A méltányossági érv egyszerű: az árak és a költségvetés mindenki számára azonos. A CEEI-től az EF következik, függetlenül az additivitástól. Ha az ágensek preferenciái additívak és szigorúak (minden halmaznak más az értéke), a CEEI Pareto-hatékonyságot jelent [8] .

A közelmúltban javasoltak néhány méltányossági kritériumot [11] :

6. Irigység -mentesség-kivéve-1 , EF1 :  Bármely két A és B ágens esetén, ha a B halmazból eltávolítjuk az A számára legfontosabb elemet, akkor A nem irigyli B-t (más szóval az irigység szintjét). A ágens B résztvevőhöz legfeljebb egy külön objektumban fekszik). Monotonitás esetén az EF1 eloszlás mindig létezik.

7. Irigységmentesség-kivéve a legolcsóbb ( EFx ) :  Bármely két A és B ágens esetén, ha eltávolítjuk a B ügynökből azt az elemet, amely a legkevésbé értékes A ügynök számára, akkor A nem irigyli B-t. Az EFx szigorúan erősebb, mint EF1. Nem ismert, hogy az EFx eloszlás mindig létezik-e.

Globális optimalitási kritérium

A globális optimalitási kritérium egy adott szociális jóléti függvény alapján particionál :

• Az egalitárius szociális jólét az egyéni ügynök minimális jóléte. Egy tételeloszlásról akkor beszélünk akkor, ha a lehető legnagyobb egalitárius társadalmi jólétet éri el, azaz maximalizálja a legszegényebb szereplő jólétét. Mivel többféle eloszlás létezik, amelyek maximalizálják a legalacsonyabb jólétet, az egalitárius optimalitást gyakran leximin-optimálisnak nevezik  – a legkisebb jólétet maximalizáló eloszlások részhalmazából ez az eloszlás kiválasztja azokat az eloszlásokat, amelyek maximalizálják a második legkisebb jólétet, majd a harmadikat. legkisebb jólét, és így tovább.
• A Nash szociális jólét  az ügynökök jólétének a terméke. Egy eloszlást Nash-optimálisnak vagy Nash Maximális gazdagságnak nevezünk , ha maximalizálja a jólét szorzatát. Az optimális Nash-eloszlásoknak van néhány hasznos igazságossági tulajdonsága [11] .

A globális optimalizálási kritériumok előnye az egyedi kritériumokkal szemben, hogy a jólét-maximalizáló allokációk Pareto-hatékonyak .

Elosztási algoritmusok

Tőke Max-min-share

Az ügynök MFS-számításának problémája NP-teljes  – ezt úgy mutathatjuk ki, hogy a problémát levezetjük a számkészlet particionálási problémájából [8] .

Az MFS-kiosztás a legtöbb esetben létezik, de nem mindig. Nagyon ritka esetek, amikor nem létezik ilyen eloszlás [12] .

Az MFS-eloszlás létezésének meghatározásának problémája , azaz megoldható nem-determinisztikus polinomiális időben egy NP-nehéz probléma prediktorával (a prediktor szükséges az ügynök max-min-share kiszámításához). Ennek a problémának a pontos számítási bonyolultsága azonban továbbra sem ismert [8] .

Mindig léteznek olyan allokációk, amelyek minden résztvevő számára garantálják a fenti érték 2/3-át [12] . A terjesztési eljárást a spliddit webszolgáltatásban valósították meg [13] .

Arányosság

1. Tételezzük fel, hogy az ügynökök numerikus segédfunkcióval rendelkeznek az objektumokon. Ekkor az a probléma, hogy van-e arányos eloszlás, egy NP-teljes probléma – ezt a számhalmaz particionálási feladatából  való redukcióval kaphatjuk meg [8] .

2. Tegyük fel, hogy az ágensek az objektumok sorrendi sorrendjében rendelkeznek azonos (preferencia szerinti) objektumok jelenlétével vagy hiányával. Ekkor a probléma, hogy szükségszerűen van-e arányos eloszlás, megoldható polinomiális időben - ezt úgy kaphatjuk meg, hogy abból az ellenőrzési feladatból redukálható, hogy egy bipartit gráf enged-e elfogadható b-illesztést ( egy olyan illesztést , amelyben az éleknek van kapacitása) [14] .

Két ügynökre létezik egy egyszerűbb algoritmus [15] .

3. Tételezzük fel, hogy az ügynökök sorszámú objektumokkal rendelkeznek, azonos (előnyös) elemek nélkül. Ekkor polinomiális időben megoldható az a probléma, hogy van-e szükségszerűen arányos eloszlás. Nem ismert, hogy ez igaz-e, ha az ágensek semlegességet fejezhetnek ki (vagyis megmutathatják, hogy két elem azonos értékű számára) [14] .

Fairness Min-max-share

Az mFS ügynök kiszámításának feladata coNP-teljes .

Az a probléma, hogy létezik-e mFS-eloszlás , de ennek pontos számítási bonyolultsága továbbra is ismeretlen [8] .

Nincs irigység (nincs pénz)

Irigység hiánya (pénzzel)

Az irigységmentességet könnyebb elérni, ha feltételezzük, hogy az ügynökök értékelései pénzben kifejezve kvázi lineárisak, és ezért lehetővé teszik a kompenzáció átutalását az ügynökök között.

Demange, Gale és Sotomayor egy természetes, alulról felfelé építkező aukciót mutatott be, amely irigységmentes kiosztást eredményez, készpénzes kifizetésekkel egy objektumra (ahol minden licitáló legfeljebb egy tárgy iránt érdeklődik) [16] .

A Fair by Design egy  általános terv irigységmentes optimalizálási problémákra, amely természetesen kiterjeszti az objektumok igazságos elosztását pénzbeli kifizetésekkel [17] .

Cavallo [18] az irigység hiányának, az arányosságnak és a hatékonyságnak (jólétnek) a hagyományos bináris kritériumait olyan mértékekre általánosította, amelyek 0 és 1 közötti tartományba esnek. A kanonikus igazságos felosztás feltételei között minden hatékony elosztási mechanizmusra , a jó közérzet foka legrosszabb esetben 0, az aránytalanság mértéke pedig 1. Vagyis a legrosszabb eset eredményei a lehető legrosszabbak. Ez erősen motiválja az átlagos eset elemzését. Olyan mechanizmust keresett, amely magas jólétet, alacsony féltékenységet és alacsony elvárások aránytalanságát éri el a méltányos megosztási beállítások spektrumában. Megmutatta, hogy a Vickrey-Clark-Groves mechanizmus nem kielégítő, a Bailey [19] és Cavallo [20] újraelosztási mechanizmus viszont igen.

Egalitárius-optimális eloszlás

Egy általános forma numerikus becslésével az egalitárius optimális eloszlások, vagy akár megközelítőleg optimális eloszlások megtalálása NP-nehéz probléma. Ezt a számhalmaz particionálási problémájából való redukcióval lehet bizonyítani . Minél korlátozottabbak a becslések, annál jobb közelítéseket kaphatunk [21] :

• Additív segédprogramok esetén bármely egész szám esetén az ügynökök törtrésze legalább értékű segédprogramot kap . Ez az eredmény a lineáris programozási probléma megfelelő lazításával és a lineáris programozási probléma lehető legjobb eredményének kerekítésével érhető el.
• Két áruosztálynál van egy közelítés .
• Van egy közelítés a szubmoduláris hasznossági függvényekkel

Nguyen, Ruus és Rote cikkében [22] és N.-T. Nguyen, TT Nguyen, Ruus és Rote [23] néhány erősebb eredményt mutat be.

Az additív hasznosság melletti egalitárius társadalmi jóléti optimalizálás egy speciális esetét "Mikulás-problémának" nevezik [24] . A probléma továbbra is NP-nehéz, és nem közelíthető 1/2-nél nagyobb tényezővel, de van egy közelítés [25] és egy bonyolultabb közelítés [26] . Lásd még Dal'Aglio és Mosca [27] cikkét a két partner elágazó és kötött algoritmusához .

A csökkenő szükségleti eljárás a szokásos értelemben vett egalitárius optimális felosztást adja vissza – maximalizálja a rangot, amikor az ügynök legalacsonyabb rangú csomagjait lineárisan rangsorolják. Ez tetszőleges számú ügynökkel és tetszőleges csomagsorrenddel működik.

Nash-optimális disztribúciók

Nguyen, Ruus és Rote cikkében [22] és N.-T. Nguyen, TT Nguyen, Ruus és Rote [23] bebizonyította, hogy nehéz az utilitarista és a Nash optimális eloszlások kiszámítása.

Nguyen és Rote [28] egy közelítő eljárást mutatott be Nash optimális eloszlására.

Mintasorozat

A komissiózási sorrend egy egyszerű protokoll, ahol az ügynökök felváltva választják ki az elemeket valamilyen előre meghatározott sorrend alapján. A cél egy olyan mintavételi sorozat megtervezése, amely maximalizálja a társadalmi jóléti függvény (pl. egalitárius vagy haszonelvű) várható értékét, bizonyos valószínűségi feltételezések mellett az ágensek becsléseire vonatkozóan.

Különféle megosztások

A cikk-hozzárendeléssel kapcsolatos legtöbb kutatás azt feltételezi, hogy minden ügynök egyenlő részesedéssel rendelkezik. Sok esetben azonban vannak más részvényekkel rendelkező ügynökök. Az egyik ilyen eset a Miniszteri Kabinet pártok szerinti felosztása. Gyakran feltételezik, hogy minden pártnak a parlamenti mandátumok számával arányos számú minisztériumot kell kapnia. Lásd Brahms és Kaplan [29] , Aziz [30] és Segala-Helevy [31] tanulmányát a probléma és néhány megoldási javaslat megvitatásához.

Jegyzetek

1. ↑ Bouveret, Chevaleyre, Maudet, 2016 , p. 285.
2. ↑ Barbera, Bossert, Pattanaik, 2004 , p. 44–48.
3. ↑ Bouveret, Endriss, Lang, 2010 .
4. ↑ Brams, Edelman, Fishburn, 2003 , p. 147.
5. ↑ Brams, 2005 , p. 387–421.
6. ↑ Bouveret, Chevaleyre, Maudet, 2016 , p. 287-288.
7. ↑ Bouveret, Chevaleyre, Maudet, 2016 , p. 289-294.
8. ↑ 1 2 3 4 5 6 7 8 9 Bouveret, Lemaître, 2015 , p. 259.
9. ↑ Budish, 2011 , p. 1061–1103.
10. ↑ 1 2 Heinen, Nguyen, Rothe, 2015 , p. 521.
11. ↑ 1 2 Caragiannis, Kurokawa és Moulin, 2016 , p. 305.
12. ↑ 1 2 Procaccia, Wang, 2014 , p. 675–692.
13. ↑ Áruk felosztása - Spliddit . Letöltve: 2019. október 15. Az eredetiből archiválva : 2019. október 19. (határozatlan)
14. ↑ 1 2 Aziz, Gaspers, MacKenzie, Walsh, 2015 , p. 71–92.
15. ↑ Pruhs, Woeginger, 2012 , p. 305.
16. ↑ Demange, Gale, Sotomayor, 1986 , p. 863–872.
17. ↑ Mu'alem, 2014 , p. 29–46.
18. ↑ Cavallo, 2012 .
19. ↑ Bailey, 1997 , p. 107–126.
20. ↑ Cavallo, 2006 , p. 882.
21. ↑ Daniel Golovin. Az oszthatatlan áruk max-min méltányos elosztása . CMU (2005). Letöltve: 2016. augusztus 27. Az eredetiből archiválva : 2017. február 2.. (határozatlan)
22. ↑ 1 2 Nguyen, Roos, Rothe, 2013 , p. 65–90.
23. ↑ 1 2 Nguyen, Nguyen, Roos, Rothe, 2013 .
24. ↑ Bansal, Sviridenko, 2006 , p. 31.
25. ↑ Bezaková, Dani, 2005 , p. tizenegy.
26. ↑ Asadpour, Saberi, 2010 , p. 2970.
27. ↑ Dall'Aglio, Mosca, 2007 , p. 218.
28. ↑ Nguyen, Rothe, 2013 .
29. ↑ Brams, Kaplan, 2004 , p. 143.
30. ↑ Aziz, Haris; Gaspers, Serge; Mackenzie, Simon & Walsh, Toby (2017), Competitive Equilibrium with Invisible Goods and Generic Budgets, arΧiv : 1703.08150 [cs.GT]. 
31. ↑ Segal-Halevi, 2018 , p. 1267–1275.

Irodalom

• Sylvain Bouveret, Yann Chevaleyre, Nicolas Maudet. 12. fejezet: Az oszthatatlan javak igazságos elosztása // Handbook of Computational Social Choice / Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. - Cambridge University Press, 2016. - ISBN 9781107060432 .
• Barberà S., Bossert W., Pattanaik PK Objektumkészletek rangsorolása. // A hasznosságelmélet kézikönyve. – Springer USA, 2004.
• Sylvain Bouveret, Ulle Endriss, Jérôme Lang. Fair Division Under Ordinal Preferences: Computing Envy-Free Allocations of Invisible Goods // Proceedings of the 2010 Conference on ECAI 2010: 19. European Conference on Artificial Intelligence . – 2010.
• Steven J. Brams, Paul H. Edelman, Peter C. Fishburn. Az oszthatatlan tételek igazságos felosztása // Elmélet és döntés. - 2003. - T. 55 , sz. 2 . - doi : 10.1023/B:THEO.0000024421.85722.0a .
• Brams SJ Efficient Fair Division: segítsen a legrosszabb helyzetben lévőknek, vagy elkerülje az irigységet? // Racionalitás és társadalom. - 2005. - T. 17 , sz. 4 . - doi : 10.1177/1043463105058317 .
• Sylvain Bouveret, Michel Lemaître. Konfliktusok jellemzése az oszthatatlan javak igazságos felosztásában egy kritériumskála segítségével // Autonomous Agents and Multi-Agent Systems. - 2015. - T. 30 , sz. 2 . - doi : 10.1007/s10458-015-9287-3 .
• Tobias Heinen, Nhan-Tam Nguyen, Jörg Rothe. Méltányosság és rangsúlyozott haszonelvűség az erőforrások elosztásában // Algoritmikus döntéselmélet. - 2015. - T. 9346. - (Számítástechnikai előadásjegyzetek). — ISBN 978-3-319-23113-6 . - doi : 10.1007/978-3-319-23114-3_31 .
• Trung Thanh Nguyen, Jörg Rothe. Irigységarány és átlag – társadalmi jólétünk optimalizálása a többügynökös erőforrás-elosztásban. — AAMAS 2013. 13.
• 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. - ISBN 9781450339360 . - doi : 10.1145/2940716.2940726 .
• Haris Aziz, Serge Gaspers, Simon MacKenzie, Toby Walsh. Oszthatatlan objektumok méltányos hozzárendelése rendes preferenciák alatt // Mesterséges intelligencia. - 2015. - T. 227 . - doi : 10.1016/j.artint.2015.06.002 . - arXiv : 1312.6546 .
• Kirk Pruhs, Gerhard J. Woeginger. A válás egyszerűen // Fun with Algorithms. - 2012. - T. 7288. - (Számítástechnikai előadásjegyzetek). - ISBN 978-3-642-30346-3 . - doi : 10.1007/978-3-642-30347-0_30 .
• Ruggiero Cavallo. Méltányosság és jólét az újraelosztás révén, ha a segédprogram átruházható . – AAAI-12, 2012.
• Martin J. Bailey. Az igényfeltáró folyamat: A felesleg szétosztása // Public Choice. - 1997. - T. 91 , sz. 2 . - doi : 10.1023/A:1017949922773 .
• Ruggiero Cavallo. Optimális döntéshozatal minimális pazarlás mellett // Az autonóm ágensek és többágens rendszerek ötödik nemzetközi közös konferenciájának előadásai - AAMAS '06. - 2006. - ISBN 1595933034 . - doi : 10.1145/1160633.1160790 .
• Trung Thanh Nguyen, Magnus Roos, Jörg Rothe. A többágens erőforrás-allokáció társadalmi jóléti optimalizálásának közelíthetőségi és megközelíthetetlenségi eredményeinek felmérése // Annals of Mathematics and Artificial Intelligence. - 2013. - T. 68 , sz. 1–3 . - doi : 10.1007/s10472-012-9328-4 .
• Nhan-Tam Nguyen, Trung Thanh Nguyen, Magnus Roos, Jörg Rothe. A szociális jóléti optimalizálás számítási összetettsége és közelíthetősége többügynökös erőforrás-allokációban // Autonomous Agents and Multi-Agent Systems. - 2013. - T. 28 , sz. 2 . - doi : 10.1007/s10458-013-9224-2 .
• Nikhil Bansal, Maxim Sviridenko. A Mikulás-probléma // A harmincnyolcadik éves ACM számítástechnikai elméleti szimpózium anyaga - STOC '06. - 2006. - ISBN 1595931341 . - doi : 10.1145/1132516.1132522 .
• Ivona Bezakova, Varsha Dani. Oszthatatlan áruk kiosztása // ACM SIGecom Exchanges. - 2005. - V. 5 , sz. 3 . - doi : 10.1145/1120680.1120683 .
• Arash Asadpour, Amin Saberi. Egy közelítő algoritmus az oszthatatlan áruk max-min méltányos elosztásához // SIAM Journal on Computing. - 2010. - T. 39 , sz. 7 . - doi : 10.1137/080723491 .
• Marco Dall'Aglio, Raffaele Mosca. Hogyan kell igazságosan elosztani a kemény cukorkákat // Mathematical Social Sciences. - 2007. - T. 54 , sz. 3 . - doi : 10.1016/j.mathsocsci.2007.04.008 .
• Steven J. Brams, Todd R. Kaplan. Az oszthatatlan felosztása // Elméleti Politikai folyóirat. - 2004. - T. 16 , sz. 2 . - doi : 10.1177/0951629804041118 .
• Erel Segal-Halevi. Versenyképes egyensúly szinte minden bevételre // Proceedings of AAMAS 2018. - International Foundation for Autonomous Agents and Multiagent Systems, 2018.
• Gabrielle Demange, David Gale, Marilda Sotomayor. Többtételes aukciók // Journal of Political Economy. - 1986. - T. 94 , sz. 4 . - doi : 10.1086/261411 . — .
• Ahuva Mu'alem. Fair by design: Többdimenziós irigységmentes mechanizmusok // Games and Economic Behavior. - 2014. - T. 88 . - doi : 10.1016/j.geb.2014.08.001 .
• Budish E. A kombinatorikus hozzárendelési probléma: Hozzávetőleges versenyképességi egyensúly egyenlő jövedelmekből // Journal of Political Economy. - 2011. - T. 119 , sz. 6 . - doi : 10.1086/664613 .
• Ariel D. Procaccia, Junxing Wang. Elég korrekt: hozzávetőleges maximális részesedés garantálása. – EC '14 Proceedings of the Tizenötödik ACM Conference on Economics and Computing. - 2014. - ISBN 9781450325653 . - doi : 10.1145/2600057.2602835 .