| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | August 31, 2016 |
| Latest Amendment Date: | August 31, 2016 |
| Award Number: | 1637418 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Tracy Kimbrel
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2016 |
| End Date: | August 31, 2019 (Estimated) |
| Total Intended Award Amount: | $475,000.00 |
| Total Awarded Amount to Date: | $475,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
450 JANE STANFORD WAY STANFORD CA US 94305-2004 (650)723-2300 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
Huang 358 Stanford CA US 94305-4026 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithms in the Field |
| Primary Program Source: |
|
| Program Reference Code(s): | |
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
YouTube competes with Hollywood as an entertainment channel, and also supplements Hollywood by acting as a distribution mechanism. Twitter has a similar relationship to news media, and Coursera to Universities. But there are no online alternatives for making democratic decisions at large scale as a society. As opposed to building consensus and compromise, public discussion boards often devolve into flame wars when dealing with contentious socio-political issues. This project aims to develop algorithms and platforms for collaborative decision making at scale. These platforms will be deployed in real decision-making processes, resulting in substantial broad impact.
Much of the work will be informed by participatory budgeting, where a group of users collectively produce a budget. Since budgetary constraints can be modeled as convex constraints, the insights from participatory budgeting will then be applied to more general convex decision spaces.
On the algorithmic side, the PIs propose to develop algorithms and mechanisms for consensus that go beyond simple voting. In complex decision spaces, the normal voting methodology of ranking a set of candidates breaks down, and we need new mechanisms. For example, for participatory budgeting, the users might be asked to solve a knapsack problem, providing a complete budget. This leads to exciting directions in incentive compatibility, opinion dynamics, fairness, and convex optimization. Indeed, the PIs believe that this is the natural next step in the evolution of social choice theory, and would represent a substantial intellectual advance in both algorithms and mechanism design.
On the experimental and evaluation side, this work will take the deliberative polling methodology developed by Co-PI Fishkin, and design tools for extending it to participatory budgeting. This project will also evaluate how deliberative polling can scale to large online communities. This is a natural next step in the evolution of deliberative democracy.
On the deployment side, this project will advance our understanding of how to design interfaces for discussion, collaboration, and voting that lead to genuine deliberation and consensus on complex problems, as opposed to devolving into vitriol like many discussion boards and comment threads.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
The goal of this project was to develop algorithms and platforms for societal decision making at scale. The project was a collaboration between three faculty members and their respective research groups: Professor Ashish Goel at Stanford (a computer scientist, and an expert in algorithms and social networks), Professor James Fishkin at Stanford (a political scientist, and expert on deliberation theory), and Professor Kamesh Munagala from Duke (a computer scientist, and an expert in the design and analysis of algorithms). As part of this project, we substantially advanced the field of social choice (the art and science of societal decision making) in both theory and practice. The mutli-disciplinary nature of this team led to advances that would not have happened in isolation, especially on the practical side.
- THEORY: We substantially advanced our algorithmic and game-theoretic understanding of voting, deliberation, and opinion dynamics for decision making at scale. Significant results include the design of markets for public decision making, developing methods for fair allocation of public resources, developing a theory of sequential decision making, and proving the best known distortion for ranking-based voting schemes in metric spaces. We mention two specific results below.
- Our work on public decision markets considers the following natural scenario: there are many yes/no issues on the ballot, and we would like to make a decision jointly on all these to maximize some notion of fairness. A natural approach, which does not directly work, is to provide each voter with a ?voting token? which he or she can then split among different issues, signaling how important that issue is to each voter. We show that this mechanism is flawed, and instead provide an alternate market design that provably maximizes a common measure of fairness, called the Nash welfare function.
- Our work on sequential deliberation shows how we can structure a decision making process as a sequence of small-group interactions. In particular, we propose and analyze the following protocol. Repeatedly pick two group-members uniformly at random, and ask them to improve the current solution that is being considered. If the two chosen members can agree on an improvement to the current solution then the improved version replaces the current solution, else the current solution remains unchanged. This kind of protocol is novel in social choice. Somewhat surprisingly, we showed that this simple protocol results in provably near-optimum solutions in a wide range of problems.
- PRACTICE: We deployed many of these algorithms in the field and conducted a rigorous evaluation. Our participatory budgeting platform (https://pbstanford.org) has been used in over 70 elections and incorporates many of the theoretical ideas we developed. We also developed a moderator bot that sits on a video-conferencing system that we also developed, and can moderate a small-group deliberation on complex societal issues. This is scheduled to be deployed in many deliberative processes in 2020, both in the US and globally. We also empirically analyzed the efficacy of different voting schemes for participatory budgeting, and developed an empirical and theoretical understanding of online advertising to recruit a diverse set of participants for civic processes.
Our ultimate vision is to bring societal decision making and deliberation to the same level of technical sophistication as web search, recommendation systems, and online advertising. This project resulted in significant progress towards that vision.
Several graduate students and postdocs were trained as a result of this project, and this research heavily influenced a new class on computational social choice at Stanford.
Last Modified: 03/12/2020
Modified by: Ashish Goel
Please report errors in award information by writing to: awardsearch@nsf.gov.
