Corte de pastel proporcional

El reparto proporcional de un pastel es una forma justa de reparto . Se trata de una división de un recurso heterogéneo ("pastel") que cumple el criterio de proporcionalidad , es decir, que cada socio sienta que su parte asignada vale al menos 1/ n del total.

Al hablar de división proporcional, normalmente se hacen dos suposiciones:

Las valoraciones de los socios no son atómicas , es decir, no hay elementos indivisibles con valor positivo.
Las valoraciones de los socios son aditivas , es decir, cuando se divide una parte, el valor de la parte es igual a la suma de sus partes.

Definiciones formales

El pastel se denota por $C$ . Hay $n$ personas. Cada persona $i$ tiene una función de valor $V_{i}$ . Una partición del pastel, $X_{1}\sqcup \cdots \sqcup X_{n}=C$ Se denomina proporcional si:

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

Procedimientos

Para dos personas, la solución clásica es dividir y elegir . Una persona divide el recurso en lo que considera mitades iguales, y la otra elige la mitad que prefiere. El supuesto de no atomicidad garantiza que quien corta el pastel pueda, efectivamente, dividirlo en dos partes iguales; el supuesto de aditividad garantiza que ambos socios valoren sus partes como al menos la mitad.

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

Procedimientos sencillos

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

Se le pide a uno de los socios que dibuje una pieza cuyo valor sea al menos 1/ n .
Los demás socios, a su vez, tienen la opción de alegar que la pieza actual vale en realidad más de 1/ n ; en ese caso, se les pide que la reduzcan de tal manera que el valor restante sea 1/ n según su propia valoración.
El último socio que disminuya 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 garantizado 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, $n\times (n-1)/2=O(n^{2})$ Se requieren acciones: una acción por jugador por turno. Sin embargo, la mayoría de estas acciones se pueden realizar en papel; solo se necesitan n − 1 cortes del pastel. Por lo tanto, es posible que todas las piezas sean contiguas bajo ciertas circunstancias.

El procedimiento de cuchilla móvil es una versión en tiempo continuo del Último Reductor. ^{[ 1 ]}

Se pasa un cuchillo por encima del pastel, perpendicular a la dirección del movimiento, desde el extremo izquierdo hacia el extremo derecho.
Cualquier persona dice "alto" cuando piensa $1/n$ de la tarta está a la izquierda del cuchillo. (La llamada detiene el cuchillo en lo que quien llama considera justo, y cualquier demora en llamar permitiría al otro tomar lo que para entonces ya sería demasiado). Luego se corta la tarta y se les queda esa porción.
Esto se repite con el pastel y los socios restantes. 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 considera mitades iguales.
El segundo elige entonces la mitad, dejando el resto para el primer compañero.
Luego, cada uno de estos dos socios divide su porción respectiva en tercios.
El tercer socio elige dos de las porciones resultantes: una del primer socio y otra del segundo.
Si hay cuatro socios, cada uno de los tres primeros divide su porción en cuatro partes iguales, y el proceso continúa.

La ventaja de este protocolo es que puede ejecutarse en línea: a medida que nuevos socios se incorporan al partido, la división existente se ajusta para dar cabida a ellos, sin necesidad de reiniciar todo el proceso de división. La desventaja es que cada socio recibe un gran número de piezas desconectadas en lugar de una sola pieza conectada.

El divisor solitario es un procedimiento basado en una partición equitativa realizada por un solo agente. Su ventaja es que puede generalizarse para producir un reparto equitativo y simétrico .

Reducción a la mitad recursiva

Utilizando una estrategia de divide y vencerás, es posible lograr una división proporcional en un tiempo O( n log n ). ^[²^] Para simplificar, el procedimiento se describe aquí para un número par de socios, pero puede adaptarse fácilmente a cualquier número de socios:

A cada participante se le pide que dibuje una línea que divida el pastel en dos porciones que considere de igual valor. Los cortes deben ser distintos; una forma sencilla de garantizarlo 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 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: aquellos cuyas líneas se encuentran 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 recursivamente entre los n /2 socios que se le asignaron.

Es posible demostrar por inducción que a cada compañero 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 compañeros.

Gracias a la estrategia de divide y elige, el número de iteraciones es solo O(log n ), en contraste con O( n ) en el procedimiento del último reductor. 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 se puede utilizar para reducir el número de marcas; véase el algoritmo Even-Paz .

