Austinin liikkuvan veitsen menettelyt

Austinin "Moving Knife" -menettelyt ovat puolueettomia kakunjakomenetelmiä . Toimenpiteissä jaetaan jokaiselle n osallistujalle pala kakkua, jonka tämä osallistuja arvioi tarkalleen koko kakussa. Tämä eroaa suhteellisista jakomenetelmistä , jotka antavat jokaiselle osallistujalle vähintään täyden kakun, mutta voivat antaa jokaiselle osallistujalle enemmän. $1/n$ $1/n$

Jos , Austin-menetelmällä saatu leikkaus on tarkka jako , eikä siinä ole kateutta . Lisäksi on mahdollista leikata kakku mihin tahansa määrään k kappaletta, jonka kumpikin osapuoli arvioi täsmälleen arvolla 1/ k . Siksi on mahdollista jakaa kakku osallistujien kesken missä tahansa suhteessa (anna esimerkiksi 1/3 Alicelle ja 2/3 Georgelle). $n = 2$

Jos , jako ei ole tarkka eikä kateudeton, koska se arvioi vain oman palansa arvoon , mutta muiden kappaleiden arvio voi poiketa tästä arvosta. $n>2$ $1/n$

Pääasiallinen Austin-proseduurin käyttämä matemaattinen työkalu on väliarvolause [1] [2] [3] .

Kaksi jäsentä ja kakkupuolikkaat

Perusmenettelyissä osallistujat jakavat kakun niin, että molemmat osallistujat saavat tasan puolet. $n = 2$

Kahden veitsen menettely

Kuvauksen helpottamiseksi kutsutaan kahta pelaajaa Aliceksi ja Georgeksi ja oletetaan, että kakku on suorakaiteen muotoinen.

Alice asettaa yhden veitsen kakun vasemmalle puolelle ja toisen sen suuntaisesti oikealle, missä hän on leikamassa kakkua kahtia.
Alice siirtää molempia veitsiä oikealle niin, että veitsien välinen osa on aina puolet kakusta (hänen arvion mukaan veitsien välinen fyysinen etäisyys saattaa muuttua).
George sanoo "seis!", kun hän luulee, että veitsien välissä on puolikas kakku. Kuinka voimme olla varmoja, että George sanoo sanan "seis!" jossain vaiheessa? Tosiasia on, että jos Alice saavuttaa reunan oikealla veitsellä, vasemman veitsen asennon tulee olla samassa kohdassa, josta oikea veitsi alkoi. Väliarvolause sanoo, että Georgen pitäisi jossain vaiheessa tyytyä leikkaamaan kakku puoliksi.
Kolikon heittäminen määrittää kaksi vaihtoehtoa - joko George saa palan veitsien väliin ja Alice saa kaksi äärimmäistä nappulaa tai päinvastoin. Jos osallistujat ovat rehellisiä, he ovat yhtä mieltä siitä, että veitsien välinen osa on tasan 1/2, joten leikkaus on tarkka.

Yhden veitsen toimenpide

Yhdellä veitsellä voidaan saavuttaa sama vaikutus.

Alice kiertää veistä kakun päällä 180° pitäen veitsen puolikkaat samanlaisina molemmilla puolilla.
George sanoo "stop!", kun hän suostuu.

Alicen on tietysti suoritettava veitsen käännös samalla linjalla, josta hän aloitti. Jälleen väliarvolauseen mukaan täytyy olla piste, jossa George ajattelee, että kaksi puolikasta ovat yhtä suuret.

Kaksi osallistujaa ja osat yleisnäkymästä

Kuten Austin huomautti, kaksi osallistujaa voi löytää yhden kakunpalan, jonka molemmat arvot ovat täsmälleen millä tahansa kokonaisluvulla [2] . Kutsutaan yllä olevaa menettelyä seuraavasti : $1/k$ $k\geqslant 2$ $\mathrm {Leikkaus} _{2}(1/k)$

