Convexity of Hypergraph Matching Game

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. This game models the nature of group formation and will have applications in, e.g., organ exchange and joint purchasing. The hypergraph matching game is intractable in general because evaluating its characteristic function is already NP-hard. Thus, we study a more tractable condition, 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. Third, we show that the problem of finding a minimum compensation to make a given hypergraph matching game convex is NP-hard, even if the input is a graph, and is 2-approximable in polynomial time if the input is an antichain. 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.