CPS 290.4/590.4, Spring 2015
Crowdsourcing Societal Tradeoffs



Details
WF, 10:05-11:20am, Soc Psy 127
We also have space reserved in the Edge, Mondays 10am-1pm, project room 6, access code 3241+ENTER.

Instructor: Vincent Conitzer. (Please call me Vince.)

... with help from Markus Brill and Rupert Freeman.
OH: At least one of us will be in the Edge Mondays 10am-1pm. If this doesn't work for you, Vince's OH are Monday 8:45-10am (LSRC D207), Wednesday 11:20-11:40am (catch me right after class), Friday 11:20-11:45am (catch me right after class).

Description
This course is an unusual joint-project-based course that is open to undergraduate and graduate students from a variety of disciplines. The objective of the course is to design a system for determining numerical tradeoffs between various forms of unethical (or just socially undesirable) behavior. For example, can we say that using a gallon of gasoline is just as bad for society as creating x bags of (landfill) trash? How might we arrive at (an estimate of) x? A system that could credibly give such estimates would be invaluable to policy makers. For certain types of tradeoff, an exact numerical tradeoff might be obtained based purely on scientific evidence. For example, for two activities whose only downside is clearly the emission of a certain amount of carbon dioxide, we can simply measure these amounts and take the ratio. However, in most cases, including even the example above, it is hard to imagine that there is an objective fact of the matter as to what the correct value of x is, so that some collective subjective assessment is necessary to establish a tradeoff.

The approach we are considering is anchored in the newly emerging field of computational social choice (which in turn is anchored in the well established field of social choice). For example, a natural approach is to have a collection of voters who each report their estimate of x, and take the median of these numbers. (There are various social-choice-theoretic reasons for preferring this to taking the average, including limiting the influence of a single voter.) Of course, such a system could be improved by allowing discussion, allowing experts a chance to teach voters about key facts that should inform the value of x, guiding people to "vote" on the comparisons about which they are actually knowledgeable, and so on. There are also many interesting social-choice-theoretic aspects when we move to more than two items to compare, if we want estimates to remain consistent with each other.

In this project-based course, we hope to create theory and tools to better address these questions, ideally culminating in a usable (e.g., web-based) system as well as publishable research. Participants in the course will organize into collaborative teams to achieve this goal. Early lectures will be devoted to giving students background in computational social choice that is useful to the project (with some assignments or perhaps a midterm to ensure absorption of the material), but focus will quickly shift primarily to the project, with class time devoted to the class working together to overcome obstacles. We plan to attract guest lecturers from a variety of disciplines (e.g., economics, political science, philosophy, environmental science, behavioral sciences, public policy, law, entrepreneurship, etc.), with half of class time devoted to the guest lecture and the other half to discussion of the project with the guest. Some of these lecturers will be invited dynamically as the course progresses to address specific issues that have come up. The instructors and/or participants will also dynamically lecture on material that has come up as being relevant to the project. Subteams will present their final findings at the end of the course.

Prerequisites

Registration is by instructor permission. If you are interested in taking this course, please e-mail Vince (see above) with an explanation of why you're interested and what your relevant background for this course is.

The goal is to bring people with different disciplinary backgrounds together, so there are no hard prerequisites. At the same time, we do want to ensure that students in the course have significant background in some areas that will allow them to be able to contribute. Enrollment is by instructor permission only. To obtain permission, please e-mail Vince with your relevant background (e.g., relevant courses you have taken and your grades in them). Examples of relevant background include: background in mathematics (especially, but not exclusively, discrete math, probability, rigorous proof-based courses), computer science (especially, but not exclusively, artificial intelligence, machine learning, algorithms, Web development), economics (especially microeconomic theory and game theory), philosophy (especially ethics and foundations of decision theory), political science (especially voting and social choice), or any other experience that you consider relevant. Again, you certainly don't need to have all of this background, but any of these would help you contribute to the course.

Grading
homework 10%
midterm 15%
class discussion participation 20%
scribe duties and wiki contribution 20%
(remaining) project contribution 35%

For the homework assignments, you may discuss them with a single other person in the class (working in pairs), but each of you should do your own writeup. This also means that you should not take detailed notes during your meeting with the other person; if you can't remember what you talked about, you probably didn't really understand it. Please acknowledge everyone you talked with about the homework (including your homework partner, if any) and all sources you used (other than material on the course website) at the beginning of your homework.

Schedule
Because of the nature of the course, we will attempt to be highly dynamic with the schedule. Discussion should be an important part of every class, and the further we progress in the course, the more class should be driven by pursuing the ideas that have come up in the course. Early on in the course, however, we will cover more standard material that is relevant to the objectives of the course, and understanding of this material will be tested on homework and a midterm. (Even here, though, we can dynamically adjust which material is presented as needed.)

Date Topic Materials
1/9, 1/14 Introduction. The problem at a high level. Why is it worth solving? Why is it hard? Which existing techniques might be useful? Slides: ppt, pdf.
Paper covering the idea of the course.
Homework 1.
1/16-1/22
Introduction to voting theory. Slides: ppt, pdf.
Homework 2.
example_election.jpg
Optional: book chapter on computational social choice (goes beyond what we'll cover in this course).
1/29, 2/4
Linear, integer, and mixed integer programs. Slides: ppt, pdf.
Homework 3.
Example files: painting.lp, painting.mod, knapsack.lp, knapsack1.mod, knapsack2.mod, cell.mod, kemeny.mod.
Board pictures: painting.jpg, knapsack.jpg, cell_phones.jpg.
2/6, 2/11
Judgment aggregation. Slides: pptx, pdf.
Optional: book chapter on judgment aggregation. logic_notation.jpg.
2/13
Guest lecture: Francesca Rossi (U. Padova / Harvard), voting in combinatorial domains. Slides: pdf.
2/18, 2/20, 2/25
Voting in pursuit of the "truth": the maximum likelihood approach. Slides: ppt, pdf.
Optional: chapter covering the MLE approach (starting at Section 8.3).
2/27
Guest lecture: Dave Pennock (Microsoft Research), prediction and decision markets. Slides: pdf.
3/4
MIDTERM. We will do some review in the Edge on Monday 3/2.
3/6
Guest lecture: Ashish Goel (Stanford), crowdsourced democracy.
3/18, 3/25
Preference elicitation. Slides: ppt, pdf.
3/27
Strategic voting when voters vote sequentially or in a combinatorial domain. Slides: pptx, pdf.
4/1
Guest lecture: Matthew Adler (Duke Law; also econ, philosophy, public policy)
4/3
Guest lecture: Jens Witkowski (University of Pennsylvania) Slides: pdf.
4/8
Guest lecture: Sasa Pekec (Duke Fuqua), selecting committees/subsets. Slides: pdf.
4/10
Presentation slots auction results. A better rule for crowdsourcing societal tradeoffs. Slides: ppt, pdf.
Tradeoff files: kemeny_soctrade_additive_example.mod, kemeny_soctrade_original_instance.mod.
Presentation auction files: students_to_presentations.C, presentation_bids.txt.