Szuper arányos felosztás

A méltányos tortavágás keretében szuperarányos felosztásnak nevezzük azt a felosztást, amelyben minden résztvevő saját szubjektív értékelése szerint ( ) szigorúan nagyobb, mint a (teljes) erőforrás 1/ n -e . $V>1/n$

Szuper arányos osztás vs arányos osztás

A szuperarányos osztás jobb, mint az arányos osztás , amelyben minden résztvevő garantáltan legalább 1/ n ( ) kap. Az arányos osztással ellentétben azonban szuperarányos osztás nem mindig létezik. Ha egy divízióban minden résztvevőnek pontosan ugyanazok az értékelési funkciói vannak, a legjobb, amit minden résztvevőnek adhatunk, pontosan 1/ n . $V\geqslant 1/n$

A szuperarányos felosztás létezésének szükséges feltétele, hogy ne legyen minden résztvevő azonos értékmérővel.

A meglepő tény az, hogy abban az esetben, ha a becslések additívak és nem atomi, ez a feltétel is elegendő. Ez azt jelenti, hogy ha van legalább két résztvevő, akiknek az értékelési funkciói, még ha kissé eltérnek is, van egy szuperarányos felosztás, amelyben minden résztvevő 1/ n - nél többet kap .

Hipotézis

A szuperarányos felosztás létezését sejtésként 1948-ban javasolták [1] .

Közben elhangzott, hogy ha két (vagy több) résztvevő van különböző értékpontokkal, akkor van egy felosztás, amely nem csupán a részesedését adja meg ( Knaster ), és ez a tény cáfolja azt az általános elképzelést, hogy a pontszámok különbsége az igazságos felosztás nehezebb.

Létezési bizonyíték

A szuperarányos felosztás létezésének első publikált bizonyítéka a Dubins-Spanier konvexitástétel következménye volt . Ez pusztán elméleti , konvexitáson alapuló létezésbizonyítás volt.

Protokoll

A szuperarányos osztás megszerzésére szolgáló protokollt 1986-ban vezették be [2] .

Egy darab különböző értékelésekkel

Legyen C egy teljes torta. A jegyzőkönyv egy konkrét tortával kezdődik, mondjuk , amit két résztvevő bírál el. Tegyük fel, hogy Alice és Bob lesz. $X\subseteq C$

Legyen a=V Alice (X) és b=V Bob (X) , és az általánosság elvesztése nélkül tegyük fel, hogy b>a .

Két darab különböző minősítéssel

Keress egy racionális számot b és a között , mondjuk p/q , hogy b > p/q > a . Kérjük meg Bobot, hogy X - et vágja p egyenlő részre, C \ X -et pedig qp egyenlő részre.

Feltételezéseink szerint Bob értékei minden egyes X darabra nagyobbak, mint 1/ q , és minden egyes C \ X darabra kisebbek, mint 1/ q . Alice esetében azonban legalább egy X -nek (mondjuk Y ) kisebbnek kell lennie, mint 1/ q , és legalább egy C\X -nek (mondjuk Z ) 1/ q - nál nagyobbnak kell lennie .

Így van két Y és Z darabunk , amelyek:

V Bob (Y)>V Bob (Z) V Alice (Y)<V Alice (Z)

Szuperarányos felosztás két résztvevőre

Hagyja, hogy Alice és Bob arányosan osszák fel maguk között a maradék C \ Y \ Z részt (például az oszd meg és válassz protokollt használva ). Adjunk hozzá Z -t Alice darabjához és Y -t Bob darabjához.

Most minden résztvevő azt gondolja, hogy az ő megoszlása szigorúan nagyobb, mint bármely más eloszlás, ezért az érték szigorúan nagyobb, mint 1/2.

Szuperarányos felosztás n résztvevőre

Ennek a protokollnak egy n tagú kiterjesztése Fink "Single Chooser" protokollján alapul .

Tegyük fel, hogy már van szuperarányos felosztásunk az i -1 résztvevőkre (for ). Új #i résztvevő lép be a játékba, és adjunk neki néhány megosztást az első i -1 résztvevők közül, hogy az új felosztás szuperarányos maradjon. $i\geqslant 3$

Vegyük például az 1. partnert. Legyen d az 1. partner aktuális értéke és (1/( i -1)) különbsége . Mivel az aktuális felosztás szuperarányos, tudjuk, hogy d>0 .

Olyan q pozitív egész számot választunk , hogy $d>{\frac {1}{(i-1)i(q(i-1)-1)))$

Kérjük meg az 1. résztvevőt, hogy ossza fel a részét az általa egyenlőnek ítélt darabokra, és hagyja, hogy az új résztvevő válassza ki a számára legértékesebb darabokat. $qi-1$ $q$

Az 1. résztvevőnek megmarad az előző értékének az értéke, amely egyenlő volt (definíció szerint d ). Az első elem , d pedig . Összegzésükből kiderül, hogy az új érték meghaladja az egész tortát. ${\frac {(qi-1)-q}{qi-1}}={\frac {q(i-1)-1}{qi-1}}$ ${\frac {1}{i-1}}+d$ ${\frac {q(i-1)-1}{(i-1)(qi-1)))$ ${\frac {1}{i(i-1)(qi-1)))$ ${\frac {(qi-1)(i-1)}{(i-1)i(qi-1)}}={\frac {1}{i}}$

Miután az új résztvevő, miután minden első i -1 résztvevőtől kapott q részt, összértéke nem lesz kisebb, mint a teljes torta. ${\frac {q}{qi-1}}>{\frac {1}{i}}$

Ez azt bizonyítja, hogy az új felosztás is szuperarányos.

Jegyzetek

↑ Steinhaus, 1948 , p. 101–4.
↑ Woodall, 1986 , p. 300.

Irodalom

Hugo Steinhaus. Az igazságos felosztás problémája // Econometrica. - 1948. - T. 16 , sz. 1 . — .
Woodall DR Megjegyzés a tortaosztás problémájához // Journal of Combinatorial Theory, Series A. - 1986. - V. 42 , no. 2 . - S. 300 . - doi : 10.1016/0097-3165(86)90101-9 .