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 pre-scribed 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 contribu-tions are as follows: for both pairwise matchings and limited-length exchanges, for both unweighted and weighted graph-s, (1) we prove desirable tight social welfare bounds; (2) we analyze the computational complexity for clearing the match-ings and exchanges. Extensive experiments on the kidney ex-change domain demonstrate that the optimal welfare under internal stability is very close to the unconstrained optimal