AF: Small: A Computational Lens on Participatory Democracy

点击翻译按钮获取中文摘要

Participatory democracy is an approach to governance that emphasizes broad citizen participation, often in a way that is supported or even enabled by modern technology. Although the design of systems of participatory democracy has long been the subject of study and debate, the theme of this project is that theoretical computer science has much to bring to the table. The project explores two facets of citizen participation: allocation of public resources and selection of citizen representatives. A formal approach to address optimal and fair solutions to these two facets can potentially have a positive effect on the confidence of citizens in governing institutions that utilize these solutions.The project is divided into two main research thrusts. The first deals with participatory budgeting, a paradigm by which residents of a city or citizens of a country vote on how public resources should be allocated. Participatory budgeting has been implemented in thousands of cities around the world, and recently at national level in several countries — but the procedures being used have significant shortcomings. Indeed, participatory budgeting methods should ideally provide rigorous guarantees. This idea is beautifully captured by the notion of core solutions — outcomes that every coalition of voters prefers to what it could afford if it went it alone. Two of the research challenges focus on the existence and computation of core solutions, or of natural relaxations thereof (which are inspired by fair division). The second thrust deals with sortition — an ancient paradigm of democracy by which representatives are selected at random. After a hiatus of several centuries, sortition is being used again in the democratic process around the world. The problem of participant selection has emerged as a major sticking point, with no optimally fair solutions. One of the research challenges deals with the design of randomized participant selection algorithms that satisfy practical constraints and, simultaneously, satisfy fairness properties. Another challenge asks, in addition, for algorithms that guarantee representation for groups that are not explicitly known in advance.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.