Instructor: Jenn Wortman Vaughan
- February 2: Some presentation tips have been added below.
- January 29: The project guidelines have been posted below. Proposals are due by February 13.
- January 12: Anyone who attended the first two lectures (and signed in) is welcome to email me for a PTE. Include your UID. Additionally, I just got confirmation that this course has been approved to count for credit for AI major and minor field requirements for all CS Ph.D. students.
- January 10: First day of class! The lecture schedule, required reading, and syllabus have been updated.
This seminar-style course will explore theoretical models and frameworks for social computing. We will examine ways in which techniques from learning theory, game theory, and theoretical computer science can be used to model and analyze social computing systems such as prediction markets, crowdsourcing markets, and question and answer forums. Students will be expected to read and present research papers on these topics and complete an open-ended course project.
Who should take this course? This course is primarily intended for students interested in learning about the latest research on theoretical issues that arise in social computing systems. Students who enroll should be very familiar with the basics of probability theory (roughly at the level of the first half of CS 112) and algorithms (e.g., big O notation), comfortable reading and writing formal mathematical proofs, and eager to get involved in class discussions. A background in learning theory and/or game theory will be helpful, but is not required.
Who should not take this course? This course requires students to read and actively discuss several theoretical research papers each week. Students without the mathematical background or interest to do so will struggle with this course. If you are unsure about your background, try reading some of the papers from the reading list and see what you think.
This course has been approved to count for credit for the AI major and minor field requirements for computer science Ph.D. students.
There is no required text book for this course. All reading material is posted below.
Office hours for this course are by appointment only. Email Jenn to schedule an appointment.
Breakdown of Grades
Grades will be based on the following components:
- Paper Reviews (35%): Students are required to complete the required reading and submit a summary before each class using this form. More details are below.
- Presentation and Leading of Discussion (25%): Each student will be required to present a research paper and lead the class discussion twice during the quarter. This will likely be done in groups of 2-3, depending on the size of the class.
- Research Project (40%): Projects consist of a written report and in-class presentation. Depending on the size of the class, it might be required that projects must be completed in groups of 2-3 students.
For borderline cases, active class participation will be taken into account when determining final grades.
Paper reviews must be submitted using this form by 11:59pm on the night before each class, starting with the fourth class. To receive full credit, you must make a reasonable attempt at answering every question. Half credit will be assigned to students who submit incomplete responses. No credit will be given for responses submitted after midnight.
Reviews must contain an answer to every question, and these answers must be in your own words, not copied from the text of the paper. You may not need more than 1-2 sentences per answer, but it should be clear that you have put thought into every question. For tips on how to read and summarize a research paper, you might want to check out Michael Mitzenmacher's blog post and the link to his advice.
When it is your turn to lead the discussion, you should come prepared with enough material that you would be able to get through the whole hour and fifty minutes on your own if nobody in the class said a word. Hopefully you won't need it all, but having a little extra material prepared isn't a bad thing. Even if you don't get through everything you prepared, it will give you more flexibility in that you can decide what to present on the fly based on the interests of the class. Writing up presentation notes will also help you solidify your own understanding of the material. I often falsely believe that I fully understand a model or proof and then realize there was a subtle point I missed when I actually write up detailed notes on each step to present.
You should spend the first 20-30 minutes presenting the main ideas in the paper in detail. Yes, everyone should have read it on their own, but there is a good chance that many people were confused about different points, and this will help make sure that everyone has a basic understanding of the ideas and give people a chance to ask about things they didn't understand.
As a rough guideline, it should take a minimum of about 3 hours per person to prepare the material to present after you have read and understood the paper. I might suggest having everyone on your team read the paper individually and then get together for a couple of hours to plan the presentation.
You might find it useful to read Kilian Weinberger's General Advice on presentations. Here are a few more tips:
- If you are going to use slides, try not to put too much text on them. Instead, use them to show illustrative figures and small phrases. It is not so useful to have slides if you will just read the text off of them. Anything that you can illustrate with a picture will be helpful.
- If you are going to go through proofs in detail, you need to do so very slowly, making sure that people are with you at every step. You should start by clearly defining all of the notation you will use. Write the meaning of variables on the board. Then go through things in a step-by-step manner, making sure that it is totally clear how you get from each step to the next. Pause between steps to check if anyone has questions. Check that people understand. The steps might be obvious to you because you have spent lots of time thinking about them, but they won't be as obvious to others.
- Don't try to rush through material when you're running out of time. It will just confuse people. It's better to skip things.
- Remember that one of the goals of this class is to get discussions going. Encourage as much class participation as possible!
Contact me if you have questions about any of these points when preparing your presentation.
Final Research Projects
The final project guidelines are posted here. Be sure to read the guidelines carefully and make a note of the key dates and milestones!
Good places to look for inspiration for your project include recent workshops on related topics, like HCOMP or the Workshop on Social Computing and User Generated Content. ACM EC also contains many related papers, as do some AI and machine learning conferences.
Schedule & Reading Material
This schedule is tentative and may shift as we get further into the material. Lecture slides will be posted here when available.
Introduction and Background on Game Theory
- Tuesday, January 10 (slides, notes)
Course logistics, overview of the topics we will cover. Utility and games.
Handouts: course syllabus
- Thursday, January 12 (notes)
Normal form games and equilibria. Extensive form games.
Reading: Pages 47-64 of Multiagent Systems by Yoav Shoham and Kevin Leyton-Brown, and pages 3-15 of Basic Solution Concepts and Computational Issues by Eva Tardos and Vijay Vazirani, in Algorithmic Game Theory. We will also cover some of the material in Section 5.1 (pages 113-124) of Shoham and Leyton-Brown.
- Tuesday, January 17 (notes)
Repeated games and the folk theorem.
Reading: Pages 141-147 of Multiagent Systems.
- Thursday, January 19 (led by Jenn) (notes)
Proper scoring rules, market scoring rules, and cost function based markets.
Reading: Combinatorial Information Market Design by Robin Hanson, Information Systems Frontiers, 2003
For a thorough reference on scoring rules, see Strictly Proper Scoring Rules, Prediction, and Estimation by Tilmann Gneiting and Adrian Raftery.
See also: Logarithmic Market Scoring Rules for Modular Combinatorial Information Aggregation by Robin Hanson, Journal of Prediction Markets, 2007 and A Utility Framework for Bounded-Loss Market Makers by Yiling Chen and David Pennock, UAI 2007 -- We will cover the idea of cost function based markets from Chen and Pennock, but this reading is not required.
- Tuesday, January 24 (led by Jenn) (more slides than we got through)
A general framework for market design.
Reading: Efficient Market Making via Convex Optimization, and a Connection to Online Learning by Jacob Abernethy, Yiling Chen, and Jennifer Wortman Vaughan, to appear in ACM TEAC, 2012 (Focus the most on Sections 1-3 and the beginning of 4, through page 12. Then look at 5 and 6 if you have time.)
- Thursday, January 26 (led by Suming and Garret)
Markets for more general crowdsourcing.
Reading: A Collaborative Mechanism for Crowdsourcing Prediction Problems by Jacob Abernethy and Rafael Frongillo, NIPS 2011
Task Routing in Social Networks
- Tuesday, January 31 (led by Lung-Chih, Xiao, and Jun)
The DARPA network challenge.
Reading: Time Critical Social Mobilization: The DARPA Network Challenge Winning Strategy by Galen Pickard et al., working paper
Also related: Mechanisms for Multi-Level Marketing by Yuval Emek, Ron Karidi, Moshe Tennenholtz, and Aviv Zohar, EC 2011
- Thursday, February 2 (led by Chien-Ju, Shahin, and Vanishree)
Scoring rules for task routing.
Reading: Task Routing for Prediction Tasks by Haoqi Zhang, Eric Horvitz, Yiling Chen, and David Parkes, AAMAS 2012
User Generated Content and Crowdsourcing
- Tuesday, February 7 (led by Bryant, Damian, and Max)
Learning from crowdsourced data.
Reading: Vox Populi: Collecting High-Quality Labels From a Crowd by Ofer Dekel and Ohad Shamir, COLT 2009
Also related by the same authors: Good Learners for Evil Teachers, ICML 2009
- Thursday, February 9 (led by Chen, Bin, and Yuchen) (slides)
More learning from crowdsourced data.
Reading: Iterative Learning for Reliable Crowdsourcing Systems by David Karger, Sewoong Oh, and Devavrat Shah, NIPS 2011
See also: the longer version of this paper
- Tuesday, February 14 (led by Siming, Jianyu, and Chiachi)
Modeling crowdsourcing contests as auctions.
Reading: Crowdsourcing and All-Pay Auctions by Dominic DiPalantino and Milan Vojnovic, EC 2009
Also related: Optimal Crowdsourcing Contests by Shuchi Chawla, Jason Hartline, and Balasubramanian Sivan, SODA 2012
- Thursday, February 16 (led by Quinn, Jonathan, and Garret)
Game-theoretic models for incentivizing contributions.
Reading: Incentivizing High-quality User-Generated Content by Arpita Ghosh and Preston McAfee, WWW 2011
Also related: A Game-Theoretic Analysis of Rank-Order Mechanisms for User-Generated Content by Arpita Ghosh and Patrick Hummel, EC 2011
- Tuesday, February 21 (led by Suming, Chien-Ju, and Shahin)
Pricing crowdsourced tasks.
Reading: Pricing Mechanisms for Online Labor Markets by Yaron Singer and Manas Mittal, HCOMP 2011
- Thursday, February 23 (led by Quinn, Lung-Chih, and Max)
Game theoretic models of question and answer forums.
Reading: Designing Incentives for Online Question and Answer Forums by Shaili Jain, Yiling Chen, and David Parkes, EC 2009
Reputation and Recommendation Mechanisms
- Tuesday, February 28 (led by Chiachi, Jianyu, and Siming)
Designing reputation mechanisms.
Reading: Reputation Mechanism Design in Online Trading Environments with Pure Moral Hazard by Chrysanthos Dellarocas, Information Systems Research, 2005 (Focus the most on Sections 1-3 and go on if you have time.)
- Thursday, March 1 (led by Yuchen, Chen, and Bin)
Reputation and social networks.
Reading: Trust-Based Recommendation Systems: An Axiomatic Approach by Reid Andersen et al., WWW 2008
- Tuesday, March 6 (led by Xiao, Jun, and Jonathan)
Reading: Manipulation-Resistant Reputation Systems by Eric Friedman, Paul Resnick, and Rahul Sami, in Algorithmic Game Theory, Cambridge University Press, 2007
Games with a Purpose
- Thursday, March 8 (led by Damian, Bryant, and Vanishree)
A game theoretic model of games with a purpose.
Reading: A Game-Theoretic Analysis of the ESP Game by Shaili Jain and David Parkes, to appear in ACM TEAC, 2012 (Focus on Sections 1-3 and just skim the results in Section 4.)
For a less technical overview of games with a purpose, see: Designing Games With a Purpose by Luis von Ahn and Laura Dabbish, CACM 2008
Research Project Presentations
- Tuesday, March 13 (sample peer review form)
Project presentations, part 1.
- Thursday, March 15 (sample peer review form)
Project presentations, part 2.
Academic Honesty Policy
All students are expected to meet the guidelines laid out in UCLA's Student Guide to Academic Integrity. Any student suspected of academic dishonesty will be referred to the Dean of Students for disciplinary action.
Many thanks to Yiling Chen, Arpita Ghosh, Chien-Ju Ho, Shaili Jain, and Haoqi Zhang for their fantastic suggestions of relevant papers to include in this course.