Problema de asignación de viviendas

En economía e informática , el problema de asignación de viviendas consiste en asignar objetos a personas con preferencias diferentes , de manera que cada persona reciba exactamente un objeto. El nombre «asignación de viviendas» proviene de su principal aplicación, que es la asignación de residencias estudiantiles. ^{[ 1 ]} Otros términos comúnmente utilizados son problema de asignación y emparejamiento unilateral . Cuando los agentes ya poseen viviendas (y pueden intercambiarlas con otros agentes), el problema se denomina a menudo mercado inmobiliario . ^{[ 2 ]} En los problemas de asignación de viviendas, se supone que no se permiten transferencias monetarias; la variante en la que se permiten transferencias monetarias se conoce como armonía de alquiler .

Hay n personas (también llamadas agentes ) y m objetos (también llamados casas ). Los agentes pueden tener diferentes preferencias respecto a las casas. Pueden expresar sus preferencias de diversas maneras:

• Valoraciones binarias : cada agente valora cada casa con un 1 (lo que significa que al agente le gusta la casa) o con un 0 (lo que significa que al agente no le gusta la casa).
• Clasificación por preferencias : cada agente clasifica las casas de mejor a peor. La clasificación puede ser estricta (sin preferencias) o flexible (se permiten preferencias).
• Utilidad cardinal : cada agente asigna un valor numérico no negativo a cada casa.

Existen varias consideraciones importantes a la hora de diseñar algoritmos para la asignación de viviendas.

• Eficiencia de Pareto (EP): ninguna otra asignación es mejor para algunos agentes y no peor para todos los agentes.
• Equidad : puede definirse de varias maneras, por ejemplo, ausencia de envidia (AE): ningún agente debería envidiar a otro agente.
• Inmune a la manipulación estratégica (SP): cada agente tiene un incentivo para informar sus verdaderas preferencias al algoritmo.
• Racionalidad individual (RI): ningún agente debería perder por participar en el algoritmo.

En economía , el principal requisito de eficiencia en la asignación de viviendas es la eficiencia de asignación (EA). Existen diversos algoritmos para lograr una asignación de EA en diferentes contextos.

Probablemente el algoritmo más simple para la asignación de viviendas sea la dictadura serial : los agentes se ordenan de forma arbitraria (por ejemplo, por antigüedad) y cada uno, a su vez, elige la mejor vivienda disponible según sus preferencias. Este algoritmo es obviamente SP. Si las preferencias de los agentes son estrictas, entonces se obtiene una asignación PE. Sin embargo, puede ser muy injusto para los agentes que eligen al final. Se puede hacer más justo (en promedio) eligiendo el orden de forma uniforme y aleatoria; esto da lugar al mecanismo denominado dictadura serial aleatoria . Este mecanismo es PE ex post, pero no es PE ex ante; véase asignación aleatoria justa para otros mecanismos aleatorios que son PE ex ante.

Cuando cada agente ya posee una casa, las consideraciones de equidad son menos importantes; es más importante garantizar a los agentes que no perderán por participar (IR). El algoritmo del ciclo de negociación superior es el único que garantiza IR, PE y SP. Con preferencias estrictas, TTC encuentra la asignación central estable única . ^{[ 3 ]}

Abdulkadiroglu y Sönmez ^{[ 1 ]} consideran un escenario extendido en el que algunos agentes ya poseen una casa, mientras que otros no. Su mecanismo es IR, PE y SP. Presentan dos algoritmos que implementan este mecanismo.

Ergin ^{[ 4 ]} considera reglas que también son consistentes , es decir, sus predicciones no dependen del orden en que se realizan las asignaciones.

En informática e investigación operativa , el principal requisito de eficiencia es maximizar la suma de utilidades. Encontrar una asignación de viviendas que maximice la suma de utilidades equivale a encontrar un emparejamiento de peso máximo en un grafo bipartito ponderado; también se le conoce como el problema de asignación .

Los problemas algorítmicos relacionados con la equidad del emparejamiento se han estudiado en diversos contextos.

Cuando los agentes tienen valoraciones binarias, sus relaciones de "similitud" definen un grafo bipartito en los conjuntos de agentes y casas. Una asignación de casas sin envidia corresponde a un emparejamiento sin envidia en este grafo. Se han estudiado los siguientes problemas algorítmicos.

