technical paper
Convexity of Hypergraph Matching Game
DOI: 10.48448/v3ez-9023
The hypergraph matching game is a cooperative game defined on a hypergraph such that the vertices are the players, and the characteristic function is the value of a maximum hypergraph matching on a hypergraph induced by a coalition. In this talk, we study a computationally tractable condition of the hypergraph matching game, called the convexity. First, we prove that the problem of checking whether a given hypergraph matching game is convex or not is solvable in polynomial time. Second, we prove that the Shapley value of a given convex hypergraph matching game is exactly computable in polynomial time. Finally, we consider the fractional hypergraph matching game and prove that if the fractional hypergraph matching game is convex, then its characteristic function coincides with the characteristic function of the corresponding (integral) hypergraph matching game.