# liquid_democracy_an_algorithmic_perspective__1ef8ac0d.pdf

Liquid Democracy: An Algorithmic Perspective

Anson Kahng Computer Science Department Carnegie Mellon University akahng@cs.cmu.edu

Simon Mackenzie Computer Science Department Carnegie Mellon University simonm@andrew.cmu.edu

Ariel D. Procaccia Computer Science Department Carnegie Mellon University arielpro@cs.cmu.edu

We study liquid democracy, a collective decision making paradigm that allows voters to transitively delegate their votes, through an algorithmic lens. In our model, there are two alternatives, one correct and one incorrect, and we are interested in the probability that the majority opinion is correct. Our main question is whether there exist delegation mechanisms that are guaranteed to outperform direct voting, in the sense of being always at least as likely, and sometimes more likely, to make a correct decision. Even though we assume that voters can only delegate their votes to better-informed voters, we show that local delegation mechanisms, which only take the local neighborhood of each voter as input (and, arguably, capture the spirit of liquid democracy), cannot provide the foregoing guarantee. By contrast, we design a nonlocal delegation mechanism that does provably outperform direct voting under mild assumptions about voters.

1 Introduction

Liquid democracy is a modern approach to voting in which voters can either vote directly or delegate their vote to other voters. In contrast to the classic proxy voting paradigm (Miller 1969), the key innovation underlying liquid democracy is that proxies who were selected by voters to vote on their behalf may delegate their own vote to a proxy, and, in doing so, further delegate all the votes entrusted to them. Put another way (to justify the liquid metaphor), votes may freely flow through the directed delegation graph until they reach a sink, that is, a vertex with outdegree 0. When the election takes place, each voter who did not delegate his vote is weighted by the total number of votes delegated to him, including his own. In recent years, this approach has been implemented and used on a large scale, notably by eclectic political parties such as the German Pirate Party (Piratenpartei) and Sweden s Demoex (short for Democracy Experiment).

One reason for the success of liquid democracy is that it is seen as a practical compromise between direct democracy (voters vote directly on every issue) and representative democracy, and, in a sense, is the best of both worlds. Direct

Copyright c 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

democracy is particularly problematic, as nicely articulated by Green-Armytage (2015):

Even if it were possible for every citizen to learn everything they could possibly know about every political issue, people who did this would be able to do little else, and massive amounts of time would be wasted in duplicated effort. Or, if every citizen voted but most people did not take the time to learn about the issues, the results would be highly random and/or highly sensitive to overly simplistic public relations campaigns.

By contrast, under liquid democracy, voters who did not invest an effort to learn about the issue at hand (presumably, most voters) would ideally delegate their votes to wellinformed voters. This should intuitively lead to collective decisions that are less random, and more likely to be correct, than those that would be made under direct democracy.

Our goal is to rigorously investigate the intuition that liquid democracy outperforms direct democracy from an algorithmic viewpoint. Indeed, we are interested in delegation mechanisms, which decide how votes should be delegated based on how relatively informed voters are, and possibly even based on the structure of an underlying social network. Our main research question is

... are there delegation mechanisms that are guaranteed to yield more accurate decisions than direct voting?

Overview of the Model and Results

We focus on a (common) setting where there a decision is to be made on a binary issue, i.e., one of two alternatives must be selected (see Section 5 for a discussion of the case of more than two alternatives). To model the idea of accuracy, we assume that one alternative is correct, and the other is incorrect. Each voter i has a competence level pi, which is the probability he would vote correctly if he cast a ballot himself.

Voters may delegate their votes to neighbors in a social network, represented as a directed graph. At the heart of our model is the assumption that voters may only delegate their votes to strictly more competent neighbors (and, therefore, there can be no delegation cycles). Specifically, we say that

The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)

voter i approves voter j if pj > pi + α, for a parameter α 0; voters may only delegate to approved neighbors. In defense of this strong assumption, we note that the first of our two theorems arguably the more interesting of the two is an impossibility result, so assuming that delegation necessarily boosts accuracy only strengthens it.

As mentioned above, we are interested in studying delegation mechanisms, which decide how votes are delegated (possibly randomly), based on the underlying graph and the approval relation between voters. We pay special attention to local delegation mechanisms, which make delegation decisions based only on the neighborhood of each voter. Local mechanisms capture the spirit of liquid democracy in that voters make independent delegation decisions based solely on their own viewpoint, without guidance from a central authority. By contrast, non-local mechanisms intuitively require a centralized algorithm that coordinates delegations.

Recall that our goal is to design delegation mechanisms that are guaranteed to be more accurate than direct voting. To this end, we define the gain of a mechanism with respect to a given instance as the difference between the probability that it makes a correct decision (when votes are delegated and weighted majority voting is applied) and the probability that direct voting makes a correct decision on the same instance. The desired guarantee can be formalized via two properties of mechanisms: positive gain (PG), which means that there are some sufficiently large instances in which the mechanism has positive gain that is bounded away from 0; and do no harm (DNH), which requires that the loss (negative gain) of the mechanism goes to 0 as the number of voters grows. These properties are both weak; in particular, PG is a truly minimal requirement which, in a sense, mainly rules out direct voting itself as a delegation mechanism.

In Section 3, we study local delegation mechanisms and establish an impossibility result: such mechanisms cannot satisfy both PG and DNH. In a nutshell, the idea is that for any local delegation mechanism that satisfies PG we can construct an instance where few voters amass a large number of delegated votes, that is, delegation introduces significant correlation between the votes. The instance is such that, when the high-weight voters are incorrect, the weighted majority vote is incorrect; yet direct voting is very likely to lead to a correct decision.

In Section 4, we show that non-local mechanisms can circumvent the foregoing impossibility. Specifically, we design a delegation mechanism, GREEDYCAP, that satisfies the PG and DNH properties under mild assumptions about voter competencies. It does so by imposing a cap on the number of votes that can be delegated to any particular voter, thereby avoiding excessive correlation.

In conclusion, our work highlights the significance, and potential dangers, of delegating many votes to few voters. Importantly, there is evidence that this can happen in practice. For example, Der Spiegel reported1 that one member of the

1http://www.spiegel.de/international/germany/liquid-

German Pirate Party, a linguistics professor at the University of Bamberg, amassed so much weight that his vote was like a decree. Although recent work by Kling et al. (2015) highlights the fact that, in practice, high-weight voters vote reasonably and do not abuse their power, our results corroborate the intuition that this situation should ideally be avoided.

Related Work

There is a significant body of work on delegative democracy and proxy voting (Miller 1969; Tullock 1992; Alger 2006). In particular, Cohensius et al. (2017) study a model where voters positions on an issue are points in a metric space. In their version of direct democracy, a small subset of active voters report their positions, and an aggregation method (such as the median or mean when the metric space is the real line) outputs a single position. Under proxy voting, each inactive voter delegates his vote to the closest active voter. Cohensius et al. identify conditions under which proxy voting gives a more accurate outcome than direct voting, where the measure is proximity of the outcome to the aggregation method applied to all voters positions.

To the best of our knowledge, there are only two papers that provide theoretical analyses of liquid democracy. The first is the aforementioned paper by Green-Armytage (2015). He considers a setting where, similarly to Cohensius et al. (2017), voters are identified with points on the real line, but in his model votes are noisy estimates of those positions. Green-Armytage defines the expressive loss of a voter as the squared distance between his vote and his position and proves that delegation (even transitive delegation) can only decrease the expressive loss in his model. He also defines systematic loss as the squared distance between the median vote and the median position, but discusses this type of loss only informally (interestingly, he does explicitly mention that correlation can lead to systematic loss in his model).

The second paper is by Christoff and Grossi (2017). They introduce a model of liquid democracy based on the theory of binary aggregation (i.e., their model has a mathematical logic flavor). Their results focus on two problems: the possibility of delegation cycles, and logical inconsistencies that can arise when opinions on interdependent propositions are expressed through proxies. Both are nonissues in our model (although the need to avoid cycles is certainly a concern in practice).

