Namespaces
Variants
Actions

Difference between revisions of "Core in the theory of games"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (links)
m (tex encoded by computer)
Line 1: Line 1:
The set of all non-dominated outcomes, that is, the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c0264901.png" /> of outcomes such that a [[Domination|domination]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c0264902.png" /> cannot hold for any outcomes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c0264903.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c0264904.png" /> and coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c0264905.png" />. One defines in this respect:
+
<!--
 +
c0264901.png
 +
$#A+1 = 27 n = 0
 +
$#C+1 = 27 : ~/encyclopedia/old_files/data/C026/C.0206490 Core in the theory of games
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
1) The core. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c0264906.png" /> of [[imputation]]s that are not dominated by any other imputation; the core coincides with the set of imputations satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c0264907.png" /> for any coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c0264908.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c0264909.png" /> and a von Neumann–Morgenstern solution (see [[Solution in game theory]]) exists, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649010.png" /> is contained in any von Neumann–Morgenstern solution.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
2) The kernel. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649011.png" /> of individually rational configurations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649012.png" /> (see [[Stability in game theory]]) such that the following inequality holds for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649013.png" />:
+
The set of all non-dominated outcomes, that is, the set  $  C $
 +
of outcomes such that a [[Domination|domination]] $  s \succ _ {K} c $
 +
cannot hold for any outcomes  $  s \in S $,
 +
c \in C $
 +
and coalition  $  K \in \mathfrak R _ {i} $.  
 +
One defines in this respect:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649014.png" /></td> </tr></table>
+
1) The core. The set  $  c ( v) $
 +
of [[imputation]]s that are not dominated by any other imputation; the core coincides with the set of imputations satisfying  $  \sum _ {i \in S }  x _ {i} \geq  v ( S) $
 +
for any coalition  $  S $.  
 +
If  $  c ( v) \neq \emptyset $
 +
and a von Neumann–Morgenstern solution (see [[Solution in game theory]]) exists, then  $  c ( v) $
 +
is contained in any von Neumann–Morgenstern solution.
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649016.png" /> is the set of coalitions containing the player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649017.png" /> and not containing the player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649018.png" />. The kernel <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649019.png" /> is contained in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649020.png" />-bargaining set.
+
2) The kernel. The set $  k ( v) $
 +
of individually rational configurations  $  ( x, \mathfrak B ) $(
 +
see [[Stability in game theory]]) such that the following inequality holds for any  $  i, j \in B \in \mathfrak B $:
  
3) The nucleolus. The minimal imputation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649021.png" /> relative to the quasi-order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649022.png" /> defined on the set of imputations by: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649023.png" /> if and only if the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649024.png" />, where
+
$$
 +
\left ( \max _ {S \in \tau _ {ij} }  e ( S, x) -
 +
\max _ {S \in \tau _ {ji} }  e ( S, x) \right ) x _ {j}  \leq  0,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649025.png" /></td> </tr></table>
+
where  $  e ( S, x) = v ( S) - \sum _ {k \in S }  x _ {k} $
 +
and  $  \tau _ {ij} $
 +
is the set of coalitions containing the player  $  i $
 +
and not containing the player  $  j $.  
 +
The kernel  $  k ( v) $
 +
is contained in an  $  M _ {1}  ^ {i} $-
 +
bargaining set.
  
lexicographically precedes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649026.png" />. The nucleolus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026490/c02649027.png" /> exists and is unique for any game with a non-empty set of imputations. In a cooperative game the nucleolus is contained in the kernel.
+
3) The nucleolus. The minimal imputation  $  n ( v) $
 +
relative to the quasi-order  $  \prec _  \nu  $
 +
defined on the set of imputations by:  $  x \prec _  \nu  y $
 +
if and only if the vector  $  \theta ( x, v) = ( \theta _ {1} ( x, v) \dots \theta _ {n} ( x, v)) $,
 +
where
 +
 
 +
$$
 +
\theta _ {i} ( x, v)  = \max _ {\begin{array}{c}
 +
{} \\
 +
| \mathfrak U | = i
 +
\end{array}
 +
} \
 +
\min _ {\begin{array}{c}
 +
{} \\
 +
S \in \mathfrak U
 +
\end{array}
 +
}  e
 +
( S, x) ,
 +
$$
 +
 
 +
lexicographically precedes  $  \theta ( y, v) $.  
 +
The nucleolus $  n ( v) $
 +
exists and is unique for any game with a non-empty set of imputations. In a cooperative game the nucleolus is contained in the kernel.
  
 
====References====
 
====References====
Line 19: Line 70:
 
