Procedimiento de Brams-Taylor

El procedimiento de Brams-Taylor (BTP) es un procedimiento para el reparto de pasteles sin envidia . Explicó el primer procedimiento finito para producir una división de un pastel sin envidia entre cualquier número entero positivo de jugadores. ^{[ 1 ]} Sin embargo, el tiempo de ejecución del procedimiento no está limitado por ninguna función del número de jugadores, puede tomar un tiempo arbitrariamente largo (pero siempre finito), dependiendo de las funciones de valoración. En 2016, Aziz y Mackenzie descubrieron un protocolo que incluso está limitado por el número de jugadores; para más detalles, véase aquí .

En 1988, antes del descubrimiento del BTP, Sol Garfunkel sostuvo que el problema resuelto por el teorema, a saber, el corte de un pastel sin envidia para 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 el número de enero de 1995 de American Mathematical Monthly , ^{[ 3 ]} y posteriormente en 1996 en el libro de los autores. ^{[ 4 ]}

Brams y Taylor poseen una patente estadounidense conjunta de 1999 relacionada con el BTP. ^{[ 5 ]}

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

• Una parte del pastel, por ejemplo${\displaystyle X}$, se divide de forma libre de envidias entre todos los socios.
• El resto del pastel, digamos${\displaystyle Y}$, permanece indiviso, pero -
• Un socio, digamos Alice, tiene una Ventaja Irrevocable (VI) sobre otro socio, digamos Bob, con respecto a${\displaystyle Y}$Esto significa que, independientemente de cómo${\displaystyle Y}$está dividido, incluso si damos${\displaystyle Y}$Alice sigue sin envidiar a Bob.

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

• Alicia divide el pastel en 3 partes que considera iguales; llamemos a las partes${\displaystyle A,B,C}$.
• Bob recorta la pieza que considera más grande (por ejemplo,${\displaystyle A}$) para que sea igual al segundo más grande; llamemos a los recortes${\displaystyle Y}$y la pieza recortada${\displaystyle A\setminus Y}$.
• Charlie elige un trozo de entre${\displaystyle (A\setminus Y),B,C}$; entonces Bob elige (debe tomar${\displaystyle (A\setminus Y)}$si está disponible); y por último, Alice.

Una vez terminada esta etapa, todo el pastel excepto${\displaystyle Y}$está dividido de una manera libre de envidia. Además, Alice ahora tiene una IA sobre quienquiera que haya tomado${\displaystyle (A\setminus Y)}$¿Por qué? Porque Alicia tomó una u otra${\displaystyle B}$o${\displaystyle C}$y ambos son iguales a${\displaystyle A}$en su opinión. Entonces, en opinión de Alice, quienquiera que tomara${\displaystyle (A\setminus Y)}$también puede tener${\displaystyle Y}$– esto no le provocará envidia.

Si queremos asegurarnos de que Alice obtenga una ventaja de IA sobre un jugador específico (por ejemplo, Bob), se requiere un procedimiento mucho más complejo. Este divide el pastel sucesivamente en trozos cada vez más pequeños, dándole siempre a Alice un trozo que valora más que el de Bob, de modo que se mantenga la ventaja de IA. Esto podría llevar un tiempo ilimitado, dependiendo de las valoraciones exactas de Alice y Bob .

Mediante el procedimiento IA, el procedimiento principal BTP crea acuerdos de asociación (IA) para todos los pares ordenados de socios. Por ejemplo, cuando hay 4 socios, se generan 12 pares ordenados. Para cada par (X,Y), se ejecuta un subprocedimiento que garantiza que el socio X tenga un acuerdo de asociación sobre el socio Y. Una vez que cada socio tiene un acuerdo de asociación sobre todos los demás, se puede asignar el remanente a un socio cualquiera, lo que resulta en una distribución equitativa del total.

• Procedimiento de Brams-Taylor-Zwicker : un procedimiento de cuchillo móvil para 4 socios, que utiliza un número finito de cortes.
• Cortar la tarta sin envidia : procedimientos antiguos y nuevos para el mismo problema.
• Procedimiento de ganador ajustado : procedimiento diseñado por Brams y Taylor que aborda el problema similar, pero distinto, de dividir los bienes entre dos agentes.