Procedimiento de Brams-Taylor

Procedimiento de corte de pastel sin envidia

El procedimiento de Brams-Taylor (BTP) es un procedimiento para dividir una torta sin envidias . Explicó el primer procedimiento finito para producir una división de una torta sin envidias 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, es decir, el corte de la torta sin envidia de n personas, era uno de 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 conjunta en Estados Unidos desde 1999 relacionada con el BTP. ^[5]

Descripción

El BTP divide la torta parte por parte. Un estado intermedio típico del BTP es el siguiente:

• Una parte del pastel, digamos , se divide sin envidia entre todos los socios. ${\displaystyle X}$
• El resto del pastel, digamos , permanece indiviso, pero... ${\displaystyle Y}$
• Un socio, digamos Alice, tiene una ventaja irrevocable (IA) sobre otro socio, digamos Bob, con respecto a . Esto significa que, independientemente de cómo se divida, incluso si le damos todo a Bob, Alice no envidia a Bob. ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle Y}$

Como ejemplo de cómo se puede generar una IA, considere la primera etapa del procedimiento discreto de Selfridge-Conway :

• Alicia divide el pastel en tres partes que considera iguales; llamemos a las partes . ${\displaystyle A,B,C}$
• Bob recorta el trozo que considera más grande (por ejemplo, ) para hacerlo igual al segundo más grande; llamemos a los recortes y al trozo recortado . ${\displaystyle A}$ ${\displaystyle Y}$ ${\displaystyle A\setminus Y}$
• Charlie elige una pieza de ; luego Bob elige (debe tomarla si está disponible); y por último, Alice. ${\displaystyle (A\setminus Y),B,C}$ ${\displaystyle (A\setminus Y)}$

Una vez realizada esta etapa, se reparte todo el pastel excepto , sin que haya envidia. Además, Alice ahora tiene una IA sobre quien haya tomado . ¿Por qué? Porque Alice tomó o , y ambos son iguales a en su opinión. Por lo tanto, en la opinión de Alice, quien haya tomado también puede tener - esto no la hará sentir envidia. ${\displaystyle Y}$ ${\displaystyle (A\setminus Y)}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle (A\setminus Y)}$ ${\displaystyle Y}$

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. Se divide sucesivamente la torta en porciones cada vez más pequeñas, dándole siempre a Alice una porción que ella valora más que la de Bob, de modo que se mantenga una IA. Esto puede llevar un tiempo ilimitado, dependiendo de las valoraciones exactas de Alice y Bob.

Utilizando el procedimiento IA, el procedimiento principal de BTP crea IA para todos los pares ordenados de socios. Por ejemplo, cuando hay 4 socios, hay 12 pares ordenados de socios. Para cada uno de esos pares (X, Y), ejecutamos un subprocedimiento que garantiza que el socio X tenga una IA sobre el socio Y. Después de que cada socio tenga una IA sobre todos los demás socios, podemos simplemente dar el resto a un socio arbitrario y el resultado es una división sin envidias de todo el pastel.

Véase también

• Procedimiento de Brams-Taylor-Zwicker : procedimiento de bisturí móvil para cuatro personas, que utiliza un número finito de cortes.
• Corte de pastel sin envidia : procedimientos antiguos y nuevos para el mismo problema.
• Procedimiento ganador ajustado : procedimiento diseñado por Brams y Taylor que aborda el problema similar, pero distinto, de dividir bienes entre dos agentes.

Referencias

1. "Dividiendo el botín". Revista Discover. 1 de marzo de 1995. Archivado desde el original el 10 de marzo de 2012. Consultado el 2 de mayo de 2015 .
2. Más iguales que los demás: votación ponderada Archivado el 5 de diciembre de 2019 en Wayback Machine Sol Garfunkel . Para todos los fines prácticos. COMAP. 1988
3. Brams, SJ; Taylor, AD (1995). "Un protocolo de división de tortas sin envidia". The American Mathematical Monthly . 102 (1): 9–18. doi :10.2307/2974850. JSTOR  2974850.
4. Brams, Steven J.; Taylor, Alan D. (1996). División justa: del corte de la torta a la resolución de disputas . Cambridge University Press. págs. 138-143. ISBN 0-521-55644-9.
5. Patente estadounidense 5983205, de Steven J. Brams y Alan D. Taylor, "Método basado en computadora para la división justa de la propiedad de bienes", expedida el 9 de noviembre de 1999, asignada a la Universidad de Nueva York