Alice tekee kakkuun yhdensuuntaiset merkit niin, että palat ovat täsmälleen yhtä suuret . $k-1$ $k$ $1/k$
Jos on pala, joka Georgen mielestä on myös yhtä suuri kuin , olemme saaneet sen pois. $1/k$
Muussa tapauksessa täytyy olla pala, jonka George arvioi pienemmäksi kuin at, ja viereinen kappale, jonka George arvioi suuremmaksi kuin . $1/k$ $1/k$
Anna Alicen asettaa kaksi veistä toisen palan kahden merkin päälle ja pyytää häntä liikuttamaan veitsiä rinnakkain pitäen veitsien väliset arvot täsmälleen samassa arvossa, kunnes veitset osuvat toisen palan merkkiin. Väliarvolauseen mukaan täytyy olla piste, jossa Georgen on hyväksyttävä, että veitsien välinen arvo on täsmälleen . $1/k$ $1/k$

Käyttämällä rekursiivisesti kahta osallistujaa he voivat jakaa koko kakun osiin, joista molemmat osallistujat arvioivat täsmälleen [2] : ${\displaystyle \mathrm {Leikkaa} _{2))$ $k$ $1/k$

Käytämme menettelyä leikkaamaan pala, jonka molemmat pelaajat arvostavat täsmälleen . $\mathrm {Leikkaus} _{2}(1/k)$ $1/k$
Nyt molemmat pelaajat arvioivat loput kakusta tarkalleen . Käytä leikkaamaan pala, jonka molemmat pelaajat arvioivat tarkalleen . ${\näyttötyyli (k-1)/k}$ $\mathrm {Leikkaus} _{2}(1/(k-1))$ $1/k$
Jatkamme, kunnes saamme kaikki palaset. $k$

Kaksi osapuolia voivat saavuttaa tarkan jaon millä tahansa järkevällä erääntyvien osuuksien suhteella hieman monimutkaisemmalla menettelyllä [4] .

Monet jäsenet

Kun toimenpide yhdistetään Fink -protokollaan , on mahdollista jakaa kakku osallistujien kesken siten, että jokainen osallistuja saa palan, jonka hän arvioi täsmälleen [1] [5] : ${\displaystyle \mathrm {Leikkaa} _{2))$ $n$ $1/n$

Osallistujat #1 ja #2 käyttävät , antaakseen kullekin tarkalleen 1/2, hänen mielestään. $\mathrm {Leikkaa} _{2}(1/2)$
Osallistuja #3 käyttää osallistujan #1 kanssa saadakseen tarkalleen 1/3 osuudestaan ja sitten osallistujan #2 kanssa saadakseen tarkalleen 1/3 osuudestaan. Osallistujan #1 jakaman osuuden kappaleesta molemmat osallistujat arvostavat tasan 1/6, joten osallistujalle #1 jää tasan 1/3. Sama koskee kilpailijaa nro 2. Kilpailijan nro 3 kohdalla, vaikka hän voi arvioida palat yli tai alle 1/6, näiden kahden palan summan on oltava täsmälleen 1/3 koko kakusta. $\mathrm {Leikkaa} _{2}(1/3)$ $\mathrm {Leikkaa} _{2}(1/3)$

Huomaa, että tuloksena oleva leikkaus ei ole tarkka, koska pala arvostetaan vain kappaleen omistajassa, mutta ei välttämättä samassa määrässä muiden osallistujien toimesta. Vuodesta 2015 lähtien tarkkaa osallistujien jakomenettelyä ei tiedetty, tunnetaan vain lähes tarkat jakomenettelyt . $n>2$ $1/n$ $n>2$

Katso myös

Austin -menettelyä käyttää Brahms-Taylor-Zwicker-menettely .
Muut reilun jaon ja tarkan jaon menettelytavat ja tulokset .

Muistiinpanot

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

Kirjallisuus

Austin AK jakaa kakun // The Mathematical Gazette. - 1982. - T. 66 , no. 437 . - doi : 10.2307/3616548 . — .
Jack Robertson, William Webb. Kakunleikkausalgoritmit: Ole reilu, jos voit. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .
Steven J. Brams, Alan D. Taylor. reilu jako. - 1996. - ISBN 978-0-521-55644-6 .
- Kääntäjä Stephen J. Brahms, Alan D. Taylor. Jaamme oikeudenmukaisesti tai takaamme voiton kaikille. - Moskova: SINTEG, 2002. - (Sarja "Economics and Business"). - ISBN 5-89638-058-5 .

Linkit

Fischer, Daniel. Konsensuskakun jako kahdelle ihmiselle mielivaltaisissa suhteissa . Math.SE. Haettu: 23.6.2015. (määrätön)