Recently I’ve been thinking about game-theoretic concepts like minimax, maximin, and Nash equilibrium strategies. Here’s a quick note on Nash equilibria, drawn largely from the English-language Wikipedia article on the topic.

The setup is that we have a non-empty set *P* of players. Each player *p* ∈ *P* chooses a *strategy* *x*_{p} from their non-empty set *X*_{p} of possible strategies; *X* is the Cartesian product space of all the *X*_{p} spaces, so each element *x* of *X* describes the strategy choice of all the players *p* in *P*.

The *payoff* is a function *f*: *X* →ℝ^{P}; implicitly, the idea is that under the choice of strategies *x* ∈ *X*, player *p* gets the payoff *f*_{p}(*x*), and wants the largest payoff possible. The question is, how can we say that some element *z* of *X* is “better” than all the others *x*? It’s easy to imagine an *f* for which making player *p* happier (i.e. choosing an *x* that makes *f*_{p}(*x*) larger) makes player *q* less happy (i.e. makes *f*_{q}(*x*) smaller). A Nash equilibrium is a particular notion of “everyone doing as best as they can”.

More precisely, an element *z* of *X* is called a *Nash equilibrium* if, for every player *p* in *P*, and for every *x*_{p} in *X*_{p},

*f*_{p}(*z*) ≥ *f*_{p}(*z* ← *x*_{p}),

where “*z* ←*x*_{p}” means “replace the *p*th entry of *z* by *x*_{p} and keep the other entries of *z* unchanged”. If this inequality holds strictly for every *x*_{p} other than *z*_{p}, then *z* is called a *strict Nash equilibrium*. Nash equilibria are somehow more natural objects than maximizers (or maximinimizers, or other exotic creatures) because at a Nash equilibrium, each player can do no better by unilaterally changing his/her strategy, knowing the other player’s choice of strategy.

That said, Nash equilibria do not need to be Pareto optimal, and can have non-rational consequences in sequential games because players may threaten one another with non-rational moves.

**Addendum.** The book *Essentials of Game Theory: A Concise, Multidisciplinary Introduction* by Kevin Leyton-Brown and Yoav Shoham, published by Morgan & Claypool, provides a nice sub-100-page introduction to many of these concepts. The book has a website, including options for PDF/e-book download, at www.gtessentials.org.

## One thought on “Nash Equilibrium”