修士論文 要旨

Convexity of Generalized Matching Games（一般化マッチングゲームの凸性）
隈部 壮

数理情報学専攻 48-196213

平井 広志 准教授

指導教員

treat games such that ν(X) is deﬁned by the optimal

1 Cooperative Gamesvalue of a combinatorial optimization problem on theThe cooperative game theory, whose history goessubstructure X. In this thesis, we consider the fol-back to the seminal work of von Neumann and Mor-lowing two games.

genstern [13], treats the situation in which the players

Hypergraph Matching Game [4, 5] Let G = (V, E) becan gain larger proﬁts by cooperating to each other.

a hypergraph and c : E → R>0 be a weight function.

The main conceptual problem of cooperative gameThe player set of this game is V and ν(X) is given by

theory is to ﬁnd a “good way”, referred to as a so-the maximum weight of the hypergraph matching oflution concept, to distribute the value to the players

G[X]. Here, the hypergraph matching is a subset M

when all players cooperate.

of hyperedges such that each vertex in V is contained

From computational aspect, researchers are inter-in at most one hyperedge of M .

ested in algorithms related to the concepts of “goodways”. This is the one of the main interests of com-b-matching Game [2, 11] Let G = (V, E) be a graph,putational cooperative game theory [3].

b : V → Z>0 be a budget function and c : E → R>0

Let us formulate cooperative game mathematically.

be a weight function. The player set of this game isA cooperative game (V, ν) is given by a ﬁnite set V

V and ν(X) is given by the maximum weight of the→ R with ν(∅) = 0, whereb-matching of G[X]. Here, a b-matching of G[X] is a

and a function ν : 2Vvector x ∈ ZE
≥0 such that

V is the set of n players and ν is the characteristic∑

function such that ν(X) indicates the value if players
X ⊆ V form a coalition.
One of the most famous solution concepts is theSeveral research investigate the convexity in op-formulaX⊆V \{v}

|V |!

(3)

holds for all v ∈ X.

Shapley value [9], which is explicitly deﬁned by the∑ |X|!(|V | − |X| − 1)!

x(e) ≤ b(v)e is incident to v

timization problem games.
(ν(X ∪ {v}) − ν(X)). (1)checkable characterization is known for matroid minimum base game [8], minimum spanning tree game [7],and represent the fair distribution.

and minimum coloring game and minimum vertex

A convex game [10] is a class of games with several

cover game.

desirable properties. Formally, a cooperative gameis convex if its characteristic function ν : 2

The polynomial-timeV

It is investigated the structure of

the convex hypergraph matching game [4], although→ R ispolynomial-time characterization is not given.

supermodular, i.e., the following inequality holds for

3 Our Contribution

all X, Y ⊆ V [6]:ν(X) + ν(Y ) ≤ ν(X ∩ Y ) + ν(X ∪ Y ).

In this thesis, we investigate computational prob-(2)lems and structures related to the convexity of the hypergraph matching game and the b-matching game.

2 Optimization Problem GamesOur main contribution is a polynomial-time algoThe research of optimization problem games isrithm to solve the following problems.

started by Shapley and Shubik [10], who deﬁned theProblem 1. Given a hypergraph matching game, de-assignment game. In this line of research, researchers1termine it is convex or not.

instances of the hypergraph matching game are nonconvex. Therefore, we consider modifying the game

Problem 2. Given a b-matching game, determine itby compensating the vertices not in the matching tois convex or not.

make the game convex.

For the both games, we establish a necessary andProblem 5. Given a hypergraph matching game,

suﬃcient condition of the convexity and construct ancompute the minimum total compensation to makealgorithm for checking the condition eﬃciently.

the game convex.

For the hypergraph matching game, we prove that
it is suﬃcient to check polynomial number of super-

We prove that this problem is NP-hard in generalmodular inequalities (2) to check the convexity of theand admits a 2-approximation algorithm if the wholegame. To prove this, we use a structural lemma ongraph is an antichain.

“essential” hyperedges. For the b-matching game,

参考文献

we can state much about its structure for the con-[1] Haris Aziz and Bart de Keijzer. Shapley meets Shapley. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science(STACS’14), pages 99–111, 2014.
[2] Péter Biró, Walter Kern, Daniël Paulusma, andPéter Wojuteczky.
The stable ﬁxture problemwith payments. Games and Economic Behaviour,
108:245–268, 2018.
[3] Georgios Chalkiadakis, Edith Elkind, and Michael
Wooldridge. Computational aspects of cooperative
game theory. Synthesis Lectures on Artiﬁcial Intelligence and Machine Learning, 5(6):1–168, 2011.
[4] Vincent Conitzer and Tuomas Sandholm. Complexity of constructing solutions in the core based onsynergies among coalitions. Artiﬁcial Intelligence,170(6-7):607–619, 2006.
[5] Xiaotie Deng, Toshihide Ibaraki, and Hiroshi Nagamochi. Algorithmic aspects of the core of combinatorial optimization games. Mathematics of Operations Research, 24(3):751–766, 1999.
[6] Satoru Fujishige. Submodular Functions and Optimization. Elsevier, Amsterdam, 2005.
[7] Zhuan Khye Koh and Laura Sanità. An eﬃcientcharacterization of submodular spanning tree games.
In International Conference on Integer Programming and Combinatorial Optimization, pages 275–287. Springer, 2019.
[8] Hiroshi Nagamochi, Dao-Zhi Zeng, Naohisa Kabutoya, and Toshihide Ibaraki. Complexity of the minimum base game on matroids. Mathematics of Operations Research, 22(1):146–164, 1997.
[9] Lloyd S Shapley. A value for n-person games. Contributions to the Theory of Games, 2(28):307–317,1953.
[10] Lloyd S Shapley and Martin Shubik. The assignment
game I: The core. International Journal of Game
Theory, 1(1):111–130, 1971.
[11] Marilda Sotomayor. The Multiple Partners Game.
MacMillan, London, 1992.
[12] Richard P Stanley. Enumerative Combinatorics:
Volume 1. Cambridge University Press, 2nd edition,2011.
[13] John von Neumann and Oskar Morgenstern. Theoryof Games and Economic Behavior. Princeton University Press, Princeton, 1947.

vex case. Speciﬁcally, we show that the whole graphshould be the comparability graph of a branching.
Computing the Shapley value already #P-hard tocalculate for a matching game [1], which is a common
case of the hypergraph matching game and the bmatching game. Here, we restrict the instance into
convex games and give polynomial-time algorithms
to the following problems.
Problem 3. Given a convex hypergraph matchinggame, compute the Shapley value.
Problem 4. Given a convex b-matching game, compute the Shapley value.
The algorithms heavily depend on our characterizations of the convexity. For both games,we observethat the marginal gain, ν(X ∪{v})−ν(X), takes polynomial number of diﬀerent values. For each value, we
count the number of the pair (X, v) with that value ofmarginal gain. For the hypergraph matching game,
this number is computed by the double-counting argument with the Möbius inversion formula [12]. For
the b-matching game, we explicitly write this number
using the branching that deﬁnes the whole graph.
Since the fractional relaxation of the matchingproblems deﬁne diﬀerent problems, they deﬁne diﬀerent games. However, we prove that, in convex casethey coincide; the fractional versions are convex ifand only if the corresponding integral versions areconvex.
Because the convexity is a strong condition, most2