Maximizar la cuota

Criterio de asignación justa de ítems

La participación máxima (MMS) es un criterio de asignación justa de ítems . Dado un conjunto de ítems con diferentes valores, la participación máxima de 1 de n es el valor máximo que se puede obtener al dividir los ítems en partes y tomar la parte con el valor mínimo. Una asignación de ítems entre agentes con diferentes valoraciones se llama justa MMS si cada agente obtiene un paquete que es al menos tan bueno como su participación máxima de 1 de n . La equidad MMS es una relajación del criterio de proporcionalidad : cada agente obtiene un paquete que es al menos tan bueno como la división igualitaria ( de cada recurso). La proporcionalidad se puede garantizar cuando los ítems son divisibles, pero no cuando son indivisibles, incluso si todos los agentes tienen valoraciones idénticas. Por el contrario, la equidad MMS siempre se puede garantizar a agentes idénticos, por lo que es una alternativa natural a la proporcionalidad incluso cuando los agentes son diferentes. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 1/n}$

Motivación y ejemplos

Artículos idénticos. Supongamos primero que los artículos idénticos deben distribuirse de manera justa entre las personas. Lo ideal sería que cada persona recibiera artículos, pero esto puede ser imposible si no es divisible por , ya que los artículos son indivisibles. Un segundo criterio de equidad natural es redondear hacia abajo al entero más cercano y dar a cada persona al menos artículos. Recibir menos de artículos es "demasiado injusto": es una injusticia que no se justifica por la indivisibilidad de los artículos. ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m/n}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m/n}$ ${\displaystyle \lfloor m/n\rfloor }$ ${\displaystyle \lfloor m/n\rfloor }$

Diferentes elementos. Supongamos ahora que los elementos son diferentes y que cada elemento tiene un valor diferente. Por ejemplo, supongamos que y y los valores de los elementos son , sumando . Si los elementos fueran divisibles, le daríamos a cada persona un valor de (o, si fueran divisibles solo a valores enteros como en el párrafo anterior, al menos ), pero esto no es posible. El valor más grande que se puede garantizar a los tres agentes es 7, por la partición . De manera informal, es el valor total dividido por "redondeado hacia abajo al elemento más cercano". ${\displaystyle n=3}$ ${\displaystyle m=5}$ ${\displaystyle 1,3,5,6,9}$ ${\displaystyle 24}$ ${\displaystyle 24/3=8}$ ${\displaystyle \lfloor 24/3\rfloor =8}$ ${\displaystyle \{1,6\},\{3,5\},\{9\}}$ ${\displaystyle 7}$ ${\displaystyle n}$

El conjunto que alcanza este valor maximin se denomina "1 de cada 3 maximin-share" (cuota maximin 1 de cada 3): es el mejor subconjunto de elementos que se puede construir dividiendo el conjunto original en partes y tomando la parte menos valiosa. Por lo tanto, en este ejemplo, una asignación es justa para MMS si le da a cada agente un valor de al menos . ${\displaystyle \{1,6\}}$ ${\displaystyle 3}$ ${\displaystyle 7}$

Diferentes valoraciones. Supongamos ahora que cada agente asigna un valor diferente a cada artículo, por ejemplo:

• Alicia los valora en ; ${\displaystyle 1,3,5,6,9}$
• George los valora en ; ${\displaystyle 1,7,2,6,8}$
• Dina los valora en . ${\displaystyle 1,1,1,4,17}$

Ahora, cada agente tiene un MMS diferente:

• El MMS de Alice sigue siendo el mismo que se indica arriba; ${\displaystyle 7}$
• El MMS de George es , por la partición (todos estos paquetes son equivalentes para él); ${\displaystyle 8}$ ${\displaystyle \{1,7\},\{2,6\},\{8\}}$
• El MMS de Dina es , por la partición . ${\displaystyle 3}$ ${\displaystyle \{1,1,1\},\{4\},\{17\}}$

Aquí, una asignación es MMS-justa si le da a Alice un valor de al menos , a George un valor de al menos y a Dina un valor de al menos . Por ejemplo, darle a George los dos primeros elementos , a Alice los dos siguientes y a Dina el último elemento es MMS-justa. ${\displaystyle 7}$ ${\displaystyle 8}$ ${\displaystyle 3}$ ${\displaystyle \{1,7\}}$ ${\displaystyle \{5,6\}}$ ${\displaystyle \{17\}}$

Interpretación . La MMS de 1 de cada 100 de un agente puede interpretarse como la utilidad máxima que un agente puede esperar obtener de una asignación si todos los demás agentes tienen las mismas preferencias, cuando él siempre recibe la peor parte. Es la utilidad mínima a la que un agente podría sentirse con derecho, basándose en el siguiente argumento: si todos los demás agentes tienen las mismas preferencias que yo, hay al menos una asignación que me da esta utilidad y hace que todos los demás agentes estén (débilmente) mejor; por lo tanto, no hay razón para darme menos. ${\displaystyle n}$

Una interpretación alternativa es: el paquete más preferido que el agente podría garantizar como divisor en divide y elige contra oponentes adversarios: el agente propone su mejor asignación y deja que todos los demás elijan una parte antes de tomar la restante.

La equidad MMS también puede describirse como el resultado del siguiente proceso de negociación. Se sugiere una determinada asignación. Cada agente puede oponerse a ella sugiriendo una distribución alternativa de los elementos. Sin embargo, al hacerlo debe dejar que todos los demás agentes elijan su parte antes que él. Por lo tanto, un agente se opondría a una asignación solo si puede sugerir una distribución en la que todos los paquetes sean mejores que su paquete actual. Una asignación es equitativa MMS si ningún agente se opone a ella, es decir, para cada agente, en cada distribución existe un paquete que es ligeramente peor que su parte actual.

Historia

Theodore Hill ^[1] estudió la participación máxima en 1987. Presentó un límite inferior para la participación máxima de un agente en función del valor del ítem más grande y demostró que siempre existe una asignación en la que cada agente recibe al menos este límite inferior. Nótese que la participación máxima real puede ser mayor que el límite inferior, por lo que la asignación encontrada por el método de Hill puede no ser justa para MMS.

Budish ^[2] estudió la equidad MMS en 2011, en el contexto de la asignación de cursos . Presentó el mecanismo A-CEEI , que logra una asignación aproximadamente equitativa a la MMS si se le permite agregar algunos bienes. En 2014, Procaccia y Wang ^[3] demostraron que puede no existir una asignación equitativa a la MMS exacta entre tres o más agentes.

Definición formal

Sea un conjunto que representa el recurso que se va a asignar. Sea cualquier función de valor real sobre subconjuntos de , que represente su "valor". La participación máxima de 1 de n de from se define como: ${\displaystyle C}$ ${\displaystyle v}$ ${\displaystyle C}$ ${\displaystyle v}$ ${\displaystyle C}$

${\displaystyle \operatorname {MMS} _{v}^{1{\text{-out-of-}}n}(C):=~~~\max _{(Z_{1},\ldots ,Z_{n})\in \operatorname {Partitions} (C,n)}~~~\min _{j\in [n]}~~~v(Z_{j})}$

Aquí, el máximo es sobre todas las particiones de en subconjuntos disjuntos, y el mínimo es sobre todos los subconjuntos en la partición. En los ejemplos anteriores, era un conjunto de números enteros, y era la función suma, es decir, se definió como la suma de los números enteros en . Por ejemplo, mostramos que , donde la partición maximizadora es . En un problema típico de asignación justa, hay algunos agentes diferentes con diferentes funciones de valor sobre el mismo recurso . El valor 1 de MMS de agente se denota por . Una asignación es un vector de n subconjuntos disjuntos por pares de -- un subconjunto por agente. Una asignación se llama MMS-justa , o simplemente una asignación MMS , si para cada agente , ${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle C}$ ${\displaystyle v}$ ${\displaystyle v(Z)}$ ${\displaystyle Z}$ ${\displaystyle \operatorname {MMS} _{v}^{1{\text{-out-of-}}3}(\{1,3,5,6,9\}):=7}$ ${\displaystyle \{1,6\},\{3,5\},\{9\}}$ ${\displaystyle n}$ ${\displaystyle v_{1},\dots ,v_{n}}$ ${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C):=\operatorname {MMS} _{v_{i}}^{1{\text{-out-of-}}n}(C)}$ ${\displaystyle C}$ ${\displaystyle Z_{1},\dots ,Z_{n}}$ ${\displaystyle i}$

${\displaystyle v_{i}(Z_{i})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)}$.

Una asignación se denomina partición MMS de agente si se cumple que para todos , es decir, la asignación es una de las particiones que maximiza la fórmula para el MMS de . ${\displaystyle i}$ ${\displaystyle v_{i}(Z_{j})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)}$ ${\displaystyle j}$ ${\displaystyle i}$

Límite inferior

Hill ^[1] demostró que, si el valor de cada elemento de un agente es, en la mayoría de los casos, el MMS de 1 de n de ese agente es al menos , donde es la siguiente función lineal por partes : ${\displaystyle \alpha }$ ${\displaystyle V_{n}(\alpha )}$ ${\displaystyle V_{n}(\alpha )}$

${\displaystyle V_{n}(\alpha )=1-k\cdot (n-1)\cdot \alpha }$ para todos , para todos . ${\displaystyle \alpha \in \left[{\frac {1}{k(n-1/(k+1))}},{\frac {1}{k(n-1/k)}}\right]}$ ${\displaystyle k\geq 1}$

Tenga en cuenta que es una función continua y no creciente de , con y (consulte el documento para ver un gráfico de y ) ${\displaystyle V_{n}(\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle V_{n}(0)=1/n}$ ${\displaystyle V_{n}(1)=0}$ ${\displaystyle V_{2}(\alpha )}$ ${\displaystyle V_{3}(\alpha )}$

Hill también demostró que, para cada n y , y para cualesquiera n agentes que valoran cada elemento en la mayoría de los casos el valor total, existe una partición en la que cada agente recibe un valor de al menos . Además, esta garantía es estricta: para cada n y , hay casos en los que es imposible garantizar más de a todos, incluso cuando todas las valoraciones son idénticas. ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle V_{n}(\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle V_{n}(\alpha )}$

Markakis y Psomas ^[4] reforzaron la garantía de Hill y proporcionaron un algoritmo de tiempo polinomial para calcular una asignación que satisface esta garantía más fuerte. También demostraron que ningún mecanismo veraz puede obtener una aproximación de 2/3 a esta garantía y presentar una aproximación veraz de factor constante para un número limitado de bienes. Gourves, Monnot y Tlilane ^[5] ampliaron el algoritmo de Markakis y Psomas para obtener una garantía de equidad más estricta, que funciona para el problema más general de asignar una base de un matroide .

Li, Moulin, Sun y Zhou ^[6] extendieron el límite inferior de Hill a los males y presentaron un límite más preciso que depende también del número de males. También presentaron un algoritmo de tiempo polinomial que alcanza este límite.

Existencia de asignaciones justas para el MMS

Es posible que no exista una asignación justa de MMS. Procaccia y Wang ^[3] y Kurokawa ^[7] construyeron una instancia con agentes e ítems, en la que ninguna asignación garantiza a cada agente el MMS de 1 de 3. Nótese que esto no contradice el resultado de Hill, ya que el MMS de todos los agentes puede ser estrictamente mayor que el límite inferior de Hill . En su instancia, hay objetos, indexados por y . Cada agente valora cada objeto por: ${\displaystyle n=3}$ ${\displaystyle m=12}$ ${\displaystyle V_{n}(\alpha )}$ ${\displaystyle 12}$ ${\displaystyle i\in [3]}$ ${\displaystyle j\in [4]}$ ${\displaystyle k}$ ${\displaystyle (i,j)}$

${\displaystyle v_{k}(i,j)=1,000,000+1,000\cdot T_{i,j}+E_{i,j}^{(k)}}$

donde son matrices particulares de 3 por 4 con valores menores que . Demuestran que cada agente puede dividir los objetos en subconjuntos de objetos cada uno, de modo que la suma de valores en cada subconjunto sea 4.055.000, que es por lo tanto el MMS de todos los agentes. Demuestran que cada asignación de MMS debe dar exactamente 4 objetos particulares a cada agente, pero tal asignación no existe. Por lo tanto, cada asignación da al menos a un agente un valor de como máximo 4.054.999. Generalizaron este caso y demostraron que para cada existe un caso con elementos. ${\displaystyle T,E^{(1)},E^{(2)},E^{(3)}}$ ${\displaystyle 100}$ ${\displaystyle 3}$ ${\displaystyle 4}$ ${\displaystyle n\geq 3}$ ${\displaystyle 3n+4}$

Feige, Sapir y Tauber ^[8] mejoraron el resultado de no existencia, construyendo una instancia con agentes e ítems, en la que no hay asignación de MMS. En esta instancia, cada agente tiene un MMS de 40, pero solo es posible garantizar los ítems del agente peor posicionado con un valor combinado de 39. También muestran que para cualquier , hay una instancia con ítems para los que no existe una asignación de MMS. Si es par, mejoran el límite a los ítems. Para estas instancias, el peor agente puede, como máximo, recibir una parte de su MMS. ${\displaystyle n=3}$ ${\displaystyle m=9}$ ${\displaystyle n\geq 3}$ ${\displaystyle 3n+3}$ ${\displaystyle n}$ ${\displaystyle 3n+1}$ ${\displaystyle 1-1/n^{4}}$

Si bien no se garantiza la existencia de asignaciones de MMS, se ha demostrado que, en casos aleatorios, existen asignaciones de MMS con una alta probabilidad . Kurokawa, Procaccia y Wang ^[9] demostraron que esto es válido para dos casos:

• Hay muchos ítems: para alguna constante que depende de la distribución de probabilidad. Entonces, por un resultado previo, ^[10] existe una asignación de ítem libre de envidia con alta probabilidad; dicha asignación es siempre MMS. ${\displaystyle m\geq \alpha \cdot n\ln {n}}$ ${\displaystyle \alpha }$
• Hay pocos elementos: [nótese que este caso se superpone parcialmente al caso anterior]. Para este caso, presentan un algoritmo llamado borrador emparejado . Se basa en construir un gráfico bipartito de agentes vs. elementos, y encontrar en él un emparejamiento perfecto . Demuestran que (1) la probabilidad de que el borrador emparejado tenga éxito tiende a 1 ya que tiende a infinito. (2) Si el borrador emparejado tiene éxito, entonces el valor de cada agente es al menos su MMS. ${\displaystyle m<n^{8/7}}$ ${\displaystyle n}$

Amanatidis, Markakis, Nikzad y Saberi ^[11] también prueban que, en instancias generadas aleatoriamente, existen asignaciones MMS-justas con alta probabilidad .

Para muchas clases de instancias, se ha demostrado que siempre existen asignaciones MMS. Cuando todos los n agentes tienen valoraciones idénticas, siempre existe una asignación MMS por definición (todos los agentes tienen las mismas particiones MMS). Un caso ligeramente más general en el que existe una asignación MMS es cuando algunos agentes tienen valoraciones idénticas. Una asignación MMS se puede encontrar entonces mediante dividir y elegir : los agentes idénticos dividen los elementos en paquetes, cada uno de los cuales es al menos tan bueno como su MMS; el -ésimo agente elige el paquete con el valor más alto; y los agentes idénticos toman los paquetes restantes. En particular, con dos agentes, siempre existe una asignación MMS. ${\displaystyle n-1}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n-1}$

Bouveret y Lemaître ^[12] demostraron que existen asignaciones MMS en los siguientes casos:

• Valoraciones binarias : a cada agente le gusta un artículo (lo valora en ) o no le gusta (lo valora en ). ${\displaystyle 1}$ ${\displaystyle 0}$
• Multiconjuntos idénticos : los agentes pueden valorar los elementos de manera diferente, pero los multiconjuntos de valores de los agentes son los mismos.
• Pocos artículos – . ${\displaystyle m\leq n+3}$

El último resultado fue mejorado posteriormente por Kurokawa, Procaccia y Wang ^[9] y por Feige, Sapir y Tauber ^[8] . Debido al ejemplo negativo con tres agentes y nueve elementos, esta es la constante más grande que existe, de modo que todas las instancias con agentes y elementos siempre tienen asignaciones MMS, sin importar el valor de . Hummel ^[13] demostró además que existen asignaciones MMS en los siguientes casos: ${\displaystyle m\leq n+4}$ ${\displaystyle m\leq n+5}$ ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle m\leq n+c}$ ${\displaystyle n}$

• Hay artículos y agentes. ${\displaystyle m\leq n+6}$ ${\displaystyle n\neq 3}$
• Hay artículos y agentes. ${\displaystyle m\leq n+7}$ ${\displaystyle n\geq 8}$
• Hay artículos y agentes. ${\displaystyle m\leq n+c}$ ${\displaystyle n\geq \lfloor 0.6597c(c!)\rfloor }$

Amanatidis, Markakis, Nikzad y Saberi ^[11] demostraron que las asignaciones MMS existen y se pueden encontrar en tiempo polinomial para el caso de valoraciones ternarias , en las que cada elemento se valora en 0, 1 o 2.

Uriel Feige ^[14] demostró que las asignaciones MMS siempre existen en instancias bivaluadas , en las que hay dos valores a y b , y cada agente valora cada elemento en a o b .

Aproximaciones

Budish ^[2] introdujo una aproximación al MMS 1-de -n (el MMS 1-de-( ${\displaystyle n+1}$ )): cada agente recibe al menos tanto como podría obtener al dividirlo en n +1 paquetes y obtener el peor. En general, para cualquier d > n , se puede considerar el MMS 1-de-d como una aproximación al MMS 1-de -n y buscar una asignación en la que, para cada agente i :

${\displaystyle V_{i}(Z_{i})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}d}(C)}$

Obsérvese que el valor del MMS 1-de-d es una función débilmente decreciente de d . Esto se denomina aproximación ordinal , ya que depende únicamente de la clasificación de los paquetes y no de sus valores precisos. Procaccia y Wang ^[3] introdujeron un tipo diferente de aproximación: la aproximación multiplicativa al MMS: una asignación es r-fracción MMS -justa, para alguna fracción r en [0,1], si el valor de cada agente es al menos una fracción r del valor de su MMS, es decir, para cada agente i :

${\displaystyle V_{i}(Z_{i})\geq r\cdot \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)}$

Supongamos que se puede elegir entre dos algoritmos: el primero garantiza una aproximación multiplicativa (por ejemplo, MMS de 3/4 fracciones), mientras que el segundo garantiza una aproximación ordinal (por ejemplo, MMS de 1 de (3 n /2)). ¿Cuál de las dos garantías es mayor? La respuesta depende de los valores.

• La aproximación multiplicativa es mayor, por ejemplo, cuando hay n bienes idénticos con un valor de 1. Entonces, el 1 de ${\displaystyle d}$ MMS es 0 para cualquier d > n , pero el 1 de ${\displaystyle n}$ MMS es 1, por lo que cualquier aproximación multiplicativa positiva es mejor.
• La aproximación ordinal es mayor, por ejemplo, cuando hay d bienes idénticos con un valor de 1, para algún d en { n + 1,...,2 n -1}. Entonces, el MMS 1-de-d es 1, y el MMS 1-de- ${\displaystyle n}$ también es 1, por lo que cualquier aproximación r -multiplicativa de él con r < 1 es peor.

En general, para cualquier entero k , el MMS 1-de- n es al menos k veces el MMS 1-de- nk : tome una partición MMS 1-de- nk óptima y agrupe los paquetes en n superpaquetes, cada uno de los cuales contiene k paquetes originales. Cada uno de estos superpaquetes vale al menos k veces el paquete original más pequeño. Por lo tanto, una aproximación 1/ k -multiplicativa es al menos tan grande como una aproximación ordinal 1-de- nk , pero puede ser menor que la aproximación ordinal 1-de-( nk- 1), como en el ejemplo anterior. En particular, cualquier aproximación r -multiplicativa para r ≥ 1/2 es al menos tan buena como la aproximación ordinal 1-de-(2 n ), pero podría ser peor que la aproximación ordinal 1-de-(2 n -1).

MMS - Asignación justa de bienes

Aproximaciones multiplicativas

Procaccia y Wang ^[3] presentaron un algoritmo que siempre encuentra una fracción r _n de MMS, donde

${\displaystyle r_{n}:={\frac {2\cdot {\text{oddfloor}}(n)}{3\cdot {\text{oddfloor}}(n)-1}}={\begin{cases}{\frac {2n}{3n-1}}&n~{\text{ odd}}\\{\frac {2n-2}{3n-4}}&n~{\text{ even}}\end{cases}}}$

donde oddfloor( n ) es el entero impar más grande menor o igual a n . En particular, r ₃ = r ₄ = 3/4, disminuye cuando n aumenta y siempre es mayor que 2/3. Su algoritmo se ejecuta en tiempo polinomial en m cuando n es constante, pero su tiempo de ejecución puede ser exponencial en n .

Amanatidis, Markakis, Nikzad y Saberi ^[11] presentaron varios algoritmos mejorados:

• Un algoritmo MMS de 1/2 fracción simple y rápido;
• Un algoritmo MMS de fracción 2/3 que se ejecuta en tiempo polinomial tanto en m como en n ;
• Un algoritmo MMS de fracción 7/8 para 3 agentes;

Barman y Krishnamurthy ^{[15] [16]} presentaron:

• Un algoritmo simple y rápido para MMS de fracción 2/3 con valoraciones aditivas . Su algoritmo se basa en "ordenar" la instancia (es decir, reducir la instancia a una en la que todos los agentes estén de acuerdo en la clasificación de los bienes) y luego ejecutar el procedimiento del gráfico de envidia comenzando por el bien más valioso. Su algoritmo puede verse como una adaptación del algoritmo de programación de tiempo de procesamiento más largo primero para agentes con diferentes valoraciones. Demuestran que el resultado es EFX y garantizan a cada agente su MMS, que es al menos 2/3. ${\displaystyle {\frac {2n}{3n-1}}}$
• Un algoritmo simple para MMS de fracción 1/10 para el caso más desafiante de valoraciones submodulares , basado en la asignación de artículos por turnos .

Ghodsi, Hajiaghayi, Seddighin, Seddighin y Yami ^[17] presentaron:

• Para valoraciones aditivas: una prueba de existencia de equidad MMS de 3/4 de fracción.
• Para n = 4 agentes aditivos: un algoritmo para una equidad MMS de fracción 4/5.
• Para valoraciones submodulares : un algoritmo de tiempo polinomial para equidad MMS de 1/3 de fracción y un límite superior de 3/4 de fracción.
• Para valoraciones XOS : un algoritmo de tiempo polinomial para equidad MMS de 1/8 de fracción, una prueba de existencia para 1/5 de fracción y un límite superior de 1/2 de fracción.
• Para valoraciones subaditivas : una prueba de existencia para una equidad MMS de log( m )/10-fracción y un límite superior de 1/2-fracción.

Garg, McGlaughlin y Taki ^[18] presentaron un algoritmo simple para la equidad MMS de fracción 2/3 cuyo análisis también es simple.

Garg y Taki ^[19] presentaron:

• Un algoritmo simple para MMS de fracción 3/4, que no necesita conocer el valor de MMS y, por lo tanto, se ejecuta en tiempo fuertemente polinomial.
• Una prueba de la existencia de la fracción MMS. ${\displaystyle ({\frac {3}{4}}+{\frac {1}{12n}})}$

Akrami, Garg, Sharma y Taki ^[20] mejoran el análisis del algoritmo presentado por Garg y Taki, simplificando el análisis y mejorando la garantía de existencia de . ${\displaystyle {\frac {3}{4}}+\min \left({\frac {1}{36}},{\frac {3}{16n-4}}\right)}$

Hasta la fecha, no se sabe cuál es el r más grande para que siempre exista una asignación de MMS de r -fracción. Puede ser cualquier número entre y . ${\displaystyle 3/4}$ ${\displaystyle 39/40}$

Aproximaciones ordinales

Budish ^[2] demostró que el equilibrio competitivo aproximado a partir de ingresos iguales siempre garantiza el MMS 1-de-( ${\displaystyle n+1}$ ). Sin embargo, esta asignación puede tener exceso de oferta y, lo que es más importante, exceso de demanda: la suma de los paquetes asignados a todos los agentes puede ser ligeramente mayor que el conjunto de todos los artículos. Un error de este tipo es razonable en la asignación de cursos , ya que un pequeño exceso de oferta se puede corregir añadiendo una pequeña cantidad de plazas. Pero el clásico problema de división justa supone que no se pueden añadir artículos.

Sin exceso de oferta y demanda, se conocen las siguientes aproximaciones:

• Una asignación MMS de bienes de 1 de (2 n -2) y una asignación MMS de tareas de 1 de (2 n /3), utilizando un emparejamiento sin envidia . ^[23]
• Una asignación MMS de bienes de 1 de (3 n /2), ^[24] que se puede calcular en politiempo cuando n <6.
• Una asignación MMS de bienes de 1 de (3 n /2) en tiempo polinomial y un resultado de existencia de asignación MMS de L de ([ L +1/2] n ). ^[16]
• Una asignación de tareas de MMS de 1 de (3 n /4). ^[25]

Hasta la fecha, no se sabe cuál es el valor más pequeño de d para que siempre exista una asignación de MMS de 1 de cada d . Puede ser cualquier número entre n + 1 y 3 n/ 2. El caso abierto más pequeño es n = 4.

Restricciones adicionales

Maximización del producto : Caragiannis, Kurokawa, Moulin, Procaccia, Shah y Wang ^[26] demostraron que la asignación máxima de bienestar de Nash (la asignación que maximiza el producto de las utilidades) es siempre -fracción MMS justa y es estricta. ${\displaystyle {\frac {2}{1+{\sqrt {4n-3}}}}}$

Veracidad : Amanatidis, Birmpas y Markakis ^[27] presentaron mecanismos veraces para asignaciones aproximadas de MMS justas (ver también División estratégica justa ):

• Para n agentes: un MMS de fracción 1/O( m ).
• Para 2 agentes: un MMS de 1/2 fracción y una prueba de que ningún mecanismo veraz puede alcanzar más de 1/2.

Restricciones de cardinalidad : los elementos se dividen en categorías y cada agente puede obtener como máximo k _h elementos de cada categoría h . En otras palabras, los paquetes deben ser conjuntos independientes de un matroide de partición .

• Barman y Biswas ^{[28] : 10} presentan un algoritmo que reduce el problema a un problema sin restricciones pero con valoraciones submodulares, y luego utilizan el algoritmo de ^[17] para lograr una equidad MMS de 1/3 de fracción.
• Hummel y Hetland ^[29] presentan un algoritmo de tiempo polinómico mejorado para la equidad de MMS de 1/2 fracción. Adaptan las técnicas y reducciones estándar del entorno sin restricciones al entorno con restricciones y luego aplican una variante de un procedimiento de llenado de bolsas.

Gráfico de conflictos : Hummel y Hetland ^[30] estudian otro escenario en el que hay un gráfico de conflictos entre elementos (por ejemplo: los elementos representan eventos y un agente no puede asistir a dos eventos simultáneos). Muestran que, si el grado del gráfico de conflictos es d y está en (2, n ), entonces se puede encontrar una asignación de MMS de 1/ d -fracción en tiempo polinomial, y siempre existe una asignación de MMS de 1/3-fracción.

Conectividad : los elementos están ubicados en un gráfico y cada parte debe ser un subgráfico conexo.

• Bouveret, Cechlarova, Elkind, Igarashi y Peters ^[31] demuestran que, si el grafo es acíclico, entonces siempre existe una asignación MMS-justa y se puede encontrar de manera eficiente. En los grafos generales, una asignación MMS-justa puede no existir y puede ser NP-difícil de encontrar.
• Lonc y Truszczynski ^[32] se centran en el caso en el que el gráfico es un ciclo y presentan un algoritmo para una asignación aproximadamente justa para MMS.

MMS - Distribución justa de tareas

Aziz, Rauchecker, Schryen y Walsh ^[33] extendieron la noción de MMS a las tareas domésticas (ítems con utilidades negativas). Nótese que, para las tareas domésticas, los factores de aproximación multiplicativa son mayores que 1 (ya que menos tareas tienen mayor utilidad) y los factores de aproximación ordinal son menores que n . Presentaron:

• Una prueba de que puede no existir una asignación de MMS para las tareas domésticas;
• Un algoritmo MMS de 2 fracciones para tareas domésticas;
• Algoritmos para encontrar la aproximación MMS óptima de una instancia dada, basados ​​en algoritmos para la partición de números de múltiples vías .

Barman y Krishnamurthy ^[16] presentaron un algoritmo que logra una MMS de 4/3 fracciones (precisamente, ). El algoritmo puede considerarse como una generalización del algoritmo LPT para la programación de máquinas idénticas. ${\displaystyle {\frac {4n-1}{3n}}}$

Huang y Lu ^[34] demuestran que siempre existe una asignación de tareas que sea justa en términos de MMS con una fracción de 11/9 y que se puede encontrar una asignación de tareas que sea justa en términos de MMS con una fracción de 5/4 en tiempo polinomial. Su algoritmo puede considerarse una generalización del algoritmo Multifit para la programación de máquinas idénticas.

Kulkarni, Mehta y Taki ^[35] estudian la asignación justa de MMS con valoraciones mixtas , es decir, cuando hay bienes y tareas. Demuestran que:

• ^{No es posible realizar una aproximación multiplicativa. Procaccia y Wang [3]} amplían el ejemplo de Procaccia y Wang añadiendo tres tareas con un valor de -4.054.999,75. El MMS de 1 de cada 3 de cada agente es 0,25 (cada paquete de MMS contiene cuatro bienes con una suma de 4.055.000 y una tarea). Sin embargo, cada asignación de los bienes le da al menos a un agente un valor de 4.054.999 como máximo de los bienes. Debemos dar una tarea a cada agente; por lo tanto, al menos un agente tiene un valor negativo.
• También presentan las condiciones bajo las cuales el cálculo de una asignación α-MMS y Pareto-óptima, para el mejor α posible en una instancia específica, se puede realizar en tiempo polinomial.

Ebadian, Peters y Shah ^[36] prueban que siempre existe una asignación MMS en instancias bivaluadas, cuando cada agente i divide las tareas en "fáciles" (valoradas en 1 para todos) o "difíciles" (valoradas en algún entero p _i > 1).

Técnicas y algoritmos

Se pueden aplicar varias normalizaciones al problema original sin cambiar la solución. A continuación, O es el conjunto de todos los objetos.

Escalada

Si, para cada agente i, todas las valoraciones se escalan por un factor (que puede ser diferente para distintos agentes), entonces el MMS para cada agente se escala por el mismo factor; por lo tanto, cada asignación de MMS en la instancia original es una asignación de MMS en la instancia escalada. Es común escalar las valoraciones de modo que el MMS de cada agente sea exactamente . Después de este escalamiento, los problemas de aproximación de MMS se pueden plantear como: ${\displaystyle k_{i}}$ ${\displaystyle 1}$

• ${\displaystyle r}$-fracción MMS : el valor total de es al menos ; necesitamos darle a cada uno de los agentes un paquete con un valor de al menos . ${\displaystyle O}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle r}$
• 1-de-d MMS : el valor total de es al menos ; necesitamos darle a cada uno de los agentes un paquete con un valor de al menos . ${\displaystyle O}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle 1}$

El escalamiento anterior requiere calcular el MMS de cada agente, lo que es un problema NP-hard ( partición de números multidireccional ). Un escalamiento alternativo, que se puede realizar más rápido, es: ^[18]

• ${\displaystyle r}$-fracción MMS : el valor total de es exactamente ; el MMS es como máximo ; necesitamos darle a cada uno de los agentes un paquete con un valor de al menos . ${\displaystyle O}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle r}$
• 1-de-d MMS : el valor total de es exactamente ; el MMS es como máximo ; necesitamos darle a cada uno de los agentes un paquete con un valor de al menos . ${\displaystyle O}$ ${\displaystyle d}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle 1}$

Asignar un objeto

Si eliminamos un objeto de . Entonces, para cada agente, el MMS -fuera de-( ) con respecto al conjunto restante es al menos su MMS -fuera de- con respecto al conjunto original . Esto se debe a que, en la partición MMS original, las partes permanecen intactas. ^[12] Ahora, supongamos que pretendemos dar a cada agente un valor de . Si algún objeto vale al menos para al menos un agente, entonces podemos dárselo a uno de esos agentes arbitrariamente y proceder a asignar los objetos restantes a los agentes restantes. Por lo tanto, podemos suponer que: ${\displaystyle o}$ ${\displaystyle O}$ ${\displaystyle 1}$ ${\displaystyle n-1}$ ${\displaystyle O\setminus o}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle O}$ ${\displaystyle n-1}$ ${\displaystyle r}$ ${\displaystyle o_{1}}$ ${\displaystyle r}$ ${\displaystyle o_{1}}$

• ${\displaystyle r}$-fracción MMS  : el valor de cada objeto para todos los agentes es menor que . ${\displaystyle r}$
• ${\displaystyle 1}$-de- MMS  : el valor de cada objeto para todos los agentes es menor que . ${\displaystyle d}$ ${\displaystyle 1}$

Esta normalización funciona incluso con escalamiento rápido y con valoraciones monótonas arbitrarias (incluso no aditivas). ^[17]

Relleno de bolsas

Denotemos un objeto, que es valorado como máximo por todos los agentes, como un " objeto -pequeño". Supongamos que todos los objetos son -pequeños. Tome una bolsa vacía y llénela con objeto tras objeto, hasta que la bolsa valga al menos para al menos un agente. Luego, entregue la bolsa a uno de esos agentes arbitrariamente. Dado que todos los objetos son -pequeños, los agentes restantes valoran la bolsa como máximo ; si este valor es suficientemente pequeño, entonces el valor restante es suficientemente grande para que podamos proceder recursivamente. ^[18] En particular, el llenado de bolsas da las siguientes soluciones: ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle r+s}$

• 1/2-fracción MMS  : toma ; tenga en cuenta que por la normalización anterior podemos suponer que todos los objetos son -pequeños. Inicialmente, hay n agentes y el valor total es al menos para ellos. Después de que se asigna una bolsa, los agentes restantes valoran los objetos restantes al menos , por lo que podemos proceder recursivamente. ^[17] ${\displaystyle s=r=1/2}$ ${\displaystyle 1/2}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-(r+s)=n-1}$
• 1-de-(2n) MMS  : tomar ; tenga en cuenta que, por la normalización anterior, podemos suponer que todos los objetos son -pequeños. Inicialmente, hay agentes y el valor total es al menos para ellos. Después de que se asigna una bolsa, los agentes restantes valoran los objetos restantes al menos , por lo que podemos proceder de forma recursiva. ${\displaystyle s=r=1}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle 2n}$ ${\displaystyle n-1}$ ${\displaystyle 2n-(r+s)=2n-2=2(n-1)}$

Estos algoritmos de llenado de bolsas funcionan incluso con el escalamiento rápido, por lo que se ejecutan en tiempo polinomial: no necesitan saber el valor MMS exacto. ^[18] De hecho, ambos algoritmos se pueden enunciar sin mencionar el MMS en absoluto:

• Todo agente para quien cada objeto vale como máximo el valor total, recibe como mínimo el valor total. ${\displaystyle 1/(2n)}$ ${\displaystyle 1/(2n)}$

Relleno de bolsa modificado : La condición de que todos los objetos sean -pequeños se puede relajar de la siguiente manera. ^[18] Tome algunos . Denote un objeto que no sea -pequeño (es decir, valorado al menos por al menos un agente) como un " objeto -grande". Suponga que como máximo los objetos son -grandes. Tome un objeto -grande , póngalo en una bolsa y llénela con objetos -pequeños hasta que un agente indique que vale para él al menos . Debe haber al menos un agente de este tipo, ya que algún agente valora en algún . Para este agente, quedan como máximo objetos -grandes. Por la normalización anterior, estos objetos siguen siendo -pequeños, por lo que su valor total para es como máximo , por lo que el valor de los objetos -pequeños restantes es al menos . ${\displaystyle s}$ ${\displaystyle s<r}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle o_{1}}$ ${\displaystyle s}$ ${\displaystyle r}$ ${\displaystyle i}$ ${\displaystyle o_{1}}$ ${\displaystyle x>s}$ ${\displaystyle n-1}$ ${\displaystyle s}$ ${\displaystyle r}$ ${\displaystyle i}$ ${\displaystyle r(n-1)}$ ${\displaystyle s}$ ${\displaystyle n-r(n-1)-x=r(n-1)+r-x\geq r-x}$

Realizar pedidos

Una instancia está ordenada si todos los agentes tienen el mismo ranking ordinal en los objetos, es decir, los objetos pueden ser numerados de tal manera que, para cada agente , . Intuitivamente, las instancias ordenadas son las más difíciles, ya que el conflicto entre agentes es mayor. De hecho, la instancia negativa de ^[3] está ordenada - el orden de los objetos está determinado por la matriz , que es la misma para todos los agentes. Esto también puede probarse formalmente. Supongamos que tenemos un algoritmo que encuentra, para cada instancia ordenada, una asignación de MMS de -fracción. Ahora, se nos da una instancia general de asignación de ítems . La resolvemos de la siguiente manera. ^{[12] [15]} ${\displaystyle o_{1},\dots ,o_{m}}$ ${\displaystyle i}$ ${\displaystyle v_{i}(o_{1})\geq \dots \geq v_{i}(o_{m})}$ ${\displaystyle T}$ ${\displaystyle r}$ ${\displaystyle P}$

1. Construya una instancia ordenada de la siguiente manera: para cada agente i , defina in como el -ésimo valor más alto en el conjunto de valores del agente in . Esto requiere tiempo. ${\displaystyle \mathrm {ord} (P)}$ ${\displaystyle v_{i}(o_{j})}$ ${\displaystyle \mathrm {ord} (P)}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle P}$ ${\displaystyle O(nm\lg m)}$
2. Encuentre una asignación de MMS de -fracción en . ${\displaystyle r}$ ${\displaystyle \mathrm {ord} (A)}$ ${\displaystyle \mathrm {ord} (P)}$
3. Construya una secuencia de selección en la que el agente que recibió seleccione primero, el agente que recibió seleccione segundo, etc. ${\displaystyle o_{1}}$ ${\displaystyle \mathrm {ord} (A)}$ ${\displaystyle o_{2}}$ ${\displaystyle \mathrm {ord} (A)}$
4. Dejemos que los agentes escojan sus mejores artículos de acuerdo con la secuencia de selección. Sea la asignación resultante. En , cada agente recibe exactamente la misma cantidad de artículos que en . Además, cada agente que recibió en , recibe uno de sus mejores artículos en . Por lo tanto, su valor por cada artículo que obtuvo en es al menos tan grande como su valor por el artículo correspondiente en . Por lo tanto, el valor de cada agente en es al menos tan alto como en . Dado que el orden no cambia los valores MMS, la nueva asignación sigue siendo -fracción MMS. ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle \mathrm {ord} (A)}$ ${\displaystyle o_{j}}$ ${\displaystyle \mathrm {ord} (A)}$ ${\displaystyle j}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle \mathrm {ord} (A)}$ ${\displaystyle A}$ ${\displaystyle \mathrm {ord} (A)}$ ${\displaystyle A}$ ${\displaystyle r}$

Entonces, cuando buscamos asignaciones de MMS de fracciones, podemos asumir que: ${\displaystyle r}$

• La clasificación ordinal de los objetos es la misma para todos los agentes.

Asignar dos objetos

Supongamos que encontramos dos objetos o ₁ y o ₂ , de los cuales un agente i valora al menos r , mientras que los otros agentes valoran como máximo 1. Entonces estos dos objetos pueden asignarse a i . Para los otros agentes, el MMS 1 de ( n -1) con respecto al conjunto restante es al menos su MMS 1 de n con respecto al conjunto original O . Esto se debe a que, en la partición MMS original, al menos n -2 partes permanecen intactas, mientras que las dos partes que no están intactas se pueden combinar para formar una sola parte con un valor de al menos 1. Esta normalización funciona solo con valoraciones aditivas. ^{[17] : Lem.3.2}

Además, supongamos que la instancia está ordenada, y supongamos que eliminamos de O los dos objetos o _n , o _{n +1} (es decir, los elementos de mayor valor n -ésimo y ( n +1)-ésimo). Entonces, para cada agente, el MMS 1 de ( n -1) con respecto al conjunto restante es al menos su MMS 1 de n con respecto al conjunto original O . Esto se debe a que, por el principio del palomar, al menos una parte MMS de cada agente debe contener dos o más objetos del conjunto { o ₁ , ..., o _{n +1} }. Estos elementos se pueden usar para reemplazar los objetos entregados, lo que da como resultado n -1 partes con un valor de al menos 1. Esto significa que, si los objetos o _n , o _{n +1} tienen un valor de al menos el MMS para algún agente i , podemos dárselos a i y proceder a asignar los objetos restantes a los agentes restantes. Por lo tanto, podemos suponer wlog que:

• Fracción r de MMS : el valor total de o _n , o _{n +1} para todos los agentes es menor que r . En particular, el valor de o _{n +1} y todos los objetos que le siguen en el ordenamiento es menor que r /2.
• 1-de-d MMS  : el valor total de od , o _{d +1} para todos los agentes es menor que 1. En particular, el valor de o _{d +1} y todos los objetos después de este en el ordenamiento es menor que 1/2.

Esta normalización funciona incluso con el escalamiento rápido. Al combinarla con el llenado de bolsas modificado se obtiene el siguiente algoritmo simple para MMS de 2/3 fracciones. ^[18]

• Siempre que un solo objeto valga al menos 2/3 para algún agente, asígnalo.
• Ordenar la instancia.
• Mientras o _n , o _{n +1} valgan al menos 2/3 para algún agente, asígnalos.
• Finalmente, hay como máximo n objetos con un valor de al menos 1/3; asígnelos utilizando el llenado de bolsas modificado.

La garantía de este algoritmo se puede afirmar incluso sin mencionar MMS:

• Todo agente para quien o ₁ vale como máximo 2/(3 n ) del valor total y o _n + o _n+1 valen juntos como máximo 2/(3 n ) del valor total, recibe al menos 2/(3 n ) del valor total.

Problemas algorítmicos

Algunos algoritmos básicos relacionados con el MMS son:

• Cálculo del MMS 1 de n de un agente determinado. Este es un problema de optimización NP-hard, pero tiene varios algoritmos de aproximación; consulte Partición de números multidireccional y Programación de máquinas idénticas .
• Decidir si una asignación dada es MMS-justa es co-NP completo para agentes con valoraciones aditivas (es en co-NP, ya que es posible probar en tiempo polinomial que una asignación dada no es MMS-justa, dada la partición MMS de uno de los agentes, lo que muestra que el valor MMS del agente es mayor que su valor en la asignación dada). ^[37]
• Decidir si una instancia dada admite cualquier asignación de MMS, dados los valores de MMS de todos los agentes. Está en NP ya que se puede verificar en tiempo polinomial dada la asignación; se desconoce su complejidad exacta en tiempo de ejecución.
  • Por lo tanto, decidir si una instancia dada admite cualquier asignación de MMS está en , es decir, se puede resolver en tiempo polinomial no determinista utilizando un oráculo para un problema NP (el oráculo es necesario para calcular el MMS de un agente). Sin embargo, la complejidad computacional exacta de este problema aún se desconoce: puede ser de nivel 2 o 1 o incluso 0 de la jerarquía polinomial . ^[12] ${\displaystyle NP^{NP}}$
• El problema de decisión de verificar si existe una asignación de participación minimax es NP-hard. Ambos problemas pueden ser aproximados por un PTAS , asumiendo que el número de agentes es fijo. Cuando las valoraciones de los agentes son binarias o aditivas y se basan en la puntuación de Borda , las asignaciones de participación maximin siempre pueden encontrarse de manera eficiente. Cuando sus valoraciones no son aditivas, hay casos en los que no existe una asignación MMS de r -fracción para ningún r positivo . Sin embargo, para una clase de utilidades submodulares simétricas, existe una asignación MMS ajustada de 1/2-fracción, y puede ser aproximada a un factor de 1/4. ^[38]

Relación con otros criterios de equidad

Una asignación se denomina libre de envidia excepto c elementos (EF c ) para un agente i si, para cada otro agente j , existe un conjunto de, como máximo, c elementos que, si se eliminan del conjunto de j , entonces i no envidia el resto. Una asignación EF0 se denomina simplemente libre de envidia . Las asignaciones EF1 se pueden encontrar, por ejemplo, mediante la asignación de elementos por turnos o mediante el procedimiento de grafo de envidia .

Una asignación se denomina proporcional-excepto-c-elementos (PROP* c ) para un agente i si existe un conjunto de, como máximo, c elementos fuera del paquete de i que, si se eliminan del conjunto de todos los elementos, i valora su paquete al menos 1/ n del resto. Una asignación PROP*0 se denomina simplemente proporcional .

EF0 implica PROP*0, y EF1 implica PROP*( n -1). Además, para cualquier entero c 0, EF c implica PROP*(( n -1) c ). ^{[39] : Lem.2.3} La implicación opuesta es verdadera cuando n = 2, pero no cuando n > 2.

Las siguientes aproximaciones de participación máxima están implícitas en PROP*( n -1), por lo tanto también en EF1: ^{[39] : Lem.2.7}

• Aproximación multiplicativa: 1/ n -fracción MMS (el 1/ n es ajustado); ^{[40] : Prop.3.6}
• Aproximación ordinal: 1-de-(2 n -1) MMS (el 2 n -1 es ajustado). De manera similar, para cada entero c , PROP* c implica 1-de-( c + n ) MMS.
• MMS cuando la función de valor es binaria. La implicación opuesta también es válida.

Las implicaciones anteriores se ilustran a continuación:

Una asignación se denomina libre de envidia excepto cualquier elemento (EF x ) para un agente i si, para cada otro agente j , para cualquier elemento individual eliminado del conjunto de j , i no envidia al resto. EFx es estrictamente más fuerte que EF1. Implica las siguientes aproximaciones MMS: ^{[40] : Prop.3.3-3.4}

• MMS fracción 2/3 para 2 o 3 agentes (es ajustado);
• MMS de fracción 4/7 para cualquier número de agentes (no se sabe si es estricto; el límite superior actual es 8/13).

MMS para grupos

Una asignación se denomina asignación de máxima participación equitativa por pares (PMMS-fair) si, por cada dos agentes i y j , el agente i recibe al menos su participación máxima de 1 de cada 2 restringida a los elementos recibidos por i y j . No se sabe si siempre existe una asignación PMMS, pero siempre existe una aproximación de 0,618. ^[26]

Una asignación se denomina justa en cuanto a la participación máxima en el grupo (GMMS-justa) si, para cada subgrupo de agentes de tamaño k , cada miembro del subgrupo recibe su participación máxima de 1 de k restringida a los elementos recibidos por este subgrupo. ^[41]

En las valoraciones aditivas, las distintas nociones de equidad se relacionan de la siguiente manera:

• La ausencia de envidia implica equidad GMMS; ^[41]
• La equidad GMMS implica equidad MMS (tomando el subgrupo de tamaño n ) y equidad PMMS (tomando subgrupos de tamaño 2);
• La equidad PMMS implica equidad 2/3-MMS para tres agentes y equidad 4/7-MMS en general; ^[40]
• La equidad PMMS implica EFX, lo que implica EF1.
• EF1 implica 1/2-PMMS y EFX implica 2/3-PMMS. ^{[40] : Prop.3.7-3.8} Por lo tanto, se puede encontrar una asignación de 1/2-PMMS en tiempo polinomial.
• La imparcialidad de MMS y la imparcialidad de PMMS no se implican entre sí.

Se garantiza la existencia de asignaciones GMMS cuando las valoraciones de los agentes son binarias o idénticas. Con valoraciones aditivas generales, existen asignaciones 1/2-GMMS y se pueden encontrar en tiempo polinomial. ^[41]

MMS para agentes con diferentes derechos

Cuando los agentes tienen diferentes derechos (también denominados: participaciones desiguales o derechos asimétricos ), la equidad del MMS debe adaptarse para garantizar una participación mayor a los agentes con mayores derechos. Se han sugerido varias adaptaciones. A continuación, suponemos que los derechos están dados por un vector , donde representa el derecho del agente . ${\displaystyle t=(t_{1},\ldots ,t_{n})}$ ${\displaystyle t_{i}}$ ${\displaystyle i}$

Equidad ponderada de MMS

Farhadi, Ghodsi, Hajiaghayi, Lahaie, Pennock, Seddighin y Seddigin ^[42] presentan la participación máxima ponderada (WMMS), definida por:

${\displaystyle \operatorname {WMMS} _{i}^{t}(C):=~~~\max _{(Z_{1},\ldots ,Z_{n})\in \operatorname {Partitions} (C,n)}~~~\min _{j\in [n]}~~~{\frac {t_{i}}{t_{j}}}V(Z_{j})=~~~t_{i}\cdot \max _{(Z_{1},\ldots ,Z_{n})\in \operatorname {Partitions} (C,n)}~~~\min _{j\in [n]}~~~{\frac {V(Z_{j})}{t_{j}}}}$

Intuitivamente, el WMMS óptimo se obtiene mediante una partición en la que el valor de la parte j es proporcional a la titularidad del agente j . Por ejemplo, supongamos que todas las funciones de valor son las sumas y el vector de titularidad es t = (1/6, 11/24, 9/24). Entonces, por la partición ({1,3},{5,6},{9}); es óptimo ya que el valor de cada parte es igual a . Por la misma partición, y . Cuando todas las n titularidades son iguales, . ${\displaystyle \operatorname {WMMS} _{1}^{t}(\{1,3,5,6,9\})=4}$ ${\displaystyle i}$ ${\displaystyle 24t_{i}}$ ${\displaystyle \operatorname {WMMS} _{2}^{t}=11}$ ${\displaystyle \operatorname {WMMS} _{3}^{t}=9}$ ${\displaystyle \operatorname {WMMS} _{i}^{t}\equiv \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}}$

Una asignación de C se denomina WMMS-justa para el vector de derechos t si el valor de cada agente i es al menos . Cuando todos los n agentes tienen valoraciones idénticas, siempre existe una asignación WMMS-justa por definición. Pero con diferentes valoraciones, la mejor aproximación multiplicativa posible es 1/ n . El límite superior se demuestra con el siguiente ejemplo con 2 n -1 bienes y n agentes, donde ε>0 es una constante muy pequeña: ${\displaystyle \operatorname {WMMS} _{i}^{t}(C)}$

Todos los agentes tienen una partición WMMS óptima: para los agentes "pequeños" (1, ..., n -1) es la partición ({1}, ..., { n -1}, { n }) y para el agente "grande" ( n ) es ({ n +1}, ..., {2 n -1}, {1, ..., n }). Por lo tanto, para todos los agentes i (a modo de comparación, observe que para los agentes pequeños, pero para el agente grande). ${\displaystyle \operatorname {WMMS} _{i}^{t}=t_{i}}$ ${\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}=\epsilon =t_{i}}$ ${\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}=[1-(n-1)\epsilon ]/n=t_{i}/n}$

En cualquier aproximación multiplicativa de WMMS, todos los agentes deben obtener un valor positivo. Esto significa que los agentes pequeños toman al menos n -1 de los elementos 1,..., n , por lo que, como máximo, queda un elemento de este tipo para el agente grande, y su valor es aproximadamente 1/ n en lugar de casi 1.

Siempre existe una asignación justa de WMMS de 1/ n -fracción y se puede encontrar mediante la asignación de ítems por turnos . En un caso restringido, en el que cada agente i valora cada bien como máximo , existe una asignación justa de WMMS de 1/2-fracción y se puede encontrar mediante un algoritmo similar al llenado de bolsas: las valoraciones de cada agente i se multiplican por ; y en cada iteración, se le da un ítem a un agente insatisfecho (un agente con valor menor que ) que lo valora más. Este algoritmo asigna a cada agente i como mínimo y como máximo . En la práctica, casi siempre existe una asignación justa de WMMS. ^[42] ${\displaystyle \operatorname {WMMS} _{i}^{t}}$ ${\displaystyle t_{i}/\operatorname {WMMS} _{i}^{t}}$ ${\displaystyle \operatorname {WMMS} _{i}^{t}/2}$ ${\displaystyle \operatorname {WMMS} _{i}^{t}/2}$ ${\displaystyle \operatorname {WMMS} _{i}^{t}}$

Equidad ordinal-MMS

Babaioff, Nisan y Talgam-Cohen ^[43] presentan una extensión natural de la aproximación MMS ordinal a agentes con diferentes derechos. Para dos enteros cualesquiera , conjunto C y función de valor V , defina ${\displaystyle l,d}$

${\displaystyle \operatorname {MMS} _{V}^{l{\text{-out-of-}}d}(C):=~~~\max _{P\in \operatorname {Partitions} (C,d)}~~~\min _{Z\in \operatorname {Unions} (P,l)}~~~V(Z)}$

Aquí, el máximo se encuentra sobre todas las particiones de C en subconjuntos disjuntos, y el mínimo se encuentra sobre todas las uniones de partes. Por ejemplo, por la partición ({1,6},{3,5},{9}). Ahora, la participación ordinal maximin (OMMS) se define por: ${\displaystyle d}$ ${\displaystyle l}$ ${\displaystyle \operatorname {MMS} _{V}^{2{\text{-out-of-}}3}(\{1,3,5,6,9\})=15}$

${\displaystyle \operatorname {OMMS} _{i}^{t}(C):=~~~\max _{l,d:~l/d\leq t_{i}}\operatorname {MMS} _{i}^{l{\text{-out-of-}}d}(C)}$

Por ejemplo, si el derecho del agente i es cualquier número real al menos tan grande como 2/3, entonces tiene derecho al menos a los 2 de 3 MMS de C . Nótese que, aunque hay infinitos pares que satisfacen con , solo un número finito de ellos no son redundantes (no implicado por otros), por lo que es posible calcular el OMMS en tiempo finito. ^[44] Una asignación Z ₁ ,..., Z _n se llama OMMS-justa para el vector de derecho w si el valor de cada agente i es al menos . ${\displaystyle l,d}$ ${\displaystyle l/d\leq t_{i}}$ ${\displaystyle \operatorname {OMMS} _{i}^{t}(C)}$

El OMMS puede ser mayor o menor que el WMMS, dependiendo de los valores: ^[44]

• Como ejemplo en el que WMMS es mayor, supongamos que C = {40, 60} y t = (0,4, 0,6) . Entonces, claramente WMMS ₁ = 40 y WMMS ₂ = 60, por lo que la única asignación justa para WMMS es la de 40 a 1 y la de 60 a 2. Sin embargo, OMMS ₁ = 0, ya que las fracciones que satisfacen son 1/3, 2/5, 3/7, etc., y en todos los casos, en cualquier partición de C en subconjuntos, hay al menos subconjuntos vacíos. Además, OMMS ₂ = 40, ya que las fracciones que satisfacen son 1/2, 2/4, 3/5, 4/7, etc., y en todos los casos, en cualquier partición de C en subconjuntos, los subconjuntos menos valiosos no contienen el 60. Por lo tanto, una asignación OMMS-justa podría dar el 40 a 2 y el 60 a 1, o no dar nada a 1, ambas situaciones parecen injustas. ${\displaystyle l/d\leq 0.4}$ ${\displaystyle d}$ ${\displaystyle l}$ ${\displaystyle l/d\leq 0.6}$ ${\displaystyle d}$ ${\displaystyle l}$
• Como ejemplo en el que OMMS es mayor, supongamos que C = {40, 60} y t = (0,2, 0,2, 0,6) . Entonces, WMMS _i = 0 para todos los i , ya que en cualquier partición de 3 de C , al menos un paquete está vacío. Por lo tanto, el criterio de equidad de WMMS es inútil. De manera similar, OMMS ₁ = OMMS ₂ = 0. Sin embargo, OMMS ₃ = 40 por el par y la partición ({40}, {60}), por lo que la equidad de OMMS requiere dar al menos un elemento al agente 3, lo que parece más justo. ${\displaystyle l/d=1/2}$

Equidad en AnyPrice-Share

Babaioff, Ezra y Feige ^[45] introdujeron un tercer criterio de equidad, al que denominan AnyPrice Share (APS) . Lo definen de dos maneras equivalentes; una de ellas es claramente un fortalecimiento de la participación maximin. En lugar de dividir los artículos en d paquetes disjuntos, el agente puede elegir cualquier conjunto de paquetes, que pueden superponerse. Pero, el agente debe asignar un peso a cada paquete de modo que la suma de los pesos sea al menos 1, y cada artículo pertenezca a paquetes cuyo peso total sea como máximo el derecho del agente. El APS es el valor del paquete de peso positivo menos valioso. Formalmente:

${\displaystyle \operatorname {APS} _{V}^{t}(C):=~~~\max _{P\in \operatorname {AllowedBundleSets} (C,t_{i})}~~~\min _{Z\in P}~~~V(Z)}$

donde el máximo se encuentra sobre todos los conjuntos de paquetes de modo que, para alguna asignación de pesos a los paquetes, el peso total de todos los paquetes es al menos 1, y el peso total de cada elemento es como máximo t _i . Existe un algoritmo de tiempo poliomial que garantiza a cada agente al menos 3/5 de su APS. ^[45]

El APS es siempre al menos tan alto como el OMMS: dada una partición óptima l -fuera de d , con l/d ≤ t _i , se puede asignar un peso de 1/ d a la unión de las partes 1,..., l , la unión de las partes 2,..., l +1, y así sucesivamente (de forma cíclica), de modo que cada parte esté incluida en exactamente l uniones. Por lo tanto, cada elemento pertenece a paquetes cuyo peso total es como máximo l / d , que es como máximo t _i . Al agente se le garantiza el paquete menos valioso de dichos paquetes, que es al menos el MMS l -fuera de d .

En algunos casos, el APS es estrictamente superior al OMMS. A continuación se ofrecen dos ejemplos:

• Un ejemplo simple con diferentes derechos: sea C = {2,1,1,1,0} y t _i = 2/5 . El OMMS es como máximo 1 (es suficiente comprobar l/d en {1/3, 2/5}). Pero el APS es 2, por los siguientes pesos: 0,4*{2}, 0,2*{1,1}, 0,2*{1,1}, 0,2*{1,1}. Nótese que la suma de los pesos es 1. El 2 aparece en un único conjunto con peso 0,4, mientras que cada uno de los 1 aparece en dos conjuntos con peso 0,2, 0,2.
• Un ejemplo más complejo con derechos iguales: sea C = {5, 5, 5, 7, 7, 7, 11, 17, 23, 23, 23, 31, 31, 31, 65} y t _i = 1/3 . El OMMS es igual al MMS de 1 de 3, y es como máximo 96; esto se puede verificar comprobando todas las 3 particiones. El APS es 97, ya que es posible construir 6 paquetes de 5 elementos cada uno, con un valor total de 97, de modo que cada elemento aparezca exactamente en dos paquetes. Luego, se puede asignar un peso de 1/6 a cada paquete.
  • Este ejemplo también muestra que una asignación de APS podría no existir incluso para 3 agentes con valoraciones idénticas y derechos iguales. Esto contrasta con el OMMS, que siempre existe con valoraciones idénticas y derechos iguales, y el WMMS, que siempre existe con valoraciones idénticas y derechos arbitrarios.

El APS puede ser mayor o menor que el WMMS; los ejemplos son los mismos que los utilizados para OMMS vs WMMS:

• WMMS es mayor: C = {40, 60} y t = (0,4, 0,6) . Entonces, WMMS ₁ = 40 y WMMS ₂ = 60. Pero APS ₁ = 0, ya que cada elemento debe tener un peso de como máximo 0,4, por lo que el paquete vacío debe tener un peso de al menos 0,2. Además, APS ₂ = 40, ya que cada elemento debe tener un peso de como máximo 0,6, por lo que {40} y el paquete vacío deben tener un peso total de al menos 0,4.
• El APS es mayor: C = {40, 60} y t = (0,2, 0,2, 0,6) . Entonces, WMMS _i = 0 para todos los i . De manera similar, APS ₁ = APS ₂ = 0 como se indicó anteriormente. Sin embargo, APS ₃ = 40, por ejemplo, por los pesos 0,5*{40}, 0,5*{60}.

Participación máxima en función del valor del artículo más grande

Theodore Hill ^[1] presentó una versión del MMS que depende del valor del artículo más grande.

Véase también

• Problema de cubrimiento de contenedores y problema de empaquetado de contenedores : dos problemas de optimización bien estudiados que pueden considerarse casos especiales de asignación de bienes indivisibles y asignación de tareas indivisibles , respectivamente. Muchas técnicas utilizadas para estos problemas también son útiles en el caso de la asignación de artículos con una participación máxima.
• Asignación igualitaria de artículos : a menudo llamada con el nombre muy similar de "asignación máxima-mínima de artículos", pero su definición y las asignaciones que produce son muy diferentes de la equidad de distribución máxima-mínima.

Referencias

