Game Theory (Part 20)

Last time we tackled von Neumann’s minimax theorem:

Theorem. For every zero-sum 2-player normal form game,

\displaystyle{\min_{q'} \max_{p'} \; p' \cdot A q' = \max_{p'} \min_{q'} \; p' \cdot A q'}

where p' ranges over player A’s mixed strategies and q' ranges over player B’s mixed strategies.

We reduced the proof to two geometrical lemmas. Now let’s prove those… and finish up the course!

But first, let me chat a bit about this theorem. Von Neumann first proved it in 1928. He later 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.

Von Neumann’s gave several proofs of this result:

• Tinne Hoff Kjeldesen, John von Neumann’s conception of the minimax theorem: a journey through different mathematical contexts, Arch. Hist. Exact Sci. 56 (2001) 39–68.

In 1937 he gave a proof which became quite famous, based on an important result in topology: Brouwer’s fixed point theorem. This says that if you have a ball

B = \{ x \in \mathbb{R}^n : \|x\| \le 1 \}

and a continuous function

f: B \to B

then this function has a fixed point, meaning a point x \in B with

f(x) = x

You’ll often seen Brouwer’s fixed point theorem in a first course on algebraic topology, though John Milnor came up with a proof using just multivariable calculus and a bit more.

After von Neumann proved his minimax theorem using Brouwer’s fixed point theorem, the mathematician Shizuo Kakutani proved another fixed-point theorem in 1941, which let him get the minimax theorem in a different way. This is now called Kakutani fixed-point theorem.

In 1949, John Nash generalized von Neumann’s result to nonzero-sum games with any number of players: they all have Nash equilibria if we let ourselves use mixed strategies! His proof is just one page long, and it won him the Nobel prize!

Nash’s proof used the Kakutani fixed-point theorem. There is also a proof of Nash’s theorem using Brouwer’s fixed-point theorem; see here for the 2-player case and here for the n-player case.

Apparently when Nash explained his result to von Neumann, the latter said:

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

Maybe von Neumann was a bit jealous?

I don’t know a proof of Nash’s theorem that doesn’t use a fixed-point theorem. But von Neumann’s original minimax theorem seems to be easier. The proof I showed you last time comes from Andrew Colman’s book Game Theory and its Applications in the Social and Biological Sciences. In it, 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.

There are other proofs that avoid fixed-point theorems: for example, there’s one in Ken Binmore’s book Playing for Real. But this one uses transfinite induction, which seems a bit scary and distracting! So far, Colman’s proof seems simplest, but I’ll keep trying to do better.

The lemmas

Now let’s prove the two lemmas from last time. A lemma is an unglamorous result which we use to prove a theorem we’re interested in. The mathematician Paul Taylor has written:

Lemmas do the work in mathematics: theorems, like management, just take the credit.

Let’s remember what we were doing. We had a zero-sum 2-player normal-form game with an m \times n payoff matrix A. The entry A_{ij} of this matrix says A’s payoff when player A makes choice i and player B makes choice j. We defined this set:

C = \{  A q' : \; q' \textrm{ is a mixed strategy for B} \} \subseteq \mathbb{R}^m

For example, if

\displaystyle{ A = \left( \begin{array}{rrr} 2 & 10 &  4 \\-2 & 1 & 6 \end{array} \right) }

then C looks like this:

We assumed that

\displaystyle{ \min_{q'} \max_{p'} \; p' \cdot A q' > 0}

This means there exists p' with

\displaystyle{  p' \cdot A q' > 0}

