Austins Moving Knife Procedures

Austins "Moving Knife" -procedurer er upartiske kageopdelingsprocedurer . Procedurerne uddeler til hver af de n deltagere et stykke af kagen, som denne deltager vurderer præcist i hele kagen. Dette er i modsætning til proportional divisionsprocedurer , som giver hver deltager mindst en hel kage, men kan give hver deltager mere. $1/n$ $1/n$

Hvis snittet opnået ved Austin-proceduren er en nøjagtig opdeling, og der er ingen misundelse i det . Desuden er det muligt at skære kagen i et hvilket som helst antal k stykker, som hver af partnerne vurderer nøjagtigt til 1/ k . Derfor er det muligt at dele kagen mellem deltagerne i et hvilket som helst forhold (giv for eksempel 1/3 til Alice og 2/3 til George). $n=2$

Hvis , vil opdelingen hverken være nøjagtig eller misundelsesfri, da den kun vurderer sit eget stykke til , men evalueringen af andre stykker kan afvige fra denne værdi. $n>2$ $1/n$

Det vigtigste matematiske værktøj, der anvendes af Austin-proceduren, er mellemværdisætningen [1] [2] [3] .

To medlemmer og kagehalvdele

Grundlæggende procedurer går ud på, at deltagerne deler kagen, så begge deltagere modtager præcis halvdelen. $n=2$

To kniv procedure

For at lette beskrivelsen, lad os kalde de to spillere Alice og George og antage, at kagen er rektangulær.

Alice placerer den ene kniv til venstre for kagen og den anden parallelt med den til højre, hvor hun er ved at skære kagen i to.
Alice flytter begge knive til højre, så delen mellem knivene altid er halvdelen af kagen (efter hendes vurdering, selvom den fysiske afstand mellem knivene kan ændre sig).
George siger "stop!", da han tror, der er en halv kage mellem knivene. Hvordan kan vi være sikre på, at George vil sige ordet "stop!" på et tidspunkt? Faktum er, at hvis Alice når kanten med den højre kniv, skal positionen af den venstre kniv være på det samme sted, hvorfra den højre kniv startede. Mellemværdisætningen siger, at George skal være tilfreds med at skære kagen i to på et tidspunkt.
At kaste en mønt afgør to muligheder - enten får George en brik mellem knivene, og Alice får to ekstreme brikker, eller omvendt. Hvis deltagerne er ærlige, vil de blive enige om, at delen mellem knivene er præcis 1/2, så snittet bliver præcist.

En kniv procedure

En kniv kan bruges til at opnå samme effekt.

Alice drejer kniven over kagen til 180°, og holder halvdelene på begge sider af kniven lige.
George siger "stop!", når han er enig.

Alice skal selvfølgelig gennemføre knivdrejningen på samme linje, som hun startede fra. Igen, ifølge mellemværdisætningen, skal der være et punkt, hvor George mener, at de to halvdele er lige store.

To deltagere og dele af den generelle visning

Som Austin påpegede, kan to deltagere finde et stykke kage, som begge værdier nøjagtigt til et hvilket som helst heltal [2] . Lad os kalde ovenstående procedure som : $1/k$ $k\geqslant 2$ $\mathrm {Klip} _{2}(1/k)$

Alice laver parallelle mærker på kagen, så stykkerne er helt lige store . $k-1$ $k$ $1/k$
Hvis der er en del, som George mener også er lig med , er vi færdige med at udtrække den del. $1/k$
Ellers skal der være en del, som George vurderer til mindre end ved, og en tilstødende del, som George vurderer til større end . $1/k$ $1/k$
Lad Alice placere to knive på de to mærker af en af disse stykker og få hende til at flytte knivene parallelt, og hold værdien mellem knivene nøjagtigt på, indtil knivene lander på mærkerne af den anden brik. Ved mellemværdisætningen skal der være et punkt, hvor George skal være enig i, at værdien mellem knivene er nøjagtig . $1/k$ $1/k$

Ved rekursivt at anvende to deltagere kan de opdele hele kagen i dele, som begge deltagere hver især vurderer til nøjagtigt [2] : ${\displaystyle \mathrm {Klip} _{2))$ $k$ $1/k$

Vi bruger proceduren til at skære en brik af, som begge spillere værdsætter nøjagtigt til . $\mathrm {Klip} _{2}(1/k)$ $1/k$
Nu vurderer begge spillere resten af kagen præcis kl . Bruges til at skære en brik af, som begge spillere vurderer til nøjagtigt . $(k-1)/k$ $\mathrm {Klip} _{2}(1/(k-1))$ $1/k$
Vi fortsætter indtil vi får alle brikkerne. $k$

To parter kan nå frem til en nøjagtig opdeling med et hvilket som helst rationelt forhold mellem aktier, der skal betales ved en lidt mere kompliceret procedure [4] .

Mange medlemmer

Når man kombinerer proceduren med Fink-protokollen , er det muligt at dele kagen mellem deltagerne, så hver deltager modtager et stykke, som han vurderer til præcis [1] [5] : ${\displaystyle \mathrm {Klip} _{2))$ $n$ $1/n$

Deltagerne #1 og #2 bruger , for at give hver af dem præcis 1/2 efter hans mening. $\mathrm {Klip} _{2}(1/2)$
Deltager #3 bruger med Deltager #1 for at få præcis 1/3 af sin andel, og derefter med Deltager #2 for at få præcis 1/3 af sin andel. Deltager #1s tildelte andel af brikken vurderes af begge deltagere til præcis 1/6, så deltager #1 står tilbage med præcis 1/3. Det samme gælder for deltager nr. 2. For deltager nr. 3, selvom han kan vurdere brikkerne over eller under 1/6, skal summen af de to brikker være nøjagtigt 1/3 af hele kagen. $\mathrm {Klip} _{2}(1/3)$ $\mathrm {Klip} _{2}(1/3)$

Bemærk, at det resulterende snit ikke er nøjagtigt, da stykket kun vurderes af ejeren af stykket, men ikke nødvendigvis i samme mængde af andre deltagere. Fra 2015 var den nøjagtige delingsprocedure for deltagerne ikke kendt, kun næsten nøjagtige delingsprocedurer kendes . $n>2$ $1/n$ $n>2$

Se også

Austin -proceduren bruges af Brahms-Taylor-Zwicker-proceduren .
Andre procedurer og resultater af retfærdig deling og nøjagtig deling .

Noter

↑ 1 2 Austin, 1982 , s. 212.
↑ 1 2 3 Brams og Taylor, 1996 , s. 22-27.
↑ Robertson, Webb, 1998 , s. 66.
↑ Robertson, Webb, 1998 , s. 71.
↑ Brams og Taylor 1996 , s. 43-44.

Litteratur

Austin AK deler en kage // The Mathematical Gazette. - 1982. - T. 66 , no. 437 . - doi : 10.2307/3616548 . — .
Jack Robertson, William Webb. Kage-skæringsalgoritmer: Vær fair, hvis du kan. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .
Steven J. Brams, Alan D. Taylor. retfærdig opdeling. - 1996. - ISBN 978-0-521-55644-6 .
- Oversat af Stephen J. Brahms, Alan D. Taylor. Vi deler retfærdigt eller garanterer en gevinst til alle. - Moskva: SINTEG, 2002. - (Serie "Economics and Business"). - ISBN 5-89638-058-5 .