Brahms-Taylorin menettely

Brahms -Taylor-menetelmä (PBT, eng. Brams-Taylor-menettely , BTP) on kateellinen kakun leikkaaminen . Menettelyssä ehdotetaan menettelyä kakun kateelliselle jakamiselle mihin tahansa positiiviseen pelaajien lukumäärään [1] .

Historia

Vuonna 1988, ennen PBT:n tuloa, Saul Garfunkel väitti, että teoreettisesti ratkaistu ongelma, nimittäin ongelma kakun kateellisesta jakamisesta n henkilöön, oli yksi 1900-luvun matematiikan tärkeimmistä ongelmista [2] .

PBT:n löysivät Stephen Brahms ja Alan D. Taylor. Algoritmi julkaistiin American Mathematical Monthly -lehden tammikuun 1995 numerossa [3] ja myöhemmin, vuonna 1996, kirjailijan kirjassa [4] .

Brahmsilla ja Taylorilla on ollut vuodesta 1999 lähtien yhteinen US-patentti liittyen PBT:hen [5] .

Kuvaus

PBT jakaa kakun pala palalta. Tyypillinen PBT-välitila on seuraava:

Esimerkiksi pala kakkua jaetaan kaikkien osallistujien kesken ilman kateutta. $X$
Sanotaan, että loput kakusta säilyvät jakamattomina $Y$
Yhdellä osallistujalla, esimerkiksi Alicella, on peruuttamaton etu ( IA ) verrattuna toiseen kumppaniin, esimerkiksi Bobiin . Tämä tarkoittaa, että vaikka antaisimme koko palan Bobille, Alice ei ole hänelle kateellinen. $Y$ $Y$ $Y$

Esimerkkinä siitä, kuinka voit saada kiistattoman edun, harkitse Selfridge-Conway-menettelyn ensimmäistä vaihetta :

Alice jakaa kakun 3 osaan, joita hän pitää yhtäläisinä, olkoon ne paloina . $A, B, C$
Bob leikkaa pois kappaleen, jonka hän pitää suurimmana (sanotaan, pala ), jotta se on yhtä suuri kuin toiseksi suurin pala. Merkitään leikattua kappaletta merkillä , jolloin pienennetty pala on . $A$ $Y$ $A\setminus Y$
Charlie valitsee palan joukosta , sitten Bob valitsee (hänen on otettava , jos saatavilla), viimeisen palan ottaa Alice. ${\näyttötyyli (A\setmiinus Y),B,C}$ $(A\setminus Y)$

Tämän toimenpiteen suorittamisen jälkeen koko kakku palaa lukuun ottamatta jaetaan ilman kateutta. Lisäksi Alicella on kiistaton etu teoksen ottajaan nähden . Koska Alice ottaa joko , tai , ja ne ovat molemmat samanarvoisia , hänen mielestään kuka tahansa ottaa , hän voi ottaa ja , eikä tämä ole Alicen kateutta. $Y$ $(A\setminus Y)$ $B$ $C$ $A$ $(A\setminus Y)$ $Y$

Jos haluamme olla varmoja siitä, että Alice saa kiistattoman edun tiettyyn pelaajaan (esimerkiksi Bobiin) nähden, tarvitaan monimutkaisempi menettely. Hän jakaa kakun yhä pienempiin osiin ja antaa Alicelle aina palan, jota hän arvostaa enemmän kuin Bobia, joten kiistaton etu säilyy. Tämä voi kestää rajoittamattoman ajan, riippuen Alicen ja Bobin tarkoista arvioista.

Kiistaton etumenettelyä käyttämällä perus-PBT-menettely luo kiistattomia etuja kaikille tilatuille kumppanipareille. Esimerkiksi jos kumppaneita on 4, tilattuja pareja on 12. Suoritamme kullekin tällaiselle parille (X,Y) menettelyn, joka takaa, että kumppanilla X on kiistaton etu kumppaniin Y nähden. Kun jollakin kumppanilla on etulyöntiasema muihin kumppaneihin nähden, voimme antaa loput kenelle tahansa osallistujalle ja sen seurauksena jakaa koko kakku, jossa kateutta ei tapahdu.

Katso myös

Brahms-Taylor-Zwicker- menettely on liikkuva veitsi 4 kumppanille, jossa tehdään rajallinen määrä leikkauksia.
Kateellinen kakun leikkaaminen - vanhat ja uudet menettelyt samaan tehtävään.

Muistiinpanot

↑ Saaliiden jakaminen (downlink) . Discover Magazine (1. maaliskuuta 1995). Haettu 2. toukokuuta 2015. Arkistoitu alkuperäisestä 10. maaliskuuta 2012. (määrätön)
↑ Tasa-arvoisempi kuin muut: painotettu äänestys arkistoitu 5. joulukuuta 2019 Sol Garfunkel Wayback Machinessa . Käytännössä. COMAP. 1988
↑ Brams ja Taylor 1995 , s. 9.
↑ Brams ja Taylor 1996 , s. 138-143.
↑ Steven J. Brams & Alan D. Taylor, "Tietokonepohjainen menetelmä tavaroiden omistajuuden oikeudenmukaiseen jakoon", US-patentti 5983205 , myönnetty 1999-11-09

Kirjallisuus

Brams SJ, Taylor AD An Envy-Free Cake Division Protocol // The American Mathematical Monthly. - 1995. - T. 102 . - doi : 10.2307/2974850 . — .
Steven J. Brams, Alan D. Taylor. Reilu jako: kakun leikkaamisesta riitojen ratkaisuun . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .