Schedule
Assignments
Additional Resources
Submit Comments
Project Ideas
CS286r in Previous Years
| Lecture | Date | Topics and Readings | Reading Questions | Extra Readings | Presenter |
| 1 | W 8/31 | Introduction V. Conitzer. Making Decisions Based on the Preferences of Multiple Agents. Communications of the ACM 53(3): 84-94, 2010. |
Lecture notes | Yiling | |
| M 9/5 | Labor Day Holiday | ||||
| 2 | W 9/7 | Game Theory Review I (lecture) Chapter 3, Chapter 5 (5.1 only). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, by Y. Shoham and K. Leyton-Brown (2009). (It appears that the publisher site is temporarily unavailable. If this persists, you can get a slightly older version of the book at here.) |
RQs | Lecture notes | Yiling |
| 3 | M 9/12 | Game Theory Review II (lecture) Chapter 5 (5.2 only), Chapter 6 (6.1.1, 6.1.2, and 6.3 only). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, by Y. Shoham and K. Leyton-Brown (2009). |
RQs | Lecture notes | Yiling |
| Computational Voting Theory | |||||
| 4 | W 9/14 | Voting Rules (lecture) Chapter 9 (9.1 - 9.4 only). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, by Y. Shoham and K. Leyton-Brown (2009). |
RQs | Geanakoplos'05, TL'09, MS'77,
Myerson'96, BF'02. Lecture notes |
Yiling |
| 5 | M 9/19 | Characterization and
Strategic Manipulation (lecture) L.-G. Svensson. The Proof of the Gibbard-Satterthwaite Theorem Revisited. 1999. |
RQs | May'52, Young'75, Young'95, CS'05, Gibbard'73, Satterthwaite'75, Barbera'83, DS'00,
Taylor'02. Lecture notes |
Yiling |
| 6 | W 9/21 | Computational Complexity as
a Barrier to Manipulation (lecture) P. Faliszewski and A.D. Procaccia. AI's War on Manipulation: Are We Winning? AI Magazine 31(4): 53-64, 2010. |
RQs | BTT'89, BO'91, CSL'07, ZPR'09, BNW'11, PR'07a, PR'07b, XC'08, XZPVR'09, XCP'10. | Yiling |
| 7 |
M 9/26 | Fighting Manipulation E. Birrell and R. Pass. Approximately Strategy-Proof Voting. IJCAI'11. |
RQs | Procaccia'10, MS'04. | TF Mike |
| 8 | W 9/28 | Voting Games L. Xia and V. Conitzer. Stackelberg Voting Games: Computational Aspects and Paradoxes. AAAI'10. |
RQs | DE'10, DP'00, Battaglini'05. | Lirong + Swaprava |
| 9 | M 10/3 | Voting with Partial
Information L. Xia and V. Conitzer. A Maximum Likelihood Approach towards Aggregating Partial Orders. IJCAI'11. |
RQs | CS05, Walsh'07, XC'11, BHN'09.
|
Spencer + Stanley |
| 10 | W 10/5 | Practical Voting Rules M. Kalech, S. Kraus, G.A. Kaminka, and C.V. Goldman. Practical Voting Rules with Partial Information. Autonomous Agents and Multi-Agent Systems, 22(1): 151-182, 2011. |
RQs | KL'05, LPRVW'07, PRVW'07,
Walsh'08 |
Sumit + Elena |
| M 10/10 | Columbus Day Holiday | ||||
| 11 | W 10/12 | False-Name-Proofness V. Conitzer, N. Immorlica, J. Letchford, K. Munagala, and L. Wagman. False-Name-Proofness in Social Networks. WINE'10. |
RQs | CY'10, Conitzer'08, LC'08 | Swara + Christina |
| Ranking, Trust, and Reputation |
|||||
| 12 | M 10/17 | Personalized Ranking
A. Altman and M. Tennenholtz. An Axiomatic Approach to Personalized Ranking Systems. Journal of ACM, 2010. |
RQs | BF'07, AT'05, AT'08, AT'10, AT'07, AT'06. | Bo + Mike |
| 13 | W 10/19 | Transitive Trust
P. Resnick and R. Sami. Sybilproof transitive trust protocols. ACM EC'09. Manipulation-resistant Reputation systems, Start reading from section 1.5 "Reputations Based on Transitive Trust", Ch. 27 in Algorithmic Game Theory, Nisan et al., 2008 |
RQs | LGG+'08,
RSK'06,
VCS'05, STP'09, PIKA'08, FLSC'04, CF'05, CF'06, HS'08 |
Rick + Zags |
| 14 | M 10/24 | Viral Marketing Y. Emek, R. Karidi, M. Tennenholtz, and A. Zohar. Mechanisms for Multi-Level Marketing, EC'11. |
RQs | PRPCCMP'10, DR'01, HMS'08 |
Olga + Matt |
| 15 | W 10/26 | Reputation Mechanisms C. Aperjis and R. Johari. Designing Reputation Mechanisms for Efficient Trade. Technical Report. 2010. |
RQs | AJ'10, PZSL'06,
CH'10 |
Ao + Ming |
| Fair Division | |||||
| 16 | M 10/31 | Envy-Free Cake Cutting
S.J. Brams and A.D. Taylor. An Envy-free Cake Division Protocol. American Mathematical Monthly, 102(1):9–18, 1995. |
RQs | Ulle Endriss's slides, DS'61, EP'84, BB'04, Stromquist'80, BJK'07. | Swara + Christina |
| 17 | W 11/2 | Online Cake Cutting T. Walsh. Online Cake Cutting. ADT'11. |
RQs | AD'10, CLP'11, Thomson'83,
CNS'10. |
Toby |
| 18 | M 11/7 | Truthful
and Fair Cake Cutting Y. Chen, J.K. Lai, D.C. Parkes, and Ariel D. Procaccia. Truth, Justice, and Cake Cutting, AAAI'10. |
RQs | CLPP'11, MT'10, CKKK'09. | Rick + Zags |
| 19 |
W 11/9 | Fair Allocation of
Indivisible Goods Y. Chevaleyre, U. Endriss, S. Estivie, and N. Maudet. Reaching envy-free states in distributed negotiation settings. IJCAI'07. |
RQs | EMST'06, BL'08, Sandholm'98, CEM'10, BKPE'07. | Ao + Ming |
| 20 | M 11/14 | Computational Fairness S. de Jong and K. Tuyls. Human-Inspired Computational Fairness. Autonomous Agent and Multi-Agent Systems 22:103--126, 2011. |
RQs | VNPT'07 |
Sumit + Elena |
| 21 | W 11/16 | User-Generated
Content (This belongs to Ranking, Trust, and Reputation. We put it here due to scheduling reasons.) A. Ghosh and P. Hummel. A Game-Theoretic Analysis of Rank-Order Mechanisms for User-Generated Content. ACM EC'11. |
RQs | GM'11 |
Spencer + Stanley |
| Preferences |
|||||
| 22 |
M 11/21 | Preference Elicitation and Voting T. Lu and C. Boutilier. Vote Elicitation with Probabilistic Preference Models: Empirical Estimation and Cost Tradeoffs. ADT'11. T. Lu and C. Boutilier. Robust Approximation and Incremental Elicitation in Voting Protocols. IJCAI'11. |
RQs | Olga + Matt | |
| W 11/23 | Thanksgiving Recess | ||||
| 23 | M 11/28 | Preference and Crowdsourcing J. Urbano, J. Morato, M. Marrero, and D. Martin. Crowdsourcing Preference Judgements for Evaluation of Music Similarity Tasks. ACM SIGIR Workshop on Crowdsourcing for Search Evaluation. 2010. E. Law and L. von Ahn. Input-Agreement: A New Mechanisms for Data Collection Using Human Computation Games, CHI'09. |
RQs |
Baranka11 |
Bo + Mike |
| 24 | W 11/30 | No Class -- Project Time | |||
| 25 | M 12/5 | Project presentations | |||