El problema del corte de torta proporcional

El problema del corte de torta proporcional es un tipo de problema de corte de torta justo . Esta es una partición de un recurso heterogéneo ("torta") que satisface el criterio de proporcionalidad , es decir, que cualquier participante cree que la porción de la torta que se le asigna no es peor que 1/ n de la evaluación total de la torta.

Cuando se habla de proporcionalidad , generalmente se hacen dos suposiciones:

Las valoraciones de los participantes no son atómicas , es decir, no hay elementos indivisibles con una valoración positiva.
Las puntuaciones de los participantes son aditivas , es decir, cuando se divide una pieza, la puntuación de la pieza es igual a la suma de sus partes.

Procedimientos

Para dos personas, el procedimiento Delhi-and-Choose es una solución clásica. Una persona divide el recurso en dos mitades, que considera iguales, y la otra elige la “mitad” que más le gusta. La suposición no atómica garantiza que el cortador puede cortar (como él piensa) en dos partes iguales. El supuesto de aditividad garantiza que las estimaciones de ambos participantes serán al menos 1/2 para sus piezas.

Hay muchas formas de extender este procedimiento a más de 2 personas. Cada uno de estos métodos tiene sus propias ventajas y desventajas.

Procedimientos simples

El último menos es el primer procedimiento de división proporcional desarrollado para n personas:

Se pide a uno de los participantes que seleccione una pieza, que evalúa como 1/ n .
Otros participantes, a su vez, tienen la oportunidad de objetar y declarar que la pieza es mayor que 1/ n . En este caso, se le pide que reduzca la pieza para que, según su estimación, la parte restante de la pieza sea 1/ n .
El último participante en reducir la pieza se la lleva.
Los participantes restantes dividen el resto del pastel de la misma manera entre las personas restantes. $n-1$

Por inducción, se puede probar que cada participante que se apega a las reglas tiene la garantía de obtener 1/ n del pastel, independientemente de las acciones de los demás participantes. Este es un procedimiento discreto que se puede realizar en rondas. En el peor de los casos, se requerirá acción: una acción para cada participante en cada ronda. Sin embargo, la mayoría de estas acciones se pueden hacer en papel. Solo se necesitan incisiones. Por lo tanto, si el pastel está conectado, entonces se puede garantizar que cada pieza estará conectada. $n\times (n-1)/2=O(n^{2})$ $n-1$

El procedimiento "Moving Knife" Dubins - Spanieres una versión continua del "Último Reductor" [1] .

El cuchillo se mueve a lo largo del toro en paralelo de un extremo al otro.
El concursante dice "stop" cuando considera que se ha alcanzado el valor a la izquierda del cuchillo . Se corta un trozo de pastel y se le da al participante que dijo. ${\tfrac{1}{n))$
Este procedimiento se repite con el resto del pastel y los demás participantes. El último participante se queda con el resto del pastel.

El protocolo Fink es un algoritmo que continúa dividiéndose en partes "iguales" lo suficientemente pequeñas.

El primer participante divide el recurso en partes que considera iguales;
El segundo participante elige la mitad, dejando el resto al primer participante;
Cada uno de estos dos participantes divide su porción en tercios;
El tercer participante elige dos de las porciones resultantes, una del primer y segundo participante;
Si hay cuatro participantes, cada uno de los tres primeros divide su parte en cuartos y el proceso continúa.

La ventaja de este protocolo es que se puede hacer en línea: cuando entran en juego nuevos socios, la división existente se adapta para ello sin tener que iniciar todo el proceso de división desde el principio. La desventaja de este algoritmo es que cada participante recibe una gran cantidad de fragmentos desconectados en lugar de un fragmento conectado.

El fraccionamiento único es un procedimiento basado en un fraccionamiento igualitario, llevado a cabo por un solo agente. La ventaja del procedimiento es que puede generalizarse paraun corte justo simétrico de la torta.

Véase también: [2] .

Bisección recursiva

