Último disminuidor

El último procedimiento de reductor es un procedimiento para un corte justo de pasteles . Se trata de un determinado recurso heterogéneo y divisible, como un pastel de cumpleaños, y n socios con diferentes preferencias sobre diferentes partes del pastel. Permite a las n personas lograr una división proporcional , es decir, dividir el pastel entre ellas de manera que cada persona reciba una pieza con un valor de al menos 1 / n del valor total según su propia valoración subjetiva. Por ejemplo, si Alice valora todo el pastel en $ 100 y hay 5 socios, entonces Alice puede recibir una pieza que valora como al menos $ 20, independientemente de lo que piensen o hagan los demás socios.

Historia

Durante la Segunda Guerra Mundial , el matemático polaco-judío Hugo Steinhaus , que se escondía de los nazis, se ocupó de la cuestión de cómo dividir los recursos de manera justa. Inspirado por el procedimiento Divide and Choose para dividir un pastel entre dos hermanos, pidió a sus estudiantes, Stefan Banach y Bronisław Knaster , que encontraran un procedimiento que pudiera funcionar para cualquier número de personas, y publicó su solución. ^[1]

Esta publicación ha iniciado un nuevo tema de investigación que ahora es estudiado por muchos investigadores en diferentes disciplinas; ver división justa .

Descripción

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

"Los socios que están en el rango A, B, C, .. N, A corta del pastel una parte arbitraria. B ahora tiene el derecho, pero no está obligado, a disminuir el corte cortado. Haga lo que haga, C tiene el derecho (sin obligación) de disminuir aún la rebanada ya disminuida (o no disminuida), y así sucesivamente hasta N. La regla obliga al "último disminuidor" a tomar como su parte la rebanada que fue el último en tocar. eliminado, las n -1 personas restantes comienzan el mismo juego con el resto del pastel. Una vez que el número de participantes se ha reducido a dos, aplican la regla clásica para dividir a la mitad el resto ".

Cada socio tiene un método que garantiza que recibe una rebanada con un valor de al menos 1 / n . El método es: corte siempre el corte actual de modo que el resto tenga un valor de 1 / n para usted. Hay dos opciones: o recibe la rebanada que ha cortado, o otra persona recibe una rebanada más pequeña, cuyo valor para usted es inferior a 1 / n . En el último caso, quedan n −1 socios y el valor de la torta restante es más que ( n −1) / n . Por tanto, por inducción es posible demostrar que el valor recibido es al menos 1 / n .

Caso degenerado de una función de preferencia común

El algoritmo simplifica en el caso degenerado de que todos los socios tienen la misma función de preferencia porque el socio que primero corta una rebanada de manera óptima también será su último disminuidor. De manera equivalente, ^{[ cita requerida ]} cada socio 1, 2, ..., n −1 a su vez corta una rebanada del pastel restante. Luego, en orden inverso, cada socio n , n −1, ..., 1 selecciona a su vez una porción que aún no ha sido reclamada. El primer socio que cortara una rebanada que no fuera del valor 1 / n sentiría envidia de otro socio que terminó con más de lo que hizo.

Análisis

El protocolo last-diminisher 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 acciones O ( n ² ) no son cortes reales, es decir, Alice puede marcar el corte deseado en un papel y hacer que los otros jugadores lo reduzcan en el mismo papel, etc .; sólo el "último reductor" tiene que cortar realmente el pastel. Entonces, solo se necesitan n −1 cortes.

El procedimiento es muy liberal con respecto a los recortes. los cortes realizados por los socios pueden tener cualquier forma; incluso se pueden desconectar. Por otro lado, es posible restringir los cortes para garantizar que las piezas tengan una forma agradable. En particular:

• Si el pastel original está conectado, 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 un rectángulo , entonces es posible garantizar que cada pieza sea un rectángulo.
• Si el pastel original es un triángulo , entonces es posible garantizar que cada pieza sea un triángulo.

Versión continua

Se puede ejecutar una versión de tiempo continuo de este protocolo utilizando el procedimiento de cuchilla móvil Dubins-Spanier . ^[2] Fue el primer ejemplo de un procedimiento continuo en la división justa. El cuchillo se pasa por encima del bizcocho desde el extremo izquierdo al derecho. Cualquier jugador puede decir que se detenga cuando piense que el pastel está a la izquierda del cuchillo, el pastel está cortado y el jugador que habló se queda con ese trozo. Repita con el resto del pastel y los jugadores, el último jugador se queda con el resto del pastel. Similar al último procedimiento de disminución, se puede usar para cortar el pastel en partes contiguas para cada jugador.${\displaystyle 1/n}$

Versión aproximada sin envidia

Cuando hay 3 o más socios, la división obtenida por el protocolo del último disminuidor no siempre está libre de envidia . Por ejemplo, supongamos que la primera pareja, Alice, recibe una pieza (que valora como 1/3 del total). Luego, los otros dos socios Bob y Charlie dividen el resto de tal manera que es justa en su opinión, pero en opinión de Alice, la participación de Bob vale 2/3 mientras que la participación de Charlie vale 0. Entonces Alice envidia a Bob.

Una solución simple ^[3] es permitir el reingreso . Es decir, un compañero que ganó una pieza al ser el último disminuidor, 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 se devuelve al pastel. Para asegurarnos de que el protocolo finaliza, seleccionamos una determinada constante y agregamos una regla que permite que cada socio vuelva a ingresar la mayoría de las veces.${\displaystyle \epsilon }$${\displaystyle 1/\epsilon }$

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 . El método es: corte siempre el corte actual de modo que el resto tenga un valor de más su valor actual. Esto garantiza que su valor crece cada vez que gana, y si no gana, el valor del ganador es como mucho más que su propio valor. Por lo tanto, el nivel de envidia es como máximo (una constante aditiva).${\displaystyle \epsilon }$${\displaystyle \epsilon }$${\displaystyle \epsilon }$${\displaystyle \epsilon }$${\displaystyle \epsilon }$

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

Una desventaja de la variante sin envidia aproximada es que las piezas no están necesariamente conectadas, ya que las piezas se devuelven constantemente al pastel y se vuelven a dividir. Vea Cortar pasteles sin envidia # Piezas conectadas para otras soluciones a este problema.

Mejoras

El último procedimiento de disminución se ha mejorado posteriormente de muchas maneras. Para obtener más información, consulte la división proporcional .

Referencias

1. Steinhaus, Hugo (1948). "El problema de la división justa". Econometrica . 16 (1): 101–4. JSTOR  1914289 .
2. Dubins, Lester Eli ; Spanier, Edwin Henry (1961). "Cómo cortar un pastel de forma justa". The American Mathematical Monthly . 68 : 1. doi : 10.2307 / 2311357 . JSTOR 2311357 . 
3. Brams, Steven J .; Taylor, Alan D. (1996). División justa: desde el corte de pasteles hasta la resolución de disputas . Prensa de la Universidad de Cambridge. págs. 130-131. ISBN 0-521-55644-9.