博弈论导论 丛书.pdf

Game Theory Theodore L. Turocy Bernhard von Stengel Texas AM University London School of Economics CDAM Research Report LSE-CDAM-2001-09 October 8, 2001 Contents 1 What is game theory? 4 2 Definitions of games 6 3 Dominance 8 4 Nash equilibrium 12 5 Mixed strategies 17 6 Extensive games with perfect information 22 7 Extensive games with imperfect information 29 8 Zero-sum games and computation 33 9 Bidding in auctions 34 10 Further reading 38 This is the draft of an introductory survey of game theory, prepared for the Encyclopedia of Information Systems, Academic Press, to appear in 2002. 1 Glossary Backward induction Backward induction is a technique to solve a game of perfect information. It first consid- ers the moves that are the last in the game, and determines the best move for the player in each case. Then, taking these as given future actions, it proceeds backwards in time, again determining the best move for the respective player, until the beginning of the game is reached. Common knowledge A fact is common knowledge if all players know it, and know that they all know it, and so on. The structure of the game is often assumed to be common knowledge among the players.