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.
![{\displaystyle m}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 2^{m}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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.![{\displaystyle 2^{m}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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]
![{\displaystyle 1/n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- 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] Consulte la asignación de artículos sin envidia para obtener más detalles.
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]
Varios criterios de equidad sugeridos recientemente son: [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 a objeto unico). En condiciones de monotonicidad, siempre existe una asignación EF1.
Sin envidia, excepto lo 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.
Criterios de optimización global
Un criterio de optimización global evalúa una división basada en una función de bienestar social dada :
- 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:
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. [14] 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; [15] [16]
- Nociones basadas en una ponderada ausencia de envidia; [17] [18] [19]
- Nociones basadas en participación justa ponderada; [20]
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). [21]
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. [22]
- 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 matroides generales , restricciones de coincidencia o restricciones de mochila en el conjunto elegido. [23]
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 ym 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 . [22]
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), [23] bienestar máximo de Nash, optimización de leximin y proporcionalidad hasta un elemento. [22]
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 . [24]
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. [25]
Asignaciones estocásticas de bienes indivisibles
Las asignaciones estocásticas de bienes indivisibles [26] 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.
Suponga que los artículos deben distribuirse entre los 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 subconjuntos (uno para cada agente). El conjunto de todas las asignaciones deterministas se puede describir de la siguiente manera:![{\displaystyle m}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {A}}=\{(A^{1},\dots ,A^{n})\mid \forall i\in [n]\colon A^{i}\subseteq [m ],\quad \forall i\neq j\in [n]\colon A^{i}\cap A^{j}=\emptyset ,\quad \cup _{i=1}^{n}A^{ i}=[m]\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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:![{\displaystyle {\mathcal {A}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {D}}=\{d\mid p_{d}\colon {\mathcal {A}}\to [0,1],\sum _{A\in {\mathcal {A} }}p_{d}(A)=1\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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:![{\displaystyle u_{i}\colon {\mathcal {A}}\to \mathbb {R} _{+}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle E_{i}\colon {\mathcal {D}}\to \mathbb {R} _{+}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ Displaystyle u_ {i}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle E_{i}(d)=\sum _ {A\in {\mathcal {A}}}p_{d}(A)\cdot u_{i}(A)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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 [26] 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 :
![{\displaystyle d^{*}\in {\mathcal {D}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle d^{*}={\text{argmax}}_{d\in {\mathcal {D}}}\sum _{i=1}^{n}\sum _{A\in {\ mathcal {A}}}\left(p_{d}(A)\cdot u_{i}(A)\right)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A^{*}={\text{argmax}}_{A\in {\mathcal {A}}\colon p_{d^{*}}(A)>0}\sum _{i= 1}^{n}u_{i}(A)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle d^{*}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \sum _{i=1}^{n}\sum _{A\in {\mathcal {A}}}\left(p_{d^{*}}(A)\cdot u_{i} (A)\right)=\sum _{A\in {\mathcal {A}}}p_{d^{*}}(A)\sum _{i=1}^{n}u_{i}( A)\leq \max _{A\in {\mathcal {A}}\colon p_{d^{*}}(A)>0}\sum _{i=1}^{n}u_{i} (A)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- 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 [26] ; como ejemplo, considere el caso en el que hay dos agentes idénticos y solo un elemento que vale 100. Es fácil ver que en el entorno determinista el valor igualitario es , mientras que en el entorno estocástico es .
![{\displaystyle d^{*}\in {\mathcal {D}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle d^{*}={\text{argmax}}_{d\in {\mathcal {D}}}\min _{i=1,\ldots ,n}\sum _{A\in { \mathcal {A}}}\left(p_{d}(A)\cdot u_{i}(A)\right)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 50}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Dureza: Kawase y Sumita [26] 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 .
![{\displaystyle 1-{\frac {1}{e}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Algoritmo: Kawase y Sumita [26] 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 .
![{\displaystyle \alpha }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \alpha }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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.
- ^ 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). Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 213 : 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 (2016). "Toma de decisiones públicas justas | Actas de la Conferencia ACM sobre Economía y Computación de 2017". arXiv : 1611.04034 . doi :10.1145/3033274.3085125. S2CID 30188911.
- ^ 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.