Nash Equilibria

As you know if you’ve been reading this blog lately, I’m teaching game theory. I could use some help.

Is there a nice elementary proof of the existence of Nash equilibria for 2-person games?

Here’s the theorem I have in mind. Suppose A and B are m \times n matrices of real numbers. Say a mixed strategy for player A is a vector p \in \mathbb{R}^m with

\displaystyle{ p_i \ge 0 , \quad \sum_i p_i = 1 }

and a mixed strategy for player B is a vector q \in \mathbb{R}^n with

\displaystyle{ q_i \ge 0 , \quad \sum_j q_j = 1 }

A Nash equilibrium is a pair consisting of a mixed strategy p for A and a mixed strategy q for B such that:

1) For every mixed strategy p' for A, p' \cdot A q \le p \cdot A q.

2) For every mixed strategy q' for B, p \cdot B q' \le p \cdot B q.

(The idea is that p \cdot A q is the expected payoff to player A when A chooses mixed strategy p and B chooses q. Condition 1 says A can’t improve their payoff by unilaterally switching to some mixed strategy p'. Similarly, condition 2 says B can’t improve their expected payoff by unilaterally switching to some mixed strategy q'.)

Some history

The history behind my question is sort of amusing, so let me tell you about that—though I probably don’t know it all.

Nash won the Nobel Prize for a one-page proof of a more general theorem for n-person games, but his proof uses Kakutani’s fixed-point theorem, which seems like overkill, at least for the 2-person case. There is also a proof using Brouwer’s fixed-point theorem; see here for the n-person case and here for the 2-person case. But again, this seems like overkill.

Earlier, von Neumann had proved a result which implies the one I’m interested in, but only in the special case where B = -A: the so-called minimax theorem. Von Neumann wrote:

As far as I can see, there could be no theory of games … without that theorem … I thought there was nothing worth publishing until the Minimax Theorem was proved.

I believe von Neumann used Brouwer’s fixed point theorem, and I get the impression Kakutani proved his fixed point theorem in order to give a different proof of this result! Apparently when Nash explained his generalization to von Neumann, the latter said:

That’s trivial, you know. That’s just a fixed point theorem.

But you don’t need a fixed point theorem to prove von Neumann’s minimax theorem! There’s a more elementary proof in an appendix to Andrew Colman’s 1982 book Game Theory and its Applications in the Social and Biological Sciences. He writes:

In common with many people, I first encountered game theory in non-mathematical books, and I soon became intrigued by the minimax theorem but frustrated by the way the books tiptoed around it without proving it. It seems reasonable to suppose that I am not the only person who has encountered this problem, but I have not found any source to which mathematically unsophisticated readers can turn for a proper understanding of the theorem, so I have attempted in the pages that follow to provide a simple, self-contained proof with each step spelt out as clearly as possible both in symbols and words.

This proof is indeed very elementary. The deepest fact used is merely that a continuous function assumes a maximum on a compact set—and actually just a very special case of this. So, this is very nice.

Unfortunately, the proof is spelt out in such enormous elementary detail that I keep falling asleep halfway through! And worse, it only covers the case B = -A.

Is there a good references to an elementary but terse proof of the existence of Nash equilibria for 2-person games? If I don’t find one, I’ll have to work through Colman’s proof and then generalize it. But I feel sure someone must have done this already.

31 Responses to Nash Equilibria

  1. Richard Brown says:

    Equation 2) has a typo (should be B on both left and right)

  2. Nash equil. are best conveyed by clear descriptions of interests vs tradeoffs, ie, stories from the point of view of actual players in a game.

    I asked Nash this once and he nodded and laughed at the “overproof” of the basic point.

  3. Hi John,

    In Webb’s book (which is a nice book for a mathematics course on game theory BTW) there is an elementary algebraic proof of the existence of NE in a 2 player 2 strategy game. I know this isn’t what you asked and also I’m sure you wouldn’t actually need the proof in the book but its an accessible starting point perhaps for students.

    I look forward to reading future posts!

    • John Baez says:

      Thanks! I have a big stack of game theory books on my desk, including a bunch you recommended, but it seems not that one. I’ll check out that proof. Maybe I should present it in class.

      The existence of this elementary proof, together with Colman’s fairly elementary proof that Nash equilibria exist for 2-person zero-sum games with an arbitrary number of strategies, seems to hint that there’s an elementary proof of the result I actually want.

      But this may not be true!

      Over on MathOverflow, Rabee Tourky wrote:

      Any proof of the existence of a Nash equilibrium for two person finite games games is a proof of kakutani’s fixed point theorem. This is the simplest proof that I know of. Though I can conceive of simpler proofs.

      • Andrew McLennan† and Rabee Tourky, ‡From imitation games to Kakutani.

      and Michael Greinecker wrote:

      Here is what seems to amount to a simplified version of the argument that shows how one can prove the Brouwer fixed point theorem from the existence of Nash equilibria in two player games (modulo a limiting compactness argument):

      Brouwer implies Nash implies Brouwer, The Leisure of the The Theory Class.

      However, the blog article ‘Brouwer implies Nash implies Brouwer’, which is very nice, derives Brouwer’s fixed-point theorem from the existence of Nash equilibria where the set of pure strategies is not finite, but an arbitrary compact convex subset of $\mathbb{R}^n.$ This is seemingly a much more heavy-duty fact than what I’m after! But, the post has something to say about that….

      Anyway, I seem to be closing in on the truth here.

  4. Arrow says:

    It is interesting that for mixed strategies there are always NE. But aren’t all those cases of NEs in games where they only exist for mixed strategies stalemate situations?

    Let’s take rock, paper scissors as an example. For pure strategies there is no NE, for mixed strategies there is picking at random, but that isn’t terribly interesting. Are there games where allowing mixed strategies leads to NEs (that were not there before) where one player gains an advantage?

    Another thing about rock, paper scissors is that it seems rather easy to modify the game to break even the mixed strategies NEs. For example let’s say the payoff is also dependent on the consistency of choices in previous games, +1 for regular win and +0.5 for picking the same choice as last time, that should motivate players to prefer a particular choice.

    • John Baez says:

      Arrow wrote:

      Are there games where allowing mixed strategies leads to NEs (that were not there before) where one player gains an advantage?

      Yes; wait ’til the next post… or maybe someone here can make up an example. Most games are of this form, so examples aren’t hard to find.

  5. Aaron F. says:

    Nash equil. are best conveyed by clear descriptions of interests vs tradeoffs, ie, stories from the point of view of actual players in a game.

    If this is actually true, it should be possible to write a proof along these lines. ;) Can you give examples of the “clear descriptions of interests vs. tradeoffs” you’re talking about?

    • My point is, instead of fielding proofs, try to tell a story. That’s how people learn.

      • John Baez says:

        I tell plenty of stories in the course I’m teaching, and in class we play lots of games. But it’s a course for math majors. I’ll make sure they get the idea of a Nash equilibrium, but they need to learn to understand proofs, too!

        What I’m looking for here is a proof of the existence of Nash equilibria for 2-person games that doesn’t require the Kakutani or Brouwer fixed-point theorems. It’s the use of these rather heavy-duty tools—which most kids learn only in grad school—that makes undergraduate courses on game theory present the existence of Nash equilibria as an article of faith, skipping the proof. But I suspect that for 2-person games these fixed-point theorems are overkill. It’s only linear algebra, for god’s sake!

        • Robert says:

          What about just proving a special case of the fixed point theorems, just strong enough to apply to 2-person games? Since you don’t need the full strength of the theorem, you may be able to do this at undergraduate level.

        • John Baez says:

          I could try that. I’ll get to work soon and examine various options!

  6. I agree with Prof. Benford. The easiest way I learned of Game Theory was on a bike ride from Tustin High School to Ed Thomas’ Book Carnival in Orange back in 2001. My girlfriend at the time asked about The Fermi Paradox or the Great Silence. (Why haven’t we heard them yet?)

    As you all know the points Mike Hart and Enrico Fermi brought up were:

    -The Sun is a young star.
    -There are billions of stars in the galaxy that are billions of years older;
    -Some of these stars likely have Earth-like planets[2] which, if the Earth is typical, may develop intelligent life;
    -Presumably some of these civilizations will develop interstellar travel, as Earth seems likely to do;
    -At any practical pace of interstellar travel, the galaxy can be completely colonized in just a few tens of millions of years.)

    Where is everybody?! (No evidence of Von Neumann probes either?!!)

    The movie ‘A Beautiful Mind’ just came out (2000) and I read up on Game Theory and used the simple Two prisoner Dilemma to answer her query. (Her parents where peaceniks, as are mine even though both our parents have had military/para-military experience)

    Suggesting we reach a Kardashev level 1 society (a true global society, as it would be the only logical like option) one world governing body, one world telephone system – internet, one world language – English; Terran hegemony you name it. Just because we can get along with each other relatively well in that world would not immediately mean we have inhibition to kill other species that exercise a high degree on intelligence.

    We kill elephants and dolphins all the time and they are not a threat to us.

    Extra-terrestrial species may not necessarily play nice.

    Why?

    Because, “they” are not part of our species or civilization.

    This brings us to where the prisoner dilemma kicks in.

    We cannot afford to be proven wrong to think they would be peaceful.

    A Kardashev level 1 would harness 10×16 to 18 power in W (watts)

    Using relativistic weapons would push that number even higher.

    When you get to that level then we can make starships that travel at relativistic speeds. (Thank you Prof. Benford!)

    What that is essentially is a kardashev level 1 or 2 doomsday weapon. (A weapon that can take out level 1 and 2 civilizations)

    To make it simple suggest we only had 2 intelligent level 1 or 2 societies in this galaxy.

    You then have two civilizations either both level 1 or 2 sharing 1 galaxy having this whacko scenario

    *(Me and my girl at the time had the thought matrix below. I am sure someone else online has replicated it, the internet is a big place)

    You can substitute any Type 1 or 2 civilization killer

    Be it nanites, relativistic kill vehicles, sun destroyers (weapons that make a home star go nova) etc. etc………..

    Race 2 Ignores Race 2 Attacks
    Race 1 Ignores Both live constant fear Race 1 exterminated
    Race 2 lives free of fear

    Race 1 Attacks Race 1 lives free of fear Both are devastated
    Race 2 exterminated but not destroyed

    After the date we both wanted to write a paper titled

    “Game theory / Nash Equilibria multiple player scenarios as a possible response to Fermi Paradox”

    We were both silly…..but whatcha gonna do? We were 17 year olds.

    We did eventually write it down up to about 5 players (as in 5 intelligent level 1 or 2 societies in our Galaxy.

    It was pretty funny.

    but just for a 2 player response below is a less clean cut outcomes/more detailed matrix:

    -Key(outcomes)

    2= alive, free of fear of retaliatory strike
    4= alive, but fear or retaliatory/first strike from opponent civ or federation.
    1= civilization intact, but devastated, probably downgraded from level 1 or 2
    3= total annihilation

    Cooperate Defect

    Cooperate 4,4 3,2

    Defect 2,3 1,1

    *(again I am sure someone else has this matrix somewhere online as I have been talking about this for some 13 years now)

    In jest it can be applied to kids with high capacity guns on a playgrounds, kardashev level 1 or 2 civilizations, and hegemonic empires pre-empting first strikes.

    Or whatever else you can think of.

    Hehehe.

    P.S. Prof. Baez did you catch Jeff Buckley’s “Grace” yet?

  7. Darn my coding skills suck….It looked like matrix form when I typed it and it did not when I pressed the “Post Comment” button.

  8. “That’s trivial, you know.”

    Trivial is in the eye of the beholder. Be especially careful if it is von Neumann’s eye. (I’m reminded of the fly between the trains.) There is a story about a famous mathematician, maybe Hardy, saying “this follows trivially from…” while writing on the blackboard. Then he paused. Then he stepped back from the blackboard and thought a bit. Then he sat down and thought some more. Then he went into another room. After half an hour, he came back, continuing his lecture where he left off, saying “Yes, it really is trivial”.

    • John Baez says:

      I think von Neumann claimed Nash’s theorem was trivial because he was jealous!

      Nash used the same technique von Neumann had—a fixed-point theorem—to prove the existence of equilibria for a much wider and more interesting class of games! Von Neumann had considered 2-player zero-sum games. Nash considered n-player games that could be zero-sum or nonzero-sum games. Von Neumann (being a genius) should have tried to generalize his result. Nash showed the generalization could be done in five easy paragraphs.

      So, I think von Neumann was jealous and trying to cut Nash down to size.

  9. davetweed says:

    There’s a 15 minute UK BBC radio programme that touches on game theory and poker here. It’s a bit… energetically breathless and seems, to me, more enthusiastic about big ideas than seeing if they’re actually what happens in the real world. But it might be interesting to some following these posts.

  10. Luís says:

    Maybe this is a solution.

    e, abusing notation, a little, is the vector of ones. Set

    p_2= \mathrm{max}_{p,q}  p\cdot Bq

    s.t. p\cdot e=1 and q \cdot e=1 with p \geq 0, q \geq 0. A continuous function p \cdot Bq on a compact space,

    \{(p,q) \in \mathbb{R}^{n+m}: p\cdot e=1, q\cdot e=1, p \geq \bar{0}, q \geq \bar{0} \}

    has a maximum, no prob there. Now find the maximums of player 1 payoff, on the set of points that maximized player 2, and choose one of them, (p^*,q^*) \in \mathrm{arg max}_{p,q}  p\cdot Aq s.t p\cdot  Bq \geq p_2. The function p\cdot Aq is again continuous, the set p\cdot Bq \geq p_2 is compact and non-empty. And if I did not miss anything (p^*,q^*) is your Nash equilibrium.

    • Luís says:

      I did miss something. Player 1 is not necessarily maximizing is payoff. Bah. So dumb!

    • Luís says:

      Along the same lines. For each p maximize player 2′s payoff:

      g_2(p)= \mathrm{max}_{\{q: q\cdot e=1\}} p\cdot Bq

      (continuous function on compact set).

      A sequential argument easily prove g_2(p) is continuous. The set

      \Delta=\{(p,q): p\cdot Bq \geq g_2(p), p\cdot e=p\cdot q=1, p \geq \bar{0}, q \geq \bar{0}\}

      is closed by g_2(p)‘s continuity, and bounded, so compact.

      Then any (p^*, q^*) \in \mathrm{argmax}_{ \{(p,q) \in \Delta\}} p \cdot Aq

      is a Nash equilibrium.

      • John Baez says:

        Thanks for the comments. I fixed your TeX a bit. I’ve never seen this \mathrm{argmax} notation before! I’m guessing that \mathrm{argmax}_{x \in X} f(x) stands for the set of x \in X that maximize f(x). Is that right?

        Once I’m clear on this, I’ll think about your argument.

        • Graham says:

          I am sure that’s what Luis means. I was initially surprised that you didn’t know the notation, but I think it is more commonly used by programmers than mathematicians.

        • John Baez says:

          That’s for sure. I’ve been doing math for decades and have never seen that notation. It looks useful, but I’ll need to explain it whenever I use it in front of mathematicians.

        • Graham Jones says:

          I noticed it is used in this paper you pointed to:

          Andrew McLennan and Rabee Tourky, From imitation games to Kakutani

          … but they’re economists.

      • Graham says:

        I don’t understand Luis’ proof. Let

        G_2=\{(p,q): p\cdot Bq = g_2(p), p\cdot e=p\cdot q=1, p \geq \bar{0}, q \geq \bar{0}\}

        The set G_2 is like \Delta with an inequality replaced by an equality. It is the set of points (p,q) in which q is an optimal choice for player 2 for some choice p by player 1. Similarly we can define a function g_1(q) and a set G_1. What we want to show is that the intersection of G_1 and G_2 is non-empty.
        I don’t see how it helps to extend G_2 to \Delta and look for points in that.

  11. Graham Jones says:

    I think have an elementary proof for the A=-B case. (It’s certainly elementary: I’m not capable of other kinds.) It uses induction on n+m, assuming (for example) the case n=m=2 is true, and uses the following lemma.

    Lemma. Let v_1, \dots, v_r be vectors in a finite dimensional real vector space. Then either (1) there is a vector u such that v_i \cdot u > 0 for all i or (2) there are nonnegative reals x_1, \dots, x_r, not all zero, such that \sum_1^r x_i v_i = 0.

    Proof idea for lemma: consider the convex hull of the v_i. If the origin is outside we can find a u for (1), otherwise we can show (2).

    Sketch proof of existence of Nash equilibrium. Denote the i’th row of A by A_i, regarded as a vector in \mathbb{R}^n. Player A’s payoff can be written as

    V = (\sum_1^m p_i A_i) \cdot q

    Now q belongs to a hyperplane in \mathbb{R}^n, so we can project q and the A_i onto it, with q becoming y and A_i becoming a_i in \mathbb{R}^{n-1}. Note y is constrained to a hypertetrahedron T. Then

    V = (\sum_1^m p_i a_i) \cdot y  +  f(p,A)

    where f(p,a) does not depend on q.

    Now apply the lemma. If there is a u such that a_i \cdot u > 0 for all i, then player B’s payoff can be improved by moving in direction -u from any point in T, so player B will choose a point on the boundary of T, which means at least one strategy is never chosen. So the game is equivalent to a smaller game and induction provides a Nash equilibrium. Otherwise there is some (not necessarily optimal) choice \hat{p} for player A such that \sum_1^m \hat{p}_i a_i = 0 so player B cannot change the payoff.

    The same argument with A and B reversed either gives an equilibrium by induction, or a choice \hat{q} for player B such that player A cannot change the payoff. So if induction fails in both cases, we have (\hat{p}, \hat{q}).

    • John Baez says:

      This looks interesting—sorry to take so long to reply!

      Now q belongs to a hyperplane in \mathbb{R}^n [...]

      Which hyperplane? Any old random hyperplane? Yes, q belongs to infinitely many different hyperplanes, but this makes me nervous, mainly because I’m trying to understand your proof and it’s not making sense yet.

      Now q belongs to a hyperplane in \mathbb{R}^n, so we can project q and the A_i onto it, with q becoming y [...]

      If q belongs to a hyperplane, projecting q onto this hyperplane won’t change q at all, so we get y = q. Or am I not understanding you?

      • Graham Jones says:

        I mean the hyperplane \sum_1^n q_i = 1. I want regard the unit simplex in \mathbb{R}^n as a hypertetrahedron T in \mathbb{R}^{n-1}.

        A bit later, where I say “…B’s payoff can be improved by moving in direction -u from any point in T, …” I think it would be clearer if I added that this works for any choice by player A.

      • Graham Jones says:

        Here is that part of the argument more explicitly:

        Let \eta = 1/\sqrt n and let s = \eta(1,1,\dots,1), that is, s is a unit vector normal to the hyperplane \sum_1^n q_i=1. Let

        y = q - (q\cdot s)s = q - \eta s

        and

        a_i = A_i - (A_i \cdot s)s

        Then

        p_i A_i \cdot q = p_i((A_i \cdot s)s + a_i) \cdot (\eta s + y)

        and expanding that out and using s \cdot y = 0 leads to

        V = (\sum_1^m p_i a_i) \cdot y  +  f(p,A)

        where f(p,A) does not depend on q.

      • John Baez says:

        Graham wrote:

        I mean the hyperplane \sum_1^n q_i = 1.

        Oh! I hadn’t considered that option. In math, half the time words like ‘line’, ‘plane’ and ‘hyperplane’ mean things that contain the origin, so that they’re vector spaces. And half the time they don’t. It’s about linear versus affine geometry.

        Let me think about this some more now. Thanks.

You can use HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

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

Follow

Get every new post delivered to your Inbox.

Join 2,799 other followers