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.
翻译:----
我们将房屋市场作为Shapley和Scarf(1974)所介绍的一项研究对象。我们研究了关于代理人a在房屋市场H中的情况的各种问题的计算复杂性:我们证明找到满足以下条件的房屋市场H中的核心分配方案是NP难问题:(i) a获得一个特定房子,(ii) a不获得特定房子或(iii) a获得不是她自己房子的房子。我们证明了房屋市场的核心具有下面的改进特性:在由房屋市场H中代理a获得房屋h的核心分配方案中,如果a拥有的房屋价值增加,那么所得到的房屋市场将允许在核心分配中找到这样的分配方案:a要么收到h,要么得到了比h更喜欢的房屋; 而且这样的分配方案可以有效地找到。我们进一步证明了稳定室友配对设置中的类似结果,通过证明单边市场上稳定匹配也具有改进特性。