Desafío de corte de pastel justo

El corte justo del pastel es una especie de problema de división justa . El problema involucra un recurso heterogéneo, como un pastel con varias decoraciones (de crema , bayas, chocolate ), que se supone que son divisibles , es decir, se puede cortar un trozo arbitrariamente pequeño sin destruir el valor total. El recurso debe dividirse entre varios socios que tienen diferentes preferencias para diferentes partes del pastel. Por ejemplo, algunas personas prefieren las decoraciones de chocolate, otras prefieren las cerezas, mientras que otras solo quieren una pieza más grande. El reparto debe ser subjetivamente justo, cada participante debe recibir una parte que considere justa.

El término "pastel" es solo una metáfora , los procedimientos de corte de pastel se pueden usar para separar diferentes tipos de recursos, como la propiedad de la tierra , el espacio publicitario o el tiempo de transmisión.

El problema de cortar la torta fue propuesto por Hugo Steinhaus después de la Segunda Guerra Mundial [1] y sigue siendo un tema de intenso estudio en matemáticas , informática , economía y ciencias políticas [2] .

Suposiciones

Hay un pastel , que generalmente se supone que es un segmento unidimensional finito, un polígono bidimensional o un subconjunto finito de un espacio euclidiano de dimensiones superiores . $C$ $\mathbb{R}^d$

Hay una persona con los mismos derechos a [3] . $norte$ $C$

$C$ debe dividirse en subconjuntos tan disjuntos que cada participante reciba un subconjunto separado. La pieza destinada al participante se designa como , y . $norte$ $i$ $X_{yo}$ ${\displaystyle C=X_{1}\sqcup \cdots \sqcup X_{n))$

Cada participante debe recibir una pieza con un valor "justo". La equidad se determina sobre la base de funciones de valor subjetivo . Cada cara tiene una función de valor subjetivo que asigna subconjuntos a números. $i$ $V_i$ $C$

Se supone que las funciones son absolutamente continuas en longitud, área o (generalmente) la medida de Lebesgue [4] . Esto significa que no hay "átomos", es decir, puntos singulares a los que uno o más agentes les asignan un valor positivo. Por lo tanto, todas las partes del pastel son divisibles.

Además, en algunos casos, se supone que las funciones de evaluación son sigma-aditivas .

Un ejemplo de un pastel

Usaremos el siguiente pastel como ilustración:

El pastel consta de dos partes: chocolate y vainilla.
Hay dos participantes: Alice y George.
Alice califica la porción de chocolate en 9 unidades y la porción de vainilla en 1 unidad.
George califica la porción de chocolate en 6 unidades y la porción de vainilla en 4.

Demandas de justicia

El criterio original y más general de justicia es la proporcionalidad (PR, inglés proporcionality , PR). En el reparto proporcional de la tarta , cada participante recibe un trozo, cuyo valor estima al menos en el valor total de toda la tarta. En el ejemplo anterior, se puede obtener una división proporcional entregando toda la porción de vainilla y 4/9 de la porción de chocolate a George (con una puntuación total de 6,66), y los 5/9 restantes de la porción de chocolate se le dan a Alice (con una puntuación total de 5). Simbólicamente: $1/n$

\forall {i}:\ V_{i}(X_{i})\geqslant 1/n

El criterio de proporcionalidad puede generalizarse a situaciones en las que los derechos de las personas no son iguales. Por ejemplo, al dividir proporcionalmente un pastel con diferentes partes , el pastel pertenece a los accionistas, por lo que uno de ellos posee el 20% y el otro el 80% del pastel. Esto conduce a un criterio de proporcionalidad ponderada :

\forall i:V_{i}(X_{i})\geqslant w_{i}

donde w i son pesos cuya suma es 1.

Otro criterio típico es la ausencia de envidia (OZ, inglés envy-freeness , EF). Con una división envidiosa [5] , cada persona recibe una pieza, cuyo valor, según esta persona, no es menor que el valor de las otras piezas. Lenguaje formal:

