Hispanopedia Wiki
Articulo de referencia

Participación de Maximin

La participación maximin (MMS) es un criterio de asignación justa de elementos . Dado un conjunto de elementos con diferentes valores, la participación maximin 1 de n es el valo...

Hispanopedia WikiContenido en espanolLectura gratuita

La participación maximin (MMS) es un criterio de asignación justa de elementos . Dado un conjunto de elementos con diferentes valores, la participación maximin 1 de n es el valor máximo que se puede obtener al particionar los elementos ennorte{\displaystyle n}partes y tomando la parte con el valor mínimo. Una asignación de elementos entrenorte{\displaystyle n}Se dice que MMS es justo para los agentes con diferentes valoraciones si cada agente recibe una cesta que es al menos tan buena como su participación maximin de 1 de n . La equidad MMS es una relajación del criterio de proporcionalidad : cada agente recibe una cesta que es al menos tan buena como la división igualitaria (1/norte{\displaystyle 1/n}de cada recurso). La proporcionalidad se puede garantizar cuando los elementos son divisibles, pero no cuando son indivisibles, incluso si todos los agentes tienen valoraciones idénticas. En cambio, la equidad del 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.

Motivación y ejemplos

Artículos idénticos. Supongamos primero quemetro{\displaystyle m}Los artículos idénticos deben asignarse de manera justa entrenorte{\displaystyle n}personas. Idealmente, cada persona debería recibirmetro/norte{\displaystyle m/n}artículos, pero esto puede ser imposible simetro{\displaystyle m}no es divisible pornorte{\displaystyle n}, ya que los elementos son indivisibles. Un criterio de equidad natural de segundo mejor nivel es redondearmetro/norte{\displaystyle m/n}hasta el entero más cercano y dar a cada persona al menos⌊metro/norte⌋{\displaystyle \lfloor m/n\rfloor }artículos. Recibir menos de⌊metro/norte⌋{\displaystyle \lfloor m/n\rfloor }La división de los elementos es "demasiado injusta"; se trata de una injusticia que no se justifica por la indivisibilidad de los elementos.

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

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

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

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

Ahora, cada agente tiene un MMS diferente:

  • El MMS de Alice todavía está7{\displaystyle 7}como se indicó anteriormente;
  • El MMS de George es8{\displaystyle 8}, por la partición{1,7},{2,6},{8}{\displaystyle \{1,7\},\{2,6\},\{8\}}(todos estos conjuntos son equivalentes para él);
  • El MMS de Dina es3{\displaystyle 3}, por la partición{1,1,1},{4},{17}{\displaystyle \{1,1,1\},\{4\},\{17\}}.

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

Interpretación . El 1 de cadanorte{\displaystyle n}La utilidad mínima aceptable (MMA) de un agente puede interpretarse como la utilidad máxima que puede esperar obtener de una asignación si todos los demás agentes tienen las mismas preferencias, cuando 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, existe al menos una asignación que me proporciona esta utilidad y beneficia (ligeramente) a todos los demás agentes; por lo tanto, no hay razón para darme menos.

Una interpretación alternativa es: el paquete preferido que el agente podría garantizar como divisor en dividir y elegir 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 propone una asignación determinada. Cada agente puede objetarla sugiriendo una partición alternativa de los artículos. Sin embargo, al hacerlo, debe permitir que todos los demás agentes elijan su parte antes de hacerlo él. Por lo tanto, un agente solo objetará una asignación si puede sugerir una partición en la que todos los conjuntos sean mejores que su conjunto actual. Una asignación es MMS justa si ningún agente la objeta, es decir, para cada agente, en cada partición existe un conjunto que es ligeramente peor que su parte actual.

Historia

Theodore Hill [ 1 ] estudió la participación maximin en 1987. Presentó un límite inferior para la participación maximin de un agente en función del valor del artículo más grande y demostró que siempre existe una asignación en la que cada agente recibe al menos este límite inferior. Cabe señalar que la participación maximin real podría ser mayor que el límite inferior, por lo que la asignación hallada mediante el método de Hill podría no ser equitativa en el sentido de 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 MMS si se le permite agregar algunos bienes. En 2014, Procaccia y Wang [ 3 ] demostraron que una asignación equitativa MMS exacta entre tres o más agentes puede no existir.

Definición formal

Dejardo{\displaystyle C}Sea un conjunto que represente el recurso a asignar.v{\displaystyle v}sea ​​cualquier función de valor real en subconjuntos dedo{\displaystyle C}, que representan su "valor". La participación maximin de 1 de n dev{\displaystyle v}dedo{\displaystyle C}se define como:

MMSv1-fuera-de-norte⁡(do):=   máximo(Z1,…,Znorte)∈Particiones⁡(do,norte)   minj∈[norte]   v(Zj){\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 dedo{\displaystyle C}ennorte{\displaystyle n}subconjuntos disjuntos, y el mínimo es sobre todosnorte{\displaystyle n}subconjuntos en la partición. En los ejemplos anteriores,do{\displaystyle C}era un conjunto de números enteros, yv{\displaystyle v}era la función suma, es decir,v(Z){\displaystyle v(Z)}se definió como la suma de enteros enZ{\displaystyle Z}. Por ejemplo, demostramos queMMSv1-fuera-de-3⁡({1,3,5,6,9}):=7{\displaystyle \operatorname {MMS} _{v}^{1{\text{-out-of-}}3}(\{1,3,5,6,9\}):=7}, donde la partición que maximiza es{1,6},{3,5},{9}{\displaystyle \{1,6\},\{3,5\},\{9\}}En un problema típico de asignación justa, hay algunosnorte{\displaystyle n}diferentes agentes con diferentes funciones de valorv1,…,vnorte{\displaystyle v_{1},\dots,v_{n}}sobre el mismo recursodo{\displaystyle C}. El 1 de cada-norte{\displaystyle n}Valor MMS del agentei{\displaystyle i}se denota porMMSi1-fuera-de-norte⁡(do):=MMSvi1-fuera-de-norte⁡(do){\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C):=\operatorname {MMS} _{v_{i}}^{1{\text{-out-of-}}n}(C)}. Una asignación es un vector de n subconjuntos disjuntos por pares dedo{\displaystyle C}-- un subconjunto por agente. Una asignaciónZ1,…,Znorte{\displaystyle Z_{1},\dots,Z_{n}}se denomina MMS-justo , o simplemente una asignación de MMS , si para cada agentei{\displaystyle i},

vi(Zi)≥MMSi1-fuera-de-norte⁡(do){\displaystyle v_{i}(Z_{i})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)}.

Una asignación se denomina partición MMS del agentei{\displaystyle i}si se sostiene quevi(Zj)≥MMSi1-fuera-de-norte⁡(do){\displaystyle v_{i}(Z_{j})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)}a pesar dej{\displaystyle j}, es decir, la asignación es una de las particiones que maximiza la fórmula parai{\displaystyle i}MMS.

Límite inferior

Hill [ 1 ] demostró que, si el valor de cada artículo para un agente es como máximoα{\displaystyle \alpha }veces el valor de todos los artículos, entonces el MMS 1 de n de ese agente es al menosVnorte(α){\displaystyle V_{n}(\alpha)}, dóndeVnorte(α){\displaystyle V_{n}(\alpha)}es la siguiente función lineal a trozos :

Vnorte(α)=1−k⋅(norte−1)⋅α{\displaystyle V_{n}(\alpha )=1-k\cdot (n-1)\cdot \alpha } a pesar de α∈[1k(norte−1/(k+1)),1k(norte−1/k)]{\displaystyle \alpha \in \left[{\frac {1}{k(n-1/(k+1))}},{\frac {1}{k(n-1/k)}}\right]}, para todosk≥1{\displaystyle k\geq 1}.

Tenga en cuenta queVnorte(α){\displaystyle V_{n}(\alpha)}es una función continua y no creciente deα{\displaystyle \alpha }, conVnorte(0)=1/norte{\displaystyle V_{n}(0)=1/n}yVnorte(1)=0{\displaystyle V_{n}(1)=0}(ver el artículo para un gráfico deV2(α){\displaystyle V_{2}(\alpha)}yV3(α){\displaystyle V_{3}(\alpha)})

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

Markakis y Psomas [ 4 ] reforzaron la garantía de Hill y proporcionaron un algoritmo de tiempo polinomial para calcular una asignación que satisfaga 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 presentan una aproximación veraz de factor constante para un número limitado de bienes. Gourves, Monnot y Tlilane [ 5 ] extendieron 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 la cota inferior de Hill a los elementos malos y presentaron una cota más precisa que también depende del número de elementos malos. Además, presentaron un algoritmo de tiempo polinomial que alcanza esta cota.

Existencia de asignaciones equitativas del MMS

Es posible que no exista una asignación justa MMS. Procaccia y Wang [ 3 ] y Kurokawa [ 7 ] construyeron una instancia connorte=3{\displaystyle n=3}agentes ymetro=12{\displaystyle m=12}elementos, en los 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.Vnorte(α){\displaystyle V_{n}(\alpha)}En su caso, hay12{\displaystyle 12}objetos, indexados pori∈[3]{\displaystyle i\in [3]}yj∈[4]{\displaystyle j\in [4]}Cada agentek{\displaystyle k}valores cada objeto(i,j){\displaystyle (i,j)}por:

vk(i,j)=1,000,000+1,000⋅Ti,j+mii,j(k){\displaystyle v_{k}(i,j)=1,000,000+1,000\cdot T_{i,j}+E_{i,j}^{(k)}}

dóndeT,mi(1),mi(2),mi(3){\displaystyle T,E^{(1)},E^{(2)},E^{(3)}}son matrices particulares de 3 por 4 con valores menores que100{\displaystyle 100}. Demuestran que cada agente puede particionar los objetos en3{\displaystyle 3}subconjuntos de4{\displaystyle 4}objetos cada uno, de modo que la suma de los 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 cadanorte≥3{\displaystyle n\geq 3}existe tal caso con3norte+4{\displaystyle 3n+4}elementos.

Feige, Sapir y Tauber [ 8 ] mejoraron el resultado de no existencia, construyendo una instancia connorte=3{\displaystyle n=3}agentes ymetro=9{\displaystyle m=9}elementos, en los que no hay asignación de MMS. En este caso, cada agente tiene un MMS de 40, pero solo es posible garantizar al agente en peor situación elementos con un valor combinado de 39. También muestran que para cualquiernorte≥3{\displaystyle n\geq 3}, hay un caso con3norte+3{\displaystyle 3n+3}artículos para los que no existe una asignación MMS. Sinorte{\displaystyle n}es incluso, mejoran el límite a3norte+1{\displaystyle 3n+1}artículos. En estos casos, el peor agente puede recibir como máximo un1−1/norte4{\displaystyle 1-1/n^{4}}parte de sus MMS.

Aunque no se garantiza la existencia de asignaciones MMS, se ha demostrado que en casos aleatorios existen asignaciones MMS con alta probabilidad . Kurokawa, Procaccia y Wang [ 9 ] demostraron que esto se cumple en dos casos:

  • Hay muchos artículos:metro≥α⋅norteln⁡norte{\displaystyle m\geq \alpha \cdot n\ln {n}}por alguna constanteα{\displaystyle \alpha }eso depende de la distribución de probabilidad . Entonces, según un resultado anterior, [ 10 ] existe una asignación de elementos libre de envidia con alta probabilidad; dicha asignación es siempre MMS.
  • Hay pocos elementos: metro<norte8/7{\displaystyle m<n^{8/7}}[nótese que este caso se superpone parcialmente con el caso anterior]. Para este caso, presentan un algoritmo llamado matched draft . Se basa en la construcción de un grafo bipartito de agentes vs. elementos, y en encontrar en él un emparejamiento perfecto . Demuestran que (1) la probabilidad de que el matched draft tenga éxito tiende a 1 cuandonorte{\displaystyle n}va al infinito. (2) Si el draft emparejado tiene éxito, entonces el valor de cada agente es al menos su MMS.

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

Para muchas clases de instancias, se ha demostrado que las asignaciones MMS siempre existen. Cuando todos los n agentes tienen valoraciones idénticas, una asignación MMS siempre existe 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 algunosnorte−1{\displaystyle n-1}Los agentes tienen valoraciones idénticas. Una asignación MMS se puede encontrar dividiendo y eligiendo :norte−1{\displaystyle n-1}agentes idénticos dividen los elementos ennorte{\displaystyle n}paquetes, cada uno de los cuales es al menos tan bueno como su MMS; elnorte{\displaystyle n}El agente -ésimo elige el paquete con el valor más alto; y los agentes idénticos toman el restonorte−1{\displaystyle n-1}paquetes. En particular, con dos agentes, siempre existe una asignación MMS.

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 en1{\displaystyle 1}) o le disgusta (lo valora en0{\displaystyle 0}).
  • Multiconjuntos idénticos : los agentes pueden valorar los elementos de forma diferente, pero los multiconjuntos de los valores de los agentes son los mismos.
  • Pocos artículos –metro≤norte+3{\displaystyle m\leq n+3}.

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

  • Haymetro≤norte+6{\displaystyle m\leq n+6}artículos ynorte≠3{\displaystyle n\neq 3}agentes.
  • Haymetro≤norte+7{\displaystyle m\leq n+7}artículos ynorte≥8{\displaystyle n\geq 8}agentes.
  • Haymetro≤norte+do{\displaystyle m\leq n+c}artículos ynorte≥⌊0,6597do(do¡)⌋{\displaystyle n\geq \lfloor 0.6597c(c!)\rfloor }agentes.

Amanatidis, Markakis, Nikzad y Saberi [ 11 ] demostraron que existen asignaciones MMS y que 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 1 de (norte+1{\displaystyle n+1}) MMS: cada agente recibe al menos tanto como podría obtener al dividir 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 :

Vi(Zi)≥MMSi1-fuera-de-d⁡(do){\displaystyle V_{i}(Z_{i})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}d}(C)}

Nótese 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 :

Vi(Zi)≥r⋅MMSi1-fuera-de-norte⁡(do){\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 fracción 3/4), 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-d{\displaystyle d}MMS es 0 para cualquier d > n , pero el 1 de-norte{\displaystyle n}MMS es 1, por lo que cualquier aproximación multiplicativa positiva de la misma 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 1 de d es 1.norte{\displaystyle n}MMS también es 1, por lo que cualquier aproximación multiplicativa de r 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 óptima del MMS 1 de nk 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 multiplicativa 1/ k 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 multiplicativa r para r ≥ 1/2 es al menos tan buena como la aproximación ordinal 1 de (2n ) , pero podría ser peor que la aproximación ordinal 1 de ( 2n -1).

MMS: asignación justa de bienes

aproximaciones multiplicativas

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

