Corte de pastel proporcional

Un reparto proporcional de la porción de la torta es una especie de reparto justo de la torta . Se trata de una división de un recurso heterogéneo ("torta") que satisface el criterio de proporcionalidad , es decir, que cada socio considere que su porción asignada vale al menos 1/ n del total.

Cuando se analiza la proporcionalidad se suelen hacer dos suposiciones:

• 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 misma es igual a la suma de sus partes.

Definiciones formales

La torta se denota por . Hay personas. Cada persona tiene una función de valor . Una partición de la torta, , se llama proporcional si: ${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle V_{i}}$ ${\displaystyle X_{1}\sqcup \cdots \sqcup X_{n}=C}$

${\displaystyle V_{i}(X_{i})\geq V_{i}(C)/n}$ para cada persona ${\displaystyle i\in \{1,\ldots ,n\}}$

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 quien corta el pastel puede, de hecho, cortarlo en dos partes iguales; el supuesto de aditividad garantiza que ambos socios valoran sus partes como al menos 1/2.

Existen muchas formas de extender este procedimiento a más de dos personas. Cada una de ellas tiene sus propias ventajas y desventajas.

Procedimientos sencillos

El último disminuidor es el procedimiento de división proporcional más antiguo desarrollado para n personas:

• A uno de los socios se le pide que saque una pieza que valore como mínimo 1/ n .
• Los demás socios a su vez tienen la opción de reclamar que la pieza actual vale en realidad más de 1/ n ; en ese caso, se les pide que la disminuyan de tal 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 resto del pastel se divide luego de la misma manera entre las n  − 1 personas restantes.

Por inducción, es posible demostrar que cada uno de los miembros de la pareja que sigue las reglas tiene garantizado un valor de 1/ n , independientemente de lo que hagan los demás miembros de la pareja. Se trata de 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 el papel; en realidad, solo se necesitan n  − 1 cortes de la tarta. Por tanto, si la tarta es contigua, es posible garantizar que cada trozo sea contiguo. ${\displaystyle n\times (n-1)/2=O(n^{2})}$

El procedimiento de cuchilla móvil de Dubins-Spanier es una versión de tiempo continuo de Last Diminisher. ^[1]

• Se pasa un cuchillo sobre el pastel, paralelo a él, de un extremo al otro.
• Un compañero dice "basta" cuando piensa que el pastel está a la izquierda del cuchillo. Luego, corta el pastel y se queda con ese trozo. ${\displaystyle 1/n}$
• Esto se repite con el resto del pastel y los compañeros. El último compañero 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 entonces elige la mitad, dejando el resto para el primer compañero.
• Cada uno de estos dos socios divide entonces 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 tres primeros socios divide su porciones en cuatro partes y el proceso continúa.

La ventaja de este protocolo es que se puede ejecutar en línea: a medida que se incorporan nuevos socios, la división existente se ajusta para acomodarlos, 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 igualitaria realizada por un solo agente. Su ventaja es que se puede generalizar para obtener un reparto equitativo y simétrico .

Véase también: ^[2]

Reducción a la mitad recursiva

Utilizando 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 uno de los participantes se le pide que dibuje una línea que divida la torta en dos partes que considere de igual valor. Los cortes deben ser sin intersecciones; 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, es decir, los socios cuya línea está dentro de esa mitad. Por ejemplo, los socios que dibujaron 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 recursivamente entre los n /2 socios que se le asignaron.

Es posible demostrar 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 otros 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, cada participante debe hacer una sola marca. Por lo tanto, el número total de marcas requeridas es O( n log n ).

Este algoritmo tiene una versión aleatoria que puede utilizarse para reducir el número de marcas; consulte algoritmo Even-Paz .

Procedimientos de selección

Un enfoque diferente al corte de la torta es dejar que cada compañero saque una cierta cantidad de pedazos dependiendo del número de compañeros, p ( n ), y darle a cada compañero uno de sus pedazos seleccionados, de modo que los pedazos no se superpongan.

Como ejemplo simple de un procedimiento de selección, supongamos que la torta es un intervalo unidimensional y que cada participante desea recibir un único intervalo contiguo. Utilice el siguiente protocolo:

1. Cada socio divide privadamente la torta en n intervalos que considera de igual valor; estos se llaman porciones candidatas .
2. El protocolo ordena los n ^2 candidatos por orden creciente de su extremo este (de oeste a este) y selecciona el intervalo con el extremo este más occidental. Este intervalo se denomina pieza final .
3. El protocolo entrega la última pieza a su propietario y elimina todos los candidatos que la intersectan. Luego, se repite el paso n.° 2 con los intervalos restantes de los n  − 1 socios restantes.

