"egyszeri felosztás" eljárás

Az " egyszeri felosztás " eljárás egy arányos tortavágási eljárás . Az eljárás célja egy heterogén osztható erőforrás, például egy születésnapi torta kiosztása, és n résztvevőt von be a felosztásba, akik különböző preferenciákkal rendelkeznek a torta különböző részei tekintetében. Az eljárás lehetővé teszi, hogy n ember osztja fel egymás között a tortát úgy, hogy minden résztvevő megkapja legalább a saját (szubjektív) értékelése szerinti teljes értéket.

Az eljárást Hugo Steinhaus dolgozta ki n =3 főre [1] . Később Harold Kuhn kiterjesztette n >3-ra a Frobenius-Koenig tétel segítségével [2] . Az n =3 és n =4 eseteket Brahms és Taylor [3] , az általános esetet pedig Robertson és Webb [4] cikke írja le .

Leírás

A kényelem kedvéért normalizáljuk a résztvevők pontszámait úgy, hogy a teljes torta pontszámának értéke minden résztvevőnél n legyen. A cél az, hogy minden résztvevőnek legalább 1-es értéket adjon.

1. lépés . Véletlenszerűen kiválasztunk egy játékost, amit osztásnak nevezünk , és a tortát n darabra osztja , amelyek mindegyike az ő szemében pontosan 1-et ér.

2. lépés . A többi n -1 résztvevő mindegyike kiértékeli az így kapott n darabot, és beszámol arról, hogy melyiket tartja "elfogadhatónak", azaz ér legalább 1-et.

Most a válaszoktól függően a játék a 3. lépésre lép. Bemutatjuk az n = 3 esetet, majd az általános esetet.

Steinhaus eljárás n =3 -ra

Két eset van.

• A eset: A nem osztók legalább egyike két vagy több darabot jelöl meg elfogadhatónak. Ezután a harmadik résztvevő vesz egy elfogadható darabot ( a Dirichlet-elv szerint legalább egynek kell lennie), a második résztvevő egy elfogadható darabot (kettőt jelölt meg, így legalább egy marad), az osztó pedig a maradék darabot (a elválasztó minden darab elfogadható).
• B eset: Mindkét másik résztvevő csak egy-egy elfogadható darabot jelölt meg. Akkor van legalább egy darab, amely csak az elválasztó számára elfogadható. Az elválasztó elveszi ezt a darabot, és hazamegy. Ez a darab 1-nél kevesebbet ér a maradék két résztvevőnek, tehát a maradék két darab együtt legalább 2-t ér nekik. A maradékot az „ Oszd meg és válassz ” eljárással osztják fel.

Eljárás bármely n

Az általános esetet többféleképpen is leírhatjuk. A legrövidebb leírást Segal-Halevi és Aiger-Khorev [5] cikke tartalmazza . Ez az irigységmentes illesztés koncepcióján alapul , olyan párosításon, amelyben nincs nem illő ágens a megfelelő darab mellett.

3. lépés Készítünk egy kétrészes gráfot , amelyben X minden csúcsa egy ügynök, Y minden csúcsa pedig egy darab torta, és egy él köti össze az X ügynököt és az Y darabot akkor és csak akkor, ha X kiértékeli Y -t legalább 1-re.

4. lépés A maximális számosságot (a kombinációk száma szerint) irigység nélkül találjuk G -ben . Figyeljük meg, hogy az osztó mind az n darabhoz kapcsolódik, tehát (hol van X szomszédjainak halmaza Y -ben ). Ezért létezik egy nem üres irigység-mentes egyezés.

5. lépés A párból minden egyes darabot átadunk a megfelelő ügynöknek (vagyis az illesztésben ugyanabból a párból). Vegye figyelembe, hogy minden ilyen ügynök legalább 1-re értékeli az értékét, így boldogan mehet haza.

6. lépés A maradék tortát rekurzívan elosztjuk a maradék szerekkel. Vegyük észre, hogy a megmaradt ágensek mindegyike 1-nél kisebbre becsülte az adott darabokat, így a maradék torta becslése nem kisebb, mint az ágensek száma, így a rekurzió előfeltétele teljesül.

Lásd még

• Ugyanezen probléma megoldására szolgáló további eljárások megtalálhatók az " Arányos tortavágási probléma " című cikkben.
• Az "egyszeri felosztás" eljárás egyik előnye, hogy módosítható, hogy szimmetrikus, méltányos tortavágási eljárást kapjunk .

Jegyzetek

1. ↑ Steinhaus, 1948 , p. 101–4.
2. ↑ Kuhn, 1967 , p. 29–37.
3. ↑ Brams és Taylor 1996 , p. 31-35.
4. ↑ Robertson, Webb, 1998 , p. 83-87.
5. ↑ Segal-Halevi, Aigner-Horev, 2019 .

Irodalom

• Steven J. Brams, Alan D. Taylor. Tisztességes felosztás: a tortavágástól a vitarendezésig . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .
• Hugo Steinhaus. Az igazságos felosztás problémája // Econometrica. - 1948. - T. 16 , sz. 1 . — .
• Harold Kuhn. A tisztességes felosztás játékairól // Esszék a matematikai közgazdaságtanból Oskar Morgenstern tiszteletére . — Princeton University Press, 1967. Archiválva : 2019. január 16. a Wayback Machine -nál
• Erel Segal-Halevi, Elad Aigner-Horev. Irigységmentes egyezések kétoldalú grafikonokon és alkalmazásaik a tisztességes felosztásban  . — 2019.
• Jack Robertson, William Webb. Tortavágási algoritmusok: Legyen igazságos, ha tud. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .