Date  Topic  Materials  
8/28  Course at a glance.  Slides: ppt, pdf.  
Part 0: Basic techniques from computer science.  
8/30, 9/4  Linear programming. (Mixed) integer linear programming.  Slides: ppt, pdf. Example files: class_example.lp, class_example2.lp, class_example3.lp, class_example4.lp, knapsack.lp, knapsack.mod, cell.lp, cell.mod, hotdog.mod, sudoku.mod. SLB Appendices A, B. Programming assignment 1 out (due 9/11). Guide to the modeling language. 

9/6  Computational problems. Algorithms. Runtime of algorithms. Easy and hard problems.  Slides: ppt, pdf. Sorting algorithms spreadsheet. Example files: set_cover.mod, set_cover2.mod, matching.mod. 

Part 1: Expressive marketplaces.  
9/11, 9/13, 9/18  Singleitem auctions. Combinatorial auctions. Bidding languages. Winner determination problem. Variants (reverse auctions, exchanges). 
Slides: ppt, pdf. SLB 10 introduction, 10.1.1, 10.3 introduction, 10.3.2, 10.3.3. 

9/18, 9/20  Expressive financial securities. 
Slides: ppt, pdf. SLB 10.4.2. Optional: Paper 1, paper 2. 

9/20, 9/25  Barter exchanges/matching markets. Kidney exchange. 
Slides: ppt, pdf. Paper (you do not need to understand all the details about constraint and column generation). 

9/27  Expressive negotiation over donations. 
Slides: ppt, pdf. Paper (you do not need to understand the incentive compatibility section at this point in the course). Programming assignment 2 out. Partial solution to graph winner determination problem, for first problem. 

10/2, 10/4  Voting and social choice. 
Slides: ppt, pdf. SLB Chapter 8 (excluding 8.5). Optional additional resource on social choice: section on voting. 

10/4  Iterative mechanisms/preference elicitation.  Slides: ppt, pdf. 

Part 2: Game theory.  
10/11  Risk neutrality and risk aversion. Expected utility theory. Games in normal form. Dominance and iterated dominance. Computing dominated strategies. 
Slides: ppt, pdf. SLB Chapter 2 (excluding minimax regret, rationalizability, tremblinghand perfect equilibrium, epsilonNash equilibrium), Chapter 3 (excluding LCP/LemkeHowson, computing NE of nplayer games). Some of this runs into the next lecture. Written assignment 1 out. 

10/16, 10/18, 10/30  Minimax strategies. Computing minimax strategies. Nash equilibrium. Computing Nash equilibria. Correlated equilibrium. Computing correlated equilibria.  
10/23  Midterm review.  
10/25  Midterm.  
10/30, 11/1  Games in extensive form. Backwards induction. Subgame perfect equilibrium. Imperfect information. Equilibrium refinements. Computing equilibria. Poker. 
Slides: ppt, pdf. SLB Chapter 4 (excluding alphabeta, sequence form, sequential equilibrium). Programming assignment 3 out.  
11/1, 11/6  Repeated games. Folk theorem. Stochastic games. 
Slides: ppt, pdf. SLB Chapter 5 up to Bayesian games (excluding automata). 

11/8, 11/13  Learning in games. Iterated best response. Fictitious play. Evolutionary game theory. 
Slides: ppt, pdf. SLB Chapter 6. 

SKIPPED  Coalitional game theory. Core. Nucleolus. Shapley value. Computing solutions.  SLB Chapter 11 (excluding compact representations).  
Part 3: Mechanism design.  
11/15, 11/20  Bayesian games. Auctions revisited. 
Slides: ppt, pdf. For the next few lectures: SLB 5.3, Chapter 9 up to (not including) AGV, 10.1 (the parts we did not cover before). Optional: Chapter on auctions.  
11/27  Incentive compatibility. Individual rationality. Revelation principle. Clarke mechanism. Groves mechanisms. 
Slides: ppt, pdf. Written assignment 2 out. 

11/29, 12/4  Automated mechanism design. 
Slides: ppt, pdf. Optional: Chapter on automated mechanism design, read up to and including 6.6.  
12/4, 12/6  Proper scoring rules.  Slides: ppt, pdf. SLB 10.4.2. 

12/6  Realworld applications.  Slides: ppt, pdf. 

12/13, 7pm10pm  Final exam. 