An Optimal Procedure to Check Pareto-Optimality in House Markets with Single-Peaked Preferences
This work addresses an incremental improvement in mechanism design for resource allocation, specifically for economists and computer scientists studying house markets with single-peaked preferences.
The paper tackles the problem of checking Pareto-optimality in house markets with single-peaked preferences by proposing the Diver, a variant of the Crawler that optimally verifies allocations, improving over general techniques and proving asymptotic optimality in communication complexity.
Recently, the problem of allocating one resource per agent with initial endowments (house markets) has seen a renewed interest: indeed, while in the domain of strict preferences the Top Trading Cycle algorithm is known to be the only procedure guaranteeing Pareto-optimality, individual rationality, and strategy proofness. However, the situation differs in the single-peaked domain. Indeed, Bade presented the Crawler, an alternative procedure enjoying the same properties, with the additional advantage of being implementable in obviously dominant strategies. In this paper we further investigate the Crawler and propose the Diver, a variant which checks optimally whether an allocation is Pareto-optimal for single-peaked preferences, thus improving over known techniques used for checking Pareto-optimality in more general domains. We also prove that the Diver is asymptotically optimal in terms of communication complexity.