Date  Topic  Materials  
1/15  Course at a glance.  Slides: ppt, pdf.
Optional: CACM overview article. 

Part 0: Basic techniques from computer science.  
1/20  1/29  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_simple.mod, knapsack.mod, cell.lp, cell.mod, hotdog.mod, sudoku.mod. SLB Appendices A, B. Programming assignment 1 out (due 2/3). Guide to the modeling language. 

2/3, 2/5  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. Optional: CACM article on P vs. NP. 

Part 1: Expressive marketplaces.  
2/10  2/19  Singleitem auctions. Combinatorial auctions. Bidding languages. Winner determination problem. Variants (reverse auctions, exchanges). 
Slides: ppt, pdf. Note: we are not going in the same order as the book in these lectures. The book does mechanism design before getting into auctions. SLB 11.3.111.3.4, 11.4.1. Optional: 11.2, 11.3.5, Conitzer chapter on auctions, Lehmann et al. chapter on winner determination, Sandholm chapter on optimal winner determination. 

2/24, 2/26  Expressive financial securities. 
Slides: ppt, pdf. SLB 10.4.2. Programming assignment 2 out. Partial solution to graph winner determination problem, for first problem. Optional: Paper 1, paper 2. 

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

3/17, 3/24  Voting and social choice. 
Slides: ppt, pdf. SLB Chapter 9 (9.5 is optional). 

3/19  MIDTERM  
Part 2: Game theory.  
3/26  Risk neutrality and risk aversion. Expected utility theory. 
Slides: ppt, pdf. SLB Section 3.1. 

3/26, 3/31, 4/2, 4/7  Games in normal form. Dominance and iterated dominance. Computing dominated strategies. Minimax strategies. Computing minimax strategies. Nash equilibrium. Computing Nash equilibria. 
Homework 3 out. Slides: ppt, pdf. SLB 3.2, 3.4.3, 4.5; 3.3.13.3.3, 3.4.1, 4.1, 4.2.1, 4.2.3, 4.2.4, 4.4. Optional (including the papers): 3.3.4, 4.2.2; 3.4.5, 4.6. Paper on computing dominated strategies. (You can skip the part on Bayesian games.) Paper on computing Nash equilibria. (You only need to read the part concerning 2player games.) Paper on computing special kinds of Nash equilibria. (You can skip everything from Bayesian games on.) 

4/9, 4/14  Games in extensive form. Backwards induction. Subgame perfect equilibrium. Imperfect information. Equilibrium refinements. Computing equilibria. Poker. 
Slides: ppt, pdf. SLB 5.1 (alphabeta is optional), 5.2.1, 5.2.2. Optional (including the paper): 5.2.3. Paper on finding optimal strategies to commit to. 

Part 3: Mechanism design.  
4/16, 4/21  Bayesian games. Auctions revisited. 
Homework 4 out. Slides: ppt, pdf. SLB 6.3, 11.1.111.1.8. Optional: 11.1.9, 11.1.10.  
4/23  Incentive compatibility. Individual rationality. Revelation principle. Clarke mechanism. Groves mechanisms. 
Slides: ppt, pdf. SLB 10.110.4. Optional: rest of chapter 10. 

4/28  Realworld applications. 


Tuesday May 4, 7pm10pm  Final exam. 