Internally Stable Matchings and Exchanges

Stability is a central concept in exchange-based mechanism design. It imposes a fundamental requirement that no subset of agents could beneficially deviate from the outcome prescribed by the mechanism. However, deployment of stability in an exchange mechanism presents at least two challenges. First, it reduces social welfare and sometimes prevents the mechanism from producing a solution. Second, it might incur computational cost to clear the mechanism. In this paper, we propose an alternative notion of stability, coined internal stability, under which we analyze the social welfare bounds and computational complexity. Our contributions are as follows: for both pairwise matchings and limitedlength exchanges, for both unweighted and weighted graphs, (1) we prove desirable tight social welfare bounds; (2) we analyze the computational complexity for clearing the matchings and exchanges. Extensive experiments on the kidney exchange domain demonstrate that the optimal welfare under internal stability is very close to the unconstrained optimal.

Authors

• Yicheng Liu Harbin Institute of Technology, Shenzhen
• Pingzhong Tang Institute for Interdisciplinary Information Sciences, Tsinghua University
• Wenyi Fang Tsinghua University

Keywords

No keywords are indexed for this paper.