# power_in_liquid_democracy__ba9df526.pdf

Power in Liquid Democracy

Yuzhe Zhang1, Davide Grossi1,2

1University of Groningen 2University of Amsterdam yoezy.zhang@rug.nl, d.grossi@rug.nl

The paper develops a theory of power for delegable proxy voting systems. We deﬁne a power index able to measure the inﬂuence of both voters and delegators. Using this index, which we characterize axiomatically, we extend an earlier game-theoretic model by incorporating power-seeking behavior by agents. We analytically study the existence of pure strategy Nash equilibria in such a model. Finally, by means of simulations, we study the effect of relevant parameters on the emergence of power inequalities in the model.

Introduction Liquid democracy (Blum and Zuber 2016) is a form of proxy voting (Miller 1969; Tullock 1992; Alger 2006; Green Armytage 2015; Cohensius et al. 2017) where each proxy is delegable, thereby giving rise to so-called transitive delegations. In such a system each voter may choose to cast her vote directly, or to delegate her vote to a proxy, who may in turn decide whether to vote or delegate, and so pass the votes she has accrued further to yet another proxy. The voters who decide to retain their votes the so-called gurus cast their ballots, which now carry the weight given by the number of delegations they accrued. Liquid democracy has been an inﬂuential proposal in recent public debates on democratic reform across the world, thanks also to platforms for democratic decision support such as, in particular, Liquid Feedback (Behrens et al. 2014)1. In the last couple of years it has enjoyed considerable attention from researchers in political science and e Democracy, as well as artiﬁcial intelligence (see, for an overview, Paulin (2020)).

Contribution The starting point of our paper is a controversial feature of liquid democracy: transitive delegations may in principle lead to disproportionate accrual of power, thereby harming the democratic legitimacy of the resulting vote. To the best of our knowledge, this issue has received only limited attention. A notable exception is the work of Kling et al. (2015), which provided an empirical analysis of power and inﬂuence in liquid democracy based on data from the German Pirate Party. However, a formal theory of power in voting systems with delegable proxy is lacking. We aim

Copyright c 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved. 1https://liquidfeedback.org/

at providing such a theory here, and use it to gain insights into how power may happen to be distributed among agents involved in decision-making with liquid democracy. First, we provide a generalization of the power index known as Banzhaf index to account for delegations in voting with quota rules. This novel index called delegative Banzhaf index measures not only the inﬂuence of voters, but also that of delegators. We characterize this index axiomatically (Theorem 1) and highlight how the index responds intuitively to the way in which delegations may be structured (Fact 1-3). Second, we extend the strategic model of liquid democracy developed by Bloembergen, Grossi, and Lackner (2019) to account for power-seeking behavior by agents. In our model, agents want to vote truthfully in order to relay correct information to the mechanism, but they do so by also considering how much power they retain in the system. We carry out an equilibrium analysis (pure strategy Nash equilibrium) of the model. We show equilibria may not exist if delegations are constrained (Theorem 2), but they do when everybody is allowed to delegate to anybody (Theorem 3). Finally, we simulate our game theoretic model and study how two key parameters of the model inﬂuence the distribution of power both in equilibrium and after one-shot interaction. Our experiments show that limiting the level of connectivity of the underlying network has a beneﬁcial effect in limiting the emergence of inequalities in the distribution of power (measured by Gini coefﬁcient). Perhaps less intuitively, the extent by which agents are motivated by the accumulation of power has a similar effect: groups where agents are more power-greedy appear to achieve more equal distributions of power. Proofs are sketched or omitted. All details about our proofs and experiments can be found in the full version2.

Related Work The idea of voting with delegable proxy can be traced back to Dodgson (1884) and has been object of study in the political sciences (Green-Armytage 2015). In the last couple of years, several papers in the artiﬁcial intelligence community (and in particular the computational social choice one (Brandt et al. 2016)) have focused on liquid democracy. Two lines of research have broadly been

2https://arxiv.org/pdf/2010.07070.pdf

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

pursued. On the one hand papers have pointed to potential weakenesses of voting by liquid democracy, e.g.: delegation cycles and the failure of individual rationality in multi-issue voting (Christoff and Grossi 2017; Brill and Talmon 2018); poor accuracy of group decisions as compared to those achievable via direct voting in non-strategic settings (Kahng, Mackenzie, and Procaccia 2018; Caragiannis and Micha 2019), as well as strategic ones (Bloembergen, Grossi, and Lackner 2019). On the other hand a number of papers have focused on the development of better behaved delegation schemes, e.g.: delegations with preferences over trustees (Brill and Talmon 2018) or over gurus (Escofﬁer, Gilbert, and Pass-Lanneau 2019, 2020); multiple delegations (G olz et al. 2018); complex delegations like delegations to a majority of trustees (Colley, Grandi, and Novaro 2020); dampened delegations (Boldi et al. 2011); breadth-ﬁrst delegations (Kotsialou and Riley 2020). Our paper is a contribution to the ﬁrst line of research. The possibility of large power imbalances is recognized as a potential problem for liquid democracy, although experimental work has argued the issue may be limited in practice (Kling et al. 2015). We aim at putting the discussion on power in liquid democracy on a precise footing and gain insights into how power imbalances may arise or be contained.

Preliminaries: A Model of Liquid Democracy Our model is based on the binary voting setting for truthtracking (Condorcet 1785; Grofman, Owen, and Feld 1983; Elkind and Slinko 2016). The setting has already been applied to the study of liquid democracy by Kahng, Mackenzie, and Procaccia (2018); Bloembergen, Grossi, and Lackner (2019); Caragiannis and Micha (2019).

Binary voting by truth-tracking agents A ﬁnite set of agents N = {1, 2, . . . , n} has to vote on whether to accept or reject an issue. The vote is supposed to track the correct state of the world that is whether it is best to accept or reject the issue. The agents ability to make the right choice (i.e., the agents error model) is represented by the agent s accuracy qi ( 1

2, 1], for i N. We assume the result of such an election to be determined by a quota rule with quota β ( n

2 , n]. That is, the issue is accepted if and only if there are at least β agents supporting it. We will also be working with the more general setting in which each agent is endowed with a weight. Let ω : N R+ be a weight function assigning a positive weight to every agent.3 Then the quota is β P

2 , P i N ω(i) i . That is, an issue is accepted if and only if the weight it collects from individual votes matches or exceeds the quota (cf. Chalkiadakis, Elkind, and Wooldridge (2012)).

Liquid democracy elections When agent i N delegates to agent j N we write di = j. We admit the possibility for an agent to abstain by delegating to a nul agent 0. This feature will be of technical use for the characterization of the power index we are going to introduce. Then d = (d1, d2, . . . , dn) is called a delegation proﬁle (or simply

3In the one-voter-one-vote setting, ω(i) = 1 for all i N.

proﬁle) and is a vector describing each agent s delegation. Equivalently, delegation proﬁles can be usefully thought of as maps d : N N {0}, where d(i) = di. When di = i, agent i votes on her own behalf. We call such an agent a guru. On the other hand, any agent who is not a guru, is called a delegator. For proﬁle d, and C N, let Cd denote all gurus in C in proﬁle d, i.e., Cd = {i C | di = i}. A delegation proﬁle in which all agents are gurus (i.e., for all i N di = i) is said to be trivial. We call a liquid democracy election (LDE) the tuple V = N, ω, d, β , where N is the set of agents with weights according to ω, d is a delegation proﬁle, and β is the quota. Let then V denote the set of all LDEs. Clearly, LDEs with trivial proﬁles are instances of standard weighted voting.

Gurus, chains and cycles Any proﬁle d can also be represented by a directed graph. An edge from agent i to j (i j) exists whenever di = j. Consider then a proﬁle d where a path exists from i to j, i.e., i i1 ik j. We call such paths delegation chains. When such a chain from i to guru j exists, every agent on this delegation chain (indirectly) delegates to j, and we denote i s guru by d i = d (i) = j. Additionally, the set of agents between any pair of agents on the delegation chain are called the intermediaries between the two agents. For example, suppose the above delegation chain occurs in proﬁle d. Then the set of intermediaries between i and j is {i1, . . . , ik}, and it is denoted by δd(i, j). The sum of the weights of the intermediaries between two agents i and j and the weight of j, is called the delegation distance from i to j and is denoted by d(i, j) = P a (δd(i,j) {j}) ω(a). A delegation cycle is a chain where the ﬁrst and last agents coincide. In such a case, no agent in the chain is linked to a guru. Therefore no agent linked via a delegation chain to an agent in a delegation cycle has a guru. For C N, we write D(C) = {j N | k C, d j = k} to denote the set of agents that directly or indirectly delegate to a guru in C. If C = {i} we write D(i) for the set of agents whose guru is i. One last piece of notation: we will need to consider what happens to delegation chains when we restrict to certain subsets of agents. For instance, given the chain i i1 i2 ik j, if {i, i2, . . . , ik, j} C N but i1 / C, then i is not able to delegate to j within C as she has no access to intermediary i1 in such subset. For C N we write d C(i2) = j to denote that j is the guru of i2 and the chain from i2 to j contains only elements of C. Then we write ˆD(C) = {j N | k C, d C(j) = k} for the set of agents that directly or indirectly delegate to some agent in C through intermediaries contained in C. Intuitively, this captures the support accrued by gurus in C via agents in C.

A Power Index for Liquid Democracy Once delegations are settled, liquid democracy results in weighted voting where only gurus vote with the sum of weights they accrued from direct or indirect delegations. From a voting perspective, gurus are therefore the only agents who retain voting power after the delegation phase.

However, this neglects the power that delegators actually have within liquid democracy by being able to control large number of votes. By means of a simple example: a guru i obtaining m direct delegations is intuitively more powerful than a guru obtaining m delegations via an intermediary j, who is in turn recipient of m 1 direct delegations. Most of i s power depends then on j (see also Example 1 below). So in this section we generalize the Banzhaf index (Penrose 1946; Banzhaf 1965) to the delegable proxy voting setting.4 The Banzhaf index has already been used to study the power of gurus in liquid democracy by Kling et al. (2015).

Delegative Banzhaf Index: Deﬁnition We brieﬂy recall the deﬁnition of the Banzhaf index. A simple game is a tuple G = N, ν , where N is the set of agents (|N| = n) and ν is the characteristic function ν : 2N {0, 1}. For any C N, if ν(C) = 1 then C is said to be winning, otherwise it is said to be losing. An agent i is called a swing agent for coalition C if ν(C) ν(C\{i}) = 1. Then in a simple game G, the Banzhaf index Bi(G) of agent i N is: Bi(G) = 1 2n 1 P C N\{i}(ν(C {i}) ν(C)), i.e., i s probability of being swing for a random coalition. There is one obvious way in which an LDE V induces a simple game: it is the simple game capturing the weighted voting occurring among gurus once delegations have been ﬁxed, i.e., GV = N, νV where, for any C N:

νV (C) = 1 iff X

i D(C) ω(i) β. (1)

That is, a coalition wins whenever all gurus in it together accrue enough weight to meet the quota. In such a game only gurus may have positive power: i N d if Bi(GV ) > 0, as GV is silent about the inﬂuence that delegators have in determining the winning coalitions. The inﬂuence of delegators can be captured by a different simple game G V = N, ν V where, for any C N:

ν V (C) = 1 iff X

i ˆD(C) ω(i) β. (2)

That is, a coalition C is winning whenever the sum of weights accrued by the gurus in C from agents in C, meets the quota. According to this way of constructing the simple game, an agent s weight is accrued in a coalition C if the agent, her guru, and all intermediaries between them are contained in C. We refer to G V as the delegative simple game of LDE V . Clearly, if d is trivial, all agents are gurus and therefore GV = GV . So, given an LDE V = N, ω, d, β , we deﬁne the delegative Banzhaf index of an agent i in LDE V simply as the Banzhaf index of i in the delegative simple game of V :

DBi(V ) = Bi(G V ). (3)

Observe that in LDEs V where the delegation proﬁle is trivial, and therefore games G(V ) and G (V ) coincide, the two indices coincide.

4Our approach can similarly be used to develop a generalization of the Shapley-Shubik power index (Shapley and Shubik 1954).

Figure 1: Proﬁles in Example 1

