Difference between revisions of "Saddle point in game theory"
From Encyclopedia of Mathematics
(Importing text file) |
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
||
| Line 1: | Line 1: | ||
| − | + | <!-- | |
| + | s0830601.png | ||
| + | $#A+1 = 29 n = 0 | ||
| + | $#C+1 = 29 : ~/encyclopedia/old_files/data/S083/S.0803060 Saddle point 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 point $ ( x ^ {*} , y ^ {*} ) \in X \times Y $ | |
| + | of a function $ F $ | ||
| + | defined on the Cartesian product $ X \times Y $ | ||
| + | of two sets $ X $ | ||
| + | and $ Y $ | ||
| + | such that | ||
| + | $$ \tag{* } | ||
| + | F ( x ^ {*} , y ^ {*} ) = \ | ||
| + | \max _ {x \in X } \ | ||
| + | F ( x, y ^ {*} ) = \ | ||
| + | \min _ {y \in Y } \ | ||
| + | F ( x ^ {*} , y). | ||
| + | $$ | ||
| + | For a function $ F $ | ||
| + | the presence of a saddle point is equivalent to the existence of optimal strategies (cf. [[Strategy (in game theory)|Strategy (in game theory)]]) for the players in the [[Two-person zero-sum game|two-person zero-sum game]] $ \Gamma = ( X, Y, F ) $. | ||
====Comments==== | ====Comments==== | ||
| − | A point | + | A point $ ( x ^ {*} , y ^ {*} ) \in X \times Y $ |
| + | satisfying the condition (*) is called a saddle point of $ F $ | ||
| + | in general. If $ F $ | ||
| + | is a differentiable function on $ \mathbf R ^ {n} $ | ||
| + | and $ ( \partial F / \partial x _ {i} ) ( x ^ {*} ) = 0 $, | ||
| + | $ i = 1 \dots n $, | ||
| + | while the Hessian matrix $ ( \partial ^ {2} F / \partial x _ {i} \partial x _ {j} ) ( x ^ {*} ) $ | ||
| + | is non-singular and neither positive definite nor negative definite, then locally near $ x ^ {*} $, | ||
| + | $ x ^ {*} $ | ||
| + | is a saddle point. The corresponding splitting of $ \mathbf R ^ {n} $ | ||
| + | near $ x ^ {*} $ | ||
| + | is determined by the negative and positive eigenspaces of the Hessian at $ x ^ {*} $. | ||
| − | Indeed, by the [[Morse lemma|Morse lemma]] there are coordinates | + | Indeed, by the [[Morse lemma|Morse lemma]] there are coordinates $ y _ {1} \dots y _ {n} $ |
| + | near $ x ^ {*} $ | ||
| + | such that $ F $ | ||
| + | has the form | ||
| − | + | $$ | |
| + | F( y) = F( x ^ {*} ) - y _ {1} ^ {2} - \dots - y _ {r} ^ {2} | ||
| + | + y _ {r+} 1 ^ {2} + \dots + y _ {n} ^ {2} , | ||
| + | $$ | ||
| − | where | + | where $ r $ |
| + | is the index of the quadratic form determined by the symmetric matrix $ ( \partial ^ {2} F / \partial x _ {i} \partial x _ {j} ) ( x ^ {*} ) $. | ||
| + | (The index of a quadratic form is the dimension of the largest subspace on which it is negative definite; this is also called the negative index of inertia (cf. also [[Quadratic form|Quadratic form]] and [[Morse index|Morse index]]).) | ||
| − | Let | + | Let $ X, Y $ |
| + | be the spaces of strategies of two players in a zero-sum game and let $ F: X \times Y \rightarrow \mathbf R $ | ||
| + | be (the first component of) the pay-off function (cf. [[Games, theory of|Games, theory of]]). Then a saddle point is also called an equilibrium point. This notion generalizes to $ n $- | ||
| + | player non-cooperative games, cf. [[#References|[a2]]], Chapt. 2; [[Games, theory of|Games, theory of]]; [[Nash theorem (in game theory)|Nash theorem (in game theory)]]; [[Non-cooperative game|Non-cooperative game]]. | ||
====References==== | ====References==== | ||
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> M.W. Hirsch, "Differential topology" , Springer (1976) pp. Chapt. 6</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> J. Szép, F. Forgó, "Introduction to the theory of games" , Reidel (1985) pp. 171; 199</TD></TR></table> | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> M.W. Hirsch, "Differential topology" , Springer (1976) pp. Chapt. 6</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> J. Szép, F. Forgó, "Introduction to the theory of games" , Reidel (1985) pp. 171; 199</TD></TR></table> | ||
Latest revision as of 08:12, 6 June 2020
A point $ ( x ^ {*} , y ^ {*} ) \in X \times Y $
of a function $ F $
defined on the Cartesian product $ X \times Y $
of two sets $ X $
and $ Y $
such that
$$ \tag{* } F ( x ^ {*} , y ^ {*} ) = \ \max _ {x \in X } \ F ( x, y ^ {*} ) = \ \min _ {y \in Y } \ F ( x ^ {*} , y). $$
For a function $ F $ the presence of a saddle point is equivalent to the existence of optimal strategies (cf. Strategy (in game theory)) for the players in the two-person zero-sum game $ \Gamma = ( X, Y, F ) $.
Comments
A point $ ( x ^ {*} , y ^ {*} ) \in X \times Y $ satisfying the condition (*) is called a saddle point of $ F $ in general. If $ F $ is a differentiable function on $ \mathbf R ^ {n} $ and $ ( \partial F / \partial x _ {i} ) ( x ^ {*} ) = 0 $, $ i = 1 \dots n $, while the Hessian matrix $ ( \partial ^ {2} F / \partial x _ {i} \partial x _ {j} ) ( x ^ {*} ) $ is non-singular and neither positive definite nor negative definite, then locally near $ x ^ {*} $, $ x ^ {*} $ is a saddle point. The corresponding splitting of $ \mathbf R ^ {n} $ near $ x ^ {*} $ is determined by the negative and positive eigenspaces of the Hessian at $ x ^ {*} $.
Indeed, by the Morse lemma there are coordinates $ y _ {1} \dots y _ {n} $ near $ x ^ {*} $ such that $ F $ has the form
$$ F( y) = F( x ^ {*} ) - y _ {1} ^ {2} - \dots - y _ {r} ^ {2} + y _ {r+} 1 ^ {2} + \dots + y _ {n} ^ {2} , $$
where $ r $ is the index of the quadratic form determined by the symmetric matrix $ ( \partial ^ {2} F / \partial x _ {i} \partial x _ {j} ) ( x ^ {*} ) $. (The index of a quadratic form is the dimension of the largest subspace on which it is negative definite; this is also called the negative index of inertia (cf. also Quadratic form and Morse index).)
Let $ X, Y $ be the spaces of strategies of two players in a zero-sum game and let $ F: X \times Y \rightarrow \mathbf R $ be (the first component of) the pay-off function (cf. Games, theory of). Then a saddle point is also called an equilibrium point. This notion generalizes to $ n $- player non-cooperative games, cf. [a2], Chapt. 2; Games, theory of; Nash theorem (in game theory); Non-cooperative game.
References
| [a1] | M.W. Hirsch, "Differential topology" , Springer (1976) pp. Chapt. 6 |
| [a2] | J. Szép, F. Forgó, "Introduction to the theory of games" , Reidel (1985) pp. 171; 199 |
How to Cite This Entry:
Saddle point in game theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Saddle_point_in_game_theory&oldid=18503
Saddle point in game theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Saddle_point_in_game_theory&oldid=18503
This article was adapted from an original article by V.L. Kreps (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article