Austin mozgókés eljárásai

Austin "Moving Knife" eljárásai pártatlan tortaosztó eljárások . Az eljárások során mind az n résztvevőnek kiosztanak egy-egy szelet tortát, amit ez a résztvevő pontosan kiértékel az egész tortában. Ez ellentétben áll az arányos felosztási eljárásokkal , amelyek minden résztvevőnek legalább egy teljes tortát adnak, de minden résztvevőnek többet is adhatnak. $1/n$ $1/n$

Ha az austini eljárással kapott vágás pontos felosztás , és nincs benne irigység . Sőt, tetszőleges k darabra vágható a torta , amit minden partner pontosan 1/ k -ra értékel . Ezért a tortát tetszőleges arányban el lehet osztani a résztvevők között (például adjon 1/3-ot Alice-nek és 2/3-át George-nak). $n=2$

Ha , a felosztás nem lesz sem pontos, sem irigységmentes, mivel csak a saját darabját értékeli -ra , de a többi darab értékelése eltérhet ettől az értéktől. $n>2$ $1/n$

Az Austin-eljárás által használt fő matematikai eszköz a köztes érték tétel [1] [2] [3] .

Két tag és tortafelek

Az alapvető eljárások során a résztvevők megosztják a tortát úgy, hogy mindkét résztvevő pontosan a felét kapja. $n=2$

Két késes eljárás

A leírás megkönnyítése érdekében nevezzük a két játékost Alice-nek és George-nak, és feltételezzük, hogy a torta téglalap alakú.

Alice az egyik kést a torta bal oldalára helyezi, a másikat pedig vele párhuzamosan jobbra, ahol éppen ketté akarja vágni a tortát.
Alice mindkét kést jobbra mozgatja, hogy a kések közötti rész mindig a torta felét érje el (becslése szerint bár a kések közötti fizikai távolság változhat).
George azt mondja, hogy "állj!", amikor azt hiszi, hogy a kések között van egy fél torta. Hogyan lehetünk biztosak abban, hogy George kimondja a „stop!” szót! egy bizonyos ponton? A helyzet az, hogy ha Alice a jobb késsel eléri az élt, akkor a bal kés pozíciója ugyanabban a pontban legyen, ahonnan a jobb kés indult. A köztes érték tétele kimondja, hogy George-nak meg kell elégednie azzal, hogy valamikor kettévágja a tortát.
Az érme feldobása két lehetőséget határoz meg – vagy George kap egy darabot a kések közé, Alice pedig két szélső darabot, vagy fordítva. Ha a résztvevők őszinték, megegyeznek abban, hogy a kések közötti rész pontosan 1/2, így a vágás pontos lesz.

Egy késes eljárás

Egy késsel ugyanaz a hatás érhető el.

Alice 180°-kal elforgatja a kést a torta fölött, így a kés mindkét oldalán egyenlően marad.
George azt mondja „állj!”, amikor beleegyezik.

Alice-nek természetesen ugyanazon a vonalon kell befejeznie a késforgatást, ahonnan elindult. Ismét a köztes érték tétele szerint kell lennie egy pontnak, ahol George úgy gondolja, hogy a két fél egyenlő.

Két résztvevő és az általános nézet részei

Ahogy Austin rámutatott, két résztvevő találhat egy darab tortát, amelynek értéke bármelyik egész számra pontosan értéke [2] . Nevezzük a fenti eljárást így : $1/k$ $k\geqslant 2$ $\mathrm {Cut} _{2}(1/k)$

Alice párhuzamos jelöléseket tesz a tortán, hogy a darabok pontosan egyenlőek legyenek . $k-1$ $k$ $1/k$
Ha van egy darab, amelyről George úgy gondolja, hogy egyenlő a -val , akkor befejeztük a darab kivonatát. $1/k$
Ellenkező esetben kell lennie egy darabnak, amelyet George kisebbre értékel, mint at, és egy szomszédos csonknak, amelyet George nagyobbra értékel, mint . $1/k$ $1/k$
Hagyja, hogy Alice tegyen két kést az egyik darab két jelére, és mozgassa párhuzamosan a késeket, és tartsa a kések közötti értéket pontosan addig, amíg a kések a második darab jeleire nem érnek. A köztes érték tétele szerint kell lennie egy pontnak, ahol George-nak meg kell egyeznie, hogy a kések közötti érték pontosan . $1/k$ $1/k$