Example 1. Consider two LDEs, V1 = N, ω, d1, β and V2 = N, ω, d2, β , where N = {1, 2, 3, 4}, ω(i) = 1 for all i N, β = 3 and d1 and d2 are represented in Fig. 1a and Fig. 1b, respectively. We focus on the indices of agents 1 and 4. First consider V1. Since no coalition C N exists with ν V1(C) = 1 and ν V1(C \ {1}) = 0, DB1(V1) = 0. Then we compute DB4(V1). ν V1(C) = 1 and ν V1(C \ {4}) = 0 iff C {{2, 3, 4}, {1, 2, 3, 4}}. Thus DB4(V1) = P C N(ν V1(C) ν V1(C \ {4}))/23 = 1/4. Then consider V2. First for DB1(V2), ν V2(C) = 1 and ν V2(C \ {1}) = 0 iff C {{1, 2, 4}, {1, 3, 4}}. Therefore, DB1(V2) = P C N(ν V2(C) ν V2(C \ {1}))/23 = 1/4. For DB4(V2), we have that if C {{1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}, ν V2(C) = 1 and ν V2(C \ {4}) = 0. Then DB4(V2) = P C N(ν V2(C) ν V2(C \ {4}))/23 = 1/2.

DB depends on the structure of the delegation proﬁle. For instance, in both V1 and V2, agent 1 is a delegator with no incoming delegations, but DB1(V1) = 0 while DB1(V2) = 1/4. In V1, agent 1 is far from the guru and her vote does not matter for meeting the quota. In V2, agent 1 delegates directly to the guru. Similarly, in both LDEs agent 4 collects 4 votes. However, DB4(V1) = 1/4 but DB4(V2) = 1/2 since in V1, the delegation chain pointing to 4 is long, so that agent 4 depends on 3 for almost all her weight.

Characterization of DB

To underpin (3) we present a characterization of the delegative Banzhaf index. We want to axiomatically identify DB among all functions f : V (N R) for LDEs on N. To do so we borrow ideas and techniques from existing axiomatizations of the Banzhaf index for weighted voting games (Dubey and Shapley 1979; Nowak 1997; Lehrer 1988). The strategy we follow consists in generalizing a known characterization of the Banzhaf index for standard weighted voting due to Barua, Chakravarty, and Roy (2005). We use the same axioms of that characterization (Axioms 2-5 below), with the addition of one axiom for so-called dummy agents (Axiom 1). Crucially, however, we show how to adapt the key deﬁnitions upon which the axioms are based from the standard weighted voting setting to LDEs. This concerns in particular the deﬁnitions of composition and bloc formation (Deﬁnitions 6 and 7) which play an important role in the proof. As a result one can retrieve the known characterization of the standard Banzhaf index from ours, by simply restricting to the class of LDEs where proﬁles are trivial, and therefore delegations do not matter.

Preliminary Deﬁnitions We start by introducing standard deﬁnitions from the theory of simple games. Assume an LDE V = N, ω, d, β be given. Deﬁnition 1 (Dummy Agent). An agent i N is dummy if for any C N (i C), ν V (C) = ν V (C \ {i}), where ν is the characteristic function of the delegative simple game of V . Let N dum denote all dummy agents. That is, an agent is dummy whenever she cannot inﬂuence ν V (C) by quitting or joining any coalition C N. It is worth observing that, in LDEs there are three ways in which an agent can be dummy: if the agent abstains (i.e., delegates to 0); if the agent is linked by a chain to a delegation cycle; if the agent call it i is such that d(i, d i ) β, that is, the delegation distance between i and her guru in d is larger than β. We call such an agent distant (in d). Deﬁnition 2 (Dictator). An agent i N is a dictator if ν V (C) = 1 if and only if i C, for any C N. That is, an agent i is a dictator of V whenever it belongs to all and only the winning coalitions of the delegative simple game of V . In an LDE this occurs if the dictator i is a guru and β ω(i), that is, i meets the quota on her own. Deﬁnition 3 (Symmetric Agents). Any two agents i, j N are symmetric if for all C N\{i, j}, ν V (C {i}) = ν V (C {j}). Symmetric agents are swing for exactly the same coalitions in the delegative simple game of V . Note that a pair of symmetric agents do not necessarily have the same weight. Example 2 (Example 1 continued). Consider V1 in Figure 1a. Since β = 3 and the delegation distance d(1, 4) = 3, agent 1 is a distant (and therefore dummy) agent. Next consider agents 1 and 2 (or any pair of {1, 2, 3}) in V2, each of whom directly delegates to agent 4. For any coalition C N \ {1, 2}, ν V2(C {1}) = ν V2(C {2}), thus 1 and 2 are symmetric. There is no dictator in Example 1. The following deﬁnitions generalize the standard theory of simple games to account for delegations. Deﬁnition 4 (Minimally Winning Coalition). A coalition C N is a minimally winning coalition if for any i ˆD(C), ν V (C) = 1 and ν V (C\{i}) = 0. That is, a coalition C is minimally winning if it is winning (in the delegative simple game of V ), but becomes losing if any agent who is linked to a guru in C via agents in C is removed. So a minimally winning coalition is a coalition that contains just enough gurus with just enough support through intermediaries in the same coalition to meet the quota. It follows that no distant agent may be included in a minimally winning coalition. Notice, however, that such a coalition may contain agents that are not linked to gurus in C by intermediaries in C (i.e., that do not belong to ˆD(C)) and therefore it may not be minimal w.r.t. set inclusion. Deﬁnition 5 (Unanimity LDE (ULDE)). V is a unanimity LDE if the quota β = P i D(N) ω(i). We call such a quota unanimity quota and denote it by βU. That is, in a ULDE the quota equals the sum of weights of all agents who directly or indirectly delegate to gurus.

The last two deﬁnitions concern operations on LDEs: how to combine two LDEs into a new one; and how to build an LDE from another one by merging two agents into a bloc . Deﬁnition 6 (Composition). Let two LDEs V1 = N1, ω1, d1, β1 and V2 = N2, ω2, d2, β2 be given, such that for any i N1 N2, if d1(i) = j and j N2 (resp. d2(i) = j and j N1), d2(i) = j (resp. d1(i) = j), otherwise d2(i) = 0 (resp. d1(i) = 0), and ω1(i) = ω2(i). We deﬁne two new LDEs V1 V2 = N1 N2, ω1 2, d1 2, β1 β2 and V1 V2 = N1 N2, ω1 2, d1 2, β1 β2 , where: for any i N1 (resp. i N2), ω1 2(i) = ω1 2(i) = ω1(i) (resp. ω1 2(i) = ω1 2(i) = ω2(i)); for any i N1\N2 (resp. N2\N1), d1 2(i) = d1 2(i) = d1(i) (resp. d1 2(i) = d1 2(i) = d2(i)), and for any i N1 N2, if d1(i) = d2(i) then d1 2(i) = d1 2(i) = d1(i) = d2(i), otherwise d1 2(i) = d1 2(i) = dk(i) where k {1, 2} and dk(i) = 0; β1 β2 (resp. β1 β2) is met by C N1 N2 iff P

i ˆDC N1(C N1) ω1(i) β1 and (resp. or) P

i ˆDC N2(C N2) ω2(i) β2.

Two LDEs can be composed provided the delegation graphs at their intersection coincide or, if they do not, provided that this is because an agent in N1 N2 delegates outside the intersection under one proﬁle while she abstains (i.e., delegates to 0) under the other proﬁle. The condition is required to guarantee the coherency of delegations in the composition. Then quotas in the composition are so deﬁned as to guarantee that coalitions in the delegative simple game of the composition are winning iff they are winning in both, or at least one of, the delegative simple games of the LDEs (cf. proof of Lemma 1). Deﬁnition 7 (Bloc formation). Given V = N, ω, d, β and for any i, j N such that di = j or i, j N d, V = N , ω , d , β is called the bloc LDE joining i and j into a bloc ij, where N = N\{i, j} {ij}; For d , if di = j, d ij = dj, and for any a N, such that da = i or da = j, d a = ij, but if i, j N d, for any a N such that da = i or da = j, d a = ij; ω (ij) = ω(i) + ω(j). A bloc LDE treats two agents i and j, who are either adjacent in the delegation graph or both gurus, as one new agent ij. By applying the operation in Deﬁnition 7 repeatedly, it is possible to coalesce all agents who share the same guru into one bloc. Furthermore, any pair of delegation chains can also be joined into one bloc by joining their gurus into one bloc. Such operations play an important role in the proof of our characterization result (cf. proof of Lemma 2).

Axioms We can now introduce the axioms of our characterization. Assume again that an LDE V is given. We assign minimum power to dummy agents, maximum to dictators, and identical power to symmetric agents: Axiom 1 (No Power (NP)). If i N dum, fi(V ) = 0. Axiom 2 (Maximum Power (MP)). The power index of a dictator is 1.

Axiom 3 (Equal Treatment (ET)). For any pair of symmetric agents i, j N, fi(V ) = fj(V ).

The last two axioms concern how the index should behave with respect to composition and bloc formation.

Axiom 4 (Bloc Principle (BP)). For any two agents i, j N such that di = j, or i, j N d, let V be the bloc LDE by joining i and j into bloc ij. Then fij(V ) = fi(V )+fj(V ).

Axiom 5 (Sum Principle (SP)). For any pair of LDEs V1, V2 V, such that any i N1 N2 satisﬁes the condition in Deﬁnition 6, fi(V1 V2)+fi(V1 V2) = fi(V1)+fi(V2) for any i N1 N2.

Intuitively, Axiom 4 requires the power of the bloc, which is formed by two gurus or two adjacent agents on a delegation chain, to be the sum of their individual powers. Axiom 5 requires that the sum of any agent s power in V1 V2 and V1 V2 to be the sum of her power in V1 and V2.

Characterization The result is based on two lemmas.

Lemma 1. DB satisﬁes NP, MP, ET, BP, and SP.

Proof sketch. We prove the claim for SP as it provides a nice illustration of the workings of our deﬁnitions. The other cases are provided in the appendix. To show that DB satisﬁes the SP, one ﬁrst has to show that by the way in which weights β1 β2 and β1 β2 are set in Deﬁnition 6, we have that for any coalition C N1 N2, ν V1 V2(C) = 1 iff ν V1(C N1) = 1 and ν V2(C N2) = 1, and ν V1 V2(C) = 1 iff ν V1(C N1) = 1 or ν V2(C N2) = 1. The proof can then proceed with a standard argument. First consider any i N1 N2, i.e., agent i is contained in N1 but not in N2. Let m V i denote the number of times that agent i is swing in G V i.e., m V i = |{C N \ {i} | ν V (C) = 0, ν V (C {i}) = 1}|. Then, if i is swing in C N1 in LDE V1, she is also swing in (C C ) N1, for any C N2 N1. Therefore, in LDE V1 V2, m V1 V2 i = m V1 i 2|N2 N1|, where m V1 V2 i is the number of times that i is swing in LDE V1 V2. Additionally, since i N1 N2, m V2 i = 0, that is, i cannot be swing in LDE V2, which implies m V1 V2 i = 0. Hence we have for i N1 N2, m V1 V2 i = m V1 i 2|N2 N1| + m V2 i 2|N1 N2| m V1 V2 i . Identical equations can be developed for agent i N2 N1 or i N1 N2. Divide each side of the equation by 2|N1 N2| 1

and obtain that, for any i N1 N2, m V1 V2 i 2|N1 N2| 1 = m V1 i 2|N1| 1 +

m V2 i 2|N2| 1 m V1 V2 i 2|N1 N2| 1 , which implies that DBi(V1 V2) + DBi(V1 V2) = DBi(V1) + DBi(V2).

Lemma 2. A power index f for LDEs satisﬁes NP, MP, ET, BP, and SP, only if it is DB.

Proof sketch. The proof consists of two claims: claim 1 if f is DB for any ULDE, it is DB for any LDE; claim 2 f is DB for any ULDE. To prove claim 1 , observe that any LDE V can be represented as the disjunction of m ULDEs, i.e., V = V1 . . . , Vm, given V has m minimally winning coalitions

{C1, . . . , Cm}, where Vi = Ci, ω, d Ci, βU . By induction over the number of disjunction ULDEs we show then that if f is DB for the disjunction of any k (1 k < m) ULDEs, it is also DB for the disjunction of any k + 1 ULDEs. The claim holds by SP, since fi(V1 Vk+1) = fi(V1 Vk) + fi(Vk+1) fi((V1 Vk) Vk+1), where f is DB for V1 Vk and Vk+1 by assumption, as well as for (V1 Vk) Vk+1 because it is also disjunction of k ULDEs: (V1 Vk) Vk+1 = (V1 Vk+1) (Vk Vk+1). To prove claim 2 consider an ULDE V = N, ω, d, βU . We need to show that fi(V ) = 1/2n 1 for any non-dummy agent, and fi(V ) = 0 for any dummy agent, where n is the number of non-dummy agents in the ULDE, i.e., n = |N \ N dum|. The proof is conducted by induction on |N|. As the basis, fi(V ) = 1 if |N| = 1 by MP since i is a dictator. Assume then that the claim holds when |N| = k, we show it also holds if |N| = k + 1. For any non-dummy agent, if only one non-dummy agent exists, the claim is obvious by MP. If |N \ N dum| 2, we exploit BP to join two gurus, or a delegator with her trustee, into a bloc, then obtain an LDE with k agents where the hypothesis holds. Then the claim follows by ET. For dummy agents the claim is proven by exploiting NP.

Theorem 1. A power index for liquid democracy satisﬁes MP, NP, SP, ET, and BP, if and only if it is DB.

Proof. It follows from Lemma 1 and Lemma 2.

Further Properties of DB Besides the above axioms, it is worth mentioning a few other properties of the index that highlight its dependence on the delegation graph. Here (d i, d i) is the proﬁle obtained by changing d(i) to d i in d. Fact 1 (Delegation & Power Loss). For any pair of LDEs V = N, ω, d, β and V = N, ω, d , β , such that d = (d i, d i), d(i) = i and d i = j (i = j), we have that DBi(V ) DBi(V ). That is, delegations never lead to an increase in power for the delegator. In fact one can show that the inequality DBi(V ) DBi(V ) can be strict. The last two facts show that agents closer to the guru have more power and that, power-wise, delegating directly to a guru is better than doing that indirectly. Fact 2 (Power Monotonicity). For any pair of agents i, j N, such that di = j, DBi(V ) DBj(V ). Fact 3 (Direct vs. Indirect Delegation). Let V be a LDE, in which there exists three agents i, j, k N, such that d(i) = j and d(k) = i. Let then V = N, ω, d , β , such that d = (d k, d k) where d k = j. Then, DBk(V ) DBk(V ).

A Game-theoretic Model We will now use the DB index to extend the game-theoretic model of liquid democracy by Bloembergen, Grossi, and Lackner (2019), referred to as delegation game. Like in that model, we will be assuming that delegations are constrained by an underlying social network represented by a directed graph N, E , where each agent is a node in the network

and for any i, j N (i = j), if there is an edge from i to j, i.e. (i, j) E, j is called a neighbor of i. Let E(i) denote all neighbors of agent i, i.e., E(i) = {j N | (i, j) E}.

Delegation Games In the delegation game by Bloembergen, Grossi, and Lackner (2019) agents payoffs in an LDE depend solely on the accuracy of their gurus, and the effort agents incur should they vote directly. Here we abstract from the effort element of the model and focus instead on incorporating a power-seeking element in agents utilities. The key intuition behind our extension is to model agents that are not only interested in voting accurately, but also in their own inﬂuence during the vote. So our agents choose their delegations by aiming at maximizing the trade-off between pursuing high accuracy and seeking more power. Deﬁnition 8. A delegation game is a tuple D = N, G, {qi}i N, Σ, β, u , where: N is a ﬁnite set of agents; G = N, E is a directed graph; qi is i s accuracy; Σi = E(i) {i} is i s delegation strategy space; β ( n

2 , n] is a quota; u is the utility function, deﬁned as follows:

ui(d) = DBi(d) qd i (4)

Observe that the strategy proﬁles of this game are delegation proﬁles. Each such proﬁle d induces an LDE N, ω, d, β where we assume ω to be the standard weight function assigning weight 1 to each agent. The utility of proﬁle d for i is the accuracy that i acquires in d, multiplied by i s power in d, measured by DBi(d).5 Notice that, therefore, the utility of a dummy agent is 0 and that the utility of a dictator equals her accuracy. For our experiments we will be using the more general form of (4) given by DBi(d)α qd i , with α [0, 1]. Intuitively, parameter α will be used to control how much agents are inﬂuenced by power in the range going from no inﬂuence to inﬂuence equal to that of accuracy.

Equilibrium Analysis In this section, we ask the natural question of whether the games of Deﬁnition 8 have a Nash equilibrium (NE) in pure strategies. In general, the answer to this question is negative: Theorem 2. There are delegation games that have no (pure strategy) NE.

Sketch of proof. The proof consists in providing a delegation game and then showing that it is possible to construct a proﬁtable deviation for some agent, for every possible delegation proﬁle. The game is N = {1, 2, 3, 4, 5, 6}, q1 = 0.51, q2 = 0.7, q3 = 0.9, q4 = 0.6, q5 = 0.7, q6 = 0.9, β = 4, and the underlying directed graph is G = N, E = {(1, 3), (2, 3), (4, 6), (5, 6)} .

However NE can be guaranteed to exist when the underlying network is complete. Theorem 3. In any delegation game D = N, {qi}i N, G, Σ, β, u , where G is a complete network, there exists at least one (pure strategy) NE.

5Notice that we slightly abuse notation here by using d directly as input for the index, instead of the corresponding LDE.

Sketch of proof. First of all observe that on a complete network, if an equilibrium exists, it must be such that all delegation chains are of length 1 by Fact 3. The theorem is then proven by construction. We construct a proﬁle by letting each agent choose, in turn according to a given sequence, whether to delegate to agent i N, who has the highest accuracy, or to be a guru. If an agent decides to delegate to i , this delegation is assumed to be ﬁxed. So the set of delegators (to i ) monotonically increases. The process continues until no guru wants to delegate. We show that the proﬁle constructed in such a way is a NE by showing that: 1 i has no proﬁtable deviation because were she deviating to a delegator, she would form a cycle (thereby obtaining utility 0), and were she delegating to another guru she would inherit a lower accuracy (by assumption) and have lower power (by Fact 1). 2 No delegator has a proﬁtable deviation, neither by delegating to another delegator (by Fact 3), nor by delegating to another guru (as she would inherit lower accuracy and obtain lower power), nor by becoming herself a guru. The latter claim requires some work and can be shown by proving that as more agents delegate to i , the power of delegators does not decrease while that of gurus (except for i ) does. 3 Finally, no guru has a proﬁtable deviation, neither by delegating to i (by construction), nor to another guru (as she would then be better off delegating to i ), nor by delegating to a delegator (again, by Fact 3).

Experiments We use the above model to study, by means of experiments, how the distribution of power in proﬁles is affected by speciﬁc parameters. In particular, we are interested in gaining insights into: whether higher connectivity of the underlying network increases power imbalances; whether the more agents are driven by power the less they tend to delegate.

Setup Starting from the trivial proﬁle, we generate proﬁles in two ways: by one-shot interaction (OSI), in which each agent selects her neighbor (including herself) which maximises her utility; and by iterated better response dynamics (IBRD), in which each agent iteratively selects one neighbor at random and delegates to her only if this increases her utility, until a stable state (equilibrium) is reached. As one might expect, the bottleneck in our experiments consists in the computation of DB in order to establish agents utilities by Eq. (4). It is well-known that computing the Banzhaf index in weighted voting games is intractable (Matsui and Matsui 2001). We therefore implement the approximation method described by Bachrach et al. (2008). Each time we need to estimate the DB of an agent, 15000 coalitions are randomly sampled (by uniform distribution), and the ratio of the coalitions for which the agent is swing is used as the estimator of the DB. By the analytical bounds proven by Bachrach et al. (2008), with the above method we know that the correct DB is in the conﬁdence interval [ c DB 0.011, c DB + 0.011] with probability of 0.95, where c DB is the estimator. So it should be clear that the statistics presented in this section report on values that depend on the estimator c DB, and that with high probability are close to the

p 0.0 0.2 0.4 0.6 0.8

(a) A: ratio of delegators

0.0 0.5 1.0

(b) B: ratio of delegators

p 0.0 0.2 0.4 0.6 0.8

(c) A: average DB

0.0 0.5 1.0

0.100 0.075

0.025 0.000

(d) B: average DB

p 0.0 0.2 0.4 0.6 0.8

(e) A: Gini coefﬁcient

0.0 0.5 1.0

(f) B: Gini coefﬁcient

Figure 2: Selected plots from experiments A and B

exact intended values. We will be working with two parameters. To test the effect of connectivity on power we assume that interaction happens on a random network and vary the probability p (see range in e.g., Fig. 2a) of any two agents being linked. To test the effect of different attitudes towards the importance of power for agents we work with the generalization DBi(d)α qd i of (4) with α {0, 0.25, 0.5, 0.75, 1} and assuming an underlying random network with p = 0.75. We set |N| = 30, the quota β = 16, and for each parameter setting, we use an accuracy vector Q R30, where each element in Q is drawn from a Gaussian distribution N(0.75, 0.125). All statistics are the mean value over 50 instances for each parameter setting. Further details on the setup of our experiments, including pseudo-code for the algorithms of OSI and IRBD are provided in the appendix.

Connectivity: experiment A Fig. 2a shows that the higher the connectivity (the larger p), the more agents tend to delegate both in equilibrium (IBRD) and in one-shot interaction (OSI). This is in line with expectations as agents have more chance to interact with high-accuracy agents. It is worth observing, however, that the ratio of delegators is very low (less than 0.06 on average). That is, very few agents delegate on average. This is in contrast with the behavior of the delegation game where utility is solely based on accuracy (cf. Bloembergen, Grossi, and Lackner (2019)). We will see with experiment B that the inﬂuence of power on agents utility seems to be an important factor in limiting vs. facilitating delegations. Despite the small number of delegations we can still observe that increasing p lowers the mean value

of DB (Fig. 2c) and increases inequality in the distribution of DB, measured by the Gini coefﬁcient (Fig. 2e), although it should be stressed the Gini coefﬁcient remains very low due to the small fraction of delegators. Intuitively, more delegations enhance some agents power, but reduce the power of other agents, be they gurus or delegators.

Power: experiment B Fig. 2b shows that larger values of α correspond to signiﬁcantly fewer delegators for OSI. As agents put more weight on power they are more reluctant to delegate in the initial proﬁle (recall Fact 1). For IRBD this effect is observable only for α in the upper half of the range of available values. We argue this may depend on the fact that IRBD, at the initial proﬁle, allows for delegations to take place that only suboptimally improve utility, triggering then further delegations at later iterations. As α grows, the average power increases (Fig. 2d) and inequality in the distribution of power decreases (Fig. 2f). The decreasing ratio of delegators (Fig. 2b) is another side of this trend: as α decreases the group turns from consisting mostly of delegators (α {0, 0.25}) to low numbers of delegators comparable to those observed in experiment A (α = 1). Interestingly, the average length of chains also signiﬁcantly decreases from around 5.5 for α = 0 to 1.2 for α = 0.25, and further mildly decreases to around 0.5 for α = 1. This is in line with Fact 3: as power becomes more important, agents prefer shorter chains to their gurus.

We also ran experiments to identify the effects of varying quota β in the range {0.6|N|, 0.8|N|, |N|}. We identiﬁed a similar trend showing that higher quota tend to limit the amount of delegations, but our results were less robust than those reported in experiments A and B. The reﬁnement of this experiment is left to future work.

Conclusions

The paper developed a power index for voting with delegable proxy. We showed that the index generalizes the Banzhaf index for standard weighted voting and can be axiomatized in a similar fashion. We used the index to model a variant of delegation games for liquid democracy where agents seek to ﬁnd a tradeoff between increasing their accuracy and acquiring power in the system. We showed equilibria for this sort of interaction exist under a full connectivity condition, but do not exist in general. Finally, two parameters of the model were shown, through simulations, to play an important role in containing the emergence of large inequalities in the distribution of power: the level of connectivity of an underlying (random) network, and the extent to which agents are motivated by the acquisition of power. The paper opens several directions for future research of both theoretical and experimental kind. Here we mention one: it would be interesting to understand how much agents attitude towards power could help in readdressing the deterioration of decision-making quality highlighted by Kahng, Mackenzie, and Procaccia (2018); Caragiannis and Micha (2019), through its equalizing effect on power distribution.

Acknowledgments The authors would like to thank the anonymous reviewers of AAAI 21 for their helpful comments. The authors are grateful to Shuaipeng Liu for helpful insights on the proof of Theorem 3.

References Alger, D. 2006. Voting by proxy. Public Choice 126(1-2): 1 26. doi:10.1007/s11127-006-3059-1.

Bachrach, Y.; Markakis, E.; Procaccia, A. D.; Rosenschein, J. S.; and Saberi, A. 2008. Approximating power indices. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2, 943 950.

Banzhaf, J. 1965. Weighted Voting Doesn t Work: A Mathematical Analysis. Rutgeres Law Review 19: 317 343.

Barua, R.; Chakravarty, S. R.; and Roy, S. 2005. A New Characterization of the Banzhaf Index of Power. International Game Theory Review 07(04): 545 553. doi:10.1142/ S0219198905000703.

Behrens, J.; Kistner, A.; Nitsche, A.; and Swierczek, B. 2014. Principles of Liquid Feedback. Interaktieve Demokratie.

Bloembergen, D.; Grossi, D.; and Lackner, M. 2019. On rational delegations in liquid democracy. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, volume 33, 1796 1803.

Blum, C.; and Zuber, C. I. 2016. Liquid democracy: Potentials, problems, and perspectives. Journal of Political Philosophy 24(2): 162 182.

Boldi, P.; Bonchi, F.; Castillo, C.; and Vigna, S. 2011. Viscous democracy for social networks. Communications of the ACM 54(6): 129 137.

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

Brill, M.; and Talmon, N. 2018. Pairwise Liquid Democracy. In IJCAI, 137 143.

Caragiannis, I.; and Micha, E. 2019. A Contribution to the Critique of Liquid Democracy. In Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, 116 122.

Chalkiadakis, G.; Elkind, E.; and Wooldridge, M. 2012. Computational Aspects of Cooperative Game Theory. Morgan & Claypool.

Christoff, Z.; and Grossi, 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 17), volume 251, 134 150. EPTCS.

Cohensius, G.; Mannor, S.; Meir, R.; Meirom, E.; and Orda, A. 2017. Proxy Voting for Better Outcomes. In Proceedings

of the 16th Conference on Autonomous Agents and Multi Agent Systems, 858 866. International Foundation for Autonomous Agents and Multiagent Systems.

Colley, R.; Grandi, U.; and Novaro, A. 2020. Smart Voting. In Proceeding of the the 29th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 2020.

Condorcet, M.J.A.N. de C., M. d. 1785. Essai sur l Application de l Analyse a la Probabilit e des D ecisions Rendues a la Pluralit e des Voix. Paris: Imprimerie Royale.

Dodgson, C. L. 1884. The Principles of Parliamentary Representation. Harrison and Sons.

Dubey, P.; and Shapley, L. S. 1979. Mathematical Properties of the Banzhaf Power Index. Mathematics of Operations Research 4(2): 99 131. ISSN 0364765X, 15265471.

Elkind, E.; and Slinko, A. 2016. Rationalizations of Voting Rules. In Handbook of Computational Social Choice, chapter 8, 169 196. Cambridge University Press.

Escofﬁer, B.; Gilbert, H.; and Pass-Lanneau, A. 2019. The Convergence of Iterative Delegations in Liquid Democracy in a Social Network. In Proceedings of the International Symposium on Algorithmic Game Theory (SAGT 19), 284 297.

Escofﬁer, B.; Gilbert, H.; and Pass-Lanneau, A. 2020. Iterative Delegations in Liquid Democracy with Restricted Preferences. In Proceedings of the 34th AAAI Conference on Artiﬁcial Intelligence (AAAI 20), 1926 1933.

G olz, P.; Kahng, A.; Mackenzie, S.; and Procaccia, A. D. 2018. The Fluid Mechanics of Liquid Democracy. In Proceedings of the 14th Conference on Web and Internet Economics (WINE 18), 188 202.

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.

Kahng, A.; Mackenzie, S.; and Procaccia, A. 2018. Liquid Democracy: An Algorithmic Perspective. In Proc. 32nd AAAI Conference on Artiﬁcial Intelligence (AAAI 18).

Kling, C.; Kunegis, J.; Hartmann, H.; Strohmaier, M.; and Staab, S. 2015. Voting Behaviour and Power in Online Democracy: A Study of Liquid Feedback in Germany s Pirate Party. In Proceedings of the International Conference on Weblogs and Social Media.

Kotsialou, G.; and Riley, L. 2020. Incentivising Participation in Liquid Democracy with Breadth-First Delegation. In Proceedings of the International Foundation for Autonomous Agents and Multiagent Systems (AAMAS 20), 638 644. Richland, SC: IFAAMAS. ISBN 9781450375184.

Lehrer, E. 1988. An axiomatization of the Banzhaf value. International Journal of Game Theory 17(2): 89 99.

Matsui, Y.; and Matsui, T. 2001. NP-completeness for calculating power indices of weighted majority games. Theoretical Computer Science 263(1): 305 310. ISSN 0304-3975.

doi:https://doi.org/10.1016/S0304-3975(00)00251-6. Combinatorics and Computer Science. Miller, J. C. 1969. A program for direct and proxy voting in the legislative process. Public choice 7(1): 107 113. Nowak, A. S. 1997. On an axiomatization of the banzhaf value without the additivity axiom. International Journal of Game Theory 26(1): 137 141. Paulin, A. 2020. An Overview of Ten Years of Liquid Democracy Research. In Proceedings of the 21st International Conference on Digital Government Research. Penrose, L. 1946. The Elementary Statistics of Majority Voting. Journal of the Royal Statistical Society 109(1): 53 57. Shapley, L.; and Shubik, M. 1954. A method for Evaluating the Distribution of Power in a Committee System. American Political Science Review 48(3): 787 792. Tullock, G. 1992. Computerizing politics. Mathematical and Computer Modelling 16(8-9): 59 65. doi:10.1016/ 0895-7177(92)90087-2.