Problema de asignación de viviendas

En economía e informática , el problema de asignación de casas es el problema de asignar objetos a personas con diferentes preferencias , de modo que cada persona reciba exactamente un objeto. El nombre "asignación de viviendas" proviene de la principal aplicación motivadora: la asignación de residencias a los estudiantes. ^[1] Otros términos comúnmente utilizados son problema de asignación y coincidencia unilateral . Cuando los agentes ya poseen casas (y pueden negociarlas con otros agentes), el problema suele denominarse 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 .

Definiciones

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

• Valoraciones binarias : cada agente valora cada casa en 1 (lo que significa que al agente le gusta la casa) o 0 (lo que significa que al agente no le gusta la casa).
• Ranking de preferencias : cada agente clasifica las casas de mejor a peor. La clasificación puede ser estricta (sin indiferencias) o débil (indiferencias permitidas).
• Utilidad cardinal : cada agente asigna un valor numérico no negativo a cada casa.

Varias consideraciones pueden ser importantes al diseñar algoritmos para la asignación de viviendas.

• Eficiencia de Pareto (PE): ninguna otra asignación es mejor para algunos agentes ni peor para todos los agentes.
• Equidad : se puede definir de varias maneras, por ejemplo, ausencia de envidia (EF): ningún agente debe envidiar a otro agente.
• A prueba de estrategias (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.

Asignaciones eficientes

En economía , el principal requisito de eficiencia en la asignación de viviendas es el PE. Existen varios algoritmos para lograr una asignación de PE en diversos entornos.

Probablemente el algoritmo más simple para la asignación de casas es la dictadura en serie : los agentes se ordenan en algún orden arbitrario (por ejemplo, por antigüedad) y cada agente, a su vez, elige la mejor casa restante según sus preferencias. Este algoritmo es obviamente SP. Si las preferencias de los agentes son estrictas, entonces encuentra una asignación de PE. Sin embargo, puede resultar muy injusto para los agentes que eligen en último lugar. Puede hacerse más justo (en expectativa) eligiendo el orden uniformemente al azar; esto conduce al mecanismo llamado dictadura en serie aleatoria . El 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 comercial superior es el algoritmo único que garantiza IR, PE y SP. Con preferencias estrictas, TTC encuentra la asignación única de núcleo estable . ^[3]

Abdulkadiroglu y Sönmez ^[1] consideran un escenario extendido en el que algunos agentes ya poseen una casa mientras que otros no tienen casa. 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 de operaciones , el principal requisito de eficiencia es maximizar la suma de utilidades. Encontrar una asignación de vivienda que maximice la suma de servicios públicos equivale a encontrar una coincidencia de peso máximo en un gráfico bipartito ponderado; también se le llama problema de asignación .

Asignaciones justas

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

Cuando los agentes tienen valoraciones binarias, sus relaciones "similares" definen un gráfico bipartito en los conjuntos de agentes y casas. Una asignación de casa libre de envidia corresponde a una coincidencia libre de envidia en este gráfico. Se han estudiado los siguientes problemas algorítmicos.

• Decidir si existe una asignación completa del EF . Esto es válido si existe un emparejamiento que sature a todos los agentes; esto se puede decidir en tiempo polinomial simplemente encontrando una coincidencia de cardinalidad máxima en el gráfico bipartito.
• Encontrar una asignación EF parcial de máxima cardinalidad. Aigner-Horev y Segal-Halevi ^{[5] : Thm.1.6(a)} presenta un algoritmo politiempo.
• Encontrar una asignación parcial de EF de cardinalidad máxima y costo mínimo (donde cada ventaja tiene un costo preespecificado para la sociedad). Aigner-Horev y Segal-Halevi ^{[5] : Thm.1.6(b)} presentan un algoritmo politiempo.
• 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-duro. La prueba es la 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 está parametrizado por el número de agentes envidiosos. La prueba es por reducción del problema de camarilla máxima . Sin embargo, el problema es manejable con parámetros fijos cuando se parametriza por el número total de tipos de casas y tipos de agentes , y se puede resolver de manera eficiente 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 prueba es por reducción del conjunto máximo independiente en gráficas cúbicas. Sin embargo, el problema es manejable con parámetros fijos cuando se parametriza por el número total de tipos de casas y tipos de agentes , y se puede resolver de manera eficiente cuando los agentes tienen preferencias de "intervalos extremos".

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

• Decidir si existe una asignación completa del EF .
  • Cuando m = n , se deben asignar todas las casas, por lo que una asignación es EF si cada agente obtiene una casa con el valor más alto. Por lo tanto, es posible reducir el gráfico original a un gráfico no ponderado, en el que cada agente es adyacente sólo a sus casas de mayor valor, y buscar una coincidencia perfecta en este gráfico.
  • 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 esté 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 infractor de Hall con inclusión mínima .
• Decidir si existe una asignación local completa y libre de envidia . La ausencia de envidia local significa que los agentes están ubicados 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 local completa y libre de envidia para m = n , para varias 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] : Thm.3.1} demuestra que, bajo el supuesto teórico de complejidad común, este problema es difícil de aproximar. En particular, si NP no puede resolverse en tiempo subexponencial, entonces no puede aproximarse dentro de un factor de para algunos ; Si la hipótesis de la expansión de conjuntos pequeños es cierta, entonces no se puede aproximar dentro de un factor de para ninguno (porque es trivial aproximar: basta con darle a un agente su casa favorita y asignar a los demás agentes arbitrariamente). La prueba es por reducción del problema biclique máximo equilibrado . ${\displaystyle n^{\gamma }}$ ${\displaystyle \gamma >0}$ ${\displaystyle n^{\gamma }}$ ${\displaystyle \gamma <1}$ ${\displaystyle \gamma =1}$
• Decidir si existe una asignación proporcional completa . Kamiyama, Manurangsi y Suksompong ^{[6] : Thm.4.1} demuestran que es NP-completo, mediante reducción de la cobertura exacta de 3 conjuntos .
• Decidir si existe una asignación equitativa completa . Kamiyama, Manurangsi y Suksompong ^{[6] : Thm.5.1} presentan un algoritmo politiempo.
• Encontrar una asignación EF parcial de máxima cardinalidad. La complejidad del tiempo de ejecución de este problema es abierta. ^{[5] : pregunta abierta 2}

