Date | Topic | Materials |
First class: 2014/1/9 |
Course at a glance. What problems are we trying to solve? Example applications: game playing, security, elections, electronic marketplaces, resource allocation, ... |
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/15, 1/17 | Linear, integer, and mixed integer programs. |
Slides: ppt, pdf. SLB Appendices A and B (if you need them). 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, knapsack.mod (or the one from in class), cell.lp, cell.mod (or the one from in class), hotdog.mod (or the one from in class) |
1/27 | (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. |
1/22 | Risk neutrality and risk aversion. Expected utility theory. |
Slides: ppt, pdf. SLB Section 3.1. |
1/22, 1/24, (snow day 1/29), 1/31 | Games in normal form. Dominance and iterated dominance. Computing dominated strategies. Minimax strategies. Computing minimax strategies. Nash equilibrium. Computing Nash equilibria. Correlated equilibrium. Computing correlated equilibria. |
Slides: ppt, pdf. Homework 1 out. 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/5, 3/5 | Games in extensive form. Backward induction. Subgame perfect equilibrium. Imperfect information. Equilibrium refinements. |
Slides: ppt, pdf. SLB 5.1 (alpha-beta is optional), 5.2.1, 5.2.2. Optional: 5.2.3. Paper on finding optimal strategies to commit to. |
2/7, 2/12 | (Computational) social choice. Voting rules. Desirable properties of voting rules. Arrow's impossibility theorem. Muller-Satterthwaite impossibility theorem. Manipulation. Gibbard-Satterthwaite impossibility theorem. Single-peaked preferences. |
Slides: ppt, pdf. SLB Chapter 9.1-9.4. Optional: 9.5. Chapter on computational social choice. |
2/12, (snow day 2/14), 2/19, 2/21 | Auctions. English, Japanese, Dutch, first-price sealed-bid, second-price sealed-bid (Vickrey). Combinatorial auctions. Winner determination. Combinatorial reverse auctions and exchanges. Bidding languages. |
Slides: ppt, pdf. Homework 2 out. Note: we won't go in the same order as the book in the next few 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/21, 2/26, 2/28 | Analyzing auction mechanisms: Bayesian games, Bayes-Nash equilibrium, revenue equivalence, revenue-maximizing (Myerson) auctions, redistribution auctions. |
Slides: ppt, pdf. SLB 6.3, 11.1.1-11.1.8. Optional: 11.1.9, 11.1.10. |
2/26, 3/5 | Mechanism design. Incentive compatibility. Individual rationality. Revelation principle. Clarke mechanism. Generalized Vickrey Auction. Groves mechanisms. Myerson-Satterthwaite impossibility. Computational topics. |
Slides: ppt, pdf. Chapter 10.1-10.4. Optional: rest of chapter 10. Alternative resources: Chapter on mechanism design + chapter on revelation principle. Parkes chapter on mechanism design. |
3/3 (bonus), 3/5 | Midterm review. | Practice questions: ppt, pdf. |
Planned for March 7 | MIDTERM | |
3/18 | Midterm solutions and discussion. | |
3/18, 3/21 | Preference elicitation in voting and auctions. Iterative combinatorial auctions. Communication complexity. Restricted classes of valuations. |
Slides: ppt, pdf. Optional: Parkes chapter on iterative CAs. Sandholm-Boutilier chapter on preference elicitation in CAs. |
3/21, 3/26 | Repeated games. Folk theorem. Stochastic games. | Slides: ppt, pdf. SLB 6.1, 6.2. Optional: Paper on computing a Nash equilibrium in repeated games. Paper on stochastic games and learning. |
3/26, 3/28 | Learning in games. Iterated best response. Fictitious play. No-regret algorithms. Targeted learning. Evolutionary game theory. | Slides: ppt, pdf. SLB Chapter 7. |
SKIPPED | Concise representations of games. Congestion games. Potential games. Graphical games. Action-graph games. MAIDs. |
SLB 6.4, 6.5. Optional: Paper on action-graph games. |
3/28, 4/2 | Cooperative/coalitional game theory. Core. Nucleolus. Shapley value. Computing solutions. |
Slides: ppt, pdf. SLB Chapter 12. |
4/2 | Automated mechanism design. | Slides: ppt, pdf. Chapter on automated mechanism design, read up to and including 6.6. Optional: Remainder of the chapter. |
4/4 | Algorithmic mechanism design. Approximately efficient truthful combinatorial auctions. Shortest paths. Minimizing make-span. Characterizing allocation rules that can be made incentive compatible. |
Slides: ppt, pdf. Optional: Paper on algorithmic mechanism design. Paper on computing Clarke payments for shortest paths. Paper on approximately efficient, incentive compatible combinatorial auctions. Paper on characterizing which allocation rules can be made incentive compatible. |
SKIPPED | Computational hardness as a barrier against manipulation. Limitations. |
War on manipulation article. Optional: Paper on STV being hard to manipulate. Paper on hardness with few alternatives. |
SKIPPED | Collusion. Use of false names over the Internet. |
Overview article on false names in mechanism design. Optional: Paper on collusion in combinatorial auctions and exchanges. Paper on false-name bidding. Another paper on false-name bidding. Paper on collusion/false names in coalitional game theory. |
4/9 (Abhinandan, Jananee, Naga, Rupert; 24 bonus points), 4/11 (Andrew, Brett, Matt, Zijian; 22 bonus points), 4/14 (Ang, Danny+Xu, Dennis+Paul+Rachel, Qiuyun; 12 bonus points -- Monday during regular class time), 4/16 (Garrett+Jiangwei, Mohamed, Seyed, Utku) | Student presentations | Code used to match students to presentations, student bids (input to solver). |