Asignación de artículos eficiente y aproximadamente justa

Al asignar objetos entre personas con diferentes preferencias, dos objetivos principales son la eficiencia de Pareto y la equidad. Dado que los objetos son indivisibles, puede que no exista ninguna asignación justa. Por ejemplo, cuando hay una sola casa y dos personas, cada asignación de la casa será injusta para una persona. Por lo tanto, se han estudiado varias aproximaciones comunes, como la equidad de máxima participación (MMS) , la ausencia de envidia hasta un artículo (EF1), la proporcionalidad hasta un artículo (PROP1) y la equidad hasta un artículo (EQ1). El problema de la asignación de artículos aproximadamente justa y eficiente es encontrar una asignación que sea a la vez eficiente en términos de Pareto (PE) y satisfaga una de estas nociones de equidad. El problema se presentó por primera vez en 2016 ^[1] y ha atraído considerable atención desde entonces.

Configuración

Hay un conjunto finito de objetos, denotado por M . Hay n agentes. Cada agente i tiene una función de valor V _i , que asigna un valor a cada subconjunto de objetos. El objetivo es dividir M en n subconjuntos, X ₁ ,..., X _n , y dar cada subconjunto X _i al agente i , de modo que la asignación sea eficiente en el sentido de Pareto y aproximadamente justa. Existen varias nociones de justicia aproximada.

Asignación eficiente y aproximadamente libre de envidia

Una asignación se denomina libre de envidia (FE) si cada agente cree que el valor de su parte es al menos tan alto como el de cualquier otro agente. Se denomina libre de envidia hasta un artículo (FE1) si, por cada dos agentes i y j, si se elimina como máximo un artículo del conjunto de j, entonces i no envidia a j. Formalmente:

$\forall i,j:~~~\existe Y\subseteq X_{j}:~~~|Y|\leq 1,~~~V_{i}(X_{i})\geq V_{i}(X_{j}\setminus Y)$

Algunos de los primeros algoritmos pudieron encontrar una asignación aproximadamente justa que satisficiera una forma débil de eficiencia, pero no la PE.

El procedimiento round-robin devuelve una asignación EF1 completa con utilidades aditivas . El procedimiento envy-graph devuelve una asignación EF1 completa para relaciones de preferencia monótonas arbitrarias. ^[2] Ambos procedimientos garantizan que devuelvan una asignación sin ciclos de envidia. Sin embargo, no se garantiza que la asignación sea eficiente en el sentido de Pareto.
El mecanismo Approximate-CEEI devuelve una asignación EF1 parcial para relaciones de preferencia arbitrarias. Es PE con respecto a los objetos asignados, pero no PE con respecto a todos los objetos (ya que algunos objetos pueden permanecer sin asignar). ^[3]

Esto planteó la cuestión de encontrar una asignación que sea a la vez PE y EF1.

Regla de bienestar máximo de Nash

Caragiannis, Kurokawa, Moulin, Procaccia, Shah y Wang ^[1] fueron los primeros en demostrar la existencia de una asignación PE+EF1. Demostraron que, cuando todos los agentes tienen utilidades aditivas positivas , toda asignación que maximice el producto de las utilidades (también conocido como bienestar de Nash ) es EF1. Como es obvio que la asignación maximizadora es la EP, se deduce la existencia de una asignación PE+EF1.

Si bien la asignación de máximo producto tiene propiedades deseables, no se puede calcular en tiempo polinomial: encontrar una asignación de máximo producto es NP-difícil ^[4] e incluso APX-difícil . ^[5] Esto llevó a varios trabajos que intentaron aproximar el producto máximo, con factores de aproximación mejorados:

Cole y Gkatzelis ^[6] presentaron una aproximación de 2,89 factores.
Anari, Gharan, Saberi y Singh ^[7] presentaron una aproximación del factor e.
Cole, Devanur, Gkatelis, Jain, Mai, Vazirani y Yazdanbod ^[8] presentaron una aproximación de 2 factores.

Sin embargo, estas aproximaciones no garantizan el EF1. Algunos algoritmos más recientes garantizan tanto el producto máximo aproximado como la imparcialidad:

Barman, Krishanmurthy y Vaish ^[9] presentan un algoritmo que garantiza PE, (1+epsilon)-EF1 y una aproximación de 1,45 al producto máximo, en tiempo pseudopolinomial (ver algoritmo de precio creciente a continuación).
Garg y McGlaughlin ^[10] presentan un algoritmo que garantiza PE, PROP1 y una aproximación de 2 al producto máximo, en tiempo fuertemente polinomial.
Caragiannis, Gravin y Huang ^[11] presentan un algoritmo que garantiza EFX, PROP1 y una aproximación de 2,9 al producto máximo, descartando algunos bienes (también muestran la existencia de una asignación de 2 aproximaciones).

La solución de producto máximo es particularmente atractiva cuando las valoraciones son binarias (el valor de cada artículo es 0 o 1):

Amanatidis, Birmpas, Filos-Ratsikas, Hollender y Voudouris ^[12] demuestran que con valoraciones binarias la solución de máximo producto no es solo EF1 sino también EFX (libre de envidia hasta cualquier bien). Esto se cumple siempre que el valor de cada artículo pueda tomar uno de dos valores, no necesariamente 0 o 1. Con valoraciones aditivas generales, el máximo producto no implica EFX sino una generalización natural de este.
Halpern, Procaccia, Psomas y Shah ^[13] demuestran que con valoraciones binarias la regla del máximo producto con desempate lexicográfico se puede calcular en tiempo polinomial y también es a prueba de estrategias de grupo .

Valoraciones no aditivas

Si las utilidades de los agentes no son aditivas, la solución de máximo producto no es necesariamente EF1; pero si las utilidades de los agentes son al menos submodulares , la solución de máximo producto satisface una propiedad más débil llamada Marginal-Envy-Freeness except-1-item (MEF1): significa que cada agente i valora su paquete al menos tanto como la utilidad marginal de (el paquete de j sin el mejor artículo). Formalmente: ^[14]

$\forall i,j:~~~\exists Y\subseteq X_{j}:~~~|Y|\leq 1,~~~V_{i}(X_{i})\geq V_{i}(X_{i}\cup (X_{j}\setminus Y))-V_{i}(X_{i})$

Se han encontrado aproximaciones similares para funciones de utilidad más generales:

Bei, Garg, Hoefer y Mehlhorn ^[15] y Anari, Mai, Gharan y Vazirani ^[16] estudian mercados con múltiples unidades de cada tipo de artículo, donde las valoraciones son separables [ sic ? ] cóncavas lineales por partes . Esto significa que la utilidad de un paquete con diferentes tipos de artículos es la suma de las utilidades para cada tipo de artículo individual (este es el significado de "separable"), pero para cada tipo de artículo, la valoración tiene utilidades marginales decrecientes (este es el significado de "cóncava lineal por partes"). Proporcionan una aproximación 2 al producto máximo.
Ortega ^[17] estudia un mercado multi-unitario con valoraciones binarias. Demuestra que la regla igualitaria es dominante en el sentido de Lorenz (una propiedad más fuerte que la optimalidad leximin), única en utilidades y a prueba de estrategias de grupo .
Garg, Hoefer y Mehlhorn ^[18] estudian las valoraciones aditivas presupuestarias , una subclase de utilidades submodulares. Ofrecen una aproximación (2,404 + ε ) al polinomio de máximo producto en el tiempo en el tamaño de entrada y 1/ ε.
Benabbou, Chakraborty, Igarashi y Zick ^[19] estudian utilidades submodulares con ganancias marginales binarias (es decir, cada artículo suma 0 o 1 al valor de cada paquete). Demuestran que, con tales valoraciones, tanto las asignaciones de máximo producto como las de leximin son EF1 y maximizan el bienestar utilitario (suma de utilidades).
Babaioff, Ezra y Feige ^[20] también estudian utilidades submodulares con ganancias marginales binarias ("dicotómicas"). Presentan un mecanismo veraz determinista que genera una asignación dominante de Lorenz, que es, por lo tanto, EFX y producto máximo.

Valoraciones mixtas

Martin y Walsh ^[21] demuestran que, con "maná mixto" (valoraciones aditivas que pueden ser tanto positivas como negativas), maximizar el producto de las utilidades (o minimizar el producto de menos las utilidades) no garantiza EF1. También demuestran que una asignación EFX3 puede no existir incluso con utilidades idénticas. Sin embargo, con utilidades terciarias, siempre existen asignaciones EFX y PO, o asignaciones EFX3 y PO; y con utilidades idénticas, siempre existen asignaciones EFX y PO. Para estos casos existen algoritmos de tiempo polinomial.

Algoritmo de aumento de precio

Barman, Krishanmurthy y Vaish ^[9] presentaron un algoritmo de tiempo pseudopolinomial para encontrar asignaciones PE+EF1 para valoraciones aditivas positivas. Demostraron los siguientes resultados.

El algoritmo encuentra una asignación PE+EF1 en el tiempo O(poly( m , n , v _max )), donde m es el número de objetos, n el número de agentes y v _max el valor más grande de un elemento (todas las valoraciones son números enteros).
El mismo algoritmo proporciona una aproximación de 1,45 al bienestar máximo de Nash.
El algoritmo también demuestra la existencia de una asignación que es a la vez EF1 y fraccionalmente óptima en el sentido de Pareto .

Conceptos básicos

Su algoritmo se basa en la noción de equilibrio competitivo en un mercado de Fisher y utiliza los siguientes conceptos.

Asignación EF1 aproximada : dada una constante e > 0, una asignación es e -EF1 si satisface la condición EF1 hasta una constante multiplicativa de (1+ e ). Formalmente:
- $\forall i,j:~~~\exists Y\subseteq X_{j}:~~~|Y|\leq 1,~~~(1+e)\cdot V_{i}(X_{i})\geq V_{i}(X_{j}\setminus Y)$
Vector de precios : un vector que asigna un precio (un número real) a cada artículo.
Relación precio-beneficio : para un agente i y un objeto o , es la relación entre la valoración del artículo por parte del agente y el precio del artículo: v _ij / p _j .
Conjunto de máxima rentabilidad por inversión (MBB) : para un agente i , es el conjunto de objetos que maximizan su relación rentabilidad por inversión (dado un vector de precios p ).
Asignación MBB : asignación en la que cada agente recibe solo objetos de su conjunto MBB. En una asignación MBB, cada agente maximiza su utilidad dado su presupuesto (pero la asignación MBB es una condición más fuerte). El primer teorema del bienestar implica que una asignación MBB es fraccionariamente óptima en términos de Pareto .
Asignación sin envidia de precios (pEF) : una asignación X en la que, para cada dos agentes i . j , el precio de X _i (llamado el "ingreso" de i) es al menos tan grande como el precio X _j . Esto implica que todos los ingresos son idénticos. Además, una asignación que es tanto MBB como pEF está libre de envidia , ya que cada agente maximiza su utilidad dado su ingreso, y todos los demás agentes tienen el mismo ingreso.
Asignación libre de envidia de precios excepto uno (pEF1) : una asignación en la que, para cada dos agentes i . j , el precio p( X _i ) es al menos tan grande como el precio de Xj sin su artículo más caro. Esto no implica que los ingresos sean idénticos. Sin embargo, una asignación que es a la vez MBB y pEF1 también es EF1. ^[9]^{: Lem.4.1}
Asignación e -pEF1 , para alguna constante e > 0: una asignación en la que, para cada dos agentes i . j , el producto (1+ e )·p( X _i ) es al menos tan grande como p( Xj ) sin su elemento más caro. Nótese que lacondición e -pEF1 es más débil cuando e es mayor. En particular, una asignación pEF1 es e -pEF1 para cada e > 0, pero lo opuesto no es cierto. Una asignación que es tanto MBB como e -pEF1 también es e -EF1 .^[9]^{: Lem.4.1}
El que menos gasta : dada una asignación y un vector de precios, es el agente i tal que p( X _i ) es el más pequeño (los empates se rompen en función de un orden preestablecido de los agentes). Nótese que una asignación es e -pEF1 si y solo si se cumple la condición e -pEF1 para el que menos gasta (como agente i ).
Jerarquía MBB del agente i (dada la asignación X y el vector de precios p ): una estructura de árbol construida de la siguiente manera.
- Coloque el agente i en la raíz (esto se llama nivel 0).
- Conectar al agente i todos los objetos en su conjunto MBB (dado el vector de precios p ).
- Conectarse a cada objeto o al agente que lo posee en X , si aún no está en el árbol (esto se llama nivel 1)
- Conecta a cada agente en el nivel 1, todos los objetos en su conjunto MBB que aún estén en el árbol.
- Continúe agregando agentes y objetos alternativamente de manera similar: para cada agente, agregue sus objetos MBB; para cada elemento, agregue su agente propietario.
Infractor (dada la asignación X y el vector de precios p ): un agente h que viola la condición pEF1 con respecto al que menos gasta i . Por lo tanto, el precio de X _h , incluso cuando se le quita el artículo más caro, es mayor que p ( X _i ). De manera similar, e -infractor es un agente que viola la condición e -pEF1 con respecto al que menos gasta.
Infractor de la ruta (dada la asignación X y el vector de precios p , y la jerarquía MBB): un agente h que aparece en la jerarquía MBB del que menos gasta i , y viola parcialmente la condición pEF1 con respecto a i . En más detalle: supongamos que hay una ruta, a lo largo de los bordes de la jerarquía MBB, desde el que menos gasta i hasta el objeto o , y luego una arista desde el objeto o hasta el agente h (esto significa que X _h contiene o ). Si p ( X _h \ { o }) > p ( X _i ), entonces h es un infractor de la ruta. Nótese que todo infractor es un infractor de la ruta, pero lo opuesto no es cierto. De manera similar, si p ( X _h \ { o }) > (1+ e )· p ( X _i ), entonces h es un e -infractor de la ruta .

Algoritmo

Dado un parámetro e , el algoritmo busca encontrar una asignación que sea tanto fPO como 3 e -pEF1. El algoritmo se desarrolla en varias fases.

Fase 1: Construir una asignación MBB inicial+precio (X, p) .

