Followup To: An Introduction To Prisoner’s Dilemma
Part Of: Algorithmic Game Theory sequence
Content Summary: 500 words, 5 min read

Consider the following game:

Both spouses prefer the company of one another. In fact, they spent the evening together, they incur zero cost. However, if faced with a choice of waiting in an empty house vs. earning some overtime, they would prefer the latter twice as much.

We encode this game’s strategy-space as follows:

Recall our previous discussion of Pareto optimality and strategic dominance. There are myriad ways to think about games, why isolate those two properties, in particular? One reason to invent names is to construct a universal toolkit: non-trivial properties that exist in all games, and amenable to our analyses.

Pareto optimality makes an appearance in the above game (H, H). But strategic dominance does not. Take a moment to convince yourself this is true.

Since strategic dominance is too strong to be a universal property, we might relax it. What happens when we encode regret? That is, what does the Spousal Game look like after we consider cases when a player wishes she had made a different choice?

Arrows represent regret.

• In bottom-left cell, Spouse A wishes she had worked (purple arrow right) but Spouse B wishes he had gone home (orange arrow up).
• In top-right cell, we see an entirely symmetric expression of mutual regret.
• In the remaining cells, neither spouse can do better by individually changing their strategy.

Let us view Prisoner’s Dilemma from the same lens.

These arrows have a peculiar pattern. Why? Because of strategic dominance!

We can explain strategic dominance in terms of regret. That is, if a player’s regrets are all in the same direction, then that player is subject to strategic dominance.

Does regret belong in our universal toolbox? No. Regret by itself is rather uninteresting: every game with non-trivial utilities comprises myriad regrets.

We need a stronger property. How about games containing outcomes with no regret? Call such outcomes Nash equilibrium.

Does every game have Nash equilibria?

• Prisoner’s Dilemma has one: (D, D)
• Spousal Game has two: (H, H) and (W, W)

Perhaps no game fail to have this peculiar creature..

Conjecture 1: Every game with a finite number of players and strategies has at least one Nash equilibrium.

Time to search for counter-examples! Consider the game Rock-Paper-Scissors. Here’s how it looks to a game theorist:

Crucially, every node has at least one arrow leaving it. Rock/Paper/Scissors has no equilibrium! We have thus disproven Conjecture 1. What now?

In addition to the absence of Nash equilibria, this game is interesting in another sense. It turns out that having a deterministic strategy in Rock/Paper/Scissors is a bad idea.  In fact, machines can reliable beat people at Rock/Paper/Scissors by exploiting patterns in human gameplay.

What happens when we expand our notion of game to incorporate non-deterministic strategies. The best mixed strategy a player can adopt is [⅓ ⅓ ⅓]; that is where each choice is randomly selected with probability 0.33.

While hard to visualize, it is easy to intuitively grasp the existence of a new equilibrium. If each player adopts [⅓ ⅓ ⅓], neither will experience regret! Thus we can safely repair our Conjecture:

Conjecture 2. Every game with a finite number of players and strategies has at least one Nash equilibrium if mixed strategies are allowed.

It turns out that Conjecture 2 is entirely correct. In fact, its correctness is one of the most significant results in all of game theory.