Compartir la maximización

La maximización de acciones (MMD, ing. Maximin share , MMS) es un criterio para una distribución justa de objetos . Dado un conjunto de objetos con diferentes valores, 1-out-n maximin-share significa el valor más grande que se puede obtener dividiendo los objetos en n partes y eligiendo la parte con el valor mínimo.

La distribución de objetos entre n agentes con diferentes puntajes se llama MMD-justa si cada agente obtiene un conjunto que es al menos tan bueno como su 1 -out- n maximin-share. La justicia MDM fue propuesta por Eric Budisch [1] como un debilitamiento del criterio de proporcionalidad : cada agente recibe un conjunto con un valor no inferior a la distribución equitativa (1/ n de cada recurso). proporcionalidadpuede garantizarse si los objetos son divisibles, pero no si son indivisibles, incluso si todos los agentes tienen estimaciones idénticas. Por el contrario, la equidad de MMD siempre se puede garantizar para agentes idénticos, por lo que esta es una alternativa natural a la proporcionalidad incluso si los agentes son diferentes.

Motivos y ejemplos

Los mismos objetos. Suponga primero que m objetos idénticos deben distribuirse equitativamente entre n personas. Idealmente, cada persona debería recibir m / n objetos, pero puede resultar que si m no es divisible por n , esto es imposible, ya que los objetos son indivisibles. Un criterio natural de segundo nivel es redondear m / n al entero más cercano y dar a cada persona al menos objetos de piso ( m / n ). Obtener objetos menores que el piso ( m / n ) sería "demasiado injusto": esta injusticia ya no puede ser cubierta por la indivisibilidad de los objetos.

objetos distinguidos. Ahora suponga que los objetos son distintos y cada uno tiene un valor diferente. Ahora, redondear hacia abajo al entero más cercano puede no dar la solución deseada. Por ejemplo, supongamos que n = 3 y m = 5 y el valor de los objetos es 1, 3, 5, 6, 9. La suma de los valores es 24 y este número es divisible por 3, por lo que lo ideal sería dar cada participante un artículo, valorado al menos 8, pero eso no es posible. El valor más alto que podemos garantizar a todos los agentes es 7, que resulta de la distribución {1,6},{3,5},{9}.

El conjunto {1,6} en el que se alcanza el valor de maximin se denomina "1-out-3 maximin-parts": este es el mejor subconjunto de objetos que se puede crear dividiendo el conjunto original en 3 partes y eligiendo el conjunto menos significativo. Por lo tanto, en este ejemplo, la distribución es MMD-justa si y solo si el valor que recibe cada agente es al menos 7.

Calificaciones variables. Supongamos ahora que cada agente evalúa cada objeto de forma diferente , por ejemplo

Alice califica los objetos en 1,3,5,6,9;
George los califica en 1,7,2,6,8;
Dayna los califica con 1,1,1,4,17.

Ahora cada agente tiene un conjunto diferente de MMD:

El MMD de Alice sigue siendo {1,6} como arriba;
El MMD de George será {1,7}, {2,6} o {8} al dividir {1,7},{2,6},{8} (todos estos conjuntos son equivalentes para él);
El MMD de Dina será {1,1,1} al dividir {1,1,1},{4},{17}.

Aquí, la distribución es MMD-justa si le da a Alice un valor de al menos 7, George al menos 8 y Dina un valor de al menos 3. Por ejemplo, una distribución en la que George obtiene los dos primeros objetos {1,7 }, Alice obtiene los siguientes dos {5,6} y Daina obtiene el objeto {17} es MMD-fair.

Interpretacion _ La MMD de 1 sobre n de un agente puede interpretarse como la utilidad máxima que un agente puede esperar obtener de una distribución si otros agentes tienen las mismas preferencias, si él siempre obtiene la peor parte. Esta es la utilidad mínima a la que tiene derecho el agente (en su opinión), en base a los siguientes argumentos: si otros agentes van a tener las mismas preferencias que yo, hay al menos una distribución que me va a dar tal utilidad y que da otros agentes no menos, por lo tanto, no tienen ninguna razón para darme menos.

