Problema de división justa en el que los elementos a dividir son discretos en lugar de continuos
La asignación justa de artículos es una especie de problema de división justa en el que los artículos a dividir son discretos en lugar de continuos. Los artículos deben dividirse entre varios socios que potencialmente los valoran de manera diferente, y cada artículo debe entregarse en su totalidad a una sola persona. [1] 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 coche, 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.
- Fiestas de intercambio de regalos con elefantes blancos
La indivisibilidad de los elementos implica que puede que 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 del reparto justo del pastel , 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 rotación basada en el tiempo , o descartando algunos de los elementos. [2] : 285 Pero estas soluciones no siempre están disponibles.
Un problema de asignación de elementos tiene varios ingredientes:
- Los socios deben expresar sus preferencias sobre 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 justa para calcular una división justa.
Estos ingredientes se explican en detalle a continuación.
Preferencias
Preferencias combinatorias
Una forma ingenua de determinar las preferencias es pedir a cada socio que proporcione un valor numérico para cada paquete posible. Por ejemplo, si los artículos 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 resultar difícil para una persona calcular los valores numéricos exactos de los paquetes.
- El número de paquetes posibles puede ser enorme: si hay artículos, entonces hay paquetes posibles. Por ejemplo, si hay 16 elementos, cada socio deberá presentar sus preferencias utilizando 65536 números.
El primer problema motiva el uso de la utilidad ordinal en lugar de la utilidad cardinal . En el modelo ordinal, cada socio sólo debe expresar una clasificación sobre las diferentes cestas, es decir, decir qué cesta es la mejor, cuál es la segunda 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 suele solucionarse trabajando con elementos individuales en lugar de con 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 de 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 artículos a preferencias sobre paquetes. [3] : 44–48 Luego, los agentes informan sus valoraciones/clasificaciones sobre artículos individuales, y el algoritmo calcula para ellos sus valoraciones/clasificaciones sobre 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 ). [4]
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 a x a y a z, entonces necesariamente prefiere {w,x} a {w,y} o a {x,y}, y {w,y} a {x}. Esta inferencia es sólo parcial, por ejemplo, no podemos saber si el agente prefiere {w} a {x,y} o incluso {w,z} a {x,y}. [5] [6]
La aditividad implica que cada socio siempre puede elegir un "elemento preferible" del conjunto de elementos de la mesa, y esta elección es independiente de los demás elementos que pueda tener el socio. Esta propiedad es utilizada por algunos algoritmos de asignación justa que se describirán a continuación. [2] : 287–288
Lenguajes de representación de preferencias compactos
Los lenguajes compactos de representación de preferencias 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: [2] : 289–294
- Preferencias 2-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 del paquete y sumando los valores de los pares del 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 preferencias k-aditivas para cada entero positivo k .
- Modelos gráficos : para cada socio, existe 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 CP net (Preferencias condicionales) y sus extensiones: TCP net , UCP net , teoría CP , CI net (Importancia condicional) y SCI net (una simplificación de CI net).
- Lenguajes basados en lógica : cada socio describe algunos paquetes utilizando una fórmula lógica de primer orden y puede asignar un valor a cada fórmula. Por ejemplo, un compañero 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 oferta : 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 individuales
Un criterio de garantía individual es un criterio que debe ser válido para cada socio individual, siempre que el socio informe verazmente de sus preferencias. A continuación se presentan cinco de estos criterios. Están ordenados del más débil al más fuerte (suponiendo que las valoraciones sean aditivas): [7]
La participación máxima (también llamada: garantía de participación máxima-mínima) de un agente es el paquete preferido que podría garantizarse como divisor en divide y elige contra oponentes adversarios. Una asignación se denomina MMS justa si cada agente recibe un paquete que prefiere débilmente a su MMS. [8]
La parte proporcional equitativa de un agente es 1/ n de su utilidad del conjunto completo de elementos. Una asignación se llama proporcional si cada agente recibe un paquete que vale al menos su parte justa proporcional.
Participación justa mínima y máxima (mFS)
La participación justa 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 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 justa para mFS si todos los agentes reciben un paquete que prefieren débilmente a su mFS. [7] La equidad mFS se puede describir 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 haga una asignación diferente, dejándole elegir primero. Por lo tanto, un agente se opondría a una asignación sólo si en todas las particiones hay una cesta que prefiere claramente sobre su cesta 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 ligeramente peores que su participación actual.
Por cada agente con utilidad subaditiva , el mFS vale al menos . Por lo tanto, cada asignación justa de mFS es proporcional. Por cada agente con utilidad superaditiva , el MMS vale como máximo . Por lo tanto, toda asignación proporcional es justa para MMS. Ambas inclusiones son estrictas, aun cuando cada agente tiene utilidad aditiva . Esto se ilustra en el siguiente ejemplo: [7]
- Hay tres agentes y tres 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 otorga un artículo a cada agente es justa para MMS.
- Cada asignación que da el primer y segundo elemento a Bob y Carl y el tercer elemento a Alice es proporcional.
- Ninguna asignación es justa para mFS.
Las implicaciones anteriores no se cumplen cuando las valoraciones de los agentes no son sub/superaditivas. [9]
Cada agente prefiere débilmente su propio paquete a cualquier otro paquete. Cada asignación libre de envidia de todos los artículos es justa para mFS; esto se sigue directamente de las definiciones ordinales y no depende de la aditividad. Si las valoraciones son aditivas, entonces una asignación del EF también es proporcional y justa para el MMS. De lo contrario, una asignación del EF puede no ser proporcional e incluso no ser MMS. [9]
Las versiones más débiles de EF incluyen: [10]
- Libre de envidia excepto 1 (EF1) : para cada dos agentes A y B, si eliminamos 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 un solo artículo). En condiciones de monotonicidad, siempre existe una asignación EF1.
- Sin envidia, excepto el más barato (EFx) : para cada dos agentes A y B, si eliminamos del paquete de B el artículo menos valioso para A, entonces A no envidia a B. EFx es estrictamente más fuerte que EF1. No se sabe si las asignaciones EFx siempre existen.
Este criterio se basa en el siguiente argumento: el proceso de asignación debe ser considerado como una 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, teniendo cada agente el mismo presupuesto para la compra de los objetos). Un equilibrio competitivo se alcanza 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 . [7]
Criterios de optimización global
Un criterio de optimización global evalúa una división basada en una función de bienestar social determinada :
- El bienestar social igualitario es la utilidad mínima de un solo agente. Una asignación de ítems se llama igualitaria-óptima si logra el máximo bienestar igualitario posible, es decir, maximiza la utilidad del agente más pobre. Dado que puede haber varias asignaciones diferentes que maximicen la utilidad más pequeña, la optimización igualitaria a menudo se refina a la óptima leximin : del subconjunto de asignaciones que maximizan la utilidad más pequeña, selecciona aquellas asignaciones que maximizan la segunda utilidad más pequeña y luego la tercera utilidad más pequeña. , etcétera.
- El bienestar social de Nash es producto de las utilidades de los agentes. Una asignación llamada Nash-optimal o Maximum-Nash-Welfare si maximiza el producto de las utilidades. Las asignaciones óptimas de Nash tienen algunas buenas propiedades de equidad. [10]
Una ventaja de los criterios de optimización global sobre los criterios individuales es que las asignaciones que maximizan el bienestar son eficientes en el sentido de Pareto .
Algoritmos de asignación
En páginas sobre criterios de equidad específicos se analizan varios algoritmos para la asignación justa de artículos:
Entre divisible e indivisible
Los documentos tradicionales sobre asignación justa suponen que todos los elementos son divisibles o que todos los elementos son indivisibles. Algunos artículos recientes estudian entornos en los que la distinción entre divisible e indivisible es más confusa.
Limitar la cantidad de compartir
Varios trabajos suponen que todos los objetos pueden dividirse si es necesario (por ejemplo, mediante propiedad compartida o tiempo compartido), pero compartirlos es costoso o indeseable. Por lo tanto, se desea encontrar una asignación justa con el menor número posible de objetos compartidos o de recursos compartidos. Existen límites superiores estrictos en el número de objetos compartidos/compartimientos necesarios para varios tipos de asignaciones justas entre n agentes:
Esto plantea la cuestión de si es posible lograr asignaciones justas con menos participaciones que el límite superior del peor de los casos:
- Sandomirskiy y Segal-Halevi [14] estudian la minimización del reparto en asignaciones que son justas y fraccionalmente eficientes en Pareto (fPO). Demuestran que, si las valoraciones de los agentes no son degeneradas, el número de asignaciones de fPO es polinomio en el número de objetos (para un número fijo de agentes). Por lo tanto, es posible enumerarlos todos en tiempo polinómico y encontrar una asignación que sea justa y fPO con el menor número de comparticiones. Por el contrario, si las valoraciones son degeneradas, el problema se vuelve NP-duro. Presentan evidencia empírica de que, en casos realistas, a menudo existe una asignación con sustancialmente menos participaciones que en el peor de los casos.
- Misra y Sethia [16] complementan su resultado demostrando que, cuando n no es fijo, incluso para valoraciones no degeneradas, es NP-difícil decidir si existe una asignación fPO libre de envidia con 0 participaciones. También demuestran un enfoque alternativo para enumerar gráficos de consumo distintos para asignaciones con una pequeña cantidad de participaciones.
- Goldberg, Hollender, Igarashi, Manurangsi y Suksompong [15] estudian la minimización del intercambio en la división por consenso . Demuestran que, para agentes con utilidades aditivas , existe un algoritmo de tiempo polinomial para calcular una división por consenso con como máximo n comparticiones, y para calcular una k -división de consenso con como máximo ( k −1) n cortes. Pero la minimización de compartir es NP-difícil: para cualquier n fijo , es NP-difícil distinguir entre una instancia que requiere n compartidos y una instancia que requiere 0 compartidos. Probabilísticamente, es casi seguro que las distribuciones n son necesarias para el consenso de reducción a la mitad cuando las utilidades de los agentes se extraen de distribuciones probabilísticas. Para agentes con utilidades monótonas no aditivas, la reducción a la mitad por consenso es difícil de PPAD, pero existen algoritmos de tiempo polinómico para un número fijo de agentes.
- Bismuth, Makarov, Shapira y Segal-Halevi [17] estudian la asignación justa con valoraciones idénticas, que equivale a la programación de máquinas idénticas , y también el entorno más general de la programación de máquinas uniformes . Estudian la complejidad en tiempo de ejecución de decidir la existencia de una asignación justa con s objetos compartidos u objetos compartidos, donde s es más pequeño que el límite superior del peor de los casos de n −1. Demuestran que, para compartir, el problema es NP-difícil para cualquier s ≤ n −2; pero para objetos compartidos y n ≥ 3, el problema es polinómico para s = n −2 y NP-duro para cualquier s ≤ n −3. Cuando n no se soluciona, el problema es fuertemente NP-difícil.
Mezcla de bienes divisibles e indivisibles
- Bei, Li, Liu, Liu y Lu [18] estudian una mezcla de bienes indivisibles y divisibles (objetos con utilidades positivas). Definen una aproximación a la ausencia de envidia llamada EFM (libre de envidia para elementos mixtos), que generaliza tanto la ausencia de envidia para elementos divisibles como EF1 para elementos indivisibles. Demuestran que siempre existe una asignación EFM para cualquier número de agentes con valoraciones aditivas. Presentan algoritmos eficientes para calcular asignaciones EFM para dos agentes con valoraciones aditivas generales y para n agentes con valoraciones lineales por partes sobre los bienes divisibles. También presentan un algoritmo eficiente que encuentra una asignación EFM aproximada de épsilon .
- Bei, Liu, Lu y Wang [19] estudian el mismo escenario, centrándose en la equidad maximin-share . Proponen un algoritmo que calcula una asignación de MMS aproximada alfa para cualquier número de agentes, donde alfa es una constante entre 1/2 y 1, que aumenta monótonamente con el valor de los bienes divisibles en relación con los valores de MMS.
- Bhaskar, Sricharan y Vaish [20] estudian una mezcla de tareas indivisibles (objetos con utilidades negativas) y un pastel divisible (con utilidad positiva). Presentan un algoritmo para encontrar una asignación de EFM en dos casos especiales: cuando cada agente tiene la misma clasificación de preferencia sobre el conjunto de tareas y cuando el número de elementos es como máximo el número de agentes más 1.
- Li, Liu, Lu y Tao [21] estudian mecanismos veraces para la EFM. Muestran que, en general, no existe ningún algoritmo EFM veraz, incluso si solo hay un bien indivisible y un bien divisible y solo dos agentes. Pero, cuando los agentes tienen valoraciones binarias de bienes indivisibles y valoraciones idénticas de un único bien divisible, existe un mecanismo EFM veraz. Cuando los agentes tienen valoraciones binarias sobre bienes divisibles e indivisibles, existe un mecanismo EFM y veraz cuando solo hay dos agentes, o cuando hay un solo bien divisible.
- Nishimura y Sumita [22] estudian las propiedades de la asignación máxima de bienestar de Nash (MNW) para bienes mixtos. Demuestran que, cuando las valoraciones de todos los agentes son binarias y lineales para cada bien, una asignación MNW satisface una propiedad más fuerte que EFM, a la que llaman "libre de envidia hacia cualquier bien para bienes mixtos". Sus resultados son válidos no sólo para el bienestar máximo de Nash, sino también para una noción de equidad general basada en minimizar una función simétrica estrictamente convexa. Para valoraciones aditivas generales, demuestran que una asignación MNW satisface una aproximación EF que es más débil que EFM.
- Kawase, Nishimura y Sumita [23] estudian la asignación óptima de bienes mixtos, donde el vector de utilidad debería minimizar una función simétrica estrictamente convexa (esta es una generalización de la asignación igualitaria de artículos y el bienestar máximo de Nash). Suponen que todos los agentes tienen valoraciones binarias. Se sabe que, si sólo existen bienes divisibles o sólo bienes indivisibles, el problema tiene solución en múltiples ocasiones. Muestran que, con bienes mixtos, el problema es NP-difícil incluso cuando todos los bienes indivisibles son idénticos. Por el contrario, si todos los bienes divisibles son idénticos, existe un algoritmo politiempo.
- Bei, Liu y Lu [24] estudian un escenario más general, en el que el mismo objeto puede ser divisible para algunos agentes e indivisible para otros. Muestran que la mejor aproximación posible para MMS es 2/3, incluso para dos agentes; y presentar algoritmos que logren este límite para 2 o 3 agentes. Para cualquier número de agentes, presentan una aproximación de 1/2 MMS. También muestran que la EFM es incompatible con el no despilfarro.
- Li, Li, Liu y Wu [25] estudian un entorno en el que cada agente puede tener una "relación de indivisibilidad" diferente (= proporción de elementos que son indivisibles). A cada agente se le garantiza una asignación que es EF/PROP hasta una fracción de un artículo, donde la fracción depende del ratio de indivisibilidad del agente. Los resultados son ajustados hasta una constante para EF y asintóticamente ajustados para PROP.
- Li, Liu, Lu, Tao y Tao [26] estudian el precio de la equidad en la asignación de artículos tanto indivisibles como mixtos. Proporcionan límites para el precio de EF1, EFx, EFM y EFxM. Proporcionan límites estrechos para dos agentes y límites asintóticamente estrechos para n agentes, tanto para servicios públicos escalados como no escalados.
Liu, Lu, Suzuki y Walsh [27] analizan algunos resultados recientes sobre elementos mixtos e identifican varias preguntas abiertas:
- ¿Es EFM compatible con la eficiencia de Pareto ?
- ¿Existen algoritmos eficientes para maximizar el bienestar social utilitario entre las asignaciones del EFM?
- ¿Existen algoritmos acotados o incluso finitos para calcular las asignaciones EFM en el modelo de consulta de Robertson-Webb ?
- ¿Existe siempre una asignación EFM cuando hay tareas indivisibles y un pastel?
- En términos más generales: ¿existe siempre una asignación EFM cuando tanto los elementos divisibles como los indivisibles pueden ser positivos para algunos agentes y negativos para otros?
- ¿Existe un algoritmo EFM veraz para agentes con valoraciones aditivas binarias?
Variantes y ampliaciones
Diferentes derechos
En esta variante, distintos agentes tienen derecho a distintas fracciones del recurso. Un caso de uso común es dividir los ministerios del gabinete entre los partidos de la coalición. [28] 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. Se consideraron varias clases de nociones de equidad:
- Nociones basadas en el equilibrio competitivo ponderado; [29] [30]
- Nociones basadas en una ponderada ausencia de envidia; [31] [32] [33]
- Nociones basadas en participación justa ponderada; [34]
Asignación a grupos
En esta variante, los paquetes no se entregan a agentes individuales sino a grupos de agentes. Los casos de uso comunes son: dividir la herencia entre familias o dividir las instalaciones entre departamentos de una universidad. Todos los agentes de un mismo grupo consumen el mismo paquete, aunque puedan valorarlo de forma diferente. La configuración clásica de asignación de elementos corresponde al caso especial en el que todos los grupos son únicos.
Con los grupos, puede ser imposible garantizar la equidad unánime (justicia a los ojos de todos los agentes de cada grupo), por lo que a menudo se relaja hacia la equidad democrática (justicia a los ojos de, por ejemplo, al menos la mitad de los agentes de cada grupo). [35]
Asignación de bienes públicos
En esta variante, cada elemento proporciona utilidad no sólo a un único agente sino a todos los agentes. Diferentes agentes pueden atribuir diferentes utilidades a un mismo artículo. El grupo tiene que elegir un subconjunto de elementos que satisfagan algunas restricciones, por ejemplo:
- Se pueden seleccionar como máximo k elementos. Esta variante está estrechamente relacionada con la votación con múltiples ganadores , excepto que en la votación con múltiples ganadores el número de candidatos electos suele ser mucho menor que el número de votantes, mientras que en la asignación de bienes públicos el número de bienes elegidos suele ser mucho mayor que el número de agentes. Un ejemplo es una biblioteca pública que tiene que decidir qué libros comprar, respetando las preferencias de los lectores; el número de libros suele ser mucho mayor que el número de lectores. [36]
- El costo total de todos los artículos no debe exceder un presupuesto fijo. Esta variante suele conocerse como presupuesto participativo .
- El número de elementos debe ser lo más pequeño posible, sujeto a que todos los agentes deben estar de acuerdo en que el conjunto elegido es mejor que el conjunto no elegido. Esta variante se conoce como problema del subconjunto agradable .
- Puede haber restricciones generales de matroide , restricciones de coincidencia o restricciones de mochila en el conjunto elegido. [37]
La asignación de bienes privados puede verse como un caso especial de asignación de bienes públicos: dado un problema de bienes privados con n agentes y m artículos, donde el agente i valora el artículo j en vij , construya un problema de bienes públicos con n · m artículos , donde el agente i valora cada elemento i,j en v ij y los demás elementos en 0. El elemento i,j esencialmente representa la decisión de darle el elemento j al agente i . Esta idea puede formalizarse para mostrar una reducción general de la asignación de bienes privados a la asignación de bienes públicos que retiene la asignación máxima de bienestar de Nash, así como una reducción similar que retiene la asignación óptima de leximin . [36]
Los conceptos de solución comunes para la asignación de bienes públicos son la estabilidad central (que implica tanto eficiencia de Pareto como proporcionalidad), [37] bienestar máximo de Nash, optimización de leximin y proporcionalidad hasta un elemento. [36]
Toma de decisiones públicas
En esta variante, varios agentes tienen que aceptar decisiones sobre varias cuestiones. Un caso de uso común es una familia que tiene que decidir qué actividad hacer cada día (aquí cada tema es un día). Cada agente asigna distintas utilidades a las distintas opciones de cada emisión. La configuración clásica de asignación de ítems corresponde al caso especial en el que cada emisión corresponde a un ítem, cada opción de decisión corresponde a entregar ese ítem a un agente en particular, y las utilidades de los agentes son cero para todas las opciones en las que el ítem 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 la PROP1 se puede lograr mediante la asignación de elementos por turnos . [38]
Asignación repetida
A menudo, los mismos elementos se asignan repetidamente. Por ejemplo, las tareas domésticas recurrentes. Si el número de repeticiones es múltiplo del número de agentes, entonces es posible encontrar en tiempo polinómico una secuencia de asignaciones libre de envidia y completa, y encontrar en tiempo exponencial una secuencia proporcional y óptima de Pareto. . Pero es posible que no exista una secuencia óptima de Pareto y libre de envidia. Con dos agentes, si el número de repeticiones es par, siempre es posible encontrar una secuencia libre de envidia y óptima en Pareto. [39]
Asignaciones estocásticas de bienes indivisibles
Las asignaciones estocásticas de bienes indivisibles [40] son un tipo de asignación justa de artículos en la que una solución describe una distribución de probabilidad sobre el conjunto de asignaciones deterministas.
Supongamos que m artículos deben distribuirse entre n agentes. Formalmente, en el entorno determinista, una solución describe una asignación factible de los elementos a los agentes: una partición del conjunto de elementos en n subconjuntos (uno para cada agente). El conjunto de todas las asignaciones deterministas se puede describir de la siguiente manera:
En el entorno estocástico, una solución es una distribución de probabilidad sobre el conjunto . Es decir, el conjunto de todas las asignaciones estocásticas (es decir, todas las soluciones factibles al problema) se puede describir de la siguiente manera:
Hay dos funciones relacionadas con cada agente, una función de utilidad asociada a una asignación determinista ; y una función de utilidad esperada asociada con una asignación estocástica que se define de la siguiente manera:
Criterios de equidad
Los mismos criterios que se sugieren para la configuración determinista también se pueden considerar en la configuración estocástica:
- Regla utilitarista : esta regla dice que la sociedad debe elegir la solución que maximice la suma de utilidades. Es decir, elegir una asignación estocástica que maximice el bienestar utilitario : Kawase y Sumita [40] muestran que la maximización del bienestar utilitario en el entorno estocástico siempre se puede lograr con una asignación determinista . La razón es que el valor utilitario de la asignación determinista es al menos el valor utilitario de :
- Regla igualitaria: esta regla dice que la sociedad debe elegir la solución que maximice la utilidad de los más pobres. Es decir, elegir una asignación estocástica que maximice la bienestar igualitario : en contraste con la regla utilitarista, aquí, la configuración estocástica permite a la sociedad alcanzar un valor más alto [40] ; como ejemplo, considere el caso en el que hay dos agentes idénticos y solo un artículo que vale la pena100 . Es fácil ver que en el marco determinista el valor igualitario es0 , mientras que en el ajuste estocástico es50 .
- Dureza: Kawase y Sumita [40] demuestran que encontrar una asignación estocástica que maximice el bienestar igualitario es NP-difícil incluso cuando las utilidades de los agentes son todas aditivas al presupuesto ; y también, que es NP-difícil aproximar el bienestar igualitario a un factor mejor que incluso cuando todos los agentes tienen la misma función de utilidad submodular .
- Algoritmo: Kawase y Sumita [40] presentan un algoritmo que, dado un algoritmo para encontrar una asignación determinista que aproxima el bienestar utilitario a un factor α , encuentra una asignación estocástica que aproxima el bienestar igualitario al mismo factor α .
Ver también
Referencias
- ^ Demko, Stephen; Colina, Theodore P. (1 de octubre de 1988). "Reparto equitativo de objetos indivisibles". Ciencias Sociales Matemáticas . 16 (2): 145-158. doi :10.1016/0165-4896(88)90047-9. ISSN 0165-4896.
- ^ abc Sylvain Bouveret y Yann Chevaleyre y Nicolas Maudet, "Asignación justa de bienes indivisibles". Capítulo 12 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)
- ^ Barberá, S.; Bossert, W.; Pattanaik, PK (2004). "Clasificación de conjuntos de objetos". (PDF) . Manual de teoría de la utilidad . Springer Estados Unidos.
- ^ Sylvain Bouveret; Ulle Endriss; Jérôme Lang (2010). División justa según preferencias ordinales: cálculo de asignaciones de bienes indivisibles sin envidia. 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 Artículos 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 y eficiente: ¿ayudar a los más desfavorecidos o evitar la envidia?". Racionalidad y Sociedad . 17 (4): 387–421. CiteSeerX 10.1.1.118.9114 . doi :10.1177/1043463105058317. S2CID 154808734.
- ^ abcde Bouveret, Sylvain; Lemaître, Michel (2015). "Caracterización de conflictos en la división justa de bienes indivisibles mediante 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 la asignación combinatoria: equilibrio competitivo aproximado a partir 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.
- ^ ab Heinen, Tobías; Nguyen, Nhan-Tam; Rothe, Jörg (2015). "Equidad y utilitarismo ponderado por rangos en la asignación de recursos". Teoría de la decisión algorítmica . Apuntes de conferencias sobre informática. vol. 9346. pág. 521. doi :10.1007/978-3-319-23114-3_31. ISBN 978-3-319-23113-6.
- ^ ab Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). La imparcialidad irrazonable del máximo bienestar de Nash (PDF) . Actas de la Conferencia ACM sobre Economía y Computación de 2016 - 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 inaproximabilidad 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 proximidad 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; 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.
- ^ ab Sandomirskiy, Fedor; Segal-Halevi, Erel (mayo de 2022). "División justa eficiente con un intercambio mínimo". Investigación de Operaciones . 70 (3): 1762–1782. arXiv : 1908.01669 . doi :10.1287/opre.2022.2279. ISSN 0030-364X.
- ^ ab Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2022). "Reducción a la mitad del consenso para conjuntos de elementos". Matemáticas de la Investigación de Operaciones . 47 (4): 3357–3379. arXiv : 2007.06754 . doi :10.1287/moor.2021.1249. S2CID 246764981.
- ^ Misra, Neeldhara; Sethia, Aditi (2021). "La división justa es difícil incluso para los agentes amigables". En Bureš, Tomáš; Dondi, Ricardo; Gamper, Johann; Guerrini, Giovanna; Jurdziński, Tomasz; Pahl, Claus; Sikora, Florian; Wong, Prudence WH (eds.). SOFSEM 2021: Teoría y Práctica de la Informática . Apuntes de conferencias sobre informática. vol. 12607. Cham: Springer International Publishing. págs. 421–430. doi :10.1007/978-3-030-67731-2_31. ISBN 978-3-030-67731-2.
- ^ Bismuto, Samuel; Makárov, Vladislav; Segal-Halevi, Erel; Shapira, Dana (8 de noviembre de 2023), Partición de números con división , arXiv : 2204.11753
- ^ Bei, Xiaohui; Li, Zihao; Liu, Shengxin; Lu, Xinhang (5 de enero de 2021). "División equitativa de bienes mixtos divisibles e indivisibles". Inteligencia artificial . 293 103436. Elsevier. arXiv : 1911.07048 . doi :10.1016/j.artint.2020.103436.
- ^ Bei, Xiaohui; Liu, Shengxin; Lu, Xinhang; Wang, Hongao (30 de junio de 2021). "Maximizar la equidad con bienes mixtos divisibles e indivisibles". Agentes Autónomos y Sistemas Multiagente . 35 (2): 34. arXiv : 2002.05245 . doi :10.1007/s10458-021-09517-7. ISSN 1573-7454.
- ^ Bhaskar, Umang; Sricharan, AR; Vaish, Rohit (2021). "Sobre la ausencia aproximada de envidia para tareas indivisibles y recursos mixtos". DROPS-IDN/V2/Document/10.4230/LIPIcs.APPROX/RANDOM.2021.1 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi : 10.4230/LIPIcs.APPROX/RANDOM.2021.1 .
- ^ Li, Zihao; Liu, Shengxin; Lu, Xinhang; Tao, Biaoshuai (19 de agosto de 2023). "Mecanismos justos y veraces para la asignación de bienes mixtos divisibles e indivisibles". Actas de la Trigésima Segunda Conferencia Internacional Conjunta sobre Inteligencia Artificial . IJCAI '23. Macao, República Popular China. págs. 2808–2816. doi :10.24963/ijcai.2023/313. ISBN 978-1-956792-03-4.
{{cite book}}
: CS1 maint: location missing publisher (link) - ^ Nishimura, Koichi; Sumita, Hanna (13 de agosto de 2023), Sin envidia y máximo bienestar de Nash para bienes mixtos divisibles e indivisibles , arXiv : 2302.13342
- ^ Kawase, Yasushi; Nishimura, Koichi; Sumita, Hanna (8 de noviembre de 2023), Asignación justa con valoraciones binarias para bienes mixtos divisibles e indivisibles , arXiv : 2306.05986
- ^ Bei, Xiaohui; Liu, Shengxin; Lu, Xinhang (2023-10-02), División justa con divisibilidad subjetiva , arXiv : 2310.00976
- ^ Li, Bo; Li, Zihao; Liu, Shengxin; Wu, Zekai (28 de abril de 2024), Asignación de bienes mixtos con una relación personalizada de equidad e indivisibilidad , arXiv : 2404.18132
- ^ Li, Zihao; Liu, Shengxin; Lu, Xinhang; Tao, Biaoshuai; Tao, Yichen (2 de enero de 2024), Un paisaje completo al precio de la ausencia de envidia , arXiv : 2401.01516
- ^ Liu, Shengxin; Lu, Xinhang; Suzuki, Mashbat; Walsh, Toby (24 de marzo de 2024). "División de ferias mixtas: una encuesta". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 38 (20): 22641–22649. arXiv : 2306.09564 . doi : 10.1609/aaai.v38i20.30274. ISSN 2374-3468.
- ^ Brams, Steven J.; Kaplan, Todd R. (2004). "Dividiendo lo indivisible". Revista de Política Teórica . 16 (2): 143. doi : 10.1177/0951629804041118. hdl : 10036/26974 . S2CID 154854134.
- ^ Babaioff, Moshé; Nisán, 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 . Amas '18. Fundación Internacional para Agentes Autónomos y Sistemas Multiagente. págs. 1267-1275.
- ^ Chakraborty, Mithun; Igarashi, Ayumi; Suksompong, Warut; Zick, Yair (16 de agosto de 2021). "Libre de envidia ponderada en la asignación de artículos indivisibles". Transacciones ACM sobre Economía y Computación . 9 (3): 18:1–18:39. arXiv : 1909.10502 . doi :10.1145/3457166. ISSN 2167-8375. S2CID 202719373.
- ^ Chakraborty, Mithun; Schmidt-Kraepelin, Ulrike; Suksompong, Warut (1 de diciembre de 2021). "Elección de secuencias y monotonicidad en división justa ponderada". Inteligencia artificial . 301 : 103578. arXiv : 2104.14347 . doi :10.1016/j.artint.2021.103578. ISSN 0004-3702. S2CID 233443832.
- ^ Chakraborty, Mithun; Segal-Halevi, Erel; Suksompong, Warut (28 de junio de 2022). "Revisión de las nociones de equidad ponderadas para elementos indivisibles". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 36 (5): 4949–4956. arXiv : 2112.04166 . doi : 10.1609/aaai.v36i5.20425 . ISSN 2374-3468. S2CID 244954009.
- ^ Babaioff, Moshé; Esdras, Tomer; Feige, Uriel (15 de noviembre de 2021). "Asignaciones de participación justa para agentes con derechos arbitrarios". arXiv : 2103.04304 [cs.GT].
- ^ Segal-Halevi, Erel; Suksompong, Warut (1 de diciembre de 2019). "Asignación democrática y justa de bienes indivisibles". Inteligencia artificial . 277 : 103167. arXiv : 1709.02564 . doi :10.1016/j.artint.2019.103167. ISSN 0004-3702. S2CID 203034477.
- ^ abc Garg, yugal; Kulkarni, Pooja; Murhekar, Aniket (2021). Bojańczy, Miko\laj; Chekuri, Chandra (eds.). "Sobre asignaciones justas y eficientes de bienes públicos indivisibles". 41.a Conferencia Anual de la IARCS sobre los fundamentos de la tecnología de software y la informática teórica (FSTTCS 2021) . Procedimientos internacionales de informática de Leibniz (LIPIcs). 213 . Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 22:1–22:19. doi : 10.4230/LIPIcs.FSTTCS.2021.22 . ISBN 978-3-95977-215-0. S2CID 236154847.
- ^ ab Fain, Brandon; Munagala, Kamesh; Shah, Nisarg (11 de junio de 2018). "Asignación justa de bienes públicos indivisibles". Actas de la Conferencia ACM de 2018 sobre Economía y Computación . CE '18. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 575–592. doi :10.1145/3219166.3219174. ISBN 978-1-4503-5829-3. S2CID 3331859.
- ^ Conitzer, Vicente; Freeman, Ruperto; Shah, Nisarg (2017). "Toma de decisiones públicas justa". En Daskalakis, Constantinos; Babaioff, Moshé; Moulin, Hervé (eds.). Actas de la Conferencia ACM sobre Economía y Computación de 2017, EC '17, Cambridge, MA, EE. UU., 26 al 30 de junio de 2017 . {ACM}. págs. 629–646. arXiv : 1611.04034 . doi :10.1145/3033274.3085125. ISBN 978-1-4503-4527-9.
- ^ Igarashi, Ayumi; Lackner, Martín; Nardi, Oliviero; Novaro, Arianna (4 de abril de 2023). "Asignación justa repetida de elementos indivisibles". arXiv : 2304.01644 [cs.GT].
- ^ abcde Kawase, Yasushi; Sumita, Hanna (2020). "Sobre la asignación estocástica justa Max-Min de bienes indivisibles". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (2): 2070–2078. doi : 10.1609/AAAI.V34I02.5580 . S2CID 214407880.