Super proportional opdeling

I sammenhæng med retfærdig kageskæring er en superproportional division en division, hvor hver deltager modtager en andel, der er strengt taget større end 1/ n af den (samlede) ressource ifølge hans egen subjektive vurdering ( ). $V>1/n$

Super proportional division vs proportional division

En superproportional division er bedre end en proportional division , hvor hver deltager er garanteret at modtage mindst 1/ n ( ). Men i modsætning til proportional division eksisterer superproportional division ikke altid. Når alle deltagere i en division har nøjagtig de samme evalueringsfunktioner, er det bedste, vi kan give hver deltager, præcis 1/ n . $V\geqslant 1/n$

En nødvendig betingelse for eksistensen af en superproportional opdeling er, at ikke alle deltagere har samme værdimål.

Det overraskende faktum er, at i det tilfælde, hvor estimaterne er additive og ikke atomare, er denne betingelse også tilstrækkelig. Det vil sige, at hvis der er mindst to deltagere, hvis evalueringsfunktioner er, selvom de er lidt forskellige, er der en superproportional inddeling, hvor alle deltagere modtager mere end 1/ n .

Hypotese

Eksistensen af en superproportional opdeling blev foreslået som en formodning i 1948 [1] .

Det er blevet sagt i forbifarten, at hvis der er to (eller flere) deltagere med forskellige værdiscores, er der en division, der giver hver enkelt mere end blot sin andel ( Knaster ), og dette faktum modbeviser den generelle forestilling om, at forskellen i scores gør en retfærdig opdeling sværere.

Eksistensbevis

Det første offentliggjorte bevis på eksistensen af en superproportional division var en konsekvens af Dubins-Spanier konveksitetsteoremet . Dette var et rent teoretisk eksistensbevis baseret på konveksitet.

Protokol

En protokol til opnåelse af en superproportional division blev indført i 1986 [2] .

Et stykke med forskellige vurderinger

Lad C være en fuld kage. Protokollen begynder med et bestemt stykke kage, f.eks ., som bedømmes af to deltagere. Lad os sige, at det bliver Alice og Bob. $X\subseteq C$

Lad a=V Alice (X) og b=V Bob (X) og antag uden tab af almenhed, at b>a .

To stykker med forskellige vurderinger

Find et rationelt tal mellem b og a , sig p/q , sådan at b > p/q > a . Lad os bede Bob om at skære X i p lige store dele og skære C \ X i qp lige store dele.

Ifølge vores antagelser er Bobs værdier for hver brik X større end 1/ q , og for hver brik er C \ X mindre end 1/ q . Men for Alice skal mindst et stykke X (f.eks. Y ) have en værdi mindre end 1/ q , og mindst et stykke af C\X ( f.eks. Z ) skal have en værdi større end 1/ q .

Således har vi to stykker Y og Z , således at:

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

Superproportional opdeling for to deltagere

Lad Alice og Bob dele resten af C \ Y \ Z mellem sig proportionalt (f.eks. ved at bruge del-og-vælg- protokollen ). Lad os føje Z til Alices chunk og Y til Bobs chunk.

Nu tror hver deltager, at hans/hendes fordeling er strengt taget større end nogen anden fordeling, så værdien er strengt taget større end 1/2.

Superproportional inddeling for n deltagere

En n - medlem udvidelse af denne protokol er baseret på Finks "Single Chooser" protokol .

Antag, at vi allerede har en superproportional inddeling for i -1 deltagere (for ). En ny deltager #i går ind i spillet, og vi bør give ham nogle andele fra de første i -1 deltagere, så den nye division forbliver superproportional. $i\geqslant 3$

Overvej for eksempel partner #1. Lad d være forskellen mellem partner #1s aktuelle værdi og (1/( i -1)). Fordi den nuværende division er superproportional, ved vi, at d>0 .

Vi vælger et positivt heltal q sådan, at $d>{\frac {1}{(i-1)i(q(i-1)-1)))$

Lad os bede deltager #1 om at dele sin andel i stykker, som han anser for lige, og lade den nye deltager vælge de stykker, der er mest værdifulde for ham. $qi-1$ $q$

Deltager #1 står tilbage med værdien af sin tidligere værdi, som var lig med (per definition d ). Det første element bliver , og d bliver . Deres summering giver, at den nye værdi overstiger hele kagen. ${\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 at den nye deltager, efter at have modtaget q dele fra hver af de første i -1 deltagere, vil have en samlet værdi ikke mindre end hele kagen. ${\frac {q}{qi-1}}>{\frac {1}{i}}$

Dette beviser, at den nye opdeling også er superproportional.

Noter

↑ Steinhaus, 1948 , s. 101-4.
↑ Woodall, 1986 , s. 300.

Litteratur

Hugo Steinhaus. Problemet med retfærdig opdeling // Econometrica. - 1948. - T. 16 , Nr. 1 . — .
Woodall DR En note om kagedelingsproblemet // Journal of Combinatorial Theory, Series A. - 1986. - V. 42 , no. 2 . - S. 300 . - doi : 10.1016/0097-3165(86)90101-9 .