Procedurile cuțitului în mișcare ale lui Austin

Procedurile lui Austin „Moving Knife” sunt proceduri imparțiale de împărțire a torturilor . Procedurile distribuie fiecăruia dintre cei n participanți câte o bucată de tort, pe care acest participant o evaluează exact în întregul tort. Acest lucru este în contrast cu procedurile de împărțire proporțională , care oferă fiecărui participant cel puțin o prăjitură plină, dar poate oferi fiecărui participant mai mult. $1/n$ $1/n$

Daca , taietura obtinuta prin procedura Austin este o impartire exacta si nu exista invidie in ea . Mai mult, este posibil să tăiați tortul în orice număr k de bucăți, pe care fiecare dintre parteneri le evaluează exact la 1/ k . Prin urmare, este posibil să împărțiți tortul între participanți în orice proporție (de exemplu, dați 1/3 lui Alice și 2/3 lui George). $n=2$

Dacă , împărțirea nu va fi nici exactă, nici lipsită de invidie, deoarece își evaluează doar propria piesă la , dar evaluarea altor piese poate diferi de această valoare. $n>2$ $1/n$

Instrumentul matematic principal folosit de procedura Austin este teorema valorii intermediare [1] [2] [3] .

Doi membri și jumătăți de tort

Procedurile de bază implică participanții să împartă tortul, astfel încât ambii participanți să primească exact jumătate. $n=2$

Procedura cu două cuțite

Pentru ușurință de descriere, să îi sunăm pe cei doi jucători Alice și George și să presupunem că tortul este dreptunghiular.

Alice pune un cuțit în stânga prăjiturii și celălalt paralel cu acesta în dreapta, unde este pe cale să taie tortul în două.
Alice mută ambele cuțite spre dreapta, astfel încât partea dintre cuțite să fie întotdeauna jumătate din tort (în opinia ei, deși distanța fizică dintre cuțite se poate modifica).
George spune „oprește-te!” când crede că este o jumătate de tort între cuțite. Cum putem fi siguri că George va spune cuvântul „stop!” la un moment dat? Cert este că, dacă Alice ajunge la margine cu cuțitul din dreapta, poziția cuțitului din stânga ar trebui să fie în același punct de la care a pornit cuțitul din dreapta. Teorema valorii intermediare afirmă că George ar trebui să fie mulțumit să taie tortul în jumătate la un moment dat.
Aruncarea unei monede determină două opțiuni - fie George primește o bucată între cuțite, iar Alice primește două piese extreme, sau invers. Dacă participanții sunt sinceri, vor fi de acord că partea dintre cuțite este exact 1/2, astfel încât tăierea va fi precisă.

Procedura cu un cuțit

Un cuțit poate fi folosit pentru a obține același efect.

Alice rotește cuțitul peste tort la 180°, menținând egale jumătățile de pe ambele părți ale cuțitului.
George spune „oprește-te!” când este de acord.

Alice trebuie, desigur, să finalizeze întoarcerea cuțitului pe aceeași linie de la care a pornit. Din nou, conform teoremei valorii intermediare, trebuie să existe un punct în care George crede că cele două jumătăți sunt egale.

Doi participanți și părți ale vederii generale

După cum a subliniat Austin, doi participanți pot găsi o bucată de tort pe care amândoi o valorează exact pentru orice număr întreg [2] . Să numim procedura de mai sus ca : $1/k$ $k\geqslant 2$ $\mathrm {Cut} _{2}(1/k)$

Alice face semne paralele pe tort, astfel încât bucățile să fie exact egale . $k-1$ $k$ $1/k$
Dacă există o bucată despre care George crede că este, de asemenea, egală cu , am terminat de extras acea bucată. $1/k$
În caz contrar, trebuie să existe o bucată pe care George o evaluează la mai puțin decât la și o bucată adiacentă pe care George o evaluează la mai mare decât . $1/k$ $1/k$
Lăsați-o pe Alice să plaseze două cuțite pe cele două semne ale uneia dintre aceste piese și puneți-o să miște cuțitele în paralel, păstrând valoarea dintre cuțite exact la până când cuțitele aterizează pe semnele celei de-a doua piese. După teorema valorii intermediare, trebuie să existe un punct în care George trebuie să fie de acord că valoarea dintre cuțite este exact . $1/k$ $1/k$

Aplicând recursiv doi participanți, aceștia pot împărți întregul tort în părți, fiecare dintre ele pe care ambii participanți le evaluează exact [2] : $\mathrm {Cut} _{2)$ $k$ $1/k$

Folosim procedura pentru a tăia o piesă pe care ambii jucători o prețuiesc exact la . $\mathrm {Cut} _{2}(1/k)$ $1/k$
Acum ambii jucători evaluează restul tortului exact la . Utilizați pentru a tăia o piesă la care ambii jucători o estimează exact . $(k-1)/k$ $\mathrm {Cut} _{2}(1/(k-1))$ $1/k$
Continuăm până obținem toate piesele. $k$

Două părți pot ajunge la o împărțire exactă cu orice raport rațional de acțiuni datorate printr-o procedură ceva mai complicată [4] .

Mulți membri

La combinarea procedurii cu protocolul Fink , este posibil să se împartă tortul între participanți, astfel încât fiecare participant să primească o bucată pe care o evaluează exact [1] [5] : $\mathrm {Cut} _{2)$ $n$ $1/n$

Participanții #1 și #2 folosesc , pentru a da fiecăruia exact 1/2, în opinia sa. $\mathrm {Cut} _{2}(1/2)$
Participantul #3 folosește cu Participantul #1 pentru a obține exact 1/3 din cota sa, iar apoi cu Participantul #2 pentru a obține exact 1/3 din cota sa. Cota de piesa alocată participantului #1 este evaluată de ambii participanți la exact 1/6, astfel încât participantul #1 rămâne cu exact 1/3. Același lucru este valabil și pentru concurentul # 2. Pentru concurentul # 3, deși el poate evalua piesele peste sau sub 1/6, suma celor două piese trebuie să fie exact 1/3 din întregul tort. $\mathrm {Cut} _{2}(1/3)$ $\mathrm {Cut} _{2}(1/3)$

Rețineți că pentru tăierea rezultată nu este exactă, deoarece piesa este evaluată doar în proprietarul piesei, dar nu neapărat în aceeași cantitate de către alți participanți. Din 2015, procedura exactă de împărțire a participanților nu era cunoscută, se cunosc doar procedurile de împărțire aproape exacte . $n>2$ $1/n$ $n>2$

Vezi și

Procedura Austin este utilizată de procedura Brahms-Taylor-Zwicker .
Alte proceduri și rezultate ale împărțirii corecte și exacte .

Note

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

Literatură

Austin AK Sharing a Cake // The Mathematical Gazette. - 1982. - T. 66 , nr. 437 . - doi : 10.2307/3616548 . — .
Jack Robertson, William Webb. Algoritmi de tăiere a prăjiturii: fiți corect dacă puteți. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .
Steven J. Brams, Alan D. Taylor. împărțire corectă. - 1996. - ISBN 978-0-521-55644-6 .
- Tradus de Stephen J. Brahms, Alan D. Taylor. Împărtășim în mod echitabil sau garantăm un câștig pentru toată lumea. - Moscova: SINTEG, 2002. - (Seria „Economie și afaceri”). - ISBN 5-89638-058-5 .

Link -uri

Fischer, Daniel. Împărțirea consensuală a unui tort la două persoane în proporții arbitrare . Matematică.SE. Preluat: 23 iunie 2015. (nedefinit)