# smart_voting__be775c3b.pdf

Smart Voting

Rachael Colley , Umberto Grandi and Arianna Novaro IRIT, University of Toulouse {rachael.colley, umberto.grandi, arianna.novaro}@irit.fr

We propose a generalisation of liquid democracy in which a voter can either vote directly on the issues at stake, delegate her vote to another voter, or express complex delegations to a set of trusted voters. By requiring a ranking of desirable delegations and a backup vote from each voter, we are able to put forward and compare four algorithms to solve delegation cycles and obtain a ﬁnal collective decision.

1 Introduction Advances in information technology are opening up avenues for the improvement of democratic practices and collective decision-making processes (see, e.g., Brill [2018]). One of the most popular ideas is to explore the space between direct democracy often infeasible due to the limited amount of resources decision-makers can invest in each direct vote and representative democracy, by allowing for transitive delegations to take place among agents. This method is named liquid democracy, in contrast to proxy voting in which delegations are not transitive [Miller, 1969]. Liquid democracy has been the subject of numerous recent investigations in AI, ranging from analysing its truth-tracking power [Cohensius et al., 2017; Bloembergen et al., 2019; Kahng et al., 2018] to its adaptation for multiple issues and alternatives [Christoff and Grossi, 2017; Brill and Talmon, 2018]. In its simplest form, liquid democracy works as follows: a collective decision needs to be taken on a binary issue; agents can either vote directly or delegate their vote to a single other agent; direct votes are then weighted by the number of transitive delegations received, and a ﬁnal decision is taken using a standard voting rule. In this paper we propose to push forward the idea of liquid democracy under two aspects. First, while most implementations of liquid democracy [see, e.g., Behrens et al., 2014] introduce a platform for the elicitation of voters delegations, we aim at a decentralised voting system in which voters ballots and delegations can remain private. Thus, we deﬁne a language for voters to express a direct vote, or a delegation to a single other agent, or a combination of the votes of multiple other agents. Second, to tackle the issue of delegation cycles we allow voters to express a number of prioritized delegations, with a ﬁnal backup vote with the lowest priority. An

Liquid democracy Smart voting

Figure 1: A proﬁle of binary votes in liquid democracy on the left: voter A delegates her vote to B, who in turn delegates to C, who casts a direct vote in favour, unlike D who casts a direct vote against. On the right, a proﬁle of smart ballots: voter A wants her vote to coincide with the majority of B, C, and D s votes, and in case this leads to a delegation cycle she gives a single delegation to B. Voter B delegates to D, who casts a direct vote against, while C votes in favour. Voters A and B abstain (*) as their ﬁnal backup option.

example of what we call a smart ballot can be seen on the right-hand side of Figure 1. Two possible practical implementations can be envisaged for smart voting. The ﬁrst is a fully decentralised version that might make use of smart contract technology (hence the title of this paper), where a smart ballot would be a piece of self-executable and publicly available code included in a blockchain, with full transparency and accountability of the election procedure.1The second, in applications where vote secrecy is crucial, is a more standard method of votes being collected by a trusted central authority raising interesting computational questions on providing a certiﬁcate to each voter that their ballot has been taken into account. Our contribution. We deﬁne a script language for voters to express ranked, possibly complex, delegations in collective decisions with multiple issues (Section 2). The intended application is voting in a purely preferential setting (deciding on food is a perfect example [see, e.g., Hardt and Lopes, 2015]), and delegations are seen as a way to elicit trust or inﬂuence relations among voters. To transform proﬁles of smart ballots into direct votes for alternatives we propose four unravelling procedures (Section 2), and we show that they terminate in polynomial time (Section 3). The ﬁnal objective of smart voting is that of obtaining a collective decision from the agents

1Recent work by Dhillon et al. [2019] conducts a detailed analysis of smart contracts for electronic voting and liquid democracy. See also the reports of Kotsialou et al. [2018] and Riley et al. [2019].

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

ballots, and we assume here that a standard voting rule is applied on the outcome of the proposed unravelling procedures. We investigate further algorithmic properties of our setting in Section 3, and we conclude with a study of ranked delegations to single voters and participation axioms (Section 4). Some proofs are sketched or omitted due to space constraints. Related work. Recent papers have analysed the efﬁcacy of liquid democracy and proxy voting as a truth-tracking mechanism, mostly for a binary decision [Green-Armytage, 2015; Cohensius et al., 2017; Kahng et al., 2018; Caragiannis and Micha, 2019; Bloembergen et al., 2019]. We do not study truth-tracking here, and rather propose a method to elicit mutual inﬂuence from voters and infer a collective decision. This work takes inspiration from papers trying to solve the issue of delegation cycles. As in the work of Kotsialou and Riley [2020] and Escofﬁer et al. [2019; 2020], we let voters express a ranking of possible delegates, to break potential cycles of delegations.2 We also draw inspiration from Degrave [2014] and Abramowitz and Mattei [2019] in allowing a delegation to be spread to multiple voters. However, we keep the transitivity of delegations and stick to the principle of one person, one vote in not splitting the voting power of any individual. We also borrow from Christoff and Grossi [2017] the requirement that voters must specify a default value (i.e., a backup vote) on each issue. Generalisations of liquid democracy have been studied by Christoff and Grossi [2017] on multiple logically connected issues, and by Brill and Talmon [2018], who consider delegations on pairwise preferences on alternatives. We assume here votes on multiple independent issues, and we also do not consider aspects of strategic voting or analysis of voters power, as done by Escofﬁer et al. [2019] and G olz et al. [2018]. In allowing voters to express complex delegations combining the votes of other agents, we follow the vast literature on social inﬂuence and opinion diffusion on networks [see, e.g., Easley and Kleinberg, 2010] and, most notably, research studying the use of aggregation functions such as majority in binary opinion diffusion [Grandi et al., 2015; Bredereck and Elkind, 2017; Auletta et al., 2018].

2 Formal Framework We deﬁne here the components of our model for smart voting.

2.1 Smart Ballots In smart voting we have a set N of n agents (or voters) who decide on a set I of m issues. The alternative values, or simply alternatives, for each issue i I range over a non-empty ﬁnite domain D(i), which can also include abstention. An agent a expresses her opinion over an issue i I by submitting a (valid) smart ballot Bai deﬁned as follows: Deﬁnition 1 (Smart Ballot). A smart ballot of agent a for an issue i I is an ordering ((S1, F 1) > > (Sk, F k) > x) where k 0 and for 1 h k we have that Sh N is a set of agents, F h : D(i)Sh D(i) is a resolute aggregation function and x D(i) is an alternative.

2We note in passing that ranked delegations for collective decisions were also experimented by Google [Hardt and Lopes, 2015].

Thus, a smart ballot can be seen as a preference ordering over the agent s desired delegations, ending with a direct backup vote for an alternative in the issue s domain.

Deﬁnition 2 (Valid Smart Ballot). A valid smart ballot of agent a for an issue i I is a smart ballot such that, for all 1 s = t k, (i) if Ss St = then F s is not equivalent to F t, and (ii) a / Ss.

The two validity requirements ensure that agents are not manipulating the election by submitting many equivalent versions of the same delegation function, and that they are not generating delegation loops by including themselves in the set of delegates. The following example shows the expressiveness of smart ballots:

Example 1. Alice, Bob, Carl, and Diana, wonder whether to try a new restaurant (1) or stay in (0). Alice knows that her friends are real foodies, and she is too tired to check online reviews. She would like to state this complex delegation: I vote to go if and only if Bob, and at least one of Carl or Diana, think it s worth it.3 If that creates a delegation cycle, I will copy Bob s vote. If that also creates a cycle, I will vote to go . She submits the following smart ballot:

(({B, C, D}, B (C D)) > ({B}, B) > 1).

The next ballot represents Alice wanting to delegate to Bob, then Carl, then Diana, and as a last resort voting to go:

(({B}, B) > ({C}, C) > ({D}, D) > 1).

This last ballot expresses Alice wanting to vote with the majority opinion of her friends, and otherwise voting to go:

(({B, C, D}, Maj) > 1).

Let Bh ai denote the hth preference level given by agent a on issue i in her smart ballot Bai thus, Bh ai = (Sh ai, F h ai) or Bh ai = x with x D(i). For instance, in Example 1 we have in the second case that B2 Ai = (S2 Ai, F 2 Ai) = ({C}, C). Given n smart ballots for an issue i I from each agent in N, a (smart) proﬁle for this issue i, is a vector Bi = (B1i, . . . , Bni). A valid (smart) proﬁle is a smart proﬁle where each smart ballot is valid (as per Deﬁnition 2).

2.2 Unravelling Procedures In this section we propose four procedures that transform a valid smart proﬁle into a proﬁle of direct votes, i.e., votes supporting a single alternative in the issue s domain, D(i).

