In Defense of Liquid Democracy

Fluid democracy is a voting paradigm that allows voters to choose between directly voting and transitively delegating their votes to other voters. While fluid democracy has been viewed as a system that can combine the best aspects of direct and representative democracy, it can also result in situations where few voters amass a large amount of influence. To analyze the impact of this shortcoming, we consider what has been called an epistemic setting, where voters decide on a binary issue for which there is a ground truth. Previous work has shown that under certain assumptions on the delegation mechanism, the concentration of power is so severe that fluid democracy is less likely to identify the ground truth than direct voting. We examine different, arguably more realistic, classes of mechanisms, and prove they behave well by ensuring that (with high probability) there is a limit on concentration of power. Our proofs demonstrate that delegations can be treated as stochastic processes and that they can be compared to well-known processes from the literature -- such as preferential attachment and multi-types branching process -- that are sufficiently bounded for our purposes. Our results suggest that the concerns raised about fluid democracy can be overcome, thereby bolstering the case for this emerging paradigm.


Introduction
Fluid democracy (also known as liquid democracy) is a voting paradigm that is conceptually situated between direct democracy, in which voters have direct influence over decisions, and representative democracy, where voters choose delegates who represent them for a period of time. Under fluid democracy, voters have a choice: they can either vote directly on an issue similar to direct democracy, or they can delegate their vote to another voter, entrusting them to vote on their behalf. The defining feature of fluid democracy is that these delegations are transitive: if voter 1 delegates to voter 2 and voter 2 delegates to voter 3, then voter 3 votes (or delegates) on behalf of all three voters.
In recent years, fluid democracy has gained prominence around the world. The most impressive example is that of the German Pirate Party, which adopted the LiquidFeedback platform in 2010 [22]. Other political parties, such as the Net Party in Argentina and Flux in Australia, have run on the wily promise that, once elected, their representatives would be essentially controlled by voters through a fluid democracy platform. Companies are also exploring the use of fluid democracy for corporate governance; Google, for example, has run a proof-of-concept experiment [17].
Practitioners, however, recognize that there is a potential flaw in fluid democracy, namely, the possibility of concentration of power, in the sense that certain voters amass an enormous number of delegations, giving them pivotal influence over the final decision. This scenario seems inherently undemocratic -and it is not a mere thought experiment. Indeed, in the LiquidFeedback platform of the German Pirate Party, a linguistics professor at the University of Bamberg received so many delegations that, as noted by Der Spiegel, 1 his "vote was like a decree. " Kahng et al. [21] examine fluid democracy's concentration-of-power phenomenon from a theoretical viewpoint, and established a troubling impossibility result in what has been called an epistemic setting, that is, one where there is a ground truth. 2 Informally, they demonstrate that, even under the strong assumption that voters only delegate to more "competent" voters, any "local mechanism" satisfying minimal conditions will, in certain instances, fall victim to a concentration of power, leading to relatively low accuracy.
More specifically, Kahng et al. model the problem as a decision problem where voters decide on an issue with two outcomes, {0, 1}, where 1 is correct (the ground truth) and 0 is incorrect. Each of the voters i ∈ {1, . . . , n} is characterized by a competence p i ∈ [0, 1]. The binary vote V i of each voter i is drawn independently from a Bernoulli distribution, that is, each voter votes correctly with probability p i . Under direct democracy, the outcome of the election is determined by a majority vote: the correct outcome is selected if and only if more than half vote for the correct outcome. Under fluid democracy, there exists a set of weights, weight i for each i ∈ [n], which represent the number of votes that voter i gathered transitively after delegation. If voter i delegates, then weight i = 0. The outcome of the election is then determined by a weighted majority; it is correct if and only if n i=1 weight i V i ≥ n/2. Kahng et al. also introduce the concept of a delegation mechanism, which determines whether voters delegate and if so to whom they delegate. They are especially interested in local mechanisms, where the delegation decision of a voter only depends on their local neighborhood according to an underlying social network. They assume that voters only delegate to those with strictly higher competence, which excludes the possibility of cyclic delegations.
In order to evaluate fluid democracy, Kahng et al. [21] test the intuition that society makes more informed decisions under fluid democracy than under direct democracy (especially given the foregoing assumption about upward delegation). To that end, they define the gain of a delegation mechanism to be the difference between the probability the correct outcome is selected under fluid democracy and the probability the correct outcome is selected under direct democracy. A delegation mechanism satisfies positive gain if its gain is strictly positive in some cases, and it satisfies do no harm if its loss (negative gain) is at most ε for all sufficiently large instances. The main result of Kahng et al. [21] is that local mechanisms can never satisfy these two requirements. Caragiannis and Micha [7] further strengthen this negative result by showing that there are instances where local mechanisms perform much worse than either direct democracy or dictatorship (the most extreme concentration of power).
These theoretical critiques undermine the case for fluid democracy: the benefits of delegation appear to be reversed by concentration of power. However, the negative conclusion relies heavily on modeling assumptions, and has not been borne out by experiments [2]. In this paper, we provide a rebuttal by introducing an arguably more realistic model, in which fluid democracy is able to avoid extreme concentration of power, thereby satisfying both do no harm and positive gain (for suitably defined extensions).

Our Contributions and Techniques
Our point of departure from the existing literature is the way we model delegation in fluid democracy. Our delegation mechanisms are defined by M = (q, ϕ), where q : [0, 1] → [0, 1] is a function that maps a voter's competence to the probability they delegate and ϕ : [0, 1] 2 → R ≥0 maps a pair of competencies to a weight. In this model, each voter i votes directly with probability 1 − q(p i ) and, conditioned on delegating with probability q(p i ), delegates to voter j = i with probability proportional to ϕ(p i , p j ). Crucially, a voter does not need to "know" the competence of another voter in order to decide whether to delegate; rather, the delegation probabilities are merely influenced by competence in an abstract way captured by ϕ. Also note that delegation cycles are possible, and we take a worst-case approach to dealing with them: If the delegations form a cycle then all voters in the cycle are assumed to be incorrect (vote 0). 3 The most significant difference between our model of delegation and that of Kahng et al. [21] is that in our model each voter has a chance of delegating to any other voter, whereas in their model an underlying social network restricts delegation options. Our model captures a connected world where, in particular, voters may have heard of experts on various issues even if they do not know them personally. Although our model eschews an explicit social network, it can be seen as embedded into the delegation process, where the probability that i delegates to j takes into account the probability that i is familiar with j in the first place.
Another difference between our model and that of Kahng et al. [21] is that we model the competencies p 1 , . . . , p n as being sampled independently from a distribution D. While this assumption is made mostly for ease of exposition, it allows us to avoid edge cases and obtain robust results.
Our goal is to identify delegation mechanisms that satisfy (probabilistic versions of) positive gain and do no harm. Our first technical contribution, in Section 3, is the formulation of general conditions on the mechanism and competence distribution that are sufficient for these properties to hold (Lemma 1). In particular, to achieve the more difficult do no harm property, we present conditions that guarantee the maximum weight max-weight(G n ) accumulated by any voter be sublinear with high probability and that the expected increase in competence post-delegation be at least a positive constant times the population size. These conditions intuitively prevent extreme concentration of power, and ensure that the representatives post-delegation are sufficiently better than the entire population to compensate for any concentration of power that does happen.
It then suffices to identify mechanisms and distribution classes that verify these conditions. A delegation mechanism M and a competence distribution D induce a distribution over delegation instances that generates random graphs in ways that relate to well-known graph processes, which we leverage to analyze our mechanisms. Specifically, we introduce three mechanisms, all shown to satisfy do no harm and positive gain under any continuous distribution over competence levels. The first two mechanisms, upward delegation and confidence-based delegation, can be seen as interesting but somewhat restricted case studies, whereas the general continuous delegation mechanism is, as the name suggests, quite general and arguably realistic. Despite the simplicity of the first two mechanisms, the three mechanisms, taken together, reveal the robustness of our approach.
Upward Delegation. In Section 4, we consider a model according to which the probability of delegating p is exogenous and constant across competencies and delegation can only occur towards voters with strictly higher competence. That is, the probability that any voter i delegates is q(p i ) = p and the weight that any voter i puts on an other voter j is φ(p i , p j ) = I {p j −p i >0} . This mechanism captures the fact that there might be some reluctance to delegate regardless of the voter's competence, but does assume that voters act in the interest of society in only delegating to voters that are more competent than they are.
To generate a random graph induced by such a mechanism, one can add a single voter at a time in order of decreasing competence, and allow the voter to either not delegate and create their own disconnected component, or delegate to the creator of any other component with probability proportional to p times the size of the component. This works because delegating to any voter in the previous components is possible (since they have strictly higher competence) and would result in the votes being concentrated in the originator of that component by transitivity. Such a process is exactly the one that generates a preferential attachment graph with positive probability of not attaching to the existing components [30]. We can then show that, with high probability, no component grows too large, so long as p < 1. Further, there needs to be a constant improvement by continuity of the competence distribution, which ensures that a positive fraction of voters below a certain competence delegate to a positive fraction of voters with strictly higher competencies.
Confidence-Based Delegation. In Section 5, we consider a model in which voters delegate with probability decreasing in their competencies and choose someone at random when they delegate. That is, the probability q(p i ) that any voter i delegates is decreasing in p i and the weight that any voter i gives to any voter j is φ(p i , p j ) = 1. In other words, in this model competence does not affect the probability of receiving delegations, only the probability of delegating.
To generate a random graph induced by such a mechanism, one can begin from a random vertex and study the delegation tree that starts at that vertex. A delegation tree is defined as a branching process, where a node i's "children" are the nodes that delegated to node i. In contrast to classical branching process, the probability for a child to be born increases as the number of people who already received a delegation decreases. Nevertheless, we prove that, with high probability, as long as a delegation tree is no larger than O(log n), our heterogeneous branching process is dominated by a sub-critical graph branching process [1]. We can then conclude that no component has size larger than O(log n) with high probability. Next, we show that the expected competence among the voters that do not delegate is strictly higher than the average competence. Finally, given that no voter has weight larger than O(log n), we prove that a small number of voters end up in cycles with high probability. We can therefore show that the conditions of Lemma 1 are satisfied.
General Continuous Delegation. Finally, we consider a general model in Section 6 where the likelihood of delegating is fixed and the weight assigned to each voter when delegating is increasing in their competence. That is, each voter i delegates with probability q(p i ) = p and the weight that voter i places on voter j is ϕ(p i , p j ), where ϕ is continuous and increases in its second coordinate. Thus, in this model, the delegation distribution is slightly skewed towards more competent voters.
To generate a random graph induced by such a mechanism, we again consider a branching process, but now voters j and k place different weights on i per ϕ. Therefore, voters have a type that governs their delegation behavior; this allow us to define a multi-type branching process with types that are continuous in [0, 1]. The major part of the analysis is a proof that, with high probability, as long as the delegation tree is no larger than O(log n), our heterogeneous branching process is dominated by a sub-critical Poisson multi-type branching process. To do so, we group the competencies into buckets that partition the segment [0, 1] into small enough pieces. We define a new ϕ ′ that outputs, for any pair of competencies p i , p j , the maximum weight a voter from i's bucket could place on a voter from j's bucket. We can show that such a discrete multi-type branching process is sub-critical and conclude that no component has size larger than O(log n) with high probability. In a similar fashion to Confidence-Based Delegation, we also show that there is an expected increase in competence post-delegation.

Related work
Our work is most closely related to that of Kahng et al. [21], which was discussed in detail above. It is worth noting, though, that they complement their main negative result with a positive one: when the mechanism can restrict the maximum number of delegations (transitively) received by any voter to o( √ log n), do no harm and positive gain are satisfied. Imposing such a restriction would require a central planner that monitors and controls delegations. Gölz et al. [14] build on this idea: they study fluid democracy systems where voters may nominate multiple delegates, and a central planner chooses a single delegate for each delegator in order to minimize the maximum weight of any voter. Similarly, Brill and Talmon [6] propose allowing voters to specify ordinal preferences over delegation options, and possibly restricting or modifying delegations in a centralized way. Caragiannis and Micha [7], and then Becker et al. [2] also consider central planners; they show that, for given competencies, the problem of choosing among delegation options to maximize the probability of a correct decision is hard to approximate. In any case, implementing these proposals would require a fundamental rethinking of the practice of fluid democracy. By contrast, our positive results show that decentralized delegation mechanisms are inherently self-regulatory, which supports the effectiveness of the current practice of fluid democracy.
More generally, there has been a significant amount of theoretical research on fluid democracy in recent years. To give a few examples: Green-Armytage [15] studies whether it is rational for voters to delegate their vote from a utilitarian viewpoint; Christoff and Grossi [8] examine a similar question but in the context of voting on logically interdependent propositions; Bloembergen et al. [3] and Zhang and Grossi [31] study fluid democracy from a game-theoretic viewpoint.
Further afield, fluid democracy is related to another paradigm called proxy voting, which dates back to the work of Miller [26]. Proxy voting allows voters to nominate representatives that have been previously declared. Cohensius et al. [10] study utilitarian voters that vote for the representative with the closest platform to theirs; they prove that the outcome of an election with proxy votes yields platforms closer to the median platform of the population than classical representative democracy. Their result provides a different viewpoint on the value of delegation.

