Procedura Brahms-Taylor

Procedura Brahms -Taylor (PBT, ing. Procedura Brams-Taylor , BTP) este o procedură invidioasă de tăiere a prăjiturii . Procedura propune o procedură de împărțire invidioasă a tortului în orice număr pozitiv de jucători [1] .

Istorie

În 1988, înainte de apariția PBT, Saul Garfunkel a susținut că o problemă rezolvată teoretic, și anume problema împărțirii cu invidie a tortului în n persoane, era printre cele mai importante probleme de matematică ale secolului XX [2] .

PBT a fost descoperit de Stephen Brahms și Alan D. Taylor. Algoritmul a fost publicat în numărul din ianuarie 1995 al American Mathematical Monthly [3] și mai târziu, în 1996, în cartea autorului [4] .

Brahms și Taylor au deținut un brevet comun din SUA din 1999 legat de PBT [5] .

Descriere

PBT împarte tortul bucată cu bucată. O stare intermediară tipică PBT este următoarea:

O bucată de tort, să zicem, este împărțită între toți participanții fără a crea invidie. $X$
Restul tortului, sa zicem, ramane insa nedivizat $Y$
Un participant, să spunem Alice, are un Avantaj Irevocabil ( IA ) față de alt partener, să spunem Bob, dat fiind . Asta înseamnă că indiferent cum , chiar dacă îi dăm toată piesa lui Bob, Alice nu va fi geloasă pe el. $Y$ $Y$ $Y$

Ca exemplu despre cum puteți obține un avantaj incontestabil, luați în considerare prima etapă a procedurii Selfridge-Conway :

Alice împarte tortul în 3 părți, pe care le consideră egale, să fie bucăți . $A,B,C$
Bob taie piesa despre care crede că este cea mai mare (să zicem, piesa ) pentru a o face egală cu cea de-a doua cea mai mare bucată. Să notăm piesa tăiată cu , iar piesa redusă va fi atunci . $A$ $Y$ $A\setminus Y$
Charlie alege o piesă din , apoi Bob alege (trebuie să ia dacă este disponibilă), ultima piesă este luată de Alice. $(A\setminus Y),B,C$ $(A\setminus Y)$

Dupa efectuarea acestei operatii, intreaga prajitura, cu exceptia unei bucati , se imparte fara invidie. În plus, Alice are un avantaj incontestabil față de cel care a luat piesa . Deoarece Alice ia fie , fie , și ambele sunt egale , în opinia ei, oricine ia , el poate lua și , iar aceasta nu va fi invidia lui Alice. $Y$ $(A\setminus Y)$ $B$ $C$ $A$ $(A\setminus Y)$ $Y$

Dacă vrem să fim siguri că Alice va obține un avantaj incontestabil față de un anumit jucător (de exemplu, Bob), este nevoie de o procedură mai complicată. Ea împarte tortul în bucăți din ce în ce mai mici, oferindu-i mereu lui Alice piesa pe care o prețuiește mai mult decât Bob, astfel încât să rămână avantajul incontestabil. Acest lucru poate dura o perioadă nelimitată de timp, în funcție de estimările exacte ale lui Alice și Bob.

Folosind procedura de avantaj incontestabil, procedura de bază PBT creează avantaje incontestabile pentru toate perechile ordonate de parteneri. De exemplu, dacă sunt 4 parteneri, sunt 12 perechi ordonate. Pentru fiecare astfel de pereche (X,Y), efectuăm o procedură care garantează că partenerul X are un avantaj incontestabil față de partenerul Y. După ce orice partener are un avantaj față de ceilalți parteneri, putem da restul oricărui participant și, ca urmare, vom obține o împărțire a întregului tort, în care invidia nu va avea loc.

Vezi și

Procedura Brahms-Taylor-Zwicker este o procedură de cuțit în mișcare pentru 4 parteneri în care se efectuează un număr finit de tăieturi.
Tăierea de tort geloasă - proceduri vechi și noi pentru aceeași sarcină.

Note

↑ Împărțirea pradei (link descendent) . Revista Discover (1 martie 1995). Preluat la 2 mai 2015. Arhivat din original la 10 martie 2012. (nedefinit)
↑ Mai egal decât alții: vot ponderat Arhivat 5 decembrie 2019 la Sol Garfunkel Wayback Machine . Pentru toate scopurile practice. COMAP. 1988
↑ Brams și Taylor 1995 , p. 9.
↑ Brams și Taylor 1996 , p. 138–143.
↑ Steven J. Brams și Alan D. Taylor, „Metoda bazată pe computer pentru diviziunea echitabilă a proprietății bunurilor”, brevet american 5983205 , emis în 1999-11-09

Literatură

Brams SJ, Taylor AD Un protocol de divizie a prăjiturii fără invidie // The American Mathematical Monthly. - 1995. - T. 102 . - doi : 10.2307/2974850 . — .
Steven J. Brams, Alan D. Taylor. Împărțirea echitabilă: de la tăierea prăjiturii până la soluționarea disputelor . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .