Último reductor

El último procedimiento de reducción es un método para dividir un pastel de manera justa . Implica un recurso heterogéneo y divisible, como un pastel de cumpleaños, y n personas con diferentes preferencias sobre distintas partes del pastel. Permite que las n personas logren una división proporcional , es decir, que dividan el pastel entre ellas de manera que cada una reciba una porción con un valor de al menos 1/ n del valor total, según su propia valoración subjetiva. Por ejemplo, si Alice valora el pastel entero en $100 y hay 5 personas, Alice puede recibir una porción que valore en al menos $20, independientemente de lo que piensen o hagan los demás.

Durante la Segunda Guerra Mundial , el matemático polaco-judío Hugo Steinhaus , que se escondía de los nazis, se dedicó a la cuestión de cómo dividir los recursos de manera justa. Inspirado por el método de dividir y elegir para repartir un pastel entre dos hermanos, pidió a sus alumnos, Stefan Banach y Bronisław Knaster , que encontraran un método que funcionara para cualquier número de personas, y publicó su solución. ^{[ 1 ]}

Esta publicación ha dado origen a un nuevo tema de investigación que ahora estudian muchos investigadores de diferentes disciplinas; véase división justa .

Esta es la descripción del protocolo de división en palabras del autor:

Los participantes, numerados A, B, C, ..., N, comienzan con A cortando una porción arbitraria del pastel. B tiene ahora el derecho, pero no la obligación, de reducir la porción cortada. Independientemente de lo que haga, C tiene el derecho (sin obligación) de reducir aún más la porción ya reducida (o no reducida), y así sucesivamente hasta N. La regla obliga al último participante a tomar como su parte la porción que tocó en último lugar. Una vez que este participante ha sido eliminado, los n -1 restantes comienzan el mismo juego con el resto del pastel. Cuando el número de participantes se ha reducido a dos, aplican la regla clásica para dividir el resto por la mitad.

Cada participante tiene un método que le garantiza recibir una porción con un valor de al menos 1/ n . El método consiste en cortar siempre la porción actual de forma que el resto tenga un valor de 1/ n . Hay dos opciones: o bien recibes la porción que has cortado, o bien otra persona recibe una porción más pequeña, cuyo valor para ti es menor que 1/ n . En este último caso, quedan n − 1 participantes y el valor del pastel restante es mayor que ( n − 1)/ n . Por lo tanto, por inducción, es posible demostrar que el valor recibido es al menos 1/ n .

El protocolo del último reductor es discreto y se puede jugar por turnos. En el peor de los casos, se necesitan n × (n−1) / 2 = O ( n ² ) acciones: una acción por jugador por turno.

Sin embargo, la mayoría de estas O ( n² ) acciones no son cortes reales; es decir ^, Alice puede marcar la porción que desea en un papel y hacer que los demás jugadores la disminuyan en el mismo papel, etc.; solo el "último en disminuir" tiene que cortar el pastel. Por lo tanto, solo se necesitan n -1 cortes.

El procedimiento es muy flexible en cuanto a los cortes. Los cortes realizados por los socios pueden tener cualquier forma; incluso pueden estar desconectados. Por otro lado, es posible restringir los cortes para garantizar que las piezas tengan una forma armoniosa. En particular:

• Si el pastel original está unido, entonces es posible garantizar que cada pieza esté conectada (contigua).
• Si el pastel original es un conjunto convexo , entonces es posible garantizar que cada pieza sea convexa.
• Si el pastel original es rectangular , entonces es posible garantizar que cada trozo sea rectangular.
• Si el pastel original es un triángulo , entonces es posible garantizar que cada trozo sea un triángulo.

Una versión en tiempo continuo de este protocolo se puede ejecutar utilizando el procedimiento de cuchillo móvil de Dubins-Spanier . ^{[ 2 ]} Fue el primer ejemplo de un procedimiento continuo en la división justa. El cuchillo se pasa sobre el pastel desde el extremo izquierdo al derecho. Cualquier jugador puede decir alto cuando lo piense. ${\displaystyle 1/n}$Si una porción del pastel queda a la izquierda del cuchillo, se corta y el jugador que habló se queda con esa porción. Se repite el proceso con el resto del pastel y los jugadores restantes; el último jugador se queda con el resto. De forma similar al procedimiento del último reductor, se puede usar para cortar el pastel en porciones contiguas para cada jugador.

Cuando hay tres o más socios, la división obtenida mediante el protocolo del último en disminuir no siempre está libre de envidia . Por ejemplo, supongamos que la primera socia, Alice, recibe una parte (que valora como 1/3 del total). Luego, los otros dos socios, Bob y Charlie, dividen el resto de una manera que consideran justa, pero según Alice, la parte de Bob vale 2/3, mientras que la de Charlie vale 0. En ese caso, Alice envidia a Bob.

Una solución simple ^{[ 3 ]} es permitir la reentrada . Es decir, un compañero que ganó una pieza al ser el último en disminuir, no tiene que abandonar el juego, sino que puede quedarse y participar en los siguientes pasos. Si vuelve a ganar, debe soltar su pieza actual y esta se devuelve al pastel. Para asegurar que el protocolo finalice, seleccionamos una cierta constante.${\displaystyle \epsilon }$y agregar una regla que permita a cada socio volver a entrar como máximo${\displaystyle 1/\epsilon }$veces.

En la versión reentrante, cada socio tiene un método que garantiza que recibe una porción con un valor de al menos el valor más grande menos${\displaystyle \epsilon }$. El método es: siempre cortar la porción actual de tal manera que el resto tenga un valor de${\displaystyle \epsilon }$más su valor actual. Esto garantiza que su valor crezca en${\displaystyle \epsilon }$cada vez que ganas, y si no ganas, el valor del ganador es como máximo${\displaystyle \epsilon }$más que tu propio valor. Por lo tanto, el nivel de envidia es como máximo${\displaystyle \epsilon }$(una constante aditiva).

El tiempo de ejecución es como máximo${\displaystyle n^{2}/\epsilon }$, ya que hay como máximo${\displaystyle n/\epsilon }$pasos y en cada paso consultamos cada uno de los${\displaystyle n}$fogonadura.

Una desventaja de la variante aproximada sin envidia es que las piezas no están necesariamente conectadas, ya que se devuelven constantemente al pastel y se vuelven a dividir. Consulte envy-free cake-cutting#Connected pieces para ver otras soluciones a este problema.

El último procedimiento de disminución se ha mejorado posteriormente de muchas maneras. Para más detalles, véase división proporcional .