Model
There is a set of n voters, denoted [n] = {1, . . . , n}. We assume voters are making a decision on a binary issue and there is a correct alternative and an incorrect alternative. Each voter i has a competence level p i ∈ [0, 1] which is the probability that i votes correctly. We denote the vector of competencies by p n = (p 1 , . . . , p n ). When n is clear from the context, we sometimes drop it from the notation.
Delegation graphs A delegation graph G n = ( [n], E) on n voters is a directed graph with voters as vertices and a directed edge (i, j) ∈ E denoting that i delegates their vote to j. Again, if n is clear from context, we occasionally drop it from the notation. The outdegree of a vertex in the delegation graph is at most 1, since each voter can delegate to at most one person. Voters that do not delegate have no outgoing edges. In a delegation graph G n , the delegations received by a voter i, dels i (G n ), is defined as the total number of people that (transitively) delegated to i in G n , (i.e., the total number of ancestors of i in G n ). The weight of a voter i, weight i (G n ), is dels i (G n ) if i delegates, and 0 otherwise. We define max-weight(G n ) = max i∈ [n] weight i (G n ) to be the largest weight of any voter and define total-weight(G n ) = n i=1 weight i (G n ). Since each vote is counted at most once, we have that total-weight(G n ) ≤ n. However, note that if delegation edges form a cycle, then the weight of the voters on the cycle and voters delegating into the cycle are all set to 0 and hence will not be counted. In particular, this means that total-weight(G n ) may be strictly less than n. 4 Delegation instances We call the tuple ( p n , G n ) a delegation instance, or simply an instance, on n voters. Let V i = 1 if voter i would vote correctly if i did vote, and V i = 0 otherwise. Fixed competencies p n induce a probability measure P pn over the n possible binary votes V i , where V i ∼ Bern(p i ). Given votes V 1 , . . . , V n , we let X D n be the number of correct votes under direct democracy, that is, We let X F Gn be the number of correct votes under fluid democracy with delegation graph G n , that is, The probability that direct democracy and fluid democracy are correct are P pn [X D n > n/2] and P pn [X F Gn > n/2], respectively.
Gain of a delegation instance We define the gain of an instance as In words, it is the difference between the probability that fluid democracy is correct and the probability that majority is correct.
Randomization over delegation instances In general, we assume that both competencies and delegations are chosen randomly. Each voter's competence p i is sampled i.i.d. from a fixed distribution D with support contained in [0, 1]. Delegations will be chosen according to a mechanism M . A mechanism M = (q, ϕ) is composed of two parts. The first q : [0, 1] → [0, 1] is a function that maps competencies to the probability that the voter delegates. The second ϕ : [0, 1] 2 → R ≥0 maps pairs of competencies to a weight. A voter i with competence p i will choose how to delegate as follows: -With probability 1 − q(p i ) they do not delegate.
-With probability q(p i ), i delegates; i places weight ϕ(p i , p j ) on each voter j = i and randomly sample another voter j to delegate to proportional to these weights. In the degenerate case where ϕ(p i , p j ) = 0 for all j = i, we assume that i does not delegate.
A competence distribution D, a mechanism M , and a number n of voters induce a probability measure P D,M,n over all instances ( p n , G n ) of size n.
We can now redefine the do no harm (DNH) and positive gain (PG) properties from Kahng et al. [21] in a probabilistic way.
Definition 1 (Probabilistic do no harm). A mechanism M satisfies probabilistic do no harm with respect to a class D of distributions if, for all distributions D ∈ D and all ε, δ > 0, there exists n 0 ∈ N such that for all n ≥ n 0 , Definition 2 (Probabilistic positive gain). A mechanism M satisfies probabilistic positive gain with respect to a class D of distributions if there exists a distribution D ∈ D such that for all ε, δ > 0, there exists n 0 ∈ N such that for all n ≥ n 0 ,

Core Lemma
In this section, we prove the following key lemma, which provides sufficient conditions for a mechanism M to satisfy probabilistic do no harm and probabilistic positive gain with respect to a class D of distributions. This lemma will form the basis of all of our later results.

Lemma 1. If M is a mechanism, D a class of distributions, and for all distributions
then M satisfies probabilistic do no harm. If in addition, there exists a distribution D ∈ D and an α ∈ (0, 1) such that then M satisfies probabilistic positive gain.
In words, condition (1) ensures that, with high probability, the largest weight accumulated by a voter post-delegation is sub-linear. This condition prevents extreme concentration of power. Condition (2) ensures that, with high probability, the (weighted) average competence post-delegation is at least a positive constant more than the average competence pre-delegation. This condition guarantees that representatives post-delegation are sufficiently more competent than the entire population to compensate for any concentration of power that does occur. Finally, condition (3) ensures that there exists a distribution for which, with high probability, the average competence pre-delegation is at most 1/2 minus a constant, while the average competence post-delegation is at least 1/2 plus a constant. This condition suffices to guarantee that the probability that fluid democracy is correct goes to 1 while direct democracy goes to 0.
Throughout many of the proofs, we will make use of the the following well-known concentration inequality [18]: Proof of Lemma 1. We establish the two properties separately.
Probabilistic do no harm: We first show that a mechanism M that satisfies conditions (1) and (2) satisfies probabilistic do no harm. Fix an arbitrary competence distribution D ∈ D and let α and C be such that (1) and (2) are satisfied. Without loss of generality, suppose that C(n) ≤ n for all n, as replacing any larger values of C(n) with n will not affect (1) (since max-weight(G n ) ≤ n for all graphs G n on n vertices). Fix ε, δ > 0. We must identify some n 0 such that for all n ≥ n 0 , We will begin by showing there exists n 1 ∈ N such that for all instances ( p n , G n ) on n ≥ n 1 voters, if both Since (4) and (5) each hold with probability 1 − o(1) by (1) and (2), for sufficiently large n, say n ≥ n 2 , they will each occur with probability at least 1 − δ/2. Hence, by a union bound, for all n ≥ n 2 , they both occur with probability at least 1 − δ. By taking n 0 = max(n 1 , n 2 ), this implies that probabilistic do no harm is satisfied. We now prove that, for sufficiently large n, (4) and (5) imply (6). Fix an instance ( p n , G n ) on n voters satisfying (4) and (5). We first show that for sufficiently large n, we have and Assume that (7) and (8) hold. Note that (5) Hence, in either case, (6) holds. It remains to prove that (7) and (8) hold for sufficiently large n. For (7), this follows directly from Hoeffding's inequality (Lemma 2). To prove (8), first note that, as shown in Kahng et al. [21], where the first inequality holds because p(1 − p) is upper bounded by 1/4, the second because so the value is maximized by setting as many terms to C(n) as possible, and the final inequality holds because C(n) ≤ n.
Hence, by Chebyshev's inequality, This bound is o(1) because the numerator is o(n 2 ) and the denominators is Ω(n 2 ). Hence, for sufficiently large n, it will be strictly less than ε/2, which implies that (8) holds.
Probabilistic positive gain: Fix a distribution D ∈ D and an α ∈ (0, 1) such that (3) holds. We want to show that M satisfies probabilistic positive gain. Since D ∈ D, it also satisfies (1) for some C. We show below that there exists an n 3 such that all instances ( p n , G n ) with n ≥ n 3 voters satisfying (4) As with the DNH part of the proof, since the events of (1) and (3) each hold with probability 1 − o(1), for sufficiently large n, say n ≥ n 4 , they each occur with probability at least 1 − δ/2. Hence, by a union bound, for all n ≥ n 4 , they both occur with probability 1 − δ. For n 0 = max(n 3 , n 4 ), probabilistic positive gain is satisfied.
It remains to show that that if (1) and (3) hold for a specific instance ( p n , G n ), then gain( p n , G n ) ≥ 1 − ε for sufficiently large n. Since D ∈ D, (7) and (8) are both satisfied for sufficiently large n. When is satisfied as well, we get that P pn X D n > n/2 < ε/2 and P pn In the following sections, we investigate natural delegation mechanisms and identify conditions such that the mechanisms satisfy probabilistic do no harm and probabilistic positive gain. In all instances, we will invoke Lemma 1 after showing that its sufficient conditions are satisfied.

Strictly Upward Delegation Mechanism
We now turn to the analysis of a simple mechanism that assumes that voters either do not delegate with fixed exogenous probability, or delegate to voters that have a competence greater than their own.
Formally, for a fixed p ∈ [0, 1] we let M U p = (q, ϕ) be the mechanism consisting of q(p i ) = p for all p i ∈ [0, 1], and ϕ(p i , p j ) = I {p j >p i } for all i, j ∈ [n]. That is, voter i delegates with fixed probability p and puts equal weight on all the more competent voters. In other words, if voter i delegates, then i does so to a more competent voter chosen uniformly at random. Note that a voter with maximal competence will place 0 weight on all other voters, and hence is guaranteed not to delegate. We refer to M U p as the Upward Delegation Mechanism parameterized by p. Proof. To prove the theorem, we will prove that the Upward Delegation Mechanism with respect to D C satisfies (1) and (2), which implies that the mechanism satisfies probabilistic do no harm by (1). Later, we demonstrate a continuous distribution that satisfies (3), implying the mechanism satisfies probabilistic positive gain.

Upward Delegation satisfies (1)
We show there exists C(n) ∈ o(n) such that the maximum weight max-weight(G n ) ≤ C(n) with high probability-that is, such that (1) holds. Fix some sampled competencies p n . Recall that each entry p i in p n is sampled i.i.d. from D, a continuous distribution. Hence, almost surely, no two competencies are equal. From now on, we condition on this probability 1 event. Now consider sampling the delegation graph G n . By the design of the mechanism M U p , we can consider a random process for generating G n that is isomorphic to sampling according to P D,M,n as follows: first, order the competencies p (1) > p (2) > · · · > p (n) (note that such strict order is possible by our assumption that all competencies are different) and rename the voters such that voter i has competence p (i) ; then construct G n iteratively by adding the voters one at a time in decreasing order of competencies, voter 1 at time 1, voter 2 at time 2, and so on.
We start with the voter with the highest competence, voter 1. By the choice of ϕ, voter 1 places weight 0 on every other voter and hence by definition does not vote. These voters form the first component in the graph G n , which we call C (1) . Then, we add voter 2 who either delegates to voter 1 joining component C (1) with probability p, or starts a new component C (2) with probability 1 − p. Next, we add voter 3. If 2 ∈ C (1) (that is, if 2 delegated to 1), 3 either delegates to 1 (either directly or through 2 by transitivity) with probability p or she starts a new component C (2) . If 2 ∈ C (2) , then 3 either delegates to 1 with probability p/2 and is added to C (1) , or delegates to 2 with probability p/2 and is added to C (2) , or starts a new component C (3) . In general, at time t, if there are k existing components C (1) , . . . , C (k) , voter t either joins each component C(j) with probability p|C(j)| t−1 or starts a new component with probability 1 − p. To construct G n , we run this process for n steps.
This is precisely the model introduced by Simon [30]. It has been studied under the name infinite Polya urn process [9] and is considered a generalization of the preferential attachment model (with a positive probability of not attaching to the existing graph).
Let U (k) t be the size of the kth component, C (k) , at time t. In general, our approach will be to show that each component C (k) remains below some o(n) function by time n with high enough probability so that we can union bound over all possible k ≤ n (there can never be more than n components in the graph). That is, we will show for some C(n) ∈ o(n) to be chosen later. Hence, it will be useful to consider this process more formally from the perspective of the kth component, C (k) . The kth component C (k) is "born" at some time t ≥ k when the kth person chooses to not delegate, at which point U (k) t = 1 (prior to this, U (k) t = 0). More specifically, the first component is guaranteed to be born at time t = 1 and for all other k > 1, it will be born at time t ≥ k with probability t−1 k−1 (1 − p) k p t−k , although these exact probabilities will be unimportant for our analysis. Once born, we have the following recurrence on U (k) t describing the probability C (k) will be chosen at time t: be the process for the size of component that is born at time k. That is, W Hence, it suffices to show that Choose γ to be a constant such that 3/4 < γ < 1 (say γ = 7/8); note that p + (1 − p)γ < p + (1 − p) = 1. Choose another constant δ such that p + (1 − p)γ < δ < 1. This additionally implies 3/4 < γ < δ. Finally, choose C(n) = n δ . We show that the probability that any component is of size greater than n δ by time n (when the delegation process completes) is negligible. That is, (9) holds for C(n) = n δ . We split our analysis into two parts: the first consider the first n γ components, while the second considers the last n − n γ components.
We first show that n γ k=1 P[W k n > n δ ] = o(1). Recall that we have W (k) k = 1, and the following recurrence for all t > k: Our first goal is to show that the expectation of W for all k ≤ n, where Γ represents the Gamma function. By the tower property of expectation, for all t ≥ k + 1, Thus, where the first four equalities follow from the recursive formula for E[U k ] = 1, the sixth and seventh by rearranging terms, the eighth uses the fact that Γ(x + 1) = xΓ(x) for all x ∈ R, and the last uses the fact that Γ(n) = (n − 1)! for all n ∈ N. This proves (10).
We can now use Markov's inequality to show that for all k, Hence, .
What remains to be shown is that To do this, first note that Γ(p+t) Γ(t) = Θ(t p ). Indeed, the fact that follows from Gautschi's inequality [13], and both the upper and lower bounds are Θ(t p ). Because n γ is an increasing function of n, we have that Further, Hence, the left-hand side of (11) is Θ(n −δ+p+γ·(1−p) ). By our choice of δ, δ > p + γ · (1 − p), so this implies that it is is o(1), as desired. Now consider the final n − n γ components. We will prove that P D,M U p ,n [W To do this, we compare the W (n γ +1) t process to another process, V t . We define V 0 = 1, and for t > 0, take V t to satisfy the following recurrence: This is identical to the W recurrence except without the p factor. Hence, V n−n γ +1 clearly stochastically dominates W (n γ +1) n . For convenience in calculation, we will instead focus on bounding V n which itself stochastically dominates V n−n γ +1 .
Next, note that the V t process is in fact isomorphic to the following classic Polya's urn process. We begin with with two urns, one with a signle ball and the other with n γ balls. At each time, a new ball is added to one of the two bins with probability proportional to the bin size. The process V t is isomorphic to the size of the the one-ball urn after t steps. Classic results tell us that for fixed starting bin sizes a and b, as the number of steps grows large, the possible proportion of balls in the a-bin follows a Beta(a, b) distribution [25,11,29,20,24].
The mean and variance of such a Beta distribution would be sufficient to prove our necessary concentration bounds; however, for us, we need results after exactly n − n γ steps, not simply in the limit. Hence, we will be additionally concerned with the speed of convergence to this Beta distribution.
Let X n = Vn n and Z n ∼ Beta(1, n γ ). From Janson [19], we know that the rate of convergence is such that, for any p ≥ 1 ℓ p (X n , Z n ) = Θ(1/n) where ℓ p is the minimal L p metric, defined as which can be thought of as the minimal L p norm over all possible couplings between X and Y . For our purposes, the only fact about the ℓ p metric we will need is that ℓ p (X, 0) = E[|X| p ] 1/p where 0 is the identically 0 random variable. Since ℓ p is in fact a metric, the triangle inequality tells us that ℓ p (0, X n ) ≤ ℓ p (0, Z n ) + ℓ p (Z n , X n ), so, combining with (12), we have that for all p ≥ 1. Note that since Z n ∼ Beta(1, n γ ), and Var[Z n ] = n γ (2 + n γ )(1 + n γ ) 2 = Θ(n −2γ ).
Given these results, we are ready to prove that V n is smaller than n δ with probability 1−o(1/n). Precisely, we want to show that P D,M U p ,n [X n ≥ n δ−1 ] = o(1). By Chebyshev's inequality, (13) with p = 1 along with the fact that X n and Z n are always nonnegative implies that We can therefore write: = Ω(n −2(δ−1) ).
as well.
Combining (14) and (15), we have that Since −2γ + 2(1 − δ) < 1, given our assumption that 3/4 < γ < δ, it follows that P D,M U p ,n [X n ≥ n δ−1 ] = o(1/n), which allows us to conclude that Since we showed earlier that n γ k=1 P D, as needed. It follows that M U p satisfies (1). Upward Delegation satisfies (2) We will show there exists α ∈ (0, 1) such that n i=1 weight i (G n ) · p i − n i=1 p i ≥ 2αn with high probability, so (2) is satisfied. Note that in the present scheme, cycles are impossible, so do need to worry about ignored voters.
Since D is a continuous distribution, there exists a < b such that π a := D[{p : p < a}] > 0 and π b := D[{p : p > b}] > 0. Let N a,n ( p n ) be the number of voters in p n with competence p i < a and N b,n ( p n ) be the number of voters with competence p i > b. When we sample competencies, since each is chosen independently, N a,n ∼ Bin(n, π a ) and N b,n ∼ Bin(n, π b ). By Hoeffding's inequality (Lemma 2) and the union bound, with probability 1 − o(1), there will be at least π a /2 · n voters with competence p i < a and π b /2 · n voters with competence p i > b. Indeed, where the first line comes from De Morgan's law, the second from the union bound, and the last from Heoffding's inequality (Lemma 2). Conditioned on this occurring, each voter with competence p i < a has probability at least pπ b /2 of delegating to a voter with competence at least b. As they each decide to do this independently, the number N ab,n of n voters deciding to do this stochastically dominates a random variable following the Bin(π a /2 · n, p · π b /2) distribution. We can again apply Hoeffding's inequality to conclude that with probability 1 − o(1), at least π a · π b · p/8 · n voters do so. Indeed, where the first inequality holds because N ab,n stochastically dominates the corresponding binomial random variable and the second holds by Hoeffding's inequality. Finally, using (16) and (17), we have Under these upward delegation mechanisms, delegations can only increase the total competence of all voters. Hence, Each of these π a · π b · p/8 · n voters results in a competence increase of at least b − a. Hence, under these high probability events, the total competence increase is at least , we see that there is an α · n increase in competence with high probability, as needed.
We have proved that for any continuous distribution D, and for well-behaved realizations of p n which occur with high probability, the graph generated from the random delegation process yields an increase in the expected sum of the votes of at least α · n. We can then conclude that M U p satisfies Equation (2) with respect to the class of continuous distributions.

