Dual Core in Cooperative Game Theory

654 Views Asked by At

I'm a bit confused over if the dual core of a game is the same as the core of the original game. Definition of dual game:

$$ v^*(S) = v(N) - v( N \setminus S ), \forall~ S \subseteq N.\, $$

I then propose a game with two players, with v({1}) = 1, v({2}) = 1, v({1,2}) = 3. In this case it seems likt the core of the dual game is empty while the core of the original game is not. What makes me confused is the following quote from wikipedia https://en.wikipedia.org/wiki/Cooperative_game:

A cooperative game and its dual are in some sense equivalent, and they share many properties. For example, the core of a game and its dual are equal. For more details on cooperative game duality, see for instance (Bilbao 2000).

The article seems well cited and I can't seem to find any other source clearly dealing with this matter. Would be thankful for some clarification!

1

There are 1 best solutions below

0
On

The core of a game is not self-dual, to see this, consider an average-convex game quantified by (lexi-order):

v=[0,0,0,0,4,9,8,2,4,10,13,13,39/2,14,149/6]

which gives another counter-example. The core of the game is given by the following extreme points:

 65/6            0           13/6          71/6     
   9             0           71/6            4      
   4             0           71/6            9      
   4             0             9           71/6     
 65/6            0            10             4      
 65/6            4            10             0      
   8           16/3          23/2            0      
   8             5           71/6            0      
   9             4           71/6            0      
 19/2          16/3           10             0      
 65/6            4             0            10      
 65/6          13/6            0           71/6     
   9           16/3            0           21/2     
   9             4             0           71/6     
 19/2          16/3            0            10      
   0           16/3          23/2            8      
   0             5           71/6            8      
   0           16/3            9           21/2     
   0             4           71/6            9      
   0             4             9           71/6

The dual game is specified by

dv=[65/6,16/3,71/6,71/6,89/6,125/6,137/6,101/6,95/6,125/6,149/6,149/6,149/6,149/6,149/6]

one can immediately see that the core of the dual game is empty, since $65/6+16/3+71/6+71/6 = 239/6 > 149/6$. However, the core of the game coincides with the anti-core of the dual game, this can be verified while comparing set of vertices of the anti-core of the dual game with the set from above, hence

65/6            0           13/6          71/6     
   9             0           71/6            4      
   4             0           71/6            9      
   4             0             9           71/6     
 65/6            0            10             4      
 65/6            4            10             0      
   8           16/3          23/2            0      
   8             5           71/6            0      
   9             4           71/6            0      
 19/2          16/3           10             0      
 65/6            4             0            10      
 65/6          13/6            0           71/6     
   9           16/3            0           21/2     
   9             4             0           71/6     
 19/2          16/3            0            10      
   0           16/3          23/2            8      
   0             5           71/6            8      
   0           16/3            9           21/2     
   0             4           71/6            9      
   0             4             9           71/6

For completeness, the anti-core of the dual game of your example is

 2     1
 1     2

which is equal to the core.

Have a look in the original article to see if the author means actually the anti-core of the dual game. Have also a look on the following paper that should clarify various anti-solution concepts. Article

Addendum

Even though, it is easily seen that the anti-core of a dual game $(N,v^{*})$ coincides with the core $C(v)$ of game $(N,v)$, there is some need to clarify the relationship. Starting with the anti-core $C^{\#}(v^{*})$ of a dual game $(N,v^{*})$, we get \begin{equation} \begin{split} C^{\#}(v^{*}) & := \{\vec{x} \in \mathcal{I}(v) \,\arrowvert\; x(S) \le v^{*}(S) \;\forall\; S \subseteq N \} \\ & \Longleftrightarrow \{\vec{x} \in \mathcal{I}(v) \,\arrowvert\; x(S) + x(N\backslash S) - x(N\backslash S) \le v(N)-v(N\backslash S) \;\forall\; S \subseteq N \} \\ & \Longleftrightarrow \{\vec{x} \in \mathcal{I}(v) \,\arrowvert\; x(N\backslash S) \ge v(N\backslash S) \;\forall\; S \subseteq N \} = C(v), \end{split} \end{equation} whereas $\mathcal{I}(v)$ is the pre-imputation set.