The Core

From Theory

Notes for CS 8803 - Game Theory and Computer Science. Spring 2008

Scribe: Liam Mac Dermed

Lecturer: Yair Tauman

The Core of V: (Shapley and Gillies 1953)

A set of payoff vectors

(x 1,..., x n)

s.t. $x_i\geq V(i)$

and $\sum_{i\in S} x_i \geq V(S) \ \ \ \forall \ S\subseteq N$

and $\sum_{i\in S} x_i = V(N)$

if $\sum x_i < V(S)$ for some S then S can object since S can do better by itself.

Note: The core is convex, since it is the solution of a set of linear constraints. For the same reason, it can contain zero, exactly one, or infinite vectors.

[edit]

Example 1

A simple majority game with N = {1,2,3}

I.E. V(S) =

1 if $|S| \geq 2$

0 otherwise

suppose that $x \in C(V)$ then from our definition of the core:

$x_1 + x_2 \geq V(1,2) = 1$

$x_1 + x_3 \geq V(1,3) = 1$

$x_2 + x_3 \geq V(2,3) = 1$

thus $2x_1 + 2x_2 + 2x_3 \geq 3$ so $x_1 + x_2 + x_3 \geq 1.5$ but we know that $V (1,2,3) = 1$ so $C(V) = \emptyset$ .

[edit]

Example 2

N = {1,2,3} where players 1 and 2 have a left glove while player 2 has a right glove.

V(S) =

1 if S = {1,3} or {2,3} or {1,2,3}

0 otherwise

Suppose (x_1, x_2, x_3) \in C(V)

$x_1 + x_2 \geq V(1,2) = 1$

$x_1 \geq 0$

$x_1 + x_2 + x_3 \geq V(1,2,3) = 1$

therefore $x 2 = 0$ .

The same logic can be applied to show $x 1 = 0$ so $x 3 = 1$ .

Both left gloves (player 1 and 2) are in competition with each other and for any positive allocation to the other player can offer player 3 a bigger piece of the pie. Thus player 3 will get everything. $C (V) = (0,0,1)$ .

[edit]