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 Pareto-eficiente para al menos un vector de funciones de utilidad aditivas consistentes con las clasificaciones de elementos de los agentes).

El 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 del SE satisface la regla de ausencia de envidia de SD , una variante ordinal fuerte de la ausencia de envidia (significa que la asignación está libre de envidia para todos los vectores de funciones de utilidad aditivas consistentes con las clasificaciones de ítems de los agentes). Esta variante particular del SE se llama regla serial probabilística (PS). ^[1]

SE fue desarrollado por Hervé Moulin y Anna Bogomolnaia como una solución para el problema de asignación aleatoria justa , donde la fracción que cada agente recibe de cada artículo 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 sobre 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 expectativa ( ex-ante ) para todos los vectores de funciones de utilidad consistentes con las clasificaciones de artículos de los agentes.

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

Descripción

Cada elemento se representa como una barra de pan (u otro alimento). Al principio, cada agente se dirige a su elemento favorito y comienza a comerlo. Es posible que varios agentes coman el mismo elemento al mismo tiempo.

Cada vez que un artículo se consume 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 elemento, se registra la fracción de ese elemento que cada agente ha consumido. En el contexto de las asignaciones aleatorias, estas fracciones se consideran probabilidades. En función de estas probabilidades, se realiza un sorteo. El tipo de sorteo depende del problema:

• Si a cada agente se le permite recibir cualquier cantidad de artículos, se puede realizar un sorteo independiente para cada artículo. Cada artículo se entrega a uno de los agentes que comió una parte, elegido al azar según la distribución de probabilidad para ese artículo.
• Si cada agente debe recibir exactamente un elemento, entonces debe haber una única lotería que elija una asignación mediante alguna distribución de probabilidad en el conjunto de asignaciones deterministas. Para ello, 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 que se 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 dar 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 la configuración 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 (denominados 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 consumo 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 objeto simultáneamente. Después de medio 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 objeto restante favorito) y Chana y Dana van a z (su objeto restante favorito). Después de medio minuto, Alice y Bob tienen cada uno la mitad de y y Chana y Dana tienen cada uno la mitad de z.

La matriz de fracciones ahora es:

Alicia: 1/2 0 1/2 0

Bob: 1/2 0 1/2 0

Chana: 0 1/2 0 1/2

Dana: 0 1/2 0 1/2

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

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 descripción a continuación supone que todos los agentes tienen preferencias neutrales al riesgo , es decir, su utilidad a partir de una lotería es igual al valor esperado de su utilidad a partir 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 hay otra matriz que todos los agentes prefieran débilmente SD y al menos un agente prefiera estrictamente SD.

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

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

Justicia