\forall i,j:\ V_{i}(X_{i})\geqslant V_{i}(X_{j})

En algunos casos, existe una relación de implicación (consecuencia) entre la proporcionalidad y la ausencia de envidia, reflejada en el siguiente cuadro:

Agentes	Calificaciones	de OZ sigue PR?	de PR sigue a OZ?
2	aditivo	Sí	Sí
2	general	No	Sí
3+	aditivo	Sí	No
3+	general	No	No

El tercer criterio, menos utilizado, es la imparcialidad ( equitability en inglés , EQ). En una división imparcial , cada persona come una pieza con exactamente el mismo valor de evaluación. En el ejemplo del pastel, se puede obtener un corte imparcial entregando a cada participante la mitad del chocolate y la mitad de las piezas de vainilla, de modo que cada participante disfrute de un valor de 5. Simbólicamente:

\forall i,j:\ V_{i}(X_{i})=V_{j}(X_{j})

El cuarto criterio es la precisión . Si la participación de cada socio i es igual a w i , entonces una división exacta es una división en la que:

{\ estilo de visualización \ para todos {i,j}:\ V_{i}(X_{j})=w_{j}}

Si todos los pesos son iguales (1/ n ), entonces el corte se llama perfecto y

\forall i,j:\ V_{i}(X_{j})=1/n

Requisitos geométricos

En algunos casos, las piezas destinadas a los participantes deben satisfacer algunas restricciones geométricas además de la equidad.

La limitación más común es la conectividad . En el caso de un pastel unidimensional, este requisito se traduce en un requisito de que las piezas sean intervalos. En el caso de que el pastel sea un círculo unidimensional ("pastel"), esto se traduce en el requisito de que cada pieza sea un arco. Ver el artículo " El problema del corte justo del pastel ".
Otra limitación es la adyacencia . Esta limitación se aplica al caso en que el "pastel" sea un territorio en disputa para ser dividido entre países limítrofes. En este caso, podrá exigirse que las piezas entregadas al país linden con el territorio actual del país. Esta restricción es manejada por el problema de división de tierras de Hill-Beck .
Al dividir la tierra, a menudo existen restricciones bidimensionales, como que cada pieza sea un cuadrado o (más generalmente) un objeto grueso [6] [7] .

Requisitos adicionales

En la jurisprudencia, a menudo se considera la rentabilidad de la partición. Consulte el artículo " Corte eficiente de tortas ".

Además de las propiedades deseables de los cortes finitos, también existen propiedades deseables del proceso de división. Una de esas propiedades es la veracidad (también conocida como compatibilidad de estímulo ), que puede ser de dos niveles.

La veracidad débil significa que si un socio revela su verdadero valor al algoritmo, tiene la garantía de obtener una parte justa (por ejemplo, los valores de todo el pastel en el caso de la división proporcional), independientemente de lo que hagan los otros socios. . Incluso si todos los demás socios forman una coalición para infligirle el máximo daño, aún recibirá su parte garantizada. La mayoría de los algoritmos de corte de torta son ciertos en este sentido [1] . $1/n$
La veracidad fuerte significa que ninguna de las partes puede obtener una ventaja mintiendo. Es decir, el comportamiento veraz es la estrategia dominante . La mayoría de los protocolos para cortar pasteles no son estrictamente veraces. Construir un protocolo de división estrictamente veraz es una tarea difícil [8] .

Resultados

2 personas - una división proporcional y sin envidias

Para los humanos, la división OD siempre existe y se puede encontrar utilizando el protocolo divide y elige . Si las funciones de evaluación son aditivas, este corte también será PR, en caso contrario no se garantiza la proporcionalidad. ${\ estilo de visualización n = 2}$

División proporcional

Para n personas con puntajes aditivos, siempre hay un corte proporcional. Protocolos más utilizados:

Procedimiento de último mínimo , un protocolo que puede garantizar que los fragmentos estén conectados (es decir, ningún participante obtiene dos o más fragmentos separados). En particular, si el pastel es un intervalo unidimensional, cada participante recibirá un intervalo. El protocolo es discreto y puede llevarse a cabo en rondas. Requiere acción. $norte$ $O(n^{2})$
El procedimiento Dubins-Spenier Moving Knife es una versión continua en el tiempo del protocolo Last Decreasing [9] .
El protocolo Fink (también conocido como pares consecutivos o selector único ) es un protocolo discreto que se puede usar para cortar en línea: si se conoce el corte proporcional para los socios, cuando un nuevo socio ingresa al juego, el protocolo modifica el corte existente para que el participante entrante y los ya participantes en el intercambio reciben . La desventaja del protocolo es que cada socio recibe una gran cantidad de piezas individuales. $n-1$ $1/n$
El protocolo Even-Paz , basado en la bisección continua de un pastel y un grupo de agentes, y que requiere todas lasacciones. Este es el protocolo determinista más rápido posible para la división proporcional y el protocolo más rápido posible para la división proporcional, lo que garantiza que todas las piezas estén conectadas. $O(n\log n)$
El protocolo de Edmonds-Prus es un protocolo aleatorio que requiere todas las acciones pero garantiza solo un corte parcialmente proporcional (cada participante obtiene al menos , donde hay alguna constante), y puede dar a cada participante un conjunto de migajas en lugar de una pieza coherente. $En)$ ${\ estilo de visualización 1/un}$ $a$
El protocolo de división de tierras de Beck puede dar una división proporcional del territorio en disputa entre varios países vecinos. En este caso, cada país recibe una parte que está conectada y limita con el territorio actual del país.
El protocolo de división superproporcional de Woodall produce una división en la que cada participante recibe estrictamente más de , dado que al menos dos participantes tienen opiniones diferentes sobre el valor de al menos una pieza. $1/n$

Consulte el artículo " División proporcional de un pastel con diferentes proporciones " para obtener detalles y una bibliografía completa.

Los algoritmos anteriores se centran principalmente en agentes con una parte igual de los requisitos de recursos. Sin embargo, puede generalizarlos y obtener una división proporcional del pastel con diferentes partes .

División envidiosa

La división PO para una persona existe incluso si las calificaciones no son aditivas, siempre que estén representadas por conjuntos de preferencias coherentes. La división OD se estudió por separado para el caso en que las piezas deben estar conectadas y para el caso en que las piezas pueden consistir en partes separadas desconectadas. $norte$

Para piezas conectadas, los principales resultados son:

El procedimiento "Mover cuchillo" de Stromquist produce una división sin envidia para 3 personas al asignarles a cada uno un cuchillo y pedirles que muevan sus cuchillos continuamente sobre el pastel de acuerdo con el procedimiento prescrito.
El Protocolo Simmons puede dar una aproximación de corte sin envidia para humanos con precisión arbitraria. Si las funciones de evaluación son aditivas, la división también será proporcional. De lo contrario, la división queda libre de envidia, pero no necesariamente proporcional. El algoritmo proporciona una forma rápida y práctica de resolver algunos problemas de división justa [10] [11] . $norte$

Ambos algoritmos son infinitos: el primero es continuo, mientras que el segundo puede tardar una cantidad infinita de tiempo en converger. De hecho, ningún protocolo finito puede encontrar cortes libres de envidia en intervalos conectados para 3 o más personas .

Para fragmentos (posiblemente) desconectados, los principales resultados son:

