Stability in game theory

A principle reflecting directly or indirectly the idea of stability of a situation (or of a set of situations). One singles out the following basic concepts of stability.

1) $ \phi $- stability, cf. Coalitional game.

2) $ \psi $- stability. An optimality principle in a cooperative game, connected with the concept of stability of pairs, consisting of a partition of the set $ I $ of players into coalitions and allocations relative to the formation of new coalitions. A partition $ {\mathcal T} = ( T _ {1} \dots T _ {m} ) $ of the set $ I $ of players is called a coalition structure. Let $ \langle I, v \rangle $ be a cooperative game and $ \psi $ a function associating with every coalition structure $ {\mathcal T} $ a set of coalitions $ \psi ( {\mathcal T} ) $. A pair $ ( x, {\mathcal T} ) $, where $ x $ is an allocation, is called $ \psi $- stable if $ \sum _ {i \in S } x _ {i} \geq v ( S) $ for all $ S \in \psi ( {\mathcal T} ) $ and if $ x _ {i} > v ( \{ i \} ) $ when $ \{ i \} \notin {\mathcal T} $.

3) $ k $- stability. A special case of $ \psi $- stability, when for $ \psi ( {\mathcal T} ) $ a set of coalitions is chosen, each of which differs from any element of $ {\mathcal T} $ by not more than $ k $ players.

4) $ M $- stability. An optimality principle in the theory of cooperative games which formalizes the intuitive notion of stability of formation of coalitions and allocation of values $ v ( T) $ of a characteristic function $ v $ defined on the set of coalitions $ T $ relative to the possible threat of one coalition against the others. A pair $ ( x, {\mathcal T} ) $, where $ x = ( x _ {i} ) _ {i \in I } $ is a vector satisfying the condition $ \sum _ {i \in T _ {k} } x _ {i} = v ( T _ {k} ) $, $ k = 1 \dots m $, while $ {\mathcal T} = ( T _ {1} \dots T _ {m} ) $ is a coalition structure, is called a configuration. A configuration is said to be individually rational if $ x _ {i} \geq v ( \{ i \} ) $, $ i \in I $. A configuration $ ( x, {\mathcal T} ) $ is called coalitionally rational if the vector $ x $ satisfies $ \sum _ {i \in S } x _ {i} \geq v ( S) $ for any coalition $ S \subset T _ {k} $, $ k = 1 \dots m $. In case $ \sum _ {k = 1 } ^ {m} v ( T _ {k} ) = v ( I) $, in particular when $ {\mathcal T} = \{ I \} $, for every individually rational configuration $ ( x, {\mathcal T} ) $ the vector $ x $ is an allocation.

The set $ P ( K; {\mathcal T} ) = \{ {i \in I } : {i \in T _ {k} \textrm{ and } T _ {k} \cap K \neq \emptyset } \} $ is called the set of partners of a coalition $ K \subset I $ in a coalition structure $ {\mathcal T} $. Let $ ( x, {\mathcal T} ) $ be a coalitionally rational configuration and let $ K, L \subset I $ be disjoint coalitions. A coalitionally rational configuration $ ( y, U) $ satisfying the conditions

$$ P ( K; U) \cap L = \emptyset , $$

$$ y _ {i} > x _ {i} \ \textrm{ for } \textrm{ all } i \in K, $$

$$ y _ {i} \geq x _ {i} \ \textrm{ for } \textrm{ all } i \in P ( K; U), $$

is called a threat of a coalition $ K $ against $ L $. By a counter-threat of $ L $ against $ K $ one understands a coalitionally rational configuration $ ( z, V) $ satisfying the conditions

$$ K \subset \setminus P ( L; V), $$

$$ z _ {i} \geq x _ {i} \ \textrm{ for } \textrm{ all } i \in P ( L; V), $$

$$ z _ {i} \geq y _ {i} \ \textrm{ for } \textrm{ all } i \in P ( L; V) \cap P ( K; U). $$

A coalitionally rational configuration $ ( x, {\mathcal T} ) $ is called $ M $- stable if for any pair of disjoint coalitions $ K, L $ and for every threat of $ K $ against $ L $ there is a counter-threat of $ L $ against $ K $. The set of all $ M $- stable configurations for a coalition structure $ {\mathcal T} $ is called the $ M $- stable set and is denoted by $ M $ or $ M ( {\mathcal T} ) $. In the case $ \sum _ {k} v ( T _ {k} ) = v ( I) $, the set $ M $ contains the core (cf. Core in the theory of games) of the cooperative game $ \langle I, v \rangle $. The set $ M $ often turns out to be empty, and therefore one considers further the set $ M _ {1} ^ {(} i) $ which is defined analogously to $ M $, with the following changes: one considers not only coalitionally rational configurations, but all individually rational configurations admitting only threats and counter-threats among one-element coalitions, i.e. between individual players. It can be proved that the set $ M _ {1} ^ {(} i) $ is non-empty for any coalition structure. The set $ M _ {1} ^ {(} i) $ for $ {\mathcal T} = \{ I \} $ contains the $ k $- kernel and coincides with it and the core for a convex game $ \langle I, v \rangle $.

The concepts of $ M $- stability and $ M _ {1} ^ {(} i) $- stability have a natural generalization to cooperative games without side payments. It is known that in this case the set $ M _ {1} ^ {(} i) $ may be empty; there are certain conditions for $ M _ {1} ^ {(} i) $ to be non-empty.

References

[1]	R.J. Aumann, M. Maschler, "The bargaining set for cooperative games" , Advances in game theory , Princeton Univ. Press pp. 443–476
[2]	N.N. Vorob'ev, "The present state of the theory of games" Russian Math. Surveys , 25 : 2 (1970) pp. 77–150 Uspekhi Mat. Nauk , 25 : 2 (1970) pp. 81–140
[3]	R.D. Luce, , Mathematical Models of Human Behaviour , Stanford (1955) pp. 32–44
[4]	R.D. Luce, H. Raiffa, "Games and decisions. Introduction and critical survey" , Wiley (1957)
[5]	B. Peleg, "Existence theorem for the bargaining of " Bull. Amer. Math. Soc. , 69 (1963) pp. 109–110
[6]	B. Peleg, "Quota games with a continuum of players" Israel J. Math. , 1 (1963) pp. 48–53
[7]	G. Owen, "The theory of games" , Acad. Press (1982)