and this implies that at least one of the numbers (Aq')_i must be positive. So, if we define a set N by

\displaystyle{ N = \{(x_1, \dots, x_m) : x_i \le 0 \textrm{ for all } i\} \subseteq \mathbb{R}^m }

then Aq' can’t be in this set:

\displaystyle{ Aq' \notin N }

In other words, the set C \cap N is empty.

Here’s what C and N look like in our example:

Next, we choose a point in N and a point in C:

• let r be a point in N that’s as close as possible to C,

and

• let s be a point in C that’s as close as possible to r,

These points r and s need to be different, since C \cap N is empty. Here’s what these points and the vector s - r look like in our example:

To finish the job, we need to prove two lemmas:

Lemma 1. r \cdot (s-r) = 0, s_i - r_i \ge 0 for all i, and s_i - r_i > 0 for at least one i.

Proof. Suppose r' is any point in N whose coordinates are all the same those of r, except perhaps one, namely the ith coordinate for one particular choice of i. By the way we’ve defined s and r, this point r' can’t be closer to s than r is:

\| r' - s \| \ge  \| r - s \|

This means that

\displaystyle{ \sum_{j = 1}^m  (r_j' - s_j)^2 \ge  \sum_{j = 1}^m  (r_j - s_j)^2  }

But since r_j' = r_j except when j = i, this implies

(r_i' - s_i)^2 \ge  (r_i - s_i)^2

Now, if s_i \le 0 we can take r'_i = s_i. In this case we get

0 \ge  (r_i - s_i)^2

so r_i = s_i. On the other hand, if s_i > 0 we can take r'_i = 0 and get

s_i^2 \ge  (r_i - s_i)^2

which simplifies to

2 r_i s_i \ge r_i^2

But r_i \le 0 and s_i > 0, so this can only be true if r_i = 0.

In short, we know that either

r_i = s_i

or

s_i > 0 and r_i = 0.

So, either way we get

(s_i - r_i) r_i = 0

Since i was arbitrary, this implies

\displaystyle{ (s - r) \cdot r = \sum_{i = 1}^m (s_i - r_i) r_i = 0 }

which is the first thing we wanted to show. Also, either way we get

s_i - r_i \ge 0

which is the second thing we wanted. Finally, s_i - r_i \ge 0 but we know s \ne r, so

s_i - r_i > 0

for at least one choice of i. And this is the third thing we wanted!   █

Lemma 2. If Aq' is any point in C, then

(s-r) \cdot Aq' \ge 0

Proof. Let’s write

Aq' = a

for short. For any number t between 0 and 1, the point

ta + (1-t)s

is on the line segment connecting the points a and s. Since both these points are in C,, so is this point ta + (1-t)s, because the set C is convex. So, by the way we’ve defined s and r, this point can’t be closer to r than s is:

\| r - (ta + (1-t)s) \| \ge  \| r - s \|

This means that

\displaystyle{  (r + (1-t)s - ta) \cdot  (r + (1-t)s - ta) \ge (r - s) \cdot (r - s) }

With some algebra, this gives

\displaystyle{ 2 (a - s)\cdot (s - r) \ge -t (a - s) \cdot (a - s)  }

Since we can make t as small as we want, this implies that

\displaystyle{  (a - s)\cdot  (s - r) \ge 0  }

or

\displaystyle{ a \cdot (s - r) \ge  s \cdot (s - r)}

or

\displaystyle{ a \cdot (s - r) \ge  (s - r) \cdot (s - r) + r \cdot (s - r)}

By Lemma 1 we have r \cdot (s - r) \ge 0, and the dot product of any vector with itself is nonnegative, so it follows that

\displaystyle{ a \cdot (s - r) \ge 0}

And this is what we wanted to show!   █

Conclusion

Proving lemmas is hard work, and unglamorous. But if you remember the big picture, you’ll see how great this stuff is.

We started with a very general concept of two-person game. Then we introduced probability theory and the concept of ‘mixed strategy’. Then we realized that the expected payoff of each player could be computed using a dot product! This brings geometry into the subject. Using geometry, we’ve seen that every zero-sum game has at least one ‘Nash equilibrium’, where neither player is motivated to change what they do—at least if they’re rational agents.

And this is how math works: by taking a simple concept and thinking about it very hard, over a long time, we can figure out things that are not at all obvious.

For game theory, the story goes much further than we went in this course. For starters, we should look at nonzero-sum games, and games with more than two players. John Nash showed these more general games still have Nash equilibria!

Then we should think about how to actually find these equilibria. Merely knowing that they exist is not good enough! For zero-sum games, finding the equilibria uses a subject called linear programming. This is a way to maximize a linear function given a bunch of linear constraints. It’s used all over the place—in planning, routing, scheduling, and so on.

Game theory is used a lot by economists, for example in studying competition between firms, and in setting up antitrust regulations. For that, try this book:

• Lynne Pepall, Dan Richards and George Norman, Industrial Organization: Contemporary Theory and Empirical Applications, Blackwell, 2008.

For these applications, we need to think about how people actually play games and make economic decisions. We aren’t always rational agents! So, psychologists, sociologists and economists do experiments to study what people actually do. The book above has a lot of case studies, and you can learn more here:

• Andrew Colman, Game Theory and its Applications in the Social and Biological Sciences, Routledge, London, 1982.

As this book title hints, we should also think about how game theory enters into biology. Evolution can be seen as a game where the winning genes reproduce and the losers don’t. But it’s not all about competition: there’s a lot of cooperation involved. Life is not a zero-sum game! Here’s a good introduction to some of the math:

• William H. Sandholm, Evolutionary game theory, 12 November 2007.

For more on the biology, get ahold of this classic text:

• John Maynard Smith, Evolution and the Theory of Games, Cambridge University Press, 1982.

And so on. We’ve just scratched the surface!

4 Responses to Game Theory (Part 20)

  1. Reeve says:

    This has been a fun class! Thanks for everything!

    Any chance you might continue this series casually every now and then, touching on more advanced and interesting topics like evolutionary and Bayesian game theory? I’d certainly read it, and I think many of your Google+ followers would enjoy it too!

    • John Baez says:

      I’m glad you liked the class!

      If you want to read my thoughts on evolutionary game theory, start with these posts in my Information Geometry series:

      Part 8 – information geometry and evolution: how natural selection resembles Bayesian inference, and how it’s related to relative entropy. (website version)

      Part 9 – information geometry and evolution: the replicator equation and the decline of entropy as a successful species takes over. (website version)

      Part 10 – information geometry and evolution: how entropy changes under the replicator equation. (website version)

      Part 11 – information geometry and evolution: the decline of relative information. (website version)

      Part 12 – information geometry and evolution: an introduction to evolutionary game theory. (website version)

      Part 13 – information geometry and evolution: the decline of relative information as a population approaches an evolutionarily stable state. (website version)

      I have a lot more I’d like to say about this, and a lot more I want to figure out, but this should keep you busy for a little while! Feel free to post comments and questions.

  2. You may be interested to know that the Japanese Mathematician (and Mathematical Economist) Nikaido sets out a proof of von Neumann’s minimax theorem in his 1960 text, in addition, discussing its relationship to the fix point theorems and Perron-Frobenius theorems:

    • Hukukane Nikaido, Introduction to Sets and Mappings in Modern Economics, North Holland, 1960.

    Cheers, James

    • John Baez says:

      Thanks! Now that you mention it, the Perron–Frobenius theorem is another result about linear algebra that’s sometimes proved with the help of the Brouwer fixed point theorem!

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,877 other followers