Upward Delegation satisfies (3)
We now show that there exists a distribution D such that n i=1 p i +αn ≤ n/2 ≤ n i=1 weight i (G n )· p i − αn with probability 1 − o(1) for some α > 0. This implies that the mechanism satisfies probabilistic positive gain by Lemma 1, and will conclude the proof.
∼ D η , the p i s are bounded independent random variables with mean 1/2 − η, so Hoeffding's inequality directly implies that n i=1 p i ≤ n/2 − nη/2 = n/2 − nα with high probability. Now consider E F , the event consisting of instances ( p n , G n ) such that n i=1 weight i (G n ) · p i ≥ n/2 + nα. We denote by E D the event that n i=1 p i ≥ n/2 − 3nη/2. The same reasoning as before implies that Pr Dη,M U p ,n (E D ) = 1 − o(1). Let a = 1/4−η/2 and b = 1/2−η, so we have that π a := D η [p i < a] = 1/4 and π b := D η [p i > b] = 1/2. We proved in the preceding derivation that (1 − η) with high probability. Hence, if both this and E D occur, which is the case with high probability, by the union bound, it follows that n i=1 weight i (G n ) · p i > n/2 + n( p 128 (1 − η) − 3η/2) with high probability.
Since η < p 512 < 1/2, we have that and we can conclude that E F occurs with high probability. This implies that M U p satisfies Equation (3).

Confidence-Based Delegation Mechanism
We now explore a mechanism according to which voters delegate with probability that is strictly decreasing in their competence and when they do decide delegate, they do so by picking a voter uniformly at random. This models the case where voters do not need to know anything about their peers' competencies, but do have some sense of their own competence, and delegate accordingly.
Formally, for any q, let M C q = (q, ϕ 1 ) where ϕ 1 (p i , p j ) = 1 for all i, j ∈ [n]. Voter i puts equal weight on all the voters and hence samples one uniformly at random when they delegate. We refer to M C q as the Confidence-Based Delegation Mechanism.
Theorem 2 (Confidence-Based Delegation Mechanism). All mechanisms M C q with monotonically decreasing q satisfy probabilistic do no harm and probabilistic positive gain with respect to the class D C of all continuous distributions.

Confidence-Based Delegation satisfies (1)
Fix some distribution D ∈ D C . We show there exists C(n) ∈ O(log n) such that (1) holds. Note that when sampling an instance ( p n , G n ), the probability an arbitrary voter i chooses to delegate is precisely p := E D [q]. Further, since D is continuous and q is monotonically decreasing, p ∈ (0, 1). When a voter does decide to delegate, they do so by picking another voter uniformly at random. Hence, we can consider the marginal distribution of delegation graphs directly (ignoring the competencies). We will show that when sampling a delegation graph, for any specific voter i, with probability 1 − o(1/n), dels i (G n ) ≤ C(n), which implies weight i (G n ) ≤ C(n). A union bound over all n voters implies max-weight(G n ) ≤ C(n) with probability 1 − o(1).
To that end, we will describe a branching process similar to the well-known graph branching process [1], which has the property that the distribution of its size exactly matches the distribution of dels i (G n ) for an arbitrary voter i. We will compare this process to a known graph branching process that has size at most O(log n) with high probability. We will show our process is sufficiently dominated such that it too has size at most O(log n) with high probability. The branching process works as follows. Fix our voter i. We sample which other voters end up in i's "delegation tree" (i.e., its ancestors in G n ) dynamically over a sequence of time steps. As is standard for these processes, all voters V will be one of three types, live, dead, or neutral. Dead voters are those whose "children" (i.e., voters who delegate to them) we have already sampled. Live voters are voters who have decided to delegate, but whose children have not yet been sampled. Neutral voters are still in the "pool" and have yet to commit to a delegation. At time zero, i is a live voter, there are no dead voters, and all other voters V \ {i} are neutral. At each time step, we take some live voter j, sample which of the neutral voters choose to delegate to j, add these voters as live vertices and update j as dead. The procedure ends when there are no more live vertices, at which point the number of delegations received by i is simply the total number of dead vertices.
Let us now describe this more formally. Following the notation of Alon and Spencer [1], let Z t denote the number of voters we sample to delegate at time t. Let Y t be the number of live vertices at time t; we have that Y 0 = 1. At time t, we remove one live vertex and add Z t more, so we have the recursion Y t = Y t−1 − 1 + Z t . We let N t be the number of neutral vertices at time t. We have that N 0 = n − 1, and N t = N t−1 − Z t . Note that after t time steps, there are t dead vertices and Y t live ones, so this is equivalent to N t = n − 1 − t − Y t . To sample Z t , we fix some live voter j and ask how many of the neutral voters chose to delegate to j, conditioned on them not delegating to any of the dead voters. Note that when sampling at this step, there are t − 1 dead voters and conditioned on the neutral voters not delegating to the dead ones, the probability they delegate to any of the other n − t individuals (not including themselves) is exactly p n−t , equally split between them for a total delegation probability of p.
. We denote by X D n,p the random variable that counts the size of this branching process, i.e., the number of time steps until there are no more live vertices. Note that the number of delegations received by any voter has the same distribution as X D n,p . Choose some constant p ′ such that p < p ′ < 1. We will be comparing the X D n,p to a graph branching process X G n,p ′ . The graph branching process is nearly identical, except the probability each of the neutral vertex joins our component is independent of the number of dead vertices and is simply p ′ n . In other words, A key result about this branching process is the probability of seeing a component of a certain size ℓ decreases exponentially with ℓ. In other words, there is some constant c such that Take C(n) = c log (n). Note that as long as t is such that p n−t ≤ p ′ n , the sampling in the delegation branching process is dominated by the sampling in this graph branching process. Hence, as long as

