Un corte de pastel proporcional es una especie de corte de pastel justo . Es una división de un recurso heterogéneo ("torta") que satisface el criterio de proporcionalidad , es decir, que cada socio siente que su parte asignada vale al menos 1 / n del total.
Por lo general, se hacen dos suposiciones cuando se analiza la proporcionalidad:
- Las valoraciones de los socios son no atómicas , es decir, no existen elementos indivisibles con valor positivo.
- Las valoraciones de los socios son aditivas , es decir, cuando se divide una pieza, el valor de la pieza es igual a la suma de sus partes.
Definiciones formales
El pastel se denota por . Existenpersonas. Cada persona tiene una función de valor . Una partición del pastel,, se llama proporcional si:
para cada persona .
Procedimientos
Para dos personas, dividir y elegir es la solución clásica. Una persona divide el recurso en lo que cree que son mitades iguales, y la otra persona elige la "mitad" que prefiere. El supuesto de no atomicidad garantiza que el cortador puede cortar el pastel en dos partes iguales; la suposición de aditividad garantiza que ambos socios valoren sus piezas como al menos 1/2.
Hay muchas formas de extender este procedimiento a más de 2 personas. Cada forma tiene sus propias ventajas y desventajas.
Procedimientos sencillos
El último reductor es el primer procedimiento de división proporcional desarrollado para n personas:
- A uno de los socios se le pide que dibuje una pieza que valore como al menos 1 / n .
- Los otros socios, a su vez, tienen la opción de afirmar que la pieza actual vale en realidad más de 1 / n ; en ese caso, se les pide que lo disminuyan de manera que el valor restante sea 1 / n según su propia valoración.
- El último socio en disminuir la pieza actual, la recibe.
- El pastel restante se divide de la misma manera entre las n - 1 personas restantes .
Por inducción, es posible demostrar que cada socio que sigue las reglas tiene la garantía de obtener un valor de 1 / n , independientemente de lo que hagan los demás socios. Este es un procedimiento discreto que se puede jugar por turnos. En el peor de los casos,Se necesitan acciones: una acción por jugador por turno. Sin embargo, la mayoría de estas acciones se pueden realizar en papel; en realidad, solo se necesitan n - 1 cortes del pastel. Por lo tanto, si el pastel es contiguo, es posible garantizar que cada pieza sea contigua.
El procedimiento de cuchilla móvil Dubins-Spanier es una versión en tiempo continuo de Last Diminisher. [1]
- Se pasa un cuchillo sobre el pastel, paralelo a sí mismo, de un extremo al otro.
- Un compañero dice 'detente' cuando piensa del pastel está a la izquierda del cuchillo. Luego se corta la tarta y obtienen ese trozo.
- Esto se repite con el resto de la torta y los socios. el último socio se queda con el resto del pastel.
El protocolo Fink es un algoritmo que continúa la división en porciones "iguales" sucesivamente más pequeñas.
- El primer socio divide el recurso en lo que cree que son mitades iguales.
- El segundo luego elige la mitad, dejando el resto para el primer socio.
- Cada uno de estos dos socios luego divide sus respectivas porciones en tercios.
- El tercer socio elige dos de las porciones resultantes: una del primer socio y otra del segundo socio.
- Si hay cuatro socios, cada uno de los primeros tres socios divide sus porciones en cuartos y el proceso continúa.
La ventaja de este protocolo es que se puede ejecutar en línea: a medida que nuevos socios ingresan a la fiesta, la división existente se ajusta para adaptarse a ellos, sin necesidad de reiniciar todo el proceso de división. La desventaja es que cada socio recibe una gran cantidad de piezas desconectadas en lugar de una sola pieza conectada.
El divisor solitario es un procedimiento basado en una partición igual hecha por un solo agente. Su ventaja es que se puede generalizar para producir un corte de torta justo simétrico .
Ver también: [2]
Reducción a la mitad recursiva
Usando una estrategia de divide y vencerás, es posible lograr una división proporcional en el tiempo O ( n log n ). [3] Para simplificar, el procedimiento se describe aquí para un número par de socios, pero se puede adaptar fácilmente a cualquier número de socios:
- A cada compañero se le pide que dibuje una línea que divida el pastel en dos piezas que crea que tienen el mismo valor. Se requiere que los cortes no se crucen; una forma sencilla de garantizar esto es permitir solo líneas horizontales o solo líneas verticales.
- El algoritmo ordena las n líneas en orden creciente y corta el pastel en la mediana de las líneas. Por ejemplo, si hay 4 socios que dibujan líneas en x = 1, x = 3, x = 5 y x = 9, entonces el algoritmo corta el pastel verticalmente en x = 4.
- El algoritmo asigna a cada una de las dos mitades n / 2 socios: los socios cuya línea está dentro de esa mitad. Por ejemplo, los socios que trazaron líneas en x = 1 y x = 3 se asignan a la mitad occidental y los otros dos socios se asignan a la mitad oriental. Cada mitad se divide de forma recursiva entre los n / 2 socios que se le asignan.
Es posible probar por inducción que a cada socio que juega según las reglas se le garantiza una pieza con un valor de al menos 1 / n , independientemente de lo que hagan los demás socios.
Gracias a la estrategia de divide y vencerás, el número de iteraciones es solo O (log n ), en contraste con O ( n ) en el procedimiento Last Diminisher. En cada iteración, se requiere que cada socio haga una sola marca. Por lo tanto, el número total de puntos requeridos es O ( n log n ).
Este algoritmo tiene una versión aleatoria que se puede utilizar para reducir el número de marcas; consulte el algoritmo Even-Paz .
Procedimientos de selección
Un enfoque diferente para cortar pasteles es dejar que cada socio dibuje un cierto número de piezas dependiendo del número de socios, p ( n ), y darle a cada socio una de sus piezas seleccionadas, de modo que las piezas no se superpongan.
Como ejemplo simple de un procedimiento de selección, suponga que el pastel es un intervalo unidimensional y que cada socio desea recibir un único intervalo contiguo. Utilice el siguiente protocolo:
- Cada socio divide en forma privada el pastel en n intervalos que considera de igual valor; estos se denominan piezas candidatas .
- El protocolo ordena los candidatos n ^ 2 aumentando el orden de su este (de oeste a este) y selecciona el intervalo con el extremo oriental más occidental. Este intervalo se llama pieza final .
- El protocolo entrega la pieza final a su propietario y elimina a todos los candidatos cruzados por ella. A continuación, se repite el paso 2 con los intervalos restantes de los n - 1 socios restantes .
La regla de selección en el paso n. ° 2 garantiza que, en cada iteración, se elimina como máximo un intervalo de cada socio. Por lo tanto, después de cada iteración, el número de intervalos por socios sigue siendo igual al número de socios, y el proceso puede continuar hasta que cada socio reciba un intervalo. [4]
Este protocolo requiere que cada socio responda n consultas, por lo que la complejidad de la consulta es O ( n 2 ), de manera similar a Last Diminisher.
Versiones aleatorias
Es posible utilizar la aleatorización para reducir el número de consultas. La idea es que cada socio informe, no la colección completa de n candidatos, sino solo un número constante d de candidatos, seleccionados al azar. La complejidad de la consulta es O ( n ), que obviamente es la mejor posible. En muchos casos, todavía será posible dar a cada socio un solo candidato de modo que los candidatos no se superpongan. Sin embargo, hay escenarios en los que tal asignación será imposible.
Todavía podemos cortar un pastel usando consultas O ( n ) si hacemos varios compromisos:
- En lugar de garantizar la proporcionalidad total, garantizamos la proporcionalidad parcial , es decir, cada socio recibe una cierta fracción constante f ( n ) del valor total, donde f ( n ) <1 / n .
- En lugar de darle a cada socio una sola pieza contigua, le damos a cada socio una unión de una o más piezas disjuntas.
El esquema general es el siguiente: [5]
- Los tabiques de cada socio privado la torta a una piezas de igual valor subjetivo. Estas piezas n⋅an se denominan piezas candidatas .
- Cada socio elige 2 d piezas candidatas de manera uniforme al azar, con reemplazo. Los candidatos se agrupan en d pares, que el socio informa al algoritmo. Estos n⋅d pares se denominan paréntesis de cuartos de final .
- De cada paréntesis de cuartos de final, el algoritmo selecciona una sola pieza: la pieza que se cruza con la menor cantidad de otras piezas candidatas. Estas nuevas piezas se denominan piezas semifinales .
- Para cada socio, el algoritmo selecciona una sola pieza; se llaman piezas finales . Las piezas finales se seleccionan de manera que cada punto de la torta esté cubierto por un máximo de 2 piezas finales (ver más abajo). Si tiene éxito, continúe con el paso 5. Si esto falla, comience de nuevo en el paso # 1.
- Cada parte del pastel que pertenece a una única pieza final, se entrega al propietario de esa pieza. Cada parte del pastel que pertenece a dos piezas finales, se divide proporcionalmente por cualquier algoritmo de división proporcional determinista.
El algoritmo garantiza que, con probabilidad O (1 a 2 ), cada socio recibe al menos la mitad de una de sus piezas candidatas, lo que implica (si los valores son aditivos) un valor de al menos 1/2 an . Hay O ( n ) piezas candidatas y O ( n ) divisiones adicionales en el paso # 5, cada una de las cuales toma O (1) tiempo. Por tanto, el tiempo de ejecución total del algoritmo es O ( n ).
El principal desafío en este esquema es seleccionar las piezas finales en el paso # 4. Para obtener más información, consulte el protocolo Edmonds-Pruhs .
Resultados de dureza
Los resultados de dureza se expresan en términos del modelo de consulta de Robertson-Webb , es decir, se relacionan con procedimientos que solicitan a los agentes dos tipos de consultas: "Evaluar" y "Cortar".
Cada procedimiento de división proporcional determinista para n ≥3 socios debe utilizar al menos n consultas, incluso si todas las valoraciones son idénticas. [3]
Además, cada procedimiento de división proporcional determinista o aleatoria que asigna a cada persona una pieza contigua debe usar acciones Ω ( n log n ). [6]
Además, todo procedimiento de división proporcional determinista debe utilizar consultas Ω ( n log n ), incluso si se permite que el procedimiento asigne a cada socio una pieza que sea una unión de intervalos, e incluso si se permite que el procedimiento solo garantice una equidad aproximada . La prueba se basa en limitar la complejidad para encontrar, para un solo jugador, un pedazo de pastel que sea rico en valor y delgado en ancho. [7]
Estos resultados de dureza implican que la reducción a la mitad recursiva es el algoritmo más rápido posible para lograr la proporcionalidad total con piezas contiguas, y es el algoritmo determinista más rápido posible para lograr una proporcionalidad incluso parcial e incluso con piezas desconectadas. El único caso en el que se puede mejorar es con algoritmos aleatorizados que garanticen proporcionalidad parcial con piezas desconectadas.
Si los jugadores pueden cortar con una precisión finita, entonces el límite inferior Ω (n log n) también incluye protocolos aleatorios. [7]
La siguiente tabla resume los resultados conocidos: [5]
Proporcionalidad (total / parcial) | Piezas (contiguas / disjuntas) | Tipo de protocolo (determinista / aleatorio) | Consultas (exactas / aproximadas) | #consultas |
---|---|---|---|---|
completo | contiguo | det. | exacto | O ( n log n ) [3] Ω ( n log n ) [6] |
completo | contiguo | det. | aproximado | Ω ( n log n ) [6] |
completo | contiguo | rand. | exacto | O ( n log n ) [3] Ω ( n log n ) [6] |
completo | contiguo | rand. | aproximado | Ω ( n log n ) [6] |
completo | desconectado | det. | exacto | O ( n log n ) [3] Ω ( n log n ) [7] |
completo | desconectado | det. | aproximado | Ω ( n log n ) [7] |
completo | desconectado | rand. | exacto | O ( n log n ) [3] |
completo | desconectado | rand. | aproximado | Ω ( n log n ) [7] |
parcial | contiguo | det. | exacto | O ( n log n ) [3] Ω ( n log n ) [7] |
parcial | contiguo | det. | aproximado | Ω ( n log n ) [7] |
parcial | contiguo | rand. | exacto | O ( n log n ) [3] |
parcial | contiguo | rand. | aproximado | Ω ( n log n ) [7] |
parcial | desconectado | det. | exacto | O ( n log n ) [3] Ω ( n log n ) [7] |
parcial | desconectado | det. | aproximado | Ω ( n log n ) [7] |
parcial | desconectado | rand. | exacto | O ( n ) [5] |
parcial | desconectado | rand. | débilmente aprox. (error independiente del valor) | O ( n ) [5] |
parcial | desconectado | rand. | aproximado | Ω ( n log n ) [7] |
Variantes
Diferentes derechos
El criterio de proporcionalidad puede generalizarse a situaciones en las que los derechos de los socios no son iguales. Por ejemplo, el recurso puede pertenecer a dos accionistas, de modo que Alice tiene 8/13 y George 5/13. Esto conduce al criterio de proporcionalidad ponderada (WPR): hay varios pesos w i que suman 1, y cada socio i debe recibir al menos una fracción w i del recurso por su propia valoración. Se pueden usar varios algoritmos para encontrar una división WPR. El principal desafío es que la cantidad de recortes puede ser grande, incluso cuando solo hay dos socios. Ver corte de pastel proporcional con diferentes derechos .
División superproporcional
Una división superproporcional es una división en la que cada socio recibe estrictamente más de 1 / n del recurso por su propia valoración subjetiva.
Por supuesto, tal división no siempre existe: cuando todos los socios tienen exactamente las mismas funciones de valor, lo mejor que podemos hacer es darle a cada socio exactamente 1 / n . Entonces, una condición necesaria para la existencia de una división superproporcional es que no todos los socios tengan la misma medida de valor.
Lo sorprendente es que, cuando las valoraciones son aditivas y no atómicas, esta condición también es suficiente. Es decir, cuando hay al menos dos socios cuya función de valor es incluso ligeramente diferente, entonces hay una división superproporcional en la que todos los socios reciben más de 1 / n . Consulte la división superproporcional para obtener más detalles.
Restricción de adyacencia
Además de la restricción habitual de que todas las piezas deben estar conectadas, en algunos casos existen restricciones adicionales. En particular, cuando el pastel a dividir es un territorio en disputa que se encuentra entre varios países, puede ser necesario que la pieza asignada a cada país sea adyacente a su ubicación actual. Siempre existe una división proporcional con esta propiedad y se puede encontrar combinando el protocolo Last Diminisher con trucos geométricos que involucran mapeos conformes . Véase el problema de la división de tierras de Hill-Beck .
Restricciones geométricas bidimensionales
Cuando el "pastel" a dividir es bidimensional, como una finca o un espacio publicitario 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, puede ser necesario que cada pieza sea un cuadrado, un rectángulo grueso o, en general, un objeto grueso . Con tales restricciones de grosor, generalmente no existe una división proporcional, pero generalmente existe una división parcialmente proporcional y se puede encontrar mediante algoritmos eficientes. [8]
División económicamente eficiente
Además de ser proporcional, a menudo se requiere que la división sea económicamente eficiente , es decir, maximice el bienestar social (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, dividido entre dos socios, uno de los cuales solo quiere el chocolate y el otro solo la vainilla. Muchos protocolos de corte de pasteles le darán a cada agente 250 gramos de chocolate y 250 gramos de vainilla. Esta división es proporcional porque cada socio recibe 0.5 de su valor total por lo que el bienestar social normalizado es 1. Sin embargo, esta partición es muy ineficiente porque podríamos darle todo el chocolate a un socio y toda la vainilla al otro socio, logrando un valor normalizado. bienestar social de 2.
El problema de la división proporcional óptima es el problema de encontrar una asignación proporcional que maximice el bienestar social entre todas las asignaciones proporcionales posibles. Este problema actualmente tiene solución solo para el caso muy especial en el que la torta es un intervalo unidimensional y las funciones de densidad de utilidad son lineales (es decir, u ( x ) = Ax + B ). En general, el problema es NP-hard. Cuando las funciones de utilidad no están normalizadas (es decir, permitimos que cada socio tenga un valor diferente para todo el pastel), el problema es incluso NP-difícil de aproximar dentro de un factor de 1 / √ n . [9]
División veraz
La veracidad no es una propiedad de una división, sino una propiedad del protocolo. Todos los protocolos para la división proporcional son débilmente veraces, ya que cada socio que actúa de acuerdo con su valoración real tiene la garantía de obtener al menos 1 / n (o 1 / an en el caso de un protocolo parcialmente proporcional) independientemente de lo que hagan los demás socios. Incluso si todos los demás socios forman una coalición con la única intención de dañarlo, seguirá recibiendo su proporción garantizada. [10]
Sin embargo, la mayoría de los protocolos no son muy veraces, ya que algunos socios pueden tener un incentivo para mentir para recibir incluso más que la parte garantizada. Esto es cierto incluso para el protocolo simple de dividir y elegir : si el cortador conoce las preferencias del selector, puede cortar una pieza que el selector valora como un poco menos de 1/2, pero que el cortador mismo valora mucho más que 1 / 2.
Existen mecanismos veraces para lograr una división perfecta ; dado que una división perfecta es proporcional, estos también son mecanismos veraces para la división proporcional.
Estos mecanismos se pueden ampliar para proporcionar una división superproporcional cuando existe: [11]
- Pídale a cada socio que informe toda su medida de valor.
- Elija una partición aleatoria (consulte [11] para obtener más detalles).
- Si la partición aleatoria resulta ser superproporcional de acuerdo con las medidas de valor informadas, impleméntela. De lo contrario, utilice un mecanismo veraz para proporcionar una división perfecta.
Cuando existe una división superproporcional, existe una posibilidad positiva de que se elija en el paso 2. Por lo tanto, el valor esperado de cada socio veraz es estrictamente más de 1 / n . Para ver que el mecanismo es veraz, considere tres casos: (a) Si la partición elegida es verdaderamente superproporcional, entonces el único resultado posible de mentir es engañar al mecanismo para que piense que no lo es; esto hará que el mecanismo implemente una división perfecta, que será peor para todos los socios incluido el mentiroso. (b) Si la partición recogido no es super-proporcional, ya que da sólo el mentiroso un valor de 1 / n o menos, entonces el único efecto de la mentira es hacer que el mecanismo de pensar que la partición es super-proporcional y ponerlo en práctica, que solo perjudica al mentiroso mismo. (c) Si la partición recogido es verdaderamente no super-proporcional, ya que da otro socio un valor de 1 / n o menos, luego se extiende no tiene ningún efecto en absoluto desde la partición no se llevará a cabo en cualquier caso.
División proporcional de tareas
Cuando el recurso a dividir no es deseable (como en la división de tareas ), una división proporcional se define como una división que le da a cada persona como máximo 1 / n del recurso (es decir, el signo de desigualdad se invierte).
La mayoría de los algoritmos para la división proporcional se pueden adaptar a la división de tareas de una manera sencilla.
Ver también
- División exacta
- División perfecta
Referencias
- ^ Dubins, Lester Eli ; Spanier, Edwin Henry (1961). "Cómo cortar un pastel de forma justa". The American Mathematical Monthly . 68 (1): 1-17. doi : 10.2307 / 2311357 . JSTOR 2311357 .
- ^ Tasnadi, Atila. "Un nuevo procedimiento proporcional para el problema de corte de pastel de n personas" . Consultado el 24 de septiembre de 2015 .
- ^ a b c d e f g h yo Incluso, S .; Paz, A. (1984). "Una nota sobre el corte de la torta". Matemáticas aplicadas discretas . 7 (3): 285. doi : 10.1016 / 0166-218x (84) 90005-2 .
- ^ Este procedimiento de selección es similar a la Programación de intervalos # Solución polinomial codiciosa )
- ^ a b c d Jeff Edmonds y Kirk Pruhs (2006). "Asignaciones equilibradas de pastel". 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) . págs. 623–634. doi : 10.1109 / focs.2006.17 . ISBN 978-0-7695-2720-8. S2CID 2091887 . Falta o vacío
|title=
( ayuda ) - ^ a b c d e Gerhard J. Woeginger y Jiri Sgall (2007). "Sobre la complejidad del corte de la torta". Optimización discreta . 4 (2): 213–220. doi : 10.1016 / j.disopt.2006.07.003 .
- ^ a b c d e f g h yo j k Edmonds, Jeff (2006). Cortar un pastel realmente no es pan comido . Actas del Decimoséptimo Simposio Anual ACM-SIAM sobre Algoritmos Discretos - SODA '06 . págs. 271-278. CiteSeerX 10.1.1.412.7166 . doi : 10.1145 / 1109557.1109588 . ISBN 978-0898716054., Edmonds, Jeff (2011). "Cortar un pastel realmente no es pan comido". Transacciones ACM sobre algoritmos . 7 (4): 1–12. CiteSeerX 10.1.1.146.1536 . doi : 10.1145 / 2000807.2000819 . S2CID 2440968 .
- ^ Segal-Halevi, Erel; Nitzan, Shmuel; Hassidim, Avinatan; Aumann, Yonatan (2017). "Justo y cuadrado: corte de tarta en dos dimensiones". Revista de Economía Matemática . 70 : 1–28. arXiv : 1409.4511 . doi : 10.1016 / j.jmateco.2017.01.007 . S2CID 1278209 .
- ^ Bei, Xiaohui; Chen, Ning; Hua, Xia; Tao, Biaoshuai; Yang, Endong (2012). "Corte de torta proporcional óptimo con piezas conectadas" . Actas de la conferencia AAAI . Consultado el 2 de noviembre de 2014 .
- ^ Steinhaus, Hugo (1948). "El problema de la división justa". Econometrica . 16 (1): 101–4. JSTOR 1914289 .
- ^ a b Mossel, Elchanan; Tamuz, Omer (2010). División justa veraz . Apuntes de conferencias en informática. 6386 . págs. 288-299. arXiv : 1003.5480 . Código bibliográfico : 2010LNCS.6386..288M . doi : 10.1007 / 978-3-642-16170-4_25 . ISBN 978-3-642-16169-8. S2CID 11732339 .
- Un resumen de los procedimientos de división proporcional y de otro tipo aparece en: Austin, AK (1982). "Compartiendo un pastel". La Gaceta Matemática . 66 (437): 212–215. doi : 10.2307 / 3616548 . JSTOR 3616548 .