Starkt proportionell uppdelning

En starkt proportionell division (ibland kallad superproportionell division ) är en sorts rättvis division . Det är en uppdelning av resurser mellan n partners, där värdet som varje partner erhåller är strikt mer än hans/hennes förfallna andel av 1/ n av det totala värdet. Formellt, i en starkt proportionell uppdelning av en resurs C mellan n partners, får varje partner i , med värdemått V _{i , en andel} X _i sådan att

$V_{i}(X_{i})>V_{i}(C)/n$ .

Uppenbarligen existerar inte en starkt proportionell uppdelning när alla partners har samma värdemått. Det bästa tillståndet som alltid kan garanteras är ${\displaystyle V_{i}(X_{i})\geq V_{i}(C)/n} ,$ vilket är villkoret för en vanlig proportionell delning . Man kan dock hoppas att, när olika agenter har olika värderingar, kan det vara möjligt att använda detta faktum till förmån för alla spelare, och ge var och en av dem strikt mer än sin andel.

Existens

1948 anade Hugo Steinhaus existensen av en superproportionell uppdelning av en tårta :

Det kan för övrigt sägas att om det finns två (eller flera) partners med olika uppskattningar, så finns det en uppdelning som ger var och en mer än hans tillbörliga del ( Knaster ); detta faktum motbevisar den vanliga uppfattningen att skillnader i uppskattningar gör rättvis uppdelning svår.

1961 bevisade Dubins och Spanier att det nödvändiga villkoret för existens också är tillräckligt. Det vill säga, närhelst partnernas värderingar är additiva och icke-atomära, och det finns minst två partners vars värdefunktion till och med skiljer sig något, så finns det en superproportionell uppdelning där alla partners får mer än 1/ n .

Beviset var en följd av Dubins-Spaniers konvexitetsteorem . Detta var ett rent existentiellt bevis baserat på konvexitetsargument.

Algoritmer

1986 publicerade Douglas R. Woodall det första protokollet för att hitta en superproportionell division.

Låt C vara hela kakan. Om agenternas värderingar är olika, så måste det finnas ett vittne för det: ett vittne är en specifik bit av kakan, säg X ⊆ C , som värderas olika av några två partners, säg Alice och Bob. Låt Y := C \ X. Låt a _x =V _Alice (X) och b _x =V _Bob (X) och a _y =V _Alice (Y) och b _y =V _Bob (Y) , och anta wlog att:

b _x > a _x , vilket innebär: b _y < a _y .

Tanken är att partitionera X och Y separat: när vi partitionerar X kommer vi att ge något mer till Bob och något mindre till Alice; när vi partitionerar Y kommer vi att ge något mer till Alice och något mindre till Bob.

Woodalls protokoll för två agenter

Hitta ett rationellt tal mellan b _x och a _x , säg p/q så att b _x > p/q > a _x . Detta innebär b _y < (qp)/q < a _y . Be Bob dela X i p lika delar och dela Y till qp lika delar.

₀₀ Enligt våra antaganden värderar Bob varje del av X vid b _x /p > 1/ q , och varje del av Y vid b _y /(qp) < 1/ q . Men för Alice måste minst en bit av X (säg X ) ha ett värde mindre än 1/ q och minst en bit av Y (säg Y ) måste ha ett värde mer än 1/ q .

Så nu har vi två delar, X ₀ och Y ₀ , så att:

₀₀ V _Bob (X )>V _Alice (X )

₀₀ V _Bob (Y )<V _Alice (Y )

Låt Alice och Bob dela upp resten ₀ C \ X \ Y ₀ mellan sig på ett proportionellt sätt (t.ex. med dividera och välj ). Lägg till Y ₀ till biten av Alice och lägg till X ₀ till biten av Bob.

Nu tycker varje partner att hans/hennes tilldelning är strikt bättre än den andra tilldelningen, så dess värde är strikt sett mer än 1/2.

Woodalls protokoll för n partners

Utvidgningen av detta protokoll till n partners är baserat på Finks "Lone Chooser"-protokoll .

Anta att vi redan har en starkt proportionell uppdelning till i -1 partners (för i≥3 ). Nu kommer partner # i in i partiet och vi bör ge honom en liten bit från var och en av de första i -1-partnerna, så att den nya uppdelningen fortfarande är starkt proportionell.

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

