Namespaces
Variants
Actions

Core in the theory of games

From Encyclopedia of Mathematics
(Redirected from Kernel of a game)
Jump to: navigation, search


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:
Kernel of a game. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Kernel_of_a_game&oldid=43344