Usando la estrategia divide y vencerás , la división proporcional se puede lograr en el tiempo [3] . Para simplificar, el procedimiento descrito aquí se proporciona para un número par de participantes, pero se puede adaptar fácilmente a cualquier número de participantes: $O(n\log n)$

Se pide a cada participante que dibuje una línea dividiendo el pastel en dos partes que considere equivalentes. Se requiere que los cortes no se crucen. La forma más fácil de garantizar esto es permitir solo líneas horizontales o solo líneas verticales.
El algoritmo ordena las n líneas en orden ascendente y corta el pastel en la mediana de las líneas. Por ejemplo, si hay 4 participantes que dibujan líneas en los puntos y , el algoritmo corta el pastel verticalmente en el punto . ${\ estilo de visualización x = 1, x = 3, x = 5}$ ${\ estilo de visualización x = 9}$ ${\ estilo de visualización x = 4}$
El algoritmo asigna a cada una de las dos mitades n /2 participantes: socios cuyas líneas están dentro de la mitad. Por ejemplo, los miembros que dibujaron líneas en los puntos se asignan a la mitad occidental, mientras que los miembros restantes se asignan a la mitad oriental. Cada mitad se divide recursivamente entre los n /2 participantes asignados a esa mitad. $x=1$ $x=3$

Se puede demostrar por inducción que a cualquier jugador que siga las reglas se le garantiza una pieza con un valor de al menos 1/ n , independientemente de cómo se comporten los otros jugadores.

Gracias a la estrategia divide y vencerás, el número de iteraciones será solo O(log n ), a diferencia del valor O( n ) en el procedimiento Última disminución. En cada iteración, cada participante se encarga de hacer una nota. Por lo tanto, el número total de puntos será igual a . $O(n\log n)$

El algoritmo tiene una versión aleatoria que se puede utilizar para reducir el número de ticks. Ver el artículo " Algoritmo de Paz Par ".

Procedimientos de Selección

Otro enfoque para cortar el pastel es dejar que cada participante extraiga una cierta cantidad de piezas dependiendo de la cantidad de participantes, p ( n ), y darle a cada participante una de sus piezas elegidas para que las piezas no se superpongan.

Como un ejemplo simple de un procedimiento de selección, imagine un pastel como un segmento unidimensional, y cada participante quiere obtener un segmento conectado separado. Utilizamos el siguiente protocolo:

Cada participante en privado divide el pastel en n intervalos, que él considera de igual valor, llamemos a estos pedazos candidatos .
El protocolo organiza a los candidatos en el orden de sus fronteras orientales (de oeste a este) y selecciona el segmento con el extremo oriental más occidental. Este segmento se llama la pieza final . $n^{2}$
El protocolo entrega la pieza final a su propietario y elimina todos los candidatos que se cruzan con ella. Luego se repite el paso #2 para los segmentos restantes del resto de los participantes. ${\ estilo de visualización n-1}$

La regla de selección del paso n.º 2 garantiza que, en cada iteración, se elimine como máximo un segmento de cada participante. Por lo tanto, después de cada iteración, la cantidad de segmentos por participante permanece igual a la cantidad de participantes y el proceso puede continuar hasta que todos los participantes reciban un segmento [4] .

Este protocolo requiere que cada parte responda n consultas, por lo que la complejidad de la consulta es similar al procedimiento de última disminución. $O(n^{2})$

Versiones aleatorias

Puede utilizar la aleatorización para reducir el número de solicitudes. La idea es que cada participante no reporte el conjunto completo de n candidatos, sino solo un número constante d de candidatos elegidos al azar. La complejidad de la consulta es O( n ), que obviamente será la mejor posible. En muchos casos, sigue siendo posible dar a cada participante un solo candidato que no se superponga con otros. Sin embargo, hay escenarios en los que dicha distribución no es posible.

Podemos cortar el pastel con consultas O( n ) si nos comprometemos:

En lugar de garantizar la proporcionalidad total, garantizamos la proporcionalidad parcial , es decir, cada participante recibe una cierta fracción constante f ( n ) del valor total, donde . $f(n)<{\tfrac{1}{n))$
En lugar de pasarle a cada participante una pieza conectada por separado, le pasamos la unión de una o más piezas que no se cruzan al participante.

