Problema de asignación de viviendas

En economía y ciencias de la computación , el problema de asignación de viviendas 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, que es la asignación de casas dormitorio a los estudiantes. ^[1] Otros términos comúnmente utilizados son problema de asignación y emparejamiento unilateral . Cuando los agentes ya poseen casas (y pueden intercambiarlas con otros agentes), el problema a menudo se denomina mercado de vivienda . ^[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 diversas maneras:

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

Hay varias consideraciones que pueden ser 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 ni peor para todos los agentes.
• Equidad : se puede definir de varias maneras, por ejemplo, ausencia de envidia (FE): ningún agente debería 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 requisito de eficiencia principal en la asignación de viviendas es el PE. Existen varios algoritmos para lograr una asignación de PE en diferentes entornos.

Probablemente el algoritmo más simple para la asignación de casas es la dictadura serial : 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 PE. Sin embargo, puede ser muy injusto para los agentes que eligen en último lugar. Puede hacerse más justo (en expectativa) eligiendo el orden de manera uniforme al azar; esto conduce al mecanismo llamado dictadura serial aleatoria . El mecanismo es PE ex post, pero no es PE ex ante; consulte la 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 de ciclo comercial superior es el único algoritmo que garantiza IR, PE y SP. Con preferencias estrictas, TTC encuentra la única asignación estable de núcleo . ^[3]

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

Asignaciones justas

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

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

• Decidir si existe una asignación completa de EF . Esto se cumple si existe una correspondencia que sature a todos los agentes; esto se puede decidir en tiempo polinomial simplemente encontrando una correspondencia de cardinalidad máxima en el gráfico bipartito.
• Búsqueda de una asignación EF parcial de cardinalidad máxima. Aigner-Horev y Segal-Halevi ^{[5] : Thm.1.6(a)} presentan un algoritmo politemporal.
• Encontrar una asignación de EF parcial de cardinalidad máxima y costo mínimo (donde cada arista tiene un costo preestablecido para la sociedad). Aigner-Horev y Segal-Halevi ^{[5] : Thm.1.6(b)} presentan un algoritmo politemporal.
• 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} prueban que es NP-hard. La prueba es por reducción del problema de cobertura mínima (también conocido como expansión bipartita ). Madathil, Misra y Sethia ^[7] prueban que es NP-hard incluso cuando cada agente valora como máximo 2 casas, y W[1]-hard cuando se parametriza 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 casa y tipos de agente , y se puede resolver de manera eficiente cuando los agentes tienen preferencias de "intervalos extremos".
• Encontrar una asignación de 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-hard 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 independiente máximo en gráficos cúbicos. 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 de EF .
  • Cuando m = n , se deben asignar todas las casas, 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 gráfico original a un gráfico no ponderado, en el que cada agente es adyacente solo a sus casas de mayor valor, y buscar una correspondencia 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 completa de EF 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 completa de EF para cualquier m ≥ n . Su algoritmo utiliza, como subrutina, un algoritmo para encontrar un violador de Hall de inclusión mínima .
• Decidir si existe una asignación completamente libre de envidia local . 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 completamente libre de envidia local para m = n , para varias estructuras de red.
• Encontrar una asignación de EF completa , en la que se maximice el número de agentes no envidiosos. Kamiyama, Manurangsi y Suksompong. ^{[6] : Teoría 3.1.} Pruebe que, bajo el supuesto teórico de la complejidad común, 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 para algún ; si la hipótesis de expansión de conjuntos pequeños es verdadera, entonces no se puede aproximar dentro de un factor de para ningún (ya que es trivial aproximarse: simplemente déle a un agente su casa favorita y asigne a los otros agentes arbitrariamente). La prueba es por reducción del problema biclique máximo balanceado . ${\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] : Teoría 4.1} demuestran que es NP-completa, mediante 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 politiempo.
• Encontrar una asignación de EF parcial de cardinalidad máxima. La complejidad de 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 recibir un único objeto. Se permite la aleatorización. La asignación debe ser justa y eficiente.
• Armonía en el alquiler : cada agente debe obtener un único objeto y pagar un precio; la asignación de objetos + precios debe estar libre de envidia.
• Coincidencia sin envidia : algunos agentes pueden permanecer sin asignar, siempre y cuando no les guste ninguna de las casas asignadas.
• Asignación justa de objetos : cada agente puede obtener cualquier cantidad de objetos.

Referencias

1. Abdulkadiroğlu, Atila; Sönmez, Tayfun (1999-10-01). "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". Economics Letters . 9 (2): 127–132. doi :10.1016/0165-1765(82)90003-9. ISSN  0165-1765.
4. Ergin, Haluk İ. (1 de agosto de 2000). "Consistencia en 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 grafos 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 Multiagente: 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.