El procedimiento "última reducción"

El último procedimiento decreciente es el procedimiento justo de corte de torta . El procedimiento está diseñado para asignar un recurso divisible heterogéneo, como un pastel de cumpleaños, e involucra a n participantes en la división con diferentes preferencias por diferentes partes del pastel. El procedimiento permite que n personas obtengan una división proporcional , es decir, dividir el pastel entre ellos para que cada participante reciba al menos el valor total según su propia evaluación (subjetiva). Por ejemplo, si el estimado de Alice de todo el pastel es de $100 y hay 5 participantes, entonces Alice puede obtener un pedazo que ella valore en al menos $20, independientemente de lo que piensen o hagan los demás participantes. ${\tfrac{1}{n))$

Historia

Durante la Segunda Guerra Mundial, el matemático judío polaco Hugo Steinhaus , escondiéndose de los nazis, se interesó en la cuestión de cómo compartir el recurso de manera justa. Inspirado por el procedimiento Delhi-and-Choose de compartir un pastel entre dos hermanos, pidió a sus alumnos, Stefan Banach y Bronisław Knaster , que encontraran un procedimiento que pudiera funcionar para más personas y publicó su solución [1] .

Esta publicación inició una nueva rama de investigación que ahora está siendo llevada a cabo por muchos investigadores en muchas disciplinas. Ver artículo División ferial .

Descripción

A continuación se muestra la descripción del autor del protocolo de intercambio:

“Hay participantes A, B, C, .. N. El participante A corta un trozo arbitrario del pastel. El miembro B ahora tiene el derecho, pero no la obligación, de reducir la pieza cortando una pieza. Después de haber hecho esto, C tiene el derecho (pero no la obligación) de reducir la pieza ya reducida (o no reducida), y así sucesivamente al participante N. La regla obliga al último que redujo (cortado) a tomar su parte. parte. Este participante deja la división y los n − 1 participantes restantes comienzan el mismo juego con el resto del pastel. Después de que el número de participantes se reduce a dos, se aplica la clásica regla del halving.

Cada miembro tiene un método que asegura que recibe un fragmento con un valor mayor o igual a . El método es el siguiente: corte siempre la pieza actual para que el valor restante sea para usted. Hay dos opciones: usted obtiene la pieza que cortó o la otra persona obtiene una pieza más pequeña, que usted valora menos de . En el último caso, hay n − 1 participantes restantes y la estimación del pastel restante es mayor que . Por inducción, podemos probar que el valor resultante será al menos . ${\tfrac{1}{n))$ ${\tfrac{1}{n))$ ${\tfrac{1}{n))$ ${\ estilo de visualización {\ tfrac {n-1} {n}}}$ ${\tfrac{1}{n))$

Un caso degenerado de una función de preferencia general

El algoritmo se simplifica en el caso degenerado cuando todos los participantes tienen las mismas funciones de preferencia, ya que el participante que hizo el primer corte óptimo se convierte en el último en reducir. De manera equivalente, cada participante 1, 2, ..., n − 1 a su vez corta un trozo del pastel restante. Luego, en orden inverso, cada participante n , n − 1, ..., 1 elige una pieza que aún no ha sido reclamada.

Análisis

El protocolo Last Diminisher es discreto y se puede realizar en rondas. En el peor de los casos, necesitará acciones: una acción por ronda. ${\tfrac {n\times (n-1)}{2}}=O(n^{2})$

Sin embargo, la mayoría de estas acciones no son cortes reales, es decir, Alicia puede marcar la pieza deseada en el papel, y el otro participante la reduce en el mismo papel, y así sucesivamente. Solo el "último cortador" debería cortar el pastel. Por lo tanto, solo se necesitan n − 1 cortes. $O(n^{2})$

El procedimiento es muy liberal en cuanto a las incisiones. Las incisiones realizadas por los participantes pueden ser de cualquier forma. Incluso pueden ser incoherentes. Por otro lado, se pueden limitar los cortes para asegurar que las piezas tengan una forma aceptable. En particular:

Si el pastel original está conectado, entonces se puede garantizar que cada pieza esté conectada (continua).
Si el pastel original es un conjunto convexo , entonces se puede garantizar que cada pieza sea convexa.
Si el pastel original es un rectángulo , entonces se puede garantizar que cada pieza sea un rectángulo.
Si el pastel original es un triángulo , entonces se puede garantizar que cada pieza sea un triángulo.

Versión continua

Se puede ejecutar una versión de tiempo continuo del protocolo utilizando el procedimiento de cuchilla móvil de Dubins-Spanier [2] . Este fue el primer ejemplo de un procedimiento de división justa continua. El cuchillo se mueve sobre el pastel de izquierda a derecha. Cualquier participante puede decir “stop” si cree que el valor de la pieza a la izquierda del cuchillo es . Se corta el pastel y el participante que dijo “basta” recibe este trozo. Repita con el resto del pastel y los participantes. El último participante se queda con el resto del pastel. Similar al último procedimiento de reducción, este procedimiento se puede utilizar para obtener fragmentos contiguos para cada participante. ${\ estilo de visualización 1/n}$

Versión aproximada sin envidia

Si hay 3 o más participantes, la partición obtenida con el protocolo last-to-reduce no siempre está libre de envidia . Por ejemplo, supongamos que el primer jugador, Alicia, obtiene una pieza (que valora en 1/3). Luego, los otros dos, Bob y Charlie, comparten el resto equitativamente, en su opinión, pero en opinión de Alice, la parte de Bob vale 2/3, mientras que la parte de Charlie vale 0. Resulta que Alice está celosa de Bob.

Una solución simple [3] es permitir return . Es decir, el participante que ganó la pieza según el protocolo “el último que redujo” no abandona el juego, pero puede permanecer en el juego y participar en los siguientes pasos. Si vuelve a ganar, debe devolver su pieza actual al pastel. Para asegurarnos de que el protocolo termine, elegimos alguna constante y agregamos una regla de que cada participante puede regresar al juego no más de una vez. $\varepsilon$ ${\tfrac{1}{\varepsilon}}$

En la versión de retorno, cada miembro tiene un método para asegurarse de que recibe un fragmento cuyo valor es al menos tan grande como el fragmento más grande menos . El método es el siguiente: siempre corte la pieza actual para que la parte restante tenga un valor más su pieza actual. Esto asegura que el valor de su pieza crezca cada vez que gane, y cuando no gane, el valor del ganador no exceda su propio valor. Así, el nivel de envidia no supera . $\varepsilon$ $\varepsilon$ $\varepsilon$ $\varepsilon$

El tiempo de ejecución del algoritmo no excede , ya que hay como máximo pasos, y en cada paso encuestamos a los participantes. ${\tfrac {n^{2}}{\varepsilon}}$ ${\ Displaystyle {\ tfrac {n} {\ varepsilon}}}$ $norte$

La desventaja de la aproximación sin envidia es que las piezas no estarán necesariamente conectadas, ya que las piezas vuelven constantemente al pastel y se redistribuyen. Consulte Jealous Cake Cutting#Connected Pieces para conocer otras soluciones a este problema.

Mejoras

El procedimiento Last Reducer se mejoró más tarde de varias maneras. Consulte el artículo División proporcional para obtener más información .

Notas

↑ Steinhaus, 1948 , pág. 101–4.
↑ Dubins y Spanier, 1961 , pág. una.
↑ Brams y Taylor 1996 , pág. 130–131.

Literatura

Steven J. Brams, Alan D. Taylor. División justa: del corte del pastel a la resolución de disputas . - Prensa de la Universidad de Cambridge, 1996. - ISBN 0-521-55644-9 .
Lester Eli Dubins, Edwin Henry Spanier. Cómo cortar un pastel de manera justa // The American Mathematical Monthly. - 1961. - T. 68 , núm. 1 . -doi : 10.2307/ 2311357 . — .
Hugo Steinhaus. El problema de la división justa // Econometrica. - 1948. - T. 16 , núm. 1 . — .