El esquema general es el siguiente [5] :

Cada participante divide en privado el pastel en partes iguales de acuerdo con su evaluación subjetiva. Estas piezas se llamarán candidatas . $n\cdot an$
Cada participante elige 2 candidatos d uniformemente al azar con retorno. Los candidatos se agrupan en d pares, que el participante informa al algoritmo. Estas parejas se denominarán conjuntos de cuartos de final . $n\cdot d$
De cada conjunto de cuartos de final, el algoritmo selecciona una sola pieza, la que cruza la menor cantidad de otros candidatos. Estas piezas serán llamadas semifinales . $n\cdot d$
Para cada participante, el algoritmo selecciona una sola pieza, llamémosla final . Las piezas finales se seleccionan de forma que cada punto de la tarta quede cubierto por un máximo de dos piezas finales (ver más abajo). Si esto tiene éxito, vaya al paso número 5. Si falla, regrese al paso número 1.
Cada pieza del pastel que pertenece a una sola pieza final se entrega al dueño de esa pieza. Cada parte del pastel que pertenece a las dos piezas finales se divide proporcionalmente mediante cualquier algoritmo de división proporcional determinista.

El algoritmo garantiza que, con probabilidad, cada participante recibirá al menos la mitad de una de sus piezas candidatas, lo que implica (si las estimaciones son aditivas) que la estimación no será inferior a 1/2 an . Hay O( n ) fragmentos candidatos y O( n ) divisiones adicionales en el paso 5, cada una de las cuales toma O(1) tiempo. Por lo tanto, el tiempo total de ejecución del algoritmo es O( n ). ${\ estilo de visualización O (1a ^ {2})}$

El principal problema de este esquema es la selección de las piezas finales en el paso 4. Consulte el protocolo de Edmonds-Prus para obtener más detalles .

Resultados por dificultad

Los resultados sobre complejidad se formulan en términos del "modelo estándar de Robertson-Webb", es decir, se refieren a procedimientos que utilizan dos tipos de acciones: "Estimar" y "Cortar".

Cualquier procedimiento de división proporcional determinista para los participantes debe utilizar al menos n acciones, incluso si todas las funciones de puntuación son idénticas [3] . $n\geqslant 3$

Además, cualquier procedimiento de división proporcional determinista o aleatoria (probabilística) que asigne a cada participante una pieza conectada debe utilizar acciones [6] . $\Omega (n\log n)$

Además, cualquier procedimiento de división proporcional determinista debe realizar acciones, incluso si se permite que el procedimiento asigne a cada participante una pieza que es la unión de segmentos, y aunque se permita que el procedimiento garantice solo la equidad aproximada . La prueba se basa en un límite inferior de la complejidad de encontrar para los jugadores individuales un trozo de pastel de gran valor y poco ancho [7] [8] . $\Omega (n\log n)$

De estos resultados de dificultad se deduce que la bisección recursiva es el algoritmo más rápido para lograr la proporcionalidad total con piezas conectadas, y es el algoritmo determinista más rápido posible para lograr la proporcionalidad parcial incluso con piezas desconectadas. El único caso en el que se puede mejorar es en algoritmos aleatorios que garanticen proporcionalidad parcial con piezas desconectadas.

Si los jugadores solo pueden cortar con una precisión finita, el límite inferior también incluye protocolos aleatorios [7] [8] . $\Omega (n\log n)$

La siguiente tabla contiene resultados conocidos [5] :