Further afield, there is a rich body of work in computational social choice (Brandt et al. 2016) on the aggregation of objective opinions (Conitzer and Sandholm 2005; Conitzer, Rognlie, and Xia 2009; Elkind, Faliszewski, and Slinko 2010; Xia, Conitzer, and Lang 2010; Xia and Conitzer 2011; Lu and Boutilier 2011; Procaccia, Reddi, and Shah 2012; Azari Soufiani, Parkes, and Xia 2012; 2013; Mao, Procaccia, and Chen 2013; Caragiannis, Procaccia, and Shah 2014; 2016; Procaccia, Shah, and Zick 2016). As in our work, the

democracy-web-platform-makes-professor-most-powerfulpirate-a-818683.html

high-level goal is to pinpoint the correct outcome based on noisy votes. However, previous work in this area does not encompass any notion of vote delegation.

2 The Model

We represent an instance of our problem using a directed, labeled graph G = (V, E, p). V = {1, . . . , n} is a set of n voters, also referred to as vertices (we use the two terms interchangeably). E represents a (directed) social network in which the existence of an edge (i, j) means that voter i knows (of) voter j.

We assume that the voters vote on a binary issue; there is a correct alternative and an incorrect alternative. Each voter i V is labeled by his competence level pi. This is the probability that i has the correct opinion about the issue at hand, i.e., the probability that i will vote correctly.

Our setting is also parameterized by α [0, 1). Given this parameter and a labeled graph G = (V, E, p), we define an approval relation between voters: i V approves j V if (i, j) E and pj > pi + α. In words, i approves his neighbor j if the difference in their competence levels is strictly greater than α. The strict inequality guarantees that the approval relation is acyclic. Denote

AG(i) = {j V : i approves j}.

Delegation Mechanisms

The liquid democracy paradigm is implemented through a delegation mechanism M, which takes as input a labeled graph G, and outputs, for each voter i, a delegation probability distribution over AG(i) {i} that represents the probability that i will delegate his vote to each of his approved neighbors, or to himself (which means he does not delegate his vote).

To determine whether a delegation mechanism M makes a correct decision on a labeled graph G = (V, E, p), we use the following 4-step process (which is described in words to avoid introducing notation that will not be used again):

1. Apply M to G.

2. Sample the probability distribution for each vertex to obtain an acyclic delegation graph. Each sink i of the delegation graph (i.e., vertex with no outgoing edges) has weight equal to the number of vertices with directed paths to i, including i itself.

3. Each sink i votes for the correct alternative with probability pi, and for the incorrect alternative with probability 1 pi.

4. A decision is made based on the weighted majority vote.2

We denote the probability that the mechanism M makes a correct decision on graph G via this 4-step process by PM(G).

2Ties can be broken arbitrarily.

We are especially interested in a special class of delegation mechanisms that we call local mechanisms. Intuitively, local mechanisms capture the natural setting where each voter makes an independent delegation decision without central coordination. Formally, a local delegation mechanism is a delegation mechanism such that the probability distribution of each vertex i depends only on the neighborhood of i in G, i.e., on {j V : (i, j) E}, and on AG(i), i.e., the subset of these neighbors that are approved. For example, the following delegation mechanisms are local:

Voters do not delegate their votes. This direct voting mechanism plays a special role in our model, and we denote it by D.

Each voter delegates his vote to a random approved neighbor, if he has any.

Each voter delegates his vote to a random approved neighbor, if he has approved neighbors but has even more nonapproved neighbors.

Each voter delegates his vote deterministically to a single approved neighbor, if he has any.3

Recall that we are interested in comparing the likelihood of making correct decisions via delegative voting with that of direct voting. To this end, define the gain of delegation mechanism M on labeled graph G as

gain(M, G) = PM(G) PD(G).

We would like to design delegation mechanisms that have positive gain (bounded away from zero) in some situations, and which never lose significantly to direct voting. Formally, we are interested in the following two desirable axioms:

A mechanism M satisfies the positive gain (PG) property if there exist γ > 0, n0 N such that for all n n0 there exists a graph Gn on n vertices such that gain(M, Gn) γ.

A mechanism M satisfies the do no harm (DNH) property if for all ε > 0, there exists n1 N such that for all graphs Gn on n n1 vertices, gain(M, Gn) ε.

