display | more...

In the field of game theory, backwards induction is a method used to determine optimal strategies in a sequential game. A sequential game consists of players taking turns with their actions instead of playing them simultaneously as they would in a standard prisoner’s dilemma. Building on the assumption that the players have perfect information and are behaving rationally (that is, they seek to maximize their own personal benefit), it is possible to use backwards induction to determine the optimal strategies that the rational players will use. If the players can logically determine all possible outcomes of the game (and it’s assumed they can because they have perfect information about themselves and their opponents), they can work backwards to arrive at an optimal solution.

For example, suppose that you are running a mom-and-pop grocery store and you get word that the Walton family wants to open up a new Wal-mart across the street. You have sufficient political clout in the community to attempt to block their construction, but mustering your resources will cost you a significant amount of money and you won’t do much to Wal-mart except increase their construction costs. Wal-mart then has the option to build their new store, or to back off and leave your business in peace. Assume the game is structured as follows:

Your business currently earns $500. If Wal-Mart builds, they’ll poach your customers and take $400 from you. Blocking their construction will cost you $200, but it’ll add $200 to their construction costs.

There are four possible outcomes to the game:

  1. You don’t block the construction. Wal-Mart doesn’t build. (You earn $500, Wal-Mart earns nothing)
  2. You don’t block the construction. Wal-Mart builds their store. (You earn $100, Wal-Mart earns $400)
  3. You block the construction. Wal-Mart doesn’t build. (You earn $300, Wal-Mart earns nothing)
  4. You block the construction. Wal-Mart builds anyway. (You lose $100, Wal-Mart earns $200)

Wal-Mart’s payoffs in the 2nd round depend on your actions in the first, so we start by looking at Wal-Mart’s options. If you block the construction, Wal-Mart has a choice between earning nothing or earning $200 by building the store; they’d clearly choose to build, given a choice between those two options. Similarly, if you don’t block the construction, Wal-Mart has a choice between earning nothing or earning $400. Thus the only two rational outcomes in the 2nd round are B and D. Moving backwards to the first round, given a choice between the $100 earnings in B and the $100 loss in D (since you can predict that Wal-Mart will build during the 2nd round regardless of what you do), your only rational option is to save your money and just let Wal-Mart poach your customers. Tough luck.

The structure of the game can be expanded to include more players, options, or rounds of action. Based on the structuring of the payoffs, it is also possible that more than one optimal strategy exists. Theoretically, it’s possible to determine optimal strategies for extremely complex games (like Go, diplomacy, love, or chess) by working backwards from the possible end-game situations. In the example of Go, since there are approximately 2.0816×10^170 possible endgame scenarios on a standard 19x19 board, using backwards induction to “solve” the game of Go is not a feat most people are capable of accomplishing, though there’s probably a Nobel Prize waiting for anyone who can.

Log in or register to write something here or to contact authors.