Department of Electrical and Computer Engineering

ECE 586BH: SPRING 2013
Topics in Decision and Control: Static and Dynamic Game Theory

Problem set 1 Solutions
Classification of evolutionary states
Problem set 2 Solutions
Problem set 3 Solutions
Problem set 4 Solutions
Problem set 5 Solutions
Problem set 6 Solutions
Exam 1 Monday, April 1, 7:00-8:30 p.m. Room 168 Everitt Lab
You may bring two sheets of notes, two-sided, to consult during the exam.
Exam 1 Solutions
Exam 2 Wednesday, May 1, 7:00-8:30 p.m. Room 168 Everitt Lab Exam topics
Exam 2 Solutions
You may bring three sheets of notes, two-sided, to consult during the exam.
The fifteen minute presentations are scheduled for Wednesday, May 8, 7-10 p.m. in Room 141 CSL (on first floor).
If you don't have access to CSL, please meet at the main entrance on the west side of the building at five minutes to 7 pm and we'll let you in.
The papers are due Friday, May 10, by 5 p.m. and can be turned in by sliding under my CSL office door, Room 105. (See guidelines for projects below.)

Lectures 1-5 Static games: dominated strategies, dominant strategies, Nash equilibrium, existence, zero sum two player games
Lectures 6-9 uniqueness condition, Cournot game, fictitious play, evolution as a game, ESS and replicator dynamics
Lectures 10-13 potential games, forecasting to minimize regret, Blackwell approachability theorem
Lectures 14-17 Extensive form games with imperfect information: normal representation, behavioral strategies, subgame perfect equilibria, sequential equilibria
Lectures 18-21 Multistage games with observed actions, feasibility theorems for repeated games, Bayesian games, VCG mechanism
Lectures 21-24 Revenue optimal seller mechanisms for independent private valuations, auctions with interdependent values
Lectures 25-27 Coalitional games with transferable payments: Core, Bondareva-Shapely theorem, replicated games, markets with transferable payment, Shapley value

Description: Game theory is the theory of decision problems with multiple decision makers, often with conflicting objectives. The theory seeks to describe the actions of decision makers in various settings, and, in some cases, to aid in the design of incentives to steer the collective actions towards specified objectives. The course focuses on fundamental theory, with applications to a broad range of problems arising in networks, such as resource allocation, incentives for investment, and pricing.

Grading scheme: Homework (40%), two ninety minute midterms (20% each), project (20%).

Prerequisites: Familiarity with dynamic systems (at the level of ECE 515), background in probability theory (at the level of ECE 313, and preferably ECE 534), familiarity with the basics of linear and nonlinear programming (at the level of ECE 490).

Credit: 4 graduate hours

Assigned Reading: There will be no required text, but there will be selected readings from books, journal papers, and other information availalble online.

Meeting times: 12:30-1:50 p.m. TuTh in 106B3 Engineering Hall

Instructor: Professor Bruce Hajek

Office hours: Wednesday and Friday,1-2 p.m. in Room 105 CSL

Preliminary listing of tentative summary of topics:

  • I. Static games of complete information
    • Dominant strategies, iterated elimination of dominated strategies, mixed strategies, Nash equilibrium, saddle-point theory,
    • Conditions for existence, and conditions for uniqueness, of Nash equilibrium
    • Correlated equilibria
    • Fictitious play and convergence results
    • Evolutionarily stable strategies (ESS) and evolutionarily stable states of replicator dynamics
    • Trembling hand equilibrium
    • Blackwell's approachability theorem and learning
  • II. Dynamic games of complete information
    • Extensive form games with imperfect information: normal form, subgame perfect equilibrium, sequential equilibria
    • Multistage games with observed actions: one step deviation principle
    • Repeated games: trigger strategies, feasibility theorems (aka folk theorems)
  • III. Static games of incomplete information
    • Bayes-Nash equilibrium
  • IV. Mechanism design and the theory of auctions
    • Vikrey second price auction and its generalization (VCG mechanism)
    • Revenue optimal auctions (direct revelation principle, revenue equivalence, virtual valuations (Myerson theory)
    • Equilbrium bidding strategies and revenue ordering for second price and ascending auctions with correlated private information (Milgrom and Weber theory)
  • V. Coalitions in cooperative games
    • Core, exchange economies with transferrable payments, Shapley value

About the project: For the project you are to choose a topic related to the course content and understand and critically evaluate two or three major papers in that area. Then demonstrate knowledge of the papers by working an example based on a paper or possibly extending the theory of a paper. You will need to write a project report of five to ten pages in length, and prepare a fifteen minute presentation.

Additional policy: Collaboration on the homework is permitted, however each student must write and submit independent solutions. Homework is due within the first 5 minutes of the class period on the due date. No late homework will be accepted (unless an extension is granted in advance by the instructor).

You may bring two sheets of notes to the first exam and three sheets of notes to the second exam. You may use both sides of the sheets, with font size 10 or larger printing (or similar handwriting size). The examinations are closed book otherwise. Calculators, laptop computers, tables of integrals, etc. are not permitted.