El SE con velocidades de alimentación iguales (llamado PS) satisface una propiedad de equidad llamada ex ante dominancia estocástica libre de envidia (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, para cada dos agentes i y j :

• El agente i tiene una probabilidad ligeramente mayor de obtener su mejor artículo en la fila i que en la fila j ;
• El agente i tiene una probabilidad ligeramente mayor de obtener uno de sus dos mejores elementos 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 elementos en la fila i que en la fila j .

Cabe señalar que la ausencia de envidia está garantizada ex ante : es justa solo antes de que se realice el sorteo. Por supuesto, el algoritmo no es justo ex post : después de que se realiza el sorteo, 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 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

El 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. Lo siguiente se sabe sobre la manipulación estratégica de 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 con respecto a la relación lexicográfica descendente . Cuando hay dos agentes, cada uno puede calcular en tiempo polinomial una mejor respuesta con respecto a la utilidad esperada. Cuando el número de agentes puede variar, calcular una mejor respuesta con respecto a la UE es NP-hard. ^[4]
• Las mejores respuestas con respecto a la utilidad esperada pueden ser cíclicas. Sin embargo, existe un equilibrio de Nash puro para cualquier número de agentes y elementos. Cuando hay dos agentes, hay algoritmos de tiempo lineal para calcular un perfil de preferencias que se encuentra en equilibrio de Nash con respecto a las preferencias originales. En algunos contextos empíricos, la utilidad esperada es menos propensa a la manipulación. Cuando un agente es reacio al riesgo y no tiene información sobre las estrategias de los otros agentes, su estrategia maximin es ser veraz. ^[4]
• Un agente manipulador puede incrementar su utilidad en un factor de 3/2 como máximo. 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 verdadera.

Extensiones

El algoritmo SE se ha ampliado de muchas maneras.

• Katta y Sethuraman ^[7] presentan Extended PS (EPS), que permite preferencias ordinales débiles (clasificaciones con indiferencias). El algoritmo se basa en la resolución repetida de instancias de flujo de red paramétrica .
• 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 las indiferencias como las 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 inferiores y superiores, y restricciones distribucionales (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 la asignación justa de ítems 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 cantidad de elementos, la injusticia ex post puede ser arbitrariamente mala: teóricamente, es posible que un agente obtenga todos los elementos mientras que otros agentes no obtengan ninguno. Recientemente, se han sugerido varios algoritmos que garantizan tanto la justicia ex ante como la justicia 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 de máximo producto ex ante, que logra ex ante la ausencia de envidia de grupo (GEF; implica tanto EF como PO), y ex post PROP1+EF ₁ ¹ _. Esta 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 fraccional.
• El RecPS puede modificarse para lograr garantías similares (EF ex ante y EF1 ex post) para los préstamos malos.

Aziz ^[15] muestra:

• El algoritmo PS-lotería , en el que la asignación es ex-ante sd-EF, y la lotería se realiza solo entre asignaciones deterministas que son sd-EF1, es decir, las garantías EF y EF1 se cumplen 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 sd-EF ex ante, EF1 ex post y PO ex post; o PO ex ante y sd-EF ex ante.
• Comprobar si una asignación aleatoria dada 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 1/2 fracción de participación maximin (y también 1/2 fracción de participación proporcional truncada ).
• Estas propiedades son casi óptimas: es imposible garantizar más que PROP ex ante, y más que n /(2 n -1) parte proporcional truncada ex post.

Hoefer, Schmalhofer y Varricchio ^[17] extienden el concepto de lotería "lo mejor de ambos mundos" a agentes con diferentes derechos .

Véase 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 asignación aleatoria". Journal of Economic Theory . 100 (2): 295. doi :10.1006/jeth.2000.2710.
2. Aziz, Haris; Ye, Chun (2014). "Algoritmos de corte de torta para valoraciones constantes por partes y uniformes por partes". En Liu, Tie-Yan; Qi, Qi; Ye, Yinyu (eds.). Economía de Internet y de la Web . Apuntes de clase en Ciencias de la Computación. Vol. 8877. Cham: Springer International Publishing. págs. 1–14. doi :10.1007/978-3-319-13129-0_1. ISBN 978-3-319-13129-0.S2CID18365892  .​
3. Bogomolnaia, Anna (1 de julio de 2015). "Asignación aleatoria: redefiniendo 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, Simon; Mattei, Nicholas; 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). "Investigación de las características de los mecanismos de emparejamiento unilateral 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 limitados 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". Journal of Economic Theory . 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 fraccionarias". Revista internacional de teoría de juegos . 40 (3): 481–513. doi :10.1007/s00182-010-0251-9. ISSN  1432-1270. S2CID  15909570.
10. Budish, 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". American Economic Review . 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 elección social aleatoria en serie probabilística". 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. Freeman, Rupert; 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 de la ACM sobre economía y computación . EC '20. Evento virtual, Hungría: Association for Computing Machinery. págs. 21–22. arXiv : 2005.14122 . doi :10.1145/3391403.3399537. ISBN . 978-1-4503-7975-5.S2CID211141200  .​
15. Aziz, Haris (7 de diciembre de 2020). "Lograr simultáneamente equidad ex ante y ex post". Economía de la Web e Internet . Apuntes de clase en 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. Número de identificación del sujeto  214802174.
16. Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (9 de febrero de 2021). "Asignaciones equitativas de lo mejor de ambos mundos". arXiv : 2102.04909 [cs.GT].
17. Hoefer, Martin; Schmalhofer, Marco; Varricchio, Giovanna (8 de septiembre de 2022). "Lo mejor de ambos mundos: agentes con derechos". arXiv : 2209.03908 [cs.GT].