La regla de selección del paso n.° 2 garantiza que, en cada iteración, se elimine como máximo un intervalo de cada socio. Por lo tanto, después de cada iteración, la cantidad de intervalos por socio sigue siendo igual a la cantidad 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 ² ), 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 toda la colección 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 es la mejor posible. En muchos casos, todavía será posible dar a cada socio un único candidato de modo que los candidatos no se superpongan. Sin embargo, hay escenarios en los que dicha asignación será imposible.

Todavía podemos cortar un pastel usando consultas O( n ) si hacemos varios compromisos:

• En lugar de garantizar una proporcionalidad total, garantizamos una 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 única pieza contigua, le damos a cada socio una unión de una o más piezas disjuntas.

El esquema general es el siguiente: ^[5]

1. Cada socio se reparte en privado la torta en porciones de igual valor subjetivo. Estas porciones se denominan " porciones candidatas " .
2. Cada socio elige 2 d piezas candidatas de manera uniforme al azar, con reemplazo. Las candidatas se agrupan en d pares, que el socio informa al algoritmo. Estos n⋅d pares se denominan llaves de cuartos de final .
3. De cada grupo de cuartos de final, el algoritmo selecciona una única pieza: la pieza que se cruza con la menor cantidad de otras piezas candidatas. Estas n⋅d piezas se denominan piezas de semifinales .
4. Para cada pareja, el algoritmo selecciona una sola pieza; se denominan piezas finales . Las piezas finales se seleccionan de modo que cada punto de la torta esté cubierto por, como máximo, 2 piezas finales (ver a continuación). Si esto tiene éxito, continúe con el paso n.° 5. Si esto falla, comience nuevamente en el paso n.° 1.
5. Cada parte del pastel que pertenece a un solo pedazo final se le entrega al dueño de ese pedazo. Cada parte del pastel que pertenece a dos pedazos finales se divide proporcionalmente mediante cualquier algoritmo de división proporcional determinista.

El algoritmo garantiza que, con probabilidad O(1 a ² ), 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 n.° 5, cada una de las cuales toma O(1) tiempo. Por lo tanto, el tiempo total de ejecución del algoritmo es O( n ).

El principal desafío de este esquema es seleccionar las piezas finales en el paso n.° 4. Para obtener más detalles, 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 formulan a los agentes dos tipos de consultas: "Evaluar" y "Marcar".

Todo 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, todo procedimiento de división proporcional determinista o aleatorio que asigne a cada persona una pieza contigua debe utilizar Ω( n log n ) acciones. ^[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 parte que sea una unión de intervalos, e incluso si se permite que el procedimiento solo garantice una imparcialidad aproximada . La prueba se basa en limitar la complejidad para encontrar, para un solo jugador, una porción del pastel que sea rica en valor y delgada en ancho. ^[7]

Estos resultados de dureza implican que la reducción recursiva a la mitad es el algoritmo más rápido posible para lograr una proporcionalidad total con piezas contiguas, y es el algoritmo determinista más rápido posible para lograr una proporcionalidad parcial e incluso con piezas desconectadas. El único caso en el que se puede mejorar es con algoritmos aleatorios que garanticen una proporcionalidad parcial con piezas desconectadas.

Si los jugadores pueden cortar con precisión finita, entonces el límite inferior de Ω(n log n) también incluye protocolos aleatorios. ^[7]

La siguiente tabla resume los resultados conocidos: ^[5]

Variantes

Diferentes derechos

El criterio de proporcionalidad se puede generalizar 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 posee 8/13 y George 5/13. Esto conduce al criterio de proporcionalidad ponderada (WPR): existen varios pesos w _i que suman 1, y cada socio i debería recibir al menos una fracción w _i del recurso según su propia valoración. Se pueden utilizar varios algoritmos para encontrar una división WPR. El principal desafío es que el número de cortes puede ser grande, incluso cuando solo hay dos socios. Véase 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 según su propia valoración subjetiva.

Por supuesto, una división de este tipo no siempre existe: cuando todos los socios tienen exactamente las mismas funciones de valor, lo mejor que podemos hacer es dar a cada socio exactamente 1/ n . Por lo tanto, una condición necesaria para la existencia de una división superproporcional es que no todos los socios tengan la misma medida de valor.

El hecho 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 . Véase división superproporcional para 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 la torta a dividir es un territorio en disputa que se encuentra entre varios países, puede requerirse que la porción asignada a cada país sea adyacente a su ubicación actual. Una división proporcional con esta propiedad siempre existe y se puede encontrar combinando el protocolo Last Diminisher con trucos geométricos que involucran aplicaciones conformes . Véase el problema de división de tierras de Hill-Beck .

Restricciones geométricas bidimensionales

Cuando el "pastel" que se va a dividir es bidimensional, como un terreno 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 requerirse que cada pieza sea un cuadrado, un rectángulo grueso o, en general, un objeto grueso . Con tales restricciones de grosor, normalmente no existe una división proporcional, pero sí una división parcialmente proporcional que puede encontrarse 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, supongamos que un pastel contiene 500 gramos de chocolate y 500 gramos de vainilla, dividido entre dos socios, uno de los cuales quiere sólo el chocolate y el otro sólo la vainilla. Muchos protocolos de corte de pastel 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 dar todo el chocolate a un socio y toda la vainilla al otro socio, logrando un bienestar social normalizado 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 una solución solo para el caso muy especial donde 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-difícil. Cuando las funciones de utilidad no están normalizadas (es decir, permitimos que cada socio tenga un valor diferente para toda la torta), 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 más bien una propiedad del protocolo. Todos los protocolos de división proporcional son débilmente veraces en el sentido de que cada socio que actúe de acuerdo con su verdadera valoración tiene garantizado 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 perjudicarlo, él seguirá recibiendo su proporción garantizada. ^[10]

Sin embargo, la mayoría de los protocolos no son del todo veraces , ya que algunos socios pueden tener un incentivo para mentir con el fin de recibir incluso más de la parte garantizada. Esto es cierto incluso para el protocolo simple de dividir y elegir : si el que corta conoce las preferencias del que elige, puede cortar una pieza que el que elige valora como ligeramente inferior a la mitad, pero que el que corta valora como mucho más que la mitad.

Existen mecanismos veraces para lograr una división perfecta ; como 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]

