Tentative Schedule

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

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

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

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
5 M 9/19 Characterization and Strategic Manipulation

L.-G. Svensson. The Proof of the Gibbard-Satterthwaite Theorem Revisited. 1999.
RQs May'52, Young'75, Young'95, CS'05, Gibbard'73, Satterthwaite'75Barbera'83, DS'00Taylor'02.

Lecture notes
6 W 9/21 Computational Complexity as a Barrier to Manipulation

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'11PR'07a, PR'07b, XC'08XZPVR'09, XCP'10. Yiling
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'08FLSC'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'80BJK'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
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
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.
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
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.
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.
Bo + Mike
24 W 11/30 No Class -- Project Time

25 M 12/5 Project presentations