El corte justo de la torta es una especie de problema de división justa . El problema involucra un recurso heterogéneo , como un pastel con diferentes ingredientes, que se supone divisible : es posible cortar pedazos arbitrariamente pequeños sin destruir su valor. El recurso debe dividirse entre varios socios que tienen diferentes preferencias sobre las diferentes partes del pastel, es decir, algunas personas prefieren las coberturas de chocolate, algunas prefieren las cerezas, algunas simplemente quieren un trozo lo más grande posible. La división debe ser unánimemente justa: cada persona debe recibir una pieza que crea que es una parte justa.
El "pastel" es solo una metáfora ; Los procedimientos para el corte justo de pasteles se pueden utilizar para dividir varios tipos de recursos, como propiedades de tierras, espacios publicitarios o tiempo de transmisión.
El procedimiento prototípico para un corte justo de pasteles es dividir y elegir , que ya se menciona en el libro del Génesis . Resuelve el problema de la división justa para dos personas. El estudio moderno del corte justo de pasteles se inició durante la Segunda Guerra Mundial , cuando Hugo Steinhaus pidió a sus estudiantes Stefan Banach y Bronisław Knaster que encontraran una generalización de dividir y elegir para tres o más personas. Desarrollaron el último procedimiento reductor . [1] Hoy en día, la tarta justa es objeto de una intensa investigación en matemáticas , informática , economía y ciencias políticas . [2]
Supuestos
Hay una torta C , que generalmente se supone que es un segmento unidimensional finito, un polígono bidimensional o un subconjunto finito del plano euclidiano multidimensional R d .
Hay n personas con funciones de valor subjetivos más C . Cada persona i tiene una función de valor V i que asigna subconjuntos de C a números. Se supone que todas las funciones de valor son absolutamente continuas con respecto a la longitud, el área o (en general) la medida de Lebesgue . [3] Esto significa que no hay "átomos" - no hay puntos singulares a los que uno o más agentes asignen un valor positivo, por lo que todas las partes del pastel son divisibles. En muchos casos, se supone que las funciones de valor son sigma aditivas (el valor de un todo es igual a la suma de los valores de sus partes).
C tiene que dividirse en n subconjuntos disjuntos, de modo que cada persona reciba un subconjunto disjunto. La pieza asignada a la persona i se llama, y .
Las n personas tienen los mismos derechos a C . Es decir, no hay disputa sobre los derechos de las personas: todos están de acuerdo en que todos los demás tienen derecho a una parte justa. El único problema es cómo dividir el pastel de manera que cada persona reciba una parte justa.
En los siguientes ejemplos, el siguiente pastel se utilizará como ilustración.
- El bizcocho tiene dos partes: chocolate y vainilla.
- Hay dos personas: Alice y George.
- Alice valora el chocolate como 9 y la vainilla como 1.
- George valora el chocolate como 6 y la vainilla como 4.
Requisitos de justicia
Proporcionalidad
El criterio original y más común de justicia es la proporcionalidad (RP). En un corte de torta proporcional , cada persona recibe un trozo que valora como al menos 1 / n del valor de la torta completa. En el pastel de ejemplo, se puede lograr una división proporcional dando toda la vainilla y 4/9 del chocolate a George (por un valor de 6,66), y los otros 5/9 del chocolate a Alice (por un valor de 5 ). En símbolos:
Para n personas con valoraciones aditivas, siempre existe una división proporcional. Los protocolos más comunes son:
- Last diminisher , un protocolo que puede garantizar que las n piezas estén conectadas (es decir, ninguna persona obtiene un conjunto de dos o más piezas desconectadas). En particular, si el pastel es un intervalo unidimensional, cada persona recibe un intervalo. Este protocolo es discreto y se puede jugar por turnos. Requiere acciones O ( n 2 ).
- El procedimiento de cuchillo móvil Dubins-Spanier es una versión en tiempo continuo de Last diminisher. [4]
- El protocolo Fink (también conocido como pares sucesivos o elector solitario ) es un protocolo discreto que se puede usar para la división en línea: dada una división proporcional para n - 1 socios, cuando un nuevo socio ingresa a la fiesta, el protocolo modifica la división existente para que tanto el nuevo socio como los socios existentes permanecen con 1 / n . La desventaja es que cada socio recibe una gran cantidad de piezas desconectadas.
- El protocolo Even-Paz , basado en dividir a la mitad de manera recursiva el pastel y el grupo de agentes, requiere solo O ( n log n ) acciones. 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 que puede garantizar que las piezas estén conectadas.
- El protocolo Edmonds-Pruhs es un protocolo aleatorio que requiere solo O ( n ) acciones, pero garantiza solo una división parcialmente proporcional (cada socio recibe al menos 1 / an , donde a es una constante), y podría dar a cada socio una colección de "migas" en lugar de una sola pieza conectada.
- Beck protocolo de división de la tierra puede producir una división proporcional de un territorio en disputa entre varios países vecinos, de manera que cada país recibe una parte que es tanto conectado y adyacente a su territorio que actualmente ocupa.
- El protocolo de división superproporcional de Woodall produce una división que le da a cada socio estrictamente más de 1 / n , dado que al menos dos socios tienen opiniones diferentes sobre el valor de al menos una sola pieza.
Consulte corte proporcional de pasteles para obtener más detalles y referencias completas.
El criterio de proporcionalidad se puede generalizar a situaciones en las que los derechos de las personas no son iguales. Por ejemplo, en el corte proporcional de la torta con diferentes derechos , la torta pertenece a los accionistas de manera que uno de ellos tiene el 20% y el otro el 80% de la torta. Esto conduce al criterio de proporcionalidad ponderada (WPR):
Cuando el w i son pesos que resumen a 1.
Libre de envidia
Otro criterio común es la ausencia de envidia (EF). En un corte de pastel sin envidia , cada persona recibe una pieza que valora al menos tanto como cualquier otra pieza. En símbolos:
En algunos casos, existen relaciones de implicación entre proporcionalidad y ausencia de envidia, como se resume en la siguiente tabla:
Agentes | Valoraciones | EF implica PR? | PR implica EF? |
---|---|---|---|
2 | aditivo | sí | sí |
2 | general | No | sí |
3+ | aditivo | sí | No |
3+ | general | No | No |
El protocolo de dividir y elegir encuentra una asignación que siempre es EF. Si las funciones de valor son aditivas, esta división también es PR; de lo contrario, no se garantiza la proporcionalidad.
Existe una división EF para n personas incluso cuando las valoraciones no son aditivas, siempre que puedan representarse como conjuntos de preferencias consistentes. La división EF se ha estudiado por separado para el caso en el que las piezas deben estar conectadas, y para el caso más fácil en el que las piezas pueden desconectarse.
Para piezas conectadas, los principales resultados son:
- El procedimiento de cuchillos móviles de Stromquist produce una división libre de envidia para 3 personas, dándoles a cada uno un cuchillo e indicándoles que muevan sus cuchillos continuamente sobre el pastel de una manera preestablecida.
- El protocolo de Simmons puede producir una aproximación de una división sin envidia para n personas con una precisión arbitraria. Si las funciones de valor son aditivas, la división también será proporcional. De lo contrario, la división seguirá siendo 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. [5] [6]
Ambos algoritmos son infinitos: el primero es continuo y el segundo puede tardar un tiempo infinito en converger. De hecho, ningún protocolo finito puede encontrar divisiones libres de envidia de intervalos conectados a 3 o más personas .
Para piezas posiblemente desconectadas, los principales resultados son:
- El procedimiento discreto de Selfridge-Conway produce una división sin envidia para 3 personas utilizando como máximo 5 cortes.
- El procedimiento de cuchillos móviles de Brams-Taylor-Zwicker produce una división sin envidia para 4 personas utilizando como máximo 11 cortes.
- Una variante reentrante del protocolo Last Diminisher encuentra una aproximación aditiva a una división sin envidia en el tiempo limitado. Específicamente, para cada constante, devuelve una división en la que el valor de cada socio es al menos el valor más grande menos , a tiempo .
- Tres procedimientos diferentes, uno de Brams y Taylor (1995) y uno de Robertson y Webb (1998) y uno de Pikhurko (2000), producen una división libre de envidia para n personas. Ambos algoritmos requieren un número de cortes finito pero ilimitado.
- Un procedimiento de Aziz y Mackenzie (2016) encuentra una división libre de envidia para n personas en un número limitado de consultas.
El resultado negativo en el caso general es mucho más débil que en el caso conectado. Todo lo que sabemos es que cada algoritmo para la división sin envidia debe usar al menos consultas Ω ( n 2 ). Existe una gran brecha entre este resultado y la complejidad en tiempo de ejecución del procedimiento más conocido.
Consulte Corte de pastel sin envidia para obtener más detalles y referencias completas.
Otros criterios
Un tercer criterio menos común es la equidad (EQ). En una división equitativa , cada persona disfruta exactamente del mismo valor. En el pastel de ejemplo, se puede lograr una división equitativa dando a cada persona la mitad del chocolate y la mitad de la vainilla, de modo que cada persona disfrute de un valor de 5. En símbolos:
Un cuarto criterio es la exactitud . Si el derecho de cada socio i es w i , entonces una división exacta es una división en la que:
Si los pesos son todos iguales (a 1 / n ), entonces la división se llama perfecta y:
Requisitos geométricos
En algunos casos, las piezas asignadas a los socios deben satisfacer algunas restricciones geométricas, además de ser justas.
- La restricción más común es la conectividad . En caso de que el "pastel" sea un intervalo unidimensional, esto se traduce en el requisito de que cada pieza sea también un intervalo. En 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 corte de pastel justo .
- Otra limitación es la adyacencia . Esta restricción se aplica al caso en que el "pastel" es un territorio en disputa que debe dividirse entre países vecinos. En este caso, puede requerirse que la pieza asignada a cada país sea adyacente a su territorio actual; esta restricción es manejada por el problema de la división de tierras de Hill .
- En la división de la tierra, a menudo hay restricciones geométricas bidimensionales, por ejemplo, cada pieza debe ser un cuadrado o (más generalmente) un objeto grueso . [7]
Requisitos de procedimiento
Además de las propiedades deseadas de las particiones finales, también existen propiedades deseadas del proceso de división. Una de estas propiedades es la veracidad (también conocida como compatibilidad con incentivos ), que se presenta en dos niveles.
- La veracidad débil significa que si el socio revela su verdadera medida de valor al algoritmo, se le garantiza que recibirá su parte justa (por ejemplo, 1 / n del valor de todo el pastel, en caso de división 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. La mayoría de los algoritmos para cortar pasteles son veraces en este sentido. [1]
- La veracidad fuerte significa que ningún socio puede ganar con la mentira. Es decir, decir la verdad es una estrategia dominante . La mayoría de los protocolos prácticos no son muy veraces, pero se han desarrollado algunos protocolos veraces; ver corte de pastel veraz .
Otra propiedad es la simetría : no debería haber una diferencia entre los diferentes roles en el procedimiento. Se han estudiado varias variantes de esta propiedad:
- El anonimato requiere que, si se permuta a los agentes y se vuelve a ejecutar el procedimiento, cada agente reciba exactamente la misma pieza que en la ejecución original. Ésta es una condición fuerte; Actualmente, un procedimiento anónimo solo se conoce para 2 agentes.
- La simetría requiere que, si los agentes se permutan y el procedimiento se vuelve a ejecutar, entonces cada agente recibe el mismo valor que en la ejecución original. Esto es más débil que el anonimato; Actualmente, se conoce un procedimiento simétrico y proporcional para cualquier número de agentes y requiere O ( n 3 ) consultas. Se conoce un procedimiento simétrico y sin envidias para cualquier número de agentes, pero lleva mucho más tiempo: ¡requiere n ! ejecuciones de un procedimiento sin envidia existente.
- La aristotelidad requiere que, si dos agentes tienen una medida de valor idéntica, reciban el mismo valor. Esto es más débil que la simetría; se satisface con cualquier procedimiento sin envidia. Además, se conoce un procedimiento aristotélico y proporcional para cualquier número de agentes, y requiere O ( n 3 ) consultas.
Consulte la sección de corte de pastel simétrico para obtener detalles y referencias.
Una tercera familia de requisitos de procedimiento es la monotonicidad : cuando se vuelve a aplicar un procedimiento de división con una torta más pequeña / más grande y un conjunto de agentes más pequeño / más grande, la utilidad de todos los agentes debería cambiar en la misma dirección. Consulte la monotonicidad de los recursos para obtener más detalles.
Requisitos de eficiencia
Además de la justicia, también es común considerar la eficiencia económica de la división; ver corte eficiente de pasteles . Hay varios niveles de eficiencia:
- La noción más débil es la eficiencia de Pareto . Se puede satisfacer fácilmente con solo darle el pastel completo a una sola persona; el desafío es satisfacerlo junto con la equidad. Consulte División eficiente sin envidia .
- Una noción más fuerte es la maximalidad utilitaria: maximizar la suma de utilidades. (UM). Cuando las funciones de valor son aditivas, existen divisiones UM. Intuitivamente, para crear una división de UM, debemos darle cada pedazo de pastel a la persona que más lo valora. En el pastel de ejemplo , una división UM le daría todo el chocolate a Alice y toda la vainilla a George, logrando un valor utilitario de 9 + 4 = 13. Este proceso es fácil de llevar a cabo cuando las funciones de valor son constantes por partes, es decir el pastel se puede dividir en pedazos de modo que la densidad de valor de cada pedazo sea constante para todas las personas. Cuando las funciones de valor no son constantes por partes, la existencia de asignaciones UM se deriva de los teoremas clásicos de la teoría de la medida. Consulte Corte de pasteles utilitario .
División justa eficiente
Para n personas con funciones de valor aditivo, siempre existe una división PEEF. [8]
Si el pastel es un intervalo unidimensional y cada persona debe recibir un intervalo conectado, se cumple el siguiente resultado general: si las funciones de valor son estrictamente monótonas (es decir, cada persona prefiere estrictamente una pieza sobre todos sus subconjuntos adecuados), entonces cada división EF es también PE. [9] Por lo tanto, el protocolo de Simmons produce una división PEEF en este caso.
Si el pastel es un círculo unidimensional (es decir, un intervalo cuyos dos puntos finales están identificados topológicamente) y cada persona debe recibir un arco conectado, entonces el resultado anterior no se cumple: una división EF no es necesariamente PE. Además, hay pares de funciones de valor (no aditivas) para las que no existe división PEEF. Sin embargo, si hay 2 agentes y al menos uno de ellos tiene una función de valor aditivo, entonces existe una división PEEF. [10]
Si el pastel es unidimensional pero cada persona puede recibir un subconjunto desconectado, entonces una división EF no es necesariamente PE. En este caso, se requieren algoritmos más complicados para encontrar una división PEEF.
Si las funciones de valor son aditivas y constantes por partes, entonces hay un algoritmo que encuentra una división PEEF. [11] Si las funciones de densidad de valor son aditivas y Lipschitz continuas , entonces pueden aproximarse como funciones constantes por partes "tan cercanas como queramos", por lo tanto, ese algoritmo se aproxima a una división PEEF "tan cercana como queramos". [11]
Una división EF no es necesariamente UM. [12] [13] Un enfoque para manejar esta dificultad es encontrar, entre todas las posibles divisiones EF, la división EF con el valor utilitario más alto. Este problema se ha estudiado para un pastel que es un intervalo unidimensional, cada persona puede recibir trozos desconectados y las funciones de valor son aditivas. [14]
Modelos de computación
Razonar sobre la complejidad de los algoritmos en tiempo de ejecución requiere un modelo de cálculo . Varios de estos modelos son comunes en la literatura:
- El modelo de consulta de Robertson-Webb , en el que el algoritmo puede solicitar a cada agente una consulta de uno de dos tipos: "evaluar un trozo de pastel determinado" o "marcar un trozo de pastel con un valor dado".
- El modelo de cuchillos móviles : en el que el algoritmo mueve continuamente uno o más cuchillos por encima del pastel hasta que algunos agentes gritan "alto".
- El modelo de revelación directa - en el que todos los agentes revelan toda su valoración al mecanismo. Este modelo solo tiene sentido cuando las valoraciones se pueden representar de forma sucinta, por ejemplo, cuando son uniformes por partes, constantes por partes o lineales por partes .
- El modelo de informes simultáneos, en el que los agentes envían simultáneamente discretizaciones de sus medidas de valor. Una discretización es una secuencia de puntos de corte y los valores de las piezas entre estos puntos de corte (por ejemplo: un protocolo para dos agentes puede requerir que cada agente informe una secuencia de tres puntos de corte (0, x , 1) donde los valores de (0, x ) y ( x , 1) son 1/2). [15]
División de varios pasteles
Hay una generalización del problema del corte de la torta en la que hay varias tortas y cada agente necesita obtener un trozo en cada torta.
- Cloutier, Nyman y Su [16] estudian la división multicapa sin envidia de dos jugadores. Para dos pasteles, demuestran que puede no existir una asignación de EF cuando hay 2 agentes y cada pastel se corta en 2 trozos. Sin embargo, existe una asignación de EF cuando hay 2 agentes y una torta se corta en 3 partes (se descarta la parte menos deseada), o cuando hay 3 agentes y cada torta se corta en 2 partes (se ignora un agente; el la asignación es EF para los dos restantes).
- Lebert, Meunier y Carbonneaux [17] prueban, para dos pasteles, que siempre existe una asignación de EF cuando hay 3 agentes y cada pastel se corta en 5 trozos (los dos trozos menos buscados de cada pastel se descartan).
- Nyman, Su y Zerbib [18] prueban, para k pasteles, que siempre existe una asignación de EF cuando hay k ( n -1) +1 agentes y cada pastel se corta en n trozos (la asignación es EF para algún conjunto de n agentes).
Dos problemas relacionados son:
- Corte de pasteles de varias capas, [19] donde los pasteles están dispuestos en "capas" y los trozos del mismo agente no deben superponerse (por ejemplo, cada pastel representa el momento en el que una determinada instalación está disponible durante el día; un agente no puede utilizar dos instalaciones simultáneamente).
- Corte justo de pasteles múltiples, [20] donde los agentes no quieren obtener un pedazo en cada pastel, por el contrario, quieren obtener pedazos en la menor cantidad de pasteles posible.
Ver también
- Asignación justa de artículos : un problema similar en el que los artículos a dividir son indivisibles.
Referencias
- ↑ a b Steinhaus, Hugo (1949). "El problema de la división justa". Econometrica . 17 : 315–9. doi : 10.2307 / 1907319 . JSTOR 1907319 .
- ^ Ariel Procaccia, "Algoritmos de corte de pastel". Capítulo 13 en: Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Manual de elección social computacional . Prensa de la Universidad de Cambridge. ISBN 9781107060432.( versión gratuita en línea )
- ^ Hill, TP; Morrison, KE (2010). "Cortar pasteles con cuidado". The College Mathematics Journal . 41 (4): 281. CiteSeerX 10.1.1.185.656 . doi : 10.4169 / 074683410x510272 . S2CID 3813775 .
- ^ 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 .
- ^ "La calculadora de la división justa" . Archivado desde el original el 28 de febrero de 2010 . Consultado el 10 de julio de 2014 .
- ^ Ivars Peterson (13 de marzo de 2000). "Un trato justo para los compañeros de casa" . MathTrek .
- ^ 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 .
- ^ Weller, D. (1985). "División justa de un espacio medible". Revista de Economía Matemática . 14 : 5–17. doi : 10.1016 / 0304-4068 (85) 90023-0 .
- ^ Berliant, M .; Thomson, W .; Dunz, K. (1992). "Sobre la justa división de una mercancía heterogénea". Revista de Economía Matemática . 21 (3): 201. doi : 10.1016 / 0304-4068 (92) 90001-n .
- ^ Thomson, W. (2006). "Niños llorando en fiestas de cumpleaños. ¿Por qué?". Teoría económica . 31 (3): 501–521. doi : 10.1007 / s00199-006-0109-3 . S2CID 154089829 .
- ^ a b Reijnierse, JH; Potter, JAM (1998). "Sobre la búsqueda de una división óptima de Pareto sin envidia". Programación matemática . 83 (1-3): 291-311. doi : 10.1007 / bf02680564 . S2CID 10219505 .
- ^ Caragiannis, I .; Kaklamanis, C .; Kanellopoulos, P .; Kyropoulou, M. (2011). "La eficiencia de la división justa". Teoría de los sistemas informáticos . 50 (4): 589. CiteSeerX 10.1.1.475.9976 . doi : 10.1007 / s00224-011-9359-y . S2CID 8755258 .
- ^ Aumann, Y .; Dombb, Y. (2010). "La eficiencia de la división justa con piezas conectadas" . Economía de Internet y redes . Apuntes de conferencias en Ciencias de la Computación. 6484 . págs. 26 . CiteSeerX 10.1.1.391.9546 . doi : 10.1007 / 978-3-642-17572-5_3 . ISBN 978-3-642-17571-8.
- ^ Cohler, Yuga Julian; Lai, John Kwang; Parkes, David C; Procaccia, Ariel (2011). Corte de pastel óptimo sin envidia . AAAI.
- ^ Balkanski, Eric; Brânzei, Simina; Kurokawa, David; Procaccia, Ariel (21 de junio de 2014). "Corte simultáneo de tartas" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 28 (1). ISSN 2374-3468 .
- ^ Cloutier, John; Nyman, Kathryn L .; Su, Francis Edward (1 de enero de 2010). "División de varios pasteles sin envidia de dos jugadores" . Ciencias Sociales Matemáticas . 59 (1): 26–37. arXiv : 0909.0301 . doi : 10.1016 / j.mathsocsci.2009.09.002 . ISSN 0165-4896 . S2CID 15381541 .
- ^ Lebert, Nicolas; Meunier, Frédéric; Carbonneaux, Quentin (1 de noviembre de 2013). "M-cake de dos jugadores sin envidia y divisiones de dos tartas de tres jugadores" . Cartas de investigación operativa . 41 (6): 607–610. doi : 10.1016 / j.orl.2013.07.010 . ISSN 0167-6377 .
- ^ Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (15 de septiembre de 2020). "División justa con múltiples piezas" . Matemáticas aplicadas discretas . 283 : 115-122. arXiv : 1710.09477 . doi : 10.1016 / j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .
- ^ Hosseini, Hadi; Igarashi, Ayumi; Searns, Andrew (28 de abril de 2020). "División justa del tiempo: corte de pastel de varias capas". arXiv : 2004.13397 [ cs.GT ].
- ^ Segal-Halevi, Erel (11 de marzo de 2021). "Corte justo de multicartas" . Matemáticas aplicadas discretas . 291 : 15–35. doi : 10.1016 / j.dam.2020.10.011 . ISSN 0166-218X .
Otras lecturas
- Una lista de libros sobre la división de la feria
- Una lista de trabajos de investigación sobre la división justa