Procedimientos de selección

Otro enfoque para cortar el pastel es dejar que cada participante saque una cierta cantidad de piezas dependiendo del número de participantes, p ( n ), y darle a cada participante una de las piezas que ha seleccionado, de manera que las piezas no se superpongan.

Como ejemplo sencillo de un procedimiento de selección, supongamos que el pastel es un intervalo unidimensional y que cada socio desea recibir un único intervalo contiguo. Utilice el siguiente protocolo:

Cada socio divide el pastel en privado en n intervalos que considera de igual valor; estos se denominan porciones candidatas .
El protocolo ordena los n ^2 candidatos en orden creciente de su extremo este (de oeste a este) y selecciona el intervalo con el extremo este más occidental. Este intervalo se llama pieza final .
El protocolo entrega la pieza final a su propietario y elimina todos los candidatos que se cruzan con ella. A continuación, 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, el número de intervalos por socio sigue siendo igual al número de socios, y el proceso puede continuar hasta que cada socio reciba un intervalo. ^{[ 3 ]}

Este protocolo requiere que cada socio responda n consultas ^, por lo que la complejidad de la consulta es O( n² ), de forma similar a Last Diminisher.

Versiones aleatorias

Es posible utilizar la aleatorización para reducir el número de consultas. La idea es que cada participante informe no sobre la colección completa de n candidatos, sino solo sobre un número constante d de candidatos, elegidos al azar. La complejidad de la consulta es O( n ), lo cual es obviamente el mejor resultado posible. En muchos casos, aún será posible asignar a cada participante un único candidato, de manera que no haya solapamiento entre ellos. Sin embargo, existen escenarios en los que dicha asignación será imposible.

Aún podemos cortar un pastel usando O( n ) consultas si hacemos varias concesiones:

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 dar a cada socio una sola pieza contigua, le damos a cada socio la unión de una o más piezas disjuntas.

El esquema general es el siguiente: ^{[ 4 ]}

Cada socio divide privadamente el pastel en an trozos de igual valor subjetivo. Estos n⋅an trozos se denominan trozos candidatos .
Cada participante elige 2d piezas candidatas al azar de forma uniforme, con reemplazo. Las candidatas se agrupan en d pares, que el participante comunica al algoritmo. Estos n⋅d pares se denominan cuadros de cuartos de final .
De cada cuadro de cuartos de final, el algoritmo selecciona una sola pieza: la pieza que se interseca con el menor número de otras piezas candidatas. Estas n⋅d piezas se denominan piezas de semifinal .
Para cada socio, el algoritmo selecciona una pieza; estas se denominan piezas finales . Las piezas finales se seleccionan de manera que cada punto del pastel quede cubierto por un máximo de dos piezas finales (véase más abajo). Si esto tiene éxito, pase al paso 5. Si falla, vuelva a empezar desde el paso 1.
Cada porción del pastel que pertenece a una sola pieza final, se entrega al dueño de esa pieza. Cada porción del pastel que pertenece a dos piezas 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 #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 #4. Para más detalles, consulte el protocolo de Edmonds-Pruhs .

Resultados de dureza

Los resultados de la dificultad se expresan en términos del modelo de consulta de Robertson-Webb , es decir, se relacionan con procedimientos que plantean 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. ^{[ 2 ]}

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. ^{[ 5 ]}

Además, todo procedimiento de división proporcional determinista debe usar Ω( n log n ) consultas, incluso si se le permite asignar a cada socio una porción que es una unión de intervalos, e incluso si solo se le permite garantizar una equidad aproximada . La demostración se basa en acotar inferiormente la complejidad para encontrar, para un solo jugador, una porción de pastel que sea a la vez rica en valor y delgada en ancho. ^{[ 6 ]}

Estos resultados de complejidad implican que la división recursiva por la mitad es el algoritmo más rápido posible para lograr una proporcionalidad completa con piezas contiguas, y el algoritmo determinista más rápido para lograr incluso una proporcionalidad parcial, 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 Ω(n log n) también incluye protocolos aleatorios. ^{[ 6 ]}