1. Pídale a cada socio que informe su medida de valor completa.
2. Elija una partición aleatoria (consulte ^[11] para más detalles).
3. Si la partición aleatoria resulta ser superproporcional según las medidas de valor informadas, entonces impleméntela. De lo contrario, utilice un mecanismo veraz para proporcionar una división perfecta.

Cuando existe una división superproporcional, hay una probabilidad positiva de que se elija en el paso 2. Por lo tanto, el valor esperado de cada socio veraz es estrictamente mayor que 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, lo que será peor para todos los socios, incluido el mentiroso. (b) Si la partición elegida no es superproporcional porque solo le da al mentiroso un valor de 1/ n o menos, entonces el único efecto de mentir es hacer que el mecanismo piense que la partición es superproporcional y la implemente, lo que solo perjudica al mentiroso mismo. (c) Si la partición elegida realmente no es superproporcional porque le da al otro socio un valor de 1/ n o menos, entonces mentir no tiene ningún efecto ya que la partición no se implementará en ningún caso.

División proporcional de tareas

Cuando el recurso a dividir no es deseable (como en la división de tareas domésticas ), una división proporcional se define como una división que da a cada persona como máximo 1/ n del recurso (es decir, el signo de la 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.

Véase también

• División exacta
• División perfecta

Referencias

1. Dubins, Lester Eli ; Spanier, Edwin Henry (1961). "Cómo cortar un pastel de manera justa". The American Mathematical Monthly . 68 (1): 1–17. doi :10.2307/2311357. JSTOR  2311357.
2. Tasnadi, Attila. "Un nuevo procedimiento proporcional para el problema del corte de torta de n personas" . Consultado el 24 de septiembre de 2015 .
3. Even, 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 .
4. Este procedimiento de selección es similar al de la fecha límite más temprana (primera programación )
5. Jeff Edmonds y Kirk Pruhs (2006). "Asignaciones equilibradas de la torta". 47.º Simposio anual IEEE sobre fundamentos de la informática (FOCS'06) de 2006. págs. 623–634. doi :10.1109/focs.2006.17. ISBN 978-0-7695-2720-8.S2CID2091887  .​
6. Gerhard J. Woeginger y Jiri Sgall (2007). "Sobre la complejidad del corte de tartas". Optimización discreta . 4 (2): 213–220. doi : 10.1016/j.disopt.2006.07.003 .
7. Edmonds, Jeff (2006). "Cortar la torta no es realmente tarea fácil". 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 la torta no es realmente tarea fácil". ACM Transactions on Algorithms . 7 (4): 1–12. CiteSeerX 10.1.1.146.1536 . doi :10.1145/2000807.2000819. S2CID  2440968. 
8. Segal-Halevi, Erel; Nitzan, Shmuel; Jasidim, Avinatan; Aumann, Yonatan (2017). "Justo y limpio: corte de tartas 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.
9. 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 .
10. Steinhaus, Hugo (1948). "El problema de la división justa". Econometrica . 16 (1): 101–4. JSTOR  1914289.
11. Mossel, Elchanan; Tamuz, Omer (2010). División justa y veraz . Notas de clase en informática. Vol. 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. Número de identificación del sujeto  11732339.

• Un resumen de los procedimientos de división proporcional y de otro tipo aparece en: Austin, AK (1982). "Sharing a Cake". The Mathematical Gazette . 66 (437): 212–215. doi :10.2307/3616548. JSTOR  3616548. S2CID  158398839.