• Decidir si existe una asignación EF completa . Esto se cumple si y solo si existe un emparejamiento que satura a todos los agentes; esto se puede decidir en tiempo polinomial simplemente encontrando un emparejamiento de cardinalidad máxima en el grafo bipartito.
• Encontrar una asignación EF parcial de cardinalidad máxima. Aigner-Horev y Segal-Halevi ^{[ 5 ] : Thm.1.6(a)} presentan un algoritmo de tiempo polinomial.
• Encontrar una asignación EF parcial de cardinalidad máxima y costo mínimo (donde cada arista tiene un costo preespecificado para la sociedad). Aigner-Horev y Segal-Halevi ^{[ 5 ] : Thm.1.6(b)} presentan un algoritmo de tiempo polinomial.
• Encontrar una asignación EF completa , en la que se minimice el número de agentes envidiosos. Kamiyama, Manurangsi y Suksompong ^{[ 6 ] : Thm.3.5} demuestran que es NP-difícil. La demostración es por reducción del problema de cobertura mínima (también conocido como expansión bipartita ). Madathil, Misra y Sethia ^{[ 7 ]} demuestran que es NP-difícil incluso cuando cada agente valora como máximo 2 casas, y W[1]-difícil cuando se parametriza por el número de agentes envidiosos. La demostración es por reducción del problema de clique máximo . Sin embargo, el problema es tratable con parámetros fijos cuando se parametriza por el número total de tipos de casas y tipos de agentes , y puede resolverse eficientemente cuando los agentes tienen preferencias de "intervalos extremos".
• Encontrar una asignación EF completa , en la que se minimice el número máximo de agentes envidiados por un solo agente. Madathil, Misra y Sethia ^{[ 7 ]} demuestran que es NP-difícil incluso cuando cada agente valora como máximo 2 casas, cada casa es aprobada por un número constante de agentes y la envidia máxima permitida es solo 1. La demostración se realiza mediante reducción a partir del conjunto independiente máximo en grafos cúbicos. Sin embargo, el problema es tratable con parámetros fijos cuando se parametriza por el número total de tipos de casas y tipos de agentes , y puede resolverse eficientemente cuando los agentes tienen preferencias de "intervalos extremos".

Cuando los agentes tienen valoraciones cardinales , el grafo de agentes y casas se convierte en un grafo bipartito ponderado . Se han estudiado los siguientes problemas algorítmicos.

• Decidir si existe una asignación completa de EF .
  • Cuando m = n , todas las casas deben ser asignadas, por lo que una asignación es EF si y solo si cada agente obtiene una casa con el valor más alto. Por lo tanto, es posible reducir el grafo original a un grafo no ponderado, en el que cada agente es adyacente solo a sus casas de mayor valor, y buscar una correspondencia perfecta en este grafo.
  • Cuando m > n , el algoritmo anterior puede no funcionar, ya que no todas las casas deben ser asignadas: incluso si una sola casa es la más preferida por todos los agentes, puede existir una asignación EF completa en la que esta casa específica no sea asignada. Gan, Suksompong y Voudouris ^{[ 8 ]} presentan un algoritmo de tiempo polinomial que decide, en tiempo polinomial, si existe una asignación EF completa para cualquier m ≥ n . Su algoritmo utiliza, como subrutina, un algoritmo para encontrar un violador de Hall mínimo de inclusión .
• Decidir si existe una asignación completamente libre de envidia local . La ausencia de envidia local significa que los agentes se encuentran en una red social y solo envidian a sus vecinos en esa red. Beynier, Chevaleyre, Gourves, Harutyunyan, Lesca, Maudet y Wilczynski ^{[ 9 ]} estudian el problema de decidir si existe una asignación completamente libre de envidia local para m = n , para diversas estructuras de red.
• Encontrar una asignación EF completa , en la que se maximice el número de agentes no envidiosos. Kamiyama, Manurangsi y Suksompong. ^{[ 6 ] : El teorema 3.1} demuestra que, bajo supuestos teóricos de complejidad comunes, este problema es difícil de aproximar. En particular, si NP no se puede resolver en tiempo subexponencial, entonces no se puede aproximar dentro de un factor de${\displaystyle n^{\gamma }}$para algunos${\displaystyle \gamma >0}$; si la hipótesis de expansión de conjuntos pequeños es verdadera, entonces no se puede aproximar con un factor de${\displaystyle n^{\gamma }}$para cualquier${\displaystyle \gamma <1}$(para${\displaystyle \gamma =1}$Es trivial aproximarlo: basta con darle a un agente su casa favorita y asignar a los demás agentes arbitrariamente. La demostración se realiza mediante reducción a partir del problema de la biclique equilibrada máxima .
• Decidir si existe una asignación proporcional completa . Kamiyama, Manurangsi y Suksompong ^{[ 6 ] : Thm.4.1} demuestran que es NP-completo , por reducción a partir de una cobertura exacta de 3 conjuntos .
• Decidir si existe una asignación equitativa completa . Kamiyama, Manurangsi y Suksompong ^{[ 6 ] : Thm.5.1} presentan un algoritmo de tiempo polinomial.
• Encontrar una asignación parcial de EF de cardinalidad máxima. La complejidad temporal de este problema es un problema abierto. ^{[ 5 ] : pregunta abierta 2}

• Problema de asignación : cada agente debe obtener un único objeto. El objetivo es maximizar la suma de las valoraciones o minimizar la suma de los costes.
• Asignación aleatoria justa : cada agente debe recibir un solo objeto. Se permite la aleatorización. La asignación debe ser justa y eficiente en términos generales.
• Armonía en el alquiler : cada agente debe obtener un solo objeto y pagar un precio; la asignación de objetos y precios debe estar libre de envidias.
• Emparejamiento sin envidia : algunos agentes pueden permanecer sin asignar, siempre y cuando no les guste ninguna de las casas asignadas.
• Asignación equitativa de objetos : cada agente puede obtener cualquier número de objetos.