Nash Equilibrium

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 pP chooses a strategy xp from their non-empty set Xp of possible strategies; X is the Cartesian product space of all the Xp 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 xX, player p gets the payoff fp(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 fp(x) larger) makes player q less happy (i.e. makes fq(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 xp in Xp,

fp(z) ≥ fp(zxp),

where “zxp” means “replace the pth entry of z by xp and keep the other entries of z unchanged”. If this inequality holds strictly for every xp other than zp, 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.

Advertisements

1 thought on “Nash Equilibrium”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s