Housing markets through graphs

Housing market is a special type of exchange economy where each agent is endowed with one unit of an indivisible good (house) and wants to end up again with one unit, possibly the best one according to his preferences. If the endowments of all agents are pairwise different, an equilibrium as well as a core allocation always exist. However, for markets in which some agents' houses are equivalent, the existence problem for the economic equilibrium is NP-complete. In this paper we show that the hardness result is not valid if the preferences of all agents are strict, but it remains true in markets with trichotomous preferences. Further, we extend some known results about housing markets to the case with equivalent houses using graph-theoretical methods.