How Should We Vote? A Comparison of Voting Systems within Social Networks

1 Introduction

One person, one vote; is this the best way to run elections? This paper explores whether new methods can lead to high quality election outcomes while requiring less effort from voters. Paradigms of voting such as liquid democracy and sortition aim to apply modern understanding to centuries-old social choice methods. Liquid democracy [Blum and Zuber, 2016] tries to make use of expert knowledge by allowing voters to transitively delegate their vote on issues they feel less informed of or less interested in. Sortition [Dowlen, 2017] involves selecting a subset of voters to participate in the election to reduce the effort required of the total voter population while maintaining desired properties such as fairness or representation of subgroups [Flanigan et al., 2021]. In both systems only a subset of voters are fully active in the election, in contrast to direct democracy where all voters participate equally.

We examine these paradigms within a binary ground truth setting. That is, voters are asked to choose between two options - one correct and one incorrect - and all wish to choose the correct option. An election might be any question being asked of a group where an objectively measurable truth exists, such as a trial where a jury is asked whether a defendant is innocent or guilty [Forsyth, 1852], or an investors meeting where attendants are asked whether a stock will have a higher or lower price 30 days in the future. In some cases, voters may be unsure of, e.g., whether a stock price will rise, and will prefer to rely on someone whose expertise they trust by delegating their vote. In other cases, an organization selecting participants in an election from a larger pool may know that some voters bring more expertise than others and will try to select such voters, as in jury selection.

These settings are examples of group decision-making. In many such settings - particularly in rapidly growing online communities - attention is a scarce resource. Communities need to find methods of coping with the increased burden of governance as they grow. Liquid democracy and sortition allow the community to balance the number of individuals making participating with the attention the group is willing to put towards governance.

Voters in the above example situations have their own knowledge, understanding, and biases that affect the likelihood that they will select the correct outcome. It is natural to model this by viewing each participant as able to contribute some noisy evaluation of the ground truth. Understanding the dynamics that affect the accuracy of an entire group's decision are key to both anyone running an election and anyone participating in such an election.

Some papers in the literature have provided primarily theoretical results showing, e.g., the conditions under which liquid democracy can reliably improve the decision-making ability of a group [Kahng et al., 2018], or that perfectly optimizing delegations to maximize the ability of a group to identify ground truth is NP-Hard [Caragiannis and Micha, 2019]. Here we focus on understanding the practical factors affecting the accuracy of the decision-making ability of a group that employs either liquid democracy or sortition. To allow for a more intuitive understanding, and due to the difficulty of analytically analysing the situations we are interested in, we focus our efforts on computer-based simulation results and expand upon our previous work [Alouf-Heffetz et al., 2022].

The primary question we seek to answer is: What factors affect the quality of the group decision when using liquid democracy or sortition? To answer this question, we explore a model in which voters exist within a social network. In modern times, the exponential increase in size and prevalence of social networks allows us to consider the social structure as a given fact for many social choice settings. Additionally, we use a single parameter that denotes the voters' competency, which is their intrinsic probability of selecting the correct outcome. Within this model we compare the ability of direct democracy, sortition, and liquid democracy to uncover ground truth.

Our results demonstrate that achieving better accuracy than direct democracy is achievable as long as there is some method to approximate the relative competence of voters, in which case, it is possible to run a highly accurate election where only a fraction of voters must actively participate. Our experiments found consistent results across both artificial and real social networks. Furthermore, we show there is no clear correlation between the properties of a social network and group accuracy. Lastly, we find that a version of simulated annealing for Liquid Democracy approaches the optimal distributions of delegations among voters. This was not easy to foresee as finding optimal delegations is NP-Hard, therefore it seems that the annealing algorithms rather quickly find states that yield much higher accuracy than other forms of liquid democracy.

The remainder of the paper is organized as follows. This section finishes with a look at the related work while Section 2 describes our model in greater depth. Section 3 introduces our experimental design including the specific voting rules we explore and the parameters we analyze. We describe the experiments that we run and discuss their results in Section 4. Section 5 concludes and briefly describes possible future work.