La siguiente tabla resume los resultados conocidos: ^{[ 4 ]}

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 posea 8/13 y George 5/13. Esto da lugar al criterio de proporcionalidad ponderada (RPP): 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 RPP. El principal desafío es que el número de repartos puede ser elevado, incluso cuando solo hay dos socios.

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, tal división no siempre existe: cuando todos los socios tienen exactamente las mismas funciones de valor, lo mejor que podemos hacer es asignar 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.

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 .

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 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, la cual se puede encontrar combinando el protocolo del Último Reductor con trucos geométricos que involucran transformaciones conformes .

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 cumplan ciertas 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, normalmente no existe una división proporcional, pero sí una división parcialmente proporcional, que puede hallarse mediante algoritmos eficientes. ^{[ 7 ]}

División económicamente eficiente

Además de ser proporcional, a menudo se exige que la distribución sea económicamente eficiente , es decir, que maximice el bienestar social (definido como la suma de las utilidades de todos los agentes).

Por ejemplo, consideremos un pastel que contiene 500 gramos de chocolate y 500 gramos de vainilla, dividido entre dos personas, una de las cuales solo quiere el chocolate y la otra solo la vainilla. Muchos protocolos de reparto de pasteles asignarían a cada participante 250 gramos de chocolate y 250 gramos de vainilla. Esta división es proporcional, ya que cada participante recibe el 0,5 de su valor total, por lo que el bienestar social normalizado es 1. Sin embargo, esta partición es muy ineficiente, ya que podríamos darle todo el chocolate a una persona y toda la vainilla a la otra, logrando un bienestar social normalizado de 2.

El problema de la división proporcional óptima consiste en encontrar una asignación proporcional que maximice el bienestar social entre todas las posibles asignaciones proporcionales. Actualmente, este problema solo tiene solución para el caso muy especial en el que el pastel 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 todo el pastel), el problema es incluso NP-difícil de aproximar con un factor de 1/ √n . ^[⁸^]

División veraz

La veracidad no es una propiedad de la división, sino del protocolo. Todos los protocolos de división proporcional son débilmente veraces, ya que cada socio que actúa según su verdadera valoración tiene garantizado recibir 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, seguirá recibiendo su proporción garantizada. ^{[ 9 ]}

Sin embargo, la mayoría de los protocolos no son del todo veraces, ya que algunos socios pueden tener incentivos para mentir con el fin de recibir incluso más de la parte garantizada. Esto ocurre incluso en el sencillo protocolo de dividir y elegir : si quien corta conoce las preferencias de quien elige, puede cortar una porción que este último valora ligeramente por debajo de la mitad, pero que él mismo valora mucho más que la mitad.

Existen mecanismos veraces para lograr una división perfecta ; puesto que una división perfecta es proporcional, estos también son mecanismos veraces para la división proporcional.

Estos mecanismos pueden extenderse para proporcionar una división superproporcional cuando existe: ^{[ 10 ]}

Pida a cada socio que informe sobre su medida de valor completa.
Seleccione una partición aleatoria (consulte ^{[ 10 ]} para obtener más detalles).
Si la partición aleatoria resulta ser superproporcional según las medidas de valor reportadas, entonces impleméntela. De lo contrario, utilice un mecanismo veraz para lograr una división perfecta.

Cuando existe una división superproporcional, hay una probabilidad positiva de que se seleccione en el paso 2. Por lo tanto, el valor esperado de cada socio veraz es estrictamente mayor que 1/ n . Para comprobar que el mecanismo es veraz, consideremos tres casos: (a) Si la partición seleccionada es realmente superproporcional, entonces el único resultado posible de mentir es engañar al mecanismo haciéndole creer que no lo es; esto hará que el mecanismo implemente una división perfecta, lo cual será peor para todos los socios, incluido el mentiroso. (b) Si la partición seleccionada 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 crea que la partición es superproporcional y la implemente, lo cual solo perjudica al propio mentiroso. (c) Si la partición seleccionada realmente no es superproporcional porque le da a 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 las tareas domésticas

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, se invierte el signo de desigualdad).

La mayoría de los algoritmos para la división proporcional se pueden adaptar fácilmente a la división de tareas domésticas.

Véase también

División exacta

Referencias