The choice of quantifiers here is of great significance. PG asks for the existence of (large enough) instances where the gain is at least γ, for a constant γ. By contrast, DNH essentially requires that any loss would go to 0 as the size of the graph goes to infinity. That is, there may certainly be small instances where delegative voting loses out to direct voting, but that should not be the case in the large.

3There is a technical subtlety here: To implement such a local mechanism, vertices cannot be anonymous, so we require an ordering over the approved neighbors of each vertex, e.g., the one induced by the indices. We do not belabor this point but note that it is not an issue for our technical results.

3 Impossibility for Local Mechanisms

In our model, we make the strong assumption that voters can only delegate their vote to other voters who are more competent than they are, and, in particular, delegation chains can significantly boost the competence of any particular vote. Under this assumption, it seems natural to expect that delegative voting will always do at least as well as direct voting in every situation, and strictly better in some situations. This should intuitively be true under local mechanisms, say, when each voter delegates his vote to an arbitrary approved neighbor (if he has any). The following example helps build intuition for what can go wrong.

Example 1. Consider the labeled graph Gn = (V, E, p) over n vertices, where E = {(i, 1) : i V \ {1}}, i.e., G is a star with 1 at the center. Moreover, p1 = 4/5, pi = 2/3 for all i V \ {1}, and α = 1/10. Then, as n grows larger, PD(Gn) goes to 1 by the Law of Large Numbers, or, equivalently, by the Condorcet Jury Theorem (Grofman, Owen, and Feld 1983). By contrast, all leaves approve the center, and a na ıve local delegation mechanism M would delegate all their votes. In that case, the decision depends only on the vote of the center, so PM(Gn) = 4/5 for all n N, and gain(M, Gn) converges to 1/5. We conclude that M violates the DNH property.

One might hope that there are smarter local delegation mechanisms, that, say, recognize that when a voter only has one approved neighbor, his vote should not be delegated. However, our first result shows that this is not the case: local delegation mechanisms cannot even satisfy the two minimal requirements of PG and DNH.

Theorem 1. For any α0 [0, 1), there is no local mechanism that satisfies the PG and DNH properties.

The first step in the proof is better understanding the way in which local mechanisms are constrained. This is captured by the following lemma.

Lemma 1. Let M be a local mechanism. Then M satisfies the PG property only if there exist k, m, ρ > 0 such that, if a voter approves of exactly k of his m neighbors, then the total probability of delegation to any of these approved neighbors is exactly ρ.

Proof. Suppose that PG holds. Let γ > 0 and fix a labeled graph G such that gain(M, G) γ > 0. In order for this to be the case, there must exist some vertex i that delegates with positive probability ρ. Let k be the number of neighbors in G that i approves, and let m be his total number of neighbors in G; this yields the desired tuple (k, m, ρ).

The crux of the theorem s proof is the construction of a graph that, from the local viewpoint of many of the vertices, looks like the neighborhood prescribed by Lemma 1. Specifically, a k-center m-uniform star consists of vertices called leaves that are each connected to k central vertices (the centers) as well as m k other leaves. Each leaf vertex has competence level pℓ, and each center vertex has competence

Figure 1: Graph G for nℓ= 6 leaves (shown in red), nc = 3 centers (shown in blue), nd = 24 disconnected vertices (shown in yellow), and m = 4.

level pc, such that pc > pℓ+ α. We set the value of k and m to be the values whose existence is guaranteed by Lemma 1, which means that the construction of a k-center m-uniform star satisfies the property that each leaf delegates to some center vertex with probability ρ. Throughout the proof, we will let nc = k be the number of centers, and nℓwill denote the number of leaves.

At a high level, we show that the loss of any local mechanism can approach (1 pc)k, which is constant given k. We do this by constructing a graph that consists of a k-center m-uniform star with an independent disconnected component consisting of nd vertices of competence level pd. We set the parameters so that the direct voting mechanism D decides correctly with high probability. By contrast, under the local delegation mechanism M, enough leaves delegate their votes to the centers so that if all centers were to vote incorrectly, which happens with probability (1 pc)k, then M would decide incorrectly. While the basic idea is simple enough, the formal construction is quite delicate, as many different parameters must be perfectly balanced.

