Clique games: a family of games with coincidence between the nucleolus and the Shapley value

Christian Trudeau (U. Windsor)

Juan Vidal-Puga (U. Vigo)

​

Lisbon, November 2017

Shapley value and nucleolus

• The Shapley value is an average of the marginal contributions of a player.
• The prenucleolus is the value that minimizes the dissatisfaction of the worst-off coalitions.
• The nucleolus differs from the prenucleolus by also requiring that the value be individually rational.

2

Shapley value and nucleolus

• Coincidence between these two values is uncommon and, in general, difficult to check without computing both values (Yokote, Funaki and Kamijo, 2017).
• For general TU games we have coincidence if
• n = 2 or
• all players are symmetric within the normalized game .

3

Our contribution

• We introduce a new family of cooperative games for which there is coincidence between the nucleolus and the Shapley value: Clique games.
• There are multiple examples for clique games, chief among them minimum cost spanning tree problems. This allows us to obtain new correspondence results between the nucleolus and the Shapley value, as well as other cost sharing methods for the minimum cost spanning tree problem.

4

Minimum cost spanning tree games

• A group of agents, located at different geographical points, want some service which can only be provided by a common supplier, called the source.
• Agents can be served through connections which entail some cost.
• The agents are not concerned whether they are connected directly or indirectly to the source.

5

Examples

• Connection to a dam
• Connection to a power station
• Connection to a sewage plant
• Internet
• Cable TV
• ...

6

Elementary minimum cost spanning tree games

• A group of agents, located at different geographical points, want some service which can only be provided by a common supplier, called the source.
• Agents can be served through connections which entail some either a fixed cost (normalized to 1) or zero cost (they are already connected).
• The agents are not concerned whether they are connected directly or indirectly to the source.
• Utility of being connected is 1.

7

Private vs public case

Private case

Agents may refuse others to use their respective nodes.

Public case

Agents can use other nodes if they are closer to the source.

8

Example (private case)

9

A

B

C

v(A) = v(C) = 1

v(B) = 0

v(A,B) = v(A,C) = v(B,C) = 2

v(A,B,C) = 3

Example (private case)

10

A

B

C

v(A) = v(C) = 1

v(B) = 0

v(A,B) = v(A,C) = v(B,C) = 2

v(A,B,C) = 3

Example (private case)

11

A

B

C

v(A) = v(C) = 1

v(B) = 0

v(A,B) = v(A,C) = v(B,C) = 2

v(A,B,C) = 3

Example (private case)

12

A

B

C

v(A) = v(C) = 1

v(B) = 0

v(A,B) = v(A,C) = v(B,C) = 2

v(A,B,C) = 3

Example (private case)

13

A

B

C

v(A) = v(C) = 1

v(B) = 0

v(A,B) = v(A,C) = v(B,C) = 2

v(A,B,C) = 3

Example (private case)

14

A

B

C

v(A) = v(C) = 1

v(B) = 0

v(A,B) = v(A,C) = v(B,C) = 2

v(A,B,C) = 3

Shapley value:

(7/6, 4/6, 7/6)

Example (private case)

15

A

B

C

v(A) = v(C) = 1

v(B) = 0

v(A,B) = v(A,C) = v(B,C) = 2

v(A,B,C) = 3

Shapley value:

(7/6, 4/6, 7/6)

NOT IN THE CORE!

11/6

11/6

Example (private case)

16

A

B

C

v(A) = v(C) = 1

v(B) = 0

v(A,B) = v(A,C) = v(B,C) = 2

v(A,B,C) = 3

Nucleolus:

(1, 1, 1)

Example (public case)

17

A

B

C

v(A) = v(C) = 1

v(B) = 1

v(A,B) = v(A,C) = v(B,C) = 2

v(A,B,C) = 3

Example (public case)

18

A

B

C

v(A) = v(C) = 1

v(B) = 1

v(A,B) = v(A,C) = v(B,C) = 2

v(A,B,C) = 3

Example (public case)

19

A

B

C

v(A) = v(C) = 1

v(B) = 1

v(A,B) = v(A,C) = v(B,C) = 2

v(A,B,C) = 3

Shapley value = nucleolus

(1, 1, 1)

The Shapley value of the public case

The Shapley value of the public case (the folk rule) has many good properties even for the private case:

• It always belong to the core.
• An increase in the cost of a link never benefit anyone.
• Arrival of new players will not harm anyone in the former society.
• ...

​

20

From now on...

21

=

The Shapley value of the public case

• In the public case, the cost of a link vanishes if there is a zero-cost path connecting both nodes.

22

Example

23

Example

24

“Obvious” result

Theorem: If the cost of a link is zero whenever there is a zero-cost path connecting both nodes, then the Shapley value and the nucleolus coincide.

​

Proof (sketch): All players are essentially symmetric. Since the Shapley value and the nucleolus are both symmetric, they should coincide.

​

​

25

The cycle-free Shapley value

• In the public case, the cost of a link vanishes if there is a zero-cost path connecting both nodes.
• Assume that the cost of link vanishes if there are two zero-cost paths connecting both nodes.
• The Shapley value of the resulting game (Trudeau, 2012) also has nice properties. For example, it belongs to the core.

​

26

Example

27

Example

28

Example

29

Cliques

Not so “obvious” result

Theorem: If the cost of a link is zero when there are two zero-cost paths connecting both nodes (clique games), then the Shapley value and the nucleolus coincide.

​

Theorem: In elementary cost spanning tree games, the cycle-free Shapley value and the nucleolus coincide.

30

Clique games

A cooperative game (N, v) is a clique game if there exists a cover 𝓠 = {Q₁,...,Q_k} of N such that

• |Q_l ∩ Q_m| ∊ {0,1} for all l,m.
• There is at most one path between any two elements of 𝓠.
• There exist v_i ∊ ℝ for each i ∊ N and v_Q ∊ ℝ for each Q ∊ 𝓠 such that �v(S) = ∑_i∊Sv_i + ∑_{Q∊𝓠:Q∩S≠∅}(|Q∩S| − 1)v_Q

31

Example

32

𝓠 = {Q₁,Q₂,Q₃,Q₄,Q₅,Q₆,Q₇,Q₈}

​

Cost are not 0, but they are:

• small with respect to the cost to the source
• different inside each clique.

Main result

Theorem: In clique games, the Shapley value and the nucleolus coincide.

​

Sh_i(N,v) = Nu_i(N,v) = v_i + ∑_{Q∊𝓠:Q∩S≠∅}(|Q| − 1)v_Q / |Q|

​

for all i ∊ N.

​

​

​

33

Related literature

Kar, Mitra and Mutuswami (2009) prove that coincidence holds in PS games, where there exists c ∊ ℝ^N such that

v(S ∪ {i}) − v(S) + v(N \ S) − v(N\(S ∪ {i})) = c_i

for all i ∊ N and S ⊆ N \ {i}.

​

Clique games and PS games are logically independent.

​

​

34

Summary

35

Sh = Nu

Elementary mcst

mcst

PS games

Clique games