1. Hill, Theodore P. (1987). "Partitioning General Probability Measures". Anales de probabilidad . 15 (2): 804–813. doi : 10.1214/aop/1176992173 . ISSN  0091-1798. JSTOR  2244076.
2. 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.
3. Procaccia, AD; Wang, J (2014). "Es justo: garantizar cuotas maximin aproximadas". EC '14 Actas de la decimoquinta conferencia de la ACM sobre economía y computación . págs. 675–692. doi :10.1145/2600057.2602835. ISBN 9781450325653. Número de identificación del sujeto  53223172.
4. Markakis, Evangelos; Psomas, Christos-Alexandros (2011). "Sobre las asignaciones en el peor de los casos en presencia de bienes indivisibles". En Chen, Ning; Elkind, Edith; Koutsoupias, Elias (eds.). Internet and Network Economics . Apuntes de clase en informática. Vol. 7090. Berlín, Heidelberg: Springer. págs. 278–289. doi :10.1007/978-3-642-25510-6_24. ISBN 978-3-642-25510-6.
5. Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (19 de julio de 2015). "Compromisos en el peor de los casos en matroides con aplicaciones a la asignación de bienes indivisibles". Ciencias de la Computación Teórica . 589 : 121–140. doi :10.1016/j.tcs.2015.04.029. ISSN  0304-3975.
6. Li, Bo; Moulin, Hervé; Sol, Ankang; Zhou, Yu (2023). "Sobre la garantía del peor de los casos de Hill para males indivisibles". arXiv : 2302.00323 [cs.GT].
7. "Copia archivada" (PDF) . Archivado desde el original (PDF) el 28 de julio de 2019. Consultado el 29 de noviembre de 2019 .{{cite web}}: CS1 maint: archived copy as title (link)
8. Feige, Uriel; Sapir, Ariel; Tauber, Laliv (19 de octubre de 2021). "Un ejemplo negativo ajustado para asignaciones justas de MMS". arXiv : 2104.04977 [cs.GT].
9. Kurokawa, David; Procaccia, Ariel; Wang, Junxing (21 de febrero de 2016). "¿Cuándo se puede garantizar la garantía de participación de Maximin?". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 30 (1). doi : 10.1609/aaai.v30i1.10041 . ISSN  2374-3468. S2CID  7556264.
10. Dickerson, John; Goldman, Jonathan; Karp, Jeremy; Procaccia, Ariel; Sandholm, Tuomas (21 de junio de 2014). "El ascenso y la caída computacional de la imparcialidad". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 28 (1). doi : 10.1609/aaai.v28i1.8884 . ISSN  2374-3468. S2CID  3178022.
11. Amanatidis, Georgios; Markakis, Evangelos; Nikzad, Afshin; Saberi, Amin (4 de diciembre de 2017). "Algoritmos de aproximación para calcular asignaciones de acciones de Maximin". ACM Transactions on Algorithms . 13 (4): 1–28. arXiv : 1503.00941 . doi :10.1145/3147173. S2CID  13366555.
12. Bouveret, Sylvain; Lemaître, Michel (2015). "Caracterización de los conflictos en la división justa de bienes indivisibles utilizando una escala de criterios". Agentes autónomos y sistemas multiagente . 30 (2): 259. doi :10.1007/s10458-015-9287-3. S2CID  16041218.
13. Hummel, Halvard (1 de febrero de 2023). "Sobre los límites inferiores para las garantías de participación máxima". arXiv : 2302.00264 [cs.GT].
14. https://www.wisdom.weizmann.ac.il/~feige/mypapers/MMSab.pdf ^{[ URL simple PDF ]}
15. Barman, Siddharth; Krishnamurthy, Sanath Kumar (6 de marzo de 2017). "Algoritmos de aproximación para la división justa de Maximin". arXiv : 1703.01851 [cs.GT].
16. Barman, Siddharth; Krishnamurthy, Sanath Kumar (6 de marzo de 2020). "Algoritmos de aproximación para la división justa de Maximin". ACM Transactions on Economics and Computation . 8 (1): 5:1–5:28. arXiv : 1703.01851 . doi :10.1145/3381525. ISSN  2167-8375. S2CID  217191332.
17. Ghodsi, Mohammad; Hajiaghayi, Mohammadtaghi; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi (11 de junio de 2018). "Asignación justa de bienes indivisibles: mejoras y generalizaciones". Actas de la Conferencia ACM de 2018 sobre economía y computación . EC '18. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 539–556. doi :10.1145/3219166.3219238. ISBN 978-1-4503-5829-3. Número de identificación del sujeto  450827.
18. Garg, yugal; McGlaughlin, Peter; Taki, Setareh (2018). Fineman, Jeremy T.; Mitzenmacher, Michael (eds.). "Aproximación a las asignaciones de acciones de Maximin". 2do Simposio sobre Simplicidad en Algoritmos (SOSA 2019) . Serie OpenAccess en Informática (OASIcs). 69 . Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik: 20:1–20:11. doi : 10.4230/OASIcs.SOSA.2019.20 . ISBN 978-3-95977-099-6.
19. Garg, Jugal; Taki, Setareh (13 de julio de 2020). "Un algoritmo de aproximación mejorado para acciones de Maximin". Actas de la 21.ª Conferencia de la ACM sobre economía y computación . EC '20. Evento virtual, Hungría: Association for Computing Machinery. págs. 379–380. arXiv : 1903.00029 . doi :10.1145/3391403.3399526. ISBN 978-1-4503-7975-5.S2CID67855844  .​
20. Akrami, Hannaneh; Garg, Jugal; Sharma, Eklavya; Taki, Setareh (29 de marzo de 2023). "Simplificación y mejora de la aproximación MMS". arXiv : 2303.16788 [cs.GT].
21. Feige, Uriel; Norkin, Alexey (11 de mayo de 2022). "Asignación equitativa maximin mejorada de elementos indivisibles a tres agentes". arXiv : 2205.05363 [cs.GT].
22. Akrami, Hannaneh; Melhorn, Kurt; Seddighin, Masoud; Shahkarami, Golnoosh (15 de diciembre de 2023). "Aproximaciones aleatorias y deterministas de participación máxima para valoraciones fraccionariamente subaditivas" (PDF) . Avances en sistemas de procesamiento de información neuronal . 36 : 58821–58832. arXiv : 2308.14545 .
23. Aigner-Horev, Elad; Segal-Halevi, Erel (2022). "Emparejamientos sin envidia en grafos bipartitos y sus aplicaciones a la división justa". Ciencias de la información . 587 : 164–187. arXiv : 1901.09527 . doi :10.1016/j.ins.2021.11.059. S2CID  170079201.
24. Hosseini, Hadi; Searns, Andrew (1 de diciembre de 2020). "Garantizar las acciones de Maximin: algunos agentes se quedaron atrás". arXiv : 2105.09383 [cs.GT].
25. Hosseini, Hadi; Searns, Andrew; Segal-Halevi, Erel (19 de enero de 2022). "Aproximación de la proporción ordinal máxima para las tareas domésticas". arXiv : 2201.07424 [cs.GT].
26. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (1 de septiembre de 2019). "La irrazonable equidad del máximo bienestar de Nash" (PDF) . ACM Trans. Econ. Comput . 7 (3): 12:1–12:32. doi :10.1145/3355902. ISSN  2167-8375. S2CID  202729326.
27. Amanatidis, Georgios; Birmpas, Georgios; Markakis, Evangelos (12 de mayo de 2016). "Sobre mecanismos veraces para la asignación de cuotas máximas". arXiv : 1605.04026 [cs.GT].
28. Barman, Siddharth; Biswas, Arpita (25 de abril de 2018). "División justa bajo restricciones de cardinalidad". arXiv : 1804.09521 [cs.GT].
29. Hummel, Halvard; Hetland, Magnus Lie (14 de junio de 2021). "Garantizar acciones Half-Maximin bajo restricciones de cardinalidad". arXiv : 2106.07300 [cs.GT].
30. Hummel, Halvard; Hetland, Magnus Lie (2022). "Asignación justa de elementos conflictivos". Agentes autónomos y sistemas multiagente . 36 . arXiv : 2104.06280 . doi :10.1007/s10458-021-09537-3. S2CID  233219836.
31. Bouveret, Sylvain; Cechlárová, Katarína; Elkind, Edith; Igarashi, Ayumi; Peters, Dominik (6 de junio de 2017). "División justa de un gráfico". arXiv : 1705.10239 [cs.GT].
32. Lonc, Zbigniew; Truszczynski, Miroslaw (9 de mayo de 2019). "Maximin asignaciones de acciones en ciclos". arXiv : 1905.03038 [cs.SI].
33. Aziz, Haris; Rauchecker, Gerhard; Schryen, Guido; Walsh, Toby (5 de abril de 2016). "Algoritmos de aproximación para asignaciones de acciones máximas y mínimas de tareas y bienes indivisibles". arXiv : 1604.01435 [cs.GT].
34. Huang, Xin; Lu, Pinyan (10 de julio de 2019). "Un marco algorítmico para aproximar la asignación de tareas con la máxima participación". arXiv : 1907.04505 [cs.GT].
35. Kulkarni, Rucha; Mehta, Ruta; Taki, Setareh (5 de abril de 2021). "Maná mixto indivisible: sobre la computabilidad de las asignaciones MMS + PO". arXiv : 2007.09133 [cs.GT].
36. Ebadian, Soroush; Peters, Dominik; Shah, Nisarg (3 de febrero de 2022), Cómo distribuir de manera justa las tareas fáciles y difíciles , arXiv : 2110.11285
37. Lang, Jérôme; Rothe, Jörg (2016). "División justa de bienes indivisibles". En Rothe, Jörg (ed.). Economía y computación . Springer Texts in Business and Economics. Springer Berlin Heidelberg. págs. 493–550. doi :10.1007/978-3-662-47904-9_8. ISBN 9783662479049. {{cite book}}: |journal=ignorado ( ayuda )
38. Heinen, Tobias; Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Rothe, Jörg (1 de noviembre de 2018). "Aproximación y complejidad de los problemas de optimización y existencia para la asignación de bienes indivisibles con cuotas maximin, cuotas proporcionales y cuotas minimax". Agentes autónomos y sistemas multiagente . 32 (6): 741–778. doi :10.1007/s10458-018-9393-0. ISSN  1573-7454. S2CID  49479969.
39. Segal-Halevi, Erel; Suksompong, Warut (1 de diciembre de 2019). "Asignación justa y democrática de bienes indivisibles". Inteligencia artificial . 277 : 103167. arXiv : 1709.02564 . doi :10.1016/j.artint.2019.103167. ISSN  0004-3702. S2CID  203034477.
40. Amanatidis, Georgios; Birmpas, Georgios; Markakis, Evangelos (13 de julio de 2018). "Comparación de relajaciones aproximadas de la ausencia de envidia". Actas de la 27.ª Conferencia conjunta internacional sobre inteligencia artificial . IJCAI'18. Estocolmo, Suecia: AAAI Press: 42–48. arXiv : 1806.03114 . ISBN 978-0-9992411-2-7.
41. Barman, Siddharth; Biswas, Arpita; Krishnamurthy, Sanath Kumar; Narahari, Y. (20 de noviembre de 2017). "Asignación justa maximin grupal de bienes indivisibles". arXiv : 1711.07621 [cs.GT].
42. Farhadi, Alireza; Ghodsi, Mohammad; Hajiaghayi, Mohammad Taghi; Lahaie, Sébastien; Pennock, David; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi (7 de enero de 2019). "Asignación justa de bienes indivisibles a agentes asimétricos". Revista de investigación en inteligencia artificial . 64 : 1–20. arXiv : 1703.01649 . doi : 10.1613/jair.1.11291 . ISSN  1076-9757. S2CID  15326855.
43. Babaioff, Moshe; Nisan, Noam; Talgam-Cohen, Inbal (27 de enero de 2021). "Equilibrio competitivo con bienes indivisibles y presupuestos genéricos". Matemáticas de la investigación de operaciones . 46 (1): 382–403. arXiv : 1703.08150 . doi :10.1287/moor.2020.1062. ISSN  0364-765X. S2CID  8514018.
44. Segal-Halevi, Erel (18 de diciembre de 2019). "La relación de dominancia accionaria de Maximin". arXiv : 1912.08763 [matemáticas.CO].
45. Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (6 de junio de 2021). "Asignaciones de participación justa para agentes con derechos arbitrarios". arXiv : 2103.04304 [cs.GT].