1.1 RelatedWork

Voting systems. Forms of direct democracy and sortition [Sintomer, 2018] were originally practiced well over 2000 years ago in Athens [Tridimas, 2017]. Liquid democracy is comparatively recent, having roots in Charles Dodgson's work in the 19th century [Dodgson, 1884]. Most recent works on these voting systems in the AI and computational social choice communities has focused on worst case performance scenarios or improving their fairness properties (see [Caragiannis and Micha, 2019], [Escoffier et al., 2018], and [Kahng et al., 2018]).

Liquid democracy. In recent years liquid democracy has been adapted for use by several political parties. This has been most well documented in the case of the LiquidFeedback software [Kling et al., 2015]; a recent overview is also found in [Paulin, 2020]. Liquid democracy [Blum and Zuber, 2016] is usually studied for settings with a ground truth, in which its worst-case performance is theoretically analyzed. Kahng et al. [2018] have shown that, to guarantee a superior group accuracy from liquid democracy than from direct democracy, voters must have access to non-local information. Caragiannis and Micha [2019] have shown that finding optimal delegations is NP-Hard. These hardness results were strengthened by Becker et al. [2021], who presented simulations showing that, under particular settings, various delegation methods are able to lead to a more accurate result than direct democracy. They also apply an optimization process to delegations to achieve a similar result as our simulated annealing, albeit without exploration of the similarity of the result to optimal weights. Bloembergen et al. [2019] have considered a game-theoretic model of liquid democracy where each voter has a "type" and competency is construed as the ability of a voter to identify and communicate their own type.

Sortition. Sortition is typically studied in a setting focused on aspects other than decision accuracy. In particular, Benade et al. [2019] have shown that sortition guarantees fair representation of subsets of a population. Similarly, Flanigan et al. [2021] developed several algorithms that select sortition participants to optimally balance between equal selection probability for each voter and accurate representation of the underlying population. We primarily focus on sortition as a voting system that is easy to implement but, since it requires only a subset of the voters to actively participate in the election, minimizes the collective effort of voting.

Voter competence. Relatively little work has focused on understanding the effects of voter competency distributions on the outcome of elections. Grofman [1983] studied direct democracy in a binary ground truth setting; several of their theorems can be viewed as extensions of the Condorcet Jury Theorem. Nitzan and Paroush [2017] summarize the long history of research into jury theorems.

2 Model

Competence networks. We consider a basic social choice setting with n agents, V " tv1, . . . , vnu, and two alternatives A " ta`, a´u. Our focus is on a ground truth voting scenario where a` is the objectively correct outcome that the agents collectively aim to elect. However, each voter vi P V has a competency level qi P r0, 1s that corresponds to the probability vi would vote "correctly" (i.e., would vote for a`). 1

The agents are connected via an underlying social network, thus we have a set of undirected edges E, representing the connections between the agents. Combining the ingredients of our setting, our basic mathematical object is a so-called competence network, which is an undirected labeled graph G " pV,Eq, where V " tv1, . . . , vnu, and each vertex vi P V acts as voter and is labeled with its competence value qi. We thus use agents, voters, and vertices interchangeably.

Voting Systems. A voting system defines a process that operates on a competence network and defines how the agent groups make their joint binary decision. Formally speaking, a voting system takes as input a competence network and outputs a winner, which is either the correct alternative a` or the incorrect alternative a´. As we always have exactly two alternatives we use a weighted majority voting system. Each voter that votes in an election commits their weight to a single alternative and the alternative with the most weight is the winner.

1 Note that we do not require qi ¥ 0.5. Caragiannis et al. [2019] point out that qi � 0 might indicate a strongly held incorrect belief. It is possible that a voter with qi � 0.5 prefers to delegate to a voter with even lower competency, thus inducing an echo-chamber dynamic. However, we agree with the view proposed by Becker et al. [2021] that there exist objective indications of competency that all voters recognize.

Elections. An election is a competence network pairedwith a voting system. When the election is run the voting system is used on the competence network and results in a winning alternative. We refer to the probability that a` will be chosen as the accuracy of the election.

3 Experimental Design

In this section we describe our experimental setup and the details of each voting system we use. In particular, the steps we follow in each experiment are as follows:

1. We create the underlying network that connects the agents.
2. We assign competence levels to the voters in the network.
3. We choose and use a voting system.
4. As our setting is probabilistic, we estimate the outcome of the election.

3.1 Voting Systems

We consider several variants of sortition and liquid democracy, as well as direct democracy, which we use as a benchmark. Note that in direct democracy all voters actively participate in the election by voting. In contrast, in sortition and liquid democracy only a subset of the voters actively vote.

Definition 1. An active voter is one whose choice of alternative is considered when computing the winner of the election. The set of active voters is denoted V active .

Direct democracy. In direct democracy, all voters actively vote. That is, in direct democracy, every voter vi votes with equal weight for either a` or a´, where vi chooses a` with probability equal to qi. The winning alternative is the one that receives the most votes. Throughout the paper, ties are broken in favour of a`.

Sortition. In sortition, only a subset of the voters are active and all those are given equal weight while all other voters do not participate in the election at all and do not affect the outcome. There are many variants of sortition, corresponding to the method by which the set of active voters is selected. Here we consider sortition as it might be used for a task such as jury selection, where some individuals could be considered more competent than others, rather than the sortition used in citizen's assemblies where the goal is to most accurately represent the underlying population. Sortition works best if the set of active voters are exactly those voters who are the most competent. As it may not be possible to accurately estimate the competence levels of voters, we consider the following, parameterized variant.

Definition 2. ρ-noisy sortition is a method of sortition in which all voters are sorted in descending order of competence. Then, beginning from the most competent voter, in each iteration i P r1, ..., ns, with probability ρ P r0, 1s, the ith voter is swapped with one of the voters from the ti ` 1, .., nu, chosen uniformly at random. Finally, the first k voters are selected as the set of active voters (and other voters are disregarded).

Observe that, for ρ " 0, the ρ-noisy sortition variant is equivalent to selecting the k most accurate voters (i.e., pure meritocracy); while, for ρ " 1, it is equivalent to selecting k voters uniformly at random (i.e., pure sortition).

Liquid democracy. In liquid democracy, like in sortition, there is a set of active voters; however the other voters are not disregarded. Each voter chooses whether to actively vote or to delegate to another voter of their choice, and these delegations are transitive (e.g. If v1 delegates their vote to v2 then v2 can vote with a weight of 2 or can instead delegate their vote as well as v1's vote to v3.). Each active voter has a set of voters who delegate (either directly or transitively) to them. In contrast to sortition, the voting weight of each active voters is not the same, but is equal to the number of delegations they receive (either directly or transitively), plus one (for their own vote).

In our simulations, each voter has an equal chance of being chosen to be an active voter, based upon an experiment parameter. For the delegations of the nonactive voters, we use the following variants:

• Liquid Better: For each nonactive voter vi, we select one of their neighbours uniformly at random, among the neighbours with higher competence than vi. That is, vi delegates to a random voter from the set tj P N ` G piq |qj ą qi, pi, jq P Eu where N ` G piq " tj P V | pi, jq P E , qj ą qiu.
• Liquid Max: For each nonactive voter vi, we select their delegate to be their most competent neighbour.

In liquid democracy computing the delegations that result in the highest probability of the resulting group decision being correct is NP-hard [Caragiannis and Micha, 2019]. For this reason, we also consider a heuristic approach that takes a competence network as input and aims to find the accuracymaximizing partition of voters into active/nonactive sets and set of delegations for those nonactive voters. Our heuristic is based on the popular local search heuristic of simulated annealing (SA).

In our implementation of SA, we begin with either existing delegations (Experiments 1 and 2), or a state with no delegations (Experiment 4), then make a single, randomly chosen, local delegation change at each time step. If the delegation leads to a higher group accuracy that state is accepted, otherwise the state is accepted probabilistically based on the difference between accuracies of the old and new states. If si is the state after i steps of annealing and scurrent the current state, the probability of accepting a new state is expp´pscurrent ´ siq{Tq. In all our experiments we hold T constant at 1.0 and use the basinhopping function within the SciPy library to implement simulated annealing [Virtanen et al., 2020]. For a detailed overview of simulated annealing see the overview in [Dowsland and Thompson, 2012] or [Wales and others, 2003] for more detail on basin-hopping.

3.2 Network Generation

We use both real-world and artificially-generated networks.

Real-world networks. We have explored an array of realworld networks from the SNAP database [Leskovec and Krevl, 2014] and included a real-world instance that is a sampled network of Facebook users with 534 nodes and 9626 edges.

Artificial networks. We use the following two classical probabilistic models for generating artificial networks, which are often used to replicate properties of real-world social networks (see, e.g., the overview of Kleinberg [2010]): (1) Erd˝os-R´enyi (ER): ER networks are parameterized by two parameters-the number n of nodes and the connection probability p-and are generated by initializing an empty network of n nodes and inserting each possible edge with the fixed connection probability p, independently [Erdos et al., 1960]; and (2) Barab´asi-Albert (BA): BA networks are parameterized by one parameter m and are generated via a preferential attachment process where nodes are added one at a time and connected to m of the existing nodes where the probability of an existing node to be connected to the current node is proportional to its degree [Albert and Barab´asi, 2002].

3.3 Competence Assignment

Given a network G " pV,Eq generated via one of our network generation processes, we use different probability distributions to assign competence levels to the voters V " tv1, . . . , vnu in the network.

In particular, in our experiments we select some distribution D from which we draw voter competencies, so that for each vi P V we sample a value qi " D. That is, the competence levels are chosen independently for each voter. In particular, we consider the following families of distributions:

• uniform distributions;
• truncated normal distributions; 2 and
• truncated exponential distributions. 3

3.4 Accuracy Calculation

Recall that the accuracy of an election is the probability that the correct alternative a` will be selected. The accuracy of a given election can be computed using dynamic programming with a table of size O `n2 ˘ [Becker et al., 2021]. However, our preliminary experiments with this algorithm found it expensive in memory and time (particularly with well connected networks of several hundred nodes or more). Therefore in our experiment we use an approximation algorithm, based on Monte Carlo simulation [Mooney, 1997]. Concretely, we proceed by performing 1000 iterations. In each iteration we sample the votes of the voters using their competence values (so that a voter vi with competence value qi is voting for a` with probability qi), and then use the voting system with these votes. Finally, we take the fraction of iterations resulting in a` winning as our estimate of the accuracy of the election. This method proved to be computationally efficient and highly accurate in estimating the accuracy of our elections.

2 We use the SciPy implementation of the truncated normal distribution [Burkardt, 2014].

3 Since the exponential distribution does not provide an upper bound on sampled values whenever we sample a competency value greater than 1 we map the value to 1. This leads to a mean value slightly lower than the original distribution, i.e µ1 � 1λ � e�λ λ .

4 Results and Discussion

Here we describe the specific experiments we have performed. For each experiment, we describe its experimental design, show its results, and discuss them. The goal of our experiments is to identify the conditions under which each voting system is most useful. That is: are there particular competency distributions, network structures, or levels of voter participation where any system give higher or lower accuracy?

Our simulation code is written in Python and run using Python 3.8. We use Matplotlib [Hunter, 2007] to visualize our data, and Scikit [Virtanen et al., 2020] for our statistical analysis. In all our experiments we study voters with an average competency of 0.5 in order to demonstrate the ability of liquid democracy and sortition to utilize expert knowledge.

4.1 Experiment 1: Fraction of Active Voters

In this experiment we concentrate on how the number of active voters affects the accuracy of the group decision. We consider networks of 100 and 1000 voters, all with an average degree of approximately 20. For BA networks, we set m " 10 and in ER networks p " 0.20202 (p " 0.02002) for networks of 100 (1000) voters. Voter competencies are sampled as follows for each distribution:

• (i) Uniform - @i : qi " U p0.3, 0.7q
• (ii) Gaussian - @i : qi " N p0.5, 0.1q
• (iii) Exponential - @i : qi " Exp p2q

We use ρ " 0.1 for our ρ-noisy sortition model and report the average result of 10 trials.

In each individual plot of Figure 1, which shows the results of this experiment, the X-axis shows the portion of active voters used, ranging from 10% to 90%. The Y -axis shows the resulting group accuracy.

Discussion. Whenever the fraction of active voters is low (corresponding to the left side of the plots in Figure 1), the possible variance of delegation is higher as there are more nonactive voters. Interestingly, whenever more than half of the voters delegate (i.e., when the fraction of active voters is less than half) the accuracy achieved by Liquid Better is very close to that of Liquid Max. This means that even though Liquid Better only requires the nonactive voters to find a delegate who is more competent than themselves, it still is able to elicit the "experts" of the network. Observe also that both Liquid Better and Liquid Max achieve group accuracy levels very close to that of the SA solution. Moreover, all methods are significantly better than direct democracy. Lastly, note that due to the asymmetry of exponential distribution the differences described above are magnified. More than half of the voters have a competence below 0.5 so direct democracy approaches an accuracy of 0 when the number of voters increases and the room for improvement from delegation or sortition increases dramatically.

4.2 Experiment 2: Variance of Competencies

Here we consider the effect that the variance of voter competence has on the group accuracy. In particular, we keep the mean competency constant at 0.5 and slowly increase the variance. The results of this experiment are shown in Figure 2. Note that, as the exponential distribution accepts only a single parameter, that affects both the mean and the variance, in this experiment we consider only the uniform and the Gaussian distributions. We consider 20 uniform distributions with upper and lower bounds evenly-spaced between Up0.475, 0.525q to Up0, 1q, and 20 Gaussian distributions with σ P t0.05, 0.5u. We average all results over 10 trials. In all cases 90% of voters are active.

Discussion. Figure 2 shows, particularly with more voters present, that having even just 10% of voters delegating or left out by sortition can lead to a dramatic increase in accuracy. This suggests that indirect voting methods are very well suited to situations where expert knowledge exists; as the higher the competence variance is the higher the number of voters with very high competency.

4.3 Experiment 3: Optimizing Delegations and Active Voter Weight

Here we investigate the performance of simulated annealing over time. In particular, we first run the heuristic and record the accuracy it obtains as more iterations are being made.

We also complement our analysis by comparing the specific vote weights that result from using the heuristic to a theoretical result from the literature. In particular, Grofman et al. [1983, Theorem XIII] consider weighted direct democracy and show that in a binary ground-truth setting such as in ours, in order to maximize the accuracy of direct democracy, the weight of each voter vi with competence level qi shall be proportional to logp qi 1´qi q. We thus set to investigate whether our SA heuristic find delegations that result in vote weights of the active voters that are getting closer to the theoretical optimum of Grofman et al. To this end, we proceed by examining the set of active voters selected by SA, each 10 iterations of SA, as follows:

• (i) Calculate the normalized optimal weight 1n logp qi 1´qi q@i P V active . Sort the results in descending order and denote them by wopt .
• (ii) Define w˚ as the normalized actual weights of all active voters induced by SA and sort them in descending order.
• (iii) Finally, calculate the L2 distance between the two weight vectors, L2 " bΣiPV active `wopt i ´w˚ i ˘2 .

The results of this experiment are shown in Figure 3

Discussion. By comparing to the optimal weights described by Grofman et al., this experiment indicates how well annealing does at finding optimal delegations. When the L2 distance from optimal weights is low the delegations are more closely approximating the optimal weight distribution among active voters. And, indeed, we do see in Figure 3 that the best solution found by annealing approaches to the optimal weights of Grofman et al. [1983]. Interestingly, the figure also shows that there are delegations found by annealing with high accuracy that are very dissimilar to the optimal weight distribution.

4.4 Experiment 4: Sortition

To better understand the effect of different values of ρ in our model of sortition we ran an experiment considering several competency distributions over a wide range of ρ. These included two Gaussian distributions with σ " 0.1 and 0.5, two uniform distributions ranging from 0.4 ´ 0.6 and 0.1 ´ 0.9, and an exponential distribution created as in previous experiments. As in previous experiments, all distributions have a mean competency of 0.5. We ran simulations with these values and examined the outcome of sortition when selecting 10%, 25%, and 50% of the voters to actively participate. Figure 4 presents the results of this experiment.

Discussion. In general, the results are approximately as expected: As ρ increases, the most competent voters are more likely to be swapped for less competent voters and accuracy decreases. Interestingly, different distributions respond differently to changes in the fraction of active voters. For example, when ρ is low, the low variance uniform distribution is more accurate when 50% of voters are active than when 10% are active. In contrast, as ρ increases, the exponential distribution loses accuracy more quickly with more active voters. These differences reflect the relative difference between competent and incompetent voters in each distribution. An additional voter from the low variance uniform distribution (which has a minimum competency of 0.4) can do much less "harm" than an additional voter from the exponential distribution (which has a minimum competency of 0).

4.5 Experiment 4: Network Properties

We now set to examine how different network properties affect accuracy. To this end, we have fixed the competency distribution and the chance of active participation and ran elections on each network type. Then, we calculated the following properties: mean degree, mean neighbour degree, connectivity, clustering coefficient, radius, and diameter. Figure 5 show the comparison between the average degree of voters in an ER network and group accuracy, using a Gaussian competency distribution with µ " 0.5, σ " 0.2. We considered 99 ER networks with attachment parameters uniformly distribution between 0.1 and 0.99 and each data point represents the mean of 30 elections. We also performed similar experiments on BA networks; all experiments for each property found results similar to those in Figure 5.

Discussion. None of the network properties we considered exhibited a strong relationship with group accuracy. We only observed a very small drop in the accuracy of liquid democracy in some extremely sparse networks. Of course, as with previous experiments, sampling from different competency distributions on the same network affects the accuracy but such variations appear unrelated to any network parameter within the family of ER and BA networks we examined. We believe we did not observe any relationship between network properties and accuracy because only a bare minimum of connectivity is required for delegation to be maximally effective. This strongly suggests that any real social network structure would not be a hindrance to the benefits of liquid democracy.

4.6 Summary

The overarching message from our experiments is that if voter competency can be identified then direct democracy is unlikely to be the most accurate decision-making mechanism. When a coordinator is able to identify competency with high accuracy sortition is an excellent tool and liquid democracy performs well even when voters are only able to recognize another voter's relative competence. Liquid democracy has proven itself robust to variations in network structure as long as the network is sufficiently connected and we have also seen its ability to effectively utilize expert knowledge when a majority of voters have low competency..

5 Conclusion

We started this paper with the question "One person, one vote; is this the best way to run an election?". In the context studied here we believe that our findings conclusively show that the answer to this question is "No". All of our results combine to show that liquid democracy and sortition are both highly effective tools for uncovering ground truth. Furthermore, we believe that our experiments also serve to demonstrate that these social choice paradigms are well suited for empirical use across many settings.

Our work opens up many avenues for future research. Our results were empirical and formalizing the relationship, for example, of the trade-off between accuracy and the portion of active voters could provide deeper insight into the problem. Furthermore, we assumed that voters with qi ă 0.5 will choose more competent delegates. However, in the face of disinformation this may not be the case, and exploring the resulting echo-chamber dynamics and methods for combating such an issue may prove important.