Stable cores in information graph games

1

Marina Núñez (Universitat de Barcelona)

Juan Vidal-Puga (Universidade de Vigo)

Information graph games

• A group of agents require to know some information.

2

Information graph games

• A group of agents require to know some information.
• Some of the agents may already be informed.

3

Information graph games

• A group of agents require to know some information.
• Some of the agents may already be informed.
• Information can be freely shared by two agents if there is a connection between them (undirected graph).

4

Information graph games

• A group of agents require to know some information.
• Some of the agents may already be informed.
• Information can be freely shared by two agents if there is a connection between them (undirected graph).
• Uninformed players may get the information by an external source at a fixed cost (normalized to 1).

5

Information graph games

• A group of agents require to know some information.
• Some of the agents may already be informed.
• Information can be freely shared by two agents if there is a connection between them (undirected graph).
• Uninformed players may get the information by an external source at a fixed cost (normalized to 1).

6

Core

• Since information can be shared, there are benefits of cooperation
• How should the benefits of cooperation be shared?

7

Core

• Since information can be shared, there are benefits of cooperation.
• How should the benefits of cooperation be shared?

8

0.25

0.25

0.25

0.25

Core

• Since information can be shared, there are benefits of cooperation.
• How should the benefits of cooperation be shared?

9

0.25

0.25

0.25

0.25

α

α

α

-3α

Stable? core

• Since information can be shared, there are benefits of cooperation.
• How should the benefits of cooperation be shared?

10

0.25

0.25

0.25

0.25

α

α

α

-3α

?

?

?

?

Stable? core

• Since information can be shared, there are benefits of cooperation.
• How should the benefits of cooperation be shared?

11

0.25

0.25

0.25

0.25

α

α

α

-3α

0

0

0

0

Stable core? (answer: NO)

• Since information can be shared, there are benefits of cooperation
• How should the benefits of cooperation be shared?

12

0.25

0.25

0.25

0.25

α

α

α

-3α

0

α

0

-α

The model

• Information graph situation: (N∪{0}, G) where
• N = {1, 2,..., n} set of agents
• 0 information source
• N∪{0} set of nodes
• G undirected graph
• Information graph (cost) game (N,C) where
• C(S) = number of connected components of S∪{0} in G.
• An information graph situation is saturated if 0i, 0j connected ⇒ ij connected.�

13

13

1

2

0

3

1

2

0

3

The model

Proposition: For each information graph situation, there exists a unique saturated information graph situation that defines the same information cost game.

14

Saturated information graph situations

Information games

Stability

• An imputation is a cost allocation x∊ℝ^N satisfying x(N) = ∑_i∊Nx_i = C(N) and x_i ≤ C({i}) for all i ∊ N.
• Given two imputations x, y, we say that x dominates y via T⊂N if x_i < y_i for all i ∊ N and x(T) ≤ C(T).
• The core is the set of undominated imputations:

Core(N,C) = {x∊ℝ^N : x(N)= C(N), x(T) ≤ C(T) for all T⊂N}

15

Stable set

A set S of imputations is...

• Internally stable if any two imputations in S do not dominate one another.�(The core is internally stable by definition).
• Externally stable if any imputation outside S is dominated by some imputation in S. �(Any externally stable set should contain the core).
• A stable set if S is internally and externally stable.�

​

16

Example

• Core(N,C) = {(0,0,0)} is not externally stable because, f.ex., (-α,0,α) with α∊(0,1] is not dominated by (0,0,0).
• {(-α,0,α) : α∊[0,1]} is a stable set.
• {(0,-α,α) : α∊[0,1]} is a stable set.

17

1

2

0

3

Example

• Core(N,C) = {(0,0,0)} is externally stable (it coincides with the set of imputations).

18

1

2

0

3

Cycle-completeness

An information graph situation is cycle-complete if for each cycle and pair nodes i, j in this cycle, it holds that i and j are connected.

19

1

2

0

3

1

2

0

3

Cycle-completeness

An information graph situation is cycle-complete if for each cycle and pair nodes i, j in this cycle, it holds that i and j are connected.

20

1

2

0

3

4

5

6

1

2

0

3

4

5

6

Main result

Theorem: The following statements are equivalent in information graph games:

1. The core is stable.
2. The associated saturated graph is cycle-complete.
3. The cost game is concave.

21

Ring topology of informed agents

Assume:

• The graph of (N,C) is {01, 12, 23,..., n0, 1n}.
• The graph of (N,C’) is {01, 12, 23,..., n0, 1n}.

​

Theorem: The Core of (N,C’) is a stable set of (N,C).

​

22

1

n

0

2

3

...

...

...

Ring topology of informed agents

Assume:

• The graph of (N,C) is {01, 12, 23,..., n1}.
• The graph of (N,C’) is {01, 12, 23,..., n1}.

​

Theorem: The Core of (N,C’) is an externally stable set of (N,C).

​

23

1

n

0

2

3

...

...

...

Summary

• We characterize the stability of the core of information graph games.
• We provide a stable set for ring structures that contain the source.
• It remains as an open question whether
• stable sets always exists for information graph games and games and,
• if this is the case, whether there is always a stable set consisting of the core of some related information graph game after removing some nodes or edges in incomplete cycles.

24