Algorithms for Participatory Democracy

We introduce Flexible Representative Democracy (FRD), a novel hybrid of Representative Democracy (RD) and Direct Democracy (DD) in which voters can alter the issue-dependent weights of a set of elected representatives. FRD allows the voters to actively determine the degree to which the system is direct versus representative. We introduce and analyze FRD in the setting where issues are binary and symmeric and compare the outcomes of various voting systems using Direct Democracy with majority voting and full participation as an ideal baseline. First, we demonstrate the shortcomings of Representative Democracy in our model. We provide NP-Hardness results for electing an ideal set of representatives, discuss pathologies, and demonstrate empirically that common multi-winner election rules for selecting representatives do not perform well in expectation. To analyze the effects of adding flexibility, we begin by providing theoretical results on how issue-specific delegations determine outcomes. Finally, we provide empirical results comparing the outcomes of Representative Democracy, proxy voting with fixed sets of proxies across issues, and Flexible Representative Democracy with issue-specific delegations. Our results show that variants of Proxy Voting yield no discernible benefit over unweighted representatives and reveal the potential for Flexible Representative Democracy to improve outcomes as voter participation increases.

Participatory budgeting (PB) is a democratic paradigm whereby voters decide on a set of projects to fund with a limited budget. We consider PB in a setting where voters report ordinal preferences over projects and have (possibly) asymmetric weights. We propose proportional representation axioms and clarify how they fit into other preference aggregation settings, such as multi-winner voting and approval-based multi-winner voting. As a result of our study, we also discover a new solution concept for approval-based multi-winner voting, which we call Inclusion PSC (IPSC). IPSC is stronger than proportional justified representation (PJR), incomparable to extended justified representation (EJR), and yet compatible with EJR. The well-studied Proportional Approval Voting (PAV) rule produces a committee that satisfies both EJR and IPSC; however, both these axioms can also be satisfied by an algorithm that runs in polynomial-time.

We ask how a voter in a participatory budgeting process should be prompted to express their preferences. When assuming additive utilities, theoretical analysis finds clear separation in the worst case loss of common input formats, compared to the optimal social welfare under complete information. We complement this with user experiments that compare input formats based on the efficiency of their outcomes as well as how expressive and easy to use voters find the format.

By the characterization of Moulin (1980), all anonymous and strategyproof voting rules on single-peaked domains take the form of generalized median mechanisms. Recent work has identified one particular generalized median mechanism known as the uniform phantom mechanism. In this talk I describe the uniform phantom mechanism and its properties, and propose possible generalizations and extensions.

One of the most innovative aspects of blockchain technology consists in the introduction of an incentive layer to regulate the behavior of distributed protocols. The designer of a blockchain system faces therefore issues that are akin to those relevant for the design of economic mechanisms, and faces them in a computational setting. In this talk I argue for the importance of computational social choice in blockchain research and I identify a few challenges at the interface of the two fields that illustrate the strong potential for cross-fertilization between them.

Are there group decision methods which: (i) give everyone, including minorities, an equal share of effective power even when voters act strategically, (ii) promote consensus and equality, rather than polarization and inequality, and (iii) do not favour the status quo or rely too much on chance?

We describe two non-deterministic group decision methods that meet these criteria, one based on automatic bargaining over lotteries, the other on conditional commitments to approve compromise options.

Through theoretical analysis, agent-based simulations and a behavioral experiment, we show that these methods prevent majorities from consistently suppressing minorities, as with deterministic methods, and proponents of the status quo from blocking decisions as in other consensus-based approaches. These methods achieve aggregate welfare comparable to that of common methods, while employing chance judiciously.

In an experiment with naive participants, we find that a sizable fraction prefers to use a non-deterministic method over familiar Plurality Voting to allocate resources, though this depends on participants’ position within the group.

Overall, we show that the welfare costs of fairness and consensus are small compared to the inequality costs of majoritarianism.

In this talk, I give an overview of quadratic voting (also called plural voting), which is a system of voting in which voters may spend real or artificial currency in order to purchase votes, where $x$ votes costs $x^2$ currency units. In the binary, discrete case, the option with a majority of votes wins the election. I cover the intuition behind why quadratic voting leads to near-perfect efficiency in theory, assuming voters have quasi-linear utilities for saving credits. I also discuss implementations of quadratic voting in the real world, notably in the Colorado state legislature, as well as uses of quadratic voting for information elicitation (notably surveys, where it is used as an alternative to the Likert scale). Lastly, I discuss criticisms of quadratic voting and open theoretical and practical problems in the area.

