Game theory is a branch of mathematics that deals with decision-making in strategic situations. In sequential games, players make decisions one after another, taking into account the decisions made by the other players. The goal is to find a strategy that maximizes your outcome, given the actions of your opponents.
There are several methods for solving sequential games, but one of the most popular is backward induction. This technique involves working backwards from the end of the game, considering each player’s optimal strategy at each step.
To illustrate this approach, let’s consider a simple example: a two-player game where each player can choose to either cooperate or defect. If both players cooperate, they each receive a reward of 3.
If both players defect, they each receive a reward of 1. If one player cooperates and the other defects, the defector receives a reward of 5 and the cooperator receives a reward of 0.
To solve this game using backward induction, we start at the end: if both players are rational and know each other’s preferences, they will both defect since this guarantees them at least 1 point. Therefore, we can eliminate the (Cooperate, Cooperate) outcome from consideration.
Next, we consider what Player 2 would do if Player 1 were to cooperate. In this case, Player 2 would prefer to defect (since it yields him more points), so we can eliminate (Cooperate, Defect) from consideration as well.
Finally, we are left with only one outcome: (Defect, Cooperate). Both players know that if they were to change their strategy unilaterally at this point they would be worse off; therefore this is their best response and it represents our solution.
We can represent this solution as a game tree:
Game Tree for Two-Player Game
- Player 1
- Player 2: Cooperate (3,3)
- Player 2: Defect (0,5)
- Player 2: Cooperate (5,0)
- Player 2: Defect (1,1)
In this game tree, each node represents a decision point for one of the players. The outcomes are represented by the edges connecting the nodes; for example, the edge from (Cooperate, Cooperate) to (3,3) indicates that both players receive a reward of 3 in that outcome.
Overall, backward induction is a powerful and widely-used technique for solving sequential games. By working backwards from the end of the game and considering each player’s optimal strategy at each step, we can find a solution that maximizes our outcome given our opponents’ actions.