Game Theory Tuesday: The Non-Mathematical Guide to Fixed Point Theorems and Proving Nash Equilibria Exist

Today, I present a brain teaser and some related trivia for you to talk about during your Thanksgiving celebration. And in the spirit of game theory, you can use the trivia to distract others as you grab more turkey.

Problem: The journey of the monk.

One morning at 6 am, a monk began climbing a tall mountain, which happened to only have one path to the top. He ascended the path at his leisure, taking some stops along the way. He reached the top at 8 pm.

The next morning at 6 am, the monk descended the mountain along the same path. He took several breaks along the way, and reached the bottom at 8 pm.

The amazing result: there is some spot on the path that the monk occupied at precisely the same time of day for both trips. Why is this?

This is true even if the monk took breaks to meditate, chatted it up with a fellow traveler, or if he took some time to massage his feet. You get the point: it really does not matter what he did during the trips going up or down.

Why is this true?

The problem is actually an illustration of the math behind game theory called fixed point theorems. The theorems are fundamental to game theory but unfortunately not easy to explain. Though, you’ll see me try throughout this article…

When you transform the monk problem into math notation (I’ll spare you the details), the solution is a direct implication of a fixed point theorem called the Intermediate Value Theorem.

But you don’t need to know math to solve the monk problem. Just do a thought experiment: superimpose the two trips into a single day.

That is, imagine instead that two monks are taking the journey on the same day, one climbing up and the other climbing down. Now it is clear that no matter how each monk takes the trip, there has to be some spot where they cross paths.

Now pretend those trips happened on two separate days and you have your answer–the monk is at the same spot on the path at precisely the same time of day for both trips.

Pretty cool, eh?

So now I try to describe a few more interesting illustrations of fixed point theorems as trivia:

Trivia 1: Mixing up soda

You are playing a prank on a friend by shaking up his soda in a can. You shook the can well enough that the soda will spray on your friend.

But no matter how well you shake it up, at least one point in the can was not moved: it ended up in the same spot as where it started.

This spot is a fixed point, and it must exist because of Brouwer’s fixed point theorem.

Trivia 2: Peaceful earth

No matter what the weather patterns are, there is at least one spot on earth the wind is not blowing.

The point where there is no wind blowing is a fixed point. This has to exist due to the interestingly named Hairy Ball Theorem.

Trivia 3: Most economic games have solutions

The most widely known solution concept is a Nash equilibrium. So I use the words “solution” and “Nash equilibrium” to mean the same thing.

Roughly speaking, a Nash equilibrium is a situation where no player can individually deviate profitably. That means each player is choosing the best strategy, given what others are doing. It is self-enforcing since no one can individually get out of it.

So you might look at a game and ask, does it have a Nash equilibrium?

Naively you could try to compute equilibriums. You might randomly pick a set of strategies for each player and see the outcome. From there, you check if any player can deviate profitably, and if so, change that strategy. Then you see if other players may react by changing their choices. When you iterate this optimization process, you might end up in a situation where no one wants to change. This is a Nash equilibrium.

In the rock-paper-scissors game, for instance, the Nash equilibrium involves players randomly picking each choice 1/3 of the time. If you favor rock more than 1/3 of the time, then your opponent can beat you more often than not by countering with paper.

When you are in a Nash equilibrium, you simply cannot optimize the choices by changing one person at a time. Thus, you have reached a set of strategies that is “fixed” under the optimization process. And speaking mathematically, this set of strategies is a fixed point.

If you followed all of that, congratulations. You know understand the logic in proving that Nash equilibriums exist for a variety of games.

John Nash was a bit more precise in his proof. He used math notation to describe the “optimization process” (known as a best response correspondence), the “sets of strategies” (known as strategy profiles), and the “fixed point” (he called it an equilibrium point, and we honor his work by calling it a Nash equilibrium). Incidentally, Nash relied on the Kakutani fixed point theorem.

There are some specifications on the strategy sets and utility functions, but that is a technical point I won’t go into now (like you have to allow mixed strategies).

But practically, the theorem is great since it tells me that the games I draw up for you must have solutions. I might not know the answer right away, but it has to exist!

Nash’s existence proof was not appreciated at the time of publication in 1950. The polymath John von Neumann is believed to have quipped, “That’s trivial, you know. That’s just a fixed point theorem.”

Just a fixed point theorem? Oh no, it’s some good trivia.