Mechanism Design for Housing Markets over Social Networks

In this paper we investigate the effect of an underlying social network over agents in a well-known multi-agent resource allocation problem; the housing market. We first show that, when a housing market takes place over a social network with more than two agents and these agents have an option to avoid forwarding information about it to their followers, there does not exist an exchange mechanism that simultaneously satisfies strategy-proofness, Pareto efficiency, and individual rationality. It is also impossible to find a strategy-proof exchange mechanism that always chooses an outcome in a weakened core. These results highlight the difficulty of taking into account the agents' incentive of information diffusion in the resource allocation. To overcome these negative results, we consider two different ways of restricting the problem; limiting the domain of preferences and the structure of social networks.