La asignación equitativa de artículos es una especie de problema de división equitativa en el que los artículos a dividir son discretos en lugar de continuos. Los artículos deben dividirse entre varios socios que los valoren de manera diferente, y cada artículo debe entregarse en su totalidad a una sola persona. Esta situación surge en varios escenarios de la vida real:
- Varios herederos quieren dividir la propiedad heredada, que contiene, por ejemplo, una casa, un automóvil, un piano y varios cuadros.
- Varios profesores quieren dividir los cursos impartidos en su facultad. Cada profesor puede impartir uno o más cursos completos.
La indivisibilidad de los elementos implica que tal vez no sea posible una división justa. Como ejemplo extremo, si hay un solo artículo (por ejemplo, una casa), se debe entregar a un solo socio, pero esto no es justo para los demás socios. Esto contrasta con el problema de la tarta justa , donde el dividendo es divisible y siempre existe una división justa. En algunos casos, el problema de la indivisibilidad puede mitigarse introduciendo pagos monetarios o rotaciones temporales , o descartando algunos de los elementos. [1] : 285 Pero estas soluciones no siempre están disponibles.
Un problema de asignación de artículos tiene varios ingredientes:
- Los socios deben expresar sus preferencias por los diferentes paquetes de artículos.
- El grupo debe decidir sobre un criterio de equidad .
- Según las preferencias y el criterio de equidad, se debe ejecutar un algoritmo de asignación equitativa para calcular una división equitativa.
Estos ingredientes se explican en detalle a continuación.
Preferencias
Preferencias combinatorias
Una forma ingenua de determinar las preferencias es pedirle a cada socio que proporcione un valor numérico para cada paquete posible. Por ejemplo, si los elementos a dividir son un automóvil y una bicicleta, un socio puede valorar el automóvil en 800, la bicicleta en 200 y el paquete {automóvil, bicicleta} en 900 (consulte Funciones de utilidad en bienes indivisibles para obtener más ejemplos). . Hay dos problemas con este enfoque:
- Puede ser difícil para una persona calcular valores numéricos exactos para los paquetes.
- La cantidad de paquetes posibles puede ser enorme: si hay entonces hay elementos posibles paquetes. Por ejemplo, si hay 16 elementos, cada socio deberá presentar sus preferencias utilizando números 65536.
El primer problema motiva el uso de la utilidad ordinal en lugar de la utilidad cardinal . En el modelo ordinal, cada socio solo debe expresar una clasificación sobre eldiferentes paquetes, es decir, decir qué paquete es el mejor, cuál es el segundo mejor, etc. Esto puede ser más fácil que calcular números exactos, pero sigue siendo difícil si la cantidad de elementos es grande.
El segundo problema a menudo se resuelve trabajando con elementos individuales en lugar de paquetes:
- En el enfoque cardinal, cada socio debe informar una valoración numérica para cada artículo;
- En el enfoque ordinal, cada socio debe informar una clasificación sobre los elementos, es decir, decir qué elemento es el mejor, cuál es el segundo mejor, etc.
Bajo supuestos adecuados, es posible elevar las preferencias sobre los artículos a las preferencias sobre los paquetes. [2] : 44–48 Luego, los agentes informan sus valoraciones / clasificaciones sobre elementos individuales y el algoritmo calcula para ellos sus valoraciones / clasificaciones en paquetes.
Preferencias aditivas
Para simplificar el problema de asignación de artículos, es común suponer que todos los artículos son bienes independientes (por lo que no son bienes sustitutos ni complementarios ). [3] Entonces:
- En el enfoque cardinal, cada agente tiene una función de utilidad aditiva (también llamada: función de utilidad modular ). Una vez que el agente informa un valor para cada artículo individual, es fácil calcular el valor de cada paquete sumando los valores de sus artículos.
- En el enfoque ordinal, la aditividad nos permite inferir algunas clasificaciones entre paquetes. Por ejemplo, si una persona prefiere w axay y z, entonces necesariamente prefiere {w, x} a {w, y} o {x, y} y {w, y} a {x}. Esta inferencia es solo parcial, por ejemplo, no podemos saber si el agente prefiere {w} a {x, y} o incluso {w, z} a {x, y}. [4] [5]
La aditividad implica que cada socio siempre puede elegir un "elemento preferible" del conjunto de elementos en la mesa, y esta elección es independiente de los otros elementos que el socio pueda tener. Esta propiedad es utilizada por algunos algoritmos de asignación justa que se describirán a continuación. [1] : 287–288
Idiomas de representación de preferencias compactos
Los lenguajes de representación de preferencias compactos se han desarrollado como un compromiso entre la expresividad total de las preferencias combinatorias y la simplicidad de las preferencias aditivas. Proporcionan una representación sucinta de algunas clases naturales de funciones de utilidad que son más generales que las utilidades aditivas (pero no tan generales como las utilidades combinatorias). Algunos ejemplos son: [1] : 289–294
- 2-preferencias aditivas : cada socio informa un valor para cada paquete de tamaño como máximo 2. El valor de un paquete se calcula sumando los valores de los artículos individuales en el paquete y sumando los valores de los pares en el paquete. Normalmente, cuando hay elementos sustitutos, los valores de los pares serán negativos y cuando hay elementos complementarios, los valores de los pares serán positivos. Esta idea se puede generalizar a k preferencias aditivas para cada entero positivo k .
- Modelos gráficos : para cada socio, hay un gráfico que representa las dependencias entre diferentes elementos. En el enfoque cardinal, una herramienta común es la red GAI (Independencia aditiva generalizada). En el enfoque ordinal, una herramienta común es la red CP (preferencias condicionales) y sus extensiones: red TCP , red UCP , teoría CP , red CI (importancia condicional) y red SCI (una simplificación de red CI).
- Lenguajes basados en lógica : cada socio describe algunos paquetes utilizando una fórmula lógica de primer orden y puede asignar un valor para cada fórmula. Por ejemplo, un socio puede decir: "Para (x o (y y z)), mi valor es 5". Esto significa que el agente tiene un valor de 5 para cualquiera de los paquetes: x, xy, xz, yz, xyz.
- Lenguajes de licitación : se han estudiado muchos lenguajes para representar preferencias combinatorias en el contexto de subastas combinatorias . Algunos de estos idiomas se pueden adaptar a la configuración de asignación de elementos.
Criterios de equidad
Criterios de garantía individual
Un criterio de garantía individual es un criterio que debe ser válido para cada socio individual, siempre que el socio informe verazmente sus preferencias. A continuación se presentan cinco de estos criterios. Están ordenados del más débil al más fuerte (asumiendo que las valoraciones son aditivas): [6]
El maximin-share (también llamado: garantía max-min-fair-share) de un agente es el paquete más preferido que podría garantizarse a sí mismo como divisor en dividir y elegir contra oponentes adversarios. Una asignación se llama MMS-fair si cada agente recibe un paquete que prefiere débilmente sobre su MMS. [7]
La parte justa proporcional de un agente es 1 / n de su utilidad de todo el conjunto de elementos. Una asignación se llama proporcional si cada agente recibe un paquete que vale al menos su parte justa proporcional.
La participación equitativa mínima-máxima de un agente es la utilidad mínima que puede esperar obtener de una asignación si todos los demás agentes tienen las mismas preferencias que ella, cuando ella siempre recibe la mejor participación. También es la utilidad mínima que un agente puede obtener con seguridad en el juego de asignación "Alguien corta, yo elijo primero". Una asignación es mFS-justa si todos los agentes reciben un paquete que prefieren débilmente sobre su mFS. [6] La equidad de mFS puede describirse como el resultado del siguiente proceso de negociación. Se sugiere una cierta asignación. Cada agente puede oponerse a ello exigiendo que otro agente realice una asignación diferente, dejándolo elegir primero. Por lo tanto, un agente se opondría a una asignación solo si en todas las particiones hay un paquete que prefiere mucho sobre su paquete actual. Una asignación es mFS-justa si ningún agente se opone a ella, es decir, para cada agente existe una partición en la que todos los paquetes son débilmente peores que su participación actual.
Para cada agente con utilidad subaditiva , el mFS vale al menos . Por lo tanto, cada asignación equitativa de mFS es proporcional. Para cada agente con utilidad superaditiva , el MMS vale como máximo . Por lo tanto, toda asignación proporcional es justa en MMS. Ambas inclusiones son estrictas, incluso cuando cada agente tiene una utilidad aditiva . Esto se ilustra en el siguiente ejemplo: [6]
- Hay 3 agentes y 3 elementos:
- Alice valora los elementos como 2,2,2. Para ella, MMS = PFS = mFS = 2.
- Bob valora los elementos como 3,2,1. Para él, MMS = 1, PFS = 2 y mFS = 3.
- Carl valora los elementos como 3,2,1. Para él, MMS = 1, PFS = 2 y mFS = 3.
- Las posibles asignaciones son las siguientes:
- Cada asignación que le da un artículo a cada agente es justa para MMS.
- Cada asignación que le da el primer y segundo artículo a Bob y Carl y el tercer artículo a Alice es proporcional.
- Ninguna asignación es justa para mFS.
- Hay 3 agentes y 3 elementos:
Las implicaciones anteriores no son válidas cuando las valoraciones de los agentes no son sub / superaditivas. [8]
Libre de envidia (EF)
Cada agente prefiere débilmente su propio paquete a cualquier otro paquete. Cada asignación libre de envidia de todos los elementos es mFS-justa; esto se deriva directamente de las definiciones ordinales y no depende de la aditividad. Si las valoraciones son aditivas, entonces una asignación EF también es proporcional y justa en MMS. De lo contrario, una asignación de EF puede no ser proporcional e incluso no MMS. [8] Consulte la asignación de artículos sin envidia para obtener más detalles.
Equilibrio competitivo de la igualdad de ingresos (CEEI)
Este criterio se basa en el siguiente argumento: el proceso de asignación debe ser considerado como la búsqueda de un equilibrio entre la oferta (el conjunto de objetos, cada uno con un precio público) y la demanda (los deseos de los agentes, cada agente tiene el mismo presupuesto para la compra de los objetos). Se alcanza un equilibrio competitivo cuando la oferta coincide con la demanda. El argumento de la equidad es sencillo: los precios y los presupuestos son los mismos para todos. CEEI implica EF independientemente de la aditividad. Cuando las preferencias de los agentes son aditivas y estrictas (cada paquete tiene un valor diferente), CEEI implica eficiencia de Pareto . [6]
Varios criterios de equidad sugeridos recientemente son: [9]
Envidia-libre-excepto-1 (EF1)
Para cada dos agentes A y B, si quitamos del paquete de B el artículo más valioso para A, entonces A no envidia a B (en otras palabras, el "nivel de envidia" de A en B es como máximo el valor de a objeto unico). Bajo monotonicidad, siempre existe una asignación EF1.
Envidia-libre-excepto-más-barato (EFx)
Para cada dos agentes A y B, si eliminamos del paquete de B el elemento menos valioso para A, entonces A no envidia a B. EFx es estrictamente más fuerte que EF1. No se sabe si siempre existen asignaciones EFx.
Criterios de optimización global
Un criterio de optimización global evalúa una división en función de una función de bienestar social determinada :
- El bienestar social igualitario es la mínima utilidad de un solo agente. Una asignación de elementos se denomina igualitaria-óptima si alcanza el máximo bienestar igualitario posible, es decir, maximiza la utilidad del agente más pobre. Dado que puede haber varias asignaciones diferentes que maximizan la utilidad más pequeña, la optimalidad igualitaria a menudo se refina a leximin-optimalidad : desde el subconjunto de asignaciones que maximizan la utilidad más pequeña, selecciona aquellas asignaciones que maximizan la segunda utilidad más pequeña, luego la tercera utilidad más pequeña. , y así.
- El bienestar social de Nash es producto de las utilidades de los agentes. Una asignación llama Nash-óptima o máxima-Nash-Bienestar si maximiza el producto de servicios públicos. Las asignaciones óptimas de Nash tienen algunas propiedades de equidad agradables. [9]
Una ventaja de los criterios de optimización global sobre los criterios individuales es que las asignaciones que maximizan el bienestar son Pareto eficientes .
Algoritmos de asignación
Varios algoritmos para la asignación de artículos justos se analizan en páginas sobre criterios de equidad específicos:
- Asignación de partidas maximin-share ;
- Asignación proporcional de artículos ;
- Asignación de elementos compartidos por Minimax: el problema de calcular la mFS de un agente es coNP-completo . El problema de decidir si existe una asignación de mFS está en, pero aún se desconoce su complejidad computacional exacta. [6]
- Asignación de artículos sin envidia ;
- Asignación igualitaria de artículos ;
- Asignación óptima de Nash: [10] y [11] demuestran la dificultad de calcular las asignaciones óptimas de Nash y utilitaristas. [12] presentan un procedimiento de aproximación para las asignaciones óptimas de Nash.
- Secuencia de selección : un protocolo simple en el que los agentes se turnan para seleccionar elementos, basándose en una secuencia de turnos preespecificada. El objetivo es diseñar la secuencia de selección de una manera que maximice el valor esperado de una función de bienestar social (por ejemplo, igualitaria o utilitaria) bajo algunos supuestos probabilísticos sobre las valoraciones de los agentes.
- Equilibrio competitivo: varios algoritmos para encontrar una asignación de CE se describen en el artículo sobre el mercado de Fisher .
Variantes y ampliaciones
Diferentes derechos
En esta variante, diferentes agentes tienen derecho a diferentes fracciones del recurso. Un caso de uso común es dividir los ministerios del gabinete entre los partidos de la coalición. Es común suponer que cada partido debe recibir ministerios de acuerdo con el número de escaños que tiene en el parlamento. Las diversas nociones de equidad deben adaptarse en consecuencia. Consulte [13] y [14] y [15] para obtener información sobre este problema y algunas soluciones.
Asignación a grupos
En esta variante, los paquetes no se dan a agentes individuales sino a grupos de agentes. Los casos de uso comunes son: dividir la herencia entre familias o dividir las instalaciones entre los departamentos de una universidad. Todos los agentes del mismo grupo consumen el mismo paquete, aunque pueden valorarlo de manera diferente. La configuración clásica de asignación de artículos corresponde al caso especial en el que todos los grupos son singleton.
Con los grupos, puede ser imposible garantizar una equidad unánime (equidad a los ojos de todos los agentes de cada grupo), por lo que a menudo se relaja la equidad democrática (equidad a los ojos de, por ejemplo, al menos la mitad de los agentes de cada grupo). [dieciséis]
Toma de decisiones públicas
En esta variante, varios agentes deben aceptar decisiones sobre varios temas. Un caso de uso común es una familia que tiene que decidir qué actividad hacer cada día (cada problema es un día). Cada agente asigna diferentes utilidades a las distintas opciones de cada tema. La configuración clásica de asignación de artículos corresponde al caso especial en el que cada emisión corresponde a un artículo, cada opción de decisión corresponde a entregar ese artículo a un agente en particular, y las utilidades de los agentes son cero para todas las opciones en las que el artículo se entrega a alguien. demás. En este caso, proporcionalidad significa que la utilidad de cada agente es al menos 1 / n de su "utilidad de dictadura", es decir, la utilidad que podría obtener eligiendo la mejor opción en cada tema. La proporcionalidad puede ser inalcanzable, pero PROP1 se puede lograr mediante la asignación de elementos por turnos . [17]
Ver también
- Problema de cobertura de contenedores y problema de embalaje de contenedores : dos problemas de optimización bien estudiados que pueden verse como casos especiales de asignación de bienes indivisibles y asignación de tareas indivisibles , respectivamente. Muchas técnicas utilizadas para estos problemas también son útiles en el caso de la asignación justa de artículos.
- Experimentos de división justa , incluidos algunos estudios de casos y experimentos de laboratorio relacionados con la asignación de artículos justos.
- Armonía de alquiler : un problema de división equitativa en el que los elementos indivisibles y un costo total fijo deben dividirse simultáneamente.
- Precio de equidad : una medida general de la compensación entre equidad y eficiencia, con algunos resultados sobre la configuración de asignación de elementos.
- Problema de suma justa de subconjuntos
Referencias
- ^ a b c Sylvain Bouveret y Yann Chevaleyre y Nicolas Maudet, "Asignación justa de bienes indivisibles". Capítulo 12 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 )
- ^ Barberà, S .; Bossert, W .; Pattanaik, PK (2004). "Clasificación de conjuntos de objetos". (PDF) . Manual de teoría de la utilidad . Springer EE. UU.
- ^ Sylvain Bouveret; Ulle Endriss; Jérôme Lang (2010). División justa bajo preferencias ordinales: cálculo de asignaciones libres de envidia de bienes indivisibles . Actas de la conferencia de 2010 sobre ECAI 2010: XIX Conferencia europea sobre inteligencia artificial . Consultado el 26 de agosto de 2016 .
- ^ Brams, Steven J .; Edelman, Paul H .; Fishburn, Peter C. (2003). "División justa de ítems indivisibles". Teoría y Decisión . 55 (2): 147. doi : 10.1023 / B: THEO.0000024421.85722.0a . S2CID 153943630 .
- ^ Brams, SJ (2005). "División justa eficiente: ¿ayudar a los peores o evitar la envidia?". Racionalidad y Sociedad . 17 (4): 387–421. CiteSeerX 10.1.1.118.9114 . doi : 10.1177 / 1043463105058317 . S2CID 154808734 .
- ^ a b c d e Bouveret, Sylvain; Lemaître, Michel (2015). "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. doi : 10.1007 / s10458-015-9287-3 . S2CID 16041218 .
- ^ Budish, E. (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.357.9766 . doi : 10.1086 / 664613 . S2CID 154703357 .
- ^ a b Heinen, Tobías; Nguyen, Nhan-Tam; Rothe, Jörg (2015). "Equidad y utilitarismo ponderado por rango en la asignación de recursos". Teoría de la decisión algorítmica . Apuntes de conferencias en informática. 9346 . pag. 521. doi : 10.1007 / 978-3-319-23114-3_31 . ISBN 978-3-319-23113-6.
- ^ a b Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D .; Shah, Nisarg; Wang, Junxing (2016). La equidad irrazonable del máximo bienestar de Nash (PDF) . Actas de la Conferencia ACM 2016 sobre Economía y Computación - EC '16. pag. 305. doi : 10.1145 / 2940716.2940726 . ISBN 9781450339360.
- ^ Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "Una encuesta de resultados de aproximabilidad e inaproximación para la optimización del bienestar social en la asignación de recursos multiagente". Anales de Matemáticas e Inteligencia Artificial . 68 (1-3): 65-90. CiteSeerX 10.1.1.671.3497 . doi : 10.1007 / s10472-012-9328-4 . S2CID 6864410 .
- ^ Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "Complejidad computacional y aproximabilidad de la optimización del bienestar social en la asignación de recursos multiagente". Agentes autónomos y sistemas multiagente . 28 (2): 256. doi : 10.1007 / s10458-013-9224-2 . S2CID 442666 .
- ^ Trung Thanh Nguyen y Jörg Rothe (2013). Optimización del bienestar social del índice de envidia y del nash promedio en la asignación de recursos de múltiples agentes . AAMAS 13.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Brams, Steven J .; Kaplan, Todd R. (2004). "Dividiendo lo indivisible". Revista de política teórica . 16 (2): 143. doi : 10.1177 / 0951629804041118 . S2CID 154854134 .
- ^ 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 (9 de julio de 2018). "Equilibrio competitivo para casi todos los ingresos" . Actas de AAMAS 2018 . Aamas '18. Fundación Internacional de Agentes Autónomos y Sistemas Multiagente. págs. 1267-1275.
- ^ Segal-Halevi, Erel; Suksompong, Warut (1 de diciembre de 2019). "Asignación justa democrática de bienes indivisibles". Inteligencia artificial . 277 : 103167. arXiv : 1709.02564 . doi : 10.1016 / j.artint.2019.103167 . ISSN 0004-3702 . S2CID 203034477 .
- ^ Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2016). "Toma de decisiones públicas justas | Actas de la Conferencia ACM 2017 sobre economía y computación". arXiv : 1611.04034 . doi : 10.1145 / 3033274.3085125 . S2CID 30188911 . Cite journal requiere
|journal=
( ayuda )