Megosztás maximalizálása

A megosztás maximalizálása (MMD, eng.  Maximin share , MMS) az objektumok igazságos elosztásának kritériuma . Adott egy halmaz különböző értékű objektumokat, az 1-out-n maximin-share jelenti azt a legnagyobb értéket, amelyet az objektumok n részre bontásával és a minimális értékű rész kiválasztásával kaphatunk.

Az objektumok eloszlását n különböző pontszámú ügynök között MMD-fair- nek nevezzük, ha minden ügynök olyan halmazt kap, amely legalább olyan jó, mint az 1 -ből n -es maximális részesedése. Az MDM-igazságot Eric Budisch [1] javasolta az arányossági kritérium gyengítéseként – minden ügynök kap egy halmazt, amelynek értéke nem kisebb, mint az egyenlő eloszlás (1/ n minden erőforrás). Az arányosság garantálható, ha az objektumok oszthatók, de nem, ha oszthatatlanok, még akkor sem, ha minden ügynök azonos becsléssel rendelkezik. Ezzel szemben az MMD-méltányosság mindig garantálható azonos szerekre, így ez az arányosság természetes alternatívája akkor is, ha a szerek eltérőek.

Motívumok és példák

Ugyanazok a tárgyak. Először is tegyük fel, hogy m azonos tárgyat igazságosan kell elosztani n ember között. Ideális esetben mindenkinek m / n objektumot kell kapnia, de kiderülhet, hogy ha m nem osztható n -nel , ez lehetetlen, mivel az objektumok oszthatatlanok. A természetes második szintű kritérium az, hogy m / n - t lefelé kerekítsünk a legközelebbi egész számra, és minden személynek legalább emelet( m / n ) objektumot adjunk. A padlónál ( m / n ) kisebb tárgyak beszerzése „túl igazságtalan” lenne – ezt az igazságtalanságot már nem lehet elfedni a tárgyak oszthatatlanságával.

Kitüntetett tárgyak. Most tegyük fel, hogy az objektumok különböznek egymástól, és mindegyiknek más az értéke. Előfordulhat, hogy most a legközelebbi egész számra lefelé kerekítve nem adjuk meg a kívánt megoldást. Tegyük fel például, hogy n = 3 és m = 5, és az objektumok értéke 1, 3, 5, 6, 9. Az értékek összege 24, és ez a szám osztható 3-mal, tehát ideális esetben megadná minden résztvevő egy elemet, legalább 8-as értékkel, de ez nem lehetséges. A legmagasabb érték, amit minden ügynöknek garantálni tudunk, a 7, ami a {1,6},{3,5},{9} eloszlásból adódik.

Azt az {1,6} halmazt, amelyen a maximin értékét elérjük, "1-out-3 maximin-parts"-nak nevezzük - ez az objektumok legjobb részhalmaza, amelyet úgy lehet létrehozni, hogy az eredeti halmazt 3 részre osztjuk, és kiválasztjuk a legkevésbé jelentős halmaz. Ezért ebben a példában az eloszlás akkor és csak akkor MMD-tisztességes, ha az egyes ügynökök által kapott érték legalább 7.

Változó értékelések. Tegyük fel , hogy például minden ügynök másként értékeli az egyes objektumokat

Most minden ügynök más-más MMD-készlettel rendelkezik:

Itt az eloszlás MMD-tisztességes, ha Alice-nek legalább 7-et, George-nak legalább 8-at, Dinának pedig legalább 3-as értéket ad. Például egy olyan eloszlás, amelyben George megkapja az első két objektumot: {1,7 }, Alice megkapja a következő két {5,6} és Daina objektum {17} MMD-fair.

Értelmezés . Egy ügynök 1-out- n MMD-je úgy értelmezhető, mint az a maximális hasznosság, amelyet az ügynök remélhet nyerni egy disztribúcióból, ha más ügynökök is ugyanolyan preferenciákkal rendelkeznek, ha mindig ő kapja a legrosszabb részesedést. Ez az a minimális hasznosság, amelyre az ügynök jogosult (szerinte), a következő érvek alapján: ha más ágensek ugyanazokkal a preferenciákkal rendelkeznek, mint én, akkor van legalább egy disztribúció, amely megadja nekem ezt a hasznosságot, és más ügynökök nem kevesebbet, ezért nincs okuk kevesebbet adni nekem.

