The Computational Complexity of the Housing Market
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929250039234560 |
|---|---|
| author | Lock, Edwin Qiu, Zephyr Teytelboym, Alexander |
| author_facet | Lock, Edwin Qiu, Zephyr Teytelboym, Alexander |
| contents | We prove that the classic problem of finding a competitive equilibrium in an exchange economy with indivisible goods, money, and unit-demand agents is PPAD-complete. In this "housing market", agents have preferences over the house and amount of money they end up with, but can experience income effects. Our results contrast with the existence of polynomial-time algorithms for related problems: Top Trading Cycles for the "housing exchange" problem in which there are no transfers and the Hungarian algorithm for the "housing assignment" problem in which agents' utilities are linear in money. Along the way, we prove that the Rainbow-KKM problem, a total search problem based on a generalization by Gale of the Knaster-Kuratowski-Mazurkiewicz lemma, is PPAD-complete. Our reductions also imply bounds on the query complexity of finding competitive equilibrium. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08484 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Computational Complexity of the Housing Market Lock, Edwin Qiu, Zephyr Teytelboym, Alexander Computer Science and Game Theory Computational Complexity We prove that the classic problem of finding a competitive equilibrium in an exchange economy with indivisible goods, money, and unit-demand agents is PPAD-complete. In this "housing market", agents have preferences over the house and amount of money they end up with, but can experience income effects. Our results contrast with the existence of polynomial-time algorithms for related problems: Top Trading Cycles for the "housing exchange" problem in which there are no transfers and the Hungarian algorithm for the "housing assignment" problem in which agents' utilities are linear in money. Along the way, we prove that the Rainbow-KKM problem, a total search problem based on a generalization by Gale of the Knaster-Kuratowski-Mazurkiewicz lemma, is PPAD-complete. Our reductions also imply bounds on the query complexity of finding competitive equilibrium. |
| title | The Computational Complexity of the Housing Market |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2402.08484 |