Superproportionell uppdelning

I samband med rättvis kakskärning är en superproportionell division en division där varje deltagare får en andel som är strikt större än 1/ n av den (totala) resursen enligt hans egen subjektiva bedömning ( ). $V>1/n$

Superproportionell division vs proportionell division

En superproportionell division är bättre än en proportionell division , där varje deltagare är garanterad att få minst 1/ n ( ). Men till skillnad från proportionell division existerar inte alltid superproportionell division. När alla deltagare i en division har exakt samma utvärderingsfunktioner är det bästa vi kan ge varje deltagare exakt 1/ n . $V\geqslant 1/n$

En nödvändig förutsättning för att det ska finnas en superproportionell uppdelning är att inte alla deltagare har samma värdemått.

Det överraskande faktum är att i fallet när uppskattningarna är additiva och inte atomära, är detta villkor också tillräckligt. Det vill säga, om det finns minst två deltagare vars utvärderingsfunktioner är även om de är något olika, finns det en superproportionell uppdelning där alla deltagare får mer än 1/ n .

Hypotes

Förekomsten av en superproportionell uppdelning föreslogs som en gissning 1948 [1] .

Det har sagts i förbigående att om det finns två (eller flera) deltagare med olika värdepoäng finns det en division som ger var och en mer än bara sin andel ( Knaster ), och detta faktum motbevisar den allmänna uppfattningen att skillnaden i poäng gör en rättvis uppdelning svårare.

Existensbevis

Det första publicerade beviset på förekomsten av en superproportionell division var en följd av Dubins-Spaniers konvexitetsteorem . Detta var ett rent teoretiskt existensbevis baserat på konvexitet.

Protokoll

Ett protokoll för att erhålla en superproportionell indelning infördes 1986 [2] .

En bit med olika betyg

Låt C vara en hel kaka. Protokollet börjar med en specifik tårta, säg , som bedöms av två deltagare. Låt oss säga att det blir Alice och Bob. $X\subseteq C$

Låt a=V Alice (X) och b=V Bob (X) och anta utan förlust av allmänhet att b>a .

Två stycken med olika betyg

Hitta ett rationellt tal mellan b och a , säg p/q , så att b > p/q > a . Låt oss be Bob att klippa X i p lika delar och klippa C \ X i qp lika delar.

Enligt våra antaganden är Bobs värden för varje bit X större än 1/ q , och för varje bit är C \ X mindre än 1/ q . För Alice måste dock minst en bit av X (säg Y ) ha ett värde mindre än 1/ q , och minst en bit av C\X ( säg Z ) måste ha ett värde större än 1/ q .

Således har vi två delar Y och Z så att:

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

Superproportionell uppdelning för två deltagare

Låt Alice och Bob dela resten av C \ Y \ Z mellan sig proportionellt (till exempel genom att använda dela-och-välj- protokollet ). Låt oss lägga till Z till Alices chunk och Y till Bobs chunk.

Nu tror varje deltagare att hans/hennes fördelning är strikt större än någon annan fördelning, så värdet är strikt större än 1/2.

Superproportionell uppdelning för n deltagare

En n -medlemsförlängning av detta protokoll är baserad på Finks "Single Chooser"-protokoll .

Anta att vi redan har en superproportionell indelning för i -1-deltagare (för ). En ny deltagare #i går in i spelet och vi bör ge honom några andelar från de första i -1-deltagarna så att den nya divisionen förblir superproportionell. $i\geqslant 3$

Tänk till exempel partner #1. Låt d vara skillnaden mellan partner #1:s nuvarande värde och (1/( i -1)). Eftersom den nuvarande divisionen är superproportionell vet vi att d>0 .

Vi väljer ett positivt heltal q så att $d>{\frac {1}{(i-1)i(q(i-1)-1)))$

Låt oss be deltagare #1 att dela upp sin andel i bitar som han anser vara lika, och låt den nya deltagaren välja de bitar som är mest värdefulla för honom. $qi-1$ $q$

Deltagare #1 lämnas med värdet av sitt tidigare värde, vilket var lika med (per definition d ). Det första elementet blir , och d blir . Deras summering ger att det nya värdet överstiger hela kakan. ${\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}}$

Efter att den nya deltagaren, efter att ha fått q delar från var och en av de första i -1-deltagarna, kommer att ha ett totalt värde som inte är mindre än hela kakan. ${\frac {q}{qi-1}}>{\frac {1}{i}}$

Detta bevisar att den nya uppdelningen också är superproportionell.

Anteckningar

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

Litteratur

Hugo Steinhaus. Problemet med rättvis uppdelning // Econometrica. - 1948. - T. 16 , nr. 1 . — .
Woodall DR A not on the cake-division problem // Journal of Combinatorial Theory, Series A. - 1986. - V. 42 , no. 2 . - S. 300 . - doi : 10.1016/0097-3165(86)90101-9 .