We study housing markets as introduced by Shapley and Scarf [39]. 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 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 where a receives either h,
or a house that she 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.