Proof of Theorem 1. Let M be a local mechanism that satisfies PG. By Lemma 1, there must exist at least one (k, m, ρ) tuple for M that satisfies the lemma s conclusion. For any n1 prescribed by DNH and any α0, we can construct a graph Gn such that DNH does not hold.

Let G be a graph of size n = nc + nℓ+ nd that consists of a k-center m-uniform star and a disconnected component containing nd disconnected points (see Figure 1). Each center has competence level pc, each leaf in the star has competence level pℓ, and each point in the disconnected component has competence level pd. Given (k, m, ρ), n1, and α0, note that the following constraints must hold.

nℓ m nc (1) n = nℓ+ nc + nd n1 (2) pc > pℓ+ α0 (3)

We will prove that the following explicit construction violates DNH for any input of (k, m, ρ), n1, and α = α0 + ε

for ε = 1 α0

2 > 0, as δ 0.

nd = C1 n1m

σ nℓ pℓ nℓ)

pd n/2 nℓpℓ

nd , (11) n/2 nℓpℓ

+ (nℓρ τ)pℓ σ n

Note that we define τ in (12) below. The following claim, whose proof is relegated to the full version of the paper,4 asserts that the construction is feasible.

Claim 1. C1 > 0 and the range of values for pd in (11) is nonempty.

Because α, δ (0, 1) and C1 > 0, the value of nℓin (5) is greater than both n1 and m, hence constraints (1) and (2) are immediately satisfied. Moreover, constraint (3) is satisfied by (9) and (10).

Turning to the proof that DNH is violated, let S, Z, and W be the random variables corresponding to the number of correct votes under D, the number of delegated votes under M, and the number of non-delegated correct votes under M. Additionally, let ε, τ, and ξ be as follows.

2 nℓ 2 , and (12)

4Available from http://procaccia.info/research.

2 (n nc (ρnℓ τ))

Our goal is to bound the expectations of S, Z, and W. First, we examine E[S]. We would like to show that

E[S] n/2 + ε. (13)

Expanding out the expected value, this is equivalent to

pcnc + pℓnℓ+ pdnd n/2 + ε.

From (11), we have

pd n/2 pℓnℓ+ ε

so it is sufficient to show that

pcnc + pℓnℓ+ nd

n/2 pℓnℓ+ ε

and simplifying results in pcnc 0. This is true by Equation (9), because α and k are both constrained to be strictly positive.

Next, we examine E[Z]. We would like to show that

E[Z] = nℓρ. (14)

This is trivial to see, as Z is a sum of nℓBernoulli random variables with success probability ρ.

Finally, we examine the typical case over W, or E[W|Z = v] for all integers v [nℓρ τ, nℓρ + τ]. Intuitively, this is examining the number of correct votes cast by stillindependent vertices after enough leaf vertices have delegated their votes. If these votes do not make up a majority, then all centers voting incorrectly will cause the entire graph to vote incorrectly. We would like to show that

E[W|Z = v] n/2 ξ. (15)

for all integers v [nℓρ τ, nℓρ + τ]. Conditionally on Z being in the prescribed range above, we see that in the worst case, Z = nℓρ τ, meaning the fewest possible voters delegate under this assumption. Given this, we would like to show that

pdnd + pℓ(nℓ (ρnℓ τ)) n/2 ξ.

From Equation (11) we have

pd n/2 pℓnℓ+ (nℓρ τ)pℓ ξ

which yields n/2 pℓnℓ+ (nℓρ τ)pℓ ξ

nd + pℓ(nℓ (ρnℓ τ))

Simplifying results in 0 0 a tautology. This establishes Equation (15).

We now wish to bound the probability of S, Z, and W deviating by too much. We use Hoeffding s inequality, which states that given n independent Bernoulli random variables

Xi [0, 1] and X =

i Xi, the following concentration bound holds:

Pr [|X E[X]| ε] 2 exp 2ε2

First, we examine S. From (16) and a straightforward substitution for ε, we obtain

Pr (|S E[S]| ε) 2 exp 2ε2

Likewise, for Z, from (16) and a straightforward substitution for τ, we obtain

Pr [|Z E[Z]| τ] 2 exp 2τ 2

Finally, for W, we are interested in upper-bounding

