Convexity of B-Matching Games

Abstract

The b-matching game is a cooperative game defined on a graph, which 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. In contrast to the matching game, the b-matching game is computationally hard, i.e., 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, often more tractable than the core non-emptiness, and has several additional benefits. In this study, we give a necessary and sufficient condition of the convexity of the b-matching game, which yields 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, 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.