Interpretación alternativa: el conjunto preferido por el agente, garantizado por el divisor en el protocolo divide y elige entre oponentes rivales: el agente propone la mejor asignación y deja la regla de selección del conjunto a otros, mientras que él toma el conjunto restante [2 ] .

La equidad de MMD también se puede describir como el resultado del siguiente proceso de negociación. Se ha sugerido alguna distribución. Cada agente puede quejarse de tal distribución y ofrecer la suya propia. Sin embargo, una vez hecho esto, debe permitir que los demás tomen sus partes, mientras que él mismo toma el conjunto restante. Por lo tanto, un agente se quejará de una distribución solo si puede ofrecer una distribución en la que todos los conjuntos sean mejores que el actual. Una asignación es MMD-justa si y solo si ninguno de los agentes se queja de ello, es decir, para cualquier agente en cualquier asignación hay un conjunto que no es mejor que la parte que recibirá en la asignación actual.

Existencia de distribuciones justas de MMD

Si todos los n agentes tienen valoraciones idénticas, por definición siempre existe una distribución justa de MMD.

Si solo n -1 agentes tienen puntajes idénticos, la distribución justa de MMD todavía existe y se puede encontrar usando el protocolo divide y elige : n -1 agentes idénticos dividen objetos en n conjuntos, cada uno de los cuales no es peor que MMD, luego, el agente n elige el conjunto con la puntuación más alta y los agentes idénticos clasifican los n -1 conjuntos restantes.

En particular, para dos agentes, siempre existe una distribución justa de MMD.

Bouvre y Lemaitre [2] realizaron simulaciones intensivas en datos aleatorios para más de 2 agentes y encontraron que existían distribuciones justas de MMD en cada prueba. Demostraron que existen distribuciones justas de MMD en los siguientes casos:

Calificaciones binarias : al agente le gusta el objeto (el valor es 1) o no le gusta (el valor es 0).
Conjuntos múltiples idénticos : los agentes pueden evaluar objetos de diferentes maneras, pero los conjuntos múltiples de evaluaciones de los agentes son los mismos.
Pocos objetos - . $m\leqslant n+3$

Procaccia y Won [3] , así como Kurokawa [4] , construyeron un ejemplo con n= 3 agentes y m = 12 objetos, en el que la distribución garantiza a cada agente un MMD de 1 sobre 3. Además, demostraron que para cualquiera hay un ejemplo con objetos. $n\geqslant 3$ ${\ estilo de visualización 3n+4}$

Aproximación multiplicativa

Para el caso de la inexistencia de distribuciones de MMD, Procaccia y Vaughn propusieron una aproximación multiplicativa para la MMD: la distribución se denomina MMD de participación r para alguna fracción r de [0,1] si el valor de cualquier agente no es menos que la fracción r del valor de su MMD.

Presentaron un algoritmo que siempre encuentra el MMD compartido, donde , y oddfloor( n ) es el entero impar más grande que no excede n . En particular, , decrece a medida que n aumenta y siempre es mayor que . Su algoritmo se ejecuta en tiempo polinomial en m si n es constante. $r_{n}$ $r_{n}:={\tfrac {2\cdot {\text{piso impar}}(n)}{3\cdot {\text{piso impar}}(n)-1}}$ $r_{3}=r_{4}={\tfrac{3}{4))$ ${\tfrac{2}{3))$

Amanatidis, Markakis, Nikzad y Saberi [5] demostraron que en problemas generados aleatoriamente, las distribuciones MMD justas existen con alta probabilidad . Propusieron varios algoritmos mejorados.