Alternatív értelmezés: az ügynök számára legelőnyösebb halmaz, amelyet az osztó garantál az oszd meg és válassz protokollban a rivális ellenfelek között - az ügynök a legjobb allokációt javasolja és a halmazkiválasztási szabályt másokra hagyja, míg a fennmaradó halmazt átveszi [2 ] .

Az MMD-méltányosság az alábbi tárgyalási folyamat eredményeként is leírható. Valamilyen elosztást javasoltak. Minden ügynök panaszkodhat egy ilyen elosztásra, és felajánlhatja a sajátját. Azonban miután ezt megtette, engednie kell a többieknek, hogy elvegyék a részeiket, míg ő maga veszi át a maradék készletet. Ezért egy ügynök csak akkor panaszkodik egy disztribúcióra, ha tud olyan disztribúciót kínálni, amelyben minden halmaz jobb, mint a jelenlegi. Egy allokáció akkor és csak akkor tisztességes MMD-vel, ha egyik ügynök sem panaszkodik rá, azaz bármely allokációban bármelyik ügynök számára van egy halmaz, amely semmivel sem jobb, mint az a részesedés, amelyet az aktuális allokációban kap.

MMD-fair disztribúciók létezése

Ha mind az n ügynöknek azonos az értékelése, akkor definíció szerint mindig létezik MMD-méltányos eloszlás.

Ha csak n -1 ügynöknek van azonos pontszáma, az MMD-méltányos eloszlás továbbra is létezik, és megtalálható az oszd meg és válassz protokoll használatával - n -1 azonos ágens n készletre osztja az objektumokat , amelyek mindegyike nem rosszabb, mint az MMD, akkor az n- edik ügynök kiválasztja a legmagasabb pontszámot elért halmazt, és az azonos ágensek rendezik a fennmaradó n -1 halmazt.

Konkrétan két ügynök esetében mindig létezik MMD-méltányos eloszlás.

Bouvre és Lemaitre [2] több mint 2 ágens véletlenszerű adatain végzett intenzív szimulációkat, és azt találta, hogy az MMD-méltányos eloszlás minden kísérletben létezett. Bebizonyították, hogy MMD-fair eloszlások léteznek a következő esetekben:

Procaccia és Won [3] , valamint Kurokawa [4] konstruált egy példát n= 3 ügynökkel és m =12 objektummal, amelyben az elosztás minden ügynöknek 1-out-3 MMD-t garantál. Sőt, megmutatták, hogy mindenre van példa a tárgyakkal.

Multiplikatív közelítés

Az MMD-eloszlások hiánya esetén Procaccia és Vaughn az MMD szorzó közelítését javasolta – az eloszlást r-részesedés MMD- nek nevezik a [0,1]-ből származó r néhány törtére, ha bármely ágens értéke nem kisebb, mint MMD-je értékének r töredéke.

Bemutattak egy algoritmust, amely mindig megtalálja a megosztott MMD-t, ahol , és oddfloor( n ) a legnagyobb páratlan egész szám, amely nem haladja meg az n értéket . Konkrétan , csökken, ahogy n növekszik , és mindig nagyobb, mint . Algoritmusuk m -ben polinomiális időben fut, ha n konstans.

Amanatidis, Markakis, Nikzad és Saberi [5] bebizonyították, hogy véletlenszerűen generált problémák esetén nagy valószínűséggel léteznek MMD-fair eloszlások . Számos továbbfejlesztett algoritmust javasoltak

Barman és Krishnamurti [6] bemutatták

Godsi, Hadzhigoyi, Sedigin és Yami [7] javasolta

Garg, McGlaflin és Taki [8] egy egyszerű algoritmust javasoltak a 2/3-részes MMD-hez, amelynek elemzése egyszerű.

Jelenleg nem ismert, hogy mi az r legnagyobb értéke, amelyre mindig létezik r -részleges MMD eloszlás. Ez lehet 3/4 és 1 közötti szám (az 1-et nem számítva).

Amanatidis, Burmpas és Markakis [9] sebezhetetlen stratégiákat javasolt a közelítő MMD-fair eloszláshoz (lásd még Stratégiailag fair felosztás ):

Xin és Pingyang [10] a feladatok MMD-méltányos eloszlását tanulmányozták (negatív minősítésű objektumok), és kimutatták, hogy a 9/11-es részleges MMD-eloszlás mindig létezik.

Ordinális közelítés