Problemas relacionados

• Problema de asignación : cada agente debe obtener un único objeto. El objetivo es maximizar la suma de valoraciones o minimizar la suma de costos.
• Asignación aleatoria justa : cada agente debe obtener un único objeto. Se permite la aleatorización. La asignación debe ser justa y eficiente según las expectativas.
• Armonía en el alquiler : cada agente debe adquirir un único objeto y pagar un precio; la asignación de objetos+precios debe estar libre de envidia.
• Emparejamiento sin envidia : algunos agentes pueden permanecer sin asignar, siempre y cuando no les guste ninguna de las casas asignadas.
• Asignación justa de artículos : cada agente puede obtener cualquier cantidad de objetos.

Referencias

1. Abdulkadiroğlu, Atila; Sönmez, Tayfun (1 de octubre de 1999). "Asignación de viviendas con inquilinos existentes". Revista de teoría económica . 88 (2): 233–260. doi : 10.1006/jeth.1999.2553 . ISSN  0022-0531.
2. Aziz, Haris; Keijzer, Bart de (2012). "Mercados inmobiliarios con indiferencias: una historia de dos mecanismos". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 26 (1): 1249-1255. doi : 10.1609/aaai.v26i1.8239 . ISSN  2374-3468. S2CID  15395473.
3. Roth, Alvin E. (1 de enero de 1982). "Compatibilidad de incentivos en un mercado con bienes indivisibles". Cartas de Economía . 9 (2): 127-132. doi :10.1016/0165-1765(82)90003-9. ISSN  0165-1765.
4. Ergin, Haluk İ. (1 de agosto de 2000). "Coherencia en los problemas de asignación de viviendas". Revista de Economía Matemática . 34 (1): 77–97. doi :10.1016/S0304-4068(99)00038-5. hdl : 11693/18154 . ISSN  0304-4068.
5. Segal-Halevi, Erel; Aigner-Horev, Elad (2022). "Emparejamientos sin envidia en gráficos bipartitos y sus aplicaciones a la división justa". Ciencias de la Información . 587 : 164–187. arXiv : 1901.09527 . doi : 10.1016/j.ins.2021.11.059. S2CID  170079201.
6. Kamiyama, Naoyuki; Manurangsi, Pasin; Suksompong, Warut (1 de julio de 2021). "Sobre la complejidad de la asignación justa de viviendas". Cartas de investigación operativa . 49 (4): 572–577. arXiv : 2106.06925 . doi :10.1016/j.orl.2021.06.006. ISSN  0167-6377. S2CID  235422019.
7. Madathil, Jayakrishnan; Misra, Neeldhara; Sethia, Aditi (30 de mayo de 2023). "La complejidad de minimizar la envidia en la asignación de viviendas". Actas de la Conferencia Internacional de 2023 sobre Agentes Autónomos y Sistemas Multiagente . AAMAS '23. Richland, SC: Fundación Internacional para Agentes Autónomos y Sistemas Multiagentes: 2673–2675. ISBN 978-1-4503-9432-1.
8. Gan, Jiarui; Suksompong, Warut; Voudouris, Alexandros A. (1 de septiembre de 2019). "Libre de envidia en los problemas de asignación de viviendas". Ciencias Sociales Matemáticas . 101 : 104-106. arXiv : 1905.00468 . doi : 10.1016/j.mathsocsci.2019.07.005. ISSN  0165-4896. S2CID  143421680.
9. Beynier, Aurélie; Chevaleyre, Yann; Gourvès, Laurent; Harutyunyan, Ararat; Lesca, Julián; Maudet, Nicolás; Wilczynski, Anaëlle (1 de septiembre de 2019). "Libre de envidia local en los problemas de asignación de viviendas". Agentes Autónomos y Sistemas Multiagente . 33 (5): 591–627. doi :10.1007/s10458-019-09417-x. ISSN  1573-7454. S2CID  51869987.