Asignación aleatoria justa

La asignación aleatoria justa (también llamada emparejamiento unilateral probabilístico ) es un tipo de problema de división justa .

En un problema de asignación (también llamado problema de asignación de vivienda o emparejamiento unilateral ), hay m objetos que deben distribuirse entre n agentes, de manera que cada agente reciba como máximo un objeto. Algunos ejemplos incluyen la asignación de puestos de trabajo a trabajadores, habitaciones a compañeros de piso, residencias estudiantiles a alumnos, franjas horarias a usuarios de una máquina común, etc.

En general, una asignación justa puede ser imposible de lograr. Por ejemplo, si Alice y Bob prefieren la habitación del este a la del oeste, solo uno de ellos la obtendrá y el otro sentirá envidia. En el caso de la asignación aleatoria , la equidad se logra mediante un sorteo. Así, en el ejemplo anterior, Alice y Bob lanzarán una moneda justa y el ganador obtendrá la habitación del este.

La asignación aleatoria ya se menciona en la Biblia : se utilizó una lotería para repartir las tierras de Canaán entre las tribus de Israel (Números 26:55).

En Estados Unidos, se utilizaron loterías para asignar tierras públicas a los colonos (por ejemplo, Oklahoma en 1901) y para asignar espectros radioeléctricos a las emisoras (por ejemplo, la FCC entre 1981 y 1993). La lotería todavía se utiliza para otorgar tarjetas de residencia permanente (green cards ). ^{[ 1 ]}

Existen varias maneras de extender el método del "lanzamiento de moneda" a situaciones en las que hay más de dos agentes, y estos pueden tener diferentes relaciones de preferencia sobre los objetos:

• La Prioridad Aleatoria (PR, también conocida como Dictadura Serial Aleatoria o DSA) es un mecanismo muy simple que solo requiere que los agentes tengan una clasificación ordinal de los elementos individuales. Elige un orden de prioridad aleatorio para los elementos y permite que cada agente, por turno, seleccione su elemento favorito entre los restantes.
• Probabilistic Serial (PS) ^{[ 2 ]} es otro mecanismo que funciona solo con clasificación ordinal de elementos. Los agentes "comen" sus elementos favoritos restantes a una velocidad constante, y la fracción que cada agente logró comer es su probabilidad de obtener ese elemento.
• El Equilibrio Competitivo a partir de Ingresos Iguales (CEEI) ^{[ 3 ]} es un mecanismo basado en el mercado: cada artículo se considera una mercancía divisible. A cada agente se le asigna un presupuesto igual de una moneda fiduciaria, y luego se les permite comerciar hasta que se alcance un equilibrio de precios . Este es un mecanismo más complejo que requiere que los agentes tengan funciones de utilidad cardinales completas (o, alternativamente, una clasificación ordinal en loterías).

Tanto la regla PS como la CEEI calculan una matriz de asignaciones esperadas, es decir, las probabilidades marginales con las que cada agente recibe cada objeto. Sin embargo, dado que la asignación final debe ser una coincidencia, es necesario descomponer esta matriz en una lotería de coincidencias.