Algoritmo MMD de 1/2 parte simple y rápido;
Algoritmo MMD parcial de 2/3 que se ejecuta en tiempo polinomial tanto en m como en n ;
Algoritmo MMD de 7/8 partes para 3 agentes;
Algoritmo MMD-fair para el caso de evaluaciones ternarias , cuando el valor es igual a uno de tres números: 0, 1 o 2.

Barman y Krishnamurti [6] presentaron

Un algoritmo simple y eficiente para MDM de 2/3 partes con estimaciones aditivas basado en el procedimiento de ciclos de envidia .
Un algoritmo simple para MDM de 1/10 partes para el caso más complejo de funciones de conjuntos submodulares basado en la distribución de objetos en un círculo (Round-robin).

Godsi, Hadzhigoyi, Sedigin y Yami [7] propusieron

Para estimaciones aditivas: algoritmo de tiempo polinomial para MMD de 3/4 partes.
Para n =4 agentes aditivos: Algoritmo para MDM de 4/5 partes.
Para estimaciones submodulares: un algoritmo de tiempo polinomial para MMD de 1/3 partes y un límite superior para MMD de 3/4 partes.
Para estimaciones con subaditividad fraccionaria : algoritmo de tiempo polinómico para MMD de 1/8 partes, prueba de la existencia de MMD de 1/5 partes y un límite superior para MMD de 1/2 partes.
Para estimadores semiaditivos : prueba de la existencia de log( m )/10-MMD parcial y un límite superior para 1/2-MMD parcial.

Garg, McGlaflin y Taki [8] propusieron un algoritmo simple para MMD de 2/3 partes, cuyo análisis es simple.

Actualmente se desconoce cuál es el valor más grande de r para el cual siempre existe una distribución de MMD parcial de r . Puede ser un número entre 3/4 y 1 (sin incluir el 1).

Amanatidis, Burmpas y Markakis [9] propusieron estrategias invulnerables para distribuciones justas aproximadas de MMD (ver también División estratégicamente justa ):

Para n agentes: 1/O( m )-MMD parcial.
Para 2 agentes: 1/2 cuota MMD y prueba que ningún mecanismo invulnerable dará más de 1/2.

Xin y Pingyang [10] estudiaron la distribución justa de deberes de MMD (objetos con calificaciones negativas) y demostraron que siempre existe una distribución parcial de MMD del 11 de septiembre.

Aproximación ordinal

Budish [1] propuso otra aproximación de la distribución 1-out- n MMD - 1-out-( $n+1$ ) MMD (cada agente obtiene al menos tanto como podría obtener dividiéndose en n + 1 conjuntos y eligiendo el peor de ellos) . Demostró que un equilibrio competitivo aproximado con ingresos iguales siempre garantiza 1 de ( $n+1$ ) MMD. Sin embargo, esta distribución puede exceder la cantidad de objetos disponibles y, lo que es más importante, exceder las necesidades: la suma de conjuntos distribuidos a todos los agentes puede ser ligeramente mayor que la suma de todos los objetos. Tal error es aceptable en la asignación de asientos a los estudiantes del curso, ya que una pequeña escasez puede corregirse agregando un pequeño número de sillas. Pero el clásico problema de división justa supone que no se pueden sumar elementos.

Para cualquier número de agentes con estimadores aditivos, cualquier distribución justa libre de envidia con la excepción de uno ( EF1) da a cada agente al menos 1-out-(2 n -1) MMD [11] . La distribución BZ1 se puede encontrar, por ejemplo, utilizando la distribución cíclica de objetos o el procedimiento de ciclos de envidia .

Además, la distribución de MMD 1-out-(2 n -2) se puede encontrar utilizando coincidencias sin envidia [12] .

En la actualidad, no se sabe cuál es el N mínimo para el cual siempre existe una distribución MMD de 1 de N. Puede ser cualquier número entre n +1 y 2 n -2. El valor más pequeño de n para el que tal N ya no se conoce es 4.

La condición MDM inicial se puede utilizar para agentes asimétricos (agentes con diferentes acciones debido a ellos) [13] .

Otros problemas algorítmicos

