Brahms-Taylor procedure

Brahms- Taylor procedure (PBT, eng. Brams-Taylor procedure , BTP) er en misundelig kageskæringsprocedure . Proceduren foreslår en procedure for den misundelige opdeling af kagen i et hvilket som helst positivt antal spillere [1] .

Historie

I 1988, før fremkomsten af PBT, argumenterede Saul Garfunkel for, at et teoretisk løst problem, nemlig problemet med misundeligt at opdele kagen i n personer, var blandt de vigtigste problemer i matematikken i det 20. århundrede [2] .

PBT blev opdaget af Stephen Brahms og Alan D. Taylor. Algoritmen blev offentliggjort i januar 1995 - udgaven af American Mathematical Monthly [3] og senere, i 1996, i forfatterens bog [4] .

Brahms og Taylor har haft et fælles amerikansk patent siden 1999 relateret til PBT [5] .

Beskrivelse

PBT deler kagen stykke for stykke. En typisk PBT-mellemtilstand er som følger:

Et stykke kage, f.eks., deles blandt alle deltagere uden at skabe misundelse. $x$
Resten af kagen forbliver dog udelt $Y$
En deltager, f.eks. Alice, har en Irrevocable Advantage ( IA ) i forhold til en anden partner, f.eks. Bob, givet . Det betyder, at uanset hvordan , selvom vi giver hele stykket til Bob, vil Alice ikke være jaloux på ham. $Y$ $Y$ $Y$

Som et eksempel på, hvordan du kan få en ubestridelig fordel, kan du overveje den første fase af Selfridge-Conway-proceduren :

Alice deler kagen i 3 dele, som hun anser for lige store, lad dem være stykker . $A,B,C$
Bob skærer det stykke af, han synes er det største (f.eks. stykke ), for at gøre det lig med det næststørste stykke. Lad os betegne det afskårne stykke med , og det reducerede stykke bliver så . $EN$ $Y$ $A\setminus Y$
Charlie vælger en brik fra , så vælger Bob (han skal tage , hvis den er tilgængelig), den sidste brik bliver taget af Alice. $(A\setminus Y),B,C$ $(A\setminus Y)$

Efter denne operation er udført, deles hele kagen, med undtagelse af et stykke , uden misundelse. Derudover har Alice en ubestridelig fordel i forhold til den, der tog stykket . Da Alice tager enten , eller , og de begge er lige , efter hendes mening, hvem der tager , kan han tage og , og dette vil ikke være Alices misundelse. $Y$ $(A\setminus Y)$ $B$ $C$ $EN$ $(A\setminus Y)$ $Y$

Hvis vi vil være sikre på, at Alice vil få en ubestridelig fordel i forhold til en bestemt spiller (for eksempel Bob), er en mere kompliceret procedure nødvendig. Hun deler kagen op i mindre og mindre stykker, og giver altid Alice det stykke, hun værdsætter mere end Bob, så den ubestridelige fordel forbliver. Dette kan tage ubegrænset tid, afhængigt af Alices og Bobs nøjagtige skøn.

Ved at bruge proceduren med ubestridelige fordele skaber den grundlæggende PBT-procedure ubestridelige fordele for alle bestilte partnerpar. For eksempel, hvis der er 4 partnere, er der 12 bestilte par. For hvert sådant par (X,Y) udfører vi en procedure, der garanterer, at partner X har en ubestridelig fordel i forhold til partner Y. Når enhver partner har en fordel i forhold til andre partnere, kan vi give resten til enhver deltager, og som et resultat heraf få en deling hele kagen, hvori misundelse ikke vil finde sted.

Se også

Brahms-Taylor-Zwicker- proceduren er en bevægelig kniv-procedure for 4 partnere, hvor der foretages et begrænset antal snit.
Jaloux kageskæring - gamle og nye procedurer til samme opgave.

Noter

↑ Opdeling af byttet (downlink) . Discover Magazine (1. marts 1995). Hentet 2. maj 2015. Arkiveret fra originalen 10. marts 2012. (ubestemt)
↑ More Equal than Others: Weighted Voting Arkiveret 5. december 2019 på Sol Garfunkel Wayback Machine . Til alle praktiske formål. KOMAP. 1988
↑ Brams og Taylor 1995 , s. 9.
↑ Brams og Taylor 1996 , s. 138-143.
↑ Steven J. Brams & Alan D. Taylor, "Computer-baseret metode til retfærdig deling af ejerskab af varer", US patent 5983205 , udstedt 1999-11-09

Litteratur

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. Fair opdeling: fra kageskæring til konfliktløsning . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .