Zermelo's Theorem

In game theory, we separate games into two different categories: normal form games (think payoff matrices), and extended form games. Extended form games consist of players moving sequentially (one after the other). This changes the information given to each player, as the players that move later on will have knowledge about how the players before have moved. This is why extended form games are also called sequential games. Today I will focus on a special type of sequential games: chiefly those will only two players. Below is a sequential game with two players summarized as a tree diagram:

A                B

o----T-----o-----L-------o (3,4)

|                 |

|                 ------R------o (2,2)

-----D-----o-----L------o (1,2 )

                  |

                  --------R----o (4,3) 

Where payoffs are written in the form of (Payoff A, Payoff B). Each "o" is a node. 

In this game, A moves first, with a choice of either top (T) or down (D). B then follows, and moves with the choices Left (L) or Right (R), given the information about how A has moved. The correct way to analyze this game is to use backward induction. Basically, we start from the end of the tree. Given that A has chosen T, B will ALWAYS choose L because a payoff of 4 is greater than a payoff of 2. Given that A has chosen down, B will ALWAYS choose R because a payoff of 3 is greater than a payoff of 2. Given this information, we can basically simplify our tree diagram to the following: 

A                B

o----T-----o (3,4)

|                 

|                

-----D-----o (4,3) 

Now, given this choice, it is obvious that A will choose down (D), because a payoff of 4 is greater than a payoff of 3. Therefore, the Subgame Perfect Nash Equilibrium is (D, R). This is the process of backward induction: we start from the end of the tree and move backwards to find our equilibrium. Because the topic is rather extensive (no pun intended), if you'd like to find out more on this subject, please see the following lecture: Sequential Games Lecture.

Now, let's see a game that's a bit more complicated (credit to xkcd)... 

So as you can see, tic tac toe is just a two player sequential game. We can turn this diagram into a tree diagram and use backward induction to find out the Subgame Perfect Nash Equilibrium for this game (hint: the  equilibrium is a tie). But as I'm sure you'll find out very quickly, drawing the tree out becomes very tedious (which is why most analysis involves computers now). 

Now, I'd like to introduce the concept known as "Zermelo's Theorem." Basically, it states that in a given game with 2 players, perfect information, finite nodes, and 3 outcomes (1, 0, and -1 for Win, Tie, and Lose), one of the three things below will happen: 

1. Player 1 can force a win

2. Player 1 can force a tie

3. Player 2 can force a win

This may sound obvious and stupid at first, but think about the applications. When applied to chess, it states that there is a solution to chess. One player can force either a win or tie on the other players. We could draw a very large extended tree diagram of every possible move of chess and use backward induction to find the Subgame Perfect Nash Equilibrium. As I'm sure you've noticed, this is a considerable task due to the ridiculously large permutation of moves available. This is why the solution to chess has not yet been found (but just know that it does indeed exist!).