--- title: "Measuring a Priori Voting Power in Liquid Democracy" authors: - "Rachael Colley" - "Théo Delemazure" - "Hugo Gilbert" doi: "10.24963/ijcai.2023/290" url: "https://ijcai.org/proceedings/2023/290" pdf: "https://ijcai.org/proceedings/2023/0290.pdf" venue: "Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence" year: 2023 pages: "2607-2615" track: "Main Track" keywords: - "Game Theory and Economic Paradigms: GTEP: Computational social choice" --- # Measuring a Priori Voting Power in Liquid Democracy Rachael Colley, Théo Delemazure, Hugo Gilbert *Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence*, pages 2607-2615. DOI: [10.24963/ijcai.2023/290](https://doi.org/10.24963/ijcai.2023/290) ## Abstract We introduce new power indices to measure the a priori voting power of voters in liquid democracy elections where an underlying network restricts delegations. We argue that our power indices are natural extensions of the standard Penrose-Banzhaf index in simple voting games. We show that computing the criticality of a voter is #P-hard even in weighted games with weights polynomially-bounded in the size of the instance. However, for specific settings, such as when the underlying network is a bipartite or complete graph, recursive formulas can compute these indices for weighted voting games in pseudo-polynomial time. We highlight their theoretical properties and provide numerical results to illustrate how restricting the possible delegations can alter voters' voting power. ## Full text ## 1 Introduction Voting games have been used extensively to study the a priori voting power of voters participating in an election [Felsenthal and Machover, 1998]. A priori voting power means the power granted solely by the rules governing the election process. Notably, these measures do not consider the nature of the bill nor the affinities between voters. The class of I-power measures (where I represents influence) "calculate" how likely a voter will influence the outcome. Several I-power measures have been defined, the best known being the PenroseBanzhaf measure in simple voting games [Banzhaf III, 1964; Penrose, 1946]. In simple voting games, an assembly of voters come to a collective decision on a proposal which voters may either support or oppose. The Penrose-Banzhaf measure is as follows: voters are assumed to vote independently from one another; a voter is as likely to vote in favour or against the proposal. It then measures the probability of a voter altering the election's outcome, given this probabilistic model. Simple voting games have been extended in several directions to take into account more complex and realistic frameworks. For example, taking into account abstention [Freixas, 2012], several levels of approval [Freixas and Zwicker, 2003], or coalition structures [Owen, 1981]. Hence, new power indices have been designed to better understand voters' criticality in these frameworks. However, elections with delegations have been largely unexplored with respect to a priori voting power. Still, frameworks such as Proxy Voting (PV) [Miller, 1969; Tullock, 1992] or Liquid Democracy (LD) [Behrens et al., 2014; Brill, 2018] have received increasing interest in the AI community due to their ability to provide more flexibility and engagement in the voting process. Thus, studying these frameworks via their distribution of a priori voting power is an interesting research direction. Our Contribution. We extend simple voting games to model elections where voters can delegate their votes along a social network, modelled as a digraph G. Our model encapsulates both the LD and PV settings. We design a new I-voting power measure to quantify the voters' criticality in these settings. We argue that our power measure is a natural extension of the Penrose-Banzhaf measure, and we illustrate the intuitions behind it through various examples. When G is an arbitrary digraph, we show that the computation of our measure is #P-hard in Weighted Voting Games (WVGs) even when voters' weights are polynomially-bounded in the number of voters. However, we prove that it can be computed for WVGs in pseudo-polynomial time in the PV setting, in which G is directed bipartite with all arcs going from one side (possible delegators) to the other (proxies), and in the LD setting when G is complete. Last, we complement our theoretical results with numerical results to illustrate how introducing delegations modifies voters' a priori voting power. 1 ## 1.1 RelatedWork Voting Power. Measuring a voter's voting power in a specific setting quantifies how critical they are in deciding the outcome of the election. A voter i's voting power can be considered as the difference in probability of i voting for the issue when the outcome is also in favour and i voting for the issue when the outcome is not [Gelman et al., 2002]. We give an overview of some standard measures (we recommend [Lucas, 1974] for an overview of voting power and [Felsenthal and Machover, 2005] for a historical overview). The measure introduced by Shapley and Shubik [1954] quantifies the voter's expected pay-off, known as P-power, unlike the other measures we will discuss. P-power differs in motivation from I-power as it cares about a voter being in the winning coalition, sharing the coalition's utility among its members, with those not in the coalition receiving utility 0. In contrast, I-power has a policy-seeking motivation and is, therefore, concerned with the voter's stance on the issue. 1 Omitted proofs and additional results can be found in the long version of this article [Colley et al., 2023]. I-power was independently given a mathematical explanation by Penrose [1946], Banzhaf III [1964], and Coleman [1971]. It counts, for an agent i, in how many of the 2n possible profiles changing i's vote from 0 to 1 changes the outcome. The Banzhaf measure (or absolute Banzhaf index) is denoted by β′ , whereas the Banzhaf index is the relative quantity denoted by β (found from normalising β′ ). Extending the Notion of Voting Power. Standard voting power measures are defined on binary issues. Yet, as the study of voting models has advanced, so has the study of voting power. One generalisation is to the domain of the available votes, thus, moving away from binary decisions on the issue. Influenced by Felsenthal and Machover [2001], probabilistic models of voting power with abstention and a binary outcome are well-studied [Felsenthal and Machover, 1997; Freixas, 2012]. Freixas and Lucchetti [2016] extended the Banzhaf index by introducing two measures of being positively critical, i.e., changing your vote from being for the issue to abstaining and abstaining to being against the issue. Voting games with approvals form a subclass of voting games with varying levels of approvals in both the input and output of the election [Freixas and Zwicker, 2003]. Another well-studied extension of the standard notions of voting power measures in WVGs is to allow for randomised weights. The Shapley-Shubik index has been well-studied in these settings [Filmus et al., 2016; Bachrach et al., 2016]. Boratyn et al. [2020] also studied the Banzhaf index in this setting; this is close to our own work when focusing on PV elections. Proxy Voting (PV) and Liquid Democracy (LD). PV allows agents to choose their proxy from a list of representatives who will vote on their behalf. In some models, a delegator may only choose a proxy from the list of representatives [Abramowitz and Mattei, 2019; Alger, 2006; Cohensius et al., 2017]. In other models, delegators can also vote directly yet still cannot receive votes [Green-Armytage, 2015; Miller, 1969; Tullock, 1992]. Models of LD allow voters to either vote on the issue or delegate their vote to another voter, which can be transitively delegated further. Some examples of recent advancements in the study of LD are: extending the model to account for different situations, whether it be ranked delegations [Brill et al., 2022; Colley et al., 2022; Kotsialou and Riley, 2020] or allowing for multiple interconnected issues [Brill and Talmon, 2018; Jain et al., 2022; Colley and Grandi, 2022]; assessing how successful LD is in finding a ground truth [Halpern et al., 2021; Kahng et al., 2018]; or studying (non-cooperative) game-theoretic aspects [Bloembergen et al., 2019; Escoffier et al., 2020; Markakis and Papasotiropoulos, 2021; Noel et al., 2021]. Our closest work is that of Zhang and Grossi [2021], who study a version of the Banzhaf measure in LD. Their measure, for a given delegation graph, determines how critical an agent is in changing the outcome. Our work differs as we focus on a priori voting power, where no prior knowledge is known about the election, such as a specific delegation graph. ## 2 Model Let V be a set of n voters taking part in an election to decide if some binary proposal should be accepted or not. Each voter has different possible actions: they may vote directly, either for (1) or against (-1) the proposal, or delegate their vote to another voter. A voter who decides to vote (resp. delegate) will be termed a delegatee (resp. delegator). An underlying social network G = (V, E) restricts the possible delegations between the agents, hence voter i ∈ V can only delegate to a voter in their out-neighbourhood NBout(i) = {j ∈ V | (i, j) ∈ E}. We will consider in more detail two cases: when G is complete and when G is bipartite with all arcs going from one side to the other, where the former corresponds to the LD setting when voters can choose any other voter as a delegate and the latter corresponds to the PV setting. Definition 1. Given a digraph G = (V,E), a G-delegation partition D is a map defined on V such that D(i) ∈ NBout(i)∪ {-1, 1} for all i ∈ V . We let D be the set of all such partitions and D-, D+, and Dv be the inverse images of {-1}, {1} and {v} for each v ∈ V under D. A direct-vote partition divides the voters into partition cells that correspond to a possible voting option. We let abstentions model situations where delegators do not have a delegatee voting on their behalf (e.g., due to delegation cycles). Definition 2. A direct-vote partition of a set V is a map T from V to the votes {-1, 0, 1}. We let T -, T 0 , and T + denote the inverse images of {-1}, {0} and {1} under T . A G-delegation partition D naturally induces a direct-vote partition TD by resolving the delegations. First, we let voters in D-, and D+ also be in T -, and T +, respectively. From this point, for some ◦ ∈ {-, +}, if v′ ∈ Dv and v ∈ T ◦ , then v′ ∈ T ◦ . This continues until no more voters can be added to T + or T -. The remaining unassigned agents abstain and thus are in T 0 . This procedure assigns agents their delegate's vote unless it leads to a cycle. In this case, their vote is recorded as an abstention. Next we define a partial ordering ≤ among direct-vote partitions: if T1 and T2 are two direct-vote partitions of V , we let: T1 ≤ T2 ⇔ T1(x) ≤ T2(x), ∀x ∈ V . Definition 3. A ternary (resp. binary) voting rule is a map W from the set {-1, 0, 1}n (resp. {-1, 1}n ) of all direct-vote partitions (resp. all direct-vote partitions without abstention) of V to {-1, 1} satisfying the following conditions: Note that ternary (and binary) voting rules only use the direct-vote partition to find an outcome, i.e., only the information of which agents voted directly or indirectly in favour or against the proposal or abstained. Thus, these rules do not need the delegations to find an outcome. 2 Not all ternary voting rules satisfy monotonicity, e.g., a weighted voting rule with an additional quorum condition. However, we enforce this condition such that we may only look at the election result when the voter favours the proposal on the one hand and against the proposal on the other to define criticality. Figure 1: The underlying network G used in Example 1. While all edges give us E, the solid edges give us a valid G-delegation partition where the superscripts of + or - represent the direct votes of the delegatees. Each node's subscript refers to its voting weight. ![Image](https://ijcai.org/proceedings/2023/fulltext/290/image_000000_e5e3b010c6f9be76f9f78051c3ee046e7b599f0230b24676c1ee394529fba508.png) A ternary (resp. binary) voting rule is symmetric if W(T) = -W(-T), where -T is the direct-vote partition defined by -T(x) = -(T(x)), ∀x ∈ V . Moreover, for ease of notation, we may also use W(T +, T -) to denote W(T), noting that T 0 can be obtained from T + and T -. Weighted Voting Games. Weighted Voting Games (WVGs) express ternary voting rules compactly, with a quota q ∈ (0.5, 1] and a map w : V → N>0 assigning each voter a positive weight. Given a set S ⊆ V , we let w(S) = ∑i∈S w(i). In a WVG with weight function w, we let W(T) = 1 if and only if w(T +) > q ×w(T + ∪T -), i.e., the proposal is accepted if the sum of the voters' weights for the proposal is greater than a proportion q of the total weight of non-abstaining voters; otherwise, the proposal is rejected. Example 1. Consider agents V = {a, b, · · · ,m} connected by the underlying network G as depicted in Figure 1. The solid lines give a valid G-delegation partition D with D+ = {c, i}, D- = {a, b, h}, Da = {d}, Db = {e}, Dc = {f, g}, Dd = {j, k}, Dℓ = {m}, and Dm = {ℓ}. This Gdelegation partition induces the following direct-vote partition: T + = {c, f, g, i}, T - = {a, b, d, e, h, j, k}, and T 0 = {ℓ,m}. Consider W induced by the WVG where q = 0.5 and w(a) = 3, w(b) = w(d) = 2 and the remaining voters x ∈ V \{a, b, d} have weight w(x) = 1. The proposal is rejected under this G-delegation partition as w(T +) = 4 ≤ 7.5 = q · w(T + ∪ T -). We conclude this subsection with some notation. Given a set X, let Pk(X) denote the set of k ordered partitions of X. By ordered partitions, we mean that ({1}, {2, 3}) should be considered different to ({2, 3}, {1}). Next, given a voting rule W, a voter i ∈ V , and (X, Y,Z) three non-intersecting subsets of V \ {i}, we define: We say a voter i ∈ V is critical when they can affect the outcome of the vote. Thus for three non-intersecting subsets of V \ {i}, namely X, Y,Z, where X (resp. Y ) denotes the set of voters supporting (resp. opposing) the proposal through their vote of delegation, and Z is the set of voters delegating directly or indirectly to i, then i is critical iff δW i,-→+(X, Y, Z) > 0. We say a voter i ∈ V is positively (resp, negatively) critical if by changing a positive (resp. negative) vote to a negative (resp. positive) one, the outcome will also change from being for to against (resp. against to for) the issue. In Example 1, we see that a is critical in this G-delegation partition, as V \{a} is partitioned as such X = {c, f, g, i}, Y = {b, e, h} and Z = {d, j, k} and thus δW a,-→+(X, Y, Z) = 1-(-1) 2 = 1. ## 2.1 Modelling a Priori Voting Power We aim to measure a priori voting power in this setting. An agent's voting power is their probability of being able to affect the election's outcome. Similarly to the intuitions behind the Penrose-Banzhaf measure, we invoke the principle of insufficient reason. There are two ways of seeing this principle. The Global Uniformity Assumption. If there is no information about the proposal or voters, we assume all G-delegation partitions are equally likely with probability Πi∈V 1 |NBout(i)|+2 . In Example 1, as |NBout(i)| = 2 for every i ∈ V , this means that every G-delegation partition occurs with probability ( 14 )13 . The Individual Uniformity Assumption. The global uniformity assumption is similar to a model in which each voter delegates with probability pid = |NBout(i)|/|NBout(i)|+2 and votes with probability piv = 1 - pid = 2/|NBout(i)|+2. Delegation (resp. voting) options are chosen uniformly at random and voters make their choices independently from one another. This is consistent with the idea that we have no information about voters' personalities and interests, or the nature of the proposal. Hence, voters should be equally likely to support (probability py) or oppose (probability pn) the proposal, i.e., py = pn = 1/2. Moreover, in ignorance of any concurrence or opposition of interests between voters, we should assume that the likelihood of a voter choosing between each of their possible delegates is equally likely, i.e., the probability that a delegator i delegates to a voter j ∈ |NBout(i)| is 1/NBout(i). The individual uniformity assumption is an extension of the global uniformity assumption in which pid can be any value in [0, 1] dependent on |NBout(i)|, such that pid = 0 when NBout(i) = ∅. For generality, we consider this latter model unless specified otherwise. We now define the LD Penrose-Banzhaf measure of a voter i for a given underlying graph G when considering that the probability of each G-delegation partition is determined by the individual uniformity assumption. Definition 4 (LD Penrose-Banzhaf measure). Given a digraph G = (V,E) and a ternary voting rule W, the LD Penrose-Banzhaf measure of voter i ∈ V is defined as: where P(D) is the probability of the G-delegation partition D occurring, and D+ i (resp. Di ) is the G-delegation partition identical to D with the only possible difference being that i supports (resp. opposes) the proposal. Mld i quantifies the probability of sampling a delegation partition where i is able to alter the election's outcome (formally stated in the following Theorem). Theorem 1. Given a digraph G = (V,E), a ternary voting rule W, and a voter i ∈ V , we have that: Moreover, if NBout(i) = ∅ or W is symmetrical, we have that: This proof relies on the fact that we are summing over the probability of each D with respect to W(TD+ i ) - W(TDi ), which measures when the voter i is critical. Recall that being positively critical means that by changing a vote for the issue to against it, the outcome will also change in the same way (negatively critical is defined similarly). Furthermore, this happens equally when NBout(i) = ∅ (the only option is to vote either for or against the issue) or when W is symmetric. For the second part of Theorem 1, the condition is necessary as if W reflects unanimity, i.e., W(T) = 1 if and only if T = 1, then voters will be more likely to be positively critical than negatively critical. 3 Additionally, observe that the LD Penrose-Banzhaf measure of voting power extends the standard Penrose-Banzhaf measure (formalized in Proposition 1) and that its values are not normalized (i.e., summing over the agents does not yield 1). The corresponding voting power index can be defined by normalizing over voters. Proposition 1. If pid = 0 for all i ∈ V , e.g., if E = ∅, then the LD Penrose-Banzhaf measure of voting power is equivalent to the standard Penrose-Banzhaf voting power measure. ## 3 Hardness of Computation Computing the standard Penrose-Banzhaf measure in WVGs is #P-complete [Prasad and Kelly, 1990]. However, it can be computed by a pseudo-polynomial algorithm that runs in polynomial time with respect to the number of voters and the maximum weight of a voter [Matsui and Matsui, 2000]. We show that the problem of computing the LD Penrose-Banzhaf measure is #P -hard even when voter's weights are bounded linearly by the number of voters. Hence, a similar pseudopolynomial algorithm is unlikely to exist. The proof uses an enumeration trick inspired by that of Chen et al. (2010, Theorem 1). Informally speaking, this trick shows that one can solve the #P -hard problem of counting the number of simple paths between two vertices in a digraph by using a polynomial number of calls to a subroutine of our power measure computation problem and inverting a specific Vandermonde matrix. As a result, note that the type of reduction that is used is a Turing reduction. Theorem 2. Given a digraph G = (V,E) and a WVG defined on V , computing the LD-Penrose-Banzhaf power measure of a voter is #P-hard under Turing reductions even when voter's weights are bounded linearly by the number of voters. 3 If the voting rule requires total agreement to accept the proposal, then voter i will be critical iff all delegatees (other than i) agree on the proposal. Thus, the probability that i is critical while voting directly or indirectly in favour of the proposal is higher than i being critical while voting directly or indirectly against it. Proof sketch. We give a reduction from the problem of counting simple paths in a digraph which is known to be #Pcomplete [Valiant, 1979]. The problem takes as input a digraph G = (V, E) and nodes s, t ∈ V . The problem then returns the number of simple paths from s to t in G. Let denote Pℓ the set of paths of length ℓ between s and t in G. Given G = (V,E) and s, t ∈ V two vertices, we create |V | + 1 different digraphs Gk = (Vk,Ek) with k ∈ {0, . . . , |V |} such that Gk is obtained by modifying G to impose some condition on the out-degree of nodes in V . Thus, in each digraph Gk = (Vk,Ek), we consider a WVG where weights are linearly bounded in |V | and such that voter s is a dictator. Hence, t is only critical when in s's delegation path. Under the individual uniformity assumption, we obtain the criticality of t in each Gk as a weighted sum of values |Pℓ| such that the weights of these |V | + 1 equations form a Vandermonde matrix. Inverting this matrix makes it possible to derive the values |Pℓ| from the criticality of t in each graph Gk, and thus to solve the problem of counting simple paths from s to t. While computing the LD Penrose-Banzhaf voting power measure exactly is hard, it can be approximated easily by using a standard sampling procedure. We sample enough Gdelegation partitions by simulating the behaviours of the different voters according to the individual uniformity assumption and consider the expected criticality of the voters given these samples. Relying on Hoeffding's inequality, one can then prove that these estimates are within some ϵ of the true voting power measure (technical details are discussed by Colley et al. [2023]). In the next two sections, two restricted classes of instances are discussed. In both, more compact formulations of the LD Penrose-Banzhaf measure can be designed such that pseudopolynomial algorithms can compute the measure exactly. ## 4 Proxy Voting This section models a PV setting where G = (V, E) is bipartite with V = (Vd, Vv) and E = {(i, j) | i ∈ Vd, j ∈ Vv}. The set of delegatees Vv is given in input and is predetermined, e.g., by an election, self-nomination, or sortition. Each delegatee i ∈ Vv will vote, i.e., NBout(i) = ∅ and pd = 0, whereas each voter i ∈ Vd can vote or delegate to any delegatee in Vv, i.e., NBout(i) = Vv. 4 Note that, under our individual uniformity assumption, the probability of delegating for each i ∈ Vd is equal as they all have the same out-degree. We denote this value by pd and let pv = 1 - pd. Moreover, let nv = |Vv| and nd = |Vd| = n-nv. We provide a more compact version of the LD Penrose-Banzhaf measure in this PV setting. We consider binary voting rules as there are no delegation cycles in this setting (T 0 = ∅). To measure how critical an agent i can be, we consider partitions of V \{i} into three sets V +, V -, V i where V + (resp. V -) represents the n+ (resp. n-) voters whose final vote is in favour of (resp. against) the proposal, either by voting directly or indirectly and V i is the set of ni voters who delegate to voter i. Note that V +, V -, V i form a partition of V \{i} and V i = ∅ when i ∈ Vd. We focus on how these sets intersect Vd and Vv. We define V + d , V - d , V + v , and V - v with size n+d , n-d , n+v , and n-v , respectively, such that V ◦ x = Vx ∩ V ◦ for x ∈ {v, d} and ◦ ∈ {-, +}. 4 Colley et al. [2023] present an alternative PV model where voters in Vd must delegate to a voter in Vv, showing that voters' criticalities can also be computed by a pseudo-polynomial algorithm. Given our probabilistic model of delegation partitions, observe that the probability of having a partition V +, V -, V i only depends on these cardinalities. More precisely: - When i ∈ Vv, note that n-v = nv - 1 - n+v and ni = nd - n+d - n-d . Hence, we denote this probability of having such a partition V +, V -, V i by Pv(n+v , n+d , n-d ): - When i ∈ Vd, note that n-v = nv - n+v and n-d = nd - 1 - n+d . We let Pd(n+v , n+d ) denote the probability of having such a partition of V +, V -: There are some conditions on the integer parameters n+v , n+d , and n-d . If i ∈ Vv, we have that n+v ≤ nv-1, and n+d +n-d ≤ nd. If i ∈ Vd, we have n+v ≤ nv, and n+d ≤ nd - 1. If these conditions are not respected, we set Pv(n+v , n+d , n-d ) = 0 (resp. Pd(n+v , n+d ) = 0). We now detail Equation 1 (Equation 2 is obtained similarly). The probability of the binary votes of the delegatees other than i being a certain way is (1/2)nv-1 . Then, the probability that each voter in V + d (resp. V - d ) votes in favour of the proposal is pv/2 + pdn+v/nv (resp. against is pv/2 + pdn-v/nv) where the first summand corresponds to the case in which the voter votes and the second to the one in which they delegate. Last, the probability that each voter in V i d delegates to i is pd/nv. Equation 1 is the product of these terms. Given the probability of having a partition V +, V -, V i of V \ {i}, the voting power measure for a voter in our PV setting i ∈ V can be formulated in the following way. Proposition 2. Given a bipartite digraph G = (V,E) with V = (Vd, Vv) and E = {(i, j)|i ∈ Vd, j ∈ Vv} and a binary voting rule W , the LD Penrose-Banzhaf measure Mld i (W,G) of voter i ∈ V can be formulated as: We return to Example 1 to illustrate our power measures. Notably, we shall see that a voter in Vv with a small weight can achieve a higher criticality through delegation. Table 1: Mld when pd = 0, 0.5, 0.9 for voters V = {a, · · · ,m} in the PV setting with Vv = {a, b, c} (Values are rounded to 3 d.p.). | Agent x ∈ V | pd = 0 | pd = 0.5 | pd = 0.9 | |---------------|----------|------------|------------| | a: w = 3 | 0.511 | 0.552 | 0.542 | | b: w = 2 | 0.306 | 0.395 | 0.438 | | c: w = 1 | 0.148 | 0.303 | 0.390 | | d: w = 2 | 0.306 | 0.206 | 0.138 | | Vd\{d}: w = 1 | 0.148 | 0.098 | 0.065 | Example 2. Consider the voters in Example 1; however, now in the PV setting, we assume that Vv = {a, b, c} and Vd = V \Vv and we compute the voters' LD Penrose-Banzhaf measures using Proposition 2. The resulting power measures can be seen in Table 1 when pd = 0, 0.5, 0.9. As those in Vd have the possibility of voting directly as well as delegating, they have more influence on the outcome when they are more likely to vote directly; conversely, those in Vv have less as they are less likely to receive delegations. When pd = 0, all agents vote and thus, we return to a standard WVG with the standard Banzhaf measure where all voters with the same weight have the same voting power. Computational Aspects. We turn to some computational aspects regarding the PV setting. We obtain that the exact computation of the LD measure of voting power is #P-hard due to Proposition 1 [Prasad and Kelly, 1990]. More positively, we show that in WVGs, Mld in the PV setting can be computed in pseudo-polynomial time, like the PenroseBanzhaf measure. This result uses the following lemma. Lemma 1. Given a WVG with weight function w and an integer c. Computing the number of ways of having a partition (S1, S2, . . . , Sc) in Pc(S) of a set S ⊆ V with sizes n1, n2,. . ., nc with ∑cl=1 nl = |S|, and weights w(S1) = w1, w(S2) = w2, . . ., and w(Sc) = wc with ∑cl=1 wl = w(S) can be computed in pseudo-polynomial time. Theorem 3. Given a bipartite digraph G = (V, E) with V = (Vd, Vv) and E = {(i, j)|i ∈ Vd, j ∈ Vv}, a WVG with weight function w and quota-ratio q, and a voter i, measure Mld i can be computed in pseudo-polynomial time. ## 5 Liquid Democracy with Complete Digraph This section discusses the case where G = (V,E) is complete, representing LD where any voter can vote directly or delegate their vote to any other voter. Since the graph is complete, every voter has the same out-degree |V |-1. Under our individual uniformity assumption, this implies that the probability to delegate pd is the same for every voter. As with PV, we provide a more compact formulation of our power measure by grouping over similar voters instead of summing over all delegation partitions. By abuse of notation, we say that a set S of voters form an in-forest when the graph obtained by having a vertex per voter in S and an arc from i to j when i delegates to j forms an in-forest. We consider a partition of V \ {i} into four sets V +, V -, V 0 , V i where V + (resp. V -) is a set of n+ (resp. n-) voters voting directly in favour of (resp. against) the issue or indirectly by transitively delegating to a root voter in V + (resp. V -); V 0 is a set of n0 voters abstaining as their delegation leads to a delegation cycle; and V i is the set of ni voters delegating (directly or not) to i. Note that V +,V -,V 0 and V i form a partition of V \ {i}. We will use recursive formulas to compute the probability of having such a partition into four sets. Let P ld (m, p) be the probability that the m voters of a set S ⊆ V form an in-forest where the roots all make the same action; 5 an action which is chosen by each root voter with probability p. For instance, P ld (n+, pv/2) would be the probability that the voters in V + form a forest where each root voter is in favour of the proposal. Consider an arbitrary voter j ∈ S, and a two partition (S1, S2) ∈ P2(S \ {j}) with respectively m1 and m2 = m- 1 -m1 voters. The voters in S1 are those who delegate directly or indirectly to j, while voters in S2 do not. Another way of seeing it is that all voters in S1 form an inforest where every root delegates to voter j (with probability pd/(n-1)), while voters in S2 form an in-forest where every root realizes the same action as in S. Regarding voter j, there are two possibilities: either voter j realizes the same action as the roots of S (e.g., voting for the proposal), or they delegate to a member of S2 (with probability pdm2/(n-1)). Hence, we obtain the following recursive formula: with m2 = m - 1 - m1 and base cases P ld (1, p) = p and P ld (0, p) = 1. Thus, the probability that V + (resp. V -) forms an in-forest where the roots vote in favour of (resp. against) the issue is P ld (n+, pv/2) (resp. P ld (n-, pv/2)); and that the probability that V i forms an in-forest where the roots delegate to voter i is P ld (ni , pd/(n - 1)). For V 0 , we need a different formula. Voters in V 0 have their delegation leading to a delegation cycle through other voters in V 0 iff each voter in V 0 delegates to another voter in V 0 . This occurs with probability P ld 0 (n0 ) = (pd(n0-1)/(n-1))n0 . Consequently, the probability of having the four partition (V +, V -, V i , V 0 ) of V \{i} is equal to P ld (n+, pv/2)P ld (n-, pv/2)P ld (ni , pd/(n - 1))P ld 0 (n0 ). Proposition 3. Given a complete digraph G = (V,E) and a ternary voting rule W, the LD Penrose-Banzhaf measure Mld i (W,G) of voter i ∈ V can be formulated as: Example 3. We return to the agents V = {a, · · · ,m} from the previous examples, with the same weights as before; however, we are in the LD setting where the underlying network is a complete digraph. In Table 2, we see the power measures of 5P ld (m, p) depends only on |S| and p, and not on the list of voters in S, and thus is independent in the choice of voters in S. Table 2: Mld x (rounded to 3 d.p.) for pd ∈ {0, 0.5, 0.9} for v = {a, · · · , m} from Example 1 when considering a complete network. | Agent x ∈ V | pd = 0 | pd = 0.5 | pd = 0.9 | |---------------------|----------|------------|------------| | a: w = 3 | 0.511 | 0.424 | 0.696 | | b, d: w = 2 | 0.306 | 0.308 | 0.638 | | V \{a, b, d}: w = 1 | 0.148 | 0.212 | 0.568 | each agent where the probability of delegating varies. When pd = 0, we are in the standard weighted voting game where all agents vote directly. When pd = 0.5, those with less voting weight have their voting power measure increase, this is due to the possibility of others delegating to them and the voting weight they control becoming higher. Note that when pd = 1, all agents are caught in delegation cycles and T 0 = V . Thus, we also give the measures when pd = 0.9. In simulated examples, similar to Example 3, we noticed two trends. First, a flattening effect on the power measures as pd increased. By this, we mean that the difference between the lowest and highest measure of power in the WVG (for any agent) becomes smaller. For instance, in Table 2, this difference is 0.363, 0.212, and 0.128 for pd = 0, 0.5, and 0.9, respectively. This flattening, in our LD setting, is due to all voters having the same available voting actions, no matter their weights. Notably, there can be no dummy agents when pd > 0, as for any agent, the delegation partition where all other voters delegate to them has a positive probability. Second, as illustrated by Table 2, we see that when the probability of delegating increases, so does the probability of being critical, especially when the weights are equal. 6 As when pd increases, the number of direct voters decreases while the expected accumulated weight of an agent increases. Hence, they are more likely to be critical when they vote directly. Although it seems intuitive that as the probability of delegating increases, so does the probability of being critical, this is not generally true. In Table 2, we indeed observe that the criticality of voter a decreases when pd increases from 0 to 0.5. Computational Aspects. Using Proposition 3 and Lemma 1, we show that, if the digraph is complete, our power measure can be computed in pseudo-polynomial time. Theorem 4. Given a complete digraph G = (V, E), a WVG with weight function w and quota-ratio q, and a voter i, Mld i can be computed in pseudo-polynomial time. The idea of this result is as follows. We can compute the number of ways λ of having a partition (S1 , S2 , S3 , S4 ) in P4(V \{i}) with sizes n+, n-, n0 , ni , and weights w+, w-, w0 , and wi using Lemma 1, and may compute the product λ × P ld (n+, pv 2 )P ld (n-, pv 2 )P ld (ni , pd n-1 )P ld 0 (n0 ). The result is the sum of these terms for the different tuples (n+, n-, n0 , ni ,w+,w-,w0 ,wi ) for which i is critical. The number of tuples to be considered is bounded by n3 ×w(V )3 . ## 6 Experiments We performed numerical tests on our power measure to test the impact of the different parameters. For each experiment, we estimate the criticality of voters by sampling over delegation-partitions due to the long runtimes required for exact calculations. Colley et al. [2023] give the sampling details as well as additional experimental results. 6 We conjecture that when voting weights are equal, the probability of being critical strictly increases with pd. Figure 2: The probability of an agent being critical in the PV setting with pd varying from 0 to 1. We have |V | = 100, |Vv| ∈ {20, 50}, and W is a WVG with all weights equal to 1 and q = 0.5. This experiment sampled over 100,000 delegations partitions. ![Image](https://ijcai.org/proceedings/2023/fulltext/290/image_000001_aad6dcf4092b16253c4baacb3b430538c002ab677d38d395e50758639ab77965.png) We first computed the criticality of voters with a variety of underlying networks. First, we observed a strong correlation between the voters' criticality and their in-degree in the network. This follows the intuition that the higher the in-degree of a voter, the higher the number of voters that can delegate to them. Second, we noticed that the type of the underlying network had a large impact on the differences between the voters' criticality. In particular, inequality in voting power was the largest on preferential attachment networks [Barab´asi and Albert, 1999] and the smallest on small-world networks [Watts and Strogatz, 1998]. We will now focus on two special cases, bipartite digraphs and complete digraphs. ## 6.1 The Number of Delegators in Proxy Voting In the experiments on proxy voting, we study the case when all voters have the same voting weight and delegators can delegate to any delegatee, as in Section 4. Note that within either Vv or Vd, all voters have the same voting power. We inspect the effect of pd in the PV setting, i.e., does the probability of those in Vd delegating affect the probability of being critical for both those in Vv and Vd. We set |V | = 100 and look at two different amounts of delegatees, |Vv| ∈ {20, 50}. In Figure 2, when pd = 0 we obtain the standard voting model where all agents vote directly and thus have the same chance of being critical. In both instances, as pd increases, so does the delegatees' probability of being critical, yet the probability of the delegators being critical decreases, reflecting the intuition that there is some transfer of power from the delegators to the delegatees when pd increases. Observe that the difference between the criticality of the delegators and delegatees is smaller when |Vv| = 50 than when |Vv| = 20 for every value of pd, as a higher number of delegatees share a lower number of delegators. Thus in the PV setting, increasing |Vv| will flatten the distribution of criticalities. Figure 3: The probability of an agent being critical when the underlying graph is complete, varying pd from 0 to 0.9. We have |V |=100 in a WVG W with 50 (resp. 30, 20) voters with weights of 1 (resp. 2, 5) and q=0.5 and sampled over 10,000 delegations partitions. ![Image](https://ijcai.org/proceedings/2023/fulltext/290/image_000002_033ec0984cead367d30dfef1fb3aa0cdcda8aae50d930e6789419b24ed763c8e.png) ## 6.2 The Effect of Voters' Weights in the LDModel We study the impact of pd in the LD model where the underlying network is complete as in Section 5. We have |V | = 100 voters, with 50 voters (resp. 30 and 20) having weight 1 (resp. 2 and 5). The quota of the WVG remains q = 0.5. We vary pd between 0 and 0.9. In the case pd = 1, all voters delegate to each other, and thus they all have a criticality of 1. In Figure 3, we see that voters with higher weights have more voting power. We observe a flattening effect: the initial gap between the criticality of agents with different weights becomes increasingly small as pd increases. As in Table 2, the criticality of voters with smaller weights always increases with pd while it is not the case for voters with weight 5. ## 7 Conclusion This paper continues the tradition of extending the notion of a priori voting power to new voting models. We have introduced the LD Penrose-Banzhaf measure to evaluate how critical voters are in deciding the outcome of an election where delegations play a key role. We study a general setting where an underlying graph restricts the possible delegations of the voters. We provided a hardness result on the computation of our measure of voting power. Nevertheless, we designed a sampling procedure to estimate them as well as two pseudopolynomial algorithms that can be used when the graph restricting the delegations is either bipartite or complete. There are several possible directions for future work. First, one could study the same models with more voting options, such as abstention. We have restricted ourselves to two voting options (approving or disapproving) to keep these new models simple. Another direction would be to find the conditions, such as adding or removing neighbours, that affect the power measure. Additionally, by extending the Coleman indices, one could study how to differentiate the ability to support an initiative from vetoing it in our setups. Lastly, analysing realelection data using our model is a promising option. ## Acknowledgments Rachael Colley acknowledges the support of the ANR JCJC project SCONE (ANR 18-CE23-0009-01). Th´eo Delemazure was supported by the PRAIRIE 3IA Institute under grant ANR-19-P3IA-0001 (e). Hugo Gilbert acknowledges the support from the project THEMIS ANR-20-CE23-0018 of the French National Research Agency (ANR). ## References 1. [Abramowitz and Mattei, 2019] Ben Abramowitz and Nicholas Mattei. Flexible representative democracy: An introduction with binary issues. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 3-10, 2019. 2. [Alger, 2006] Dan Alger. Voting by proxy. Public Choice, 126(1):1-26, 2006. 3. [Bachrach et al., 2016] Yoram Bachrach, Yuval Filmus, Joel Oren, and Yair Zick. A characterization of voting power for discrete weight distributions. In Proceedings of the 25th International Joint Conference on Artificial Intelli- gence, IJCAI 2016, New York, NY, USA, July 9-15, 2016, pages 74-80, 2016. 4. [Banzhaf III, 1964] John F Banzhaf III. Weighted voting doesn't work: A mathematical analysis. Rutgers L. Rev., 19:317, 1964. 5. [Barabási and Albert, 1999] Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. 6. [Behrens et al., 2014] J. Behrens, A. Kistner, A. Nitsche, and B. Swierczek. The principles of LiquidFeedback. Interack- tive Demokratie, Berlin, 2014. 7. [Bloembergen et al., 2019] Daan Bloembergen, Davide Grossi, and Martin Lackner. On rational delegations in liquid democracy. In Proceedings of the 33rd AAAI Con- ference on Artificial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, January 27 -February 1, 2019, pages 1796-1803, 2019. 8. [Boratyn et al., 2020] Daria Boratyn, Werner Kirsch, Wojciech Słomczyński, Dariusz Stolicki, and Karol Życzkowski. Average weights and power in weighted voting games. Mathematical Social Sciences, 108:90-99, 2020. 9. [Brill and Talmon, 2018] Markus Brill and Nimrod Talmon. Pairwise liquid democracy. In Proceedings of the 27th In- ternational Joint Conference on Artificial Intelligence, IJ- CAI 2018, Stockholm, Sweden, July 13-19, 2018, pages 137-143, 2018. 10. [Brill et al., 2022] Markus Brill, Théo Delemazure, Anne- Marie George, Martin Lackner, and Ulrike Schmidt- Kraepelin. Liquid democracy with ranked delegations. In Proceedings of the 26th AAAI Conference on Artifi- cial Intelligence, AAAI 2022, Virtual Event, February 22 -March 1, 2022, pages 4884-4891, 2022. [Brill, 2018] Markus Brill. Interactive democracy. In Pro- ceedings of the 17th International Conference on Au- tonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pages 1183-1187, 2018. 11. [Chen et al., 2010] Wei Chen, Yifei Yuan, and Li Zhang. Scalable influence maximization in social networks under the linear threshold model. In Proceedings of the 10th IEEE International Conference on Data Mining, ICDM 2010, Sydney, Australia, December 14-17, 2010, pages 88-97, 2010. 12. [Cohensius et al., 2017] Gal Cohensius, Shie Mannor, Reshef Meir, Eli A. Meirom, and Ariel Orda. Proxy voting for better outcomes. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Sys- tems, AAMAS 2017, São Paulo, Brazil, May 8-12, 2017, pages 858-866, 2017. 13. [Coleman, 1971] James S Coleman. Control of collectivities and the power of a collectivity to act. Social choice, pages 269-300, 1971. 14. [Colley and Grandi, 2022] Rachael Colley and Umberto Grandi. Preserving consistency in multi-issue liquid democracy. In Proceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, July 23-29, 2022, pages 201-207, 2022. 15. [Colley et al., 2022] Rachael Colley, Umberto Grandi, and Arianna Novaro. Unravelling multi-agent ranked dele- gations. Autonomous Agents and Multi-Agent Systems, 36(1):1-35, 2022. 16. [Colley et al., 2023] Rachael Colley, Théo Delemazure, and Hugo Gilbert. Measuring a priori voting power-taking delegations seriously. arXiv preprint arXiv:2301.02462, 2023. 17. [Escoffier et al., 2020] Bruno Escoffier, Hugo Gilbert, and Adèle Pass-Lanneau. Iterative delegations in liquid democracy with restricted preferences. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, AAAI 2020, New York, NY, USA, February 7-12, 2020, pages 1926-1933, 2020. 18. [Felsenthal and Machover, 1997] Dan S Felsenthal and Moshé Machover. Ternary voting games. International journal of game theory, 26(3):335-351, 1997. 19. [Felsenthal and Machover, 1998] Dan S Felsenthal and Moshé Machover. The measurement of voting power: Theory and practice, problems and paradoxes. In The Measurement of Voting Power. Edward Elgar Publishing, 1998. 20. [Felsenthal and Machover, 2001] Dan S Felsenthal and Moshé Machover. Models and reality: the curious case of the absent abstention. In Power indices and coalition formation, pages 87-103. Springer, 2001. 21. [Felsenthal and Machover, 2005] Dan S Felsenthal and Moshé Machover. Voting power measurement: a story of misreinvention. Social choice and welfare, 25(2):485-506, 2005. 22. [Filmus et al., 2016] Yuval Filmus, Joel Oren, and Kannan Soundararajan. Shapley values in weighted voting games with random weights. arXiv preprint arXiv:1601.06223, 2016. 23. [Freixas and Lucchetti, 2016] Josep Freixas and Roberto Lucchetti. Power in voting rules with abstention: an ax- iomatization of a two components power index. Annals of operations research, 244(2):455-474, 2016. 24. [Freixas and Zwicker, 2003] Josep Freixas and William S Zwicker. Weighted voting, abstention, and multiple lev- els of approval. Social choice and welfare, 21(3):399-431, 2003. 25. [Freixas, 2012] Josep Freixas. Probabilistic power indices for voting rules with abstention. Mathematical Social Sci- ences, 64(1):89-99, 2012. 26. [Gelman et al., 2002] Andrew Gelman, Jonathan N Katz, and Francis Tuerlinckx. The mathematics and statistics of voting power. Statistical Science, pages 420-435, 2002. 27. [Green-Armytage, 2015] James Green-Armytage. Direct voting and proxy voting. Constitutional Political Econ- omy, 26(2):190-220, 2015. 28. [Halpern et al., 2021] Daniel Halpern, Joseph Y Halpern, Ali Jadbabaie, Elchanan Mossel, Ariel D Procaccia, and Manon Revel. In defense of fluid democracy. arXiv preprint arXiv:2107.11868, 2021. 29. [Jain et al., 2022] Pallavi Jain, Krzysztof Sornat, and Nim- rod Talmon. Preserving consistency for liquid knapsack voting. In Proceedings of the 19th European Conference on Multi-Agent Systems, EUMAS 2022, Düsseldorf, Ger- many, September 14-16, 2022, pages 221-238, 2022. 30. [Kahng et al., 2018] Anson Kahng, Simon Mackenzie, and Ariel D. Procaccia. Liquid democracy: An algorithmic perspective. In Proceedings of the 32nd AAAI Confer- ence on Artificial Intelligence, AAAI 2018, New Orleans, Louisiana, USA, February 2-7, 2018, pages 1095-1102, 2018. 31. [Kotsialou and Riley, 2020] Grammateia Kotsialou and Luke Riley. Incentivising participation in liquid democ- racy with breadth-first delegation. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020, Auckland, New Zealand, May 9-13, 2020, pages 638-644, 2020. 32. [Lucas, 1974] W Lucas. Measuring power in weighted vot- ing systems. Technical report, Cornell University Opera- tions Research and Industrial Engineering, 1974. 33. [Markakis and Papasotiropoulos, 2021] Evangelos Markakis and Georgios Papasotiropoulos. An approval-based model for single-step liquid democracy. In Proceedings of the 14th International Symposium on Algorithmic Game The- ory, SAGT 2021, Aarhus, Denmark, September 21-24, 2021, pages 360-375, 2021. 34. [Matsui and Matsui, 2000] Tomomi Matsui and Yasuko Matsui. A survey of algorithms for calculating power in- dices of weighted majority games. Journal of the Opera- tions Research Society of Japan, 43(1):71-86, 2000. 35. [Miller, 1969] James C Miller. A program for direct and proxy voting in the legislative process. Public choice, 7(1):107-113, 1969. 36. [Noel et al., 2021] Jonathan A. Noel, Mashbat Suzuki, and Adrian Vetta. Pirates in wonderland: Liquid democracy has bicriteria guarantees. In Proceedings of the 14th Inter- national Symposium on Algorithmic Game Theory, SAGT 2021, Aarhus, Denmark, September 21-24, 2021, pages 391-405, 2021. 37. [Owen, 1981] Guillermo Owen. Modification of the banzhaf-coleman index for games with a priori unions. In Power, voting, and voting power, pages 232-238. Springer, 1981. 38. [Penrose, 1946] Lionel S Penrose. The elementary statistics of majority voting. Journal of the Royal Statistical Society, 109(1):53-57, 1946. 39. [Prasad and Kelly, 1990] Kislaya Prasad and Jerry S Kelly. NP-completeness of some problems concerning voting games. International Journal of Game Theory, 19(1):1- 9, 1990. 40. [Shapley and Shubik, 1954] Lloyd S Shapley and Martin Shubik. A method for evaluating the distribution of power in a committee system. American political science review, 48(3):787-792, 1954. 41. [Tullock, 1992] Gordon Tullock. Computerizing politics. Mathematical and Computer Modelling, 16(8-9):59-65, 1992. 42. [Valiant, 1979] Leslie G Valiant. The complexity of enumer- ation and reliability problems. SIAM Journal on Comput- ing, 8(3):410-421, 1979. 43. [Watts and Strogatz, 1998] Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440-442, 1998. 44. [Zhang and Grossi, 2021] Yuzhe Zhang and Davide Grossi. Power in liquid democracy. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Event, February 2-9, 2021, pages 5822-5830, 2021.