Proceduren "sidst reduceret"

Den sidste aftagende procedure er den retfærdige kageskæring . Proceduren er designet til at allokere en heterogen delbar ressource, såsom en fødselsdagskage, og involverer n deltagere i divisionen med forskellige præferencer for forskellige dele af kagen. Proceduren giver mulighed for , at n personer kan få en proportional opdeling , det vil sige at dele kagen imellem sig, så hver deltager får mindst ${\tfrac {1}{n))$ fuld værdi efter hans egen (subjektive) vurdering. For eksempel, hvis Alices vurdering af hele kagen er $100, og der er 5 deltagere, så kan Alice få et stykke, som hun værdsætter mindst $20, uanset hvad de andre deltagere tænker eller gør.

Historie

Under Anden Verdenskrig blev den polske jødiske matematiker Hugo Steinhaus , der gemte sig for nazisterne, interesseret i spørgsmålet om, hvordan man deler ressourcen retfærdigt. Inspireret af Delhi-and-Choose- proceduren med at dele en kage mellem to brødre, bad han sine elever, Stefan Banach og Bronisław Knaster , om at finde en procedure, der kunne fungere for flere mennesker, og offentliggjorde deres løsning [1] .

Denne publikation indledte en ny forskningsgren, som nu udføres af mange forskere inden for mange discipliner. Se artiklen Fair opdeling .

Beskrivelse

Nedenfor er forfatterens beskrivelse af delingsprotokollen:

”Der er deltager A, B, C, .. N. Deltager A skærer et vilkårligt stykke fra kagen. Medlem B har nu ret, men ikke pligt, til at reducere stykket ved at skære et stykke af. Efter at han har gjort dette, har C ret (men ikke pligten) til at reducere det allerede reducerede (eller ikke reducerede) stykke, og så videre til deltager N. Reglen forpligter den sidste der reducerede (afskåret) til at tage sit en del. Denne deltager forlader divisionen og de resterende n − 1 deltagere starter det samme spil med resten af kagen. Efter at antallet af deltagere er reduceret til to, anvender de den klassiske halveringsregel.

Hvert medlem har en metode, der sikrer, at det modtager en del med en værdi større end eller lig med . Metoden er som følger: klip altid det aktuelle stykke, så den resterende værdi er til dig. Der er to muligheder - enten får du den brik, du klipper af, eller også får den anden person en mindre brik, som du værdsætter mindre end . I sidstnævnte tilfælde er der n − 1 tilbageværende deltagere, og estimatet af den resterende kage er større end . Ved induktion kan vi bevise, at den resulterende værdi vil være mindst . ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {n-1}{n))$ ${\tfrac {1}{n))$

Et degenereret tilfælde af en generel præferencefunktion

Algoritmen er forenklet i det degenererede tilfælde, hvor alle deltagere har de samme præferencefunktioner, da den deltager, der lavede det første optimale snit, bliver den sidste til at reducere. Tilsvarende skærer hver deltager 1, 2, ..., n − 1 på skift et stykke fra den resterende kage. Derefter, i omvendt rækkefølge, vælger hver deltager n , n − 1, ..., 1 et stykke, der endnu ikke er blevet gjort krav på.

Analyse

Last Diminisher-protokollen er diskret og kan udføres i runder. I værste fald får du brug for handlinger - én handling pr. runde. ${\tfrac {n\ gange (n-1)}{2}}=O(n^{2})$

De fleste af disse handlinger er dog ikke rigtige klip, dvs. Alice kan markere det ønskede stykke på papiret, og den anden deltager reducerer det på det samme stykke papir, og så videre. Kun den "sidste skærer" skal faktisk skære kagen. Der er således kun brug for n − 1 snit. $O(n^{2})$

Proceduren er meget liberal med hensyn til snit. Indsnittene foretaget af deltagerne kan have enhver form. De kan endda være usammenhængende. På den anden side kan udskæringer begrænses for at sikre, at stykkerne har en acceptabel form. I særdeleshed:

