Credible Group-Stability in General Multi-Partner Matching Problems∗

Pairwise-stable matching mechanisms are practically used and per-form very well in the real world two-sided matching markets (e.g., the US hospital-intern market, and the British hospital-intern markets: see Roth 1984 and 1991, respectively). It is known, however, that in a two-sided many-to-many matching market (the British market), pairwise-stability is not logically related with the (weak) core unlike in a one-to-many matching market (the US market) [see Blair (1988) and Roth and Sotomayor (1990)]. In this paper, we use a graph representation of matching problems, and we define strong group-stability, a matching-variation of a solution concept in the network literature (Jackson and van den Nouweland, 2002). Although strong group-stability is equiva-lent to pairwise-stability in a one-to-many matching market, unfortu-nately, the solution concept is too strong for many-to-many matching markets. Therefore, we proceed to define executable coalitional devia-tions to discuss the credibility of coalitional deviations, and define cred-ibly group-stable matchings. We prove that credible group-stability is equivalent to pairwise-stability in a wide class of matching problems. We also prove the equivalence between the set of pairwise-stable matchings and the set of matchings resulting from coalition-proof Nash equilibria in an appropriately defined strategic form game. ∗Preliminary. Comments from Al Roth and conversations with Eiichi Miyagawa in the early stage of this research were very useful