Participatory Budgeting (PB) processes are often designed to span several years, with referenda for new budget allocations taking place regularly. In this talk, I will discuss a formal framework for long-term PB, based on a sequence of budgeting problems as main input. I introduce a theory of fairness for this setting, focusing on three main concepts that apply to types (groups) of voters: (i) achieving equal welfare for all types, (ii) minimizing inequality of welfare (as measured by the Gini coefficient), and (iii) achieving equal welfare in the long run. All three fairness criteria cannot be guaranteed in a single round of PB and thus necessitate a long-term perspective.

In this talk, we have first given an overview of the (relatively recent) framework of liquid/delegative democracy. Then, in the first part of the talk Arianna presented the framework of multiagent ranked delegations (what we call “smart voting”), which generalizes standard liquid democracy in two ways: (1) the agents can express more complex delegation functions to multiple other agents; (2) the agents can express a ranking over preferred delegations. We proposed four greedy unravelling procedures, and two optimal procedures, that transform the delegation profiles into “classical” voting profiles, and we studied both computational and axiomatic properties for them. Then, in the second part of the talk, Umberto focused on the case where multiple interconnected issues are to be decided upon, and the agents can delegate parts of the decision (i.e., the decision on a subset of the issues) to other agents. To this end, he presented some procedures to be used to restore or guarantee that the final ballots respect the underlying constraints. Finally, we discussed some open problems (e.g., a more refined axiomatic analysis, and the existing tension between anonymity and transparency in delegations), as well as some recent computational and experimental work that has been done for the smart voting model.

This talk surveyed uses of currency for group decision making. Currency is useful for both preference aggregation and belief aggregation, the two main components of group decision making. Both virtual and real currency can be used for preference aggregation, including trading votes, storable votes, quadratic voting, and decision auctions. Virtual and real currency is also used for belief aggregation in the form of scoring rules, prediction markets, and wagering mechanisms.

Using participatory budgeting (PB), cities give their residents an opportunity to influence how the city’s budget is spent. This is often done by collecting project proposals, and then voting on those proposals. I give a survey on work in computational social choice on this voting problem. First, I give an overview of voting systems in use in major cities, which mostly involve a naive greedy algorithm based on approval scores. Then I formalize a model of voting under a knapsack constraint with additive valuations, and discuss how standard approval votes fit in that model. Then I discuss the goal of proportional representation formalized using axioms such as Extended Justified Representation, and introduce the Method of Equal Shares. I mention PB work on the core, strategyproofness, computational complexity, and several extensions which could form directions for future research: allowing negative votes, allowing for constraints, as well as analyzing input formats and the process of agenda setting, among others.

We study a voting model with incomplete information in which the evaluation of social welfare must be based on information about agents’ top choices plus general qualitative background conditions on preferences. The former is elicited individually, while the latter is not. We apply this “frugal aggregation” model to multi-dimensional budget allocation problems, relying on the specific assumptions of convexity and separability of preferences. We propose a solution concept of ex-ante Condorcet winners which flexibly incorporates the epistemic assumptions of particular frugal aggregation models. We show that for the case of convex preferences, the ex-ante Condorcet approach naturally leads to a refinement of the Tukey median. By contrast, in the case of separably convex preferences, the same approach leads to different solution, the 1-median, i.e. the minimization of the sum of the L1-distances to the agents’ tops. An algorithmic characterization renders the latter solution analytically tractable and efficiently computable.

What if you were so enamored with formalizing social choice problems that you made all group decisions that way and even raised your kids to do so? I describe in this talk what happens. In particular, I describe the half dozen or so auction- and prediction-market-based decision mechanisms we use in our family. Additionally I describe new work at Beeminder implementing group commitment mechanisms.

In this talk I introduced an end-to-end model for participatory budgeting grounded in social choice theory. Our model accounts for the interplay between the two stages commonly encountered in real-life participatory budgeting. In the first stage participants propose projects to be shortlisted, while in the second stage they vote on which of the shortlisted projects should be funded. Prior work of a formal nature has focused on analysing the second stage only. We introduce several shortlisting rules for the first stage and analyse them in both normative and algorithmic terms. Our main focus is on the incentives of participants to engage in strategic behaviour during the first stage, in which they need to reason about how their proposals will impact the range of strategies available to everyone in the second stage. On top of the technical presentation, this talk was also a call for more realistic models for participatory budgeting, in an attempt to capture processes as they occur in real-life.

Liquid democracy is a novel paradigm for collective decision-making that gives agents the choice between casting a direct vote or delegating their vote to another agent. We consider a generalization of the standard liquid democracy setting by allowing agents to specify multiple potential delegates, together with a preference ranking among them. This generalization increases the number of possible delegation paths and enables higher participation rates because fewer votes are lost due to delegation cycles or abstaining agents. In order to implement this generalization of liquid democracy, we need to find a principled way of choosing between multiple delegation paths. We provide a thorough axiomatic analysis of the space of delegation rules, i.e., functions assigning a feasible delegation path to each delegating agent. In particular, we prove axiomatic characterizations as well as an impossibility result for delegation rules. We also analyze requirements on delegation rules that have been suggested by practitioners, and introduce novel rules with attractive properties. By performing an extensive experimental analysis on synthetic as well as real-world data, we compare delegation rules with respect to several quantitative criteria relating to the chosen paths and the resulting distribution of voting power. Our experiments reveal that delegation rules can be aligned on a spectrum reflecting an inherent trade-off between competing objectives.

Cordial Miners are a family of permissioned “blockchain consensus” protocols, with optimal instances for asynchrony and eventual synchrony. Their efficiency – almost half the latency of state-of-the-art DAG-based protocols – stems from their not using reliable broadcast as a building block. Rather, Cordial Miners use the blocklace – a partially-ordered generalization of the totally-ordered blockchain – for all algorithmic tasks required for ordering consensus: Dissemination, equivocation-exclusion, and ordering. We present the protocols within the broader context of the blocklace consensus protocol stack, offered as an alternative architectural foundation for the digital realm that is grassroots and egalitarian.

The standard setting of participatory budgeting does not treat several aspects of the problem that are relevant for certain cases and can improve the usability of such processes. I will speak about algorithms for several generalizations of participatory budgeting, in particular: a setting with project interactions in which projects are not independent; a setting with project groups in which projects have (perhaps intersecting) types; and on the possibility of fine-grained liquid democracy for participatory budgeting.

We initiate the study of incentive-compatible forecasting competitions in which multiple forecasters make predictions about one or more events and compete for a single prize. We have two objectives: (1) to incentivize forecasters to report truthfully and (2) to award the prize to the most accurate forecaster. Proper scoring rules incentivize truthful reporting if all forecasters are paid according to their scores. However, incentives become distorted if only the best-scoring forecaster wins a prize, since forecasters can often increase their probability of having the highest score by reporting more extreme beliefs. In this paper, we introduce two novel forecasting competition mechanisms. Our first mechanism is incentive compatible and guaranteed to select the most accurate forecaster with probability higher than any other forecaster. Moreover, we show that in the standard single-event, two-forecaster setting and under mild technical conditions, no other incentive compatible mechanism selects the most accurate forecaster with higher probability. Our second mechanism is incentive compatible when forecasters’ beliefs are such that information about one event does not lead to belief updates on other events, and it selects the best forecaster with probability approaching 1 as the number of events grows. Our notion of incentive compatibility is more general than previous definitions of dominant strategy incentive compatibility in that it allows for reports to be correlated with the event outcomes. Moreover, our mechanisms are easy to implement and can be generalized to the related problems of outputting a ranking over forecasters and hiring a forecaster with high accuracy on future events.

Much of the research around participatory budgeting (both theory and practice) makes an implicit assumption that only the preferences and votes of the active voters matter. Based on this assumption, there are many “guarantees” such as axiomatic properties, welfare and fairness bounds.

However in reality only a small fraction of the population actively votes, while everyone is affected by the outcome. This means that a crucial part of studying PB is about understanding and mitigating the effect of partial participation.

In the group discussion we briefly discussed two design ideas, and started to develop a model to evaluate the effect of partial participation.

The model itself involves a measure based on welfare loss, similar to the “price of anarchy” common in game theory literature. The difference is that we compare partial participation to full participation, rather than equilibrium to optimal behavior. Without further assumptions, the “cost of partial participation” may be quite high, but more nuanced results can be obtained under assumptions on the “distance” between the full and partial vote distribution.

