| Week | Date | Topic | By | Slides & Video | Further reading |
| 1 | 8-26 | Introduction to the course | Lirong Xia | ||
| 8-29 | Basic social choice: voting rules, axiomatic characterizations | Lirong Xia | pdf ppsx video |
SLB 9.1-9.4 | |
| 2 | 9-2 Labor day | No class | |||
| 9-5 | Basic game theory: normal form games and Nash equilibrium; extensive form games, subgame perfect equilibrium, backward induction. | Lirong Xia | pdf ppsx |
SLB 3.2; 3.3-3.3.2; 5.1 | |
| 3 | 9-9 | Basic mechanism design: revelation principle, VCG mechanisms, auctions | Lirong Xia | Mechanism Theory | |
9-12 HW1 due before class |
Linear and integer programming, computational complexity | Lirong Xia | pdf ppsx |
CACM | |
| 4 | 9-16 | Computational Social Choice: The easy-to-compute axiom | Lirong Xia | pdf ppsx |
|
| 9-19 | Computational Social Choice: Combinatorial voting | Lirong Xia | pdf ppsx |
||
| 5 | 9-23 | Computational Social Choice: The hard-to-manpulate axiom | Lirong Xia | pdf ppsx |
|
| 9-26 HW2 due before class | Computational Social Choice: Statistical approaches | Lirong Xia | pdf ppsx |
||
| 6 | 9-30 Preferences over papers due | Guest lecture: Random sample elections | Richard Carback & David Chaum | paper | |
| 10-3 Upcoming | Matching | Lirong Xia | pdf ppsx |
||
| 7 | 10-7 | Fair division | Lirong Xia | pdf ppsx |
End-10 |
| 10-10 | Judgement aggregation | Lirong Xia | pdf ppsx |
List-12 | |
| 8 | 10-15 Tuesday Makeup class for Columbus Day | Recommender systems | Lirong Xia | pdf ppsx |
|
| 10-17 | Topic: A new class of voting rules Lirong Xia. Generalized Scoring Rules: A Framework That Reconciles Borda and Condorcet. SIGecom Exchanges, 2013. Related papers:
|
Yosef | pptx | Xia 13 | |
| 9 | 10-21 | Topic: Extensive-form game of sequential voting Lirong Xia and Vincent Conitzer. Stackelberg Voting Games: Computational Aspects and Paradoxes. AAAI-10. Related papers:
|
James&John | pptx | |
| 10-24 | Topic: Manipulation with incomplete information Vincent Conitzer, Toby Walsh, and Lirong Xia. Dominating Manipulations in Voting with Partial Information. AAAI-11. Related papers:
|
James&John | pptx | ||
| 10 | 10-28 Project proposal due |
Topic: Game and equilibria of combinatorial voting David S. Ahn and Santiago Oliveros. Combinatorial voting. Econometrica-12. If the link above is broken, see here for an old version. Related papers:
|
Eric | ||
| 10-31 | Topic: Regret-based vote elicitation Tyler Lu and Craig Boutilier. Robust Approximation and Incremental Elicitation in Voting Protocols. IJCAI-11. If the link above is broken, see here. Related papers:
|
Samta & Onkar | |||
| 11 | 11-4 | Topic: Information-based vote elicitation Thomas Pfeiffer and Xi Alice Gao and Andrew Mao, Yiling Chen, and David G. Rand. Adaptive Polling and Information Aggregation. AAAI-12. Related papers:
|
Jon Crall | odp | |
| 11-7 | Hypothesis testing and statistical decision theory |
Lirong Xia | pdf ppsx |
A nice book chapter | |
| 12 | 11-11 | Topic: Matching with partial orders B. Rastegari, A. Condon, N. Immorlica, K. Leyton-Brown. Two-Sided Matching with Partial Information ACM EC-13. Related papers:
|
Samta & Onkar |
||
| 11-14 | Fair allocation: Random serial dictatorships Anna Bogomolnaia and HerveMoulin. A New Solution to the Random Assignment Problem. JET 2001. Related papers:
|
Zach & Bharath | BCKM, | ||
| 13 | 11-18 | Cake cutting Brams, Steven J.; Michael A. Jones and Christian Klamler. Better Ways to Cut a Cake. Notices of AMS 2006. Related papers:
|
Yu-li | ||
| 11-21 | Ensemble learning: AdaBoost Yoav Freund and Robert E. Schapire. A Short Introduction to Boosting. |
Zach & Bharath | |||
| 14 | 11-25 | Project presentation (Samta/Onkar) | |||
11-28 Thanksgiving |
No class | ||||
| 15 | 12-2 | Project presentation (Yosef, John, James) | |||
| 12-5 | Project presentation (Eric, Jon, Yu-li, Zach) | ||||
| 16 | 12-9 midnight |
||||