Convexity of b-matching Games

Abstract

The b-matching game is a cooperative game defined on a graph. The game generalizes the matching game to allow each individual to have more than one partner. The game has several applications, such as the roommate assignment, the multi-item version of the seller-buyer assignment, and the international kidney exchange. Compared with the standard matching game, the b-matching game is computationally hard. In particular, the core non-emptiness problem and the core membership problem are co-NP-hard. Therefore, we focus on the convexity of the game, which is a sufficient condition of the core non-emptiness and often more tractable concept than the core non-emptiness. It also has several additional benefits. In this study, we give a necessary and sufficient condition of the convexity of the b-matching game. This condition also gives an O(n log n + m α(n)) time algorithm to determine whether a given game is convex or not, where n and m are the number of vertices and edges of a given graph, respectively, and α(・) is the inverse-Ackermann function. Using our characterization, we also give a polynomial-time algorithm to compute the Shapley value of a convex b-matching game.