Computing Least Cores ofSupermodular Cooperative
Games (AAAI’17)
波多野大督(NII)（Joint work with 𠮷𠮷田悠一 (NII & PFI)）

河原林ERATO感謝祭シーズンⅣ
2017年8月4日

An example of the cooperative game
• Given ( , )
• ={}
•
= 15
•
= 25
•
= 30
•
= 30
•
= 50
•
= 50
•
= 80

= 80

Find a value division

violate

• 𝑥𝑥
• 𝑥𝑥
• 𝑥𝑥

= 15
= 35
= 30

leave from the cooperation2

An example of the cooperative game
• Given ( , )
= 80
• ={}
•
= 15
Find a value division
•
= 25
• 𝑥𝑥
= 15
•
= 30
• 𝑥𝑥
= 30
•
= 30
• 𝑥𝑥= 35•
= 50
No violation!
•= 50
•
= 80
No one leaves3

A goal of the cooperative gameFinding a core can be described as the following program• A value division• A value division is in the core if

for allFinding a core of a cooperative game is NP-complete
Supermodular cooperative game4Supermodular cooperative game• Supermodular cooperative game is a cooperative gamewhere a characteristic function 𝜈𝜈 is supermodular• Applications• Induced subgraph game [Deng and Papadimitriou 1994]• Airport game [Littlechild and Owen 1973]• Bidder collusion game [Graham, Marshall and Richard 1990]• Multicast tree game [Feigenbaum, Papadimitriou andShenker 2001]• Bankruptcy game [O’Neill 1982]
5

An application of the supermodular cooperative gameInduced subgraph game

• Weighted hypergraph:• Characteristic function ∶ 2𝑉𝑉 → ℝ+ is the total weight ofhyperedges
such that every vertex in belongs toExample:
1e1
1e2

6

An example of induced subgraph gameIn a certain K-project…
• Professor K gives bonuses depending on the number of
accepted top conference-papers• Want to find a bonus division in the core
1
AAAI

1
ICML

※この例はフィクションであり、実在する人物、団体等とは一切関係ありません7Motivation• Property of supermodular cooperative game

• A value division called Shapley value is always in thecore• Focus on more general solution concepts than thecore• Want to find the stablest value division• Strong least core
• Weak least core8

Goal of our work
• Goal is to find the strong and weak least core valuesof supermodular cooperative game• The strong and weak least core values is obtained bysolving the following LP

whereis supermodular

No computational analysis about the strong and weak least corevalues of supermodular cooperative game exists
9Idea of our approach (1)• Instead of solving the optimization problem,fixand consider its feasibility• Define a functionasis a supermodular game• Solve the following feasibility problem

10

Idea of our approach (2)• To check the feasibility…

• Define, where• The above program is feasible iff•
can be computed in polynomial time

(Frank and Tardos 1988; Naitoh and Fujishige 1992)11

Idea of our approach (3)is crossing submodular
12

Idea of our approach (4)To compute…

By the theorem, characterize the strong and weak least
core values of the supermodular cooperative game13

Induced subgraph game
1e11e2• The strong least core value

How well the hypergraphis clustered by the partition• A value division in the strong least core

• Use the ellipsoid method to find the value division

14

Conclusion• Goal:To find the strong least core and the weak least
core of the supermodular cooperative game• Contributions:• Provide theoretical characterizations of the strong andthe weak least core values• Derive explicit concise formulations of the induced
subgraph game and the airport game15