Algoritmo de alimentación simultánea

Un algoritmo de alimentación simultánea (SE) ^[1] es un algoritmo para asignar objetos divisibles entre agentes con preferencias ordinales . "Preferencias ordinales" significa que cada agente puede clasificar los elementos de mejor a peor, pero no puede (o no quiere) especificar un valor numérico para cada elemento. La asignación SE satisface la eficiencia SD , una variante ordinal débil de la eficiencia de Pareto (significa que la asignación es eficiente en el sentido de Pareto para al menos un vector de funciones de utilidad aditivas consistentes con las clasificaciones de elementos de los agentes).

SE está parametrizado por la "velocidad de alimentación" de cada agente. Si a todos los agentes se les da la misma velocidad de alimentación, entonces la asignación SE satisface SD-libre de envidia , una variante ordinal fuerte de libre de envidia (significa que la asignación es libre de envidia para todos los vectores de funciones de utilidad aditivas consistentes con los agentes 'clasificaciones de artículos). Esta variante particular de SE se llama regla serial probabilística (PS). ^[1]

SE fue desarrollado por Hervé Moulin y Anna Bogomolnaia como una solución al problema de asignación aleatoria justa , donde la fracción que cada agente recibe de cada ítem se interpreta como una probabilidad. Si la integral de la velocidad de alimentación de todos los agentes es 1, entonces la suma de las fracciones asignadas a cada agente es 1, por lo que la matriz de fracciones se puede descomponer en una lotería de asignaciones en la que cada agente obtiene exactamente un artículo. Con velocidades de alimentación iguales, la lotería está libre de envidia en cuanto a expectativas ( ex-ante ) para todos los vectores de funciones de utilidad consistentes con las clasificaciones de elementos de los agentes.

También se aplicó una variante de SE al corte de pasteles , donde la asignación es determinista (no aleatoria). ^[2]

Descripción

Cada artículo se representa como una barra de pan (u otro alimento). Inicialmente, cada agente va hacia su artículo favorito y comienza a comérselo. Es posible que varios agentes coman el mismo artículo al mismo tiempo.

Cada vez que un artículo se come por completo, cada uno de los agentes que lo comió va a su artículo restante favorito y comienza a comerlo de la misma manera, hasta que se consumen todos los artículos.

Para cada artículo, se registra la fracción de ese artículo consumida por cada agente. En el contexto de asignaciones aleatorias, estas fracciones se consideran probabilidades. En base a estas probabilidades se realiza un sorteo. El tipo de lotería depende del problema:

• Si a cada agente se le permite recibir cualquier cantidad de artículos, entonces se puede realizar una lotería por separado para cada artículo. Cada artículo se entrega a uno de los agentes que se comió una parte del mismo, elegido al azar según la distribución de probabilidad de ese artículo.
• Si cada agente debe recibir exactamente un artículo, entonces debe haber una lotería única que elija una asignación según alguna distribución de probabilidad en el conjunto de asignaciones deterministas. Para hacer esto, la matriz de probabilidades n por n debe descomponerse en una combinación convexa de matrices de permutación . Esto se puede hacer mediante el algoritmo de Birkhoff . Se garantiza encontrar una combinación en la que el número de matrices de permutación sea como máximo n ² -2 n +2.

Un parámetro importante para SE es la velocidad de alimentación de cada agente. En el caso más simple, cuando todos los agentes tienen los mismos derechos, tiene sentido dejar que todos los agentes coman a la misma velocidad todo el tiempo. Sin embargo, cuando los agentes tienen diferentes derechos, es posible otorgar a los agentes más privilegiados una mayor velocidad de alimentación. Además, es posible dejar que la velocidad de alimentación cambie con el tiempo. Lo importante es que la integral de la velocidad de alimentación de cada agente sea igual al número total de elementos que el agente debe recibir (en el entorno de asignación, cada agente debe obtener exactamente 1 elemento, por lo que la integral de todas las funciones de velocidad de alimentación debe ser 1).

Ejemplos

Hay cuatro agentes y cuatro elementos (denotados w, x, y, z). Las preferencias de los agentes son:

• Alice y Bob prefieren w a x a y a z.
• Chana y Dana prefieren x a w a z a y.

Los agentes tienen los mismos derechos, por lo que aplicamos SE con una velocidad de alimentación igual y uniforme de 1 unidad por minuto.

Inicialmente, Alice y Bob van a w y Chana y Dana van a x. Cada pareja come su artículo simultáneamente. Después de 1/2 minuto, Alice y Bob tienen cada uno la mitad de w, mientras que Chana y Dana tienen cada uno la mitad de x.

Luego, Alice y Bob van a y (su elemento restante favorito) y Chana y Dana van a z (su elemento restante favorito). Después de 1/2 minuto, Alice y Bob tienen cada uno 1/2 de y y Chana y Dana tienen cada uno 1/2 de z.

La matriz de fracciones ahora es:

Alicia: 1/2 0 1/2 0

Bob: 1/2 0 1/2 0

Chaná: 0 1/2 0 1/2

Dana: 0 1/2 0 1/2

Según las fracciones consumidas, el elemento w se le da a Alice o Bob con la misma probabilidad y lo mismo se hace con el elemento y; El elemento x se le da a Chana o Dana con la misma probabilidad y lo mismo se hace con el elemento z. Si se requiere dar exactamente 1 artículo por agente, entonces la matriz de probabilidades se descompone en las dos matrices de asignación siguientes:

1 0 0 0 ||| 0 0 1 0

0 0 1 0 ||| 1 0 0 0

0 1 0 0 ||| 0 0 0 1

0 0 0 1 ||| 0 1 0 0

Una de estas asignaciones se selecciona al azar con una probabilidad de 1/2.

Se pueden generar otros ejemplos en el sitio web MatchU.ai.

Propiedades

La siguiente descripción supone que todos los agentes tienen preferencias neutrales al riesgo , es decir, su utilidad de una lotería es igual al valor esperado de su utilidad de los resultados.

Eficiencia

SE con cualquier vector de velocidades de alimentación satisface una propiedad de eficiencia llamada eficiencia SD (también llamada eficiencia ordinal). Informalmente significa que, considerando la matriz de probabilidad resultante, no existe otra matriz que todos los agentes prefieran débilmente y que al menos un agente prefiera estrictamente.

En el contexto de las asignaciones aleatorias, la eficiencia SD implica eficiencia ex post: cada asignación determinista seleccionada por lotería es eficiente en el sentido de Pareto .

Una asignación fraccionaria es eficiente en SD si y solo si es el resultado de SE para algún vector de funciones de velocidad de alimentación. ^{[1] : Thm.1}

Justicia

SE con velocidades de alimentación iguales (llamada PS) satisface una propiedad de equidad llamada ex-ante libre de envidia de dominancia estocástica (sd-envy-free). Informalmente significa que cada agente, considerando la matriz de probabilidad resultante, prefiere débilmente su propia fila de probabilidades a la fila de cualquier otro agente. Formalmente, por cada dos agentes i y j :

• El agente i tiene una probabilidad débilmente mayor de obtener su mejor artículo en la fila i que en la fila j ;
• El agente i tiene una probabilidad débilmente mayor de obtener uno de sus dos mejores artículos en la fila i que en la fila j ;
• ...
• Para cualquier k ≥ 1, el agente i tiene una probabilidad ligeramente mayor de obtener uno de sus k mejores artículos en la fila i que en la fila j .

Tenga en cuenta que la sd-envy-freeness está garantizada ex ante : es justa sólo antes de que se realice la lotería. Por supuesto, el algoritmo no es justo a posteriori : una vez realizada la lotería, los agentes desafortunados pueden envidiar a los afortunados. Esto es inevitable en la asignación de objetos indivisibles.

PS satisface otra propiedad de equidad, además de la ausencia de envidia. Dada cualquier asignación fraccionaria, para cualquier agente i y un entero positivo k , defina t ( i , k ) como la fracción total que el agente i recibe de sus k clases de indiferencia más altas. Este t es un vector de tamaño como máximo n * m , donde n es el número de agentes y m es el número de elementos. Una asignación ordinalmente igualitaria es aquella que maximiza el vector t en el orden leximin. PS es la única regla que devuelve una asignación ordinalmente igualitaria. ^[3]

Estrategia

SE no es un mecanismo veraz : un agente que sabe que su artículo preferido no es deseado por ningún otro agente puede manipular el algoritmo comiéndose su segundo artículo preferido, sabiendo que su mejor artículo permanecerá intacto. Se sabe lo siguiente sobre la manipulación estratégica del PS:

• PS es veraz cuando los agentes comparan paquetes utilizando la relación lexicográfica descendente . ^[3]
• Un agente puede calcular en tiempo polinomial una mejor respuesta frente a la relación lexicográfica descendente . Cuando hay dos agentes, cada agente puede calcular en tiempo polinomial la mejor respuesta frente a la utilidad esperada. Cuando el número de agentes puede variar, calcular la mejor respuesta frente a la UE es NP-difícil. ^[4]
• Las mejores respuestas frente a la utilidad esperada pueden ciclar. Sin embargo, existe un equilibrio de Nash puro para cualquier número de agentes y elementos. Cuando hay dos agentes, existen algoritmos de tiempo lineal para calcular un perfil de preferencias que está en equilibrio de Nash con respecto a las preferencias originales. En algunos entornos empíricos, el PS es menos propenso a la manipulación. Cuando un agente tiene aversión al riesgo y no tiene información sobre las estrategias de los demás agentes, su estrategia maximin es ser veraz. ^[4]
• Un agente manipulador puede aumentar su utilidad en un factor de como máximo 3/2. Esto se observó primero empíricamente en casos aleatorios ^[5] y luego se demostró formalmente. ^[6]

Tenga en cuenta que la regla de prioridad aleatoria , que resuelve el mismo problema que PS, es veraz.

Extensiones

El algoritmo SE se ha ampliado de muchas maneras.

• Katta y Sethuraman ^[7] presentan PS extendido (EPS), que permite preferencias ordinales débiles (clasificaciones con indiferencias). El algoritmo se basa en resolver repetidamente instancias de flujo de red paramétrico .
• Bogomolnaia ^[3] presentó una definición más simple de la regla PS para preferencias débiles, basada en el orden leximin .
• Yilmaz ^[8] permite tanto indiferencias como dotaciones.
• Athanassoglout y Sethuraman ^[9] presentan la regla del consumo controlado (CC) , que permite indiferencias y dotaciones fraccionarias de cualquier cantidad.
• Budish, Che, Kojima y Milgrom ^[10] presentan PS generalizado , que permite múltiples unidades por artículo, más artículos que agentes, cada agente puede obtener varias unidades, cuotas superiores y restricciones bijerárquicas en las asignaciones factibles.
• Ashlagi, Saberi y Shameli ^[11] presentan otro PS generalizado , que permite cuotas superiores e inferiores, y restricciones distributivas (restricciones en la distribución de probabilidad y no solo en la asignación final).
• Aziz y Stursberg ^[12] presentan la Reserva Simultánea Igualitaria (ESR) , que permite no sólo una asignación justa de artículos sino también problemas generales de elección social , con posibles indiferencias.
• Aziz y Brandl ^[13] presentan Vigilant Eating (VE) , que permite restricciones aún más generales.

Garantizar la equidad aproximada ex post

Como se explicó anteriormente, la asignación determinada por PS es justa sólo ex ante pero no ex post. Además, cuando cada agente puede obtener cualquier número de artículos, la injusticia ex post podría ser arbitrariamente mala: teóricamente es posible que un agente obtenga todos los artículos mientras que otros agentes no obtengan ninguno. Recientemente, se han sugerido varios algoritmos que garantizan tanto la equidad ex ante como la equidad aproximada ex post.

Freeman, Shah y Vaish ^[14] muestran:

• El algoritmo Recursive Probabilistic Serial (RecPS), que devuelve una distribución de probabilidad sobre asignaciones que están todas libres de envidia excepto un elemento (EF1). La distribución es EF ex-ante y la asignación es EF1 ex-post. Una versión ingenua de este algoritmo produce una distribución sobre un número posiblemente exponencial de asignaciones deterministas; un polinomio de tamaño de soporte en el número de agentes y bienes es suficiente y, por lo tanto, el algoritmo se ejecuta en tiempo polinomial. El algoritmo utiliza oráculos de separación .
• Un algoritmo diferente, basado en una asignación ex ante de máximo producto, que logra ex ante la ausencia de envidia de grupo (GEF; implica tanto EF como PO), y ex post PROP1+EF ₁ ¹ _. Ésta es la única regla de asignación que logra todas estas propiedades. No se puede descomponer en asignaciones EF1.
• Estas combinaciones de propiedades son las mejores posibles: es imposible garantizar simultáneamente EF ex ante (incluso PROP) y PO ex ante junto con EF1 ex post; o EF ex-ante (incluso PROP) junto con EF1 ex-post y PO fraccionado.
• El RecPS puede modificarse para lograr garantías similares (EF ex ante y EF1 ex post) para males.

Aziz ^[15] muestra:

• El algoritmo de lotería PS , en el que la asignación es ex ante sd-EF, y la lotería se realiza sólo entre asignaciones deterministas que son sd-EF1, es decir, las garantías EF y EF1 son válidas para cualquier utilidad cardinal consistente con la clasificación ordinal. . Además, el resultado es sd-PO tanto ex ante como ex post. El algoritmo utiliza como subrutinas tanto el algoritmo PS como el algoritmo Birkhoff . La asignación ex ante es equivalente a la devuelta por PS; esto muestra que el resultado de PS se puede descomponer en asignaciones EF1.
• Con utilidades binarias, el algoritmo de lotería PS es a prueba de estrategias de grupo , PO ex ante, EF ex ante y EF1 ex post.
• Estas combinaciones de propiedades son las mejores posibles: es imposible garantizar simultáneamente ex ante sd-EF, ex post EF1 y ex post PO; o ex ante PO y ex ante sd-EF.
• Comprobar si una asignación aleatoria determinada puede implementarse mediante una lotería sobre las asignaciones EF1 y PO es NP-difícil.

Babaioff, Ezra y Feige ^[16] muestran:

• Un algoritmo de tiempo polinomial para calcular asignaciones que son proporcionales ex-ante y ex-post tanto PROP1 como la participación maximina de 1/2 fracción (y también la participación proporcional truncada de 1/2 fracción ).
• Estas propiedades son casi óptimas: es imposible garantizar más que PROP ex-ante y más de n /(2 n -1) participación proporcional truncada ex-post.

Hoefer, Schmalhofer y Varricchio ^[17] extienden la noción de lotería "Lo mejor de ambos mundos" a agentes con diferentes derechos .

Ver también

La página sobre asignación aleatoria justa compara la PS con otros procedimientos para resolver el mismo problema, como la regla de prioridad aleatoria .

Referencias

1. Bogomolnaia, Anna ; Moulin, Hervé (2001). "Una nueva solución al problema de la asignación aleatoria". Revista de teoría económica . 100 (2): 295. doi : 10.1006/jeth.2000.2710.
2. Aziz, Haris; Sí, Chun (2014). "Algoritmos de corte de torta para valoraciones uniformes y constantes por partes". En Liu, Tie-Yan; Qi, Qi; Vosotros, Yinyu (eds.). Economía de la Web y de Internet . Apuntes de conferencias sobre informática. vol. 8877. Cham: Editorial Internacional Springer. págs. 1-14. doi :10.1007/978-3-319-13129-0_1. ISBN 978-3-319-13129-0. S2CID  18365892.
3. Bogomolnaia, Anna (1 de julio de 2015). "Asignación aleatoria: redefinición de la regla serial". Revista de teoría económica . 158 : 308–318. doi :10.1016/j.jet.2015.04.008. ISSN  0022-0531.
4. Aziz, Haris; Gaspers, Serge; Mackenzie, Simón; Mattei, Nicolás; Narodytska, Nina; Walsh, Toby (4 de mayo de 2015). Actas de la Conferencia Internacional de 2015 sobre Agentes Autónomos y Sistemas Multiagente. Estambul, Turquía: Fundación Internacional para Agentes Autónomos y Sistemas Multiagente. págs. 1451-1459. ISBN 978-1-4503-3413-6.. Informe técnico anterior: https://arxiv.org/abs/1401.6523.
5. Hosseini, Hadi; Larson, Kate; Cohen, Robin (1 de julio de 2018). "Investigar las características de los mecanismos de emparejamiento unilaterales bajo diversas preferencias y actitudes de riesgo". Agentes Autónomos y Sistemas Multiagente . 32 (4): 534–567. arXiv : 1703.00320 . doi :10.1007/s10458-018-9387-y. ISSN  1573-7454. S2CID  14041902.
6. Wang, Zihe; Wei, Zhide; Zhang, Jie (3 de abril de 2020). "Incentivos acotados en la manipulación de la regla serial probabilística". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (2): 2276–2283. arXiv : 2001.10640 . doi : 10.1609/aaai.v34i02.5605 . ISSN  2374-3468. S2CID  210943079.
7. Katta, Akshay-Kumar; Sethuraman, Jay (2006). "Una solución al problema de asignación aleatoria en el dominio de preferencia completo". Revista de teoría económica . 131 : 231–250. doi :10.1016/j.jet.2005.05.001.
8. Yılmaz, Özgür (2009). "Asignación aleatoria bajo preferencias débiles". Juegos y comportamiento económico . 66 : 546–558. doi :10.1016/j.geb.2008.04.017.
9. Athanassoglou, Stergios; Sethuraman, Jay (1 de agosto de 2011). "Asignación de viviendas con dotaciones fraccionadas". Revista Internacional de Teoría de Juegos . 40 (3): 481–513. doi :10.1007/s00182-010-0251-9. ISSN  1432-1270. S2CID  15909570.
10. Budista, Eric; Che, Yeon-Koo; Kojima, Fuhito; Milgrom, Paul (1 de abril de 2013). "Diseño de mecanismos de asignación aleatoria: teoría y aplicaciones". Revista económica estadounidense . 103 (2): 585–623. doi :10.1257/aer.103.2.585. ISSN  0002-8282.
11. Ashlagi, Itai; Saberi, Amin; Shameli, Ali (1 de marzo de 2020). "Mecanismos de asignación bajo restricciones distributivas". Investigación de Operaciones . 68 (2): 467–479. arXiv : 1810.04331 . doi :10.1287/opre.2019.1887. ISSN  0030-364X.
12. Aziz, Haris; Stursberg, Paul (20 de junio de 2014). "Una generalización de la serie probabilística a la elección social aleatoria". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 28 (1). doi : 10.1609/aaai.v28i1.8796 . ISSN  2374-3468. S2CID  16265016.
13. Aziz, Haris; Brandl, Florian (1 de septiembre de 2022). "La regla de la alimentación vigilante: un enfoque general para el diseño económico probabilístico con restricciones". Juegos y comportamiento económico . 135 : 168–187. arXiv : 2008.08991 . doi :10.1016/j.geb.2022.06.002. ISSN  0899-8256. S2CID  221186811.
14. Hombre libre, Ruperto; Shah, Nisarg; Vaish, Rohit (13 de julio de 2020). "Lo mejor de ambos mundos: equidad ex ante y ex post en la asignación de recursos". Actas de la 21ª Conferencia ACM sobre Economía y Computación . CE '20. Evento virtual, Hungría: Asociación de Maquinaria de Computación. págs. 21-22. arXiv : 2005.14122 . doi :10.1145/3391403.3399537. ISBN 978-1-4503-7975-5. S2CID  211141200.
15. Aziz, Haris (7 de diciembre de 2020). "Lograr simultáneamente la equidad ex ante y ex post". Economía de la Web y de Internet . Apuntes de conferencias sobre informática. vol. 12495. Berlín, Heidelberg: Springer-Verlag. págs. 341–355. arXiv : 2004.02554 . doi :10.1007/978-3-030-64946-3_24. ISBN 978-3-030-64945-6. S2CID  214802174.
16. Babaioff, Moshé; Esdras, Tomer; Feige, Uriel (9 de febrero de 2021). "Asignaciones de participación justa lo mejor de ambos mundos". arXiv : 2102.04909 [cs.GT].
17. Hoefer, Martín; Schmalhofer, Marco; Varricchio, Giovanna (8 de septiembre de 2022). "Lo mejor de ambos mundos: agentes con derechos". arXiv : 2209.03908 [cs.GT].