Namespaces
Variants
Actions

Difference between revisions of "Nash theorem (in game theory)"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(Completed rendering of article in TeX. Improved clarity of exposition.)
Line 1: Line 1:
A theorem on the existence of equilibrium points in a mixed extension of a finite [[Non-cooperative game|non-cooperative game]]
+
A theorem on the existence of equilibrium points in a mixed extension of a finite [[Non-cooperative game|non-cooperative game]] $ \Gamma \stackrel{\text{df}}{=} \langle J,(S_{i})_{i \in J},(H_{i})_{i \in J} \rangle $, where
 +
* $ J $ is a finite set of players,
 +
* $ (S_{i})_{i \in J} $ is their strategy profile, and
 +
* $ H_{i}: S \stackrel{\text{df}}{=} \prod_{i \in J} S_{i} \to \mathbb{R} $ is a pay-off function for player $ i $, for each $ i \in J $ (see also [[Games, theory of|Games, theory of]]).
 +
It was established by J. Nash in [[#References|[1]]]. For each $ i \in J $, let $ M_{i} $ denote the set of all probability measures on $ S_{i} $. Nash’s theorem then asserts that there exists a measure $ \mu^{*} \in M \stackrel{\text{df}}{=} \prod_{i \in J} M_{i} $ such that
 +
$$
 +
\forall i \in J, ~ \forall \mu_{i} \in M_{i}: \qquad
 +
{H_{i}}(\mu^{*}) \geq {H_{i}}(\mu^{*} \| \mu_{i}),
 +
$$
 +
where $ \mu^{*} \| \mu_{i} $ denotes the measure on $ M $ that results from replacing the $ i $-th component of the vector $ \mu^{*} $ by $ \mu_{i} $, and $ {H_{i}}(\mu) \stackrel{\text{df}}{=} \mathsf{E}(H_{i},\mu) $. All known proofs of Nash’s theorem rely on a fixed-point theorem, such as the [[Kakutani theorem|Kakutani Fixed-Point Theorem]] or the [[Brouwer theorem|Brouwer Fixed-Point Theorem]].
  
<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/n066040/n0660401.png" /></td> </tr></table>
+
====References====
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n0660402.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n0660403.png" /> are the finite sets of players and their strategies, respectively, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n0660404.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n0660405.png" /> is the pay-off function of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n0660406.png" /> (see also [[Games, theory of|Games, theory of]]). It was established by J. Nash in [[#References|[1]]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n0660407.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n0660408.png" />, be the set of all probability measures on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n0660409.png" />. Nash' theorem asserts that there is a measure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n06604010.png" /> for which
+
<table>
 
+
<TR><TD valign="top">[1]</TD><TD valign="top">
<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/n066040/n06604011.png" /></td> </tr></table>
+
J. Nash, “Non-cooperative games”, ''Ann. of Math.'', '''54''' (1951), pp. 286–295.</TD></TR>
 
+
<TR><TD valign="top">[2]</TD><TD valign="top">
for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n06604012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n06604013.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n06604014.png" /> denotes the measure from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n06604015.png" /> that results from replacing the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n06604016.png" />-th component of the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n06604017.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n06604018.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066040/n06604019.png" />. The known proofs of Nash' theorem rely on a fixed-point theorem.
+
N.N. Vorob’ev, “Foundations of game theory. Non-cooperative games”, Moscow (1984). (In Russian)</TD></TR>
 
+
<TR><TD valign="top">[3]</TD><TD valign="top">
====References====
+
N.N. Vorob’ev, “Game theory. Lectures for economists and system scientists”, Springer (1977). (Translated from Russian)</TD></TR>
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> J. Nash,   "Non-cooperative games"  ''Ann. of Math.'' , '''54''' (1951) pp. 286–295</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> N.N. Vorob'ev,   "Foundations of game theory. Non-cooperative games" , Moscow (1984) (In Russian)</TD></TR><TR><TD valign="top">[3]</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>

Revision as of 09:52, 14 December 2016

A theorem on the existence of equilibrium points in a mixed extension of a finite non-cooperative game $ \Gamma \stackrel{\text{df}}{=} \langle J,(S_{i})_{i \in J},(H_{i})_{i \in J} \rangle $, where

  • $ J $ is a finite set of players,
  • $ (S_{i})_{i \in J} $ is their strategy profile, and
  • $ H_{i}: S \stackrel{\text{df}}{=} \prod_{i \in J} S_{i} \to \mathbb{R} $ is a pay-off function for player $ i $, for each $ i \in J $ (see also Games, theory of).

It was established by J. Nash in [1]. For each $ i \in J $, let $ M_{i} $ denote the set of all probability measures on $ S_{i} $. Nash’s theorem then asserts that there exists a measure $ \mu^{*} \in M \stackrel{\text{df}}{=} \prod_{i \in J} M_{i} $ such that $$ \forall i \in J, ~ \forall \mu_{i} \in M_{i}: \qquad {H_{i}}(\mu^{*}) \geq {H_{i}}(\mu^{*} \| \mu_{i}), $$ where $ \mu^{*} \| \mu_{i} $ denotes the measure on $ M $ that results from replacing the $ i $-th component of the vector $ \mu^{*} $ by $ \mu_{i} $, and $ {H_{i}}(\mu) \stackrel{\text{df}}{=} \mathsf{E}(H_{i},\mu) $. All known proofs of Nash’s theorem rely on a fixed-point theorem, such as the Kakutani Fixed-Point Theorem or the Brouwer Fixed-Point Theorem.

References

[1] J. Nash, “Non-cooperative games”, Ann. of Math., 54 (1951), pp. 286–295.
[2] N.N. Vorob’ev, “Foundations of game theory. Non-cooperative games”, Moscow (1984). (In Russian)
[3] N.N. Vorob’ev, “Game theory. Lectures for economists and system scientists”, Springer (1977). (Translated from Russian)
How to Cite This Entry:
Nash theorem (in game theory). Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Nash_theorem_(in_game_theory)&oldid=18406
This article was adapted from an original article by E.B. Yanovskaya (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article