Hvis den originale kage er forbundet, så kan hvert stykke garanteres at blive forbundet (kontinuerligt).
Hvis den originale kage er et konveks sæt , kan hvert stykke garanteres at være konveks.
Hvis den originale kage er et rektangel , kan hvert stykke garanteres at være et rektangel.
Hvis den originale kage er en trekant , kan hvert stykke garanteres at være en trekant.

Kontinuerlig version

En tidskontinuerlig version af protokollen kan udføres ved hjælp af Moving Knife-proceduren af Dubins-Spanier [2] . Dette var det første eksempel på en kontinuerlig retfærdig opdelingsprocedure. Kniven bevæger sig over kagen fra venstre mod højre. Enhver deltager kan sige "stop", hvis han mener, at værdien af brikken til venstre for kniven er . Kagen skæres, og deltageren, der sagde "stop", modtager dette stykke. Gentag med den resterende kage og deltagere. Den sidste deltager får resten af kagen. I lighed med den sidste reduktionsprocedure kan denne procedure bruges til at opnå sammenhængende bidder for hver deltager. $1/n$

Omtrentlig version uden misundelse

Hvis der er 3 eller flere deltagere, er den partition, der opnås ved at bruge protokollen til sidst til at reducere, ikke altid fri for misundelse . Antag for eksempel, at den første spiller Alice får en brik (som hun vurderer til 1/3). Så deler de to andre, Bob og Charlie, efter deres mening resten retfærdigt, men efter Alices mening er Bobs andel 2/3 værd, mens Charlies andel er 0 værd. Det viser sig, at Alice er jaloux på Bob.

En simpel løsning [3] er at tillade returnering . Det vil sige, at den deltager, der vandt brikken i henhold til protokollen "den sidste der reducerede", forlader ikke spillet, men kan blive i spillet og deltage i de næste trin. Hvis han vinder igen, skal han returnere sin nuværende brik til kagen. For at sikre, at protokollen slutter, vælger vi en konstant og tilføjer en regel om, at hver deltager ikke kan vende tilbage til spillet mere end én gang. $\varepsilon$ ${\tfrac {1}{\varepsilon }}$

I returversionen har hvert medlem en metode til at sikre, at det modtager en chunk, hvis værdi er mindst lige så stor som den største chunk minus . Metoden er som følger: klip altid den aktuelle brik af, så den resterende del har en værdi plus din nuværende brik. Dette sikrer, at værdien af din brik vokser for hver gang, du vinder, og når du ikke vinder, overstiger værdien af vinderen ikke din egen værdi. Således overstiger niveauet af misundelse ikke . $\varepsilon$ $\varepsilon$ $\varepsilon$ $\varepsilon$

Algoritmens køretid overstiger ikke , da der højst er trin, og ved hvert trin spørger vi deltagerne. ${\tfrac {n^{2}}{\varepsilon }}$ ${\tfrac {n}{\varepsilon ))$ $n$

Ulempen ved den misundelsesfrie tilnærmelse er, at brikkerne ikke nødvendigvis hænger sammen, da brikkerne hele tiden går tilbage i kagen og bliver omfordelt. Se Jaloux Cake Cutting#Connected Pieces for andre løsninger på dette problem.

Forbedringer

Last Reducer-proceduren blev senere forbedret på forskellige måder. Se artiklen Proportional Divide for detaljer .

Noter

↑ Steinhaus, 1948 , s. 101-4.
↑ Dubins og Spanier, 1961 , s. en.
↑ Brams og Taylor 1996 , s. 130-131.

Litteratur

Steven J. Brams, Alan D. Taylor. Fair opdeling: fra kageskæring til konfliktløsning . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .
Lester Eli Dubins, Edwin Henry Spanier. Sådan skærer du en kage retfærdigt // The American Mathematical Monthly. - 1961. - T. 68 , no. 1 . - doi : 10.2307/2311357 . — .
Hugo Steinhaus. Problemet med retfærdig opdeling // Econometrica. - 1948. - T. 16 , Nr. 1 . — .