Asignación aleatoria justa

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

En un problema de asignación (también llamado problema de asignación de casas o coincidencia unilateral ), hay m objetos y deben asignarse entre n agentes, de modo que cada agente reciba como máximo un objeto. Los 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 oriental a la occidental, sólo uno de ellos la obtendrá y el otro sentirá envidia. En el entorno de asignación aleatoria , la equidad se logra mediante una lotería. Entonces, en el ejemplo simple anterior, Alice y Batya lanzarán una moneda justa y el ganador obtendrá la habitación del este.

Historia

La asignación aleatoria ya se menciona en la Biblia : se utilizó una lotería para distribuir 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 colonos (por ejemplo, Oklahoma en 1901) y para asignar espectros de radio a 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 en serie aleatoria o RSD) es un mecanismo muy simple que solo requiere que los agentes tengan una clasificación ordinal en elementos individuales. Elige un orden de prioridad aleatorio para los artículos y permite que cada agente, por turno, elija su artículo restante favorito.
• La serie probabilística (PS) ^[2] es otro mecanismo que funciona sólo con clasificación ordinal de elementos. Los agentes "comen" sus artículos restantes favoritos a una velocidad constante, y la fracción que cada agente logró comer es su probabilidad de obtener este artículo.
• El equilibrio competitivo a partir de ingresos iguales (CEEI) ^[3] es un mecanismo basado en el mercado: cada artículo se considera un bien divisible. A cada agente se le da un presupuesto igual de una moneda fiduciaria, luego a los agentes se les permite comerciar hasta que haya un equilibrio de precios . Se trata de un mecanismo más complejo que requiere que los agentes tengan funciones de utilidad cardinales completas (o, alternativamente, clasificación ordinal en las loterías).

Propiedades

Eficiencia

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

• 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 normas anteriores (RP, PS y CEEI) son PE ex post.
• El PE ex ante es una propiedad más fuerte, relevante para agentes con utilidades cardinales. Significa que ninguna otra lotería es mejor para un 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.
• Posible PE (o sd-PE) 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 posible-PE, pero RP no.

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

Justicia

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

• FE 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 ser imposible encontrar una asignación ex post del FA de objetos indivisibles.
• Ex-ante EF 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 EF ex-ante frente a los servicios públicos esperados.
• La EF necesaria (o sd-EF) es una propiedad intermedia, relevante para agentes con utilidades ordinales . Significa que la asignación es ex ante EF (ver más abajo) para todas las funciones de valoración consistentes con la clasificación ordinal de los agentes. PS es necesario-EF, pero RP no. RP es débilmente ex-ante sd-EF; es EF cuando los agentes comparan loterías por dominancia lexicográfica (ld-EF). ^[4]

Para EF, la dirección de la 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 agentes con utilidades cardinales, significa que ningún agente puede obtener una lotería mejor informando valoraciones falsas. Esta es una propiedad fuerte, que no se satisface mediante 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. PS satisface esta propiedad débil cuando todas las clasificaciones son estrictas y hay como máximo un objeto por persona. En este contexto, también es veraz frente a dominio lexicográfico ( ld-truthful ). ^[4] No se siente satisfecho 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 la satisface RP, y puede extenderse de manera veraz también al caso general en el que 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 mediante ningún mecanismo:

• Para agentes con utilidades cardinales , Zhou ^[7] demuestra que ningún mecanismo satisface la eficiencia ex ante , la veracidad ex ante y el trato igualitario de iguales (= agentes con funciones de utilidad idénticas deberían obtener la misma utilidad).
• Para agentes con utilidades ordinales estrictas , Bogomolnaia y Moulin ^[2] demuestran 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] demuestran 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 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 encontrar una descomposición de esta matriz en una lotería de coincidencias.

En el entorno 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 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 myn arbitrarios . También permiten agregar 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 peor número de agentes 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 y al mismo tiempo garantiza que todas las coincidencias en la descomposición sean PE ex post; el segundo algoritmo se puede utilizar sólo para asignaciones fraccionarias generadas por PS, pero no para las correspondientes a RP. Para RP, solo es posible lograr 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 sujetos a PE ex post en el peor de los casos es NP-difícil. También presentan un marco de generación de columnas que se puede utilizar para optimizar otros criterios del peor de los casos.

Comparación empírica

Hosseini, Larson y Cohen ^[6] comparan RP con PS en diversos entornos. Muestran 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 veraz y RP no tiene envidia 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 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. Luego, al agente (1), tanto RP como PS le 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 está dominado estocásticamente. Entonces (1) es indiferente, (2) prefiere estrictamente PS y (3) prefiere estrictamente RP.
• La fracción de perfiles de preferencia para los cuales PS sd 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 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 sólo 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 crece 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 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 el PS disminuye cuando los agentes buscan más riesgos.
• Cuando los agentes tienen aversión al riesgo , la brecha de bienestar social entre RP y PS se vuelve más pequeña (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 llega a 1 cuando m / n crece.

Extensiones

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

Yilmaz ^[10] estudia el problema de la 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 mayores prioridades deberían obtener sus bienes preferidos antes que los agentes con menores prioridades), pero las prioridades son inciertas.

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

Ver 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 un entorno en el que los agentes pueden obtener más de un artículo.
• Sortición : selección aleatoria de funcionarios políticos.
• Emparejamiento aleatorio de dos lados : utilizado 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". Revista económica estadounidense . 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 la asignación aleatoria". Revista de teoría económica . 100 (2): 295. doi :10.1006/jeth.2000.2710.
3. Hylland, Aanund; Zeckhauser, Richard (1979). "La asignación eficiente de personas 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 asignaciones múltiples. OCLC  1106222190.{{cite book}}: Mantenimiento CS1: 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". Revista de teoría económica . 131 : 231–250. doi :10.1016/j.jet.2005.05.001.
6. Hadi Hosseini, Kate Larson, Robin Cohen (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. S2CID  14041902.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
7. Zhou, Lin (1 de octubre de 1990). "Sobre una conjetura de Gale sobre problemas de coincidencia unilateral". Revista de teoría económica . 52 (1): 123-135. doi :10.1016/0022-0531(90)90070-Z. ISSN  0022-0531.
8. Demeulemeester, Tom; Goossens, Secos; Hermans, Ben; Leus, Roel (2023). "El enfoque de un pesimista hacia 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, Ricardo; Tao, Yixin (1 de abril de 2021). "Sobre la existencia de asignaciones Pareto eficientes y sin envidia". Revista de teoría económica . 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. Amigo, Conal (2022). "Asignación aleatoria igualitaria". doi :10.2139/ssrn.4197224. S2CID  252192116. SSRN  4197224.