Schedule
Assignments
Additional Resources
Submit Comments
CS286r in Previous Years
| Lecture | Date | Topics and Readings | Reading Questions | Extra Readings | Presenter |
| 1 | W 9/5 | Introduction |
Lecture
Notes |
Yiling | |
| Background |
|||||
| 2 |
M 9/10 |
Game
Theory Review I If you didn't take CS 286r in Fall'11, read: Chapter 3, Chapter 5 (5.1 only). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, by Y. Shoham and K. Leyton-Brown (2009). If you took CS 286r in Fall'11 and are familiar with basic concepts of normal-form games and extensive-form games with perfect information, attending this lecture is optional. But you are asked to read the following chapter and submit your reading comments: Chapter 17. Algorithmic Game Theory, edited by N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani (2007). |
RQs |
Lecture
Notes |
Yiling |
| 3 |
W 9/12 |
Game Theory Review II If you didn't take CS 286r in Fall'11, read: 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). If you took CS 286r in Fall'11 and are familiar with extensive-form games with incomplete information, attending this lecture is optional. But you are asked to read the following chapter and submit your reading comments: Chapter 12. A Course in Game Theory. M. J. Osborne and A. Rubinstein (1994). |
RQs |
Lecture
Notes |
Yiling |
| 4 |
M 9/17 | Proper
Scoring Rules Verification of forecasts expressed in terms of probability. G. W. Brier. Monthly Weather Review 78, 1, 1–3, 1950. Strictly Proper Scoring Rules, Prediction, and Estimation. T. Gneiting and A. E. Raftery, Journal of the American Statistical Association, 2007. (Read Section 1 and Section 3.1. The rest is optional.) |
RQs |
Lecture
Notes GR'07, LPS'08, Selten'98, HB'71, Savage'71, WM'68, McCarthy'56 |
Yiling |
| Prediction Markets | |||||
| 5 | W 9/19 | Market
Scoring Rules and Cost Function Based Market Makers I Logarithmic Market Scoring Rules for Modular Combinatorial Information Aggregation, R. Hanson, Journal of Prediction Markets, 1(1):3-15, 2007. David Pennock's blog on how to implement market scoring rules as a market maker. |
RQs |
Lecture
Notes Hanson'03, CP'07, OPRS'10, CP'07 |
Yiling |
| 6 | M 9/24 |
Market
Scoring Rules and Cost Function Based Market Makers II Efficient Market Making via Convex Optimization, and a Connection to Online Learning, J. Abernethy, Y. Chen, and J.W. Vaughan, to appear in ACM TEAC. (Read sections 1-3, the beginning of section 4 [before 4.1], and section 8. The rest is optional.) |
RQs |
Lecture Notes OS'11 |
Yiling |
| 7 |
W 9/26 |
Empirical
Performance of Prediction Markets The Promise of Prediction Markets, K.J. Arrow et. al., Science, 320, p.877, May 16 2008. Prediction Markets, J. Wolfers and E. Zitzewitz, The Journal of Economic Perspectives 18(2), 2004. Prediction Without Markets, S. Goel, D.M. Reeves, D.J. Watts, and D.M. Pennock ACM Conference on Electronic Commerce, 2010. |
RQs |
Presentation BFNR'01, CP'02, CFH'03, CWZ'08, OS'10 |
Lily Hsiang + Carl Daher |
| 8 |
M 10/1 | Kelly
Betting and Prediction Markets The Kelly Criterion in Blackjack, Sports Betting, and the Stock Market, E. O. Thorp, International Conference on Gambling and Risk Taking, 1997. (Read sections 1 and 2. The rest is optional.) Learning Performance of Prediction Markets with Kelly Bettors, A. Beygelzimer, J. Langford, and D.M. Pennock, AAMAS 2012. |
RQs |
Slides Pennock's review of the book Fortune's Formula. More on Kelly Criterion: Chapter 6 (6.1-6.3) and Chapter 16 (16.1-16.4) of Elements of Information Theory, T.M. Cover and J.A. Thomas (2005) |
David Pennock |
| 9 |
W 10/3 | Combinatorial
Prediction Markets Blog post: A Prediction Market Trading Pit for the Digital Age. Blog post: What is (and what good is) a combinatorial prediction market? A tractable combinatorial market maker using constraint generation. M. Dudik, S. Lahaie, and D.M. Pennnock, ACM EC 2012. |
RQs |
Slides CFLPW'08, GP'09, CFNP'07 CFNP2'07, CGP'08, FKPW'04 |
David Pennock |
| M 10/8 |
Columbus Day Holiday | |
|||
| 10 | W 10/10 |
Information Aggregation with Bayesian Agents Information Aggregation in Dynamic Markets with Strategic Traders, M. Ostrovsky, to appear in Econometrica. (Read the parts for market scoring rules. The parts for Kyle's model is optional.) |
RQs |
Slides CRV'12, CDHRPHFG'10, IGM'11 |
Eli Schachar + Ryota Iijima |
| 11 |
M 10/15 |
Decision Markets Eliciting Predictions for Discrete Decision Making, Y. Chen, I.A. Kash, M. Ruberry, and V. Shnayder, manuscript, 2012. |
RQs |
Slides SCG'09, OS'10b |
Mike |
| 12 | W 10/17 |
More
on Market Making A Bayesian Market Maker, A. Brahma, M. Chakraborty, S. Das, A. Lavoie, and M. Magdon-Ismail, ACM EC 2012. |
RQs |
Slides CK'11, DMI'09, OS'12, OPRS'10 |
Andrew Liu + Tianen Li |
| |
Human Computation,
Crowdsourcing and User-Generated Content |
||||
| 13 | M 10/22 |
Human Computation S. Jain and D. Parkes. A Game-Theoretic Analysis of the ESP Game. to appear in ACM TEAC. L. v. Ahn and L. Dabbish. Designing Games with A Purpose. Communications of ACM. 51(8): 58-67, 2008. |
RQs |
Slides VLB'06, BLHL'03 |
Ming Yin + Steve Komarov |
| 14 | W 10/24 | Getting
Crowds to Work Communitysourcing: Engaging Local Crowds to Perform Expert Work Via Physical Kiosks. K. Heimerl, B. Gawalt, K. Chen, T.S. Parikh, and B. Hartmann, CHI 2012. Designing incentives for inexpert human raters. A.D. Shaw, J.J. Horton, and D.L. Chen, CSCW 2011. |
RQs |
Slides Cool applications: BLMH...'10, BBMK'11, NHZG'11 Incentives: MW'10, ARG'12 |
Naor Brown + Leah Birch |
| 15 | M 10/29 | Crowdsourcing
Workflow Control Dynamically Switching between Synergistic Workflows for Crowdsourcing, C.H. Lin, Mausam, D.S. Weld, AAAI 2012. Crowdsourcing Control: Moving Beyond Multiple Choice, C.H. Lin, Mausam, D.S. Weld, UAI 2012. |
RQs |
Slides DMW'10, DMW'11, LCGM'10, KSKK'11 |
Perry Green + Nate Tucker |
| 16 | W 10/31 | Crowdsourcing
Quality Control Iterative Learning for Reliable Crowdsourcing System, D.R. Karger, S. Oh, and D. Shah, NIPS 2011. |
RQs |
Slides IPW'10 |
Jao-ke Chin-Lee + Madalina Persu |
| 17 | M 11/5 | Crowdsourcing Contest Efficient Crowdsourcing Contest, R. Cavallo and S. Jain, AAMAS 2012. |
RQs |
Slides CHS'12, CJ'12, GBKG'12, AS'09, DV'09 |
Ruggiero Cavallo |
| 18 | W 11/7 | Social
Media and Social Influence A 61-million-person experiment in social influence and political mobilization. R.M. Bond, C.J. Fariss, J.J. Jones, A.D.I. Kramer, C. Marlow, and J.E. Settle, Nature 2012. Measuring User Influence in Twitter: The Million Follower Fallacy. M. Cha, H. Haddadi, F. Benevenuto, and K.P. Gummadi. AAAI Conference on Weblogs and Social Media, 2010. |
RQs |
Slides GWG'11, GG'12 |
Nihar Shah + Peter Tu |
| 19 | M 11/12 | Influence
over Social Networks How to Win Friends and Influence People, Truthfully: Influence Maximization Mechanisms for Social Networks, Y. Singer, ACM WSDM 2012. |
RQs |
Slides KKT'03, KR'05, JY'10 |
Lily Yingyi Gu + Yifan Wu + Jean-Rémy Bancel |
| 20 | W 11/14 | User-Generated
Content Implementing Optimal Outcomes in Social Computing: A Game-Theoretic Approach, A. Ghosh and P. Hummel, WWW 2012. |
RQs |
Slides GM'11, GH'11, GM'12 |
Peter Zhang + Zagreb Mukerjee |
| 21 | M 11/19 | General
Crowdsourcing Market A Collaborative Mechanism for Crowdsourcing Prediction Problems, J. Abernethy and R. Frongillo, NIPS 2011. |
RQs |
Slides AF'12 |
Chris Lee + Stewart Richardson |
| W 11/21 |
Thanksgiving Recess |
|
|
||
| Peer
Prediction |
|
||||
| 22 |
M 11/26 | Peer
Prediction - The Original Mechanism Eliciting Honest Feedback: The Peer-Prediction Method, N. Miller, P. Resnick, and R. Zeckhauser, Management Science, 51(9): 1359-1373, 2005. |
RQs |
Slides JF'06, JF'07, JF'08, JR'09, PRGJ'08, WP'12 |
Colin Jia Zheng + Ken Kan |
| 23 |
W 11/28 | Bayesian
Truth Serum |
RQs |
Slides DW'08 |
Joseph Schiavone + Vanessa Tan |
| 24 |
M 12/3 |
Robust
Bayesian Truth Serum |
RQs |
Slides |
Bo Waggoner + Mark Bun |
| F 12/7 | Project presentations |