CMSC 828D, Introduction to Game Theory

Fall 2010

Lecture slides

I'll update these as we go along.

1. Introduction (Chapter 1)

  • Normal form, pure strategies, and mixed strategies.
  • Utilities/payoffs, relation to rational preferences, human risk preferences.
  • Payoff-based classifications of games (zero-sum, non-zero-sum, symmetric, etc.)
  • Many examples.

2. Analyzing normal-form games (Chapter 2)

  • Pareto optimality, best responses, Nash equilibria,
  • Examples: the Prisoner's Dilemma, Battle of the Sexes, penalty kicks in soccer, Braess' Paradox (road network design), and others.

3. More about normal-form games (Chapter 3)

  • Maximin and minimax strategies, Minimax theorem
  • Dominance, elimination of dominated strategies, dominant strategy equilibria
  • Rationalizability
  • Correlated equilibria, convex combinations
  • Trembling-hand perfect equilibria, epsilon-Nash equilibria
  • Evolutionary stability
  • Examples: Battle of the Sexes, Morra, Prisoner's Dilemma, p-beauty contest, Hawk-Dove game

4a. Extensive-form games (Chapter 4)

  • Extensive form, subgame-perfect equilibria, and backward induction
  • Examples: the Centipede Game, and others

4b. Game-tree search (not in the book)

  • Minimax search, alpha-beta pruning, bounded-depth search, static evaluation functions.
  • Enhancements (node ordering, quiescence search, transposition tables, etc.)
  • Monte Carlo rollouts
  • Examples: chess, checkers, tic-tac-toe, and go

4c. Lookahead pathology (not in the book)

  • Games in which deeper game-tree saerch produces worse decisions
  • Relationships to characteristics of the game tree
  • Examples: P-games, N-games, chess, and kalah

Homework assignment for Lectures 4a, 4b, and 4c.

Review for the midterm exam

5. Imperfect-information games (Chapter 5)

  • Information sets, sequential equilibria, behavioral strategies versus mixed strategies
  • Imperfect-information game-tree search, opponent modeling
  • Examples: bridge, poker, kriegspiel chess, and several others

6a. Repeated games (Chapter 6, sections 1 and 2)

  • Finitely and infinitely repeated games, strategies for such games
  • Differences between theoretical predictions and empirical results
  • Opponent modeling and noise filtering
  • Examples: Roshambo, the Iterated Prisoner's Dilemma (with and without noise), and the infantry trenches in World War I

6b. Stochastic games (Chapter 6, section 3)

  • Markov games, reward functions, strategies, and equilibria
  • Evolutionary simulation games, imitation dynamics
  • State-dependent risk preferences
  • Examples will include Backgammon, Cultaptation, lottery games, and evolution of state-dependent risk preferences

Homework assignment for Lectures 6a and 6b

7a. Incomplete-information games (Chapter 7)

  • Comparison with imperfect information
  • Relation to uncertainty about payoffs
  • Bayesian games, extensive games with chance moves, and Bayes-Nash equilibria
  • English, Dutch, and sealed-bid auctions
  • Many examples

Homework assignment for Lecture 7

7b. Cultaptation

8. Coalitional games (Chapter 8)

  • Classes of coalitional games (superadditive, additive, convex, simple, etc.)
  • Payoff sets, imputation sets, Shapley value, core, stability
  • Examples: voting games, probably others.

Review for the final exam

Schedule for the rest of the semester

  • Nov 11 - Homework 6, start Chapter 8
  • Nov 16 - Homework 7, finish Chapter 8
  • Nov 18 - ?
  • Nov 23 - Homework 8, review
  • Nov 25 - no class (Thanksgiving)
  • Nov 30 - term-project presentations
  • Dec 2 - term-project presentations
  • Dec 7 - review
  • Dec 9 - lecture by Inon Zuckerman

Term projects

Private materials

Some proofs of the Minimax Theorem

Syllabus

This course will provide a comprehensive introduction to game theory. It will count as a core course for the Computer Science PhD and MS requirements.

Game theory is about interactions among agents (either human or computerized) that each have their own objectives and preferences -- which may differ from the objectives and preferences of other agents. Game theory has applications in fields ranging from economics and evolutionary biology to engineering and computer science. Some examples of computer science applications include computer networking, e-commerce, and computer game-playing.

Location: 1122 CSIC

Time: Tuesday/Thursday, 3:30–4:45pm

Instructor: Dana Nau

  • Office: Room 3241 AVW
  • Office hours: after class until about 5:30pm; other times by appointment
  • Telephone: 301-405-2684
  • Email: nau & cs.umd.edu     (change & to @)

Class page: follow the link my home page or from the CS Department's list of class pages.

Discussion forum: web site and RSS feed

  • That's where I'll post announcements to the class.
  • Consider posting your questions and comments there, instead of emailing them to me.

Textbook: Leyton-Brown and Shoham, Essentials of Game Theory. Morgan & Claypool, 2008.

I'll make additional resources available online.

Topics to be covered

  • In the left-hand column are a preliminary list of topics, and preliminary versions of the lecture slides.
  • I'll update both of those as we go along.

Workload

Homework: I'll assign several sets of homework problems, but won't grade them. About a week after each assignment, I'll discuss the answers in class.

Term projects: Each of you will need to do a term project. It will be like a miniature version of the research projects that most of you will need to do repeatedly throughout your career. It will include the following (the dates are tentative):

  • a written proposal, due Oct 1;
  • an in-class presentation of your proposal, during Oct 5–12;
  • a written report on the results of your project, due Nov 27 (or for 10% off, Nov 29);
  • an in-class presentation of your report, during Nov 30–Dec 7.

I haven't yet decided whether the term projects will be done individually or by small groups; this will depend partly on the class size.

Exams: There will be two exams:

  • I've tentatively scheduled the midterm exam for Tuesday, October 19.
  • According to the university exam schedule, the final exam will be on Saturday, December 18, at 10:30am.
  • Both exams will be open book and open notes. A few days before each exam, I'll do an in-class review of the material we've covered, to help you prepare for the exam.

Grading

The term project will count for 30% of your grade. The two exams will count for 70% of your grade. When you take the final exam, I'll let you choose among any of the following:

  • 20% for the midterm and 50% for the final;
  • 30% for the midterm and 40% for the final (roughly proportional to the length of each exam);
  • 40% for the midterm and 30% for the final.

Web Accessibility