Namespaces
Variants
Actions

Difference between revisions of "Non-cooperative game"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
n0669801.png
 +
$#A+1 = 32 n = 1
 +
$#C+1 = 32 : ~/encyclopedia/old_files/data/N066/N.0606980 Non\AAhcooperative game
 +
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 system
 
A system
  
<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/n/n066/n066980/n0669801.png" /></td> </tr></table>
+
$$
 +
\Gamma  = < J, \{ S _ {i} \} _ {i \in J }  ,\
 +
\{ H _ {i} \} _ {i \in J }  > ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n0669802.png" /> is the set of players, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n0669803.png" /> is the set of strategies (cf. [[Strategy (in game theory)|Strategy (in game theory)]]) of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n0669804.png" />-th player and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n0669805.png" /> is the gain function of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n0669806.png" />-th player, defined on the Cartesian product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n0669807.png" />. A non-cooperative game is played as follows: players, who are acting individually (do not form a coalition, do not cooperate), select their strategies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n0669808.png" />, as a result of which the situation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n0669809.png" /> appears, in which the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698010.png" />-th player obtains the gain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698011.png" />. The main optimality principle in a non-cooperative game is the principle of realizability of the objective [[#References|[1]]], which generates the Nash equilibrium solutions. A solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698012.png" /> is called an equilibrium solution if for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698014.png" />, the inequality
+
where $  J $
 +
is the set of players, $  S _ {i} $
 +
is the set of strategies (cf. [[Strategy (in game theory)|Strategy (in game theory)]]) of the $  i $-
 +
th player and $  H _ {i} $
 +
is the gain function of the $  i $-
 +
th player, defined on the Cartesian product $  S = \prod _ {i \in J }  S _ {i} $.  
 +
A non-cooperative game is played as follows: players, who are acting individually (do not form a coalition, do not cooperate), select their strategies $  s _ {i} \in S _ {i} $,  
 +
as a result of which the situation $  s = \prod _ {i \in J }  s _ {i} $
 +
appears, in which the $  i $-
 +
th player obtains the gain $  H _ {i} ( s) $.  
 +
The main optimality principle in a non-cooperative game is the principle of realizability of the objective [[#References|[1]]], which generates the Nash equilibrium solutions. A solution $  s  ^ {*} $
 +
is called an equilibrium solution if for all $  i \in J $,  
 +
$  s _ {i} \in S _ {i} $,  
 +
the inequality
  
<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/n/n066/n066980/n06698015.png" /></td> </tr></table>
+
$$
 +
H _ {i} ( s  ^ {*} )  \geq  H _ {i} ( s  ^ {*}  \|  s _ {i} ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698016.png" />, is valid. Thus, none of the players is interested in unilaterally disturbing the equilibrium solution previously agreed upon between them. It has been proved (Nash's theorem) that a finite non-cooperative game (the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698017.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698018.png" /> are finite) possesses an equilibrium solution for mixed strategies. This theorem has been generalized to include infinite non-cooperative games with a finite number of players [[#References|[3]]] and non-cooperative games with an infinite number of players (cf. [[Non-atomic game|Non-atomic game]]).
+
where $  s  ^ {*}  \|  s _ {i} = \prod _ {j \in J \setminus  i }  s _ {j}  ^ {*} \times s _ {i} $,  
 +
is valid. Thus, none of the players is interested in unilaterally disturbing the equilibrium solution previously agreed upon between them. It has been proved (Nash's theorem) that a finite non-cooperative game (the sets $  J $
 +
and $  S _ {i} $
 +
are finite) possesses an equilibrium solution for mixed strategies. This theorem has been generalized to include infinite non-cooperative games with a finite number of players [[#References|[3]]] and non-cooperative games with an infinite number of players (cf. [[Non-atomic game|Non-atomic game]]).
  
Two equilibrium solutions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698020.png" /> are called interchangeable if any solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698021.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698022.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698024.png" />, is also an equilibrium solution. They are called equivalent if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698025.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698026.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698027.png" /> be the set of all equilibrium solutions, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698028.png" /> be the set of equilibrium solutions which are Pareto optimal (cf. [[Arbitration scheme|Arbitration scheme]]). A game is called Nash solvable and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698029.png" /> is said to be a Nash solution if all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698030.png" /> are equivalent and interchangeable. A game is called strictly solvable if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698031.png" /> is non-empty and all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698032.png" /> are equivalent and interchangeable. Two-person zero-sum games (cf. [[Two-person zero-sum game|Two-person zero-sum game]]) with optimal strategies are Nash solvable and strictly solvable; however, in the general case such a solvability is often impossible.
+
Two equilibrium solutions $  s $
 +
and $  t $
 +
are called interchangeable if any solution $  r = \prod _ {i \in J }  r _ {i} $,  
 +
where $  r _ {i} = s _ {i} $
 +
or $  r _ {i} = t _ {i} $,  
 +
$  i \in J $,  
 +
is also an equilibrium solution. They are called equivalent if $  H _ {i} ( s) = H _ {i} ( t) $
 +
for all $  i \in J $.  
 +
Let $  Q $
 +
be the set of all equilibrium solutions, and let $  Q  ^  \prime  \subset  Q $
 +
be the set of equilibrium solutions which are Pareto optimal (cf. [[Arbitration scheme|Arbitration scheme]]). A game is called Nash solvable and $  Q $
 +
is said to be a Nash solution if all $  s \in Q $
 +
are equivalent and interchangeable. A game is called strictly solvable if $  Q  ^  \prime  $
 +
is non-empty and all $  s \in Q  ^  \prime  $
 +
are equivalent and interchangeable. Two-person zero-sum games (cf. [[Two-person zero-sum game|Two-person zero-sum game]]) with optimal strategies are Nash solvable and strictly solvable; however, in the general case such a solvability is often impossible.
  
 
Other attempts at completing the principle of realizability of the objective were made. Thus, it was suggested [[#References|[4]]] that the unique equilibrium solution or the maximum solution (in this last situation each player may ensure his/her own gain irrespective of the strategies chosen by the other players), the choice of which is based on the introduction of a new preference relation on the set of solutions, be considered as the solution of the non-cooperative game. In another approach the solution of a non-cooperative game is defined by a subjective prognosis of the behaviour of the players [[#References|[5]]].
 
Other attempts at completing the principle of realizability of the objective were made. Thus, it was suggested [[#References|[4]]] that the unique equilibrium solution or the maximum solution (in this last situation each player may ensure his/her own gain irrespective of the strategies chosen by the other players), the choice of which is based on the introduction of a new preference relation on the set of solutions, be considered as the solution of the non-cooperative game. In another approach the solution of a non-cooperative game is defined by a subjective prognosis of the behaviour of the players [[#References|[5]]].
Line 15: Line 62:
 
====References====
 
====References====
 
<table><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. 81–140</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J. Nash,  "Noncooperative games"  ''Ann. of Math.'' , '''54'''  (1951)  pp. 286–295</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  I.L. Glicksberg,  "A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points"  ''Proc. Amer. Math. Soc.'' , '''3'''  (1952)  pp. 170–174</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  J.C. Harsanyi,  "A general solution for finite noncooperative games based on risk-dominance"  L.S. Shapley (ed.)  A.W. Tucker (ed.)  M. Dresher (ed.) , ''Advances in game theory'' , Princeton Univ. Press  (1964)  pp. 651–679</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  E.I. Vilkas,  "The axiomatic definition of equilibrium points and the value of a non-coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698033.png" />-person game"  ''Theory Probab. Appl.'' , '''13''' :  3  (1968)  pp. 523–527  ''Teor. Veroyatnost. i Primenen.'' , '''13''' :  3  (1968)  pp. 555–560</TD></TR></table>
 
<table><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. 81–140</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J. Nash,  "Noncooperative games"  ''Ann. of Math.'' , '''54'''  (1951)  pp. 286–295</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  I.L. Glicksberg,  "A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points"  ''Proc. Amer. Math. Soc.'' , '''3'''  (1952)  pp. 170–174</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  J.C. Harsanyi,  "A general solution for finite noncooperative games based on risk-dominance"  L.S. Shapley (ed.)  A.W. Tucker (ed.)  M. Dresher (ed.) , ''Advances in game theory'' , Princeton Univ. Press  (1964)  pp. 651–679</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  E.I. Vilkas,  "The axiomatic definition of equilibrium points and the value of a non-coalition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066980/n06698033.png" />-person game"  ''Theory Probab. Appl.'' , '''13''' :  3  (1968)  pp. 523–527  ''Teor. Veroyatnost. i Primenen.'' , '''13''' :  3  (1968)  pp. 555–560</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  N.N. Vorob'ev,  "Game theory. Lectures for economists and system scientists" , Springer  (1977)  (Translated from Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  N.N. Vorob'ev,  "Game theory. Lectures for economists and system scientists" , Springer  (1977)  (Translated from Russian)</TD></TR></table>

Latest revision as of 08:03, 6 June 2020


A system

$$ \Gamma = < J, \{ S _ {i} \} _ {i \in J } ,\ \{ H _ {i} \} _ {i \in J } > , $$

where $ J $ is the set of players, $ S _ {i} $ is the set of strategies (cf. Strategy (in game theory)) of the $ i $- th player and $ H _ {i} $ is the gain function of the $ i $- th player, defined on the Cartesian product $ S = \prod _ {i \in J } S _ {i} $. A non-cooperative game is played as follows: players, who are acting individually (do not form a coalition, do not cooperate), select their strategies $ s _ {i} \in S _ {i} $, as a result of which the situation $ s = \prod _ {i \in J } s _ {i} $ appears, in which the $ i $- th player obtains the gain $ H _ {i} ( s) $. The main optimality principle in a non-cooperative game is the principle of realizability of the objective [1], which generates the Nash equilibrium solutions. A solution $ s ^ {*} $ is called an equilibrium solution if for all $ i \in J $, $ s _ {i} \in S _ {i} $, the inequality

$$ H _ {i} ( s ^ {*} ) \geq H _ {i} ( s ^ {*} \| s _ {i} ) , $$

where $ s ^ {*} \| s _ {i} = \prod _ {j \in J \setminus i } s _ {j} ^ {*} \times s _ {i} $, is valid. Thus, none of the players is interested in unilaterally disturbing the equilibrium solution previously agreed upon between them. It has been proved (Nash's theorem) that a finite non-cooperative game (the sets $ J $ and $ S _ {i} $ are finite) possesses an equilibrium solution for mixed strategies. This theorem has been generalized to include infinite non-cooperative games with a finite number of players [3] and non-cooperative games with an infinite number of players (cf. Non-atomic game).

Two equilibrium solutions $ s $ and $ t $ are called interchangeable if any solution $ r = \prod _ {i \in J } r _ {i} $, where $ r _ {i} = s _ {i} $ or $ r _ {i} = t _ {i} $, $ i \in J $, is also an equilibrium solution. They are called equivalent if $ H _ {i} ( s) = H _ {i} ( t) $ for all $ i \in J $. Let $ Q $ be the set of all equilibrium solutions, and let $ Q ^ \prime \subset Q $ be the set of equilibrium solutions which are Pareto optimal (cf. Arbitration scheme). A game is called Nash solvable and $ Q $ is said to be a Nash solution if all $ s \in Q $ are equivalent and interchangeable. A game is called strictly solvable if $ Q ^ \prime $ is non-empty and all $ s \in Q ^ \prime $ are equivalent and interchangeable. Two-person zero-sum games (cf. Two-person zero-sum game) with optimal strategies are Nash solvable and strictly solvable; however, in the general case such a solvability is often impossible.

Other attempts at completing the principle of realizability of the objective were made. Thus, it was suggested [4] that the unique equilibrium solution or the maximum solution (in this last situation each player may ensure his/her own gain irrespective of the strategies chosen by the other players), the choice of which is based on the introduction of a new preference relation on the set of solutions, be considered as the solution of the non-cooperative game. In another approach the solution of a non-cooperative game is defined by a subjective prognosis of the behaviour of the players [5].

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. 81–140
[2] J. Nash, "Noncooperative games" Ann. of Math. , 54 (1951) pp. 286–295
[3] I.L. Glicksberg, "A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points" Proc. Amer. Math. Soc. , 3 (1952) pp. 170–174
[4] J.C. Harsanyi, "A general solution for finite noncooperative games based on risk-dominance" L.S. Shapley (ed.) A.W. Tucker (ed.) M. Dresher (ed.) , Advances in game theory , Princeton Univ. Press (1964) pp. 651–679
[5] E.I. Vilkas, "The axiomatic definition of equilibrium points and the value of a non-coalition -person game" Theory Probab. Appl. , 13 : 3 (1968) pp. 523–527 Teor. Veroyatnost. i Primenen. , 13 : 3 (1968) pp. 555–560

Comments

References

[a1] N.N. Vorob'ev, "Game theory. Lectures for economists and system scientists" , Springer (1977) (Translated from Russian)
How to Cite This Entry:
Non-cooperative game. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Non-cooperative_game&oldid=47986
This article was adapted from an original article by E.I. VilkasE.B. Yanovskaya (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article