Budish [1] egy másik közelítést javasolt az 1 -out- n MMD eloszlására - 1-out-( ) MMD (minden ügynök legalább annyit kap, amennyit n + 1 halmazra osztva és a legrosszabb közül kiválasztva kaphat) . Megmutatta, hogy a hozzávetőleges versenyegyensúly egyenlő jövedelemmel mindig garantálja az 1/-( ) MMD-t. Ez az eloszlás azonban meghaladhatja a rendelkezésre álló objektumok számát, és ami még fontosabb, meghaladhatja a szükségleteket - az összes ügynök számára kiosztott halmazok összege valamivel nagyobb lehet, mint az összes objektum összege. Az ilyen hiba elfogadható a kurzus hallgatóinak helyek kiosztásánál, mivel a kis létszámhiány kis számú szék hozzáadásával korrigálható. De a klasszikus igazságos felosztási probléma feltételezi, hogy az elemek nem adhatók hozzá.

Tetszőleges számú, additív becsléssel rendelkező ágens esetén az irigységmentes igazságos elosztás  egy kivételével ( EF1) minden ágensnek legalább 1-out-(2 n -1) MMD -t ad [11] . A BZ1 eloszlás megtalálható például az objektumok ciklikus eloszlásának vagy az irigység ciklusának használatával .

Sőt, az 1-out-(2 n -2) MMD eloszlás megtalálható irigységmentes párosítással [12] .

Jelenleg nem ismert, hogy mi az a minimális N , amelyre mindig létezik 1-out- N MMD-eloszlás. Bármely szám lehet n +1 és 2 n -2 között. Az n legkisebb értéke, amelyre ilyen N már nem ismert , a 4.

A kezdeti MDM feltétel aszimmetrikus ágensekre (az ezek miatt eltérő részesedésű ágensekre) használható [13] .

Egyéb algoritmikus problémák

Néhány alapvető algoritmus az MMD-vel kapcsolatban:

MMD-fairness csoportoknak

Egy allokációt páronkénti -maximin-share-fair- nek ( PMMS -fair ) nevezünk, ha az i  és j ügynökpárok bármelyike ​​esetén az i ügynök legalább az 1-ből 2-ből megkapja az objektumok által korlátozott részesedését a teljes halmazból. i és j objektumok [16] .

Az eloszlást group - wise-maximin-share-fair-nek ( GMMS -fair) nevezzük, ha a  k méretű ügynökök bármely alcsoportja esetén az alcsoport minden tagja megkapja a saját k-ből 1 - es maximális részesedését, korlátozottan. az ezen alcsoport által kapott objektumokra [17] .

Az igazságosság különféle fogalmai a következő módon kapcsolódnak az additív értékelésekhez.

A HMMD-eloszlások akkor garantáltan léteznek, ha az ügynökök becslései binárisak vagy azonosak. Általános additív becslések esetén 1/2-HMMD eloszlás létezik, és megtalálható polinomiális időben [17] .

Lásd még

Jegyzetek

  1. ↑ 1 2 Budish, 2011 , p. 1061–1103.
  2. ↑ 1 2 3 Bouveret, Lemaître, 2015 , p. 259.
  3. ↑ Procaccia, Wang, 2014 , p. 675–692.
  4. ↑ Archivált másolat . Letöltve: 2020. február 26. Az eredetiből archiválva : 2019. július 28.
  5. ↑ Amanatidis, Markakis, Nikzad, Saberi, 2017 , p. 1–28.
  6. ↑ Barman, Krishnamurthy, 2017 , p. 647-664.
  7. ↑ Ghodsi, Hajiaghayi et al., 2018 , p. 539-556.
  8. ↑ Garg, McGlaughlin, Taki, 2018 , p. 20:1–20:11.
  9. ↑ Amanatidis, Birmpas, Markakis, 2016 , p. 31-37.
  10. ↑ Huang, Lu, 2019 .
  11. ↑ Segal-Halevi, Suksompong, 2019 , p. 103167.
  12. ↑ Aigner-Horev, Segal-Halevi, 2019 .
  13. ↑ Segal-Halevi, 2019 .
  14. ↑ Woeginger, 1997 , p. 149–154.
  15. ↑ Lang, Rothe, 2016 , p. 493–550.
  16. ↑ 1 2 Caragiannis, Kurokawa et al., 2019 , p. 12:1–12:32.
  17. ↑ 1 2 3 Barman, Biswas, Krishnamurthy, Narahari, 2018 .
  18. ↑ Irigység ingyenesség a legkevésbé értékű jószágig .  Lásd Caragiannis, Kurokawa et al.

Irodalom