Una forma de hacerlo es dar cada objeto o al agente i que lo valora más (deshaciendo los empates arbitrariamente), y fijar el precio de o en v _i,o . Esto garantiza que, para cada agente, el bang-for-buck de todos los objetos en su paquete sea exactamente 1, y el bang-for-buck de todos los objetos en otros paquetes sea como máximo 1. Por lo tanto, la asignación es MBB, por lo tanto también es fPO.
Si la asignación es 3 e -pEF1, devuélvalo; en caso contrario, proceda a la Fase 2.

Fase 2: Eliminar la envidia de precios dentro de la jerarquía MBB :

Construya la jerarquía MBB del que menos gasta, dada la corriente ( X , p ).
Para L = 1,2,...:
- Para cada agente h en el nivel L del árbol:
  - Si h es un violador de la ruta e a lo largo de la ruta: i → ... → h' → o → h, entonces transfiera el objeto o del agente h al agente h' (tenga en cuenta que la asignación permanece en MBB). Reinicie la Fase 2.
Una vez que ya no haya más infractores de la ruta e :
- Si la asignación es 3 e -pEF1, devuélvalo; en caso contrario, proceda a la Fase 3.

Fase 3: Aumentar los precios . Aumentar los precios de todos los objetos de la jerarquía MBB por el mismo factor multiplicativo, hasta que ocurra una de las tres cosas siguientes:

La identidad del que menos gasta cambia. Esto puede suceder si algún agente fuera de la jerarquía (cuyos artículos no aumentan de precio) se convierte en el que menos gasta. En este caso, reiniciamos en la Fase 2.
Se agrega un nuevo objeto a la jerarquía MBB. Esto puede suceder porque, cuando los precios de los objetos en la jerarquía aumentan en un factor r , la relación BB de los objetos en la jerarquía disminuye en r , mientras que la relación BB de los objetos fuera de la jerarquía permanece igual. Por lo tanto, cuando r es lo suficientemente grande, algún objeto externo se convertirá en MBB para algún agente de la jerarquía. En este caso, también reiniciamos en la Fase 2.
La asignación actual X se convierte en 3 e -pEF1. Esto puede suceder porque, cuando los precios de los objetos en la jerarquía aumentan, el ingreso del que menos gasta aumenta, mientras que el ingreso de los agentes fuera de la jerarquía permanece constante. Por lo tanto, cuando r es suficientemente grande, es posible que se cumpla la condición 3 e -pEF1 con respecto al que menos gasta. En este caso, devolvemos la asignación X y el nuevo precio p .

Prueba de corrección

Primero, supongamos que el algoritmo anterior se ejecuta en una instancia en la que todos los valores son potencias de (1+ e ), para algún e fijo > 0.

El primer desafío es demostrar que el algoritmo termina. Se puede demostrar que, cuando todas las valoraciones son potencias de (1+ e ), el algoritmo termina en el tiempo O (poly(m, n, 1/ e , ln( V _max )), donde V _max es el valor más grande de un objeto para un agente. ^[22]^{: 23–29}
La asignación inicial es una asignación MBB y todas las operaciones mantienen esta condición. Por lo tanto, la asignación devuelta es MBB, por lo que también es fPO.
Según las condiciones de terminación, siempre que el algoritmo termina, la asignación devuelta es 3 e -pEF1, por lo que también es 3 e -EF1.

Ahora, supongamos que tenemos una instancia con valoraciones generales. Ejecutamos el algoritmo anterior en una instancia redondeada , donde cada valoración se redondea hacia arriba a la potencia más cercana de (1+ e ). Tenga en cuenta que para cada agente i y objeto o , el valor redondeado V _i '( o ) está acotado entre V _i ( o ) y (1+ e ) V _i ( o ).

Por el párrafo anterior, la asignación resultante es fPO y 3 e -EF1 con respecto a la instancia redondeada.
Para cada e suficientemente pequeño (particularmente, menor que 1 / 6 m ³ V _max⁴ ), una asignación que es fPO para la instancia redondeada es PO para la instancia original. ^[22]^{: 29–34}
Al combinar la garantía 3 e -EF1 para la instancia redondeada, con el límite para el redondeo, obtenemos que la asignación devuelta satisface la siguiente condición aproximada EF1:
- $\forall i,j:~~~\exists C\subseteq X_{j}:~~~|C|\leq 1,~~~(1+e)\cdot (1+3e)\cdot V_{i}(X_{i})\geq V_{i}(X_{j}\setminus C)$
Para un valor de e suficientemente pequeño , el producto (1+ e )(1+3 e ) es como máximo (1+7 e ). Por lo tanto, una asignación que es 3 e -EF1 para la instancia redondeada es 7 e -EF1 para la instancia original.
Dado que las valoraciones originales son números enteros, cuando e es suficientemente pequeño, una asignación 7 e -EF1 también es EF1.
Por lo tanto, la asignación resultante es PO+EF1 para la instancia original.

Ganador generalizado ajustado

Aziz, Caragiannis, Igarashi y Walsh ^[23]^{: la sección 4} extendió la condición de EF1 a valoraciones mixtas (los objetos pueden tener utilidades tanto positivas como negativas). Presentaron una generalización del procedimiento ganador ajustado para encontrar una asignación PO+EF1 para dos agentes en el tiempo O( m ² ).

Asignación aproximadamente proporcional eficiente

Una asignación de objetos es proporcional (PROP) si cada agente valora su parte al menos en 1/ n del valor de todos los bienes. Se dice que es proporcional hasta un bien (PROP1) si para cada agente i , si se añade como máximo un bien al conjunto de i , entonces i valora el conjunto al menos en 1/ n del total. Formalmente, para todos los i (donde M es el conjunto de todos los bienes):

$\exists Y\subseteq M\setminus X_{i}:~~~|Y|\leq 1,~~~V_{i}(X_{i}\cup Y)\geq V_{i}(M)/n$ .

La condición PROP1 fue introducida por Conitzer, Freeman y Shah ^[24] en el contexto de la toma de decisiones públicas justas. Demostraron que, en este caso, siempre existe una asignación PE+PROP1.

Dado que cada asignación EF1 es PROP1, también existe una asignación PE+PROP1 en la asignación de elementos indivisibles; la pregunta es si dichas asignaciones se pueden encontrar mediante algoritmos más rápidos que los de PE+EF1.

Barman y Krishnamurthy ^[25] presentaron un algoritmo de tiempo strongy-polinomial que encuentra una asignación PE+PROP1 para bienes (objetos con utilidad positiva).

Branzei y Sandomirskiy ^[26] extendieron la condición de PROP1 a las tareas domésticas (objetos con utilidad negativa). Formalmente, para todo i :

$\exists Y\subseteq X_{i}:~~~|Y|\leq 1,~~~V_{i}(X_{i}\setminus Y)\geq V_{i}(M)/n$ .

Presentaron un algoritmo que determina una asignación de tareas PE+PROP1. El algoritmo es fuertemente polinomial si el número de objetos o el número de agentes (o ambos) son fijos.

Aziz, Caragiannis, Igarashi y Walsh ^[23] extendieron la condición de PROP1 a valoraciones mixtas (los objetos pueden tener utilidades tanto positivas como negativas). En este contexto, una asignación se denomina PROP1 si, para cada agente i , si eliminamos un elemento negativo del conjunto de i, o añadimos un elemento positivo al conjunto de i, entonces la utilidad de i es al menos 1/ n del total. Su algoritmo Ganador Ajustado Generalizado encuentra una asignación PE+EF1 para dos agentes; dicha asignación también es PROP1.

Aziz, Moulin y Sandomirskiy ^[27] presentaron un algoritmo de tiempo fuertemente polinomial para encontrar una asignación que sea fraccionalmente PE (más fuerte que PE) y PROP1, con valoraciones mixtas generales, incluso si el número de agentes u objetos no es fijo, e incluso si los agentes tienen diferentes derechos.

Asignación eficiente y aproximadamente equitativa

Una asignación de objetos se denomina equitativa (EQ) si el valor subjetivo de todos los agentes es el mismo. La motivación para estudiar esta noción proviene de experimentos que muestran que los sujetos humanos prefieren asignaciones equitativas a las libres de envidia. ^[28] Una asignación se denomina equitativa hasta un elemento (EQ1) si, para cada dos agentes i y j, si se elimina como máximo un elemento del conjunto de j, entonces el valor subjetivo de i es al menos el de j. Formalmente, para todos los i , j :

$\exists Y\subseteq X_{j}:~~~|Y|\leq 1,~~~V_{i}(X_{i})\geq V_{j}(X_{j}\setminus Y)$ .

Una noción más fuerte es la de equidad hasta cualquier elemento (EQx) : para cada dos agentes i y j, si se elimina un solo elemento del conjunto de j, entonces el valor subjetivo de i es al menos el de j:

$\forall y\in X_{j}:~~~V_{i}(X_{i})\geq V_{j}(X_{j}\setminus \{y\})$ .

Las asignaciones EQx fueron estudiadas por primera vez por Gourves, Monnot y Tlilane, quienes usaron un término diferente: "casi libre de celos". ^[29]^{: 3} Demostraron que siempre existe una asignación EQx parcial, incluso con el requisito adicional de que la unión de todos los bienes asignados sea una base de un matroide dado . Usaron un algoritmo similar al procedimiento del grafo de envidia . Suksompong ^[30] demostró que existe una asignación EQ1 incluso con el requisito adicional de que todas las asignaciones deben ser subconjuntos contiguos de una línea.

Freeman, Sidkar, Vaish y Xia ^[31] demostraron los siguientes resultados más contundentes:

Cuando todas las valoraciones son estrictamente positivas, siempre existe una asignación PE+EQx y hay un algoritmo de tiempo pseudopolinomial que encuentra una asignación PE+EQ1.
Cuando algunas valoraciones pueden ser cero, incluso una asignación PE+EQ1 puede no existir, y decidir si existe una PE+EQ/EQ1/EQx es fuertemente NP-hard .
Puede que no exista una asignación PE+EQ1+EF1. Decidir si existe o no es una cuestión NP-difícil en general, pero se puede resolver en tiempo polinómico con valoraciones binarias (0 o 1).

Algoritmos para un pequeño número de agentes

Bredereck, Kaczmarcyk, Knop y Niedermeier^[32] estudian un contexto en el que hay pocos agentes ( n pequeño ) y pocos tipos de ítems ( m pequeño ), la utilidad por tipo de ítem está limitada superiormente (por V ), pero puede haber muchos ítems de cada tipo. Para este contexto, demuestran el siguiente metateorema (Teorema 2): Dado un criterio de eficiencia E, y un criterio de equidad F, si es fijo, entonces es posible decidir en tiempo polinomial si existe una asignación que sea tanto E-eficiente como F-justa, siempre que E y F satisfagan las siguientes propiedades: $n+u_{\max }+m$

Equidad : La cuestión de si existe una asignación F-justa se puede modelar mediante un programa lineal entero con una dimensión fija.
Eficiencia : La cuestión de si existe una asignación que E-domina otra asignación dada puede modelarse mediante un programa entero cuya profundidad de árbol dual y el valor absoluto del coeficiente más grande están acotados superiormente por alguna función . $f(n,u_{\max })$

Luego, demuestran que varios criterios comunes de equidad y eficiencia satisfacen estas propiedades, entre ellos:

Nociones de equidad : ausencia de envidia, EF1, EFx, EF de grafo (cuando los agentes envidian solo a sus vecinos en un grafo fijo), igualitario, participación maximin y ausencia de envidia de grupo promedio (donde cada grupo de agentes valora su participación como la media aritmética de las utilidades de los miembros).
Nociones de eficiencia : Pareto-eficiencia, Pareto-eficiencia de grafos (donde la dominación de Pareto considera solo los intercambios entre vecinos en un grafo fijo) y Pareto-eficiencia de grupo. Una asignación X es k-grupo-Pareto-eficiente (GPE _k ) si no hay otra asignación Y que sea al menos tan buena (por media aritmética de utilidades) para todos los grupos de tamaño k , y estrictamente mejor para al menos un grupo de tamaño k . Nótese que GPE ₁ es equivalente a Pareto-eficiencia. GPE _n es equivalente a una asignación utilitarista-máxima, ya que para el gran grupo G de tamaño n , la utilidad de media aritmética es equivalente a la suma de las utilidades de todos los agentes. Para todos los k , GPE _k+1 implica GPE _k .

El tiempo de ejecución de su algoritmo es polinomial en el tamaño de entrada (en bits) multiplicado por , donde d es el número de variables en el ILP resultante, que es . ^[32]^{: sub.4.3} $d^{2.5d}$ $d=m(n+1)+m(n+1)\cdot (4\cdot (4n\cdot V+1)^{n})^{m(n+1)}$

Posteriormente desarrollaron algoritmos más prácticos para algunos de estos problemas. ^[33]

Véase también

Eficiencia fraccional de Pareto#Encontrar asignaciones justas y fPO

Referencias

^ ab Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (24 de septiembre de 2019). "La justicia irrazonable del bienestar máximo de Nash". ACM Transactions on Economics and Computation . 7 (3): 12:1–12:32. doi : 10.1145/3355902 . ISSN 2167-8375. S2CID 202729326.
^ Lipton, RJ; Markakis, E.; Mossel, E.; Saberi, A. (2004). "Sobre asignaciones aproximadamente justas de bienes indivisibles". Actas de la 5.ª conferencia de la ACM sobre comercio electrónico - EC '04 . pág. 125. doi :10.1145/988772.988792. ISBN 1-58113-771-0.
^ Budish, Eric (2011). "El problema de asignación combinatoria: equilibrio competitivo aproximado a partir de ingresos iguales". Revista de economía política . 119 (6): 1061–1103. doi :10.1086/664613. S2CID 154703357.
^ Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (1 de marzo de 2014). "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–289. doi :10.1007/s10458-013-9224-2. ISSN 1573-7454. S2CID 442666.
^ Lee, Euiwoong (1 de junio de 2017). "Dureza APX de la maximización del bienestar social de Nash con elementos indivisibles". Information Processing Letters . 122 : 17–20. arXiv : 1507.01159 . doi :10.1016/j.ipl.2017.01.012. ISSN 0020-0190. S2CID 14267752.
^ Cole, Richard; Gkatzelis, Vasilis (2015). "Aproximación del bienestar social de Nash con elementos indivisibles". Actas del cuadragésimo séptimo simposio anual de la ACM sobre teoría de la computación - STOC '15 . págs. 371–380. doi :10.1145/2746539.2746589. ISBN 9781450335362. Número de identificación del sujeto 52817863.
^ Anari, Nima; Gharan, Shayan Oveis; Saberi, Amin; Singh, Mohit (2017). Papadimitriou, Christos H. (ed.). "Bienestar social de Nash, polinomios estables y permanentes de matriz". 8.ª Conferencia sobre innovaciones en informática teórica (ITCS 2017) . Leibniz International Proceedings in Informatics (LIPIcs). 67. Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 36:1–36:12. doi : 10.4230/LIPIcs.ITCS.2017.36 . ISBN . 978-3-95977-029-3.S2CID2076238 .
^ Cole, Richard; Devanur, Nikhil R.; Gkatzelis, Vasilis; Jain, Kamal; Mai, Tung; Vazirani, Vijay V.; Yazdanbod, Sadra (2016). "Dualidad de programas convexos, mercados de Fisher y bienestar social de Nash". Actas de la Conferencia ACM de 2017 sobre economía y computación . págs. 459–460. arXiv : 1609.06654 . doi :10.1145/3033274.3085109. ISBN. 978-1-4503-4527-9.S2CID14525165 .
^ abcd Barman, Siddharth; Sanath Kumar Krishnamurthy; Vaish, Rohit (2017). "Encontrar asignaciones justas y eficientes". Actas de la Conferencia ACM de 2018 sobre Economía y Computación . págs. 557–574. arXiv : 1707.04731 . doi :10.1145/3219166.3219176. ISBN 978-1-4503-5829-3.S2CID20538449 .
^ McGlaughlin, Peter; Garg, Jugal (14 de mayo de 2020). "Mejora de las aproximaciones de bienestar social de Nash". Revista de investigación en inteligencia artificial . 68 : 225–245. doi : 10.1613/jair.1.11618 . ISSN 1076-9757. S2CID 218762446.
^ Caragiannis, Ioannis; Gravin, Nick; Huang, Xin (17 de junio de 2019). "Libre de envidia hasta cualquier artículo con alto bienestar de Nash: la virtud de donar artículos". Actas de la Conferencia ACM de 2019 sobre Economía y Computación . EC '19. Phoenix, AZ, EE. UU.: Association for Computing Machinery. págs. 527–545. arXiv : 1902.04319 . doi :10.1145/3328526.3329574. ISBN 978-1-4503-6792-9.S2CID60441171 .
^ Amanatidis, Georgios; Birmpas, Georgios; Filos-Ratsikas, Aris; Hollender, Alexandros; Voudouris, Alexandros A. (8 de abril de 2021). "El bienestar máximo de Nash y otras historias sobre EFX". Ciencias de la Computación Teórica . 863 : 69–85. arXiv : 2001.09838 . doi :10.1016/j.tcs.2021.02.020. ISSN 0304-3975. S2CID 210920309.
^ Halpern, Daniel; Procaccia, Ariel D.; Psomas, Alexandros; Shah, Nisarg (2020). "División justa con valoraciones binarias: una regla para gobernarlas a todas". En Chen, Xujin; Gravin, Nikolai; Hoefer, Martin; Mehta, Ruta (eds.). Economía de la Web e Internet . Apuntes de clase en Ciencias de la Computación. Vol. 12495. Cham: Springer International Publishing. págs. 370–383. arXiv : 2007.06073 . doi :10.1007/978-3-030-64946-3_26. ISBN . 978-3-030-64946-3. Número de identificación del sujeto 220496489.
^ Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). La justicia irrazonable del bienestar máximo de Nash (PDF) . Actas de la Conferencia ACM de 2016 sobre Economía y Computación - EC '16. p. 305. doi :10.1145/2940716.2940726. ISBN 9781450339360.
^ Bei, Xiaohui; Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt (2017). "Límites de ganancias en mercados de Fisher con utilidades de restricción de gasto". En Bilò, Vittorio; Flammini, Michele (eds.). Teoría de juegos algorítmicos . Apuntes de clase en informática. Vol. 10504. Cham: Springer International Publishing. págs. 67–79. doi :10.1007/978-3-319-66700-3_6. ISBN 978-3-319-66700-3.
^ Anari, Nima.; Mai, Tung.; Gharan, Shayan Oveis.; Vazirani, Vijay V. (1 de enero de 2018), "Bienestar social de Nash para elementos indivisibles bajo utilidades cóncavas lineales por partes separables [ ¿sic ? ]", Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos , Society for Industrial and Applied Mathematics, págs. 2274–2290, arXiv : 1612.05191 , doi : 10.1137/1.9781611975031.147 , ISBN 978-1-61197-503-1, Número de identificación del sujeto 15771549
^ Ortega, Josué (1 de enero de 2020). "Asignación de unidades múltiples bajo preferencias dicotómicas". Ciencias Sociales Matemáticas . 103 : 15–24. arXiv : 1703.10897 . doi :10.1016/j.mathsocsci.2019.11.003. ISSN 0165-4896. S2CID 3479888.
^ Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt (enero de 2018), "Aproximación del bienestar social de Nash con valoraciones aditivas al presupuesto", Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos , Society for Industrial and Applied Mathematics, págs. 2326-2340, doi : 10.1137/1.9781611975031.150 , hdl : 11858/00-001M-0000-002D-E7D6-2 , ISBN 978-1-61197-503-1, S2CID1282865
^ Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (17 de marzo de 2020). "Encontrar asignaciones justas y eficientes cuando las valoraciones no cuadran". Teoría de juegos algorítmicos . Apuntes de clase en informática. Vol. 12283. págs. 32–46. arXiv : 2003.07060 . doi :10.1007/978-3-030-57980-7_3. ISBN . 978-3-030-57979-1. Número de identificación del sujeto 208328700.
^ Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (27 de julio de 2020). "Mecanismos justos y veraces para valoraciones dicotómicas". arXiv : 2002.10704 [cs.GT].
^ Aleksandrov, Martin; Walsh, Toby (17 de diciembre de 2019). "Algoritmos voraces para la división justa de maná mixto". arXiv : 1911.11005 [cs.AI].
^ ab Barman, Siddharth; Krishnamurthy, Sanath Kumar; Vaish, Rohit (11 de mayo de 2018). "Encontrar asignaciones justas y eficientes". arXiv : 1707.04731 [cs.GT].
^ ab Aziz, Haris; Caragiannis, Ioannis; Igarashi, Ayumi; Walsh, Toby (11 de diciembre de 2018). "Asignación justa de combinaciones de bienes y tareas indivisibles". arXiv : 1807.10684 [cs.GT].
^ Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2016). "Toma de decisiones públicas justa". Actas de la Conferencia ACM de 2017 sobre economía y computación . págs. 629–646. arXiv : 1611.04034 . doi :10.1145/3033274.3085125. ISBN. 978-1-4503-4527-9. Número de identificación del sujeto 30188911.
^ Barman, Siddharth; Krishnamurthy, Sanath Kumar (17 de julio de 2019). "Sobre la proximidad de los mercados con equilibrios integrales". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 33 (1): 1748–1755. arXiv : 1811.08673 . doi : 10.1609/aaai.v33i01.33011748 . ISSN 2374-3468. S2CID 53793188.
^ Brânzei, Simina; Sandomirskiy, Fedor (3 de julio de 2019). "Algoritmos para la división competitiva de tareas". arXiv : 1907.01766 [cs.GT].
^ Aziz, Haris; Moulin, Herve; Sandomirskiy, Fedor (2019-09-02). "Un algoritmo de tiempo polinomial para calcular una asignación Pareto óptima y casi proporcional". arXiv : 1909.00740 [cs.GT].
^ Herreiner, Dorothea K.; Puppe, Clemens D. (1 de julio de 2009). "Libre de envidia en problemas experimentales de división justa". Teoría y decisión . 67 (1): 65–100. doi :10.1007/s11238-007-9069-8. hdl : 10419/22905 . ISSN 1573-7187. S2CID 154799897.
^ Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (18 de agosto de 2014). "Casi justicia en matroides". Actas de la 21.ª Conferencia Europea sobre Inteligencia Artificial . ECAI'14. Praga, República Checa: IOS Press: 393–398. ISBN 978-1-61499-418-3.
^ Suksompong, Warut (15 de mayo de 2019). "Asignación justa de bloques contiguos de elementos indivisibles". Matemáticas Aplicadas Discretas . 260 : 227–236. arXiv : 1707.00345 . doi :10.1016/j.dam.2019.01.036. ISSN 0166-218X. S2CID 126658778.
^ Freeman, Rupert; Sikdar, Sujoy; Vaish, Rohit; Xia, Lirong (25 de mayo de 2019). "Asignaciones equitativas de bienes indivisibles". arXiv : 1905.10656 [cs.GT].
^ ab Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (17 de junio de 2019). "Asignación justa de alta multiplicidad: Lenstra potenciada por programación entera N-fold". Actas de la Conferencia ACM de 2019 sobre economía y computación . EC '19. Phoenix, AZ, EE. UU.: Association for Computing Machinery. págs. 505–523. doi :10.1145/3328526.3329649. ISBN 978-1-4503-6792-9.S2CID 195298520 .
^ Dignum, Frank (3 de mayo de 2021). Asignación justa de alta multiplicidad más práctica. Aamas '21. págs. 260–268. ISBN 9781450383073.

Véase también

División eficiente y sin envidias : para recursos divisibles. No hay necesidad de aproximaciones, ya que es posible lograr una equidad exacta.
Asignación de artículos sin envidia , sin el requisito de PE.
Armonía en el alquiler : con una restricción adicional: cada agente debe recibir un solo artículo.