Saddle point in game theory

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[edit]

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[edit]