Brahms-Taylor-förfarande

Brahms- Taylor-proceduren (PBT, eng. Brams-Taylor-proceduren , BTP) är en avundsjuk kakskärningsprocedur . Proceduren föreslår en procedur för avundsjuk uppdelning av kakan i ett positivt antal spelare [1] .

Historik

1988, före tillkomsten av PBT, hävdade Saul Garfunkel att ett teoretiskt löst problem, nämligen problemet att avundsjukt dela upp kakan i n personer, var bland de viktigaste problemen inom matematiken på 1900-talet [2] .

PBT upptäcktes av Stephen Brahms och Alan D. Taylor. Algoritmen publicerades i januarinumret 1995 av American Mathematical Monthly [3] och senare, 1996, i författarens bok [4] .

Brahms och Taylor har haft ett gemensamt amerikanskt patent sedan 1999 relaterat till PBT [5] .

Beskrivning

PBT delar upp kakan bit för bit. Ett typiskt PBT-mellantillstånd är följande:

En piece of cake, säg, delas mellan alla deltagare utan att skapa avund. $X$
Resten av kakan, säg, förblir dock odelad $Y$
En deltagare, säg Alice, har en Irrevocable Advantage ( IA ) över en annan partner, säg Bob, givet . Det betyder att oavsett hur , även om vi ger hela stycket till Bob, kommer Alice inte att vara avundsjuk på honom. $Y$ $Y$ $Y$

Som ett exempel på hur du kan få en obestridlig fördel, överväg det första steget av Selfridge-Conway-proceduren :

Alice delar upp kakan i 3 delar, som hon anser vara lika, låt dem vara bitar . $A,B,C$
Bob skär av den bit han tror är den största (säg, bit ) för att göra den lika med den näst största biten. Låt oss beteckna den avskurna biten med , och den reducerade biten blir då . $A$ $Y$ $A\setminus Y$
Charlie väljer en bit från , sedan väljer Bob (han måste ta om det finns), den sista biten tas av Alice. $(A\setminus Y),B,C$ $(A\setminus Y)$

Efter att denna operation har utförts delas hela kakan, med undantag av en bit , utan avundsjuka. Dessutom har Alice en obestridlig fördel gentemot den som tog pjäsen . Eftersom Alice tar antingen , eller , och de båda är lika , enligt hennes åsikt, vem som än tar , kan han ta och , och detta kommer inte att vara Alices avundsjuka. $Y$ $(A\setminus Y)$ $B$ $C$ $A$ $(A\setminus Y)$ $Y$

Om vi vill vara säkra på att Alice kommer att få en obestridlig fördel gentemot en viss spelare (till exempel Bob), behövs en mer komplicerad procedur. Hon delar upp kakan i mindre och mindre bitar, och ger alltid Alice den bit hon värderar mer än Bob, så att den obestridliga fördelen kvarstår. Detta kan ta obegränsad tid, beroende på Alices och Bobs exakta uppskattningar.

Genom att använda proceduren för obestridliga fördelar, skapar den grundläggande PBT-proceduren obestridliga fördelar för alla beställda partnerpar. Till exempel, om det finns 4 partners, finns det 12 beställda par. För varje sådant par (X,Y) utför vi en procedur som garanterar att partner X har en obestridlig fördel gentemot partner Y. Efter att någon partner har en fördel gentemot andra partners kan vi ge resten till vilken deltagare som helst och som ett resultat av detta få en uppdelning hela kakan, i vilken avundsjuka inte kommer att ske.

Se även

Brahms-Taylor-Zwicker- proceduren är en rörlig knivprocedur för 4 partners där ett begränsat antal snitt görs.
Svartsjuk tårtskärning - gamla och nya procedurer för samma uppgift.

Anteckningar

↑ Dela bytet (nedlänk) . Discover Magazine (1 mars 1995). Hämtad 2 maj 2015. Arkiverad från originalet 10 mars 2012. (obestämd)
↑ More Equal than Others: Weighted Voting Arkiverad 5 december 2019 på Sol Garfunkel Wayback Machine . För alla praktiska ändamål. KOMAP. 1988
↑ Brams och Taylor 1995 , sid. 9.
↑ Brams och Taylor 1996 , sid. 138–143.
↑ Steven J. Brams & Alan D. Taylor, "Datorbaserad metod för rättvis uppdelning av ägande av varor", US patent 5983205 , utfärdat 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. Rättvis uppdelning: från tårtskärning till tvistlösning . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .