Austin's Moving Knife Procedures

Austins "Moving Knife" -procedurer är opartiska kakdelande procedurer . Procedurerna delar ut till var och en av de n deltagarna en bit av kakan, som denna deltagare utvärderar exakt i hela tårtan. Detta i motsats till procedurer för proportionell division , som ger varje deltagare minst en hel kaka, men kan ge varje deltagare mer. $1/n$ $1/n$

Om snittet som erhålls genom Austin-förfarandet är en exakt uppdelning och det finns ingen avundsjuka i det . Dessutom är det möjligt att skära kakan i valfritt antal k bitar, som var och en av partnerna utvärderar exakt till 1/ k . Därför är det möjligt att dela kakan mellan deltagarna i valfri proportion (ge till exempel 1/3 till Alice och 2/3 till George). $n=2$

Om , kommer indelningen varken att vara exakt eller avundsjuk, eftersom den bara utvärderar sin egen bit till , men utvärderingen av andra bitar kan skilja sig från detta värde. $n>2$ $1/n$

Det huvudsakliga matematiska verktyget som används av Austin-proceduren är mellanvärdessatsen [1] [2] [3] .

Två medlemmar och tårthalvor

Grundläggande rutiner innebär att deltagarna delar på tårtan så att båda deltagarna får exakt hälften. $n=2$

Två knivar procedur

För att underlätta beskrivningen, låt oss kalla de två spelarna Alice och George och anta att kakan är rektangulär.

Alice placerar en kniv till vänster om tårtan och den andra parallellt med den till höger, där hon ska skära kakan i två delar.
Alice flyttar båda knivarna åt höger så att delen mellan knivarna alltid är hälften av kakan (i hennes uppskattning, även om det fysiska avståndet mellan knivarna kan ändras).
George säger ”stopp!” när han tror att det ligger en halv kaka mellan knivarna. Hur kan vi vara säkra på att George kommer att säga ordet "stopp!" vid något tillfälle? Faktum är att om Alice når kanten med den högra kniven, bör positionen för den vänstra kniven vara på samma punkt som den högra kniven startade från. Mellanvärdessatsen säger att George någon gång ska nöja sig med att halvera kakan.
Att kasta ett mynt avgör två alternativ - antingen får George en bit mellan knivarna och Alice får två extrema bitar, eller vice versa. Om deltagarna är ärliga kommer de att hålla med om att delen mellan knivarna är exakt 1/2, så snittet blir korrekt.

En knivsprocedur

En kniv kan användas för att uppnå samma effekt.

Alice roterar kniven över kakan till 180° och håller halvorna på båda sidor av kniven lika.
George säger "stopp!" när han håller med.

Alice måste givetvis slutföra knivvarvet på samma linje som hon utgick från. Återigen, enligt mellanvärdessatsen måste det finnas en punkt där George tror att de två halvorna är lika.

Två deltagare och delar av den allmänna vyn

Som Austin påpekade kan två deltagare hitta en tårta som båda värdesätter exakt för vilket heltal som helst [2] . Låt oss kalla proceduren ovan som : $1/k$ $k\geqslant 2$ $\mathrm {Klipp} _{2}(1/k)$

Alice gör parallella märken på tårtan så att bitarna blir exakt lika . $k-1$ $k$ $1/k$
Om det finns en bit som George tror också är lika med , har vi slutfört att extrahera den biten. $1/k$
Annars måste det finnas en bit som George utvärderar till mindre än vid och en intilliggande bit som George utvärderar till större än . $1/k$ $1/k$
Låt Alice placera två knivar på de två märkena av en av dessa bitar och låt henne flytta knivarna parallellt, hålla värdet mellan knivarna exakt på tills knivarna landar på märkena på den andra biten. Med mellanvärdessatsen måste det finnas en punkt där George måste hålla med om att värdet mellan knivarna är exakt . $1/k$ $1/k$

Genom att rekursivt applicera två deltagare kan de dela upp hela kakan i delar, som båda deltagarna utvärderar till exakt [2] : ${\displaystyle \mathrm {Klipp} _{2))$ $k$ $1/k$

Vi använder proceduren för att skära av en bit som båda spelarna värderar exakt till . $\mathrm {Klipp} _{2}(1/k)$ $1/k$
Nu utvärderar båda spelarna resten av kakan exakt kl . Använd för att skära av en bit som båda spelarna uppskattar till exakt . $(k-1)/k$ $\mathrm {Klipp} _{2}(1/(k-1))$ $1/k$
Vi fortsätter tills vi får alla bitar. $k$

Två parter kan komma fram till en exakt uppdelning med valfritt rationellt förhållande mellan andelar som ska betalas genom ett något mer komplicerat förfarande [4] .

Många medlemmar

När man kombinerar proceduren med Fink-protokollet är det möjligt att dela kakan mellan deltagarna, så att varje deltagare får en bit som han utvärderar till exakt [1] [5] : ${\displaystyle \mathrm {Klipp} _{2))$ $n$ $1/n$

Deltagarna #1 och #2 använder , för att ge var och en av dem exakt 1/2, enligt hans åsikt. $\mathrm {Klipp} _{2}(1/2)$
Deltagare #3 använder med Deltagare #1 för att få exakt 1/3 av sin andel, och sedan med Deltagare #2 för att få exakt 1/3 av sin andel. Deltagare #1:s tilldelade andel av pjäsen värderas av båda deltagarna till exakt 1/6, så deltagare #1 är kvar med exakt 1/3. Detsamma gäller för tävlande #2. För tävlande #3, även om han kan betygsätta bitarna över eller under 1/6, måste summan av de två bitarna vara exakt 1/3 av hela kakan. $\mathrm {Klipp} _{2}(1/3)$ $\mathrm {Klipp} _{2}(1/3)$

Observera att det resulterande snittet inte är exakt, eftersom pjäsen utvärderas endast av ägaren till pjäsen, men inte nödvändigtvis i samma mängd av andra deltagare. Från och med 2015 var den exakta delningsproceduren för deltagarna inte känd, endast nästan exakta delningsprocedurer är kända . $n>2$ $1/n$ $n>2$

Se även

Austin -proceduren används av Brahms-Taylor-Zwicker-proceduren .
Övriga procedurer och resultat av rättvis delning och exakt delning .

Anteckningar

↑ 1 2 Austin, 1982 , sid. 212.
↑ 1 2 3 Brams och Taylor, 1996 , sid. 22–27.
↑ Robertson, Webb, 1998 , sid. 66.
↑ Robertson, Webb, 1998 , sid. 71.
↑ Brams och Taylor 1996 , sid. 43–44.

Litteratur

Austin AK Sharing a Cake // The Mathematical Gazette. - 1982. - T. 66 , nr. 437 . - doi : 10.2307/3616548 . — .
Jack Robertson, William Webb. Tårtskärningsalgoritmer: Var rättvis om du kan. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .
Steven J. Brams, Alan D. Taylor. rättvis uppdelning. - 1996. - ISBN 978-0-521-55644-6 .
- Översatt av Stephen J. Brahms, Alan D. Taylor. Vi delar rättvist eller garanterar en vinst för alla. - Moskva: SINTEG, 2002. - (Serie "Economics and Business"). - ISBN 5-89638-058-5 .

Länkar

Fischer, Daniel. Konsensusdelning av en kaka till två personer i godtyckliga förhållanden . Math.SE. Hämtad: 23 juni 2015. (obestämd)