Brahms-Taylor eljárás

A Brahms-Taylor eljárás (PBT, eng. Brams -Taylor eljárás , BTP) egy irigykedő tortavágási eljárás . Az eljárás eljárást javasol a torta irigykedő felosztására tetszőleges számú játékosra [1] .

Történelem

1988-ban, a PBT megjelenése előtt Saul Garfunkel azzal érvelt, hogy egy elméletileg megoldott probléma, nevezetesen a torta irigy n személyre osztásának problémája a 20. század matematikájának egyik legfontosabb problémája [2] .

A PBT-t Stephen Brahms és Alan D. Taylor fedezte fel. Az algoritmus az American Mathematical Monthly 1995. januári számában [3] , majd később, 1996-ban a szerző könyvében [4] jelent meg .

Brahms és Taylor 1999 óta rendelkeznek közös amerikai szabadalommal a PBT-re vonatkozóan [5] .

Leírás

A PBT darabokra osztja a tortát. Egy tipikus PBT köztes állapot a következő:

Mondjuk egy szelet tortát az összes résztvevő között osztanak szét anélkül, hogy irigységet keltene. $x$
A torta többi része azonban mondjuk osztatlan marad $Y$
Az egyik résztvevőnek, mondjuk Alice-nek, visszavonhatatlan előnye van ( IA ) egy másik partnerrel szemben, mondjuk Bobbal szemben . Ez azt jelenti, hogy hiába adjuk oda az egész darabot Bobnak, Alice nem lesz féltékeny rá. $Y$ $Y$ $Y$

Példaként arra, hogyan szerezhet vitathatatlan előnyt, tekintse meg a Selfridge-Conway eljárás első szakaszát :

Alice 3 részre osztja a tortát, amit egyenlőnek tekint, legyenek darabok . $ABC$
Bob levágja azt a darabot, amelyet a legnagyobbnak gondol (mondjuk darabot ), hogy egyenlő legyen a második legnagyobb darabbal. Jelöljük a levágott darabot -val , és a kicsinyített darab ekkor lesz . $A$ $Y$ $A\setminus Y$
Charlie kiválaszt egy darabot a -ból , majd Bob választ (el kell vennie , ha van), az utolsó darabot Alice veszi el. $(A\setminus Y),B,C$ $(A\setminus Y)$

A művelet elvégzése után az egész tortát, egy darab kivételével, irigység nélkül felosztják. Ráadásul Alice-nek tagadhatatlan előnye van azzal szemben, aki elvette a darabot . Mivel Alice vagy , vagy -t vesz , és mindketten egyenrangúak , véleménye szerint aki vesz , veheti és -t , és ez nem lesz Alice irigysége. $Y$ $(A\setminus Y)$ $B$ $C$ $A$ $(A\setminus Y)$ $Y$

Ha biztosak akarunk lenni abban, hogy Alice vitathatatlan előnyhöz jut egy adott játékossal (például Bobbal) szemben, akkor bonyolultabb eljárásra van szükség. A tortát egyre kisebb darabokra osztja, mindig azt a darabot adja Alice-nek, amelyet többre értékel, mint Bob, így a tagadhatatlan előny megmarad. Ez korlátlan ideig tarthat, Alice és Bob pontos becsléseitől függően.

A tagadhatatlan előny eljárást alkalmazva az alap PBT eljárás tagadhatatlan előnyöket teremt minden megrendelt partnerpár számára. Például ha 4 partner van, akkor 12 pár van rendezve. Minden ilyen párnál (X,Y) egy olyan eljárást hajtunk végre, amely garantálja, hogy X partnernek vitathatatlan előnye van Y partnerrel szemben. Miután bármelyik partner előnyben van a többi partnerrel szemben, a maradékot bármely résztvevőnek átadhatjuk, és ennek eredményeként kap egy osztás az egész tortát, amelyben az irigység nem kerül sor.

Lásd még

A Brahms-Taylor-Zwicker eljárás egy mozgó késes eljárás 4 partner számára, amelyben véges számú vágást végeznek.
Féltékeny tortavágás - régi és új eljárások ugyanarra a feladatra.

Jegyzetek

↑ A zsákmány felosztása (downlink) . Discover Magazine (1995. március 1.). Letöltve: 2015. május 2. Az eredetiből archiválva : 2012. március 10. (határozatlan)
↑ Másoknál egyenlőbb: Súlyozott szavazás archiválva : 2019. december 5., a Sol Garfunkel Wayback Machine -nél. Minden gyakorlati célra. COMAP. 1988
↑ Brams és Taylor 1995 , p. 9.
↑ Brams és Taylor 1996 , p. 138–143.
↑ Steven J. Brams és Alan D. Taylor, "Számítógép-alapú módszer az áruk tulajdonjogának méltányos megosztásához", 5983205 számú amerikai szabadalom , kiadva 1999.11.09.

Irodalom

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. Tisztességes felosztás: a tortavágástól a vitarendezésig . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .