El procedimiento de Brams-Taylor (BTP) es un procedimiento para cortar pasteles sin envidia . Explicó el primer procedimiento finito para producir una división sin envidia de un pastel entre cualquier número entero positivo de jugadores. [1]
Historia
En 1988, antes del descubrimiento del BTP, Sol Garfunkel sostuvo que el problema resuelto por el teorema, a saber, cortar el pastel sin envidia de n personas, estaba entre los problemas más importantes de las matemáticas del siglo XX. [2]
El BTP fue descubierto por Steven Brams y Alan D. Taylor . Se publicó por primera vez en la edición de enero de 1995 de American Mathematical Monthly , [3] y más tarde en 1996 en el libro de los autores. [4]
Brams y Taylor poseen una patente estadounidense conjunta de 1999 relacionada con el BTP. [5]
Descripción
El BTP divide el pastel parte por parte. Un estado intermedio típico del BTP es el siguiente:
- Una parte del pastel, digamos , se reparte sin envidias entre todos los socios.
- El resto del pastel, di , permanece indiviso, pero -
- Un socio, digamos Alice, tiene una ventaja irrevocable (IA) sobre otro socio, digamos Bob, con respecto a. Esto significa que, independientemente de cómo está dividido, incluso si damos enteramente a Bob, Alice todavía no envidia a Bob.
Como ejemplo de cómo se puede generar una IA, considere la primera etapa del procedimiento discreto Selfridge-Conway :
- Alice divide el pastel en 3 partes que considera iguales; llamemos a las partes.
- Bob recorta la pieza que considera más grande (digamos, ) para igualarlo al segundo más grande; llamemos a las guarniciones y la pieza recortada .
- Charlie elige una pieza de ; luego Bob elige (debe tomarsi está disponible); y por último Alice.
Una vez terminada esta etapa, todo el pastel excepto se divide sin envidias. Además, Alice ahora tiene una IA sobre quienquiera que tomó. ¿Por qué? porque Alice tomó o o , y ambos son iguales a en su opinión. Entonces, en opinión de Alice, quienquiera que tomó también puede tener - esto no le dará envidia.
Si queremos asegurarnos de que Alice obtenga una IA sobre un jugador específico (por ejemplo, Bob), entonces se requiere un procedimiento mucho más complicado. Divide sucesivamente la tarta en trozos cada vez más pequeños, dándole siempre a Alice un trozo que valora más que el de Bob, para que se mantenga una IA. Esto puede llevar un tiempo ilimitado, dependiendo de las valoraciones exactas de Alice y Bob.
Usando el procedimiento IA, el procedimiento BTP principal crea IA para todos los pares ordenados de socios. Por ejemplo, cuando hay 4 socios, hay 12 pares de socios ordenados. Para cada par (X, Y), ejecutamos un subprocedimiento que garantiza que el socio X tiene un IA sobre el socio Y. Después de que cada socio tiene un IA sobre todos los demás socios, podemos simplemente darle el resto a un socio arbitrario y el resultado es una división sin envidia de todo el pastel.
Ver también
- Procedimiento de Brams-Taylor-Zwicker : un procedimiento de cuchilla móvil para 4 socios, que utiliza un número finito de cortes.
- Cortar pasteles sin envidia: procedimientos más antiguos y más nuevos para el mismo problema.
Referencias
- ^ "Dividiendo el botín" . Revista Discover. 1995-03-01. Archivado desde el original el 10 de marzo de 2012 . Consultado el 2 de mayo de 2015 .
- ^ Más igual que otros: Voto ponderado Sol Garfunkel . Para todos los propósitos prácticos. COMAP. 1988
- ^ Brams, SJ; Taylor, AD (1995). "Un protocolo de división de pasteles sin envidia". The American Mathematical Monthly . 102 : 9. doi : 10.2307 / 2974850 . JSTOR 2974850 .
- ^ Brams, Steven J .; Taylor, Alan D. (1996). División justa: del corte de la torta a la resolución de disputas . Prensa de la Universidad de Cambridge. págs. 138-143. ISBN 0-521-55644-9.
- ^ Patente estadounidense 5983205 , Steven J. Brams y Alan D. Taylor, "Método informático para la división equitativa de la propiedad de los bienes", emitida el 9 de noviembre de 1999, asignada a la Universidad de Nueva York[ enlace muerto permanente ]