Confidence Based Delegation satisfies (2)
Letq be such thatq(x) = 1 − q(x), soq represents the probability someone with competence x does not delegate and let q + (x) =q(x)x. Let µ D the mean of the competence distribution D. We first show that Indeed, since both x andq(x) are strictly increasing functions of x, the Fortuin-Kasteleyn-Ginibre (FKG) inequality [12] tells us that This implies that the expected competence conditioned on not delegating is strictly higher than the overall expected competence.
Since the p i s are bounded independent variables, it follows directly from Heoffding's inequality that n i=1 p i ≤ n(µ + γ) with high probability, so we now focus on showing n i=1 weight i (G) · p i ≥ (µ * − γ)n with high probability. To do this, we will first show that, with high probability, the delegation graph G satisfies dels i (G) ≤ C(n) for all i and total-weight(G) ≥ n − C(n) log 2 n.
We showed in the earlier part of this proof that dels i (G) ≤ C(n) with high probability. We will now prove that P D, To do this, we will first bound the number of voters that, with high probability, end up in cycles. Fix a voter i and sample i's delegation tree. Voter i will only end up in a cycle if i chooses to delegate to someone in this delegation tree. Since we are conditioning on dels i (G) ≤ C(n), the maximum size of this tree is C(n). Hence, the total ϕ weight that voter i places on someone in the tree is at most C(n), while the total weight they place on all voters is n − 1. Hence, the probability that i delegates to someone in their tree can be at most p · C(n)/(n − 1). Since this is true for each voter i, the expected number of voters in cycles is at most np C(n) (n−1) ∈ O(log n). By Markov's inequality, the probability that more than log 2 n voters are in cycles is at most np C(n) (n−1) log 2 n = O(1/ log n) = o(1). Next, since we have conditioned on dels i (G) ≤ C(n), no single voter, and in particular no single voter in a cycle, can receive more than C(n) delegations. So conditioned on the high probability event that there are at most log 2 n voters in cycles, there are at most C(n) log 2 n voters that delegate to those in cycles. This implies that total-weight(G) ≥ n − C(n) log 2 n + log 2 n with high probability.
We now show that, conditioned on the graph satisfying these properties, the instance ( p, G) satisfies n i=1 weight i (G) · p i ≥ n(µ * − γ) with high probability. Note that the competencies satisfy that those that don't delegate are drawn i.i.d. from the distribution of competencies conditioned on not delegating, which has mean µ * . Fix an arbitrary graph G satisfying the properties. Suppose M is the set of voters that do not delegate. Note that for each i ∈ M , weight i (G) ≤ C(n), by assumption. Further i∈M weight i (G) ≥ n − C(n) log 2 (n). Hence, when we sample the non- This follows from the fact that Var[p i ] ≤ 1 and that we have fixed the graph G and hence weight i (G) for each i, so these terms can all be viewed as constants. In addition, we know that, for each voter i, weight i (G) ≤ C(n), and n i=1 weight i (G) ≤ n. Hence, we can directly apply Chebyshev's inequality: where the final step holds because the numerator is o(n 2 ) and the denominator is Ω(n 2 ). Hence, i∈M weight i (G)p i ≥ n(µ * − γ) with high probability, as needed.
To summarize, we have proved that, conditioned on dels i (G) ≤ C(n) for all i and total-weight(G) ≥ n − C(n) log 2 n, n i=1 weight i (G) · p i ≥ n(µ * − γ/3) occurs with high probability. Given that, conditioned on dels i (G) ≤ C(n), total-weight(G) ≥ n − C(n) log 2 n occurs with high probability and that dels i (G) ≤ C(n) occurs with high probability, we can conclude by the chain rule that the intersection of these events hold with high probability. Given that the probability of any of this event is greater than the probability of the intersection, we can conclude that n i=1 weight i (G) · p i ≥ n(µ * − γ/3) occurs with probability 1 − o(1), as desired.

Confidence-Based Delegation satisfies (3)
We finally show there exists a distribution D such that n i=1 p i +αn ≤ n/2 ≤ n i=1 weight i (G n )· p i −αn with probability 1−o(1). This implies that the mechanism M C q satisfies probabilistic positive gain by Lemma 1.
Note that as a function of η, , the expected competence conditioned on not delegating, is continuous. Moreover, if η = 0, then Hence, for sufficiently small η > 0, We choose D η to be our distribution for this choice of η. As in the previous section, let ) and α = γ. By the earlier argument for (2), we have that with high probability n i=1 p i ≤ n(µ + γ) ≤ n/2 − αn and n i=1 weight i (G)p i ≥ n(µ * − γ) ≥ n/2 + αn.
By the union bound, we have that both occur simultaneously with high probability, so (3) holds.

Continuous General Delegation Mechanism
We finally study a mechanism in which voters delegate with probability decreasing in their competence, and if they do delegate, they do so by picking a voter according to a continuous delegation function. This is a general model that assumes only that the more competent the voter, the less likely they are to delegate, and that delegation is more likely to occur from less competent to more competent voters.
Formally, let M S p,ϕ = (q p , ϕ) where q p is a constant function equal to p, that is, q p (x) = p for all x ∈ [0, 1]. We then have the following.

The Continuous General Delegation Mechanism satisfies (1).
Our goal is to show there is some C(n) ∈ O(log n) such that, with high probability, no voter receives more than C(n) delegations. To do this, just as in the proof of Theorem 2, we consider a branching process of the delegations received beginning with some voter i. We will show that under minimal conditions on the sampled competencies (which all occur with high probability), this branching process will be dominated by a well-known subcritical multi-type Poisson branching process [5], which has size O(log n) with high probability.
For a fixed competence vector p n , the branching process for the number of delegations received by a voter i works as follows. We keep track of three sets of voters: those that are live at time t (L t ), those dead at time t (D t ), and thos neutral at time t (N t ). Unlike in the proof of Theorem 2, where it was sufficient to keep track of the number of voters in each category, here we must keep track of the voter identities as well, as they do not all delegate with the same probability. At time zero, the only live voter is voter i and the rest are neutral, so L 0 = {i}, D 0 = ∅, and N 0 = [n] \ {i}. As long as there are still live voters, we sample the next set of delegating voters Z t in time t by choosing some live voter j ∈ R t−1 and sampling its children. Once j's children are sampled, j becomes dead and j's children become live. All voters that did not delegate and were not delegated to remain neutral. The children are sampled independently; the probability that they are included is the probability they delegate to j conditioned on k not delegating to the dead voters in D t−1 .
For each voter k ∈ N t−1 , k will be included with probability . This is precisely the probability k delegates to j conditioned on them not delegating to any voter in D t−1 . We continue this process until there are no more live voters, at which point the number of delegations is simply the number of dead voters, or equivalently, the total number of time steps. We denote by X D pn,i the size of the branching process parameterized by competencies p n and a voter i ∈ [n].
Our goal will be to compare X D pn,i to the outcome of a well-known multi-type Poisson branching process. In this branching process, there are a fixed finite number k of types of voters. 5 The process itself is parameterized by a k × k matrix M , where M τ τ ′ is the expected number of children of type τ ′ a voter of type τ will have. The process is additionally parameterized by the type τ ∈ [k] of the starting voter. The random variable Y t keeps track of the number of live voters of each type; it is a vector of length k, where the τ th entry is the number of live voters of type τ . Hence, Y 0 = e τ , the (basis) vector with a 1 in entry τ and an entry 0 for all other types. We sample children by taking an arbitrary live voter of type τ ′ (the τ ′ component in Y t−1 must be positive, indicating that there is such a voter), and sampling its children Z t , which is also a vector of length k, each entry indicating the number of children of that type. The vector Z t is sampled such that the τ ′′ entry is from the Pois(M τ ′ τ ′′ ) distribution. That is, children of different types are sampled independently from a Poisson distribution, with the given expected value. We have the Note that this means that there is no "pool" of voters to choose from; in fact, it is possible for this process to grow unboundedly large (see [1,Section 11.6] for the classical description of the single-type Poisson branching process). Nonetheless, this process will still converge often enough to remain useful. We denote by X P M,τ the random variable that gives the size of this branching process, parameterized by expected-children matrix M and starting voter type τ ∈ [k]. Such a branching process is considered sub-critical if the largest eigenvalue of M is strictly less than 1 [5].
In such a case, if we begin with voter of any type τ ∈ [k], the probability of the branching process surviving ℓ steps decreases exponentially in ℓ. Hence, there is some c such that for all τ ∈ [k], In order to compare these branching processes, we make a sequence of adjustments to the original branching process that at each step creates a dominating branching process slightly closer in flavor to the multi-type Poisson. In the end, we will be left with a sub-critical multi-type Poisson process that we can bound.
Fix some ε > 0, which is a parameter in all of our steps. Later, we will choose ε to be sufficiently small (specifically, such that p (1+ε) 3 1−2ε < 1) to ensure that the Poisson branching process is sub-critical. To convert from our delegation branching process to the Poisson branching process, we take a voter's type to be their competence (which completely characterizes their delegation behavior). However, in order to compare to the Poisson process, there must be a finite number of types. Hence, we partition the interval [0, 1] into B buckets, each of size 1/B, such that voters in the same bucket delegate and are delegated to "similarly". We choose B large enough such that all points in [0, 1] 2 within a distance of √ 2/B of each other differ in ϕ by at most L · ε. (Recall that the range of ϕ is in the interval [L, U ].) This is possible since ϕ is uniformly continuous. Further, this implies any points (x, y), (x ′ , y ′ ) within a square with side length 1/B have the property that ϕ(x, y) ≤ ϕ(x ′ , y ′ ) + L · ε ≤ (1 + ε) · ϕ(x ′ , y ′ ). Note that B depends only on ϕ and ε, and hence is a constant with respect to the number of voters n.
We say a voter i is of type τ if τ −1 B < p i ≤ τ B for 1 ≤ τ ≤ B (with a non-strict inequality for τ = 1, so 0 is of type 1). Let S τ = ( τ −1 B , τ B ] be the set of competencies of type τ (except that, in the case that τ = 1, we take S 1 to be the closed interval [0, 1 B ]). Let π τ = D[S τ ] be the probability that a voter has type τ . Since the types form a partition of [0, 1], we have that B τ =1 π τ = 1. For any two types τ, τ ′ , we define ϕ(x, y). 6 We abuse notation by extending ϕ ′ to operate directly on competencies in [0, 1] by first converting competencies to types and then applying ϕ ′ . Then, ϕ ′ has the property that for any p i , p j ∈ [0, 1], We have that for all τ , if x ∈ S τ , then Hence, we defineφ We again abuse notation to allowφ to operate directly on competencies. We have thatφ(x, y) ≥ ϕ ′ (x, y) ≥ ϕ(x, y) for all competencies x, y ∈ [0, 1] and further, for all τ , B τ ′ =1φ (τ, τ ′ )π τ ′ = 1 + ε. The Poisson branching process we will eventually compare to is one with B types parameterized by the expected-children matrix M , where First we show that M has largest eigenvalue strictly less than 1 (for our choice of ε), so that the branching process will be subcritical. Indeed, M has only positive entries, so we need only exhibit an eigenvector with all nonegative entries such that the associated eigenvalue is strictly less than 1. The Perron-Frobenius theorem tells us this eigenvalue must be maximal. The eigenvector we consider is π = (π 1 , . . . , π B ) (which has nonnegative entries, as each π τ is a probability). We show it has eigenvalue p (1+ε) 3 1−2ε , strictly less than 1 due to our choice of ε. Indeed, we have that by the definition ofφ. Hence, π is our desired eigenvector.
Since X P M,τ is sub-critical for all τ , we have that there is some c such that for all τ ∈ [B], P[X P M,τ ≤ c log(n)] = 1 − o(1/n). We take C(n) = c log(n). Now we consider our branching process, X D p,i . In order to make the comparison, we will need some minimal concentration properties. We first show that the sampled competencies p satisfy these properties with high probability, and then show that, conditioned on these properties, the branching process X D p,i is easily comparable to a Poisson process. The properties are the following: 2. For each type τ ∈ [B], the number of voters of type τ , |{i | p i ∈ S τ }| ≤ (1 + ε)π τ n.
For the first property, fix the competence p i of a single voter i. Then when sampling the p j s, j =i ϕ(p i , p j ) is the sum n − 1 independent variables, all in the interval [L, U ], with mean 1. Hence, by Hoeffding's inequality, for all competencies c, where the o(1/n) term is independent of c. By the law of total probability, this implies that even when p i is sampled as well, the 1 − o(1/n) bound continues to hold. By a union bound over all n voters, this holds for everybody with probability 1 − o(1).
For the second property, note that the number of voters of type τ follows a Bin(n, π τ ) distribution. A simple application of Hoeffding's inequality implies that for this τ , |{i | p i ∈ S τ }| ≤ (1 + ε)π τ n (note that this holds even in the extreme cases where π τ = 0 or π τ = 1). As the number B of types is fixed and independent of n, a union bound over all B types implies this holds for all τ with probability 1 − o(1). Now fix some voter competencies p such that both properties hold. We will first upper bound the probability a voter of type τ delegates to a voter of type τ ′ . Hence, we can compare our branching process to one with these larger probabilities, and this will only dominate our original process.
Including the fact that ϕ(p i , p j ) ≤φ(p i , p j ) for all p i and p j , we have that for all time steps t ≤ εn/U, .
Note that for sufficiently large n, C(n) ≤ εn/U , so from now on we restrict ourselves to such n. Further, note that by the second property, there will never be more than (1 + ε)π τ n neutral voters of type τ . Hence, if we take a voter of type τ ′ at time step t ≤ C(n), the number of children it will have of type τ will be stochastically dominated by a Bin((1 + ε)π τ n, p n ·φ (1−2ε) ), and this is independent for each τ . As n grows large, this distribution approaches a Pois(p (1+ε) 1−2εφ (τ, τ ′ )). In particular, this means that for sufficiently large n, it will be stochastically dominated by a Pois(p (1+ε) 2 1−2εφ (τ, τ ′ )) distribution (note the extra (1 + ε) factor). Hence, if voter i is of type τ , up to time t ≤ C(n), X D p,i is dominated by X P M,τ , so A union bound over all n voters tells us this is true for all voters simultaneously with probability 1 − o(1), as needed.
The Continuous General Delegation Mechanism satisfies (2). To show (2) holds, we first show the following. Let µ D be the mean of the competence distribution D. For a fixed x, let ϕ + x (y) be the function ϕ(x, y) · y. We show that there is some c > 0 such that for all x ∈ [0, 1], Indeed, if we view E D [ϕ + x ] as a function of x for x ∈ [0, 1], first note that it is a continuous function on a compact set, and hence it attains its minimum. Further, for all x ∈ [0, 1], since ϕ(x, y) and y are both increasing functions of y, by the FKG inequality [12], since, by assumption, E D [ϕ(x, ·)] = 1. Hence, this attained minimum must be strictly larger than µ, implying (18).
Since ϕ(x, y) is normalized so that E y∼D [ϕ(x, y)] = 1, E y∼D [ϕ(x, y) · y] is the expected competence of the voter to whom someone of competence x delegates to (prior to other competencies being drawn). Hence, (18) tells us that "on average", all voters (regardless of competence) tend to delegate to those with competence strictly above the mean. Ideally, we would choose α ≈ c/2 and hope that some concentration result tells us that the weighted competencies post-delegation will be strictly above µ + c/2 (the mean of all competencies will be close to µ by standard concentration results). However, proving this concentration result is surprisingly subtle, as there are many dependencies between different voter delegations. Indeed, if one voter with high competence and many delegations chooses to delegate "downwards" (that is, to someone with very low competence), this can cancel out all of the "expected" progress we had made thus far. Hence, the rest of this proof involves proving concentration does in fact hold. We prove this by breaking up the process of sampling instances into much more manageable pieces, where in each, as long as nothing goes "too" wrong, concentration will hold.
In particular, we will prove that for all γ > 0, with high probability, Fix such a γ. As in the previous part, fix ε > 0 which will paramaterize our steps. We will later choose ε sufficiently small to get our desired result (precisely ε such that 6ε + ε 2 < γ). By choosing γ < c(1 − p), this value is positive, so we can choose α = c(1−p)−γ 2 which proves Equation (2) To that end, we define a sequence of six sampling steps that together are equivalent to the standard sampling process with respect to D and M S p,ϕ . In each step, we will show that with high probability, nothing "goes wrong", and conditioned on nothing going wrong in all these steps, we will get the α improvement that we desire. The six steps are as follows: , that is, the total ϕ weight they put on voters in M divided by the total ϕ weight they put on all voters.
. We now analyze each step, describing what could "go wrong". Let E 1 , . . . , E 6 be the events that nothing goes wrong in each of the corresponding steps. We define fthese events ormally below. Our goal is to show that P D,M S p,ϕ ,n [E 1 ∩ · · · ∩ E 6 ] = 1 − o(1). • Let E 1 be the event that (p−ε)·n ≤ |M | ≤ (p+ε)·n. Note that M is the sum of n independent Bernouilli random variables with success probability p. It follows directly from a union bound over both variants of Hoeffding's inequality that • Let E 2 be the event that i∈[n]\M p i ≤ n(µ + ε)(1 − p + ε). Note that i∈ [n]\M p i is the sum of n − |M | i.i.d. random variables with mean µ. Conditioning on event E 1 , |M | is lower bounded by n(p − ε), implying that n − |M | ≤ n(1 − p + ε) as well. It follows from Lemma 2 that which, combined with P D,M S p,ϕ ,n [E 1 ] = 1 − o(1), proves that E 1 ∩ E 2 occurs with probability 1 − o(1). • Let E 3 be the event consisting of all instances ( p < G) such that j∈M ϕ(p i , p j ) · p j j∈M ϕ(p i , p j ) for all i ∈ [n] \ M . We show E 3 occurs with high probability conditional on E 1 and E 1 (conditioning on E 2 is unnecessary. but makes the final statement easier). Fix a set of voters M and p i for i ∈ [n] \ M satisfying E 1 and E 2 . For each i ∈ [n] \ M , we will show that with probability 1 − o(1/n), when we sample the p j s for j ∈ M , they satisfy j∈M ϕ(p i , p j ) ≤ |M |(1 + ε) and j∈M ϕ(p i , p j ) · p j ≥ |M |(1 − ε)(µ + c).
to be the random variable representing the competence of the voter to whom i delegates. Since we know i delegates to a voter in M , note that Q i (G) = p j with probability ϕ(p i , p j ) j ′ ∈M ϕ(p i , p j ′ ) for all j ∈ M.
By conditioning on E 3 , we have that E[Q i ] ≥ (1−ε) (1+ε) (µ+c) for each i ∈ R. Hence, E[ i∈R dels i (G)· Q i ] ≥ (n − |M | − C(n) 2 log(n)) · 1+ε 1−ε · (µ + c), since we are conditioning on E 2 and E 5 . Further, for sufficiently large n, C(n) 2 log(n) ≤ εn; since we are conditioning on E 1 , |M | ≤ (p + ε)n, so we have that for sufficiently large n, Next, consider Var[ i∈R dels i (G) · Q i ]. Since each Q i takes on values in [0, 1], Var[Q i ] ≤ 1. Further, each summand is independent, as each Q i is independent and we have fixed G, so we can can view dels i (G) as a constant. Hence, Var[ i∈R dels i (G) · Q i ] ≤ i∈R dels i (G) 2 ∈ o(n 2 ) since, for all i, dels i (G) ≤ C(n) ∈ O(log n) and i dels i (G) ≤ n. Hence, where the second inequality is due to Chebyshev's inequality, which is o(1) because the numerator is o(n 2 ) and the denominator is Ω(n 2 ). This implies the desired result.

Discussion
This paper is, to the best of our knowledge, the first to study (decentralized) fluid democracy mechanisms in which concentration of power is unlikely to occur. But it relies on a set of assumptions and modeling choices that are worth discussing.
First, the assumption that there exists a ground-truth alternative seems ill-suited for some voting scenarios. We think of this assumption as viable in the legislative process, where one option can be objectively superior to another with respect to a concrete metric, even if that metric is not always apparent beforehand. For example, an economic policy can be evaluated with respect to the metric of maximizing gross domestic product in five years. However, some decisions are inherently subjective. Second, like previous papers [21,7,2], we assume that voters vote independently. Admittedly, this is not a realistic assumption; relaxing it, as it was relaxed for the classic Condorcet Jury Theorem [16,27], is a natural direction for future work.
Third, again like much of the previous work on fluid democracy, our mechanisms do not take strategic considerations into account. It would be interesting to bridge our models and those that do capture game-theoretic issues in fluid democracy [3,31].
More generally, our work aims to provide a better understanding of a prominent shortcoming of fluid democracy, namely the concentration of power. But there are others. For example, any voter can see the complete delegation graph under current fluid democracy systems -a feature that helps voters make informed delegation decisions (because one's vote can be transitively delegated).
This may lead to voter coercion, however, and the tradeoff between transparency and security is poorly understood.
Nevertheless, there are many reasons to be excited about the potential of fluid democracy [4]. We believe that our results provide another such reason, and hope that our techniques will be useful in continuing to build the theoretical understanding of this compelling paradigm.