Pr[|W E[W|Z = v]| ξ | Z = v],

for every integer v [nℓρ τ, nℓρ+τ]. As before, we apply Equation (16), and, as it turns out, we can derive an upper bound when Z = nℓρ τ. Therefore, we obtain that for every v [nℓρ τ, nℓρ + τ],

Pr [|W E[W|Z = v]| ξ | Z = v]

n nc (ρnℓ τ)

2)(n nc (ρnℓ τ))

n nc (ρnℓ τ)

From the above, we see that

Pr[S > n/2] 1 δ, (by (13) and (17)) Pr[Z (nℓρ τ, nℓρ + τ)] 1 δ, (by (14) and (18)) Pr[W < n/2 | Z = v] 1 δ, (by (15) and (19))

where the last inequality holds for all integers v [nℓρ τ, nℓρ + τ].

Therefore, the lower bound on the probability of D deciding correctly is PD(G) 1 δ. We can lower-bound the probability of M deciding incorrectly in order to upper-bound PM(G). We slightly overload notation and let M be the event that M decides correctly, and M be the event that M decides incorrectly. Moreover, denote by V the event that Z [nℓρ τ, nℓρ + τ]. By definition, we have

Pr[ M] = Pr[ M|V ] Pr[V ] + Pr[ M| V ] Pr[ V ],

and because probabilities cannot be negative, Pr[ M] Pr[ M|V ] Pr[V ]. Now, because Pr[V ] 1 δ,

Pr[ M] Pr[ M|V ](1 δ).

Furthermore, we know that Pr[ M|V ] is also lowerbounded by (1 pc)nc(1 δ) because one setting under which M decides incorrectly is exactly when all centers vote incorrectly and W < n/2. It follows that

Pr[ M] (1 pc)nc(1 δ)(1 δ).

Therefore, taking the complement, we have an upper bound on the probability of M voting correctly of

Pr[M] 1 (1 pc)nc(1 δ)2,

and the total loss can be lower-bounded by

(1 δ) (1 (1 pc)nc(1 δ)2) = (1 pc)nc(1 δ)2 δ.

As δ 0, this tends to (1 pc)nc = (1 pc)k, which is constant and bounded away from 0. We conclude that M violates the DNH property.

4 Possibility for Non-Local Mechanisms

The main idea underlying Theorem 1 is that liquid democracy can correlate the votes to the point where the mistakes of a few popular voters tip the scales in the wrong direction. As we show in the theorem s proof, this is unavoidable under local delegation mechanisms, which, intuitively, cannot identify situations in which certain voters amass a large number of votes. However, non-local delegation mechanisms can circumvent this issue. Indeed, consider the following delegation mechanism.

input: labeled graph G, cap C : N N 1: V V 2: while V = do 3: let i argmaxj V |A 1 G (j) V | 4: J AG(i) V

5: if |J| C(n) 1 then 6: J J 7: else 8: let J J such that |J | = C(n) 1 9: end if 10: vertices in J delegate to i 11: V V \ ({i} {J }) 12: end while

Algorithm 1: GREEDYCAP

In words, the mechanism GREEDYCAP, given as Algorithm 1, receives as input a labeled graph G, and a cap C. It iteratively selects a voter with maximum approvals, and delegates votes to him, so that no more than C(n) 1 votes are delegated to a single voter (that is, no voter can have weight more than C(n)). All voters involved in the current iteration are then eliminated from further consideration, which is why delegations under this mechanism are only 1-hop.

It is obvious that GREEDYCAP satisfies the PG property. However, although it seems at first glance that it should satisfy DNH as well (as it solves the excessive correlation problem), the following example shows that, without further assumptions, it does not.

Example 2. Assume for ease of exposition that α < 1/3. For any odd n = 2k + 1, consider the labeled graph Gn = (V, E, p) on n vertices, defined as follows: E = {(1, 2)} (i.e., the only edge in the graph is from 1 to 2), p1 = 1/3, p2 = 2/3, there are k vertices with pi = 1, and k 1 vertices with pi = 0. Even if C(n) 2, GREEDYCAP would delegate the vote of voter 1 to 2. Therefore, the mechanism decides correctly if and only if 2 votes correctly, which happens with probability 2/3. By contrast, under direct voting, it is enough for either 1 or 2 to vote correctly, which happens with probability 7/9. It follows that the loss of GREEDYCAP is 1/9 a constant. We conclude that GREEDYCAP violates DNH.