rnorte:=2⋅piso extraño(norte)3⋅piso extraño(norte)−1={2norte3norte−1norte  extraño2norte−23norte−4norte  incluso{\displaystyle r_{n}:={\frac {2\cdot {\text{oddfloor}}(n)}{3\cdot {\text{oddfloor}}(n)-1}}={\begin{cases}{\frac {2n}{3n-1}}&n~{\text{ impar}}\\{\frac {2n-2}{3n-4}}&n~{\text{ par}}\end{cases}}}

donde oddfloor( n ) es el mayor entero impar menor o igual a n . En particular, r3 = r4 = 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 podría ser exponencial en n .

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

  • Un algoritmo MMS de media fracción, sencillo 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 7/8 fracciones para 3 agentes;

Barman y Krishnamurthy [ 15 ] [ 16 ] presentaron:

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

  • Para valoraciones aditivas: una prueba de existencia de equidad MMS de fracción 3/4.
  • Para n = 4 agentes aditivos: un algoritmo para la equidad MMS de fracción 4/5.
  • Para valoraciones submodulares : un algoritmo de tiempo polinomial para una equidad MMS de fracción 1/3 y un límite superior de fracción 3/4.
  • Para las valoraciones de XOS : un algoritmo de tiempo polinomial para la equidad MMS de fracción 1/8, una prueba de existencia para la fracción 1/5 y una cota superior de la fracción 1/2.
  • Para valoraciones subaditivas : una prueba de existencia para la equidad MMS de log( m )/10 fracciones y una cota 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 sencillo para MMS de fracción 3/4, que no necesita conocer el valor de MMS y, por lo tanto, se ejecuta en tiempo altamente polinomial.
  • Una prueba de existencia de(34+112norte){\displaystyle ({\frac {3}{4}}+{\frac {1}{12n}})}-fracción MMS.

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 de34+min(136,316norte−4){\displaystyle {\frac {3}{4}}+\min \left({\frac {1}{36}},{\frac {3}{16n-4}}\right)}.

Hasta la fecha, se desconoce cuál es el mayor r tal que siempre exista una asignación MMS de fracción r . Puede ser cualquier número entre3/4{\displaystyle 3/4}y39/40{\displaystyle 39/40}.

Aproximaciones ordinales

Budish [ 2 ] demostró que el equilibrio competitivo aproximado de ingresos iguales siempre garantiza el 1 de (norte+1{\displaystyle n+1}) MMS, 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 podría ser ligeramente mayor que el conjunto de todos los artículos. Tal error es razonable en la asignación de cursos , ya que un pequeño exceso de oferta se puede corregir añadiendo un pequeño número de asientos. Pero el problema clásico de la división justa supone que no se pueden añadir artículos.

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

  • A 1-out-of-(2n-2) MMS allocation of goods, and a 1-out-of(2n/3) MMS allocation of chores, using envy-free matching.[23]
  • A 1-out-of-(3n/2) MMS allocation of goods,[24]which can be computed in polytime when n<6.
  • A 1-out-of-(3n/2) MMS allocation of goods in polynomial time, and a L-out-of-([L+1/2]n) MMS allocation existence result.[16]
  • A 1-out-of-(3n/4) MMS allocation of chores.[25]

To date, it is not known what is the smallest d such that a 1-out-of-d MMS allocation always exists. It can be any number between n+1 and 3n/2. The smallest open case is n=4.

Additional constraints

Maximizing the product: Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang[26] showed that the max-Nash-welfare allocation (the allocation maximizing the product of utilities) is always 21+4n−3{\displaystyle {\frac {2}{1+{\sqrt {4n-3}}}}}-fraction MMS fair, and it is tight.

Truthfulness: Amanatidis, Birmpas and Markakis[27] presented truthful mechanisms for approximate MMS-fair allocations (see also Strategic fair division):

  • For n agents: an 1/O(m)-fraction MMS.
  • For 2 agents: a 1/2-fraction MMS, and a proof that no truthful mechanism can attain more than 1/2.

Cardinality constraints: The items are partitioned into categories, and each agent can get at most kh items from each category h. In other words, the bundles must be independent sets of a partition matroid.

  • Barman and Biswas[28]:10 present an algorithm reducing the problem to a problem with no constraints but with submodular valuations, and then use the algorithm of [17] to attain 1/3-fraction MMS-fairness.
  • Hummel and Hetland[29] present an improved polynomial-time algorithm for 1/2-fraction MMS-fairness. They adapt the standard techniques and reductions from the unconstrained setting to the setting with constraints, and then apply a variant of a bag-filling procedure.

Grafo de conflicto : Hummel y Hetland [ 30 ] estudian otro escenario donde existe un grafo de conflicto entre elementos (por ejemplo: los elementos representan eventos, y un agente no puede atender dos eventos simultáneos). Demuestran que, si el grado del grafo de conflicto es d y está en (2, n ), entonces se puede encontrar una asignación MMS de fracción 1/ d en tiempo polinomial, y siempre existe una asignación MMS de fracción 1/3.

Conectividad : los elementos se ubican en un grafo, y cada parte debe ser un subgrafo conectado.

  • Bouveret, Cechlarova, Elkind, Igarashi y Peters [ 31 ] demuestran que, si el grafo es acíclico, siempre existe una asignación MMS-justa y se puede encontrar de manera eficiente. En grafos generales, puede que no exista una asignación MMS-justa y que su búsqueda sea NP-difícil.
  • Lonc y Truszczynski [ 32 ] se centran en el caso en que el grafo es un ciclo y presentan un algoritmo para una asignación aproximadamente justa según el criterio MMS.

MMS: distribución equitativa de tareas

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

  • Una prueba de que puede que no exista una asignación de MMS para 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 multivariados .

Barman y Krishnamurthy [ 16 ] presentaron un algoritmo que alcanza MMS de fracción 4/3 (precisamente,4norte−13norte{\displaystyle {\frac {4n-1}{3n}}}). El algoritmo puede considerarse una generalización del algoritmo LPT para la planificación de máquinas idénticas.

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

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

  • No es posible ninguna aproximación multiplicativa. Extienden el ejemplo de Procaccia y Wang [ 3 ] añadiendo tres tareas con un valor de -4.054.999,75. El MMS 1 de 3 de cada agente es 0,25 (cada paquete MMS contiene cuatro bienes con una suma de 4.055.000 y una tarea). Sin embargo, cada asignación de los bienes da a al menos un agente un valor de como máximo 4.054.999 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 un caso específico, se puede realizar en tiempo polinomial.

Ebadian, Peters y Shah [ 36 ] demuestran 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 diversas normalizaciones al problema original sin modificar la solución. A continuación, O representa el conjunto de todos los objetos.

Escalada

Si, para cada agente i, todas las valoraciones se escalan por un factorki{\displaystyle k_{i}}(que puede ser diferente para diferentes 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 manera que el MMS de cada agente sea exactamente1{\displaystyle 1}Tras este escalado, los problemas de aproximación MMS pueden plantearse de la siguiente manera:

  • r{\displaystyle r}-fracción MMS : el valor total deO{\displaystyle O}es al menosnorte{\displaystyle n}; necesitamos dar a cada uno denorte{\displaystyle n}agentes un paquete que vale al menosr{\displaystyle r}.
  • 1 de MMS : el valor total deO{\displaystyle O}es al menosd{\displaystyle d}; necesitamos dar a cada uno denorte{\displaystyle n}agentes un paquete que vale al menos1{\displaystyle 1}.

El escalado anterior requiere calcular el MMS de cada agente, lo cual es un problema NP-difícil ( particionamiento de números multivariados ). Un escalado alternativo, que se puede realizar más rápido, es: [ 18 ]

  • r{\displaystyle r}-fracción MMS : el valor total deO{\displaystyle O}es exactamentenorte{\displaystyle n}; el MMS es como máximo1{\displaystyle 1}; necesitamos dar a cada uno denorte{\displaystyle n}agentes un paquete que vale al menosr{\displaystyle r}.
  • 1 de MMS : el valor total deO{\displaystyle O}es exactamented{\displaystyle d}; el MMS es como máximo1{\displaystyle 1}; necesitamos dar a cada uno denorte{\displaystyle n}agentes un paquete que vale al menos1{\displaystyle 1}.

Asignar un objeto

Si quitamos un objetoo{\displaystyle o}deO{\displaystyle O}. Luego, para cada agente, el1{\displaystyle 1}-fuera-de-(norte−1{\displaystyle n-1}) MMS con respecto al conjunto restanteO∖o{\displaystyle O\setminus o}es al menos su1{\displaystyle 1}-fuera-de-norte{\displaystyle n}MMS con respecto al conjunto originalO{\displaystyle O}Esto se debe a que, en la partición MMS original,norte−1{\displaystyle n-1}partes permanecen intactas. [ 12 ] Ahora, supongamos que nuestro objetivo es dar a cada agente un valor der{\displaystyle r}. Si algún objetoo1{\displaystyle o_{1}}vale al menosr{\displaystyle r}a al menos un agente, entonces podemos daro1{\displaystyle o_{1}}a uno de esos agentes de forma arbitraria, y proceder a asignar los objetos restantes a los agentes restantes. Por lo tanto, podemos suponer sin pérdida de generalidad que:

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

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

Relleno de la bolsa

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

  • MMS de 1/2 fracción  : tomars=r=1/2{\displaystyle s=r=1/2}; tenga en cuenta que, por la normalización anterior, podemos asumir que todos los objetos son1/2{\displaystyle 1/2}-pequeño. Inicialmente, hay n agentes y el valor total es al menosnorte{\displaystyle n}para ellos. Después de que se asigna una bolsa, el restonorte−1{\displaystyle n-1}Los agentes valoran los objetos restantes al menosnorte−(r+s)=norte−1{\displaystyle n-(r+s)=n-1}, por lo que podemos proceder recursivamente. [ 17 ]
  • 1 de (2n) MMS  : tomars=r=1{\displaystyle s=r=1}; tenga en cuenta que, por la normalización anterior, podemos asumir que todos los objetos son1{\displaystyle 1}-pequeño. Inicialmente, haynorte{\displaystyle n}agentes y el valor total es al menos2norte{\displaystyle 2n}para ellos. Después de que se asigna una bolsa, el restonorte−1{\displaystyle n-1}Los agentes valoran los objetos restantes al menos2norte−(r+s)=2norte−2=2(norte−1){\displaystyle 2n-(r+s)=2n-2=2(n-1)}, así que podemos proceder recursivamente.

Estos algoritmos de llenado de bolsas funcionan incluso con la rápida escalabilidad, por lo que se ejecutan en tiempo polinomial; no necesitan conocer el valor exacto de MMS. [ 18 ] De hecho, ambos algoritmos pueden enunciarse sin mencionar el MMS en absoluto:

  • Cada agente para quien cada objeto vale como máximo1/(2norte){\displaystyle 1/(2n)}del valor total, recibe al menos1/(2norte){\displaystyle 1/(2n)}del valor total.

Relleno de bolsa modificado : La condición de que todos los objetos esténs{\displaystyle s}-pequeño se puede relajar de la siguiente manera. [ 18 ] Tomar algunoss<r{\displaystyle s<r}. Denota un objeto que no ess{\displaystyle s}-pequeño (es decir, valorado al menoss{\displaystyle s}por al menos un agente) como un "s{\displaystyle s}-objeto grande". Supongamos que como máximonorte{\displaystyle n}los objetos sons{\displaystyle s}-grande. Toma unos{\displaystyle s}-objeto grandeo1{\displaystyle o_{1}}, ponlo en una bolsa y llénala cons{\displaystyle s}-objetos pequeños hasta que un agente indique que vale la pena para él al menosr{\displaystyle r}Debe haber al menos un agente de ese tipo, ya que algún agentei{\displaystyle i}valoreso1{\displaystyle o_{1}}en algún momentoincógnita>s{\displaystyle x>s}Para este agente, hay como máximonorte−1{\displaystyle n-1}restantes{\displaystyle s}-objetos grandes. Por la normalización anterior, estos objetos aún sonr{\displaystyle r}-pequeño, por lo que su valor total parai{\displaystyle i}es como máximor(norte−1){\displaystyle r(n-1)}, por lo tanto, el valor de lo que quedas{\displaystyle s}-los objetos pequeños son al menosnorte−r(norte−1)−incógnita=r(norte−1)+r−incógnita≥r−incógnita{\displaystyle n-r(n-1)-x=r(n-1)+r-x\geq r-x}.

Pedidos

Una instancia está ordenada si todos los agentes tienen la misma clasificación ordinal en los objetos, es decir, los objetos pueden ser numerados.o1,…,ometro{\displaystyle o_{1},\dots ,o_{m}}de tal manera que, para cada agentei{\displaystyle i},vi(o1)≥⋯≥vi(ometro){\displaystyle v_{i}(o_{1})\geq \dots \geq v_{i}(o_{m})}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.T{\displaystyle T}, que es el mismo para todos los agentes. Esto también se puede demostrar formalmente. Supongamos que tenemos un algoritmo que encuentra, para cada instancia ordenada, unr{\displaystyle r}-asignación fraccionaria de MMS. Ahora, se nos da una instancia general de asignación de elementos.PAG{\displaystyle P}Lo resolvemos de la siguiente manera. [ 12 ] [ 15 ]

  1. Construir una instancia ordenadaord(PAG){\displaystyle \mathrm {ord} (P)}de la siguiente manera: para cada agente i , definavi(oj){\displaystyle v_{i}(o_{j})}enord(PAG){\displaystyle \mathrm {ord} (P)}como elj{\displaystyle j}-ésimo valor más alto en el conjunto de valores del agentei{\displaystyle i}enPAG{\displaystyle P}Esto requiereO(nortemetrolg⁡metro){\displaystyle O(nm\lg m)}tiempo.
  2. Encuentra unr{\displaystyle r}-asignación de fracción MMSord(A){\displaystyle \mathrm {ord} (A)}enord(PAG){\displaystyle \mathrm {ord} (P)}.
  3. Construir una secuencia de selección en la que el agente que recibeo1{\displaystyle o_{1}}enord(A){\displaystyle \mathrm {ord} (A)}elige primero, el agente que recibióo2{\displaystyle o_{2}}enord(A){\displaystyle \mathrm {ord} (A)}elige segundo, etc.
  4. Deje que los agentes elijan sus mejores artículos según la secuencia de selección.A{\displaystyle A}ser la asignación resultante. EnA{\displaystyle A}, cada agente recibe exactamente el mismo número de elementos que enord(A){\displaystyle \mathrm {ord} (A)}Además, cada agente que recibióoj{\displaystyle o_{j}}enord(A){\displaystyle \mathrm {ord} (A)}, recibe uno de sus mejoresj{\displaystyle j}artículos enA{\displaystyle A}. Por lo tanto, su valor por cada artículo que obtuvo enA{\displaystyle A}es al menos tan grande como su valor para el artículo correspondiente enord(A){\displaystyle \mathrm {ord} (A)}. Por lo tanto, el valor de cada agente enA{\displaystyle A}es al menos tan alto como enord(A){\displaystyle \mathrm {ord} (A)}Dado que el orden no cambia los valores MMS, la nueva asignaciónA{\displaystyle A}todavíar{\displaystyle r}-fracción MMS.

Entonces, cuando buscar{\displaystyle r}-asignaciones fraccionarias de MMS, podemos asumir sin pérdida de generalidad que:

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

Asignación de dos objetos

Supongamos que encontramos dos objetos o 1 y o 2 , que un agente i valora al menos r , mientras que los demás agentes valoran como máximo 1. Entonces, estos dos objetos pueden asignarse a i . Para los demás 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 pueden combinarse 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 que eliminamos de O los dos objetos o n , o n +1 (es decir, los elementos de mayor valor, n y ( n +1)). 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 del MMS de cada agente debe contener dos o más objetos del conjunto { o 1 , ..., o n +1 }. Estos elementos se pueden usar para reemplazar los objetos entregados, lo que resulta en 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 sin pérdida de generalidad que:

  • MMS de fracción r : el valor total de on , on + 1 para todos los agentes es menor que r . En particular, el valor de on + 1 y todos los objetos que le siguen en el ordenamiento es menor que r /2.
  • MMS 1 de d  : 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 que le siguen en el ordenamiento es menor que 1/2.

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

  • Siempre que un solo objeto valga al menos 2/3 para algún agente, asígnelo.
  • Solicitar la instancia.
  • Siempre que on n , on n +1 valgan al menos 2/3 para algún agente, asígnelos.
  • Finalmente, hay como máximo n objetos con un valor de al menos 1/3; asígnelos utilizando el método de llenado de bolsas modificado.

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

  • Todo agente, para quien o 1 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:

  • Calcular el MMS 1 de n de un agente dado. Este es un problema de optimización NP-difícil , pero tiene varios algoritmos de aproximación; véase Particionamiento de números multivariados y Programación de máquinas idénticas .
  • Decidir si una asignación dada es MMS-justa es co-NP-completa para agentes con valoraciones aditivas (es co-NP, ya que es posible demostrar en tiempo polinomial que una asignación dada no es MMS-justa, dada la partición MMS de uno de los agentes, 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 alguna asignación de MMS, dados los valores de MMS de todos los agentes. Pertenece a NP ya que puede verificarse en tiempo polinomial dada la asignación; su complejidad temporal exacta es desconocida.
    • Por lo tanto, decidir si una instancia dada admite alguna asignación de MMS esnortePAGnortePAG{\displaystyle NP^{NP}}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, 1 o incluso 0 en la jerarquía polinomial . [ 12 ]
  • El problema de decisión de comprobar si existe una asignación de acciones minimax es NP-difícil. Ambos problemas pueden aproximarse mediante un PTAS , suponiendo 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 , siempre se pueden encontrar asignaciones de acciones maximin de manera eficiente. Cuando sus valoraciones no son aditivas, hay casos en los que no existe una asignación MMS de fracción r para ningún r positivo . Sin embargo, para una clase de utilidades submodulares simétricas, existe una asignación MMS de fracción 1/2 ajustada, y puede aproximarse con 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 de jSi el paquete de i no envidia el resto, entonces no lo envidia. Una asignación EF0 se denomina simplemente libre de envidia . Las asignaciones EF1 se pueden encontrar, por ejemplo, mediante la asignación de elementos round-robin o mediante el procedimiento envy-graph .

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 de i.'paquete de que, si se elimina del conjunto de todos los elementos, entonces 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 cierta cuando n =2, pero no cuando n >2.

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

  • Aproximación multiplicativa: MMS de fracción 1/ n (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 cualquier otro agente j , para cualquier elemento individual eliminado de jEl paquete de i no envidia al resto. EFx es estrictamente más fuerte que EF1. Esto implica las siguientes aproximaciones MMS: [ 40 ] : Prop.3.3-3.4

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

MMS para grupos

Una asignación se denomina justa por pares de participación maximin (PMMS-fair) si, para cada par de agentes i y j , el agente i recibe al menos su participación maximin de 1 de 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 de participación maximin por grupo (GMMS-fair) si, para cada subgrupo de agentes de tamaño k , cada miembro del subgrupo recibe su participación maximin de 1 de k restringida a los elementos recibidos por este subgrupo. [ 41 ]

Con 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 la equidad MMS (al tomar el subgrupo de tamaño n ) y la equidad PMMS (al tomar subgrupos de tamaño 2);
  • La equidad PMMS implica una equidad 2/3-MMS para tres agentes y una equidad 4/7-MMS en general; [ 40 ]
  • La equidad de PMMS implica EFX, que a su vez 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 equidad del MMS y la equidad del PMMS no implican una cosa la otra.

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 permisos

Cuando los agentes tienen derechos diferentes (también denominados participaciones desiguales o derechos asimétricos ), la equidad del MMS debe adaptarse para garantizar una mayor participación a los agentes con mayores derechos. Se han sugerido varias adaptaciones. A continuación, asumimos que los derechos vienen dados por un vector.t=(t1,…,tnorte){\displaystyle t=(t_{1},\ldots ,t_{n})}, dóndeti{\displaystyle t_{i}}representa el derecho del agentei{\displaystyle i}.

Equidad ponderada de MMS

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

WMMSit⁡(do):=   máximo(Z1,…,Znorte)∈Particiones⁡(do,norte)   minj∈[norte]   titjV(Zj)=   ti⋅máximo(Z1,…,Znorte)∈Particiones⁡(do,norte)   minj∈[norte]   V(Zj)tj{\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 alcanza mediante una partición en la que el valor de la parte j es proporcional al derecho del agente j . Por ejemplo, supongamos que todas las funciones de valor son sumas y que el vector de derechos es t = (1/6, 11/24, 9/24). EntoncesWMMS1t⁡({1,3,5,6,9})=4{\displaystyle \operatorname {WMMS} _{1}^{t}(\{1,3,5,6,9\})=4}por la partición ({1,3},{5,6},{9}); es óptimo ya que el valor de cada partei{\displaystyle i}igual24ti{\displaystyle 24t_{i}}. Por la misma partición,WMMS2t=11{\displaystyle \operatorname {WMMS} _{2}^{t}=11}yWMMS3t=9{\displaystyle \operatorname {WMMS} _{3}^{t}=9}Cuando todos los n derechos son iguales,WMMSit≡MMSi1-fuera-de-norte{\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 menosWMMSit⁡(do){\displaystyle \operatorname {WMMS} _{i}^{t}(C)}Cuando los n agentes tienen valoraciones idénticas, siempre existe, por definición, una asignación justa según el modelo WMMS. Pero con valoraciones diferentes, la mejor aproximación multiplicativa posible es 1/ n . El límite superior se demuestra con el siguiente ejemplo de 2n - 1 bienes y n agentes, donde ε>0 es una constante muy pequeña:

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,WMMSit=ti{\displaystyle \operatorname {WMMS} _{i}^{t}=t_{i}}para todos los agentes i (para comparar, tenga en cuenta queMMSi1-fuera-de-norte=ϵ=ti{\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}=\epsilon =t_{i}}para los agentes pequeños, peroMMSi1-fuera-de-norte=[1−(norte−1)ϵ]/norte=ti/norte{\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}=[1-(n-1)\epsilon ]/n=t_{i}/n}para el agente grande).

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 para el agente grande, y su valor es aproximadamente 1/ n en lugar de casi 1.

Siempre existe una asignación WMMS justa de fracción 1/ n y se puede encontrar mediante la asignación de elementos round-robin . En un caso restringido, en el que cada agente i valora cada bien como máximoWMMSit{\displaystyle \operatorname {WMMS} _{i}^{t}}Existe una asignación WMMS justa de fracción 1/2 y se puede encontrar mediante un algoritmo similar al de llenado de bolsas: las valoraciones de cada agente i se multiplican porti/WMMSit{\displaystyle t_{i}/\operatorname {WMMS} _{i}^{t}}; y en cada iteración, se le da un elemento a un agente insatisfecho (un agente con un valor menor queWMMSit⁡/2{\displaystyle \operatorname {WMMS} _{i}^{t}/2}) quien más lo valora. Este algoritmo asigna a cada agente i al menos WMMSit⁡/2{\displaystyle \operatorname {WMMS} _{i}^{t}/2}y como máximoWMMSit{\displaystyle \operatorname {WMMS} _{i}^{t}}En la práctica, casi siempre existe una asignación justa según el WMMS. [ 42 ]

Equidad MMS ordinaria

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

MMSVl-fuera-de-d⁡(do):=   máximoPAG∈Particiones⁡(do,d)   minZ∈sindicatos⁡(PAG,l)   V(Z){\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 es sobre todas las particiones de C end{\displaystyle d}subconjuntos disjuntos, y el mínimo es sobre todas las uniones del{\displaystyle l}partes. Por ejemplo,MMSV2-fuera-de-3⁡({1,3,5,6,9})=15{\displaystyle \operatorname {MMS} _{V}^{2{\text{-out-of-}}3}(\{1,3,5,6,9\})=15}por la partición ({1,6},{3,5},{9}). Ahora, la participación maximin ordinal (OMMS) se define por:

OMMSit⁡(do):=   máximol,d: l/d≤tiMMSil-fuera-de-d⁡(do){\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 2 de 3 MMS de C. Tenga en cuenta que, aunque hay infinitos paresl,d{\displaystyle l,d}satisfactorio conl/d≤ti{\displaystyle l/d\leq t_{i}}, solo un número finito de ellos no son redundantes (no implícitos por otros), por lo que es posible calcular el OMMS en tiempo finito. [ 44 ] Una asignación Z 1 ,..., Z n se denomina OMMS-justa para el vector de derechos w si el valor de cada agente i es al menosOMMSit⁡(do){\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 1 = 40 y WMMS 2 = 60, por lo que la única asignación justa de WMMS da el 40 al 1 y el 60 al 2. Sin embargo, OMMS 1 = 0, ya que las fracciones que satisfacenl/d≤0,4{\displaystyle l/d\leq 0.4}son 1/3, 2/5, 3/7, etc., y en todos los casos, en cualquier partición de C end{\displaystyle d}subconjuntos, hay al menosl{\displaystyle l}subconjuntos vacíos. Además, OMMS 2 =40, ya que las fracciones satisfacenl/d≤0,6{\displaystyle l/d\leq 0.6}son 1/2, 2/4, 3/5, 4/7, etc., y en todos los casos, en cualquier partición de C end{\displaystyle d}subconjuntos, ell{\displaystyle l}Los subconjuntos menos valiosos no contienen el 60. Por lo tanto, una asignación justa según el criterio OMMS podría dar el 40 a 2 y el 60 a 1, o no dar nada a 1, lo cual parece injusto en ambos casos.
  • 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 todo i , ya que en cualquier partición de 3 elementos de C , al menos un paquete está vacío. Por lo tanto, el criterio de equidad WMMS es inútil. De manera similar, OMMS 1 = OMMS 2 = 0. Sin embargo, OMMS 3 = 40 por el parl/d=1/2{\displaystyle l/d=1/2}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.

Equidad de AnyPrice-Share

Babaioff, Ezra y Feige [ 45 ] introdujeron un tercer criterio de equidad, al que denominan Participación a Cualquier Precio (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. Sin embargo, el agente debe asignar un peso a cada paquete de tal manera que la suma de los pesos sea al menos 1, y cada artículo pertenezca a paquetes cuyo peso total sea como máximo igual al derecho del agente. El APS es el valor del paquete de peso positivo menos valioso. Formalmente:

APSVt⁡(do):=   máximoPAG∈Conjuntos de paquetes permitidos⁡(do,ti)   minZ∈PAG   V(Z){\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 tales 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 polinomial que garantiza a cada agente al menos 3/5 de su APS. [ 45 ]

El APS siempre es al menos tan alto como el OMMS: dada una partición óptima l 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 cestas cuyo peso total es como máximo l / d , que es como máximo t i . Al agente se le garantiza la cesta menos valiosa de este tipo, que es al menos el MMS l de d .

En algunos casos, el APS es estrictamente superior al OMMS. Aquí hay dos ejemplos:

  • Un ejemplo sencillo 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 solo 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 particiones de 3. 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 en exactamente dos paquetes. Entonces, se puede asignar un peso de 1/6 a cada paquete.
    • Este ejemplo también demuestra que una asignación APS podría no existir incluso para tres 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 frente a WMMS:

  • WMMS es mayor: C = {40, 60} y t = (0.4, 0.6) . Entonces WMMS 1 = 40 y WMMS 2 = 60. Pero APS 1 = 0, ya que cada artículo 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 2 = 40, ya que cada artículo 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.
  • APS es mayor: C = {40, 60} y t = (0.2, 0.2, 0.6) . Entonces WMMS i = 0 para todo i . De manera similar, APS 1 = APS 2 = 0 como se indicó anteriormente. Sin embargo, APS 3 = 40, por ejemplo, con los pesos 0.5*{40}, 0.5*{60}.

Participación maximin 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 elemento más grande.

Véase también

  • El problema de cobertura de contenedores y el problema de empaquetamiento de contenedores son dos problemas de optimización ampliamente 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 resultan útiles en el caso de la asignación de artículos con participación maximin.
  • Asignación igualitaria de artículos : a menudo se la denomina con el nombre muy similar de "asignación de artículos max-min", pero su definición y las asignaciones que produce son muy diferentes de la equidad de reparto maximin.

Referencias

  1. 1 2 3 Hill, Theodore P. (1987). "Partición de medidas de probabilidad generales" . The Annals of Probability . 15 (2): 804– 813. doi : 10.1214/aop/1176992173 . ISSN 0091-1798 . JSTOR 2244076 .  
  2. 1 2 3 Budish, Eric (2011). "El problema de la asignación combinatoria: equilibrio competitivo aproximado a partir de ingresos iguales". Journal of Political Economy . 119 (6): 1061– 1103. doi : 10.1086/664613 . S2CID 154703357 . 
  3. 1 2 3 4 5 6 Procaccia, AD; Wang, J (2014). "Fair enough: ensureing approxim maximin shares". EC '14 Proceedings of the Fifteenth ACM Conference on Economics and Computation . pp. 675– 692. doi : 10.1145/2600057.2602835 . ISBN  9781450325653. S2CID 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.). Economía de Internet y redes . Lecture Notes in Computer Science. Vol. 7090. Berlín, Heidelberg: Springer. pp. 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" . Theoretical Computer Science . 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. ↑ "Fair Enough: Guaranteeing Approximate Maximin Shares" (PDF) . Archivado del original (PDF) el 28 de julio de 2019. Consultado el 29 de noviembre de 2019 .
  8. 1 2 3 4 Feige, Uriel; Sapir, Ariel; Tauber, Laliv (2021-10-19). "Un ejemplo negativo ajustado para asignaciones justas de MMS". arXiv : 2104.04977 [ cs.GT ].
  9. 1 2 Kurokawa, David; Procaccia, Ariel; Wang, Junxing (2016-02-21). "¿Cuándo se puede garantizar la 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 auge y la caída computacional de la equidad" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 28 (1). doi : 10.1609/aaai.v28i1.8884 . ISSN 2374-3468 . S2CID 3178022 .  
  11. 1 2 3 Amanatidis, Georgios; Markakis, Evangelos; Nikzad, Afshin; Saberi, Amin (2017-12-04). "Algoritmos de aproximación para el cálculo de asignaciones de participación maximin". ACM Transactions on Algorithms . 13 (4): 1– 28. arXiv : 1503.00941 . doi : 10.1145/3147173 . S2CID 13366555 . 
  12. 1 2 3 4 Bouveret, Sylvain; Lemaître, Michel (2015). "Caracterización de conflictos en la división justa de bienes indivisibles mediante una escala de criterios". Autonomous Agents and Multi-Agent Systems . 30 (2): 259. doi : 10.1007/s10458-015-9287-3 . S2CID 16041218 . 
  13. ↑ Hummel, Halvard (2023-02-01). "Sobre límites inferiores para garantías de participación maximin". arXiv : 2302.00264 [ cs.GT ].
  14. ↑ "Maximin asignaciones justas con dos valores de elementos" (PDF) . Archivado del original (PDF) el 19 de agosto de 2022.
  15. 1 2 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. 1 2 3 Barman, Siddharth; Krishnamurthy, Sanath Kumar (2020-03-06). "Algoritmos de aproximación para la división justa 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. 1 2 3 4 5 6 7 8 9 10 11 12 13 Ghodsi, Mohammad; Hajiaghayi, Mohammadtaghi; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi (2018-06-11). "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. S2CID 450827 . 
  18. 1 2 3 4 5 6 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. 1 2 Garg, Jugal; Taki, Setareh (13 de julio de 2020). "Un algoritmo de aproximación mejorado para participaciones maximin" . Actas de la 21.ª Conferencia 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. S2CID 67855844 . 
  20. 1 2 Akrami, Hannaneh; Garg, Jugal; Sharma, Eklavya; Taki, Setareh (2023-03-29). "Simplificación y mejora de la aproximación MMS". arXiv : 2303.16788 [ cs.GT ].
  21. ↑ Feige, Uriel; Norkin, Alexey (2022-05-11). "Asignación justa maximin mejorada de elementos indivisibles a tres agentes". arXiv : 2205.05363 [ cs.GT ].
  22. ↑ Akrami, Hannaneh; Melhorn, Kurt; Seddighin, Masoud; Shahkarami, Golnoosh (2023-12-15). "Aproximaciones aleatorias y deterministas de la participación maximin para valoraciones fraccionariamente subaditivas" (PDF) . Advances in Neural Information Processing Systems . 36 : 58821–58832 . arXiv : 2308.14545 .
  23. ↑ Aigner-Horev, Elad; Segal-Halevi, Erel (2022). "Emparejamientos libres de envidia en grafos bipartitos y sus aplicaciones a la división justa". Information Sciences . 587 : 164–187 . arXiv : 1901.09527 . doi : 10.1016/j.ins.2021.11.059 . S2CID 170079201 . 
  24. ↑ Hosseini, Hadi; Searns, Andrew (2020-12-01). "Garantizando acciones maximin: algunos agentes se quedan atrás". arXiv : 2105.09383 [ cs.GT ].
  25. ↑ Hosseini, Hadi; Searns, Andrew; Segal-Halevi, Erel (2022-01-19). "Aproximación de participación de maximin ordinal para tareas domésticas". arXiv : 2201.07424 [ cs.GT ].
  26. 1 2 Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2019-09-01). "La equidad irrazonable del bienestar máximo 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 (2016-05-12). "Sobre mecanismos veraces para asignaciones de participación maximin". arXiv : 1605.04026 [ cs.GT ].
  28. ↑ Barman, Siddharth; Biswas, Arpita (2018-04-25). "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". Autonomous Agents and Multi-Agent Systems . 36 8. 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 (2016-04-05). "Algoritmos de aproximación para asignaciones de participación máxima-mínima de tareas y bienes indivisibles". arXiv : 1604.01435 [ cs.GT ].
  34. ↑ Huang, Xin; Lu, Pinyan (2019-07-10). "Un marco algorítmico para aproximar la asignación de partes maximin de tareas". arXiv : 1907.04505 [ cs.GT ].
  35. ↑ Kulkarni, Rucha; Mehta, Ruta; Taki, Setareh (2021-04-05). "Maná mixto indivisible: sobre la computabilidad de las asignaciones MMS + PO". arXiv : 2007.09133 [ cs.GT ].
  36. ↑ Ebadian, Soroush; Peters, Dominik; Shah, Nisarg (2022-02-03), Cómo asignar equitativamente 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 . Textos de Springer en negocios y economía. Springer Berlin Heidelberg. pp. 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 (2018-11-01). "Aproximación y complejidad de los problemas de optimización y existencia para la asignación de participación maximin, participación proporcional y participación minimax de bienes indivisibles" . Autonomous Agents and Multi-Agent Systems . 32 (6): 741– 778. doi : 10.1007/s10458-018-9393-0 . ISSN 1573-7454 . S2CID 49479969 .  
  39. 1 2 Segal-Halevi, Erel; Suksompong, Warut (2019-12-01). "Asignación democrática justa de bienes indivisibles". Inteligencia Artificial . 277 103167. arXiv : 1709.02564 . doi : 10.1016/j.artint.2019.103167 . ISSN 0004-3702 . S2CID 203034477 .  
  40. 1 2 3 4 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 Internacional Conjunta sobre Inteligencia Artificial . IJCAI'18. Estocolmo, Suecia: AAAI Press: 42–48 . arXiv : 1806.03114 . ISBN 978-0-9992411-2-7.
  41. 1 2 3 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 operativa . 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. 1 2 Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (2021-06-06). "Asignaciones de participación justa para agentes con derechos arbitrarios". arXiv : 2103.04304 [ cs.GT ].