Proporcionalidad ( total / parcial)	Piezas (conectadas/ desconectadas)	Tipo de protocolo (determinista / aleatorizado )	Consultas (exactas/ aproximadas)	Número de solicitudes
completo	mensajeros	determinista	preciso	$O(n\log n)$ [3] [6] $\Omega (n\log n)$
completo	mensajeros	determinista	aproximado	$\Omega (n\log n)$ [6]
completo	mensajeros	aleatorio	preciso	$O(n\log n)$ [3] [6] $\Omega (n\log n)$
completo	mensajeros	aleatorio	aproximado	$\Omega (n\log n)$ [6]
completo	incoherente	determinista	preciso	$O(n\log n)$ [3] [7] [8] $\Omega (n\log n)$
completo	incoherente	determinista	aproximado	$\Omega (n\log n)$ [7] [8]
completo	incoherente	aleatorio	preciso	$O(n\log n)$ [3]
completo	incoherente	aleatorio	aproximado	$\Omega (n\log n)$ [7] [8]
parcial	mensajeros	determinista	preciso	$\Omega (n\log n)$ [3] [7] [8] $\Omega (n\log n)$
parcial	mensajeros	determinista	aproximado	$\Omega (n\log n)$ [7] [8]
parcial	mensajeros	aleatorio	preciso	$\Omega (n\log n)$ [3]
parcial	mensajeros	aleatorio	aproximado	$\Omega (n\log n)$ [7] [8]
parcial	incoherente	determinista	preciso	$O(n\log n)$ [3] [7] [8] $\Omega (n\log n)$
parcial	incoherente	determinista	aproximado	$\Omega (n\log n)$ [7] [8]
parcial	incoherente	aleatorio	preciso	O( n ) [5]
parcial	incoherente	aleatorio	débilmente aproximado (independiente del error de estimación )	O( n ) [5]
parcial	incoherente	aleatorio	aproximado	$\Omega (n\log n)$ [7] [8]

Opciones

Vencimiento de varias acciones

La prueba de proporcionalidad se puede generalizar a una situación en la que las partes debidas de los participantes no son iguales. Por ejemplo, un recurso puede ser propiedad de dos accionistas, Alice posee acciones y George posee . Esto conduce a un criterio de proporcionalidad ponderada (WPR) : hay algunos pesos w i , cuya suma es 1, y cualquier participante i debe recibir al menos una parte w i del recurso de acuerdo con su propia evaluación. Se pueden usar varios algoritmos para encontrar la división WPR. El principal problema es que la cantidad de cortes puede ser grande incluso si solo hay dos participantes. Ver Corte proporcional de la torta con diferentes partes debidas . ${\tfrac {8}{13}}$ ${\tfrac {5}{13}}$

División superproporcional

Una división superproporcional es una división en la que cada participante recibe estrictamente más de 1/ n del recurso según su propia evaluación subjetiva.

Por supuesto, tal división no siempre existe: si todos los participantes tienen exactamente las mismas funciones de evaluación, lo mejor que podemos hacer es dar a todos exactamente 1/ n . Así, una condición necesaria para la existencia de una división superproporcional es la exigencia de que no todos los socios tengan la misma medida de valoración.

Sorprendentemente, si las funciones de evaluación son aditivas y no atómicas, esta condición también es suficiente. Es decir, si hay al menos dos participantes cuyas funciones de evaluación son solo ligeramente diferentes, entonces hay una división superproporcional en la que todos los participantes reciben más de 1/ n . Ver División Súper Proporcional para más detalles.

Restricciones de vecindario

Además de la restricción habitual de que todas las piezas deben estar conectadas, existen restricciones adicionales en algunos casos. En particular, cuando el pastel que se va a dividir es un territorio en disputa que se encuentra entre varios países, se puede exigir que cada pedazo dado a un país sea adyacente a la frontera actual del país. La división proporcional en este caso siempre existe y se puede encontrar combinando el protocolo Last Decrease con técnicas geométricas usando mapeos conformes . Consulte el artículo " El problema de la división de tierras de Hill-Beck ".

Restricciones geométricas 2D

Cuando un "pastel" se divide en un espacio bidimensional (un plano), como cuando se dividen terrenos o espacios publicitarios en medios impresos o electrónicos, a menudo se requiere que las piezas satisfagan algunas restricciones geométricas además de la conectividad. Por ejemplo, se puede exigir que cada pieza sea un cuadrado, un rectángulo grueso (es decir, el largo y el ancho no difieren varias veces), o una figura gruesa de forma general. En presencia de tales restricciones en las cifras, la división proporcional generalmente no existe, pero la división parcialmente proporcional generalmente existe y se puede encontrar usando algoritmos eficientes [9] .

