Asignación aleatoria justa

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

En un problema de asignación (también llamado problema de asignación de casa o de emparejamiento unilateral ), hay m objetos y deben asignarse entre n agentes, de modo que cada agente reciba como máximo un objeto. Algunos ejemplos incluyen la asignación de trabajos a trabajadores, habitaciones a compañeros de casa, dormitorios a estudiantes, franjas horarias a usuarios de una máquina común, etc.

En general, puede resultar imposible lograr una asignación justa. Por ejemplo, si Alice y Batya prefieren la habitación del este a la del oeste, solo una de ellas la obtendrá y la otra sentirá envidia. En el caso de la asignación aleatoria , la equidad se logra mediante una lotería. Por lo tanto, en el ejemplo simple anterior, Alice y Batya lanzarán una moneda justa y la ganadora obtendrá la habitación del este.

Historia

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

En los EE. UU., se utilizaron loterías para asignar tierras públicas a los colonos (por ejemplo, Oklahoma en 1901) y para asignar espectros de radio a las emisoras (por ejemplo, FCC 1981-1993). La lotería todavía se utiliza para asignar tarjetas verdes . ^[1]

Métodos

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

• La prioridad aleatoria (RP, también conocida como dictadura serial aleatoria o RSD) es un mecanismo muy simple que solo requiere que los agentes tengan una clasificación ordinal para los elementos individuales. Elige un orden de prioridad aleatorio para los elementos y permite que cada agente elija por turno su elemento restante favorito.
• La probabilidad serializada (PS) ^[2] es otro mecanismo que funciona únicamente con la clasificación ordinal de los 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, por sus siglas en inglés) ^[3] es un mecanismo basado en el mercado: cada artículo se considera como una mercancía divisible. A cada agente se le da un presupuesto igual de una moneda fiduciaria, luego se le permite a los agentes 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 las loterías).

Propiedades

Eficiencia

Una propiedad deseada de una regla de asignación aleatoria es la eficiencia de Pareto (EP). Existen tres variantes de EP:

• La PE ex post significa que, una vez determinada la asignación final, ninguna otra asignación es mejor para algún agente y al menos tan buena para los demás. Las tres reglas anteriores (RP, PS y CEEI) son PE ex post.
• El PE ex ante es una propiedad más sólida, relevante para los agentes con utilidades cardinales. Significa que ninguna otra lotería es mejor para algún agente y al menos tan buena para los demás. CEEI es PE ex ante cuando los agentes comparan loterías en función de su utilidad esperada.
• La PE posible (o PE-sd) es una propiedad intermedia, relevante para agentes con utilidades ordinales . Significa que la asignación es PE ex ante para algunas funciones de valoración consistentes con la clasificación ordinal de los agentes. PS es PE posible, pero RP no lo es.

Para PE, las implicaciones son: ex-ante → sd(posible) → ex-post .

Justicia

Otra propiedad deseada es la ausencia de envidia (FE). Nuevamente, existen tres variantes de FE:

• La EF ex post significa que, una vez determinada la asignación final, ningún agente prefiere la asignación de otro agente. Ninguna regla satisface esta fuerte propiedad; de hecho, puede resultar imposible encontrar una asignación EF ex post de objetos indivisibles.
• El factor de eficiencia ex ante es una propiedad más débil, relevante para agentes con utilidades cardinales. Significa que ningún agente prefiere la lotería de otro agente. CEEI es un factor de eficiencia ex ante con respecto a las utilidades esperadas.
• La EF necesaria (o EF-sd) es una propiedad intermedia, relevante para los agentes con utilidades ordinales . Significa que la asignación es EF ex ante (ver más abajo) para todas las funciones de valoración consistentes con la clasificación ordinal de los agentes. PS es EF necesaria, pero RP no lo es. RP es EF-sd ex ante débil; es EF cuando los agentes comparan loterías por dominancia lexicográfica (EF-ld). ^[4]

Para EF, la dirección de implicación es opuesta a la de la eficiencia: ex-post → sd(necesario) → ex-ante .

Veracidad

Una tercera propiedad deseada es la veracidad (también llamada a prueba de estrategias). Nuevamente, existen tres variantes:

• La veracidad ex ante, relevante para los agentes con utilidades cardinales, significa que ningún agente puede obtener una mejor lotería informando valoraciones falsas. Esta es una propiedad sólida, que no se satisface con ningún mecanismo no trivial.

• La veracidad posible es una propiedad más débil, relevante para agentes con utilidades ordinales . Significa que un agente no puede obtener una lotería estocásticamente dominante informando una clasificación falsa. Esta propiedad débil se satisface por PS cuando todas las clasificaciones son estrictas y hay como máximo un objeto por persona. En este contexto, también es veraz con respecto al predominio lexicográfico ( ld-veraz ). ^[4] No se satisface cuando las clasificaciones son débiles. ^[5]
• La veracidad necesaria es una propiedad más fuerte, relevante para agentes con utilidades ordinales . Significa que un agente que informa una clasificación falsa siempre obtiene una lotería dominada estocásticamente. Esta fuerte propiedad se satisface con RP, y se puede extender de manera veraz también al caso general cuando hay más objetos que personas.

La siguiente tabla compara las propiedades de las distintas reglas (las columnas RP y PS se basan en ^[6] ):

Combinaciones imposibles