↑ 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 .
1 2 3 4 5 6 7 8 9 Even, S.; Paz, A. (1984). "Una nota sobre el corte de pasteles" . 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 con fecha límite más temprana primero .
1 2 3 4 Jeff Edmonds y Kirk Pruhs (2006). "Asignaciones equilibradas de recursos". 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. S2CID 2091887 .
1 2 3 4 5 Gerhard J. Woeginger y Jiri Sgall (2007). "Sobre la complejidad del corte de pasteles" . Optimización discreta . 4 (2): 213– 220. doi : 10.1016/j.disopt.2006.07.003 .
1 2 3 4 5 6 7 8 9 10 11 Edmonds, Jeff (2006). "Cortar un pastel realmente no es un trozo de pastel". 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 un trozo de pastel". ACM Transactions on Algorithms . 7 (4): 1– 12. CiteSeerX 10.1.1.146.1536 . doi : 10.1145/2000807.2000819 . S2CID 2440968 .
^ 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 .
↑ Bei, Xiaohui; Chen, Ning; Hua, Xia; Tao, Biaoshuai; Yang, Endong (2012). "Corte óptimo de pastel proporcional con piezas conectadas" . Actas de la Conferencia AAAI . Recuperado el 2 de noviembre de 2014 .
↑ Steinhaus, Hugo (1948). "El problema de la división justa". Econometrica . 16 (1): 101– 4. JSTOR 1914289 .
1 2 Mossel, Elchanan ; Tamuz, Omer (2010). División justa y veraz . Notas de clase en ciencias de la computación. Vol. 6386. págs. 288–299 . arXiv : 1003.5480 . Bibcode : 2010LNCS.6386..288M . doi : 10.1007/978-3-642-16170-4_25 . ISBN 978-3-642-16169-8. S2CID 11732339 .

Lecturas adicionales

Brams, Steven J.; Taylor, Alan D. «Un nuevo procedimiento proporcional para el problema del reparto de pasteles entre n personas». En: *Social Choice and Welfare*, vol. 7, n.º 3, 1990, págs. 247-261. Disponible en línea .
Un resumen de los procedimientos de división proporcional y otros aparece en: Austin, AK (1982). "Sharing a Cake". The Mathematical Gazette . 66 (437): 212– 215. doi : 10.2307/3616548 . JSTOR 3616548 . S2CID 158398839 .

[ds61-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 .

[ep84-2] 1 2 3 4 5 6 7 8 9 Even, S.; Paz, A. (1984). "Una nota sobre el corte de pasteles" . Matemáticas Aplicadas Discretas . 7 (3): 285. doi : 10.1016/0166-218x(84)90005-2 .

[3] Este procedimiento de selección es similar a la programación con fecha límite más temprana primero .

[ep06pos-4] 1 2 3 4 Jeff Edmonds y Kirk Pruhs (2006). "Asignaciones equilibradas de recursos". 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. S2CID 2091887 .

[ws07-5] 1 2 3 4 5 Gerhard J. Woeginger y Jiri Sgall (2007). "Sobre la complejidad del corte de pasteles" . Optimización discreta . 4 (2): 213– 220. doi : 10.1016/j.disopt.2006.07.003 .

[ep06neg-6] 1 2 3 4 5 6 7 8 9 10 11 Edmonds, Jeff (2006). "Cortar un pastel realmente no es un trozo de pastel". 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 un trozo de pastel". ACM Transactions on Algorithms . 7 (4): 1– 12. CiteSeerX 10.1.1.146.1536 . doi : 10.1145/2000807.2000819 . S2CID 2440968 .

[7] 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 .

[bchty12-8] Bei, Xiaohui; Chen, Ning; Hua, Xia; Tao, Biaoshuai; Yang, Endong (2012). "Corte óptimo de pastel proporcional con piezas conectadas" . Actas de la Conferencia AAAI . Recuperado el 2 de noviembre de 2014 .

[steinhaus48-9] Steinhaus, Hugo (1948). "El problema de la división justa". Econometrica . 16 (1): 101– 4. JSTOR 1914289 .

[mt10-10] 1 2 Mossel, Elchanan ; Tamuz, Omer (2010). División justa y veraz . Notas de clase en ciencias de la computación. Vol. 6386. págs. 288–299 . arXiv : 1003.5480 . Bibcode : 2010LNCS.6386..288M . doi : 10.1007/978-3-642-16170-4_25 . ISBN 978-3-642-16169-8. S2CID 11732339 .

[ 1 ]

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[

[ 9 ]

[ 10 ]