Date  Topic  Materials 
8/29  Course at a glance. What problems are we trying to solve? Example applications: game playing, trading agents, preference aggregation, elections, electronic marketplaces, resource allocation, routing.  Slides. 
8/31  Risk neutrality and risk aversion. Expected utility theory. Games in normal form. Dominance and iterated dominance. Computing dominated strategies.  Slides. Homework 1 out. SLB Appendices B and D (if you need them); Sections 3.1, 3.2, Subsection 3.3.3, Section 4.7. Paper on computing dominated strategies. (You can skip the part on Bayesian games.) 
9/5  Minimax strategies. Computing minimax strategies. Nash equilibrium. Computing Nash equilibria. Correlated equilibrium. Computing correlated equilibria.  Slides. SLB 3.3.1, 3.3.2, 3.3.5, 3.3.6, 4.1, 4.2.1, 4.2.4, 4.4, 4.5, 4.6, 4.8. Paper on computing Nash equilibria. (You only need to read the part concerning 2player games.) 
9/7  Games in extensive form. Backwards induction. Subgame perfect equilibrium. Imperfect information. Equilibrium refinements.  Slides. SLB Chapter 5; you can skip alphabeta, 5.2.3, and 5.2.4. 
9/11, 12pm, LSRC D344  Special lecture: Computing Kemeny and Slater rankings. (Vince is giving this talk on voting in the algorithms seminar and it lines up nicely with the course, so please try to attend it. The lecture on these topics that was planned for later in the course will probably be skipped.)  Slides. Kemeny paper, Slater paper. (Will not be covered in the midterm.) 
9/12  Preference aggregation/social choice. Voting rules. Desirable properties of voting rules. Arrow's impossibility theorem. MullerSatterthwaite impossibility theorem. Manipulation. GibbardSatterthwaite impossibility theorem. Singlepeaked preferences.  Slides. Quiz 1 bonus questions slides. SLB Chapter 7. Section on voting with some more voting rules. 
9/14  Bayesian games. Mechanism design. Incentive compatibility. Individual rationality. Revelation principle. Clarke mechanism. Groves mechanisms.  Homework 1 due. Homework 2 out. Slides. SLB 6.3, Chapter 8 (up to and including 8.7). Alternative resources with roughly the same content: Chapter on mechanism design + chapter on revelation principle. Parkes chapter on mechanism design. 
9/19  Mechanism design continued.  
9/21  Auctions. English, Japanese, Dutch, firstprice sealedbid, secondprice sealedbid (Vickrey). Revenue equivalence. Redistribution. Myerson's "optimal" auction. Reverse auctions. Exchanges. MyersonSatterthwaite impossibility theorem.  Slides. SLB 9.1, 9.2. Paper on redistribution. 
9/22, 1:302:30pm, LSRC D344  Special lecture: Common voting rules as maximum likelihood estimators. (Vince is giving this talk on voting in the DRIV seminar; it lines up nicely with the course and there may be some project ideas there, so please try to attend it.) 
Slides. Paper. (Will not be covered in the midterm.) 
9/26  Combinatorial auctions. Bidding languages. Winner determination. Generalized Vickrey auction. Combinatorial reverse auctions and exchanges.  Slides. SLB 9.3.1, 9.3.2, 9.3.3. Optional: Lehmann et al. chapter on winner determination. Sandholm chapter on optimal winner determination. 
9/28  Preference elicitation in voting and auctions. Iterative combinatorial auctions. Communication complexity. Restricted classes of valuations. 
Slides. Optional: Parkes chapter on iterative CAs. SandholmBoutilier chapter on preference elicitation in CAs. 
10/3  Preference elicitation continued. Review for midterm (bring questions!).  Project proposal (1+ pages) due. 
10/5  MIDTERM. Covers all material covered in class so far.  Copy of midterm. 
10/10  Fall break. No class.  
10/12  Midterm solutions. Concise representations of games. Congestion games. Potential games. Graphical games. Actiongraph games. MAIDs.  Homework 2 due. Slides. SLB 6.4, 6.5. Optional: Paper on actiongraph games. 
10/17  Repeated games. Folk theorem. Stochastic games.  Slides. SLB 6.1, 6.2. Optional: Paper on computing a Nash equilibrium in repeated games. Paper on stochastic games and learning. 
10/19  Repeated and stochastic games continued.  
10/24  Learning in games. Iterated best response. Fictitious play. Noregret algorithms. Targeted learning. Evolutionary game theory.  Slides. SLB 14.1, 14.2, 14.5, 14.6, 14.7.1, 14.7.2. 
10/26  Cooperative/coalitional game theory. Core. Nucleolus. Shapley value. Computing solutions.  Slides. SLB Chapter 11. 
10/31  No class.  
11/2  Collusion. Use of false names over the Internet.  Project progress report (~2 pages)
due. Homework 3 out. Slides. Optional: Paper on collusion in combinatorial auctions and exchanges. Paper on falsename bidding. Another paper on falsename bidding. Paper on collusion/false names in coalitional game theory. 
11/7  No class.  
11/9  Automated mechanism design.  Slides. Chapter on automated mechanism design, read up to and including 6.6. Optional: Remainder of the chapter. Paper on automatically creating multistage mechanisms. 
11/14  Algorithmic mechanism design. Approximately efficient truthful combinatorial auctions. Shortest paths. Minimizing makespan. Characterizing allocation rules that can be made incentive compatible. 
Slides. Optional: Paper on algorithmic mechanism design. Paper on computing Clarke payments for shortest paths. Paper on approximately efficient, incentive compatible combinatorial auctions. Paper on characterizing which allocation rules can be made incentive compatible. 
11/16  Computational hardness as a barrier against manipulation. Limitations. 
Slides. Optional: Paper on STV being hard to manipulate. Paper on using a preround to increase hardness. Papers 1 and 2 on hardness with few alternatives. Papers 1 and 2 on voting rules usually being easy to manipulate. 
11/20, 11:45am12:45pm, LSRC D106  Special lecture: Nicole Immorlica (Department Colloquium). Derandomizing auctions that are approximately optimal in the worst case.  Paper. 
11/21 
Wrapping up. Student project presentations: Mason: Selectively Processing Surveillance Video Using GameTheoretic Reasoning Mingyu: A Family of Strategyproof Redistribution Mechanisms for VCG Payments 
Homework 3 due. Optional: Paper on redistribution (again). 
11/23  Thanksgiving break. No class.  
11/28  Student project presentations: Susanna: Manipulating with Incomplete Information Neeti: Applying Scoring Rules to Integrated Classifiers Joe: Partially Solving Games with Bounds on Utilities 

11/30  Student project presentations: Rolando: Automated Mechanism Design with Collusion Handling Zheng: Voting as MLE with Gaussian Noise Model Mac: Can you trust eBay? The Computational Complexity of Auction Control 
Final project writeup due. 