Két résztvevő rekurzív alkalmazásával az egész tortát részekre oszthatják, melyek mindegyikét pontosan [2] értékeli : ${\displaystyle \mathrm {Cut} _{2))$ $k$ $1/k$

Az eljárást arra használjuk, hogy levágjunk egy darabot, amelyet mindkét játékos pontosan értékes . $\mathrm {Cut} _{2}(1/k)$ $1/k$
Most mindkét játékos pontosan értékeli a torta többi részét . Használja , hogy levágjon egy darabot, amelyet mindkét játékos pontosan becsül . $(k-1)/k$ $\mathrm {Cut} _{2}(1/(k-1))$ $1/k$
Addig folytatjuk, amíg az összes darabot meg nem kapjuk. $k$

Két fél tetszőleges racionális részesedési hányaddal juthat pontos felosztásra egy kicsit bonyolultabb eljárással [4] .

Sok tag

Ha az eljárást a Fink protokollal kombináljuk , lehetőség van a torta felosztására a résztvevők között, így minden résztvevő kap egy darabot, amit pontosan [1] [5] : ${\displaystyle \mathrm {Cut} _{2))$ $n$ $1/n$

Az 1-es és a 2-es résztvevő a -t használja , hogy mindegyiküknek pontosan 1/2-et adjon, véleménye szerint. $\mathrm {Cut} _{2}(1/2)$
A 3. résztvevő az 1. Résztvevővel használja, hogy részesedésének pontosan 1/3-át, majd a 2. résztvevővel a részesedésének pontosan 1/3-át kapja meg. Mindkét résztvevő pontosan 1/6-ra értékeli az 1-es résztvevő számára kiosztott darabrészt, így az 1-es résztvevőnek pontosan 1/3-a marad. Ugyanez igaz a 2. versenyzőre is. A 3. versenyző esetében, bár a darabokat 1/6 fölé vagy alá is értékelheti, a két darab összegének pontosan az egész torta 1/3-ának kell lennie. $\mathrm {Cut} _{2}(1/3)$ $\mathrm {Cut} _{2}(1/3)$

Vegye figyelembe, hogy a kapott vágás nem pontos, mivel a darabot csak a darab tulajdonosa értékeli, de nem feltétlenül ugyanannyit a többi résztvevő. 2015-ben a résztvevők pontos felosztási menete nem volt ismert, csak szinte pontos felosztási eljárások ismertek . $n>2$ $1/n$ $n>2$

Lásd még

Az Austin eljárást a Brahms-Taylor-Zwicker eljárás használja .
A tisztességes és pontos felosztás egyéb eljárásai és eredményei .

Jegyzetek

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

Irodalom

Austin AK Sharing a Cake // The Mathematical Gazette. - 1982. - T. 66 , sz. 437 . - doi : 10.2307/3616548 . — .
Jack Robertson, William Webb. Tortavágási algoritmusok: Legyen igazságos, ha tud. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .
Steven J. Brams, Alan D. Taylor. igazságos felosztás. - 1996. - ISBN 978-0-521-55644-6 .
- Fordította: Stephen J. Brahms, Alan D. Taylor. Tisztességesen megosztunk, vagy mindenki számára garantáljuk a nyereményt. - Moszkva: SINTEG, 2002. - ("Gazdaság és üzlet" sorozat). - ISBN 5-89638-058-5 .

Linkek

Fischer, Daniel. Egy torta konszenzusos felosztása két emberre tetszőleges arányban . Math.SE. Letöltve: 2015. június 23. (határozatlan)