Deﬁnition 3 (Unravelling Procedure). An unravelling procedure U for issue i I and agents in N is any function

U : (B1i Bni) D(i)n.

Due to possible delegation cycles, it may be unclear how to assign direct votes to agents. We follow two principles in our deﬁnitions: use the highest preference level of voters when breaking delegation cycles (cf. Deﬁnition 4), and keep the unravelling process polynomial (cf. Section 3). Algorithm 1 outlines our general unravelling procedure UNRAVEL. The input of UNRAVEL is a smart proﬁle Bi. A vector X is initialised with placeholders at each position xa for a N

3This can be expressed by propositional formula B (C D).

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Algorithm 1 General unravelling procedure UNRAVEL

1: X := ( , . . . , ) empty vector for direct votes 2: while X / D(i)n do 3: lev := 1 reset preference level counter to 1 4: Y := X a copy of X to compute changes 5: while X = Y do 6: procedure UPDATE({U, RU, DU, DRU}) 7: lev := lev + 1 8: return X output vector of direct votes

and it is returned when a vote in D(i) is found for all agents. Counter lev is set at the ﬁrst preference level of the agents and an additional vector Y is added to help computation. In line 6 a subroutine with one update procedure is executed.4 We give four update procedures, deﬁned by the presence or absence of two properties. Namely, direct vote priority (D), prioritising direct votes over those that can be computed from the current vector Y of votes; and random voter selection (R), randomly choosing an agent whose vote is added (or computed) next. The four procedures are thus: basic update (U), update with direct vote priority (DU), update with random voter selection (RU), update with direct vote priority and random voter selection (DRU). Unless otherwise speciﬁed, if the condition in an if statement fails, the program skips to the next step. Moreover, Y S denotes the restriction of vector Y to the elements in set S.

Algorithm 2 UPDATE(U)

1: for a N such that xa = do 2: if Blev ai D(i) then a has a direct vote at lev 3: xa := Blev ai 4: else if F lev ai (Y Slev ai ) D(i) then

5: xa := F lev ai (Y Slev ai ) add a s computable vote

UPDATE(U) checks for each agent without a direct vote at lev (line 1): if their preference at lev is either a direct vote (line 3) or can be computed from the current values in Y (line 5), then vector X is updated with the new direct votes.

Algorithm 3 UPDATE(DU)

1: for a N such that xa = do 2: if Blev ai D(i) then add direct votes 3: xa := Blev ai 4: if Y = X then if no direct vote added to X 5: for a N such that xa = do 6: if F lev ai (Y Slev ai ) D(i) then ﬁnd computables

7: xa := F lev ai (Y Slev ai )

UPDATE(DU) ﬁrst tries to add directs votes to X (line 2); if there are none (line 4) it tries with votes computable at lev. At line 1 of UPDATE(RU) an empty set P is initialised to hold agents with either a direct vote or a computable vote at

