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 diferentes ingredientes, que se supone es divisible : es posible cortar trozos arbitrariamente pequeños sin destruir su valor. El recurso tiene que dividirse entre varios socios que tienen diferentes preferencias sobre diferentes partes del pastel, es decir, algunas personas prefieren los aderezos de chocolate, otras prefieren las cerezas, otras simplemente quieren un trozo lo más grande posible. La división debe ser unánimemente justa: cada persona debe recibir una parte que se considere justa.
El "pastel" es sólo una metáfora ; Los procedimientos de reparto justo se pueden utilizar para dividir varios tipos de recursos, como propiedades, espacio publicitario o tiempo de transmisión.
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 subjetivo sobre C . Cada persona i tiene una función de valor Vi 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 debe 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 que C . Es decir, no hay disputa sobre los derechos de la gente: 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 se utilizará el siguiente pastel como ilustración.
El bizcocho tiene dos partes: chocolate y vainilla.
Hay dos personas: Alice y George.
Alice valora el chocolate con 9 y la vainilla con 1.
George valora el chocolate con 6 y la vainilla con 4.
Requisitos de justicia
Proporcionalidad
El criterio original y más común de justicia es la proporcionalidad (PR). En un corte de tarta proporcional , cada persona recibe un trozo que valora al menos como 1/ n del valor de toda la tarta. En el pastel de ejemplo, se puede lograr una división proporcional dándole 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:
Último disminuidor , un protocolo que puede garantizar que las n piezas estén conectadas (es decir, ninguna persona recibe un conjunto de dos o más piezas desconectadas). En particular, si el pastel es un intervalo unidimensional, entonces cada persona recibe un intervalo. Este protocolo es discreto y se puede jugar por turnos. Requiere O( n 2 ) acciones.
El protocolo Fink (también conocido como pares sucesivos o selector solitario ) es un protocolo discreto que se puede utilizar para la división en línea: dada una división proporcional para n − 1 socios, cuando un nuevo socio ingresa al partido, 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 recursivamente a la mitad 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 sólo O( n ) acciones, pero garantiza sólo una división parcialmente proporcional (cada socio recibe al menos 1/ an , donde a es una constante), y podría darle a cada socio una colección de "migajas" en lugar de una sola pieza conectada.
El protocolo de división de tierras de Beck puede producir una división proporcional de un territorio en disputa entre varios países vecinos, de modo que cada país reciba una parte que esté conectada y adyacente a su territorio actual.
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 pieza.
El criterio de proporcionalidad puede generalizarse a situaciones en las que los derechos de las personas no son iguales. Por ejemplo, en el corte proporcional del pastel con diferentes derechos , el pastel pertenece a los accionistas de modo que uno de ellos posee el 20% y el otro el 80% del pastel. Esto lleva al criterio de proporcionalidad ponderada (WPR):
Donde los w i son pesos que suman 1.
Libre de envidia
Otro criterio común es la ausencia de envidia (EF). En un corte de tarta 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:
El protocolo divide y elige encuentra una asignación que siempre es EF. Si las funciones de valor son aditivas entonces 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 sin 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 predeterminada.
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á estando libre de envidia pero no necesariamente proporcional. El algoritmo ofrece 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 entre 3 o más personas .
Para piezas posiblemente desconectadas, los principales resultados son:
Una variante reentrante del protocolo Last Diminisher encuentra una aproximación aditiva a una división libre de envidia en un 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 , en el tiempo .
Tres procedimientos diferentes, uno de Brams y Taylor (1995) , otro de Robertson y Webb (1998) y otro de Pikhurko (2000), producen una división libre de envidia para n personas. Ambos algoritmos requieren un número finito pero ilimitado de cortes.
Un procedimiento de Aziz y Mackenzie (2016) [7] encuentra una división libre de envidia para n personas en un número acotado de consultas.
El resultado negativo en el caso general es mucho más débil que en el caso conexo. Todo lo que sabemos es que todo algoritmo para la división sin envidia debe utilizar al menos Ω( n 2 ) consultas. Existe una gran brecha entre este resultado y la complejidad del tiempo de ejecución del procedimiento más conocido.
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 dándole 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 todos los pesos son 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 limitaciones geométricas, además de ser justas.
La limitació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 restricción es la adyacencia . Esta restricción se aplica al caso en que el "pastel" es un territorio en disputa que debe dividirse entre los países vecinos. En este caso, podrá exigirse que la pieza asignada a cada país sea adyacente a su territorio actual; esta restricción se maneja mediante el problema de división de la tierra de Hill .
En la división de tierras a menudo hay restricciones geométricas bidimensionales, por ejemplo, cada pieza debe ser un cuadrado o (más generalmente) un objeto grueso . [8]
Requisitos procesales
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 de 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 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 otros 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. La mayoría de los algoritmos para cortar pasteles son veraces en este sentido. [1]
Una fuerte veracidad significa que ninguna pareja puede beneficiarse mintiendo. Es decir, decir la verdad es una estrategia dominante . La mayoría de los protocolos básicos no son totalmente veraces, pero se han desarrollado algunos protocolos veraces; ver corte de pastel veraz .
Otra propiedad es la simetría : no debe haber diferencia entre los diferentes roles en el procedimiento. Se han estudiado varias variantes de esta propiedad:
El anonimato requiere que, si se permutan los agentes y se vuelve a ejecutar el procedimiento, cada agente reciba exactamente la misma pieza que en la ejecución original. Esta es una condición fuerte; Actualmente, se conoce un procedimiento anónimo sólo para 2 agentes.
La simetría requiere que, si se permutan los agentes y se vuelve a ejecutar el procedimiento, cada agente reciba 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 libre de envidia para cualquier número de agentes, pero lleva mucho más tiempo: requiere n ! ejecuciones de un procedimiento existente libre de envidia.
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 libre de envidia. Además, se conoce un procedimiento aristotélico y proporcional para cualquier número de agentes, y requiere O( n 3 ) consultas.
Una tercera familia de requisitos procesales es la monotonicidad : cuando se vuelve a aplicar un procedimiento de división con una torta más pequeña o más grande y un conjunto de agentes más pequeño o más grande, la utilidad de todos los agentes debería cambiar en la misma dirección. Consulte monotonicidad de 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 de pastel eficiente . Hay varios niveles de eficiencia:
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 UM, debemos darle cada trozo 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. Ver Corte de pastel utilitario .
División justa y eficiente
Para n personas con funciones de valor aditivo, siempre existe una división PEEF. Este es el teorema de Weller . [9]
Si el pastel es un intervalo unidimensional y cada persona debe recibir un intervalo conexo, se cumple el siguiente resultado general: si las funciones de valor son estrictamente monótonas (es decir, cada persona prefiere estrictamente un trozo sobre todos sus subconjuntos propios), entonces cada división EF es también educación física. [10] 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 extremos están topológicamente identificados) 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. [11]
Si el pastel es unidimensional pero cada persona puede recibir un subconjunto desconectado del mismo, 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 existe un algoritmo que encuentra una división PEEF. [12] Si las funciones de densidad de valores son aditivas y Lipschitz continuas , entonces pueden aproximarse como funciones constantes por partes "tan cerca como queramos", por lo tanto, ese algoritmo se aproxima a una división PEEF "tan cerca como queramos". [12]
Una división EF no es necesariamente UM. [13] [14] Un enfoque para manejar esta dificultad es encontrar, entre todas las divisiones EF posibles, 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 piezas desconectadas y las funciones de valor son aditivas. [15]
Modelos de computacion
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 hacer a cada agente una consulta de dos tipos: "evaluar un trozo de pastel determinado" o "marcar un trozo de pastel con un valor determinado".
El modelo de cuchillos móviles : en el que el algoritmo mueve continuamente uno o más cuchillos sobre el 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 sólo tiene sentido cuando las valoraciones se pueden representar de manera 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). [dieciséis]
Dividir varios pasteles
Existe una generalización del problema del corte de pasteles en el que hay varios pasteles y cada agente necesita obtener un trozo de cada pastel.
Cloutier, Nyman y Su [17] estudian la división de pasteles múltiples sin envidia para 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 pedazos. Sin embargo, existe una asignación EF cuando hay 2 agentes y un pastel se corta en 3 pedazos (el pedazo menos deseado se descarta), o cuando hay 3 agentes y cada pastel se corta en 2 pedazos (un agente se ignora; el la asignación es EF para los dos restantes).
Lebert, Meunier y Carbonneaux [18] demuestran, para dos pasteles, que siempre existe una asignación de EF cuando hay 3 agentes y cada pastel se corta en 5 pedazos (los dos pedazos menos deseados de cada pastel se descartan).
Nyman, Su y Zerbib [19] demuestran, 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 pedazos (la asignación es EF para algún conjunto de n agentes).
Dos problemas relacionados son:
Corte de pastel multicapa, [20] donde los pasteles se disponen en "capas" y los trozos del mismo agente no deben superponerse (por ejemplo, cada pastel representa el horario en el que una determinada instalación está disponible durante el día; un agente no se pueden utilizar dos instalaciones simultáneamente).
Corte justo de múltiples pasteles, [21] donde los agentes no quieren obtener un pedazo en cada pastel, por el contrario, quieren obtener pedazos en la menor cantidad de pasteles posible.
compartir pastel
Bei, Lu y Suksompong [22] presentan un modelo en el que, en lugar de dividir un trozo de pastel individual para cada agente, los agentes deben elegir juntos un trozo de pastel que compartirán todos. Esto puede verse como una variante de la elección del comité , donde los candidatos son divisibles. Hay un continuo de candidatos, representado por un intervalo real [0, c ], y el objetivo es seleccionar un subconjunto de este intervalo, con una longitud total como máximo k , donde k y c pueden ser cualquier número real con 0< k < c . Generalizan la noción de representación justificada a este escenario. Lu, Peters, Aziz, Bei y Suksompong [23] extienden estas definiciones a entornos con candidatos mixtos divisibles e indivisibles (ver representación justificada ).
^ ab Steinhaus, Hugo (1949). "El problema de la división justa". Econométrica . 17 : 315–9. doi :10.2307/1907319. JSTOR 1907319.
^
Ariel Procaccia, "Algoritmos de corte de pasteles". Capítulo 13 en: Brandt, Felix; Conitzer, Vicente; 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)
^ Colina, TP; Morrison, KE (2010). "Cortar pasteles con cuidado". La revista universitaria de matemáticas . 41 (4): 281. CiteSeerX 10.1.1.185.656 . doi :10.4169/074683410x510272. S2CID 3813775.
^ Dubins, Lester Eli ; Español, Edwin Henry (1961). "Cómo cortar un pastel de manera justa". El Mensual Matemático Estadounidense . 68 (1): 1–17. doi :10.2307/2311357. JSTOR 2311357.
^ "La calculadora de 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 . Archivado desde el original el 20 de septiembre de 2012 . Consultado el 10 de julio de 2014 .
^ Aziz, Haris; Mackenzie, Simon (27 de agosto de 2017). "Un protocolo de corte de pasteles discreto y limitado, sin envidia, para cualquier número de agentes". arXiv : 1604.03655 [cs.DS].
^ 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.
^ Weller, D. (1985). "División justa de un espacio mensurable". 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 división justa de un bien heterogéneo". Revista de Economía Matemática . 21 (3): 201. doi :10.1016/0304-4068(92)90001-n.
^ Thomson, W. (2006). "Niños llorando en las fiestas de cumpleaños. ¿Por qué?". Teoría económica . 31 (3): 501–521. doi :10.1007/s00199-006-0109-3. S2CID 154089829.
^ ab Reijnierse, JH; Alfareros, JAM (1998). "Sobre encontrar una división óptima de Pareto sin envidia". Programación Matemática . 83 (1–3): 291–311. doi :10.1007/bf02680564. S2CID 10219505.
^ Caragiannis, yo; Kaklamanis, C.; Kanellopoulos, P.; Kyropoulou, M. (2011). "La eficiencia de la división justa". Teoría de los Sistemas Computacionales . 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" . Internet y economía de redes. Apuntes de conferencias sobre informática. vol. 6484. págs. 26. CiteSeerX 10.1.1.391.9546 . doi :10.1007/978-3-642-17572-5_3. ISBN978-3-642-17571-8.
^ Cohler, Yuga Julián; Lai, John Kwang; Parkes, David C; Procaccia, Ariel (2011). Óptimo corte de tarta sin envidia. AAAI.
^ Balcanski, Eric; Brânzei, Simina; Kurokawa, David; Procaccia, Ariel (21 de junio de 2014). "Corte de pastel simultáneo". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 28 (1). doi : 10.1609/aaai.v28i1.8802 . ISSN 2374-3468. S2CID 1867115.
^ Cloutier, John; Nyman, Kathryn L.; Su, Francis Edward (1 de enero de 2010). "División de pasteles múltiples sin envidia para 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, Nicolás; Meunier, Federico; Carbonneaux, Quentin (1 de noviembre de 2013). "Divisiones m-cake para dos jugadores y dos cake para tres jugadores sin envidia". Cartas de investigación operativa . 41 (6): 607–610. doi :10.1016/j.orl.2013.07.010. ISSN 0167-6377. S2CID 7937916.
^ Nyman, Kathryn; Su, Francisco Eduardo; Zerbib, Shira (15 de septiembre de 2020). "División justa con múltiples piezas". Matemática Aplicada Discreta . 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 tortas múltiples". Matemática Aplicada Discreta . 291 : 15–35. doi :10.1016/j.dam.2020.10.011. ISSN 0166-218X. S2CID 219792647.
^ Bei, Xiaohui; Lu, Xinhang; Suksompong, Warut (28 de junio de 2022). "Compartir pasteles verazmente". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 36 (5): 4809–4817. arXiv : 2112.05632 . doi : 10.1609/aaai.v36i5.20408. ISSN 2374-3468.
^ Lu, Xinhang; Peters, Jannik; Aziz, Haris; Bei, Xiaohui; Suksompong, Warut (26 de junio de 2023). "Votación basada en aprobación con bienes mixtos". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 37 (5): 5781–5788. arXiv : 2211.12647 . doi : 10.1609/aaai.v37i5.25717 . ISSN 2374-3468.
Otras lecturas
Una lista de libros sobre división justa.
Una lista de trabajos de investigación sobre la división justa.