El procedimiento discreto de Selfridge-Conway produce un corte sin envidia para tres participantes en no más de 5 cortes.
El procedimiento de "cuchillo móvil" de Brahms-Taylor-Zwicker produce un corte sin envidia para cuatro participantes en no más de 11 cortes.
Una variante del protocolo " Último Reductor " con reutilización encuentra una aproximación aditiva al corte sin envidia en un tiempo limitado. Específicamente, para cualquier constante , el protocolo produce un corte en el que el valor de cada miembro es al menos mayor que el valor más grande menos el tiempo . ${\ estilo de visualización \ épsilon > 0}$ $\epsilon$ $O(n^{2}/\epsilon)$
Tres procedimientos diferentes, uno de Brahms y Taylor (1995) , otro de Robertson y Webb (1998) y otro más, el procedimiento de Pikurko (2000) proporcionan cortes sin envidia para los humanos. Ambos algoritmos requieren un número finito pero ilimitado de cortes. $norte$
El procedimiento de Aziz y McKenzie (2016) encuentra un corte sin envidia para las personas para un número limitado de consultas. $norte$

El resultado negativo en el caso general es mucho más débil que en el caso de la conectividad. Todo lo que sabemos es que cualquier algoritmo de corte sin envidia debe usar al menos consultas. Existe una gran brecha entre este resultado y la complejidad computacional de los procedimientos conocidos. ${\ estilo de visualización \ Omega (n^{2})}$

Ver corte de torta sin envidia [ 5 ] para detalles y una bibliografía completa .

División eficiente

Cuando las funciones de evaluación son aditivas, hay un corte de utilidad ( Utilitarian-maximal , UM) . Intuitivamente, para crear un corte de RP, necesitamos darle a cada participante un trozo de pastel con un valor que sea máximo para él. En el ejemplo del pastel RP, cortar le dará todo el chocolate a Alice y toda la vainilla a George, logrando utilidad . ${\ estilo de visualización 9 + 4 = 13}$

Este proceso es fácil de implementar si las funciones de evaluación son constantes por partes, es decir, el pastel se puede dividir en partes de manera que la densidad de precios de cada parte sea constante para todos los participantes. Cuando las funciones del estimador no son constantes por partes, la existencia de cortes RP se basa en una generalización de este procedimiento para las funciones del estimador usando el teorema de Radon-Nikodim , ver el Teorema 2 en Dubins y Spanier [9] .

Cuando el pastel es unidimensional y las piezas deben estar conectadas (es decir, segmentos continuos), el algoritmo simple para asignar la pieza al agente más significativo no funciona. En este caso, la tarea de encontrar el RP del corte es NP-difícil y, además, ningún esquema FPTAS es posible a menos que P = NP. Hay un algoritmo de aproximación de 8 veces y un algoritmo de complejidad parametrizada que es exponencial en el número de jugadores [12] .

Para cualquier conjunto de pesos positivos, la partición RP ponderada se puede encontrar mediante métodos similares. Por lo tanto, las particiones eficientes de Pareto ( PE) siempre existen .

Justicia procesal

Recientemente, ha habido interés no solo en la equidad de la división final, sino también en la equidad del procedimiento de división: no debe haber diferencia entre los diferentes roles en el procedimiento. Se ha estudiado cierta equidad procesal:

El anonimato requiere que en el caso de permutación de agentes y repetición del procedimiento, cada agente reciba exactamente la misma pieza que en la división original. Esta es una condición estricta. Actualmente, el procedimiento anónimo es conocido solo por 2 agentes.
La simetría requiere que en el caso de que se permuten los agentes y se repita el procedimiento para los agentes permutados, cada agente reciba el mismo valor que en la división original. Esta es una condición más débil que el anonimato. En la actualidad se conocen procedimientos simétricos y proporcionales para cualquier número de agentes, y requieren consultas. Se conoce un procedimiento simétrico y sin envidia para cualquier número de agentes, pero requiere un tiempo de ejecución mucho más largo: requiere ejecuciones del procedimiento sin envidia existente. $O(n^{3})$ $¡norte!$
El aristotelismo requiere que si dos agentes tienen idénticas medidas de significado, recibirán el mismo valor. Esto es más débil que la simetría y se satisface con cualquier procedimiento libre de envidia. Además, los procedimientos aristotélicos y proporcionales se conocen para cualquier número de agentes y requieren consultas. $O(n^{3})$

