Essentials of Game Theory: A Concise, Multidisciplinary Introduction by Kevin Leyton-Brown & Yoav Shoham

Author:Kevin Leyton-Brown & Yoav Shoham
Language: eng
Format: epub
Publisher: Morgan & Claypool Publishers
Published: 2012-07-14T16:00:00+00:00

FIGURE 4.6: Procedure for finding the value of a sample (subgame-perfect) Nash equilibrium of a perfect-information extensive-form game.

In general in this booklet we do not address computational issues, so this example could be misleading without additional explanation. While the procedure demonstrates that in principle a sample SPE is effectively computable, in practice many game trees are not enumerated in advance and are hence unavailable for backward induction. For example, the extensive-form representation of chess has around 10150 nodes, which is vastly too large to represent explicitly.

We note that BACKWARDINDUCTION has another name in the two-player, zero-sum context: the minimax algorithm. Recall that in such games, only a single payoff number is required to characterize any outcome. Player 1 wants to maximize this number, while player 2 wants to minimize it. In this context BACKWARDINDUCTION can be understood as propagating these single payoff numbers from the root of the tree up to the root. Each decision node for player 1 is labeled with the maximum of the labels of its child nodes (representing the fact that player 1 would choose the corresponding action), and each decision node for player 2 is labeled with the minimum of that node’s children’s labels. The label on the root node is the value of the game: player 1’s payoff in equilibrium.

As we said, real-world games—even zero-sum ones, such as chess—cannot be represented explicitly. Such games require the gradual development of the tree, and its heuristic search. At least in the context of zero-sum games, considerable effort has gone into such search algorithms. The best-known one, ALPHABETAPRUNING, is a heuristic version of the minimax algorithm.

Despite the fact that strong arguments can be made in its favor, the concept of backward induction is not without controversy. To see why this is, consider the well-known Centipede game, depicted in Figure 4.7. (The game starts at the node at the upper left.) In this game two players alternate in making decisions, at each turn choosing between going “down” and ending the game or going “across” and continuing it (except at the last node where going “across” also ends the game). The payoffs are constructed in such a way that the only SPE is for each player to always choose to go down. So see why, consider the last choice. Clearly at that point the best choice for the player is to go down. Since this is the case, going down is also the best choice for the other player in the previous choice point. By induction the same argument holds for all choice points.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.