Välj ett positivt heltal q så att: $d>{\frac {1}{(i-1)i(q(i- 1)-1)}}$

Be partner #1 att dela sin andel på $qi-1$ bitar som han anser vara lika värdefulla och låt den nya partnern välja de $q$ -bitar som han anser vara mest värdefulla.

Partner #1 kvarstår med värdet ${\frac {(qi-1)-q}{qi -1}}={\frac {q(i-1)-1}{qi-1}}$ av hans tidigare värde, vilket var ${\frac {1}{i- 1}}+d$ (enligt definition av d ). Det första elementet blir ${\frac {q(i-1)-1}{(i-1)(qi-1) }}$ och d blir ${\frac {1}{i(i-1)(qi-1)}}$ ; att summera dem ger att det nya värdet är mer än: ${\frac {(qi-1) (i-1)}{(i-1)i(qi-1)}}={\frac {1}{i}}$ av hela kakan.

När det gäller den nya partnern, efter att ha tagit q- bitar från var och en av de första i -1-partnerna, är hans totala värde minst: ${\frac {q}{qi-1} }>{\frac {1}{i}}$ av hela kakan.

Detta bevisar att den nya uppdelningen också är starkt proportionell.

Barbanels protokoll

Julius Barbanel utökade Woodalls algoritm till agenter med olika rättigheter , inklusive irrationella rättigheter. I den här inställningen representeras rättigheten för varje agent i av en vikt $w_{i}$ , med $W:=\sum _{i}w_{i}$ . En starkt proportionell allokering är en där för varje agent jag :

$V_{i}(X_{i})>w_{i}\cdot V_{i}(C)/W$ .

Janko-Joo protokoll

Janko och Joo presenterade en enklare algoritm för agenter med olika rättigheter. Faktum är att de visade hur man reducerar ett problem med starkt proportionell uppdelning (med lika eller olika rättigheter) till två problem med proportionell uppdelning med olika rättigheter :

För stycket X ändrar du berättigandet för Alice till $w_{A}-1/a_{x}$ och berättigandet för Bob till $w_ {B}+1/b_{x}$ . Eftersom b _x > a _x är summan av de nya rättigheterna strikt mindre än $w_{A}+w_{B}}$ _displaystyle , så summan av alla n rättigheterna (dentoed av W _X ) är strikt mindre än W.
För stycket Y ändrar du rätten för Alice till $w_{A}+1/a_{y}$ och berättigandet för Bob till $w_ {B}-1/b_{y}$ . Även här, eftersom b _y < a _y_{, är} den nya summan av alla rättigheter (dentoed av W _Y ) strikt mindre än W .
Alices värde är åtminstone ${\begin{aligned}&(w_ {A}-1/a_{x})\cdot a_{x}/W_{X}+(w_{A}+1/b_{y})\cdot b_{x}/W_{Y}=\\ =&(w_{A}a_{x}-1)/W_{X}+(w_{A}a_{y}+1)/W_{Y}\\>&(w_{A}a_{x} -1)/W+(w_{A}a_{y}+1)/W\\=&w_{A}V_{A}(C)/W\end{aligned}}$
På samma sätt är Bobs värde åtminstone ${\begin{aligned}&(w_ {B}+1/b_{x})\cdot b_{x}/W_{X}+(w_{B}-1/b_{y})\cdot b_{y}/W_{Y}=\\ =&(w_{B}b_{x}+1)/W_{X}+(w_{B}b_{y}-1)/W_{Y}\\>&(w_{B}b_{x} -1)/W+(w_{B}b_{y}+1)/W\\=&w_{B}V_{B}(C)/W\end{aligned}}$
Värdet av varannan agent i är minst ${\begin{aligned}&w_{i}\cdot V_{i}(X)/W_{X}+w_{i}\cdot V_{i}(Y)/W_{Y }\\>&w_{i}\cdot V_{i}(X)/W+w_{i}\cdot V_{i}(Y)/W\\=&w_{i}V_{i}(C)/ W\end{aligned}}$ Så uppdelningen är starkt proportionell.