Esta página enumera problemas abiertos notables relacionados con la división justa , un campo en la intersección de las matemáticas, la informática, las ciencias políticas y la economía.
Problemas abiertos en el corte justo de pasteles
Consulta la complejidad del corte de pasteles sin envidia
En el problema del corte de pastel sin envidia , hay un pastel modelado como un intervalo, yagentes con diferentes medidas de valor sobre el pastel. Las medidas de valor son accesibles solo a través de consultas de la forma "evaluar un pedazo de pastel dado" o "marcar un pedazo de pastel con un valor dado". Conagentes, se puede encontrar una división libre de envidia mediante dos consultas, a través de dividir y elegir . Con agentes, hay varios problemas abiertos con respecto al número de consultas necesarias.
1. Primero, suponga que se debe asignar todo el pastel (es decir, que no hay eliminación ) y que se pueden desconectar las piezas. ¿Cuántas consultas se requieren?
2. A continuación, suponga que un pastel puede quedar sin asignar (es decir, hay libre disposición ), pero la asignación debe ser proporcional (además de libre de envidia): cada agente debe obtener al menosdel valor total de la torta. Las piezas aún pueden estar desconectadas. ¿Cuántas consultas se requieren?
- Límite inferior: no conocido (teóricamente puede ser polinomialmente soluble).
- Límite superior: . [2]
3. A continuación, suponga que hay disposición gratuita, la asignación debe seguir siendo proporcional, pero las piezas deben estar conectadas . ¿Cuántas consultas se requieren?
- Para , hay un algoritmo con 54 consultas. [3]
- Para , actualmente no se conoce ningún algoritmo finito.
4. A continuación, suponga que hay disposición gratuita, las piezas deben estar conectadas, pero la asignación puede ser solo aproximadamente proporcional (es decir, algunos agentes pueden obtener menos de del valor total de la torta). ¿Qué valor se le puede garantizar a cada agente utilizando un protocolo finito sin envidia?
- Para , hay un algoritmo que alcanza 1/3, que es óptimo.
- Para (el caso abierto más pequeño), hay un algoritmo que alcanza 1/7. [3]
- Para cualquier , hay un algoritmo que logra . [2]
5. Por último, suponga que se debe asignar todo el pastel y que se pueden desconectar las piezas, pero la cantidad de cortes (o la cantidad de piezas por agente) debe ser lo más pequeña posible. ¿Cuántos recortes necesitamos para encontrar una asignación sin envidia en un número finito de consultas ?
- Para , no existe un algoritmo finito paracortes (1 pieza por agente). [4]
- Para El procedimiento Selfridge-Conway resuelve el problema en un tiempo finito con 5 cortes (y como máximo 2 piezas por agente).
- Para , el procedimiento de Aziz-Mackenzie resuelve el problema en tiempo finito, pero con muchos cortes (y muchas piezas por agente).
- Caso abierto más pequeño: tres agentes y 3 o 4 cortes; cuatro agentes y 2 piezas por agente.
Número de cortes para cortar pasteles con diferentes derechos
Cuando todos los agentes tienen los mismos derechos, se puede implementar un corte de torta proporcional utilizando cortes, lo cual es óptimo.
¿Cuántos cortes se requieren para implementar un corte de torta proporcional entre agentes con diferentes derechos?
- Límite inferior: ; [5]
- Límite superior: . [6]
- Caso abierto más pequeño: agentes con todos los derechos diferentes: , y . [5]
¿Cuántos cortes se requieren para implementar un corte de pastel sin envidia entre agentes con diferentes derechos?
- Límite inferior: , ya que sin envidia implica proporcional.
- Límite superior: no conocido.
División justa de una torta parcialmente quemada
Una torta parcialmente quemada es una metáfora de una torta en la que los agentes pueden tener valoraciones tanto positivas como negativas. [7]
Siempre existe una división proporcional de tal pastel.
- ¿Cuál es la complejidad en tiempo de ejecución de calcular una asignación proporcional conectada de torta parcialmente quemada?
Casos conocidos:
- Cuando todas las valoraciones son positivas o todas las valoraciones son negativas, el protocolo Even-Paz encuentra una división proporcional conectada utilizando consultas, y esto es óptimo.
- Cuando se pueden mezclar valoraciones, se puede utilizar un protocolo de cuchilla móvil para encontrar una división proporcional conectada utilizando consultas. [8] : Thm.5 ¿Se puede mejorar para ?
Se garantiza que existe una división sin envidia de una torta parcialmente quemada si, y solo si, el número de agentes es la potencia de un número entero primo. [9] Sin embargo, no se puede encontrar mediante un protocolo finito, solo se puede aproximar. Dado un pequeño número positivo D , una asignación se llama D -sin envidia si, para cada agente, la asignación se convertirá en libre de envidia si movemos los cortes como máximo D (unidades de longitud).
- ¿Cuál es la complejidad en tiempo de ejecución (en función de D) de calcular una asignación sin envidia D conectada de una torta parcialmente quemada? [7]
Corte de pastel veraz
El corte de pasteles veraz es el diseño de mecanismos veraces para un corte de pastel justo. Los algoritmos actualmente conocidos y los resultados de imposibilidad se muestran aquí . Los principales casos en los que se desconoce si existe un mecanismo equitativo veraz determinista son: [10]
- Hay 3 o más agentes con valoraciones uniformes por partes , sin libre disposición.
- Existen 2 o más agentes con valoraciones constantes a trozos , con o sin libre disposición (y sin requisitos adicionales como conectividad o no despilfarro).
Problemas abiertos en la asignación justa de elementos indivisibles.
El 1 demaximin share (MMS) de un agente es la utilidad más grande que el agente puede asegurar al dividir los elementos enpaquetes y recibir el peor paquete. Para dos agentes, dividir y elegir le da a cada agente al menos su 1 de 2 MMS. Para agentes, casi siempre, pero no siempre, es posible dar a cada agente su 1 deMMS. Esto plantea varios tipos de preguntas.
1. Complejidad computacional
¿Cuál es la complejidad en tiempo de ejecución de decidir si una instancia dada admite un 1 de¿Asignación de MMS? [11] [12]
- Límite superior: (cual es - nivel 2 en la jerarquía polinomial )
- Límite inferior: ninguno (por lo que puede ser el nivel 2 o 1 o incluso 0 de la jerarquía).
NOTA: se sabe que los siguientes problemas relacionados son difíciles de calcular:
- Calcular el 1 deEl MMS de un agente dado es NP-hard incluso si todos los agentes tienen preferencias aditivas (reducción del problema de partición ).
- Decidir si una asignación dada es 1 deMMS es co-NP completo para agentes con preferencias adicionales.
2. Aproximación cardinal
- ¿Cuál es la fracción más grande r tal que siempre exista una asignación que le dé a cada agente una utilidad de al menos r veces su 1 de maximin share?
Casos conocidos:
- Para dos agentes: por dividir y elegir.
- Para tres agentes, incluso con valoraciones aditivas: . Con un ejemplo cuidadosamente elaborado. [13]
- Para cualquier número de agentes con valoraciones aditivas: . [14]
- Para cualquier número de agentes con valoraciones negativas aditivas (es decir, para tareas domésticas):. [15]
3. Aproximación ordinal
- ¿Cuál es el número entero más pequeño? (como una función de ) tal que siempre exista una asignación entre agentes dando a cada agente al menos su 1 de MMS?
Casos conocidos:
- Para dos agentes: . Por dividir y elegir .
- Para cualquier número de agentes con valoraciones binarias: . Por turnos. Da EF1, lo que implica 1 de-MMS.
- Para agentes: . Con un ejemplo cuidadosamente elaborado. [13]
- Para cualquier número de agentes con valoraciones aditivas: , por turnos. Da EF1, lo que implica 1 de-MMS.
- Para cualquier número de agentes con valoraciones aditivas: , utilizando la combinación sin envidia . [dieciséis]
Entonces la respuesta puede ser cualquier cosa entre y , inclusive. Caso abierto más pequeño:
- Para agentes con valoraciones aditivas, ¿existe siempre una asignación de acciones maximin de 1 de 5?
Nota: siempre existe un equilibrio competitivo aproximado de ingresos iguales que garantiza el 1 de () maximin-share. [17] Sin embargo, esta asignación puede tener un exceso de oferta y, lo que es más importante, un exceso de demanda: la suma de los paquetes asignados a todos los agentes puede ser ligeramente mayor que el conjunto de todos los elementos. Este error es razonable cuando se asignan plazas de curso entre estudiantes, ya que un pequeño exceso de oferta puede corregirse añadiendo una pequeña cantidad de plazas. Pero el problema clásico de la división justa supone que no se pueden agregar elementos.
Sin envidia hasta un artículo
Una asignación se llama EF1 (sin envidia hasta un artículo) si, para dos agentes cualesquiera y , y para cualquier subconjunto de tamaño como máximo uno contenido en el paquete de , si eliminamos ese subconjunto de entonces el paquete no tiene envidia. Una asignación de EF1 siempre existe y se puede encontrar mediante el algoritmo de ciclos de envidia . Combinarlo con otras propiedades plantea algunas preguntas abiertas.
Asignación EF1 óptima de Pareto (buenos y malos)
Cuando todos los artículos son buenos y todas las valoraciones son aditivas, siempre existe un PO + EF1: la asignación que maximiza el producto de las utilidades es PO + EF1. [18] Encontrar esta asignación maximizadora es NP-difícil, [19] pero en teoría, puede ser posible encontrar otras asignaciones PO + EF1 (sin maximizar el producto).
¿Cuál es la complejidad en tiempo de ejecución de encontrar una asignación de bienes PO + EF1 ?
No se sabe que exista una asignación PO + EF1 de malas (tareas) , incluso cuando todas las valoraciones son aditivas.
¿Existe siempre una asignación de defectos PO + EF1 ?
¿Cuál es la complejidad en tiempo de ejecución de encontrar dicha asignación, si existe?
Asignación de EF1 contigua
A menudo, los productos se ordenan en una línea, por ejemplo, casas en una calle. Cada agente quiere obtener un bloque contiguo. [20]
- Para tres o más agentes con valoraciones aditivas, ¿existe siempre una asignación EF1?
Casos conocidos:
- Para dos agentes con valoraciones aditivas, la respuesta es sí: podemos redondear un corte de pastel sin envidia conectado (p. Ej., Hallado por dividir y elegir ).
- Para agentes con valoraciones aditivas, podemos encontrar una asignación "EF menos 2" redondeando un corte de pastel sin envidia conectado, y también existe una asignación EF2 (prueba usando una variante del lema de Sperner ). [21]
- Para agentes con valoraciones binarias aditivas (el valor de cada elemento es 0 o 1), una asignación "EF menos 2" también es EF1, por lo que la respuesta es sí .
Incluso cuando existe una asignación de EF1 contigua, la complejidad del tiempo de ejecución de encontrarla no está clara:
- Para tres o más agentes con valoraciones aditivas binarias, ¿cuál es la complejidad de encontrar una asignación EF1 contigua?
- Un corte de pastel conectado sin envidia puede requerir infinitas consultas para encontrarlo. Una asignación EF1 siempre se puede encontrar en tiempo finito al verificar todas las asignaciones posibles, pero este algoritmo requiere un tiempo de ejecución exponencial.
Precio de la justicia
El precio de la equidad es la relación entre el bienestar social máximo (suma de los servicios públicos) en cualquier asignación y el bienestar social máximo en una asignación justa. ¿Cuál es el precio de la equidad EF1?
- El límite superior es - por Round-robin o por el máximo bienestar de Nash.
- El límite inferior es . [22] : sección 1.1
Existencia de asignación EFx
Una asignación se llama EFx ("sin envidia hasta cualquier bien") si, para dos agentes cualesquiera y , y para cualquier bien en el paquete de , si quitamos ese bien de entonces el paquete no tiene envidia. [23]
- Para tres agentes con valoraciones aditivas, ¿existe siempre una asignación EFx?
- Para agentes con valoraciones generales monótonas, ¿podemos demostrar que no existe una asignación EFx?
Casos conocidos:
- Si al menos las valoraciones son idénticas: sí.
- Por lo tanto, para dos agentes: sí. Esto es cierto incluso para valoraciones monótonas generales. [24]
- Para tres agentes: sí, por un documento de trabajo reciente. [25]
Existencia de asignación PROPx Pareto-eficiente de males
Una asignación de males se llama PROPx (también conocido como FSx) [26] : Sec.7 si, para cualquier agente, y por cualquier mal propiedad de , si quitamos ese mal de paquete, entonces La desutilidad es menor que la total desutilidad.
¿Existe siempre una asignación de males que sea PROPx y Pareto eficiente?
Casos conocidos relacionados:
- Es posible que no exista una asignación PROPx de bienes (incluso sin la eficiencia de Pareto).
- Siempre existe una asignación PROPx de males (sin eficiencia de Pareto).
- Un PROP1 y asignación Pareto-eficiente de los bienes o males siempre existe.
Equilibrio competitivo para casi todos los ingresos
El equilibrio competitivo (EC) es una noción de equidad muy fuerte: implica optimismo de Pareto y ausencia de envidia. Cuando los ingresos son iguales, la CE puede no existir incluso cuando hay dos agentes y un bien. Pero, en todos los demás espacios de ingresos, la CE existe cuando hay dos agentes y un bien. En otras palabras, existe un equilibrio competitivo para casi todos los vectores de ingresos.
- Para dos agentes con valoraciones aditivas sobre cualquier número de bienes, ¿existe un equilibrio competitivo para casi ingresos? [27]
Casos conocidos:
- Con tres o menos mercancías: siempre sí .
- Con cuatro bienes: sí para 2 agentes con valoraciones generales, no para 3 agentes con valoraciones generales, no para 4 agentes, incluso con valoraciones aditivas. [28]
- Con cinco o más mercancías: no para dos agentes con valoraciones generales.
Conjeturas abiertas:
- Cuando hay dos agentes con valoraciones aditivas , la CE para casi todos los ingresos existe para cualquier número de bienes.
- Cuando hay tres agentes, incluso con valoraciones aditivas, es posible que no exista CE para casi todos los ingresos.
División equitativa de elementos parcialmente divisibles
Complejidad en tiempo de ejecución de la asignación justa con uso compartido limitado
Dado agentes, elementos y un entero , suponga como mucho Los elementos se pueden compartir entre dos o más agentes. ¿Cuál es la complejidad en tiempo de ejecución de decidir si existe una asignación proporcional / libre de envidia?
Casos conocidos:
- Con y valoraciones idénticas, para cualquier , el problema es equivalente al problema de la partición y, por lo tanto, es NP-completo.
- Con , la respuesta es siempre "sí" y se puede encontrar una asignación en tiempo polinomial. [29]
- Con y y valoraciones idénticas, se puede encontrar una asignación en tiempo polinomial si existe. [30]
Casos abiertos más pequeños:
- y y diferentes valoraciones.
- y y valoraciones idénticas.
Referencias
- ^ Procaccia, Ariel (2009). "Codiciarás el pastel de tu prójimo" . IJCAI'09 Actas de la 21ª Conferencia Internacional Conjunta sobre Inteligencia Artificial : 239–244.
- ^ a b c Aziz, Haris; MacKenzie, Simon (2016). "Un protocolo de corte de pastel discreto y limitado sin envidia para cualquier número de agentes". FOCS 2016 . arXiv : 1604.03655 . Código bibliográfico : 2016arXiv160403655A .
- ^ a b Segal-Halevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (19 de noviembre de 2016). "Los residuos se apresuran". Transacciones ACM sobre algoritmos . 13 (1): 1–32. arXiv : 1511.02599 . doi : 10.1145 / 2988232 . ISSN 1549-6325 .
- ^ Stromquist, Walter (2008). "Las divisiones de pastel sin envidia no se pueden encontrar mediante protocolos finitos" (PDF) . Revista electrónica de combinatoria .
- ^ a b Segal-Halevi, Erel (2019). "Pastel de corte con diferentes derechos: ¿cuántos cortes se necesitan?". Revista de Análisis y Aplicaciones Matemáticas . 480 : 123382. arXiv : 1803.05470 . doi : 10.1016 / j.jmaa.2019.123382 .
- ^ Tripulación, Logan; Narayanan, Bhargav; Spirkl, Sophie (16 de septiembre de 2019). "División desproporcionada". arXiv : 1909.07141 [ math.CO ].
- ^ a b Segal-Halevi, Erel (2018). "División justa de un pastel después de que algunas partes se quemaron en el horno" . Actas de la XVII Conferencia Internacional sobre Agentes Autónomos y Sistemas MultiAgent . AAMAS '18. Richland, SC: Fundación Internacional para Agentes Autónomos y Sistemas Multiagente: 1276–1284. arXiv : 1704.00726 . Código bibliográfico : 2017arXiv170400726S .
- ^ Aziz, Haris; Caragiannis, Ioannis; Igarashi, Ayumi; Walsh, Toby (27 de julio de 2018). "Asignación justa de combinaciones de bienes y tareas indivisibles". arXiv : 1807.10684 [ cs.GT ].
- ^ Avvakumov, Sergey; Karasev, Roman (25 de julio de 2019). "División sin envidia mediante grado de mapeo". arXiv : 1907.11183 [ math.AT ].
- ^ Bei, Xiaohui; Huzhang, Guangda; Suksompong, Warut (18 de abril de 2018). "División justa veraz sin libre disposición". arXiv : 1804.06923 [ cs.GT ].
- ^ Bouveret, Sylvain; Lemaître, Michel (1 de marzo de 2016). "Caracterización de los conflictos en la justa división de bienes indivisibles utilizando una escala de criterios". Agentes autónomos y sistemas multiagente . 30 (2): 259–290. doi : 10.1007 / s10458-015-9287-3 . ISSN 1573-7454 .
- ^ Lang, Jérôme; Rothe, Jörg (2016), Rothe, Jörg (ed.), "División justa de bienes indivisibles", Economía y computación: Introducción a la teoría algorítmica de juegos, Elección social computacional y División justa , Springer Texts in Business and Economics, Springer Berlín Heidelberg, págs. 493–550, doi : 10.1007 / 978-3-662-47904-9_8 , ISBN 9783662479049
- ^ a b Kurokawa, David; Procaccia, Ariel D .; Wang, Junxing (1 de febrero de 2018). "Suficientemente justo: Garantizar acciones aproximadas de Maximin". J. ACM . 65 (2): 8: 1–8: 27. doi : 10.1145 / 3140756 . ISSN 0004-5411 .
- ^ Ghodsi, Mohammad; Hajiaghayi, Mohammadtaghi; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi (2018). "Asignación equitativa de bienes indivisibles: mejoras y generalizaciones" . Actas de la Conferencia ACM 2018 sobre Economía y Computación . EC '18. Nueva York, NY, EE. UU.: ACM: 539–556. doi : 10.1145 / 3219166.3219238 . ISBN 9781450358293.
- ^ Huang, Xin; Lu, Pinyan (10 de julio de 2019). "Un marco algorítmico para aproximar la asignación de acciones maximin de tareas". arXiv : 1907.04505 [ cs.GT ].
- ^ Aigner-Horev, Elad; Segal-Halevi, Erel (28 de enero de 2019). "Emparejamientos sin envidia en gráficos bipartitos y sus aplicaciones a la división justa". arXiv : 1901.09527 [ cs.DS ].
- ^ Budish, Eric (2011). "El problema de asignación combinatoria: equilibrio competitivo aproximado de ingresos iguales". Revista de Economía Política . 119 (6): 1061-1103. CiteSeerX 10.1.1.144.7992 . doi : 10.1086 / 664613 .
- ^ Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D .; Shah, Nisarg; Wang, Junxing (24 de septiembre de 2019). "La equidad irrazonable del máximo bienestar de Nash" (PDF) . Transacciones ACM en Economía y Computación . 7 (3): 1–32. doi : 10.1145 / 3355902 . ISSN 2167-8375 .
- ^ Darmann, Andreas; Schauer, Joachim (1 de diciembre de 2015). "Maximización del bienestar social del producto Nash en la asignación de bienes indivisibles". Revista europea de investigación operativa . 247 (2): 548–559. doi : 10.1016 / j.ejor.2015.05.071 . ISSN 0377-2217 .
- ^ Suksompong, Warut (15 de mayo de 2019). "Asignación justa de bloques contiguos de elementos indivisibles". Matemáticas aplicadas discretas . 260 : 227-236. arXiv : 1707.00345 . doi : 10.1016 / j.dam.2019.01.036 . ISSN 0166-218X .
- ^ Bilò, Vittorio; Caragiannis, Ioannis; Flammini, Michele; Igarashi, Ayumi; Mónaco, Gianpiero; Peters, Dominik; Vinci, Cosimo; Zwicker, William S. (28 de agosto de 2018). "Asignaciones casi libres de envidia con paquetes conectados". arXiv : 1808.09406 [ cs.GT ].
- ^ Bei, Xiaohui; Lu, Xinhang; Manurangsi, Pasin; Suksompong, Warut (13 de mayo de 2019). "El precio de la equidad para los bienes indivisibles". arXiv : 1905.04910 [ cs.GT ].
- ^ Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D .; Shah, Nisarg; Wang, Junxing (24 de septiembre de 2019). "La equidad irrazonable del máximo bienestar de Nash" (PDF) . Transacciones ACM en Economía y Computación . 7 (3): 1–32. doi : 10.1145 / 3355902 . ISSN 2167-8375 .
- ^ Plaut, Benjamín; Roughgarden, Tim (2018). "Casi libre de envidia con valoraciones generales" . Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos . SODA '18. Filadelfia, Pensilvania, EE. UU.: Sociedad de Matemáticas Industriales y Aplicadas: 2584–2603. arXiv : 1707.04769 . Código Bib : 2017arXiv170704769P . doi : 10.1137 / 1.9781611975031.165 . ISBN 9781611975031.
- ^ Chaudhury, Bhaskar Ray; Garg, Jugal; Mehlhorn, Kurt (14 de febrero de 2020). "EFX existe para tres agentes". arXiv : 2002.05119 [ cs.GT ].
- ^ Moulin, Hervé (2019). "División justa en la era de Internet". Revisión anual de economía . 11 (1): 407–441. doi : 10.1146 / annurev-economics-080218-025559 .
- ^ Babaioff, Moshe; Nisan, Noam; Talgam-Cohen, Inbal (23 de marzo de 2017). "Equilibrio competitivo con bienes indivisibles y presupuestos genéricos". arXiv : 1703.08150 [ cs.GT ].
- ^ Segal-Halevi, Erel (11 de mayo de 2017). "Equilibrio competitivo para casi todos los ingresos". arXiv : 1705.04212 [ cs.GT ].
- ^ Sandomirskiy, Fedor; Segal-Halevi, Erel (5 de agosto de 2019). "División justa con participación mínima". arXiv : 1908.01669 [ cs.GT ].
- ^ "Dureza np: un problema de partición en el que se pueden cortar algunos números" . Intercambio de pilas de informática teórica . Consultado el 21 de octubre de 2019 .