The core of housing markets from an agent's perspective: Is it worth sprucing up your home?
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909067217207296 |
|---|---|
| author | Schlotter, Ildikó Biró, Péter Fleiner, Tamás |
| author_facet | Schlotter, Ildikó Biró, Péter Fleiner, Tamás |
| contents | We study housing markets as introduced by Shapley and Scarf (1974). We investigate the computational complexity of various questions regarding the situation of an agent $a$ in a housing market $H$: we show that it is $\mathsf{NP}$-hard to find an allocation in the core of $H$ where (i) $a$ receives a certain house, (ii) $a$ does not receive a certain house, or (iii) $a$ receives a house other than her own. We prove that the core of housing markets respects improvement in the following sense: given an allocation in the core of $H$ where agent $a$ receives a house $h$, if the value of the house owned by $a$ increases, then the resulting housing market admits an allocation in its core in which $a$ receives either $h$, or a house that $a$ prefers to $h$; moreover, such an allocation can be found efficiently. We further show an analogous result in the Stable Roommates setting by proving that stable matchings in a one-sided market also respect improvement. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_06875 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The core of housing markets from an agent's perspective: Is it worth sprucing up your home? Schlotter, Ildikó Biró, Péter Fleiner, Tamás Computer Science and Game Theory Data Structures and Algorithms 91A68, 68Q17, 91B52, 91B54, 91B68 We study housing markets as introduced by Shapley and Scarf (1974). We investigate the computational complexity of various questions regarding the situation of an agent $a$ in a housing market $H$: we show that it is $\mathsf{NP}$-hard to find an allocation in the core of $H$ where (i) $a$ receives a certain house, (ii) $a$ does not receive a certain house, or (iii) $a$ receives a house other than her own. We prove that the core of housing markets respects improvement in the following sense: given an allocation in the core of $H$ where agent $a$ receives a house $h$, if the value of the house owned by $a$ increases, then the resulting housing market admits an allocation in its core in which $a$ receives either $h$, or a house that $a$ prefers to $h$; moreover, such an allocation can be found efficiently. We further show an analogous result in the Stable Roommates setting by proving that stable matchings in a one-sided market also respect improvement. |
| title | The core of housing markets from an agent's perspective: Is it worth sprucing up your home? |
| topic | Computer Science and Game Theory Data Structures and Algorithms 91A68, 68Q17, 91B52, 91B54, 91B68 |
| url | https://arxiv.org/abs/2110.06875 |