Algunas combinaciones de las tres propiedades anteriores no pueden satisfacerse simultáneamente por ningún mecanismo:

• Para los agentes con utilidades cardinales , Zhou ^[7] demuestra que ningún mecanismo satisface la eficiencia ex ante , la veracidad ex ante y el trato igualitario entre iguales (= los agentes con funciones de utilidad idénticas deberían obtener la misma utilidad).
• Para agentes con utilidades ordinales estrictas , Bogomolnaia y Moulin ^[2] prueban que ningún mecanismo satisface la eficiencia posible , la veracidad necesaria y el trato igualitario de los iguales .
• Para agentes con utilidades ordinales débiles , Katta y Sethuraman ^[5] prueban que ningún mecanismo satisface la posible eficiencia , la posible veracidad y la necesaria ausencia de envidia .

Descomponiendo una asignación fraccionaria

Tanto las reglas PS como las CEEI calculan una matriz de asignaciones esperadas, es decir, las probabilidades marginales con las que cada agente recibe cada objeto. Sin embargo, como la asignación final debe ser un emparejamiento, es necesario encontrar una descomposición de esta matriz en una lotería de emparejamientos.

En el contexto clásico, en el que m = n , esto se puede hacer utilizando el algoritmo de Birkhoff . Puede descomponer cualquier matriz n por n de probabilidades de agente-objeto en una combinación convexa de matrices de permutación O( n ² ) , cada una de las cuales representa una coincidencia. 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. También 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 en el peor de los casos que reciben un objeto. Su algoritmo garantiza que el número de agentes en el peor de los casos sea 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 al tiempo que garantiza que todas las coincidencias en la descomposición sean PE ex post; el segundo algoritmo se puede utilizar solo para asignaciones fraccionarias generadas por PS, pero no para las correspondientes a RP. Para RP, solo es posible obtener una aproximación de 1/2 factor 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 sujetos a PE ex post es NP-hard. También presentan un marco de generación de columnas que se puede utilizar para optimizar otros criterios de peor de los casos.

Comparación empírica

Hosseini, Larson y Cohen ^[6] comparan la RP con la PS en distintos contextos. 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 está libre de envidia sd, 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 en el sentido de Pareto a la otra. Por ejemplo, supongamos que hay tres objetos a, b, c y tres agentes con clasificaciones 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. Entonces (1) es indiferente, (2) prefiere estrictamente a PS y (3) prefiere estrictamente a RP.
• La fracción de perfiles de preferencia en los que el PS sd domina al RP es grande cuando el número de agentes y objetos difiere, pero se acerca a cero cuando los números son iguales. Lo mismo es cierto para la dominación 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 el riesgo , el bienestar social esperado de PS es mayor que el de RP, y la diferencia crece rápidamente cuando n ≠ m. En cambio, 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 cercana a cero cuando n ≥ m, pero genera envidia cuando m > n. La envidia de RP disminuye cuando aumenta la búsqueda de riesgos. La ganancia 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 hace más pequeña (aunque sigue siendo estadísticamente significativa). La fracción de agentes envidiosos en RP aumenta, pero la envidia permanece por debajo de 0,01 cuando n ≥ m . La manipulabilidad de PS llega a 1 cuando m / n crece.

Extensiones

Tao y Cole ^[9] estudian la existencia de asignaciones aleatorias de PE y EF cuando las utilidades son no 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 deberían 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 .

Véase también

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

Referencias

1. 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.
2. 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.
3. Hylland, Aanund; Zeckhauser, Richard (1979). "La asignación eficiente de individuos a puestos". Revista de Economía Política . 87 (2): 293. doi :10.1086/260757. S2CID  154167284.
4. Kate, Hosseini, Hadi Larson (24 de julio de 2015). Mecanismos de cuotas a prueba de estrategias para problemas de asignación múltiple. OCLC  1106222190.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
5. 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.
6. Hadi Hosseini, Kate Larson, Robin Cohen (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. S2CID  14041902.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
7. Zhou, Lin (1990-10-01). "Sobre una conjetura de Gale acerca de problemas de emparejamiento unilateral". Journal of Economic Theory . 52 (1): 123–135. doi :10.1016/0022-0531(90)90070-Z. ISSN  0022-0531.
8. Demeulemeester, Tom; Goossens, Dries; Hermans, Ben; Leus, Roel (2023). "Un enfoque pesimista sobre el emparejamiento unilateral". Revista Europea de Investigación Operativa . 305 (3): 1087–1099. arXiv : 2101.00579 . doi :10.1016/j.ejor.2022.07.013. S2CID  245669132.
9. Cole, Richard; Tao, Yixin (1 de abril de 2021). "Sobre la existencia de asignaciones eficientes en el sentido de Pareto y libres de envidia". Journal of Economic Theory . 193 : 105207. arXiv : 1906.07257 . doi :10.1016/j.jet.2021.105207. ISSN  0022-0531. S2CID  189999837.
10. 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.
11. Shen, Zeyu; Wang, Zhiyi; Zhu, Xingyu; Bien, Brandon; Munagala, Kamesh (2023). "Equidad en el problema de la asignación con prioridades inciertas". arXiv : 2301.13804 [cs.GT].
12. Duddy, Conal (2022). "Asignación aleatoria igualitaria". doi :10.2139/ssrn.4197224. S2CID  252192116. SSRN  4197224.