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.
Keywords
- Agent-based and Multi-agent Systems: Algorithmic Game Theory
- Agent-based and Multi-agent Systems: Cooperative Games