División económicamente eficiente

Además de la proporcionalidad, muchas veces se exige que la división sea económicamente eficiente , es decir, maximizar el beneficio total (definido como la suma de las utilidades de todos los agentes).

Por ejemplo, considere un pastel que contiene 500 gramos de chocolate y 500 gramos de vainilla que comparten dos participantes, uno de los cuales solo quiere chocolate y el otro prefiere vainilla. Muchos protocolos para cortar pasteles le darán a cada agente 250 gramos de chocolate y 250 gramos de vainilla. Esta división es proporcional, ya que cada participante recibe 0.5 del valor total, por lo que el beneficio total normalizado es 1. Sin embargo, esta división será muy ineficiente, ya que podemos darle toda la parte de chocolate al primer participante y toda la parte de vainilla. al otro participante, obteniendo un beneficio total normalizado 2.

El problema de la división proporcional óptima es el problema de encontrar una partición proporcional que maximice el beneficio total entre todas las distribuciones proporcionales posibles. Actualmente, el problema tiene solución solo para tortas muy especiales cuando se trata de un segmento unidimensional y las funciones de densidad de utilidad son lineales (es decir, ). En general, el problema es NP-hard . Si las funciones de utilidad no están normalizadas (es decir, permitimos que cada participante tenga estimaciones diferentes de la importancia total del pastel), el problema es NP-difícil incluso para la aproximación con un factor [10] . $u(x)=Ax+B$ ${\ Displaystyle {\ tfrac {1} {\ sqrt {n}}}}$

División justa

La equidad no es una propiedad de la división, sino una propiedad del protocolo. Todos los protocolos de división proporcional son débilmente justos en el sentido de que se garantiza que cualquier participante que actúe de acuerdo con su verdadero valor recibirá al menos 1/ n (o 1/ an en el caso de un protocolo parcialmente proporcional) independientemente de cómo se comporten los demás participantes. Incluso si los otros miembros forman una coalición solo para dañarlo, aún obtendrá su proporción garantizada [11] .

Sin embargo, la mayoría de los protocolos no son estrictamente justos en el sentido de que algunos participantes pueden tener incentivos para mentir para obtener incluso más de lo que se les garantiza. Esto es cierto incluso para un protocolo simple de dividir y elegir: si el cortador conoce las preferencias del selector, puede cortar una pieza que el selector valora un poco menos de la mitad, pero que el cortador mismo valora mucho más. 1/2.

Existen mecanismos justos para obtener una partición perfecta . Debido a que la división perfecta es proporcional, estos mecanismos también son mecanismos de división justa proporcional.

Estos mecanismos pueden extenderse para obtener una división superproporcional , si existe [12] :

Pedimos a cada participante que proporcione una medida completa de evaluación.
Elegimos una partición aleatoria (ver el artículo de Mossel y Tamuz [12] para más detalles).
Si la partición aleatoria resulta ser superproporcional según las medidas reportadas, la realizamos. De lo contrario, utilizamos un mecanismo justo para asegurar una división perfecta.

Si existe una división superproporcional, existe una probabilidad positiva de que se obtenga en el paso 2. Por lo tanto, el valor esperado para cualquier participante honesto es estrictamente mayor que 1/ n . Para comprender que el mecanismo es equitativo, considere tres casos: (a) Si la partición elegida es realmente superproporcional, entonces el único resultado posible de mentir es engañar al mecanismo haciéndole creer que la partición no es superproporcional. Esto obligará al mecanismo a aplicar una división perfecta, lo que es peor para todos los involucrados, incluido el escudero. (b) Si la partición elegida no es superproporcional solo porque el mentiroso especifica 1/ n o menos, el único efecto de mentir es hacer que el motor piense que la partición es superproporcional y la use, lo que perjudicará solo al propio mentiroso. (c) Si la división seleccionada no es realmente superproporcional, lo que da a la otra parte un valor de 1/ no menos, entonces false no tendrá efecto, ya que la división no se utilizará en absoluto.