Algunos algoritmos básicos relacionados con MMD:

Cálculo de la MMD del agente dado. Este problema es NP-difícil incluso para agentes con valoraciones aditivas; puede reducirse del problema de dividir un conjunto de números . Voginger [14] desarrolló un algoritmo con complejidad PTAS para este problema.
El problema de determinar si una distribución dada es 1 de MMD $norte$ , co-NP es completo para agentes con estimaciones aditivas.
Averiguar si un problema dado permite cualquier distribución MMD pertenece a la clase , es decir, el problema se puede resolver en un tiempo polinomial no determinista usando un oráculo para un problema NP (se necesita un predictor para calcular el agente MMD). Sin embargo, se desconoce la complejidad computacional exacta de este problema: puede tener el nivel 2, 1 o incluso 0 de la jerarquía polinomial [2] [15] . $NP^{NP}$

Equidad MMD para grupos

Una asignación se denomina emparejamiento -maximin -share-fair ( PMMS -fair) si, para cualquier par de agentes i y j , el agente i recibe al menos su 1-out-2 maximin- la parte limitada por objetos del conjunto total de objetos i y j [16] .

La distribución se llama group - wise-maximin-share-fair ( GMMS -fair ) si, para cualquier subgrupo de agentes de tamaño k , cada miembro del subgrupo recibe su 1 -de- k maximin-share, limitada a los objetos obtenidos por este subgrupo [17] .

Varias nociones de justicia están relacionadas con valoraciones aditivas de la siguiente manera.

De la justicia con la ausencia de envidia sigue HMMD-justice, [17] ;
De HMMD-fairness sigue MMD-fairness (si tomamos un grupo de tamaño n ) y PMMD-fairness (si tomamos un grupo de tamaño 2);
De PMMD-fairness sigue 1/2-HMMD-fairness [16] ;
De PMMD-justice se sigue BZX [18] , de donde se sigue BZ1.
De MMD-justice no sigue PMMD-justice, lo mismo para PMMD=>MMD.

Se garantiza que las distribuciones HMMD existen cuando las estimaciones de los agentes son binarias o idénticas. Con estimaciones aditivas generales, existen distribuciones 1/2-HMMD y se pueden encontrar en tiempo polinomial [17] .

Véase también

Envidiosa distribución de objetos.

Notas

↑ 1 2 Budish, 2011 , p. 1061-1103.
↑ 1 2 3 Bouveret, Lemaître, 2015 , p. 259.
↑ Procaccia, Wang, 2014 , pág. 675–692.
↑ Copia archivada . Consultado el 26 de febrero de 2020. Archivado desde el original el 28 de julio de 2019. (indefinido)
↑ Amanatidis, Markakis, Nikzad, Saberi, 2017 , pág. 1–28.
↑ Barman, Krishnamurthy, 2017 , pág. 647-664.
↑ Ghodsi, Hajiaghayi et al., 2018 , pág. 539-556.
↑ Garg, McGlaughlin, Taki, 2018 , pág. 20:1–20:11.
↑ Amanatidis, Birmpas, Markakis, 2016 , pág. 31-37.
↑ Huang, Lu, 2019 .
↑ Segal-Halevi, Suksompong, 2019 , pág. 103167.
↑ Aigner-Horev, Segal-Halevi, 2019 .
↑ Segal-Halevi, 2019 .
↑ Woeginger, 1997 , pág. 149–154.
↑ Lang, Rothe, 2016 , pág. 493–550.
↑ 1 2 Caragiannis, Kurokawa et al., 2019 , pág. 12:1–12:32.
↑ 1 2 3 Barman, Biswas, Krishnamurthy, Narahari, 2018 .
↑ La envidia de la gratuidad hasta el Bien Menos Valorado . Véase Caragiannis, Kurokawa et al.

Literatura