Consulte el artículo " Corte de pastel justo simétrico " para obtener detalles y enlaces.

División justa eficiente

Para n personas con funciones de valor aditivo, siempre hay una división EPOS [13] .

Si el pastel es un intervalo unidimensional y cada participante debe obtener un intervalo conexo, entonces se cumple el siguiente resultado general: si las funciones de evaluación son estrictamente monótonas (cada participante prefiere fuertemente una pieza, y no cualquiera de sus propios subconjuntos), entonces cualquier división de OZ también será un EP [14] . Por lo tanto, el protocolo de Simons en este caso da la división EPOS.

Si el pastel es un círculo unidimensional (por ejemplo, un intervalo en el que se identifican topológicamente dos extremos) y cada cara debe recibir un arco conectado, entonces el resultado anterior no es correcto: la división OD no será necesariamente un EP. Además, hay pares de funciones de estimación (no aditivas) para las que no existe el uso compartido de EPOS. Sin embargo, si hay 2 agentes y al menos uno de ellos tiene una función de evaluación aditiva, entonces existe la división EPOS [15] .

Si el pastel es unidimensional, pero cualquier persona puede obtener un subconjunto discontinuo, la división OD no será necesariamente EP. En este caso, se requieren algoritmos más complejos para encontrar el EPOS de la división.

Si las funciones de evaluación son aditivas y constantes por partes, entonces hay un algoritmo que encuentra la división EPOS [16] . Si las funciones de densidad del estimador son aditivas y continuas de Lipschitz , entonces pueden aproximarse mediante funciones constantes por partes “tan cerca como queramos”, por lo que este algoritmo aproxima la división EPOS “tan cerca como queramos” [16] .

La división OD no es necesariamente la RP [17] [18] . Uno de los enfoques para hacer frente a esta dificultad es buscar la división con el valor máximo de utilidad entre todos los OC posibles de OC. Este problema fue estudiado para un pastel, que es un intervalo unidimensional, del cual cada persona puede obtener partes discontinuas, y las funciones de evaluación son aditivas [19] .

Procedimientos no aditivos

La mayoría de los procedimientos de distribución justa existentes descritos anteriormente asumen una utilidad adicional para los jugadores. En otras palabras, si un jugador obtiene alguna utilidad de 25 g de pastel de chocolate, se supone que obtendrá exactamente el doble de utilidad de 50 g del mismo pastel de chocolate.

En 2013, Rishi S. Mirchandani demostró que la mayoría de los algoritmos de división justa existentes son incompatibles con las funciones de utilidad no aditivas [20] . También demostró que el caso especial del problema de la división justa, en el que los jugadores tienen funciones de utilidad no aditivas, no puede tener soluciones proporcionales.

Mirchandani sugirió que el problema de la división justa podría resolverse utilizando técnicas de optimización no lineal. Sin embargo, la pregunta sigue siendo si existen mejores algoritmos para subconjuntos específicos de funciones de utilidad no aditivas.

Véase también

El problema de la distribución justa de objetos es un problema similar, donde los objetos de la división son indivisibles.

Notas