The reason the example works is that the outcome completely depends on voters 1 and 2, as the others vote deterministically (competence level 0 or 1). To avoid this problem, we make the natural assumption that competence levels are bounded away from 0 and 1, i.e., voters are never horribly misinformed or perfectly informed. It turns out that this additional assumption is sufficient to guarantee that GREEDYCAP satisfies the DNH property.

Theorem 2. Assume that there exists β (0, 1/2) such that all competence levels are in [β, 1 β]. Then for any α (0, 1 2β), GREEDYCAP with cap C : N N such that C(n) ω(1) and C(n) o( log n) satisfies the PG and DNH properties.

The theorem s rather technical proof is relegated to the full version of the paper. Here we provide a proof sketch.

The PG property is rather obvious. It suffices to construct a family of examples over which the property is satisfied. Let the underlying graph G consist of pairs of nodes with one competent voter with competence level 1 β, and one incompetent voter with competence level β, where there is an edge from every incompetent voter to the connected competent voter. Under the direct setting, it is clear that PD = 1/2. However, under GREEDYCAP, all incompetent voters delegate to competent voters, resulting in n/2 independent voters who each have competence 1 β and weight exactly two. By the Condorcet Jury Theorem (Grofman, Owen, and Feld 1983), the probability of success approaches 1.

For the DNH property, we denote the number of correct votes under direct voting and GREEDYCAP by XD and XM,

respectively, and consider two cases.

1. |E[XD] n

2 | > n log n.

2. |E[XD] n

2 | n log n.

In Case 1, the direct voting mechanism has mean far away from n/2. When E[XD] < n/2 n/ log n, we can show that PD goes to 0 as n goes to infinity. This means that DNH is satisfied for any value of PM. In the case where E[XD] > n/2 + n/ log n, we can show that PM goes to 1 as n goes to infinity, which means that DNH is satisfied for any value of PD.

In Case 2, the direct voting setting has mean close to n/2. From here, we consider two subcases.

1. The number of voters who delegate is greater than n/g(n), where g(n) o(log n) and g(n) ω(C(n)2) hence the upper bound on C(n).

2. The number of voters who delegate is at most n/g(n).

In Subcase 1, because a relatively large fraction of voters delegate their votes to more competent neighbors, E[XM] E[XD] is large enough to offset the simultaneous increase in the variance of XM, and, in the limit, PM goes to 1. In Subcase 2, we again have E[XM] E[XD] due to delegation. Additionally, because so few voters delegate, the ratio of the variance of XM and that of XD converges to 1 as n approaches infinity, which means that (in the worst case) the difference between PD and PM converges to 0.

5 Discussion

We wrap up with a discussion of two central issues.

How realistic is the model? We revisit an important point, which has already come up several times, including in Section 1. Our assumption that voters only delegate their votes to more competent voters is clearly restrictive. But we feel it allows us, in a sense, to distill the essence of liquid democracy (e.g., by avoiding complications that have to do with delegation cycles) and focus on central issues such as vote correlation. Moreover, as noted earlier, our negative result Theorem 1 is especially powerful in this model, that is, it holds despite the foregoing assumption. And the positive result Theorem 2 should (informally speaking) still hold in a relaxed model where voters may delegate their votes to less competent voters, as long as the average competence level increases by a constant due to delegation. We view this as a realistic assumption.

Beyond binary issues. In our model, there are only two alternatives, one correct and one incorrect. While this setting is of practical importance, it is natural to ask whether our results extend to the case of three or more alternatives. However, there are several obstacles.

First, a representation of the ground truth, and of voters perceptions thereof, is required. A popular option is the Mallows (1957) Model, where the ground truth is a ranking of

the alternatives, and the probability that a voter cast a given ranking as his vote decreases exponentially with its distance from the ground truth, in a way that depends on a (competence) parameter φi. This model coincides with ours (using a suitable transformation between φi and pi) when the number of alternatives is 2.

