Date | Topic | Materials |
1/13, 1/18 | Course at a glance. What problems are we trying to solve? | Slides:
ppt, pdf. Optional readings: Some CACM articles: Computer Science and Game Theory, Making Decisions Based on the Preferences of Multiple Agents, Designing the Perfect Auction. |
1/18, 1/20 | Proper scoring rules. | Slides: pptx, pdf. Optional readings: Gneiting-Raftery paper, Shi et al. paper. |
1/20, 1/25 | Market scoring rules and prediction markets. | Homework 1 out. Slides: pptx, pdf. Optional readings: Chen-Pennock paper. |
1/27 | Background: linear and integer programming. | Slides: ppt, pdf. Appendices A and B (if you need them) of SLB (the Multiagent Systems book above by Shoham and Leyton-Brown). In case you want to use it: GNU Linear Programming Kit. Let me know if you have trouble installing/using it. Example files: painting.lp, painting.mod. knapsack.lp, knapsack1.mod (or knapsack2.mod), cell.lp, cell.mod, hotdog.mod. |
1/30 (Monday) | (Bonus lecture.) Ridiculously brief introduction to theoretical computer science: computational problems, algorithms, runtime, complexity. |
Slides: ppt,
pdf. Modeling files: set_cover.mod, set_cover2.mod, matching.mod. Sorting spreadsheet. CACM article on P vs. NP. |
2/1, 2/3, 2/15 | Background: game theory. | Homework 2 out. Slides: ppt, pdf. SLB 3.2, 3.4.3, 4.5; 3.3.1-3.3.3, 3.4.1, 3.4.5, 4.1, 4.2.1, 4.2.3, 4.2.4, 4.4, 4.6. Optional: 3.3.4, 4.2.2. 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.) |
2/8 | Guest lecture by Sasa Pekec on combinatorial auctions. |
Slides: ppt, pdf. Note: we won't go in the same order as the SLB book in these lectures. I'm pointing out the chapters that are associated with each lecture, 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 single-item auctions and their analysis before combinatorial auctions. SLB 11.3.1-11.3.4, 11.4.1. Optional: 11.2, 11.3.5. Lehmann et al. chapter on winner determination. Sandholm chapter on optimal winner determination. |
2/10 | Guest lecture by Catherine Moon on repeated games. | Slides: pptx, pdf. |
2/15, 2/17 | Expressive financial/prediction/information markets. |
Slides: ppt, pdf. securities.mod Optional: Paper 1, paper 2. |
2/22, 2/24 | Background: Bayesian games and auctions. | Slides: ppt, pdf. SLB 6.3, 11.1.1-11.1.8. Optional: 11.1.9, 11.1.10. |
3/1, 3/3 | Background: mechanism design. | Slides: ppt, pdf. SLB 10.1-10.6. |
3/6 (Monday) | Midterm review. | Practice exam questions. |
3/8 | Midterm. | |
3/3, 3/10 | Automated mechanism design. | Slides: ppt, pdf. Chapter on automated mechanism design, read up to and including 6.6. Optional: Remainder of the chapter. Example files: amd_example.mod. divorce.dat, mod_divorce.dat, |
3/22, 3/24 | Peer prediction. | Slides: pptx, pdf Homework 3 out. Additional files: HW3_data.txt. example_mechanism.txt, check_submission.py, true_distribution.txt. |
3/29, 3/31, 4/5 | Mechanism design with correlation. Cremer-McLean. | Slides: pptx, pdf Reading: Albert, Conitzer, and Lopomo (2016), Cremer and McLean (1985). Optional: Kosenok and Severinov (2008), Ronen (2001), Roughgarden and Talgam-Cohen (2013). Example files: amd_example_corr.mod, divorce_corr.dat. |
4/5, 4/7, 4/12 | Robust Mechanism Design. | Slides: pptx, pdf Reading: Albert, Conitzer, and Stone (2017) (AAAI). Example files: RobustMech.mod, robust_mech.dat, ConstraintGen.mod, constraint_gen.dat. |
SKIPPED | Ad auctions. | Reading: Chapter 10 from Economics and Computation by Parkes and Seuken (unpublished, but this chaper is included by permission of the authors). |
SKIPPED | Machine learning with strategic agents. | Reading: Dekel, Fischer, and Procaccia (2010). |
SKIPPED | Simple vs. prior-dependent mechanisms. | Reading: Hartline and Roughgarden (2009). |
4/12 | Project presentations: Andrew; Harsh+Heer+JP; Mingxi; Yinshi+Yiqian. (22 bonus points each.) | Matching students to presentation slots: e-mail with description, code used to match teams to presentation slots, example bids (input to solver), presentation bids (input to solver). |
4/14 | Project presentations: Haiqi+Lin; Liqun+Wenlin; Nick; Zichang. (17 bonus points each.) | |
4/17 | Project presentations: Amir+Reza; Bill; Qitong; Yuan. (5 bonus points each.) | |
4/19 | Project presentations: Artem; Chaofan+Menglin; Chengkang+Zilong; Joe; Xin. (0 bonus points each.) |