↑ 1 2 Steinhaus, 1948 , pág. 101–4.
↑ Procaccia, 2016 .
↑ Los derechos humanos no se discuten aquí, la tarea es dividir el pastel para que cada persona obtenga una parte justa.
↑ Colina, Morrison, 2010 , pág. 281.
↑ 1 2 A menudo traducido como "división sin envidia" (papel de calco del inglés), aunque es la presencia de la envidia la que juega el papel principal en esta división.
↑ Es decir, para que su largo y ancho sean cercanos.
↑ Segal-Halevi, Nitzan, Hassidim, Aumann, 2017 , pág. 1–28.
↑ Chen, Lai, Parkes, Procaccia, 2013 , pág. 284–297.
↑ 1 2 Dubins, Spanier, 1961 , p. 1–17.
↑ La calculadora de división justa (enlace descendente) . Consultado el 12 de octubre de 2019. Archivado desde el original el 28 de febrero de 2010. (indefinido)
↑ Ivars Peterson. Un trato justo para los compañeros de casa . MathTrek (13 de marzo de 2000). Consultado el 12 de octubre de 2019. Archivado desde el original el 20 de septiembre de 2012. (indefinido)
↑ Aumann, Dombb, Hassidim, 2013 .
↑ Weller, 1985 , pág. 5–17.
↑ Berliant, Thomson, Dunz, 1992 , pág. 201.
↑ Thomson, 2006 , pág. 501–521.
↑ 1 2 Reijnierse, Alfareros, 1998 , p. 291–311.
↑ Caragiannis, Kaklamanis, Kanellopoulos, Kyropoulou, 2011 , pág. 589.
↑ Aumann, Dombb, 2010 , pág. 26
↑ Cohler, Lai, Parkes, Procaccia, 2011 .
↑ Mirchandani, 2013 , pág. 78–91.

Literatura

Ariel Procaccia. Capítulo 13: Algoritmos de corte de torta // Manual de elección social computacional / Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. - Cambridge University Press, 2016. - ISBN 9781107060432 .
Hugo Steinhaus. El problema de la división justa // Econometrica. - 1948. - T. 16 , núm. 1 . — .
Hill TP, Morrison KE Cortando pasteles con cuidado // The College Mathematics Journal. - 2010. - T. 41 , núm. 4 . doi : 10.4169 / 074683410x510272 .
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 . _
Yiling Chen, John K. Lai, David C. Parkes, Ariel D. Procaccia. Verdad, justicia y corte de torta // Juegos y Comportamiento Económico. - 2013. - T. 77 , núm. 1 . -doi : 10.1016/ j.geb.2012.10.009 .
Lester Dubins. Cómo cortar un pastel de manera justa // The American Mathematical Monthly. - 1961. - T. 68 , núm. 1 . -doi : 10.2307/ 2311357 . — .
Yonatan Aumann, Yair Dombb, Avinatan Hassidim. Cálculo de divisiones de pasteles socialmente eficientes . — 2013.
Weller D. División justa de un espacio medible // Journal of Mathematical Economics. - 1985. - T. 14 . - doi : 10.1016/0304-4068(85)90023-0 .
Berliant M., Thomson W., Dunz K. Sobre la división justa de una mercancía heterogénea // Journal of Mathematical Economics. - 1992. - T. 21 , núm. 3 . -doi : 10.1016 / 0304-4068(92)90001-n .
Thomson W. Niños llorando en fiestas de cumpleaños. ¿Por qué? // Teoría económica. - 2006. - T. 31 , núm. 3 . -doi : 10.1007/ s00199-006-0109-3 .
Reijnierse JH, Potters JAM Sobre cómo encontrar una división óptima de Pareto libre de envidias // Programación matemática. - 1998. - T. 83 , núm. 1–3 . -doi : 10.1007/ bf02680564 .
Caragiannis I., Kaklamanis C., Kanellopoulos P., Kyropoulou M. La eficiencia de la división justa // Teoría de los sistemas informáticos. - 2011. - T. 50 , núm. 4 . -doi : 10.1007 / s00224-011-9359-y .
Aumann Y., Dombb Y. La eficiencia de la división justa con piezas conectadas // Internet y economía de redes . - 2010. - T. 6484. - (Apuntes de cátedra en Informática). — ISBN 978-3-642-17571-8 . -doi : 10.1007 / 978-3-642-17572-5_3 . Es necesario registrarse para descargar
Yuga Julian Cohler, John Kwang Lai, David C. Parkes, Ariel Procaccia. Corte óptimo de pasteles sin envidia, conferencia AAAI . — 2011.
Rishi Mirchandani. Superaditividad y subaditividad en división justa // Journal of Mathematics Research. - 2013. - Agosto ( vol. 5 , número 3 ). doi : 10.5539 / jmr.v5n3p78 .