Tentative list of topics to coverIntroduction. Normal form, pure strategies, and mixed strategies. Utilities/payoffs, and their relation to rational preferences. Classifications of games based on their payoffs (zero-sum, non-zero-sum, symmetric, etc.). Analyzing normal-form games. Definitions of several game-theoretic solution concepts, and algorithms for computing them. Topics will include Pareto optimality, best responses, Nash equilibria, maximin and minimax strategies, the Minimax theorem, dominance, elimination of dominated strategies, dominant strategy equilibria, and rationalizability. Extensive-form games. Definitions of extensive form and subgame-perfect equilibria. Algorithms for backward induction, minimax search, alpha-beta pruning, and bounded-depth search with static evaluation functions. Lookahead pathology. Games in which deeper game-tree saerch hurts instead of helping.
Relationships to characteristics of the game tree.
Imperfect-information games. Information sets, behavioral strategies versus mixed strategies, and game-tree search algorithms for imperfect-information games. Repeated games. Finitely and infinitely repeated games, and strategies and algorithms for such games. Stochastic games. Markov games, reward functions, strategies, and equilibria. Evolutionary simulation games, imitation dynamics, algorithmic implementations. Incomplete-information games. Comparison with imperfect information, relation to uncertainty about payoffs. Auctions, truthfulness, definition of a VCG mechanism and its computational issues. Price of anarchy. Definitions of price of anarchy and price of stability, relation to optimization problems. Coalitional games. Classes of coalitional games, payoff sets, imputation sets, computing Shapley values. |