Eric Budista. El problema de asignación combinatoria: equilibrio competitivo aproximado a partir de ingresos iguales // Revista de economía política. - 2011. - T. 119 , núm. 6 _ -doi : 10.1086/ 664613 .
Sylvain Bouveret, Michel Lemaître. Caracterización de conflictos en la justa división de bienes indivisibles mediante una escala de criterios // Agentes Autónomos y Sistemas Multiagente. - 2015. - T. 30 , núm. 2 . -doi : 10.1007/ s10458-015-9287-3 .
Jérôme Lang, Jörg Rothe. División justa de bienes indivisibles // Economía y computación: una introducción a la teoría de juegos algorítmicos, elección social computacional y división justa / Rothe . - Springer Berlin Heidelberg, 2016. - (Springer Texts in Business and Economics). — ISBN 9783662479049 . -doi : 10.1007/ 978-3-662-47904-9_8 .
Ioannis Caragiannis, David Kurokawa, Herve Moulin, Ariel D. Procaccia, Nisarg Shah, Junxing Wang. La justicia irrazonable del máximo bienestar de Nash // ACM Trans. ecológico Comput.. - 2019. - V. 7 , no. 3 . — ISSN 2167-8375 . -doi : 10.1145/ 3355902 .
Procaccia AD, Wang J. Bastante justo: garantizando acciones máximas aproximadas // EC '14 Actas de la Decimoquinta Conferencia ACM sobre Economía y Computación. - 2014. - S. 675-692. — ISBN 9781450325653 . -doi : 10.1145/ 2600057.2602835 .
Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, Amin Saberi. Algoritmos de aproximación para calcular las asignaciones de acciones de Maximin // Transacciones ACM en algoritmos. - 2017. - T. 13 , núm. 4 . -doi : 10.1145/ 3147173 . -arXiv : 1503.00941 . _
Siddharth Barman, Sanath Kumar Krishnamurthy. Actas de la Conferencia ACM de 2017 sobre economía y computación. — 2017.
Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, Hadi Yami. Asignación justa de bienes indivisibles: mejora y generalización // Actas de la Conferencia ACM de 2018 sobre economía y computación. — 2018.
Jugal Garg, Peter McGlaughlin, Setareh Taki. Aproximación de las asignaciones de acciones de Maximin // 2.º Simposio sobre la simplicidad de los algoritmos (SOSA 2019) / Jeremy T. Fineman, Michael Mitzenmacher. — Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. — T. 69 . - ISBN 978-3-95977-099-6 . -doi : 10.4230 / OASICs.SOSA.2019.20 .
Georgios Amanatidis, Georgios Birmpas, Evangelos Markakis. Vigésima Quinta Conferencia Internacional Conjunta sobre Inteligencia Artificial, IJCAI 2016. - 2016.
Xin Huang, Pinyan Lu. Un marco algorítmico para aproximar la asignación máxima de acciones de las tareas. — 2019.
Erel Segal-Halevi, Warut Suksompong. Asignación justa democrática de bienes indivisibles // Inteligencia Artificial. - 2019. - T. 277 . — ISSN 0004-3702 . -doi : 10.1016/ j.artint.2019.103167 . -arXiv : 1709.02564 . _
Elad Aigner-Horev, Erel Segal-Halevi. Coincidencias sin envidia en grafos bipartitos y sus aplicaciones a la división justa. — 2019.
Erel Segal-Halevi. La relación de dominancia de acciones de Maximin. — 2019.
Gerhard J. Woeginger. Un esquema de aproximación de tiempo polinomial para maximizar el tiempo mínimo de finalización de la máquina // Cartas de investigación de operaciones. - 1997. - T. 20 , núm. 4 . — ISSN 0167-6377 . - doi : 10.1016/S0167-6377(96)00055-7 .
Siddharth Barman, Arpita Biswas, Sanath Kumar Krishnamurthy, Y. Narahari. Groupwise Maximin Asignación justa de bienes indivisibles // Trigésima segunda conferencia AAAI sobre inteligencia artificial. — 2018.