Namespaces
Variants
Actions

Difference between revisions of "Stability in game theory"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
 +
<!--
 +
s0869702.png
 +
$#A+1 = 85 n = 1
 +
$#C+1 = 85 : ~/encyclopedia/old_files/data/S086/S.0806970 Stability in game theory
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
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.
 
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s0869702.png" />-stability, cf. [[Coalitional game|Coalitional game]].
+
1) $  \phi $-
 +
stability, cf. [[Coalitional game|Coalitional game]].
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s0869704.png" />-stability. An optimality principle in a [[Cooperative game|cooperative game]], connected with the concept of stability of pairs, consisting of a partition of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s0869705.png" /> of players into coalitions and allocations relative to the formation of new coalitions. A partition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s0869706.png" /> of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s0869707.png" /> of players is called a coalition structure. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s0869708.png" /> be a cooperative game and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s0869709.png" /> a function associating with every coalition structure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697010.png" /> a set of coalitions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697011.png" />. A pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697012.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697013.png" /> is an allocation, is called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697014.png" />-stable if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697015.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697016.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697017.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697018.png" />.
+
2) $  \psi $-
 +
stability. An optimality principle in a [[Cooperative game|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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697020.png" />-stability. A special case of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697021.png" />-stability, when for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697022.png" /> a set of coalitions is chosen, each of which differs from any element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697023.png" /> by not more than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697024.png" /> players.
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697026.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697027.png" /> of a characteristic function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697028.png" /> defined on the set of coalitions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697029.png" /> relative to the possible threat of one coalition against the others. A pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697030.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697031.png" /> is a vector satisfying the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697033.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697034.png" /> is a coalition structure, is called a configuration. A configuration is said to be individually rational if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697035.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697036.png" />. A configuration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697037.png" /> is called coalitionally rational if the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697038.png" /> satisfies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697039.png" /> for any coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697040.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697041.png" />. In case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697042.png" />, in particular when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697043.png" />, for every individually rational configuration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697044.png" /> the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697045.png" /> is an allocation.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697046.png" /> is called the set of partners of a coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697047.png" /> in a coalition structure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697048.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697049.png" /> be a coalitionally rational configuration and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697050.png" /> be disjoint coalitions. A coalitionally rational configuration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697051.png" /> satisfying the conditions
+
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
  
<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/s/s086/s086970/s08697052.png" /></td> </tr></table>
+
$$
 +
P ( K; U) \cap L  = \emptyset ,
 +
$$
  
<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/s/s086/s086970/s08697053.png" /></td> </tr></table>
+
$$
 +
y _ {i}  > x _ {i} \  \textrm{ for }  \textrm{ all }  i \in K,
 +
$$
  
<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/s/s086/s086970/s08697054.png" /></td> </tr></table>
+
$$
 +
y _ {i}  \geq  x _ {i} \  \textrm{ for }  \textrm{ all }  i \in P ( K; U),
 +
$$
  
is called a threat of a coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697055.png" /> against <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697056.png" />. By a counter-threat of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697057.png" /> against <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697058.png" /> one understands a coalitionally rational configuration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697059.png" /> satisfying the conditions
+
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
  
<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/s/s086/s086970/s08697060.png" /></td> </tr></table>
+
$$
 +
K  \subset  \setminus  P ( L; V),
 +
$$
  
<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/s/s086/s086970/s08697061.png" /></td> </tr></table>
+
$$
 +
z _ {i}  \geq  x _ {i} \  \textrm{ for }  \textrm{ all }  i \in P ( L; V),
 +
$$
  
<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/s/s086/s086970/s08697062.png" /></td> </tr></table>
+
$$
 +
z _ {i}  \geq  y _ {i} \  \textrm{ for }  \textrm{ all }  i \in P ( L; V) \cap P ( K; U).
 +
$$
  
A coalitionally rational configuration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697063.png" /> is called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697065.png" />-stable if for any pair of disjoint coalitions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697066.png" /> and for every threat of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697067.png" /> against <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697068.png" /> there is a counter-threat of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697069.png" /> against <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697070.png" />. The set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697071.png" />-stable configurations for a coalition structure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697072.png" /> is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697074.png" />-stable set and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697075.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697076.png" />. In the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697077.png" />, the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697078.png" /> contains the core (cf. [[Core in the theory of games|Core in the theory of games]]) of the cooperative game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697079.png" />. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697080.png" /> often turns out to be empty, and therefore one considers further the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697081.png" /> which is defined analogously to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697082.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697083.png" /> is non-empty for any coalition structure. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697084.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697085.png" /> contains the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697086.png" />-kernel and coincides with it and the core for a [[Convex game|convex game]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697087.png" />.
+
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|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|convex game]] $  \langle  I, v \rangle $.
  
The concepts of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697088.png" />-stability and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697089.png" />-stability have a natural generalization to cooperative games without side payments. It is known that in this case the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697090.png" /> may be empty; there are certain conditions for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697091.png" /> to be non-empty.
+
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====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R.J. Aumann,  M. Maschler,  "The bargaining set for cooperative games" , ''Advances in game theory'' , Princeton Univ. Press  pp. 443–476</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  R.D. Luce,  , ''Mathematical Models of Human Behaviour'' , Stanford  (1955)  pp. 32–44</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  R.D. Luce,  H. Raiffa,  "Games and decisions. Introduction and critical survey" , Wiley  (1957)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  B. Peleg,  "Existence theorem for the bargaining of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697092.png" />"  ''Bull. Amer. Math. Soc.'' , '''69'''  (1963)  pp. 109–110</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  B. Peleg,  "Quota games with a continuum of players"  ''Israel J. Math.'' , '''1'''  (1963)  pp. 48–53</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  G. Owen,  "The theory of games" , Acad. Press  (1982)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R.J. Aumann,  M. Maschler,  "The bargaining set for cooperative games" , ''Advances in game theory'' , Princeton Univ. Press  pp. 443–476</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  R.D. Luce,  , ''Mathematical Models of Human Behaviour'' , Stanford  (1955)  pp. 32–44</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  R.D. Luce,  H. Raiffa,  "Games and decisions. Introduction and critical survey" , Wiley  (1957)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  B. Peleg,  "Existence theorem for the bargaining of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086970/s08697092.png" />"  ''Bull. Amer. Math. Soc.'' , '''69'''  (1963)  pp. 109–110</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  B. Peleg,  "Quota games with a continuum of players"  ''Israel J. Math.'' , '''1'''  (1963)  pp. 48–53</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  G. Owen,  "The theory of games" , Acad. Press  (1982)</TD></TR></table>

Revision as of 08:22, 6 June 2020


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)
How to Cite This Entry:
Stability in game theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Stability_in_game_theory&oldid=14883
This article was adapted from an original article by A.Ya. Kiruta (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article