Game Theory 101: Extensive Form & Backwards Induction

Up until now, the previous posts of the Game Theory 101 series have discussed "normal-form" games, which can be analysed via the form of one or multiple decision matrices. However, a normal-form representation may be insufficient to represent all facets of a game or certain types of games, such as "turns" in a sequential (turn-based) game.

Extensive Form

First, let us look at how the extensive form representation of a game looks like. It can be represented via a game tree, like so:

In the above game, each player takes turn playing two strategies, $A$ or $B$. At the end of the game (i.e. after Player 1's second turn), the utility/payoff $U_p$ for each player is calculated in the following manner:

where $U_p$ is the multiplicity of the player $p$'s last played strategy $s$ in the multiset $G$ (a set that allows duplicates) of all strategies played in the game.

In other words, the count of the player's last played strategy in the mutiset of all played strategies becomes the player's payoff.

One might reason that the branching "decisions" of each player in the game tree naturally represents the flow of time, i.e. the turn-based aspect of the game; while this is not wrong, it does not perfectly capture the nuances of what the extensive form represents that the normal form cannot.

Rock Paper Scissors

Let us understand the key difference between a simultaneous game and a turn-based game with an example: Rock Paper Scissors. The game matrix for the above example looks like this:

It is fairly trivial, albeit not necessarily rigourous, for us to say that this is a simultaneous game. After all, both players are making their moves at the same time, aren't they?

In contrast, consider a different game:

In this game, we can also say there is a second-mover advantage since Player 2 can simply play the best response strategy to Player 1's choice. We can also trivially (albeit, once again, non-rigourously) say that this is a turn-based game; after all, Player 2 makes his/her move only after Player 1, and not at the same time, right?

The extensive-form representation of the above game looks like this:

The two simultaneous and turn-based games above seem to suggest that time is an essential component that differentiates whether a game is simultaneous or turn-based, based on our non-rigourous observation. But is that truly the case?

Now consider a third modification of the game, where we concatenate a new element to our turn-based game in which players will have their eyes closed/open:

Is this a turn-based game or a simultaneous game?

There seems to be something happening here that might not make the answer so obvious at first thought. Previously, we have been using the concept of time to judge that our games are simultaneous or turn-based.

If we judge this game purely based on the concept of time, this would be a turn-based game; after all, the players are making their moves at different points in time, i.e. taking turns to make their move. However, what differentiates this game from the previous turn-based game is that there is no second-mover advantage; Player 2's eyes are closed when Player 1 makes his move!

Both parties only know the outcome of the game when they open their eyes after having made their moves. That makes this a simultaneous game! Which brings us to a crucial concept:

What differentiates a simultaneous game from a turn-based game is not time, but information.

Information in Extensive Form Games

We have seen that turn-based games can be represented as a tree in extensive form, but what about simultaneous games, where information is not known ahead of time? How does it look like in the extensive form? We make use of a notation called information sets to represent this in our extensive form game trees.

For example, consider our simultaneous Rock, Paper Scissors game:

Our information set represents a set of nodes (actionable by the same player) where each node is indistinguishable from one another to that player. In this case, all 3 nodes will be indistinguishable to Player 2, which suggests that Player 1's action is not known, nor is the outcome known when choosing a particular action. Thus, it is not known which of the payoffs (0,0), (1,-1), or (-1,1) we obtain when choosing strategy $R$ (likewise for $P$ and $S$).

More formally, we can define an Information Set of player $i$ as the collection of $i$'s nodes among which $i$ cannot distinguish apart, i.e.:

• All nodes in the set belong to the same player $i$
• The number of available moves must be the same for every node in the information set (otherwise, they are distinguishable)
• No node in the information set is the predecessor of another node in the set

In such a simultaneous game scenario with imperfect information, we can now resolve the best strategy players can take by using existing techniques that we have discussed for simultaneous games in a previous post.

Backwards Induction

Backwards Induction is a powerful technique for solving extensive form games (whether with perfect or imperfect information) that gives us the best strategy of each player at each decision point. One particular way that I like to understand backwards induction is the concept of foresight; if you had knowledge of what will happen in the future beforehand, this knowledge can assist in making a decision at the present.

Given the extensive form of a particular game, we can figure out the optimal actions by working backwards from the end of the game to a particular decision-making point to get the optimal decision to make. Let's use this approach on the very first example of this post:

By starting from the end of the game, each player makes an optimal decision based on the payoff that they get, and subsequent (earlier) decisions will be based on considering these optimal decisions that have been made in the future. This way, both Players A and B can ensure that they can reach the highest payoff possible (3,3).

Now let us consider a different game that is scenario based to highlight the power of backwards induction. Suppose we have 6 rational players, $A, B, C, D, E, F$, and they are trying to decide how to split 10 coins between themselves.

They have decided to take a democratic approach by taking a vote. All coins must be involved in the split. First, player $A$ will propose on how the coins will be split, and all 6 players take a vote; if more than half of the votes are for the proposal, the game ends and each player's payoff is as outlined in the proposal. Otherwise, $A$ is kicked out of the game with 0 coins, and $B$ will put forth a new proposal, which will be voted on, and so forth. If a player is indifferent, he will vote no. How does the extensive form of this game look like?

The gigantic extensive form game tree of our coin splitting game. Zoom in!
To have a sense of exactly how large this game tree is, let us determine just how many branches (possible proposals) are there at each player, i.e. we wish to answer the question: How many ways to split $n$ coins among $k$ players?

This can be answered with the help of the Stars and Bars technique in combinatorics, which works out to:

So for our first proposal for $A$, we are looking at a total of:

If we tried to consider a "forward" approach starting from all possible scenarios of A's proposals, without any additional computation support, it would be quite unfeasible for a human brain to keep track of everything. However, when we consider a backwards induction approach, the problem becomes manageable.

First, consider the last proposal scenario of the game:

• Only one player, $F$ is left
• There are ${10\choose0}=1$ way of splitting the coins: All coins to go to F.

It doesn't matter what kind of proposals or voting process led us to this scenario, but the fact of the matter is, if we reach the future where only F is left, the payoff will be (0,0,0,0,0,10) as F will rationally not vote against his own proposal, and this future is now locked in.

Now, we take a step backwards and consider the second-last proposal scenario of the game:

• $E$ must make the proposal, and both $E$ and $F$ must agree (> half of the votes condition) for it to pass
• In order for $F$ to rationally agree to the vote, the value of payoff $f$ in the proposal must be better than the outcome when this proposal fails and we reach the final proposal scenario.

It doesn't matter what kind of combination of payoffs $e$ and $f$ that $E$ tries to make in his proposal; we know that when thsi proposal fails, in the final proposal, $F$ gets all the coins with the outcome of (0,0,0,0,0,10).

$\textbf{E}$ is helpless. The best proposal he can make that $F$ will be indifferent to (and perhaps accept) is (0,0,0,0,0,10). $E$ still gets nothing. This future is locked in.

Now we move one more step backwards in time:

Now things get a little more interesting; we know that if this proposal fails, the scenario will move on to $E$'s proposal, where $E$ gets nothing and $F$ gets all the coins. There are a few considerations $D$ can now take into account:

• For this vote to pass, $D$ needs 1 more agree vote apart from himself (2/3)
• Since $E$ will get nothing if this vote fails, $D$ can incentivize $E$ with 1 coin. Rationally, $E$ should accept this offer.
• $F$ cannot be incentivized to agree without handing him all the coins, as this proposal's failure will result in (0,0,0,0,0,10) outcome.

Therefore, the rational proposal for $D$ such that he gets the most payoff while ensuring the proposal will pass is (0,0,0,9,1,0). This future is locked in.

Now we take one more step backwards in time:

You probably have a good idea of how this proposal will now play out. We can consider the future that has been locked in from our previous analysis, i.e. what would happen if this vote fails and moves to the next scenario, and what that outcome would be. In $C$'s case, we consider the outcome of (0,0,0,9,1,0) in the next proposal.

• For this proposal to pass, we need 3/4 agree votes.
• $F$ is now guaranteed to get 0 if this vote fails and $D$ proposes in the next round. $C$ can incentivize him with 1 coin.
• Considering between who to incentivize between $D$ and $E$ for this proposal, incentivizing $D$ would require 10 coins while $E$ only requires 2 coins. We cannot offer $E$ 1 coin as he will be indifferent, and will defaut to a no vote.
• The rest of the coins can be taken by $C$ himself.

Final outcome: (0,0,7,0,2,1), this future is now locked in.

Moving backwards in time:

Likewise, with similar consideration on the locked in future when the proposal fails, $B$ should make the proposal (0,7,0,1,0,2), and the future will now be locked in. I will leave the details as an exercise for the reader.

Moving backwards in time:

Arriving at the start of the game, we now know that using backwards induction, we can predict the decisions that each rational player will make at each decision point, and we will make our proposal according to the results in the future. Player $A$'s proposal and the outcome of the game is:

Closing Thoughts

I hope the above example has given you some good insights on the power of backwards induction; in some cases, such as the game above, we do not even need to consider all possibilities (proposals) of the game, but rather the logic of backwards induction helps us to prune down the cases to a manageable amount.

There are also cases where parts of the game during backwards induction may have imperfect information (information sets), and they can be solved using techniques highlighted in previous posts such as finding the Nash Equilibrium.

This might be the last of Game Theory posts for now; my summer at SNU learning Game Theory was almost 2 years ago, and I remember being so vividly captivated by these new concepts as a student.

I started these posts, in a way, to remember and commemorate that joy of learning; whoever you may be, and whatever phase of life and learning you may be at, may the winds ever be in favour of your sails.