División proporcional de funciones

Si el recurso a compartir no es deseable (similar a una división de deberes ), una división proporcional se define como una división que le da a cada persona no más de 1/ n del recurso (es decir, el signo de desigualdad en la otra dirección).

La mayoría de los algoritmos de división proporcional se pueden adaptar para compartir tareas sin dificultad.

Véase también

División exacta . Ver también "División perfecta"

Notas

↑ Dubins y Spanier, 1961 , pág. 1–17.
↑ Tasnadi, Atila. Un nuevo procedimiento proporcional para el problema de corte de torta de n personas . puerta de la investigación. Consultado: 24 de septiembre de 2015. (indefinido)
↑ 1 2 3 4 5 6 7 8 9 Par, Paz, 1984 , p. 285.
↑ Esta sección del procedimiento es similar a la solución del polinomio codicioso )
↑ 1 2 3 4 Edmonds, Pruhs, 2006 , pág. 623–634.
↑ 1 2 3 4 5 Woeginger, 2007 , pág. 213–220.
↑ 1 2 3 4 5 6 7 8 9 10 11 Edmonds, 2006 , pág. 271–278.
↑ 1 2 3 4 5 6 7 8 9 10 11 Edmonds, 2011 , pág. 1–12.
↑ Segal-Halevi, Nitzan, Hassidim, Aumann, 2017 , pág. 1–28.
↑ Bei, Chen, Hua y otros, 2012 .
↑ Steinhaus, 1948 , pág. 101–4.
↑ 1 2 Mossel, Tamuz, 2010 , pág. 288–299.

Literatura

Una descripción general de las divisiones proporcionales y otras apareció en el artículo:
Austin AK Compartiendo un pastel // The Mathematical Gazette. - 1982. - T. 66 , núm. 437 . — S. 212–215 . -doi : 10.2307/ 3616548 . — .
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 . — .
Even S., Paz A. Una nota sobre el corte de tortas // Matemática Aplicada Discreta. - 1984. - T. 7 , núm. 3 . - doi : 10.1016/0166-218x(84)90005-2 .
Jeff Edmonds, Kirk Pruhs. Asignaciones equilibradas de Cake // 2006 47º Simposio anual de IEEE sobre fundamentos de informática (FOCS'06). - 2006. - ISBN 978-0-7695-2720-8 . -doi : 10.1109/ focs.2006.17 .
Gerhard J. Woeginger. Sobre la complejidad del corte de pasteles // Optimización discreta. - 2007. - T. 4 , núm. 2 . -doi : 10.1016/ j.disopt.2006.07.003 .
Jeff Edmonds. Cortar un pastel realmente no es pan comido // Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmos discretos - SODA '06. - 2006. - ISBN 978-0898716054 . doi : 10.1145 / 1109557.1109588 .
Jeff Edmonds. Cortar pasteles realmente no es pan comido // ACM Transactions on Algorithms. - 2011. - T. 7 , núm. 4 . -doi : 10.1145/ 2000807.2000819 .
Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, Yonatan Aumann. Justo y cuadrado: corte de pastel en dos dimensiones // Journal of Mathematical Economics. - 2017. - T. 70 . -doi : 10.1016/ j.jmateco.2017.01.007 . -arXiv : 1409.4511 . _
Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, Endong Yang. Corte de torta proporcional óptimo con piezas conectadas // Actas de la conferencia AAAI. — 2012.
Hugo Steinhaus. El problema de la división justa // Econometrica. - 1948. - T. 16 , núm. 1 . — .
Elchanan Mossel, Omer Tamuz. División Justa Veraz // . - 2010. - T. 6386. - (Apuntes de cátedra en Informática). - ISBN 978-3-642-16169-8 . -doi : 10.1007 / 978-3-642-16170-4_25 .