<TR><TD valign="top">[1]</TD> <TD valign="top">  N.N. Vorob'ev,  "The present state of the theory of games"  ''Russian Math. Surveys'' , '''25''' :  2  (1970)  pp. 77–136  ''Uspekhi Mat. Nauk'' , '''25''' :  2  (1970)  pp. 103–107</TD></TR>
 
<TR><TD valign="top">[1]</TD> <TD valign="top">  N.N. Vorob'ev,  "The present state of the theory of games"  ''Russian Math. Surveys'' , '''25''' :  2  (1970)  pp. 77–136  ''Uspekhi Mat. Nauk'' , '''25''' :  2  (1970)  pp. 103–107</TD></TR>
 
</table>
 
</table>
 
 
  
 
====Comments====
 
====Comments====

Revision as of 17:28, 5 June 2020


The set of all non-dominated outcomes, that is, the set $ C $ of outcomes such that a domination $ s \succ _ {K} c $ cannot hold for any outcomes $ s \in S $, $ c \in C $ and coalition $ K \in \mathfrak R _ {i} $. One defines in this respect:

1) The core. The set $ c ( v) $ of imputations that are not dominated by any other imputation; the core coincides with the set of imputations satisfying $ \sum _ {i \in S } x _ {i} \geq v ( S) $ for any coalition $ S $. If $ c ( v) \neq \emptyset $ and a von Neumann–Morgenstern solution (see Solution in game theory) exists, then $ c ( v) $ is contained in any von Neumann–Morgenstern solution.

2) The kernel. The set $ k ( v) $ of individually rational configurations $ ( x, \mathfrak B ) $( see Stability in game theory) such that the following inequality holds for any $ i, j \in B \in \mathfrak B $:

$$ \left ( \max _ {S \in \tau _ {ij} } e ( S, x) - \max _ {S \in \tau _ {ji} } e ( S, x) \right ) x _ {j} \leq 0, $$

where $ e ( S, x) = v ( S) - \sum _ {k \in S } x _ {k} $ and $ \tau _ {ij} $ is the set of coalitions containing the player $ i $ and not containing the player $ j $. The kernel $ k ( v) $ is contained in an $ M _ {1} ^ {i} $- bargaining set.

3) The nucleolus. The minimal imputation $ n ( v) $ relative to the quasi-order $ \prec _ \nu $ defined on the set of imputations by: $ x \prec _ \nu y $ if and only if the vector $ \theta ( x, v) = ( \theta _ {1} ( x, v) \dots \theta _ {n} ( x, v)) $, where

$$ \theta _ {i} ( x, v) = \max _ {\begin{array}{c} {} \\ | \mathfrak U | = i \end{array} } \ \min _ {\begin{array}{c} {} \\ S \in \mathfrak U \end{array} } e ( S, x) , $$

lexicographically precedes $ \theta ( y, v) $. The nucleolus $ n ( v) $ exists and is unique for any game with a non-empty set of imputations. In a cooperative game the nucleolus is contained in the kernel.

References

[1] N.N. Vorob'ev, "The present state of the theory of games" Russian Math. Surveys , 25 : 2 (1970) pp. 77–136 Uspekhi Mat. Nauk , 25 : 2 (1970) pp. 103–107

Comments

The Russian word ( "yadro" ) is the same for all three notions defined above, but these notions may be distinguished by prefixing with the corresponding English letter ( "c-yadro" for core, "k-yadro" for kernel and "n-yadro" for nucleolus). These three notions do not share many properties.

See [a1], [a7] for core, [a2] for kernel and [a3] for nucleolus. [a4], [a5] are general references. [a6] deals also with mathematical economics and the role of the concept of the core of a game in that setting.

References

[a1] O.N. Bondareva, "Certain applications of the methods of linear programming to the theory of cooperative games" Probl. Kibernet , 10 (1963) pp. 119–139 (In Russian)
[a2] M. Maschler, M. Davis, "The kernel of a cooperative game" Naval Res. Logist. Quart. , 12 (1965) pp. 223–259
[a3] D. Schmeidler, "The nucleolus of a characteristic function game" SIAM J. Appl. Math. , 17 (1969) pp. 1163–1170
[a4] G. Owen, "Game theory" , Acad. Press (1982)
[a5] J. Szép, F. Forgó, "Introduction to the theory of games" , Reidel (1985) pp. 171; 199
[a6] J. Rosenmüller, "Cooperative games and markets" , North-Holland (1981)
[a7] L.S. Shapley, "On balanced sets and cores" Naval Res. Logist. Quart. , 14 (1967) pp. 453–460
How to Cite This Entry:
Core in the theory of games. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Core_in_the_theory_of_games&oldid=46518
This article was adapted from an original article by A.I. Sobolev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article