Austinovy postupy pohybujícího se nože

Austinovy postupy "Moving Knife" jsou nestranné postupy dělení dortu . Postupy rozdělí každému z n účastníků kousek dortu, který tento účastník vyhodnotí přesně v celém dortu. To je na rozdíl od postupů proporcionálního dělení , které dávají každému účastníkovi alespoň plný dort, ale každému účastníkovi může dát více. $1/n$ $1/n$

Pokud je řez získaný Austinovým postupem přesným dělením a není v něm žádná závist . Navíc je možné dort nakrájet na libovolný počet k kousků, které každý z partnerů vyhodnotí přesně na 1/ k . Proto je možné rozdělit dort mezi účastníky v libovolném poměru (například dejte 1/3 Alici a 2/3 Jiřímu). $n=2$

Pokud , dělení nebude ani přesné, ani nezáviděníhodné, protože vyhodnocuje pouze vlastní dílek do , ale hodnocení ostatních dílků se může od této hodnoty lišit. $n>2$ $1/n$

Hlavním matematickým nástrojem používaným Austinovou procedurou je věta o střední hodnotě [1] [2] [3] .

Dva členové a poloviny dortu

Základní postupy spočívají v tom, že se účastníci podělí o dort tak, aby oba účastníci dostali přesně polovinu. $n=2$

Postup se dvěma noži

Pro snazší popis nazvěme oba hráče Alice a George a předpokládejme, že dort je obdélníkový.

Alice položí jeden nůž nalevo od dortu a druhý rovnoběžně s ním napravo, kde se chystá dort rozpůlit.
Alice posune oba nože doprava tak, aby část mezi noži byla vždy polovinou dortu (dle jejího odhadu, i když fyzická vzdálenost mezi noži se může změnit).
George říká „stop!“, když si myslí, že mezi noži je půlka koláče. Jak si můžeme být jisti, že George řekne slovo "stop!" v určitém okamžiku? Faktem je, že pokud Alice dosáhne ostří pravým nožem, pozice levého nože by měla být ve stejném bodě, ze kterého začal pravý nůž. Věta o střední hodnotě říká, že George by se měl v určitém okamžiku spokojit s rozkrojením koláče napůl.
Hození mincí určuje dvě možnosti – buď George dostane figurku mezi nože a Alice dva extrémní figurky, nebo naopak. Pokud jsou účastníci poctiví, dohodnou se, že část mezi noži je přesně 1/2, takže řez bude přesný.

Postup jedním nožem

K dosažení stejného efektu lze použít jeden nůž.

Alice otočí nůž nad dortem o 180°, přičemž poloviny na obou stranách nože zůstanou stejné.
George říká „stop!“, když souhlasí.

Alice musí samozřejmě dokončit otočení nože na stejné lince, ze které začala. Opět, podle teorému střední hodnoty, musí existovat bod, kdy si George myslí, že obě poloviny jsou stejné.

Dva účastníci a části celkového pohledu

Jak Austin zdůraznil, dva účastníci mohou najít jeden kus koláče, který oba mají přesně stejnou hodnotu pro jakékoli celé číslo [2] . Nazvěme výše uvedený postup jako : $1/k$ $k\geqslant 2$ $\mathrm {Vyjmout} _{2}(1/k)$

Alice dělá na dortu rovnoběžné značky, takže kousky jsou přesně stejné . $k-1$ $k$ $1/k$
Pokud existuje kus, o kterém si George myslí, že se také rovná , dokončili jsme extrahování tohoto kusu. $1/k$
V opačném případě musí existovat blok, který George vyhodnotí jako menší než at , a sousední blok, který George vyhodnotí jako větší než . $1/k$ $1/k$
Nechte Alici položit dva nože na dvě značky jednoho z těchto kusů a nechte ji pohybovat noži paralelně, přičemž udržujte hodnotu mezi noži přesně na, dokud nože nedopadnou na značky druhého kusu. Podle teorému střední hodnoty musí existovat bod, ve kterém musí George souhlasit s tím, že hodnota mezi noži je přesně . $1/k$ $1/k$

Rekurzivní aplikací dvou účastníků mohou rozdělit celý dort na části, z nichž každý vyhodnotí oba účastníci přesně [2] : ${\displaystyle \mathrm {Vyjmout} _{2))$ $k$ $1/k$

Použijeme postup k odříznutí figurky, kterou si oba hráči cení přesně na . $\mathrm {Vyjmout} _{2}(1/k)$ $1/k$
Nyní oba hráči vyhodnotí zbytek dortu přesně na . Použijte k odříznutí dílku, který oba hráči přesně odhadnou . $(k-1)/k$ $\mathrm {Vyjmout} _{2}(1/(k-1))$ $1/k$
Pokračujeme, dokud nedostaneme všechny kousky. $k$

Dvě strany mohou dospět k přesnému rozdělení s jakýmkoli racionálním poměrem splatných podílů poněkud složitějším postupem [4] .

Mnoho členů

Při kombinaci postupu s Finkovým protokolem je možné dort rozdělit mezi účastníky tak, že každý účastník dostane kousek, který ohodnotí přesně [1] [5] : ${\displaystyle \mathrm {Vyjmout} _{2))$ $n$ $1/n$

Účastníci #1 a #2 použijí , aby každému z nich dali přesně 1/2, podle jeho názoru. $\mathrm {Vyjmout} _{2}(1/2)$
Účastník č. 3 používá s Účastníkem č. 1 přesně 1/3 svého podílu a poté s Účastníkem č. 2 získává přesně 1/3 svého podílu. Přidělený podíl účastníka č. 1 na dílku je oceněn oběma účastníky přesně 1/6, takže účastníkovi č. 1 zbývá přesně 1/3. Totéž platí pro soutěžícího č. 2. Pro soutěžícího č. 3, ačkoli může hodnotit dílky nad nebo pod 1/6, součet dvou dílků musí být přesně 1/3 celého dortu. $\mathrm {Vyjmout} _{2}(1/3)$ $\mathrm {Vyjmout} _{2}(1/3)$

Všimněte si, že výsledný střih není přesný, protože figurka je hodnocena pouze vlastníkem figurky, ale ne nutně ve stejné výši ostatními účastníky. K roku 2015 nebyl přesný postup dělení pro účastníky znám, jsou známy pouze téměř přesné postupy dělení . $n>2$ $1/n$ $n>2$

Viz také

Austinova procedura je používána procedurou Brahms-Taylor-Zwicker .
Další postupy a výsledky spravedlivého dělení a exaktního dělení .

Poznámky

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

Literatura

Austin AK Sharing a Cake // The Mathematical Gazette. - 1982. - T. 66 , no. 437 . - doi : 10.2307/3616548 . — .
Jack Robertson, William Webb. Algoritmy krájení dortů: Buďte spravedliví, pokud můžete. - Natick, Massachusetts: A. K. Peters, 1998. - ISBN 978-1-56881-076-8 .
Steven J. Brams, Alan D. Taylor. spravedlivé rozdělení. - 1996. - ISBN 978-0-521-55644-6 .
- Přeložili Stephen J. Brahms, Alan D. Taylor. Sdílíme spravedlivě nebo garantujeme výhru pro každého. - Moskva: SINTEG, 2002. - (Řada "Ekonomika a podnikání"). - ISBN 5-89638-058-5 .

Odkazy

Fischer, Daniel. Konsensuální rozdělení dortu dvěma lidem v libovolných poměrech . Math.SE. Staženo: 23. června 2015. (neurčitý)

Austinovy ​​postupy pohybujícího se nože