Internally Stable Matchings and Exchanges


  • Yicheng Liu Tsinghua University
  • Pingzhong Tang Tsinghua University
  • Wenyi Fang Tsinghua University



internally stable, kidney exchange, welfare loss


Stability is a central concept in exchange-based mechanismdesign. It imposes a fundamental requirement that no subsetof agents could beneficially deviate from the outcome pre-scribed by the mechanism. However, deployment of stabilityin an exchange mechanism presents at least two challenges.First, it reduces social welfare and sometimes prevents themechanism from producing a solution. Second, it might incurcomputational cost to clear the mechanism.In this paper, we propose an alternative notion of stability,coined internal stability, under which we analyze the socialwelfare 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) weanalyze the computational complexity for clearing the match-ings and exchanges. Extensive experiments on the kidney ex-change domain demonstrate that the optimal welfare underinternal stability is very close to the unconstrained optimal.




How to Cite

Liu, Y., Tang, P., & Fang, W. (2014). Internally Stable Matchings and Exchanges. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).



AAAI Technical Track: Multiagent Systems