Date  Topic  Materials  
1/10  Course at a glance. 
Slides: ppt, pdf. Homework 0 out (due 1/17 before class). Week 1 recitation materials. Optional: CACM overview article. 

Part 0: Basic techniques from computer science.  
1/151/24  Linear programming. (Mixed) integer linear programming. 
Slides: ppt, pdf. Example files: painting.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 1/31 before class). Guide to the modeling language. Here are also lecture notes I wrote those for a course on linear and integer programming; if you want to learn more about these topics there may be some useful resources on that course's website. 

1/25 (bonus lecture)  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.  
1/292/12  Singleitem auctions. Combinatorial auctions. Bidding languages. Winner determination problem. Variants (reverse auctions, exchanges). 
Slides: ppt, pdf. Slides for Sasa Pekec's guest lecture. Note: we are not going in the same order as the book on these topics. The book does mechanism design before getting into auctions. I'm pointing out the chapters that are associated with each topic, but for reading purposes you may prefer following the order of the book for the next few lectures, reading mechanism design (Ch. 10) before auctions (Ch. 11), and singleitem auctions and their analysis before combinatorial 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/142/16  Expressive financial securities. 
Slides: ppt, pdf. SLB 10.4.2. Programming assignment 2 out. Partial solution to graph winner determination problem, for first problem. Recitation notes. Optional: Paper 1, paper 2. Article about Predictalot. 

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

2/26  3/4  Voting and social choice. 
Homework 3 out. Slides: ppt, pdf. SLB Chapter 9 (9.5 is optional). Recitation notes. Optional (if you really like this): chapter on computational social choice. A website aiming to do liquid democracy (presented without endorsement; seems legitimate as far as I can tell but I don't know the people involved, use your own judgment if you consider signing up). 

3/6  Moral AI: kidney exchanges and social choice.  Slides: pptx, pdf. Optional: paper on kidney exchange, paper on social choice in these settings. 

3/23 (bonus lecture)  Checking in with everyone. Time for questions about the course. A bonus topic, also to practice with zoom (Sleeping Beauty and imperfect recall).  Slides: ppt, pdf. Recitation notes. 

3/25  Midterm review.  Practice midterm. More practice questions: ppt, pdf. 

around 3/27  Midterm.  
Part 2: Game theory. (We will cut a few parts of this part of the course; topics likely to be skipped are indicated by parentheses.)  
4/1  Risk neutrality and risk aversion. Expected utility theory. 
Slides: ppt, pdf. SLB Section 3.1. 

4/1  4/10  Games in normal form. Dominance and iterated dominance. Computing dominated strategies. Minimax strategies. Computing minimax strategies. Nash equilibrium. Computing Nash equilibria. 
Homework 4 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. Recitation notes. 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/104/15  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. Recitation notes. Optional (including the paper): 5.2.3. Paper on finding optimal strategies to commit to. 

Part 3: Mechanism design. (We will cut fairly significantly from this part of the course; topics likely to be skipped are indicated by parentheses.)  
4/154/17  Bayesian games. Auctions revisited. 
Slides: ppt, pdf. SLB 6.3, 11.1.111.1.8. Optional: 11.1.9, 11.1.10.  
4/174/20  Incentive compatibility. Individual rationality. Revelation principle. Clarke mechanism. Groves mechanisms. 
Slides: ppt, pdf. SLB 10.110.4. Optional: rest of chapter 10. Article on the Swoopo auction. 

SKIPPED  Automated mechanism design. 
Slides: ppt, pdf. Optional: Chapter on automated mechanism design, read up to and including 6.6.  
4/22  Final review.  Practice final. 

from 4/22 to around the originally scheduled time for the final, which was Tuesday, April 28, 9am  noon.  Final. 