CMSC 498T, Game Theory

Tentative list of topics to cover

Introduction. 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.).
Examples: the prisoner's dilemma, rock-paper-scissors, which side of the road, matching pennies, lotteries, risk preferences, penalty kicks in soccer.

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.
Examples: the prisoner's dilemma, battle of the sexes, penalty kicks in soccer, morra, the p-beauty contest, and the hawk-dove game.

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.
Examples: chess, checkers, tic-tac-toe, and go.

Lookahead pathology. Games in which deeper game-tree saerch hurts instead of helping. Relationships to characteristics of the game tree.
Examples: P-games, N-games, chess, and kalah.

Imperfect-information games. Information sets, behavioral strategies versus mixed strategies, and game-tree search algorithms for imperfect-information games.
Examples: poker, bridge, kriegspiel chess, and others.

Repeated games. Finitely and infinitely repeated games, and strategies and algorithms for such games.
Examples: rock-paper-scissors, the Iterated Prisoner's Dilemma (with and without noise), and the infantry trenches in World War I.

Stochastic games. Markov games, reward functions, strategies, and equilibria. Evolutionary simulation games, imitation dynamics, algorithmic implementations.
Examples: lottery games, evolution of state-dependent risk preferences.

Incomplete-information games. Comparison with imperfect information, relation to uncertainty about payoffs. Auctions, truthfulness, definition of a VCG mechanism and its computational issues.
Examples: English, Dutch, and sealed-bid auctions, second-price auctions.

Price of anarchy. Definitions of price of anarchy and price of stability, relation to optimization problems.
Examples: Braess’s paradox (road network design), others.

Coalitional games. Classes of coalitional games, payoff sets, imputation sets, computing Shapley values.
Examples: voting games, probably others.