La asignación aleatoria justa (también llamada coincidencia probabilística unilateral ) es una especie de problema de división justa .
En un problema de asignación (también llamado emparejamiento unilateral ), hay m objetos y deben asignarse entre n agentes. Por lo general, m ≤ n , y cada agente debe recibir como máximo un objeto. Los ejemplos incluyen la asignación de trabajos a los trabajadores, habitaciones a los compañeros de casa, dormitorios a los estudiantes, intervalos de tiempo a los usuarios de una máquina común, etc.
En general, una asignación justa puede ser imposible de lograr. Por ejemplo, si Alice y Batya prefieren la habitación del este a la habitación del oeste, solo uno de ellos lo 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 usó 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 usa para asignar tarjetas verdes . [1]
Métodos
Hay varias formas de extender el método de "lanzamiento de moneda" a situaciones en las que hay más de dos agentes, y pueden tener diferentes relaciones de preferencia sobre los objetos: [2] [3] [4]
- 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 en los elementos y permite que cada agente elija a su vez su elemento restante favorito.
- Serie probabilística (PS) es otro mecanismo que solo funciona con la clasificación ordinal de los elementos. Los agentes "comen" sus artículos favoritos restantes a una velocidad constante, y la fracción que cada agente logró comer es su probabilidad de obtener este artículo.
- El Equilibrio Competitivo por Igualdad de Ingresos (CEEI) es un mecanismo basado en el mercado: cada artículo se considera un producto divisible. A cada agente se le da-parto de cada mercancía, entonces los agentes pueden comerciar hasta que haya equilibrio. [5] Este es un mecanismo más complejo que requiere que los agentes tengan funciones de utilidad cardinal completas (o, alternativamente, clasificación ordinal en loterías).
Propiedades
Una propiedad deseada de una regla de asignación aleatoria es la eficiencia de Pareto (PE). Hay dos variantes de PE:
- La EP ex post significa que, una vez que se determina 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 fuerte. Significa que ninguna otra lotería es mejor para algún agente y al menos tan buena para los demás. Para definir esta propiedad, es importante saber cómo los agentes comparan las loterías. CEEI es PE ex ante cuando los agentes comparan loterías en función de su utilidad esperada. PS es PE ex ante cuando los agentes comparan las loterías por dominancia estocástica (esta propiedad se llama PE ex ante sd ). Por el contrario, RP no es EP ex ante.
Otra propiedad deseada es la ausencia de envidia (EF). Nuevamente, hay dos variantes de EF:
- Ex-post EF significa que, después de que se determina 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 EF ex-post de objetos indivisibles.
- Ex ante EF significa que ningún agente prefiere la lotería de otro agente. Nuevamente, definir esta propiedad requiere saber cómo los agentes comparan las loterías. CEEI es ex ante EF wrt servicios públicos esperados. PS es ex-ante EF con dominancia estocástica (esta propiedad se llama ex-ante sd-EF ). RP es débilmente ex ante sd-EF; es EF cuando los agentes comparan las loterías por dominancia lexicográfica (LD-EF). [6]
Una tercera propiedad deseada es la veracidad (también llamada resistencia a la estrategia). CEEI no es veraz. PS es débilmente sd-veraz cuando hay como máximo un objeto por persona; en este contexto también es veraz con dominio lexicográfico ( ld-veraz ). [6] RP es sd-veraz en este caso, y puede extenderse 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 [7] ):
#artículos ≤ #agentes | #artículos> #agentes | |||||
---|---|---|---|---|---|---|
RP | PD | CEEI | RP | PD | CEEI | |
Eficiencia ex ante | No | sd-PE | EDUCACIÓN FÍSICA | No | sd-PE | EDUCACIÓN FÍSICA |
Equidad ex ante | Sd-EF débil; ld-EF | sd-EF | EF | SD-EF débil | sd-EF | EF |
Veracidad | sd-veraz | Débil sd-veraz; ld-veraz | No | sd-veraz * | No | No |
Descomposición de una asignación fraccionada
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 un emparejamiento, se debe encontrar una descomposición de esta matriz en una lotería de emparejamientos.
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 2 ) , 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] El algoritmo de generalizar Birkhoff a arbitraria m y n . 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 Roel [8] presentan un algoritmo de descomposición en tiempo polinómico 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 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 al tiempo que garantiza que todos los emparejamientos en la descomposición sean ex-post PE; 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 en el peor de los casos sujetos a PE ex post 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 [7] comparan RP con PS en varios 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 no sd-envy-free, y en la mayoría de los casos, PS domina 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, suponga que hay tres objetos a, b, cy tres agentes con clasificación de preferencias (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; para el 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 para el 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 que PS sd domina RP es grande cuando el número de agentes y objetos difiere, pero se acerca a 0 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 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 RP, y la diferencia crece rápidamente cuando n ≠ m. Por el contrario, cuando n = m RP logra 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 la 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 permanece por debajo de 0.01 cuando n ≥ m . La manipulabilidad de PS pasa a 1 cuando m / n crece.
Utilidades no lineales
Tao y Cole [9] estudian la existencia de asignaciones aleatorias de PE y EF cuando las utilidades no son lineales (pueden tener complementos).
Ver también
- La armonía del alquiler es una variante del problema de la asignación en la 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.
- Clasificación : selección aleatoria de funcionarios políticos.
Referencias
- ^ a b 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 .
- ^ Bogomolnaia, Anna ; Moulin, Hervé (2001). "Una nueva solución al problema de asignación aleatoria". Revista de teoría económica . 100 (2): 295. doi : 10.1006 / jeth.2000.2710 .
- ^ 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 .
- ^ 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 .
- ^ 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 .
- ^ a b 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 .
- ^ a b 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 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Demeulemeester, Tom; Goossens, Dries; Hermans, Ben; Leus, Roel (3 de enero de 2021). "Aversión al riesgo en el emparejamiento unilateral". arXiv : 2101.00579 [ cs.DS ].
- ^ Cole, Richard; Tao, Yixin (1 de abril de 2021). "Sobre la existencia de asignaciones Pareto Eficientes y libres de envidia" . Revista de teoría económica . 193 : 105207. arXiv : 1906.07257 . doi : 10.1016 / j.jet.2021.105207 . ISSN 0022-0531 . S2CID 189999837 .