Second, we have assumed that votes are aggregated using the majority rule, which is the only reasonable voting rule when there are two alternatives. By contrast, when choosing among three or more alternatives, there are many voting rules one can use.

To conclude, any attempt to extend our model and results beyond the case of two alternatives would have to address not only technical challenges, but also conceptual ones.

Acknowledgments

This work was partially supported by NSF grants IIS1350598, IIS-1714140, CCF-1525932, and CCF-1733556; by ONR grants N00014-16-1-3075 and N00014-17-1-2428; and by a Sloan Research Fellowship.

Alger, D. 2006. Voting by proxy. Public Choice 126(1 2):1 26.

Azari Soufiani, H.; Parkes, D. C.; and Xia, L. 2012. Random utility theory for social choice. In Proceedings of the 26th Annual Conference on Neural Information Processing Systems (NIPS), 126 134.

Azari Soufiani, H.; Parkes, D. C.; and Xia, L. 2013. Preference elicitation for general random utility models. In Proceedings of the 29th Annual Conference on Uncertainty in Artificial Intelligence (UAI), 596 605.

Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds. 2016. Handbook of Computational Social Choice. Cambridge University Press.

Caragiannis, I.; Procaccia, A. D.; and Shah, N. 2014. Modal ranking: A uniquely robust voting rule. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), 616 622.

Caragiannis, I.; Procaccia, A. D.; and Shah, N. 2016. When do noisy votes reveal the truth? ACM Transactions on Economics and Computation 4(3): article 15.

Christoff, Z., and Grosssi, D. 2017. Binary voting with delegable proxy: An analysis of liquid democracy. In Proceedings of the 16th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 134 150.

Cohensius, G.; Mannor, S.; Meir, R.; Meirom, E.; and Orda, A. 2017. Proxy voting for better outcomes. In Proceedings of the 16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 858 866.

Conitzer, V., and Sandholm, T. 2005. Common voting rules as maximum likelihood estimators. In Proceedings of the 21st Annual Conference on Uncertainty in Artificial Intelligence (UAI), 145 152.

Conitzer, V.; Rognlie, M.; and Xia, L. 2009. Preference functions that score rankings and maximum likelihood estimation. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), 109 115.

Elkind, E.; Faliszewski, P.; and Slinko, A. 2010. Good rationalizations of voting rules. In Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI), 774 779.

Green-Armytage, J. 2015. Direct voting and proxy voting. Constitutional Political Economy 26(2):190 220.

Grofman, B.; Owen, G.; and Feld, S. L. 1983. Thirteen theorems in search of the truth. Theory and Decision 15(3):261 278.

Kling, C. C.; Kunegis, J.; Hartmann, H.; Strohmaier, M.; and Staab, S. 2015. Voting behaviour and power in online democracy: A study of liquidfeedback in germany s pirate party. ar Xiv preprint ar Xiv:1503.07723.

Lu, T., and Boutilier, C. 2011. Robust approximation and incremental elicitation in voting protocols. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), 287 293.

Mallows, C. L. 1957. Non-null ranking models. Biometrika 44:114 130.

Mao, A.; Procaccia, A. D.; and Chen, Y. 2013. Better human computation through principled voting. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI), 1142 1148.

Miller, J. C. 1969. A program for direct and proxy voting in the legislative process. Public Choice 7(1):107 113.

Procaccia, A. D.; Reddi, S. J.; and Shah, N. 2012. A maximum likelihood approach for selecting sets of alternatives. In Proceedings of the 28th Annual Conference on Uncertainty in Artificial Intelligence (UAI), 695 704.

Procaccia, A. D.; Shah, N.; and Zick, Y. 2016. Voting rules as error-correcting codes. Artificial Intelligence 231:1 16.

Tullock, G. 1992. Computerizing politics. Mathematical and Computer Modelling 16(8 9):59 65.

Xia, L., and Conitzer, V. 2011. A maximum likelihood approach towards aggregating partial orders. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), 446 451.

Xia, L.; Conitzer, V.; and Lang, J. 2010. Aggregating preferences in multi-issue domains by using maximum likelihood estimators. In Proceedings of the 9th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 399 408.