Confusion in Core-Veto Players Theorem

132 Views Asked by At

Consider the following simple coalitional game (the ice-cream game for those who are familiar with it):

$$N = \{1,2,3\}$$

$$v(\phi)=0, v(\{1\})=0, v(\{2\})=0, v(\{3\})=0, v(\{1,2\})=750, v(\{2,3\})=750, v(\{2,3\})=500, v(\{1,2,3\})=1000$$

The core is nonempty since $(500, 250, 250)$ is in the core. There is no veto player since each coalition of exactly $2$ players has a positive payoff.

However, this seems to be a counterexample of the following theorem (taken from Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, section 12.2.2):

Theorem 12.2.13: In a simple game the core is empty iff there is no veto player. If there are veto players, the core consists of all payoff vectors in which the nonveto players get zero.

Am I missing something here?

1

There are 1 best solutions below

0
On

Since I was asked to provide an answer, I will follow the request, though I have no clue where the exact problem is located. I guess, it is related to the concept of a simple game, of a veto-player, and veto-rich player. Please let me know if I have not got the point, then I will prepare a reedit.

A winning coalition gets a worth of one, whereas a losing coalition gets zero, or more formally a simple game in characteristic function form $(N,v)$ is specified by $$ v(S) \in \{0,1\} \qquad\text{for all}\quad S \subset N \quad\text{and}\quad v(N)=1.$$

Since, the above example game from the post provides characteristic function values different from one and zero, the game is not simple.

The set of veto-players is defined by $J^{v}:=\{k \in N\,\arrowvert\, v(N\backslash \{k\})=0\}$. That is to say, a veto-player belongs to all winning coalitions. We know that a simple game without a veto player has an empty core.

A player $i \in N$ of a TU game $\langle N, v \rangle$ is a veto-rich player, whenever for all coalitions $\emptyset \neq S \subseteq N\backslash\{i\}$ it holds $v(S)=0$. That is to say, the veto-rich player belongs to all coalitions with a positive value.

Consider the following four-person game that is specified as follows:

$$v(\{4\})=0, v(\{1,4\})=4, v(\{2,4\})= 3/2, v(\{3,4\})=10, v(\{1,2,4\})=2, v(\{1,3,4\})=9, v(\{2,3,4\})=11,v(N)=18, $$

and the remaining coalitions have a value of zero. Then the veto-rich player is player $4$, and the game has a sole kernel point given by $(3.5,4.5,4,6)$, which is the nucleolus.

The concept of a veto-rich player is useful, since then we know that the kernel is a singleton, and must coincide with the nucleolus. Related to the core, this concept is irrelevant. Hence, from the existence of a veto-rich player, we cannot deduce that the core is non-empty.

However, for three-person game it is known that the kernel and nucleolus coincides. Hence, the veto-rich player concept is irrelevant for three-person games. Nevertheless, we can check that the game has no veto-rich players.

I hope that clarifies the facts.