4In what follows, we simply write UNRAVEL(#) to indicate the UNRAVEL algorithm using UPDATE procedure #.

Algorithm 4 UPDATE(RU)

1: P := initialise an empty set 2: for a N such that xa = do 3: if Blev ai D(i) or F lev ai (Y Slev ai ) D(i) then 4: P := P {a} 5: if P = then there are direct/computable votes 6: select b from P uniformly at random 7: if Blev bi D(i) then 8: xb := Blev bi 9: else if F lev bi (Y Slev bi ) D(i) then

10: xb := F lev bi (Y Slev bi )

lev (line 3); if P is non-empty, one agent will be randomly chosen and her direct/computable vote is added to X.

Algorithm 5 UPDATE(DRU)

1: P, P := initialise an empty set 2: for a N such that xa = do 3: if Blev ai D(i) then add agents with direct vote to P 4: P := P {a} 5: else if F lev ai (Y Slev ai ) D(i) then 6: P := P {a}

7: if P = then there are agents with direct votes 8: select b from P uniformly at random 9: xb := Blev bi 10: else if P = then there are computable votes 11: select b from P uniformly at random 12: xb := F lev bi (Y Slev bi )

UPDATE(DRU) ﬁrst selects agents with a direct vote at level lev (line 3) and chooses one randomly to update X (line 9). If not, UPDATE(DRU) will repeat this process, but it will now look for computable votes at level lev. The following example shows how UPDATE(U) works: Example 2. Consider a binary issue i with D(i) = {0, 1} and agents N = {A, . . . , E}. Their valid ballots in Bi, stating their preferences for delegations or direct votes, are shown schematically in the table below and in Figure 2.

1st 2nd 3rd

A ({B, C}, B C) ({D}, D) 1 B 1 - - C ({D}, D) 0 - D ({E}, E) 1 - E ({A}, A) ({B}, B) 0

We spell out here the unravelling UNRAVEL(U) on Bi:

Starting at lev = 1, the direct vote of B is stored in X = ( , 1, , , ). As there are no direct or computable votes at lev = 1 (using Y ), the level counter is increased to lev = 2. The procedure adds the direct votes of C and D, and computes the vote of E from the current Y by copying the vote of B, obtaining X = ( , 1, 0, 1, 1).

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

B C C 0 B 1

Figure 2: A network representation of Bi from Example 2. Solid lines represent ﬁrst preferences and dashed lines second preferences. The ﬁnal preference for a direct vote is next to the agent s name.

The preference level is set back to lev = 1.

A s vote can be computed from her ﬁrst preference level, and vector X = (0, 1, 0, 1, 1) is thus returned.

An important clariﬁcation is that in all our procedures, when checking if an agent s vote can be computed from a partial proﬁle of other agents votes, we test the existence of a necessary winner [Konczak and Lang, 2005]. Formally, F lev ai (X Slev ai ) has a necessary winner y D(i) if for all a Slev ai such that xa = , for all z D(i) such that xa = z we have that F lev ai (X Slev ai ) = y.5

We conclude with two further deﬁnitions. The notion of vote certiﬁcate can explain to an agent which part of their ballot was used to compute the unravelled proﬁle, without revealing the full proﬁle:

Deﬁnition 4 (Certiﬁcates). An agent a s certiﬁcate of an unravelled proﬁle U(Bi) is Cert U(Bi, a) = (k, X Sk ai), where k is a preference level and X Sk ai is the partial proﬁle of direct votes used by U to compute a s vote.

We can then deﬁne the set of voters inﬂuenced by a voter a:

Deﬁnition 5 (Inﬂuence). The set of voters inﬂuenced by voter a in proﬁle Bi using unravelling procedure U is IU(Bi, a) = {b | a Sk bi for Cert U(Bi, b) = (k, X Sk bi)}.

Let IU (Bi, a)=IU(Bi, a) {c|c IU(Bi, b) b IU(Bi, a)} . . . be the voters b indirectly inﬂuenced by a. In Example 2, we have that Cert U(Bi, C) = (2, ) and IU(Bi, C) = {A}.

2.3 Restricting the Language of Smart Ballots In this section, we deﬁne useful restrictions to the language of smart ballots. Firstly, we focus on binary Boolean functions compactly expressed as contingent (i.e., neither a contradiction, nor a tautology) propositional formulas in DNF:

Deﬁnition 6 (BOOL Ballots). A smart ballot Bai for agent a and binary issue i belongs to language BOOL if every F h ai in Bai is a contingent propositional formula in DNF.

Therefore, BOOL ballots can only contain Boolean functions as, for instance, all the delegating ballots in Example 2. Atomic boolean functions are equivalent to the identity function, i.e., copying another agent s vote. The requirement for a contingent formula is to prevent agents from overriding the delegation structure by giving a direct vote for 1

5In Example 2, in case x B = 0 then necessarily B C will be false, and thus x A = 0 (even if x C = ).

or 0 in disguise at multiple preference levels. When using language BOOL, we will write ϕlev ai instead of F lev ai . Next, we deﬁne a restriction for smart ballots where all of the (possibly many) delegations must be to single agents:

Deﬁnition 7 (LIQUID Ballots). Smart ballot Bai for agent a and issue i belongs to LIQUID if every delegating Bh ai in Bai is of the form ({b}, id) for b N \ {a} and id the identity function, and if h > 1 the ﬁnal vote of a is abstention ( ).

Finally, for a given language L we write Lk to indicate smart ballots in L having at most k delegations in their ordering. For instance, in Example 2 the smart ballots of all agents belong to the language BOOL2.

2.4 Voting Rules The ﬁnal step of smart voting aggregates the vector of direct votes into an outcome. For the remainder of the paper, we will use the following rules (for a domain with abstentions ): the majority rule (Maj) returns the alternative in the domain having more than n/2 votes, and otherwise; the relative majority rule (RMaj) returns the plurality outcome among D(i) \ { }, and if there is a tie it returns .

3 Algorithmic Analysis

We here analyse the unravelling procedures introduced in Section 2.2. For simplicity, in the rest of the paper we assume that I contains a single issue (thus, we drop the subscript i).

3.1 Properties of Unravelling Given the four update procedures, our ﬁrst result shows that for any valid smart proﬁle the general unravelling procedure UNRAVEL always terminates:

Proposition 1. Algorithms UNRAVEL(U), UNRAVEL(DU), UNRAVEL(RU) and UNRAVEL(DRU) always terminate on a valid smart proﬁle B.

Proof (sketch). The proof (omitted in the interest of space) rests on the fact that the two while loops in UNRAVEL cannot be in an inﬁnite cycle due to each Ba having a ﬁnite number of preference levels,6 the ﬁnal preference being a direct vote, and each procedure updating at least one agent s direct vote in X at each iteration (and removing none).

In the next proposition we prove that the four update procedures actually give different results.

Proposition 2. There exists a valid smart proﬁle B for which UNRAVEL(U), UNRAVEL(DU), UNRAVEL(RU), and UNRAVEL(DRU) give different outputs.

Proof. Consider the smart proﬁle of Example 2: the outcomes of the four unravelling procedures are shown in Table 1. It is clear that procedures U and DU lead to different outcomes than the others. Although procedures RU and DRU give the same proﬁles of direct votes, these outcomes occur at different rates.

6Recall that since D(i) and the possible sets of delegates are ﬁnite, and since all functions given in an agent s valid ballot must differ, the possible number of functions must also be ﬁnite.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

UNRAVEL Output X D(i)n Random voter U (0, 1, 0, 1, 1) - DU (0, 1, 0, 1, 0) - RU (0, 1, 0, 0, 0) C (1, 1, 1, 1, 1) D (1, 1, 1, 1, 1) E DRU (0, 1, 0, 0, 0) C (1, 1, 1, 1, 1) D

Table 1: The last column indicates, for procedures RU and DRU, which voters have been picked (only one random choice here).

Observe that the proof above implies that the collective decision can be different depending on the unravelling used, and on the randomly chosen voter. The majority outcome would be 1 in two thirds of the cases with procedure RU, whereas only in half of the cases when using procedure DRU.

3.2 Computational Complexity The ﬁrst problem we study is how hard it is to verify that a smart ballot is valid with respect to language L. The VALIDB(L) problem takes as input a smart ballot Ba in L and agents N, and it asks if Ba is valid for L.

Theorem 1. VALIDB(BOOLk) is NP-complete, for k 1.

Proof. For membership, observe that for Ba to be a valid BOOLk ballot, it needs to verify the following properties (for 1 h, ℓ k), that can either be checked in polynomial time by reading Ba, or require a (polynomial) certiﬁcate. The properties are: there are k top preferences of the form (Sh a, ϕh a); there is one direct vote in {0, 1} as ﬁnal preference; each ϕh a is in DNF; each Sh a is such that a / Sh a; and each ϕh a is such that V ar(ϕh a) Sh a N. For the ﬁnal three properties, we have to guess certiﬁcates: at most k to check that each ϕh a is not a tautology ( ϕh a is satisﬁable); at most k to check that each ϕh a is not a contradiction (ϕh a is satisﬁable); at most k

2(k 1) to check that for all ϕh a and ϕℓ a such that h = ℓ, ϕh a and ϕℓ a are not logically equivalent (i.e., (ϕh a ϕℓ a) is satisﬁable). All this requires at most k

2(k + 3) certiﬁcates for constant k. Thus, VALIDB(BOOLk) is in NP. For hardness, we reduce from the NP-complete problem DNF-FALSIFIABLE,7 whose input is a formula ϕ in DNF. We create an instance of VALIDB(BOOLk) where N = V ar(ϕ) {a, b}, for fresh variables a and b, D(i) = {0, 1} and Ba = ((N\{a}, ϕ b) > 1). We now show that DNFFALSIFIABLE has a positive answer if and only if the answer to VALIDB(BOOLk) on our instance is also positive. Assume that ϕ is falsiﬁable. By construction of Ba, we only need to check that ϕ b is neither a contradiction nor a tautology: this follows from ϕ being falsiﬁable and b being a fresh variable. Assume that ϕ is not falsiﬁable, i.e., ϕ is a tautology. Thus, agent a provides a function ϕ b which is a tautology, and hence Ba is not valid. Therefore, VALIDB(BOOLk) is NP-complete.

7Since SAT-CNF is NP-hard, by the duality principle DNFFALSIFIABLE is also NP-hard; for membership in NP it sufﬁces to verify a falsifying truth assignment in polynomial time.

Although checking if a BOOLk smart ballot is valid is not a tractable problem, it is as hard as the SAT problem for propositional formulas, for which efﬁcient solvers exist. Next, we show that our unravelling procedures terminate in polynomial time given BOOL ballots. We refer to this problem as UNRAVEL(#)L for # {U, DU, RU, DRU}. Observe that the size of the input for UNRAVEL(#)BOOL is in O(maxp(B) n maxϕ(B)), where maxp(B) is the highest preference level of any ballot in B and maxϕ(B) is the maximum length of any formula from an agent in B. Proposition 3. UNRAVEL(#)BOOL terminates in at most O(n2 maxp(B) 2 maxϕ(B)) time steps, for # {U, DU, RU, DRU}.

Proof. The while loop from line 2 in UNRAVEL can be repeated at most n times (in case just one direct vote is added to X at each iteration). Moreover, the while loop from line 5 can be repeated at most maxp(B) times, in case all smart ballots are of the same length and no vote is computable in the ﬁrst maxp(B) 1 positions for any agent. The following is executed at most n maxp(B) times: UPDATE(#) checks that for each agent a such that xa = (at most n) either Blev a D(i) or ϕlev a has a necessary winner (depending on the # used). As each ϕlev a is in DNF, i.e., a disjunction of conjunctions of literals (called cubes), to verify if it has a necessary winner we check if either: 1. all literals of a cube of ϕlev a are made true by X Slev a , 2. one literal in each cube is made false by X Slev a , returning a direct vote of 1 or 0, respectively. The use of UPDATE(#) takes at most O(n 2 maxϕ(B)) steps. Hence, in O(n2 maxp(B) 2 maxϕ(B)) time steps a proﬁle X of direct votes is output by UNRAVEL(#)BOOL.

4 Ranked Singleton Delegations

In this section we focus on the language LIQUIDk from Definition 7. Agents are restricted to express either a direct vote or a (partial) ranking of single-agent delegations.

4.1 Liquid Democracy We begin by showing that our unravelling procedures yield the same result on the language LIQUID1, corresponding to the simplest setting of liquid democracy: Proposition 4. If B LIQUID1 then UNRAVEL(#) outputs the same result for # {U, DU, RU, DRU}.

Proof (sketch). At the ﬁrst iteration step, all direct votes are added to the vector X. Each unravelling procedure then computes the votes of those agents who are delegating but are not in a delegation cycle (possibly not in the same order, but with the same result). Cycles are broken by looking at backup votes of possibly different agents, which are all abstentions by the deﬁnition of LIQUID1.

Now, consider an example of liquid democracy. By creating a proﬁle of smart ballots with Ba = (({b}, id) > ) if agent a was delegating her decision to agent b N\{a} and Ba = (x) with x = if agent a was voting directly, we obtain the following result:

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Proposition 5. Liquid Democracy can be translated into a smart voting election with LIQUID1 ballots and UNRAVEL(#) for # {U, DU, RU, DRU}. The proof of Proposition 5 is omitted for lack of space.

4.2 Participation Axioms In this section we study two properties of unravelling procedures, focussing on a binary domain (with abstentions). The ﬁrst, proposed by Kotsialou and Riley [2020], was inspired by the classical participation axiom from social choice [Moulin, 1988]. Both properties focus on a voter s incentive to participate in the election, either by voting directly or by delegating. Thus, we assume that an agent a expressing a direct vote for alternative x {0, 1} prefers x over 1 x, denoted by x >a 1 x, and that a prefers x over abstention, x >a . Deﬁnition 8 (Cast-Participation). A voting rule r and unravelling procedure U satisfy cast-participation if for all valid smart proﬁles B and agents a N such that Ba D(i)\{ }

r(U(B)) a r(U(B a, B a))

for all B a = Ba, and B a is equal to B without a s ballot. Cast-participation implies that agents who vote directly have an incentive to do so, rather than to express any other ballot (recall our restriction to ranked singleton delegations). A voting rule r on the domain {0, 1, }N satisﬁes monotonicity if for any proﬁle X, if r(X) = x with x {0, 1} then r(X+x) = x, where proﬁle X+x is obtained from X by having one voter switch from an initial vote of 1 x to x or , or from an initial vote of to x. Observe that all rules introduced in Section 2.4 satisfy this property. Due to this deﬁnition we can now show the following: Theorem 2. Any monotonic rule r with unravelling procedure UNRAVEL(#) for # {U, DU, RU, DRU} satisﬁes cast-participation for LIQUID.

Proof (sketch). Without loss of generality, assume that for agent a N we have Ba = (1); thus for a it is the case that 1>a0. To falsify cast-participation, we need to construct a proﬁle B such that r(UNRAVEL(#)(B))=0 or , and a smart ballot B a such that r(UNRAVEL(#)(B a, B a))=1. If a now delegates to an agent with a direct vote for 1, the outcome does not change. Therefore, all voters c I# (a, B) vote for 1 in B, but vote for either 0 or in B (i.e., the ﬁnal votes of B can be obtained from those of B by switching 1s to 0s or s). Moreover, all c I# (a, B) do not change their vote from B to B . Thus, this contradicts the monotonicity assumption of voting rule r.

The theorem above does not hold for non-singleton delegations we omit the proof in the interest of space. We now focus on the incentive that a voter has to receive and accept delegations. Recall that I# (B, a) is the set of agents who are directly or indirectly inﬂuenced by a s vote. Deﬁnition 9 (Guru-participation). A voting rule r and unravelling procedure U satisfy the guru-participation property if and only if for all proﬁles B and all agents a N such that Ba = (x) with x D(i) \ { } we have that

r(U(B)) a r(U(B b, ( )))

for any b I# (B, a), and B b is B without b s ballot. We now show that all four unravelling procedures we propose do not satisfy this property for a speciﬁc rule r: Theorem 3. RMaj and UNRAVEL(#) do not satisfy guruparticipation for # {U, DU, RU, DRU} for LIQUID.

Proof. Consider a smart proﬁle B with Ba = (1), Bb = (({c}, id)>({a}, id)> ), Bc = (({d}, id)>({f}, id)> ), Bd = (({b}, id) > ({f}, id) > ), Be = (1) and Bf = (0) and proﬁle B = (B b, ( )) obtained from B by switching b s vote to B b = ( ). The outcomes of the four procedures are shown here:

U/ DU X1 = (1, 1, 0, 0, 1, 0)

X2 = (1, , , , 1, 0) RU/ X3 = (1, 1, 1, 1, 1, 0) DRU X4 = (1, 0, 0, 0, 1, 0) X5 = (1, 0, 0, 0, 1, 0)

By applying unravelling procedures U and DU, agent a prefers the outcome from B to B, since RMaj(X1) = and RMaj(X2) = 1. For procedures RU and DRU, the outcome on B is RMaj(X2) = 1. However, their outcome on B can be either RMaj(X4) = RMaj(X5) = 0 or RMaj(X3) = 1. Agent a strictly prefers the outcome from B , which is certainly 1, over proﬁle B which leads to an outcome of 0 for two thirds of the cases.

Observe that the proﬁle in the above proof shows that our unravelling procedures differ from those of Kotsialou and Riley [2020], as their depth-ﬁrst procedure on B would output (1, 0, 1, 0, 1, 0), while their breadth-ﬁrst procedure on B

would give (1, , 0, 0, 1, 0). The breadth-ﬁrst procedure does satisfy guru-participation, but at the price of using delegations that are quite low in the voters rankings.

5 Conclusion In this paper we propose and study an extension of liquid democracy that accounts for ranked and multi-voter delegations. We introduce four unravelling procedures to transform voters ballots into proﬁles of direct votes, on which a collective decision is taken using a standard voting rule. Our procedures are polynomial, and aim at making use of the highestranked delegations when breaking delegation cycles. With our proposal we want to put forward a general framework to study delegative voting, with notable examples being the classical settings of liquid democracy. Future work will include the investigation of further axiomatic properties for unravelling procedures and delegative voting, in line with the participation axioms, and a more ﬁne-grained analysis of restricted languages for smart ballots.

Acknowledgments The authors acknowledge the support of the ANR JCJC project SCONE (ANR 18-CE23-0009-01). This paper developed from ideas discussed at the Dagstuhl Seminar 19381 (Application-Oriented Computational Social Choice), 2019.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

References [Abramowitz and Mattei, 2019] Ben Abramowitz and Nicholas Mattei. Flexible representative democracy: An introduction with binary issues. In Proc. of the 28th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 2019. [Auletta et al., 2018] Vincenzo Auletta, Diodato Ferraioli, and Gianluigi Greco. Reasoning about consensus when opinions diffuse through majority dynamics. In Proc. of the 27th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 2018. [Behrens et al., 2014] J. Behrens, A. Kistner, A. Nitsche, and B. Swierczek. Principles of Liquid Feedback. Interacktive Demokratie, 2014. [Bloembergen et al., 2019] Daan Bloembergen, Davide Grossi, and Martin Lackner. On rational delegations in liquid democracy. In Proc. of the 33rd AAAI Conference on Artiﬁcial Intelligence (AAAI), 2019. [Bredereck and Elkind, 2017] Robert Bredereck and Edith Elkind. Manipulating opinion diffusion in social networks. In Proc. of the 26th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 2017. [Brill and Talmon, 2018] Markus Brill and Nimrod Talmon. Pairwise liquid democracy. In Proc. of the 27th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 2018. [Brill, 2018] Markus Brill. Interactive democracy. In Proc. of the 17th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 2018. [Caragiannis and Micha, 2019] Ioannis Caragiannis and Evi Micha. A contribution to the critique of liquid democracy. In Proc. of the 28th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 2019. [Christoff and Grossi, 2017] Zo e Christoff and Davide Grossi. Binary voting with delegable proxy: An analysis of liquid democracy. In Proc. of the 16th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 2017. [Cohensius et al., 2017] Gal Cohensius, Shie Mannor, Reshef Meir, Eli A. Meirom, and Ariel Orda. Proxy voting for better outcomes. In Proc. of the 16th Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 2017. [Degrave, 2014] Jonas Degrave. Resolving multi-proxy transitive vote delegation. ar Xiv preprint ar Xiv:1412.4039, 2014. [Dhillon et al., 2019] Amrita Dhillon, Grammateia Kotsialou, Peter Mc Burney, Luke Riley, et al. Introduction to voting and the blockchain: some open questions for economists. Technical report, Competitive Advantage in the Global Economy (CAGE), 2019. [Easley and Kleinberg, 2010] David Easley and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.

[Escofﬁer et al., 2019] Bruno Escofﬁer, Hugo Gilbert, and Ad ele Pass-Lanneau. The convergence of iterative delegations in liquid democracy in a social network. In Proc. of the 12th International Symposium on Algorithmic Game Theory (SAGT), 2019. [Escofﬁer et al., 2020] Bruno Escofﬁer, Hugo Gilbert, and Ad ele Pass-Lanneau. Iterative delegations in liquid democracy with restricted preferences. In Proc. of the 34th AAAI Conference on Artiﬁcial Intelligence (AAAI), 2020. [G olz et al., 2018] Paul G olz, Anson Kahng, Simon Mackenzie, and Ariel D Procaccia. The ﬂuid mechanics of liquid democracy. In International Conference on Web and Internet Economics (ICWIE), 2018. [Grandi et al., 2015] Umberto Grandi, Emiliano Lorini, and Laurent Perrussel. Propositional opinion diffusion. In Proc. of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2015. [Green-Armytage, 2015] James Green-Armytage. Direct voting and proxy voting. Constitutional Political Economy, 26(2):190 220, 2015. [Hardt and Lopes, 2015] Steve Hardt and Lia C. R. Lopes. Google votes: A liquid democracy experiment on a corporate social network. Technical report, Technical Disclosure Commons, Google, 2015. [Kahng et al., 2018] Anson Kahng, Simon Mackenzie, and Ariel D Procaccia. Liquid democracy: An algorithmic perspective. In Proc. of the 32nd AAAI Conference on Artiﬁcial Intelligence (AAAI), 2018. [Konczak and Lang, 2005] Kathrin Konczak and J erˆome Lang. Voting procedures with incomplete preferences. In Proc. of the IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling, volume 20, 2005. [Kotsialou and Riley, 2020] Grammateia Kotsialou and Luke Riley. Incentivising participation in liquid democracy with breadth-ﬁrst delegation. In Proc. of the 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2020. [Kotsialou et al., 2018] Grammateia Kotsialou, Luke Riley, Amrita Dhillon, Toktam Mahmoodi, Peter Mc Burney, Paul Massey, and Richard Pearce. Using distributed ledger technology for shareholder rights management. In Proc. of the 17th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 2018. [Miller, 1969] James C Miller. A program for direct and proxy voting in the legislative process. Public choice, 7(1):107 113, 1969. [Moulin, 1988] Hervi Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, 1988. [Riley et al., 2019] Luke Riley, Grammateia Kotsialou, Amrita Dhillon, Toktam Mahmoodi, Peter Mc Burney, and Richard Pearce. Deploying a shareholder rights management system onto a distributed ledger. In Proc. of the 18th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 2019.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)