The two suggestions we started to discuss relate to increasing the incentive to participate: Instead of using the full votes, sample a small set of voters to make the decisions. While this seems counter-productive, note that it makes every voter more pivotal and thus makes participation more attractive. Allowing the budget (which is usually assumed to be fixed) to depend on the participation rate in each region, thereby creating further reason to participate. One way to implement this indirectly is to set a minimum quorum for projects.

This working group focused on how to make the general public more aware of existing methods and platforms for collective decision-making, in order to increase the impact of COMSOC. The discussion was triggered by an app that Ayumi developed for fair division of chores in couples, which was promoted on the Japanese National TV. Indeed, some specific apps, such as Spliddit, have been quite successful (for instance, in helping with rent division), but this success has not necessarily spread to other COMSOC apps: our goal was to investigate why and to find possible avenues to change this.

Concerning the why, we first asked ourselves what was the main motivation for people to use a popular platform like Doodle: is it to make a decision for them, or just to more easily collect the information? Is it important for the users to just feel like their voice is being heard, or do they also want the experience of using the app to be “fun”? Which kind of obstacles do they perceive with existing COMSOC tools? (The latter could be an interesting question to investigate experimentally).

After some discussion, the main proposal that emerged was to create a general tool, such as a chatbot or an interactive “meta-website”, which would either be integrated to existing platforms (like on Slack or Facebook) or be independent, to guide and help the general public towards other COMSOC tools tailored to their specific problem at hand. Then, via some small-scale case studies, we could test the effectiveness of such a tool, before advertising it more broadly. A natural location for the case study would be an university, where many instances of collective decision-making arise, involving different types of agents (e.g., rent or chore division among students, creation of diverse committees, choice of journal subscriptions), and where we, as researchers, have more opportunity to have an impact.

In terms of concrete support in the development and diffusion of such a tool, we discussed the possibility for Dagstuhl itself (i.e., the Leibniz-Zentrum für Informatik) to provide help, either directly or by pointing to the right partners; or to investigate grant opportunities. To promote the tool, some options we thought of would be to write in the local university/student newspaper, and to advertise it on classical and social media (possibly via Youtube videos).

This working group explored the use of currency to improve mechanisms for collective decision making.

The group discussed a number of wide-ranging ideas, including voting using auctions, plutocracy, getting away from quasi-linear preferences, Switzerland as an unheralded but good model of democracy, sovereign coins as a grass-roots economy on blockchain, peer evaluation, peer prediction, price of anarchy for quadratic voting, use of currency to improve on envy-freeness up to one vote, a theory of investing in opposite-party candidates, allowing people to privately fund participatory-budgeting projects, allocating the public good of grant funds using lightweight methods, and whether mega-concentration of capital are important for innovation. Among these ideas, the group produced four main concrete outcomes:

First, the group discussed how to address income inequality and unfairness when real currency is used to vote. Redistribution must be part of the model. The right way to model currency in voting is in the context of the optimal taxation literature in economics. A first step would be to add quadratic voting (QV) with redistribution into the model and recompute optimal taxation. We conjecture that optimal taxes will be less due to the redistributive nature of QV.

Second, one member proposed a problem for blocklace. It’s a cooperative blockchain mining procedure called DAG-writer, instead of a competitive mining procedure, so it’s much more efficient. A good analogy is a group of runners running around a track who need to: circle the track as quickly as possible, yet stay together as a group. Another member proposed a possible solution with a preliminary analysis that it might work.

Third, a subgroup explored how to understand Uniswap, a common automated market maker (AMM) protocol responsible for trillions of dollars of transactions in cryptocurrencies, as a prediction market AMM. (This is the AMM that Manifold Markets uses.) There is a large literature on prediction market AMMs. A natural question is whether Uniswap is equivalent to a known AMM. This subgroup made some progress in rewriting the Uniswap price function as a cost function in the AMM literature. The Uniswap price function has some advantages for combinatorial prediction markets that no other known price function has.

Fourth, the group considered a liquid democracy model where voting records are public and voters delegate (probabilistically) to more historically accurate voters on binary issues. Society enacts a weighted average of the votes on each issue. Does society act as a no-regret learning algorithm? That is, are the decisions of society competitive with the single best voter?

