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 | Single-item 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.1-11.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.1-3.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 2-player 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 (alpha-beta 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.1-11.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.1-10.4. Optional: rest of chapter 10. |
|
4/28 | Real-world applications. |
|
|
Tuesday May 4, 7pm-10pm | Final exam. |