En el caso clásico, donde m = n , esto se puede lograr utilizando el algoritmo de Birkhoff . Este algoritmo descompone cualquier matriz de probabilidades agente-objeto de n × n en una combinación convexa de O( n² ⁾ matrices de permutación , cada una de las cuales representa un emparejamiento. Sin embargo, la descomposición no es única y algunas descomposiciones pueden ser mejores que otras.

Budish, Che, Kojima y Milgrom ^{[ 1 ]} generalizan el algoritmo de Birkhoff a valores arbitrarios de m y n . También permiten añadir restricciones a las asignaciones, bajo un conjunto máximo de condiciones sobre el conjunto de restricciones. Además, presentan un método de descomposición que minimiza la varianza en la utilidad experimentada por los agentes entre los diferentes emparejamientos.

Demeulemeester, Goossens, Hermans y Leus ^{[ 8 ]} presentan un algoritmo de descomposición en tiempo polinomial que maximiza el número de agentes que reciben un objeto en el peor de los casos. Su algoritmo garantiza que el número de agentes en el peor de los casos es igual al número esperado de agentes redondeado hacia abajo, que es el mejor posible. Presentan otro algoritmo de descomposición que maximiza el número de agentes asignados en el peor de los casos, garantizando que todas las coincidencias en la descomposición sean ex post PE; el segundo algoritmo solo se puede usar para asignaciones fraccionarias generadas por PS, pero no para las correspondientes a RP. Para RP, solo es posible obtener una aproximación de factor 1/2 al número óptimo de agentes asignados en el peor de los casos. Para asignaciones fraccionarias generales, maximizar el número de agentes asignados en el peor de los casos sujeto a ex post PE es NP-difícil. También presentan un marco de generación de columnas que se puede usar para optimizar otros criterios del peor de los casos.

Hosseini, Larson y Cohen ^{[ 6 ]} comparan RP con PS en diversos entornos. Demuestran que:

• Cuando hay como máximo 2 objetos y como máximo 3 agentes, RP y PS devuelven la misma asignación.
• Cuando hay como máximo 2 objetos, para cualquier número de agentes, PS es sd-veraz y RP es sd-envidioso, y en la mayoría de los casos, PS domina a RP, particularmente con 4 o más agentes.
• Cuando hay 3 o más objetos (y 3 o más agentes), RP y PS pueden devolver asignaciones diferentes, y ninguna asignación domina a la otra en el sentido de Pareto. Por ejemplo, supongamos que hay tres objetos a, b, c y tres agentes con rangos de preferencia (1) a>c>b, (2) a>b>c, (3) b>a>c. Entonces, al agente (1), tanto RP como PS dan 1/2 a + 1/2 c; al agente (2), RP da 1/2 a + 1/6 b + 1/3 c mientras que PS da 1/2 a + 1/4 b + 1/4 c que es estocásticamente dominante ; y al agente (3), RP da 5/6 b + 1/6 c mientras que PS da 3/4 b + 1/4 c que es estocásticamente dominante. Por lo tanto, (1) es indiferente, (2) prefiere estrictamente PS y (3) prefiere estrictamente RP.
• La fracción de perfiles de preferencia para los que PS domina a RP es grande cuando el número de agentes y objetos difiere, pero se aproxima a 0 cuando los números son iguales. Lo mismo ocurre con la dominancia ld.
• Cuando los agentes son neutrales al riesgo , el bienestar social esperado de PS es mayor que el de RP, pero la diferencia es sustancial solo cuando n≠m . Con RP, la fracción de agentes envidiosos es cercana a cero cuando n ≥ m. PS es manipulable, y la ganancia de la manipulación aumenta cuando m > n .
• Cuando los agentes buscan riesgos , el bienestar social esperado de PS es mayor que el de RP, y la diferencia aumenta rápidamente cuando n≠m. Por el contrario, cuando n = m, RP alcanza un mayor bienestar social en la mayoría de los casos. Con RP, la fracción de agentes envidiosos es casi cero cuando n ≥ m, pero genera envidia cuando m>n. La envidia de RP disminuye cuando aumenta la propensión al riesgo. La ganancia derivada de manipular PS disminuye cuando los agentes buscan más riesgos.
• Cuando los agentes son reacios al riesgo , la brecha de bienestar social entre RP y PS se reduce (aunque sigue siendo estadísticamente significativa). La fracción de agentes envidiosos en RP aumenta, pero la envidia se mantiene por debajo de 0,01 cuando n ≥ m . La manipulabilidad de PS tiende a 1 cuando m / n aumenta.

Tao y Cole ^{[ 9 ]} estudian la existencia de asignaciones aleatorias PE y EF cuando las utilidades no son lineales (pueden tener complementos).

Yilmaz ^{[ 10 ]} estudia el problema de asignación aleatoria donde los agentes tienen dotaciones.

Shen, Wang, Zhu, Fain y Munagala ^{[ 11 ]} estudian el problema de asignación aleatoria cuando los agentes tienen prioridades (los agentes con prioridades más altas deben obtener sus bienes preferidos antes que los agentes con prioridades más bajas), pero las prioridades son inciertas.

Duddy ^{[ 12 ]} estudia la asignación aleatoria igualitaria .

• La armonía en el alquiler es una variante del problema de asignación en la que la equidad se logra mediante pagos monetarios, en lugar de la aleatorización.
• La asignación equitativa de artículos es una configuración en la que los agentes pueden recibir más de un artículo.
• Sorteo : selección aleatoria de funcionarios políticos.
• Emparejamiento aleatorio a dos bandas , utilizado principalmente en torneos deportivos.