Procedimiento de Brahms-Taylor

El procedimiento de Brahms- Taylor (PBT, ing. Procedimiento de Brams-Taylor , BTP) es un procedimiento envidioso de corte de torta . El procedimiento propone un procedimiento para la división envidiosa del pastel en cualquier número positivo de jugadores [1] .

Historia

En 1988, antes del advenimiento de PBT, Saul Garfunkel argumentó que un problema resuelto teóricamente, a saber, el problema de dividir envidiosamente el pastel en n personas, estaba entre los problemas matemáticos más importantes del siglo XX [2] .

PBT fue descubierto por Stephen Brahms y Alan D. Taylor. El algoritmo se publicó en el número de enero de 1995 de American Mathematical Monthly [3] y más tarde, en 1996, en el libro del autor [4] .

Brahms y Taylor tienen una patente estadounidense conjunta desde 1999 relacionada con PBT [5] .

Descripción

PBT divide el pastel pieza por pieza. Un estado intermedio típico de PBT es el siguiente:

Un pedazo de pastel, digamos, se comparte entre todos los participantes sin generar envidia. $X$
El resto del pastel, digamos, permanece sin dividir, sin embargo $Y$
Un participante, digamos Alice, tiene una ventaja irrevocable ( IA ) sobre otro socio, digamos Bob, dado . Esto significa que no importa cómo , incluso si le damos toda la pieza a Bob, Alice no estará celosa de él. $Y$ $Y$ $Y$

Como ejemplo de cómo puede obtener una ventaja innegable, considere la primera etapa del procedimiento Selfridge-Conway :

Alicia divide el pastel en 3 partes, que ella considera iguales, que sean pedazos . $A B C$
Bob corta el trozo que cree que es el más grande (por ejemplo, el trozo ) para que sea igual al segundo trozo más grande. Denotemos la pieza cortada por , y la pieza reducida será entonces . $A$ $Y$ $A\setminus Y$
Charlie elige una pieza de , luego elige Bob (debe tomar si está disponible), la última pieza la toma Alice. $(A\setminus Y),B,C$ $(A\setminus Y)$

Realizada esta operación , se reparte sin envidia toda la tarta, a excepción de un trozo . Además, Alice tiene una ventaja innegable sobre el que tomó la pieza . Dado que Alice toma , o , y ambos son iguales , en su opinión, quienquiera que tome , puede tomar y , y esto no será la envidia de Alice. $Y$ $(A\setminus Y)$ $B$ $C$ $A$ $(A\setminus Y)$ $Y$

Si queremos estar seguros de que Alice obtendrá una ventaja innegable sobre un jugador en particular (por ejemplo, Bob), se necesita un procedimiento más complicado. Ella divide el pastel en pedazos cada vez más pequeños, siempre dándole a Alice el pedazo que ella valora más que Bob, para que la ventaja innegable permanezca. Esto puede tomar una cantidad ilimitada de tiempo, dependiendo de las estimaciones exactas de Alice y Bob.

Usando el procedimiento de ventaja innegable, el procedimiento PBT básico crea ventajas innegables para todos los pares ordenados de socios. Por ejemplo, si hay 4 socios, hay 12 pares ordenados. Para cada par (X,Y), realizamos un procedimiento que garantiza que el socio X tiene una ventaja innegable sobre el socio Y. Después de que cualquier socio tiene una ventaja sobre otros socios, podemos dar el resto a cualquier participante y, como resultado, obtener una división de todo el pastel, en el que no tendrá lugar la envidia.

Véase también

El procedimiento de Brahms-Taylor-Zwicker es un procedimiento de cuchillo móvil para 4 socios en el que se realizan un número finito de cortes.
Corte de torta celoso : procedimientos antiguos y nuevos para la misma tarea.

Notas

↑ Dividiendo el botín (enlace descendente) . Revista Discover (1 de marzo de 1995). Consultado el 2 de mayo de 2015. Archivado desde el original el 10 de marzo de 2012. (indefinido)
↑ More Equal than Others: Weighted Voting Archivado el 5 de diciembre de 2019 en Sol Garfunkel Wayback Machine . Para todos los propósitos prácticos. COMAP. 1988
↑ Brams y Taylor 1995 , pág. 9.
↑ Brams y Taylor 1996 , pág. 138–143.
↑ Steven J. Brams & Alan D. Taylor, "Método basado en computadora para la división justa de la propiedad de los bienes", patente de EE. UU. 5983205 , emitida el 9 de noviembre de 1999

Literatura

Brams SJ, Taylor AD Un protocolo de división de pasteles sin envidia // The American Mathematical Monthly. - 1995. - T. 102 . -doi : 10.2307/ 2974850 . — .
Steven J. Brams, Alan D. Taylor. División justa: del corte del pastel a la resolución de disputas . - Prensa de la Universidad de Cambridge, 1996. - ISBN 0-521-55644-9 .