Nash equilibrium

From Theory

Notes for CS 8803 - Game Theory and Computer Science. Spring 2008

A Nash Equilibrium (NE) is a vector of strategies (pure or mixed), one per player, such that no player can improve her own payoff by unilaterally changing strategies. For an $N$ player game $G = (N,A = \times_{i=1}^N A_i, u: A \rightarrow \reals^N)$ , a NE is $\sigma \in \Delta = \Delta_1 \times \ldots \times \Delta_N$ , such that,

$u_i(\sigma)\geq u_i(\sigma_i',\sigma_{-i}),$ for all $\sigma \in \Delta, \sigma_i'\in \Delta_i$ .

Note that it is equivalent to the following definition:

$u_i(\sigma)\geq u_i(a_i',\sigma_{-i}),$ for all $\sigma \in \Delta, a_i'\in A_i$ .

Some nice examples of Nash Eq. are:

Coordination game: it is a NE to all drive on the left side of roads, or all drive on right side of roads (there is one more... :)
Prisoner's dilemma: it is a NE to not cooperate in prisoner's dilemma.

A game is finite if it has a finite number of players and each player has a finite number of actions (or pure strategies).

Theorem. (Nash 1950) Let $G$ be a finite game. Then there exists a mixed-strategy NE for $G$ .

Proof.

( The proof can also be found at Lecture 5 of Yishay Mansour's course. )

The proof uses Brouwer's Fixed Point Theorem which states the following.

Theorem. (L.E.J. Brouwer 1909) Let $B$ be a closed and bounded, convex set. If $f : B\rightarrow B$ is a continuous map, then there must exist $x\in B$ such that $f (x) = x$ .

We now turn to the proof of the existence theorem. For every player $i$ , let the set of actions $A i$ be ${a i 1,..., a i m}$ . For $1\leq i\leq n, 1\leq j\leq m, \sigma\in \Delta$ , define $g i j (σ)$ to be the gain for player $i$ from switching to the deterministic action $a i j$ , when $σ$ is the joint strategy (if this switch is profitable). So we have,

g i j (σ) = max{u i (a i j,σ - i) - u i (σ),0}

We can now define a map between mixed strategies $y:\Delta(A)\rightarrow \Delta(A)$ by

$y_{ij}(\sigma) = \frac{\sigma_{ij}+g_{ij}(\sigma)}{1+\sum_{j=1}^{m}{g_{ij}(\sigma)}}$

We now make two observations about this mapping:

For every player $i$ and action $a i j$ , the mapping $g i j (σ)$ is continuous with respect to $σ$ . This is due to the fact that $u i (σ)$ is obviously continuous, making $g i j (σ)$ and consequently $y i j (σ)$ continuous.
For every player $i$ , the vector $(y_{ij}(\sigma))_{j=1}^{m}$ is a distribution, i.e., it is in $Δ(A i)$ . This is due to the fact that the denominator of $y i j (σ)$ is a normalization constant for any given $i$ .

Therefore $y$ fulfills the conditions of Brouwer's Fixed Point Theorem. Using the theorem, we conclude that there is a fixed point $σ$ for $y$ . This point satisfies

$\sigma_{ij} = \frac{\sigma_{ij}+g_{ij}(\sigma)}{1+\sum_{j=1}^{m}{g_{ij}(\sigma)}}$

Notice that this is possible only in one of two cases. Either $g i j (σ) = 0$ for every $i$ and $j$ , in which case we have an equilibrium (since no one can profit from their strategy). If this is not the case, then there is a player $i$ such that $g i j (σ) > 0$ . This would imply,

$\sigma_{ij}\left(1+\sum_{j=1}^{m}{g_{ij}(\sigma)}\right) = \sigma_{ij}+g_{ij}(\sigma)$

$\sigma_{ij}\left(\sum_{j=1}^{m}{g_{ij}(\sigma)}\right) = g_{ij}(\sigma)$

This means that $g i j (σ) = 0$ if and only if $σ i j = 0$ , and therefore, $\sigma_{ij}>0 \implies g_{ij}(\sigma)>0$ . However, this is impossible by the definition of $g i j (σ)$ . Recall that $u i (σ)$ is a mean with weights $σ i j$ . Therefore, it cannot be that player $i$ can profit from every pure action in the support of $σ i$ (with respect to the mean).

We are therefore left with the former possibility, i.e. $g i j (σ) = 0$ for all $i$ and $j$ , implying a Nash Equilibrium

Q.E.D.

The production of this material was supported in part by NSF award SES-0734780.

Retrieved from "http://wiki.cc.gatech.edu/theory/index.php/Nash_equilibrium"

Aug	SEP	Oct
	09
2008	2009	2010

Nash equilibrium

From Theory

Views

Personal tools

Navigation

Search

Toolbox