The idea of this working group was to have a general discussion about participatory budgeting (PB). It started from some considerations on how fairness should be defined in the context of PB. It evolved from there into a more general exchange about the more fundamental focus of PB. In the present report, we elaborate on the different points that have been discussed.

The standard model used to describe PB elections can actually be seen as the more general task of collective selection of costly alternatives. With that in mind, several real-life scenarios can be captured through the study of “PB”, for which the goals will be quite different. Let us present three typical ones.

• $\mathrm{■}$

  The usual PB election: A set of voters express their preferences over a set of costly alternatives in order to decide which ones to implement, under some budget constraint. Voter turnout is a crucial issue here (at least for the decision-makers). In that view, trying to fairly represent the diversity of voters is an important goal.

• $\mathrm{■}$

  Grant selection: A committee (the voters, actually) has to decide on behalf of a funding agency which research proposals to fund subject to a budget limit. As opposed to the above, voter participation is definitely not an issue. Similarly, a property such as exhaustiveness⁶⁶6Exhaustiveness states that it should not be possible to still fund an extra project with the leftover budget. – considered highly important in PB elections – needs not be relevant here.

• $\mathrm{■}$

  Selecting the catering options for an event: A group of organizers has to decide on the catering options offered for an event. The typical goal here would be to find cheap solutions that cover a large number of guests. In that sense, exhaustiveness is probably not desirable, but proportionality-like requirements might be.

These three examples already display a wide variety of scenarios. In the following we will only focus on PB elections, but the other examples also deserve to be studied.

One of the most fundamental questions we touched upon is that of the actual goal of a PB election. Two general approaches emerged from our discussion.

The first one is to consider PB processes as a way to inform and help decision makers with selecting which projects to fund. The idea is that PB processes help reveal the societal value of the alternatives that can then be used to make an informed decision. In this view, concepts relating to proportionality enforce selecting high societal value projects (cohesive groups can be seen as indication of high societal value). This approach also calls for an epistemic analysis where there exists a ground truth societal value for the projects, that we are trying to approximate.

Another goal for PB is that of educating citizens to the democratic process. One motivation for this is to consider PB as a way to attract citizens to democratic instances (if you engage in the PB process, then you might also engage in other democratic activities). Another aspect here could be to force citizens to think about budget constraints in general, to give them a taste of decision-making with scarce resources. This approach seems harder to account for within the social choice literature.

Given all the above, it is not surprising that fairness requirements such as proportionality are the ones that received the most attention in the current social choice literature about PB. However, it is still unclear what exactly fairness should be about. A large part of our discussion focused on this issue.

The current literature focuses mainly on satisfaction-based fairness. It can be argued that satisfaction cannot really be captured, especially when using approval ballots, and that we would thus need different kinds of fairness requirements. Several directions are opened here. One such idea could be to study equity of resources in PB, via the concept of share, see for instance [2]. A requirement that already exists in the literature and that could be explored further is IPSC [1], which is not a satisfaction-based criterion. Finally, another approach that is worth pursuing is that of market-based fairness, which has been operationalized via the idea of priceability, see for instance [3].

The objections about satisfaction-based fairness we made above are all within the context of approval voting. Another point of discussion was to challenge the use of approval ballots. Indeed, it could be that they are just too simplistic to allow for convincing fairness definitions. In that regard, exploring other types of ballots would be interesting. On the one hand, we could investigate more complex ballots to get closer to the voters’ preferences. On the other hand, we could also look into very simple ballots with clear semantics (the semantics of approval ballots is ambiguous), such as 1-approval ballots: voters are only allowed to approve of one alternative.

Studying 1-approval ballots could teach us about the fundamentals of fairness in PB. For the same reason, it would be worth studying the other end of the spectrum: weak orders over feasible subsets of alternatives. This is, of course, not a practical model, but developing a study of fairness with perfect information about the voters’ preferences could lead to a deeper understanding of what is happening in PB.

Reaching a deeper understanding of fairness in PB could also lead to new appealing mechanisms. At the moment, the method of equal shares [3] stands out as the uncontested mechanism to go for (at least when it comes to fairness). This fact is somehow surprising – for multi-winner voting, we know of several mechanisms providing strong fairness guarantees – and probably indicates that there is more to look for here.