Algoritmo de alimentación simultánea

Un algoritmo de alimentación simultánea (SE) es un algoritmo para asignar objetos divisibles entre agentes con preferencias ordinales . ^{[ 1 ]}

Las "preferencias ordinales" implican que cada agente puede clasificar los elementos de mejor a peor, pero no puede (o no quiere) especificar un valor numérico para cada uno. La asignación SE satisface la eficiencia SD , una variante ordinal débil de la eficiencia de Pareto (lo que 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 los elementos realizadas por los agentes).

La SE se parametriza mediante la "velocidad de ingesta" de cada agente. Si a todos los agentes se les asigna la misma velocidad de ingesta, la asignación de SE satisface la ausencia de envidia SD, una variante ordinal fuerte de la ausencia de envidia (lo que 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 de SE se denomina regla serial probabilística (PS). ^{[ 1 ]}

El algoritmo SE fue desarrollado por Hervé Moulin y Anna Bogomolnaia como solución al problema de la asignación aleatoria justa , donde la fracción que cada agente recibe de cada elemento se interpreta como una probabilidad. Si la integral de la velocidad de ingesta 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 puede descomponerse en una lotería sobre asignaciones en la que cada agente recibe exactamente un elemento. Con velocidades de ingesta iguales, la lotería es libre de envidia en expectativa ( 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 ]}

Cada elemento está representado por una barra de pan (u otro alimento). Inicialmente, cada agente se dirige a su alimento favorito y comienza a comerlo. Es posible que varios agentes coman el mismo alimento al mismo tiempo.

Cuando un alimento se termina de comer, cada uno de los agentes que lo comió va a su alimento favorito restante y comienza a comerlo de la misma manera, hasta que todos los alimentos se hayan consumido.

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

• Si cada agente puede recibir cualquier cantidad de artículos, se puede realizar un sorteo independiente para cada uno. Cada artículo se entrega a uno de los agentes que haya consumido una parte del mismo, elegido al azar según la distribución de probabilidad correspondiente.
• Si cada agente debe recibir exactamente un artículo, entonces debe existir una única lotería que seleccione una asignación mediante alguna distribución de probabilidad sobre el conjunto de asignaciones deterministas. Para ello, la matriz de probabilidades de n × n debe descomponerse en una combinación convexa de matrices de permutación . Esto se puede lograr 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² ^- 2n + 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 que todos coman a la misma velocidad en todo momento. Sin embargo, cuando los agentes tienen derechos diferentes, es posible otorgar a los agentes más privilegiados una mayor velocidad de alimentación. Además, es posible que la velocidad de alimentación varíe 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 debería recibir (en el contexto de asignación, cada agente debería recibir exactamente 1 elemento, por lo que la integral de todas las funciones de velocidad de alimentación debería ser 1).

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.
• Carol 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 Carol y Dana van a x. Cada pareja come su alimento simultáneamente. Después de medio minuto, Alice y Bob tienen cada uno la mitad de w, mientras que Carol y Dana tienen cada uno la mitad de x.

Luego, Alice y Bob eligen y (su artículo favorito restante) y Carol y Dana eligen z (su artículo favorito restante). Después de medio minuto, Alice y Bob tienen cada uno la mitad de y, y Carol y Dana tienen cada uno la mitad de z.

La matriz de fracciones es ahora:

Según las fracciones consumidas, el artículo w se entrega a Alice o a Bob con igual probabilidad, y lo mismo ocurre con el artículo y; el artículo x se entrega a Carol o a Dana con igual probabilidad, y lo mismo ocurre con el artículo z. Si se requiere entregar exactamente 1 artículo por agente, entonces la matriz de probabilidades se descompone en las siguientes dos matrices de asignación:

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 .

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

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é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 de 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 de distribución (restricciones sobre la distribución de probabilidad y no solo la asignación final).
• Aziz y Stursberg ^{[ 12 ]} presentan la Reserva Simultánea Igualitaria (ESR) , que permite no solo una asignación justa de elementos , sino también problemas generales de elección social , con posibles indiferencias.
• Aziz y Brandl ^{[ 13 ]} presentan la Alimentación Vigilante (VE) , que permite restricciones aún más generales.

Como se explicó anteriormente, la asignación determinada por PS es justa solo ex ante, pero no ex post. Además, cuando cada agente puede recibir cualquier cantidad de artículos, la injusticia ex post podría ser arbitrariamente grave: teóricamente, es posible que un agente reciba todos los artículos mientras que los demás no reciban ninguno. Recientemente, se han propuesto varios algoritmos que garantizan tanto la equidad ex ante como una equidad aproximada ex post.

Freeman, Shah y Vaish ^{[ 14 ]} muestran:

• El algoritmo Recursive Probabilistic Serial (RecPS) devuelve una distribución de probabilidad sobre asignaciones que son todas libres de envidia excepto un elemento (EF1). La distribución es ex ante EF, y la asignación es ex post EF1. Una versión ingenua de este algoritmo produce una distribución sobre un número posiblemente exponencial de asignaciones deterministas, un tamaño de soporte polinomial 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 max-product, que alcanza ex ante group envy-freeness (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 ex ante EF (incluso PROP) y ex ante PO junto con ex post EF1; o ex ante EF (incluso PROP) junto con ex post EF1 y fraccional-PO.
• El RecPS puede modificarse para lograr garantías similares (ex ante EF y ex post EF1) para los casos de incumplimiento.

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 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 demuestra que el resultado de PS puede descomponerse en asignaciones EF1.
• Con utilidades binarias, el algoritmo de lotería PS es a prueba de estrategias de grupo , ex ante PO, ex ante EF y ex post EF1.
• 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 dada puede implementarse mediante una lotería sobre las asignaciones EF1 y PO es un problema 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 maximin-participación de 1/2 fracción (y también 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 que 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 .

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