# preserving_consistency_in_multiissue_liquid_democracy__16af61b3.pdf

Preserving Consistency in Multi-Issue Liquid Democracy

Rachael Colley , Umberto Grandi IRIT, University of Toulouse, France {rachael.colley, umberto.grandi}@irit.fr

Liquid democracy bridges the gap between direct and representative democracy by allowing agents to vote directly on an issue or delegate to a trusted voter. Yet, when applied to votes on multiple interconnected issues, liquid democracy can lead agents to submit inconsistent votes. Two approaches are possible to maintain consistency: either modify the voters ballots by ignoring problematic delegations, or resolve all delegations and make changes to the final votes of the agents. We show that rules based on minimising such changes are NP-complete. We propose instead to elicit and apply the agents priorities over the delegated issues, designing and analysing two algorithms that find consistent votes from the agents delegations in polynomial time.

1 Introduction Delegative voting, most notably the setting called liquid democracy in which delegations are transitive, is currently under scrutiny by researchers in artificial intelligence. On the one hand, as a collective intelligence application in which its ability to track truth messages from noisy signals is evaluated [Caragiannis and Micha, 2019; Becker et al., 2021; Dhillon et al., 2021; Halpern et al., 2021; Kahng et al., 2021; Zhang and Grossi, 2022], and on the other hand, as an algorithmically rich application of interactive democracy [Boldi et al., 2011; Kotsialou and Riley, 2020; Brill et al., 2022; Markakis and Papasotiropoulos, 2021]. Liquid democracy is mostly studied in its simplest form: a binary decision has to be taken by a group of voters, who are allowed to express a direct vote (eventually including abstentions) or delegate their vote to another voter. However, its main potential lies in the fact that virtually any collective decision mechanism can be liquidised to borrow a term from Brill and Talmon [2018], i.e., to include transitive delegations: for example, the liquid version of knapsack voting (related to participatory budgeting) allows a voter to delegate their assessment of different projects to different voters [Jain et al., 2021]. Another example is pairwise liquid democracy [Brill and Talmon, 2018], in which a voter can delegate relative comparisons over two competing alternatives to (possibly different) voters in preference aggregation.

However, applying delegative voting to more complex multi-issue collective decisions runs into the problem of maintaining voters consistency (e.g., in the two settings previously mentioned, the projects approved by the agent should not exceed a given budget, and the agent s preferences should be transitive) while at the same time utilising voters delegations in the input as much as possible. Optimisation-based approaches proposed in previous work all run into high computational costs, and approximation algorithms may be hard to defend in a social choice setting where fairness criteria and explanatory power of the outcome are of primary importance.

Our Contribution. We propose to elicit a voter s priorities over the issues on which they are delegating and feed them to tractable rules that maintain ballot consistency. Such an elicitation can easily be performed by, for example, using the order in which voters enter their delegations in the voting platform. We first consider two rules that minimise either the number of ignored delegations in the voters ballots, as proposed in previous work by Brill and Talmon [2018] and Jain et al. [2021], or minimise the number of changes to the agents final votes once all delegations have been resolved. After showing that both rules are NP-complete, we propose two polynomial algorithms inspired by the two minimisation rules, that apply the agents priorities to output consistent final votes. Our results show that although these principled algorithms cannot be considered as approximations of the minimisation rules, one of our algorithms respects the agents priorities over their delegations more than its minimisation counterpart. Furthermore, when focusing on settings with budget constraints, we show that one of our minimisation rules outperforms the other rules when considering their global effects on the acceptance rates of projects.

Related Work. The seminal work of Christoff and Grossi [2017] already considered a liquidised version of binary aggregation on interdependent issues. This paper builds on this, generalising and unifying the approach of Jain et al. [2021] and Brill and Talmon [2018], where the former pertains to approved projects respecting a budget and the latter to accepted pairwise comparisons being transitive. More precisely, we study liquid democracy over multiple binary issues where the final opinions are bounded to satisfy a constraint. Another model considering a liquid version of preference aggregation is that of Harding [2021],

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

however, this work guides agents in choosing a proxy that is consistent with their views. The algorithmic literature on liquid democracy has mostly focused on eliciting rankings over potential delegates to solve the problem of delegation cycles [Kotsialou and Riley, 2020; Brill et al., 2022; Dey et al., 2021] or to study game-theoretical solution concepts where liquid democracy is interpreted as a voting game [Escoffier et al., 2019; Armstrong and Larson, 2021; Zhang and Grossi, 2021]. As already observed by Christoff and Grossi [2017] liquid democracy relates strongly to opinion diffusion, where a delegation can be interpreted as an influence link. Constraints in opinion diffusion have been considered by Friedkin et al. [2016] for real-valued beliefs and by Botan et al. [2019] for majoritarian updates on binary issues.

Paper Structure. The remainder of the paper is organised as follows. Section 2 presents the basic definitions of the model. Section 3 presents two rules that minimise the number of delegations that have to be deleted to find consistent votes, showing that they are intractable. In Section 4 we introduce the notion of priorities over the issues as well as two rules combining delegation deletion and the agents priorities, showing that they terminate with consistent votes in polynomial time (Section 4.1). In Section 4.2 we show that the tractable rules are not efficient approximations of their minimisation counterparts. In Section 4.3 we compare the four rules on how well they respect the priorities. Section 5 focuses on knapsack constraints and in Section 6 we conclude.

2 The Model

We model a group of agents N = {1, , n} making a collective decision on a set of issues I = {1, , m}, where the domain of each issue j I is D(j). Without loss of generality we will consider binary issues, thus D(j) = {0, 1} for all j I.1 Each agent i N submits a ballot Bi Πj I(D(j) N\{i}), which specifies for each issue j I if the agent gives a direct vote in D(j) or a delegation to any other agent in N\{i}. A profile of ballots, one for each agent in N, is denoted by B, and the vote of agent i on issue j in profile B is denoted as Bij. We let ˆB be an n m matrix containing only the direct votes of the agents in profile B, where ˆBij = Bij if Bij {0, 1} and ˆBij = , otherwise. We let X {0, 1}n m denote a profile of votes.

Example 1. Consider two agents N = {C, D}, two issues I = {j, k}, and a profile B composed of ballots BC = (1, D) and BD = (C, 1), where C delegates to D on issue k, and D delegates to C on issue j. The direct votes of the agents are ˆB = ((1, ), ( , 1)).

We assume that there are no delegation cycles on any given issue. To clarify this, we associate a labelled delegation graph GB=(V, E) with each profile B, where V =N and edge (C, D, j) E if C delegates to D on issue j in B (where j is the label of the edge). We assume that GB is acyclic for any issue, i.e., for each (C, D, j) E there is no j-path from

1Non-binary issues can be expressed in the binary setting by letting each alternative become a binary issue where the constraint permits only one alternative to be chosen.

C returning to C. This allows us to focus on preserving consistency without making assumptions on how delegation cycles are broken, in a similar vein as the previous work [Brill and Talmon, 2018; Jain et al., 2021]. Thanks to the assumption of acyclicity, we can define a canonical profile of votes XB {0, 1}n m for every B, where all delegating voters are assigned the vote of the direct voter at the end of the delegation chain (sometimes known as a guru or an ultimate delegate). Given a delegation graph GB, for each i N and j I, we find the endpoint k N of the longest outgoing j-path from i and let XB ij = ˆBkj. We assume that the issues in I are interconnected, i.e., that the votes of the agents have to respect a given constraint or set of constraints Γ. For instance, in knapsack voting agents have to respect a given budget in the set of approved projects, or in preference aggregation the approved comparisons are assumed to be transitive. If Xi {0, 1}m, we denote with Xi |= Γ the fact that agent i s vote satisfies the constraint Γ. If X is a profile of votes, we write X |= Γ when Xi |= Γ for all i N. The set of all consistent votes is denoted by XΓ = {X | X |= Γ}, assuming that Γ is not a contradiction, i.e. XΓ = . We allow for any representation of Γ, with the only restriction being that checking if a partial vote can be completed to a consistent one should be feasible in polynomial time. For instance, budget constraints, logical formulas in complete-DNF, and the transitivity of preferences would all be acceptable constraints. Constraints expressed as arbitrary logical formulas do not, as the problem of completing partial evaluations is equivalent to SAT. Formally, if X {0, 1, }m is a partial vote, we write X p Γ if there exists a complete vote X {0, 1}m such that X X and X |= Γ.2 We assume that every agent s (partial) direct votes can be completed, i.e., for all i N we assume ˆBi p Γ. In line with previous work, we say that a profile of ballots B is consistent if XB |= Γ.3 From our assumptions that delegations are acyclic and the membership problem of Γ is tractable, we obtain that: Remark 1. To check if a profile B is consistent is polynomial. As profiles may not be consistent, we define consistent delegation rules that take a profile of ballots B and return a profile of consistent votes, preserving the voters direct votes: Definition 1. Given a constraint Γ, a consistent delegation rule F takes a profile of ballots B and returns a profile of votes such that F(B) |= Γ and ˆB F(B). Example 2. Consider the same setting as Example 1, with the constraint that j and k cannot both be accepted. Thus, Γ can be represented as j k (a logical formula in complete DNF) and XΓ={(0, 0), (0, 1), (1, 0)}. Following the agents delegations in B, the canonical profile of votes is XB=((1, 1), (1, 1)). Thus, B is not consistent. Observe that any consistent delegation rule would give the outcome ((1, 0), (0, 1)) (where the direct votes are not changed).

2Here we slightly abuse the subset notation, for a partial assignment X {0, 1, }m and assignment X {0, 1}m, we say X X when X is found by only changing s in X to 0 or 1. 3Brill and Talmon [2018] also define a weaker notion of consistency. Both are equivalent to our definition on acyclic profiles.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

3 Minimal Changes to Ballots and Votes

In this section we introduce two consistent delegation rules that preserve vote consistency by making minimal changes, showing that associated decision problems are NP-complete. The first approach is to modify the profile of ballots B by ignoring a minimal number of delegations that conflict with the constraint, replacing them with a direct vote. This rule has been defined in previous work on multi-issue liquid democracy for the specific settings of knapsack voting [Jain et al., 2021] and preference aggregation [Brill and Talmon, 2018]. Given a profile B, the minimal delegation change rule MDC finds all consistent profiles B that replace a minimal number of delegations with direct votes and whose canonical profile of votes XB is consistent with Γ:

MDC(B)={XB |B arg max {B | ˆB XB & XB |=Γ}

i N |Bi B i|}

We now show that the following decision problem associated with MDC is NP-complete.

MINIMALDELCHANGE. Given a profile B, constraint Γ and integer k 0, is there a consistent profile B found by changing at most k delegations of B to direct votes?

Proposition 1. MINIMALDELCHANGE is NP-complete.

Proof. A sub-problem of MINIMALDELCHANGE is the consistent knapsack voting problem CKV from Jain et al. [2021] (they also consider acyclic delegation graphs, as CKV removes cycles by replacing every delegation in a cycle with a direct vote against the issue). CKV is an NP-complete problem, as shown by Jain et al. [2021] (Theorem 1), implying that MINIMALDELCHANGE is NP-hard. To see that MINIMALDELCHANGE is in NP, consider a certificate that lists agents and issues, indicating delegations to be changed to direct votes to obtain B from B. First we check that the list has at most k entries. Then we check whether B is consistent, which can be done in polynomial time by Remark 1.

The second approach, loosely inspired by related literature on judgment aggregation (see, e.g., Lang et al. [2011]), makes minimal changes to the canonical profile of votes XB directly, but only on issues where the voter expressed a delegation. The minimal vote change rule MVC is defined as follows:

MVC(B) = arg max {X| ˆB X and X|=Γ}

i N |Xi XB i |

In line with Proposition 1, we now show that the following decision problem associated with MVC is NP-complete.

MINIMALVOTECHANGE. Given a profile B, constraint Γ, and integer k 0, is there an X |= Γ such that ˆB X and X is found by changing at most k votes in XB?

Proposition 2. MINIMALVOTECHANGE is NP-complete.

Proof. For membership in NP, we take a certificate that lists pairs of agents and issues to be changed in XB to define X . We then check in polynomial time that the list has k or less entries, and that X i |= Γ for each i N.

To show NP-hardness, we reduce from the NP-complete problem independent set INDSET [Karp, 1972]. The input of INDSET is a graph G = (V, E) and integer t 0. It asks if there is a V V with |V | t such that no edge in E has both ends in V . Given an instance of INDSET, consider a set of agents N = {Av | for all v V } {A}, issues I = {Iv | v V }, and bound k = |V | t. Next, our constraint only allows for independent sets: ΓIND = {(Iu Iv) (Iv Iu) | (u, v) E}. First, observe that we can check in polynomial time if a partial assignment can be completed to one satisfying ΓIND, as we only need to check that the vertices accepted in the partial assignment are an independent set. Finally, consider a profile of ballots B such that agent A delegates to agent Av on issue Iv for all v V , and each Av only approves of Iv, rejecting all other issues. Assume there is an independent set V V with |V | t. Given that XB A =(1, , 1), consider XA containing votes for the issues Iv with v V and against the remaining issues. The resulting profile of votes is consistent: for each v V , XAv is consistent as only one issue is accepted, and XA |= ΓIND as XA reflects an independent set. Thus, we also have a solution to our problem as the number of votes changed is |V | |V | |V | t = k. Next assume that there is no independent set of size at least t, and suppose t < t is the size of the largest independent set of G. Observe that in order to make XB A consistent, at least |V | t votes need to be reverted. As |V | t > |V | t = k, there is no solution to our problem either. Hence, MINIMALVOTECHANGE is NP-hard, thus NP-complete.

4 Eliciting and Applying Priorities over Issues

In order to provide tractable and principled rules to preserve vote consistency, we propose to elicit from the voters their priorities over the issues they choose to delegate on this could be, e.g., the order in which the voter expressed their delegations. In doing so we discard a fixed parameter tractability analysis of MDC and MVC,since Jain et al. [2021] already provided extensive negative results for this approach.4

We assume that voters specify a total ordering over the issues on which they express a delegation. To simplify the presentation, we assume that these orderings are on the whole set of issues I (the two assumptions are equivalent since consistent delegation rules never change direct votes). We denote this order by i for each agent i N, and we write i (k) for the issue with the kth highest priority in i. In parallel with the minimisation rules presented in Section 3, we present two approaches based on either delegation changes or vote changes. First, the priority delegation changing rule (PDC) described in Algorithm 1 iteratively alters an agent s delegation to a direct vote if its addition is inconsistent. Second, the priority vote changing rule (PVC) described in Algorithm 2 iteratively adds consistent votes from XB following the order of priorities. We now define some notation

4Jain et al. [2021, Theorem 1] show that their version of MDC is tractable only under restrictive conditions such as when voters delegate on at most one issue. Moreover, their problem is NP-complete even when restricting many parameters to be small constants.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

Algorithm 1 Priority delegation changing (PDC)

1: Input: B, i for all i N 2: t = 0 3: Find X0 = ˆB 4: while Xt / {0, 1}n m do 5: Xt+1 := Xt

6: for i N and k [1, m] do 7: j := i (k) 8: if vote(Xt, i, j) = and vote(Xt, Bij, j) {0, 1} then 9: if (bal(Xt+1, i) j, vote(Xt, Bij, j)) p Γ then vote(Xt+1, i, j) := vote(Xt, Bij, j) 10: else vote(Xt+1,i,j):=1 vote(Xt, Bij, j)

11: X := Xt

used in the algorithms. Recall that ˆB denotes an n m matrix containing only the direct votes of B. We let bal(X, i) denote the vector of votes recorded for agent i in matrix X and vote(X, i, j) denote the vote recorded in X for agent i on issue j. Furthermore, (X j, xj) denotes the vector X with the entry for issue j appended with a new entry xj. Algorithm 1 inputs the profile B and the agents priorities over the issues i, and then sets the counter t to 0. On line 4 the algorithm starts a while-loop that continues until every agent has a vote in {0, 1} for every issue. Each iteration of the while-loop checks whether an update can be made for each agent following their priority order over the issues. In the current Xt, if i does not have a vote for j and their delegate does (on line 8), we check if adding their delegate s vote is consistent, if so we update Xt+1 i with it (line 9), otherwise we add the opposite (line 10). Note that the update to Xt+1

is simultaneous as it uses information from Xt. Hence, the order of agents in the for-loop does not affect the outcome. Algorithm 2 describes PVC, it inputs the profile B and the agents priorities. It then finds ˆB and the canonical profile of votes XB. For each agent i N it checks in the priority order i (line 4) if they have a vote recorded in X0 (line 6). If the addition of XB ij is consistent then we update X0 i with it (line 7), if not we update the opposite (line 8).

Example 3. Consider agents N = {C, D, E, F} and issues I = {j, k} where at most one issue can be accepted, i.e., Γ = j k. Consider profile B in which agents C and D vote directly, BC = (1, 0) and BD = (0, 1), whereas the remaining agents delegate as such: BE = (C, D) and BF = (E, E). Agent E has the priority j E k while F has the priority k F j. PDC first considers delegations of the highest priority issue. The top priority issue for E is j and their delegate has a vote for j in X0. As E currently has no votes in X0 we let X1 Ej = 1. Then the delegation on the second priority issue k is not consistent, thus, X1 Ek = 0. As in X0, E does not have any votes, F s votes can only be added in the second iteration. Thus, X2 F = (1, 0) and PDC(B) = ((1, 0), (0, 1), (1, 0), (1, 0)). PVC first computes the canonical profile of votes XB = ((1, 0), (0, 1), (1, 1), (1, 1)), where XB E and XB F are inconsistent. For similar reasons as when

Algorithm 2 Priority vote changing (PVC)

1: Input: B, i for all i N 2: Find X0 = ˆB 3: Find XB

4: for i N and k [1, m] do 5: j := i (k) 6: if vote(X0, i, j) = then 7: if (bal(X0, i) j, vote(X0, XB ij , j)) p Γ then

vote(X0, i, j) := vote(X0, XB ij , i)

8: else vote(X0, i, j) := 1 vote(X0, XB ij , j)

using PDC, PVC then changes E s vote to X0 E = (1, 0). However, for F, it first tries X0 F k = 1 in accordance with F s priorities, which is consistent, entailing that X0 F j = 0. Thus, PVC(B) = ((1, 0), (0, 1), (1, 0), (0, 1)).

4.1 Complexity of PDC and PVC In the absence of constraints it is easy to see that all four rules output the canonical profile of votes associated to the profile.

Remark 2. When Γ = , PDC, PVC, MDC and MVC give the same outcome, namely XB.

We next show that PDC and PVC always terminate and output a consistent profile of votes.

Proposition 3. For any acyclic profile B and constraint Γ, PDC and PVC terminate, PDC(B) |= Γ and PVC(B) |= Γ.

Proof. We start from PDC. Due to the while-loop on line 4, if Algorithm 1 terminates, it does so with X {0, 1}n m. We assume for a contradiction that Algorithm 1 does not terminate, and therefore, Xt ij = for all t > T after some iteration T N and for some i N and j I. Note that Bij / {0, 1} as the algorithm does not change any direct votes to . Therefore, Bij is a delegation, and since votes are propagated following delegations we can infer that also Xt Bijj = . By the acyclicity of B, the delegation chain on issue j starting at agent i must end at a direct voter for j, whose vote will then eventually reach voter i, against our assumption. Next, we show that every agent s votes are consistent with Γ. Recall that the initial direct votes are consistent, i.e., ˆBi p Γ for all i N. Each time a vote is added, we check if its addition allows for a consistent completion and if not, the opposite is added. As XΓ = , the process is guaranteed to give a consistent completion of votes. Next we show the same for PVC. Algorithm 2 first finds XB. It then inspects the cells of X0 with a for-loop on line 4, cycling though every agent and issue (in order of their priorities), after which it will terminate. In line 6, it inspects every entry of X0 without a vote X0 ij = and then updates it to a vote in {0, 1} from line 7 to line 8. Thus, the algorithm always returns X {0, 1}n m. We next show that the agents votes are consistent. The algorithm starts with ˆB, which by assumption is such that ˆBi p Γ for all i N. It then iteratively adds votes from XB if they can be completed

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

to a consistent set of votes, and the opposite otherwise. This will always lead to votes X0 i |= Γ. Therefore, PVC always terminates with Xn m and Xi |= Γ for all i N.

We show that both rules run in polynomial time. Recall that n is the number of voters, m the number of issues, and let ℓbe the time to check if a partial vote has a Γ-consistent completion (we assumed that ℓis polynomial in n and m).

Proposition 4. PDC terminates in O(nm(n + ℓ)) time.

Proof. In each iteration of while-loop on line 4, Algorithm 1 first checks if Xt {0, 1}n m in O(nm) time. Since each issue has at least one direct voter, in the first iteration of the while-loop the for-loop on line 6 checks at most m(n 1) delegations, to see if their delegate has a vote in X0, each taking constant time. As the profile is acyclic, at least one vote for each issue is added in each iteration. Thus, in iteration t, the for-loop checks at most m(n t) delegations. Therefore, Algorithm 1 requires at most Pn t=1 nm + (n t)m O(mn2) time to check the while-loop condition and if a voter s delegate has a direct vote. Furthermore, once for each delegation, we check if the addition of their delegate s vote has a Γ-consistent completion, in total taking at most m(n 1)ℓsteps. Hence, Algorithm 1 terminates in O(nm(n + ℓ)) time.

Proposition 5. PVC terminates in O(nm(n + ℓ)) time.

Proof. Algorithm 2 first finds XB in O(n2m) time, where for each issue and each agent it takes at most O(n) time to unravel the delegation chain until a direct voter is found. For each delegation in B, the for-loop on line 4 will check, following the order given by the priorities, if the addition of the vote found in XB along with the votes already in X0 can be completed to comply with Γ. As there are at most m(n 1) delegations and each completion check takes ℓsteps, this can be done in O(nmℓ) time. Summing the two figures we obtain that Algorithm 2 gives an outcome in O(nm(n+ℓ)) time.

4.2 Approximation Bounds Next we assess whether PDC and PVC are good polynomial approximations of MDC and MVC, giving a negative response. This is unsurprising, as PDC and PVC aim to respect priorities rather than minimise changes. We abuse notation by defining flip(F(B)) to count the number of changes that F makes when finding a consistent outcome on profile B. This corresponds to delegations in B being ignored by PDC and MDC, or direct votes being reverted in XB by PVC and MVC.

Proposition 6. For each n 3 and m 2 there is a profile B such that flip(PDC(B)) = O(nm) flip(MDC(B)).

Proof. Consider N = {A1, , An} and I = {i1, , im}, and XΓ = {(0, , 0), (1, , 1)}. Consider profile B where BA1 = (1, , 1), BA2 = (0, , 0), and for the remaining agents let BAt = (At 2, At 1, , At 1) for t [3, n], each with priorities ix At iy if and only if x < y. As replacing the delegation of A3 on issue i1 to a direct vote of 0 gives a consistent profile, flip(MDC(B)) = 1. However, PDC returns the vote XAt = (1, , 1) when t is odd and XAt =

A4 A2 A3 A3 A3 A1 A2 A2

A1 1 1 1 A2 0 0 0

(a) Profile from Proposition 6

A4 A1 A2 A2 A3 A1 A2 A2

A1 1 1 1 A2 0 0 0

(b) Profile from Proposition 7

Figure 1: The profiles from (a) Proposition 6 and (b) Proposition 7 when N = {A1, A2, A3, A4} and |I| = m.

(0, , 0) when t is even. Thus, for the n 2 delegating agents, At with t 2, all of their delegations are flipped for the issues in I\{i1}. Thus, flip(PDC(B)) = (n 2)(m 1), and flip(PDC(B)) = O(nm) flip(MDC(B)).

Proposition 7. For each n 3 and m 2 there is a profile B such that flip(PVC(B)) = O(m) flip(MVC(B)).

Proof. Consider N = {A1, , An} and I = {i1, , im}, and XΓ = {(0, , 0), (1, , 1)}. The ballots of B are as follows: BA1 = (1, , 1), BA2 = (0, , 0), and the remaining agents have the ballot BAt = (A1, A2, , A2) for t [3, n], with the priorities ix At iy for x < y. The canonical profile XB is inconsistent since XAt = (1, 0, , 0) for t > 2. MVC alters the delegated vote of such voters on issue i1, hence flip(MVC(B)) = n 2. PVC instead reverts all delegated votes except for the one on issue i1, hence flip(PVC(B)) = (n 2) (m 1). Therefore, flip(PVC(B)) = O(m) flip(MVC(B)).

4.3 Comparing Rules on Priorities In this section we compare the four consistent delegation rules with respect to the agents priorities over the issues. We use the topi function which identifies agent i s highest priority issue from a subset of issues according to i.We first define the sets of issues on which a rule F does not respect agent i s delegations, either with respect to their delegate (del):

deli F(B)={j | j I, Bij / {0, 1} and F(B)ij =F(B)Bijj},

or with respect to the canonical profile of vote (dir):

diri F(B)={j | j I and XB ij = F(B)ij}.

The set deli F(B) identifies the issues on which the votes of agent i in F(B) differ from their delegate s vote, whereas diri F(B) identifies the issues on which the votes of agent i in the outcome F(B) differ to their votes in XB. Note

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

that there is no logical connection between these sets. Intuitively, agents want lower priority issues to be in these sets, as they reflect the delegations that have been ignored in finding consistent votes. For a profile B, rules F and F , and measure c {del, dir}, we say that an agent i topprefers ci F(B) to ci F (B) (denoted by ci F(B) top i ci F (B)) if topi(ci F(B)) i topi(ci F (B)), where topi(c) gives the highest element of c with respect to i. Thus, top-preferring ci F(B) to ci F (B) entails that the top issue whose delegation is ignored using F has a lower priority than the top issue using F . Let c B F = (c1 F(B), , cn F(B)), and c B F top N c B F if and only if ci F (B) top i ci F(B) for every i N. The following proposition shows that PVC respects issues with higher priorities than its minimisation counterpart MVC.

Proposition 8. dir B MVC top N dir B PVC for any profile B.

Proof. We assume for a contradiction that there exists a profile B such that dir B MVC top N dir B PVC. Therefore, there is an agent i N such that topi(diri MVC(B)) i topi(diri PVC(B)). Suppose that topi(diri MVC(B)) is i s kth

priority and that topi(diri PVC(B)) is i s mth priority (thus, m < k). MVC outputs a consistent vote including i s first (k 1) top-priority issues. Thus, the partial truth assignment Xi including i s direct votes and accepting the delegations on the top (k 1) priority issues is such that Xi p Γ. PVC on the other hand only accepts the delegations on i s top (m 1) priorities and rejects the delegation on the mth issue. Yet if Xi p Γ, then any X Xi is such that X p Γ, including the partial assignment accepting i s direct votes and their delegations on the first m priority issues. We have reached a contradiction as PVC rejected a partial assignment that could be completed.

We now show that the analogous result is not true for PDC.

Proposition 9. There exists profiles B and B such that del B MDC top N del B PDC and del B PDC top N del B MDC .

Proof. First we give B such that del B MDC top N del B PDC. We have N={C, D, E, F} and issues I={i, j, k} with the set of consistent votes being XΓ = {(1, 0, 0), (0, 1, 1)}. We let BC = (1, 0, 0), BD = (0, 1, 1), BE = (0, 1, 1) and agent F delegates as such: BF = (C, D, E) with the following priorities over the issues i F j F k. PDC first adds F s delegation on i giving XF = (1, , ), and then attempts to add the delegations on j and k but rejects both giving XF = (1, 0, 0). Thus, del F PDC(B) = {j, k}. MDC returns X F = (0, 1, 1), where only the delegation on issue i is changed, thus del F MDC(B) = {i}. All agents T N\{F} are direct voters, hence del T MDC(B)=del T PDC(B)= . As top F (del F MDC) F top F (del F PDC), we can conclude that del B MDC top N del B PDC. Now let N, I, and XΓ be as in the first part of the proof, and let profile B be composed of BC=(0, 1, 1), BD=(1, 0, 0), BE=(C, C, 1), and BF =(E, E, D), with E and F having the priority i j k. The first iteration of Algorithm 1 gives XE = (0, 1, 1) and XF = ( , , 0).

In the second iteration we have XF = (1, 0, 0), as the delegations to E are inconsistent. Therefore, del C PDC(B ) = del D PDC(B ) = del E PDC(B ) = , whereas, del F PDC(B )={i, j}. MDC however lets XF =(0, 1, 1) where del F MDC(B )={k}. As top F (del F MDC(B )) F top F (del F PDC(B )), we have that del B PDC top N del B MDC.

5 Knapsack Constraints In this section we focus on knapsack or budget constraints, i.e., sets of feasible votes respecting a budget limit L N of the form ΓL={X | P j I xj L}. They have the property that turning a vote from acceptance to rejection in a consistent ballot preserves consistency. This property is exploited by Jain et al. [2021] in their algorithm to remove cycles and solve inconsistent delegations. However, this can lead to rejecting a large number of issues and potentially leaving funds unassigned. In this section we evaluate this factor for the four rules we proposed. Let count(X) = P i N ,j I xij be the number of acceptances in the profile of votes X. Remark 3. Given a profile B and budget constraint ΓL, we have that count(XB) count(F(B)) for F {MDC, MVC, PDC, PVC}. Proposition 10. For any profile B, count(MVC(B)) count(F(B)) for F {MDC, PVC, PDC}.

Proof. B is an arbitrary profile and ΓL a budget constraint. MVC(B) outputs all consistent profiles of votes obtained from XB with a minimal number of 1s changed to 0s. Our rules do not change 0s to 1s, as rejections do not use any of the budget. Note that if X, X MVC(B) then count(X) = count(X ). Thus, any other consistent delegation rule must approve at most the same number of issues as MVC(B).

An analogous result showing that PVC accepts more issues than MDC or PDC does not hold, as can be shown by counterexample. To conclude, the approach of minimal delegation changes proposed in the literature might not be appropriate for budgeting applications, where it is outperformed by minimal vote changes in terms of number of projects accepted.

6 Conclusion Existing approaches in the literature looked at changes to the ballots of voters to maintain consistency, in knapsack voting and in preference aggregation. We generalise this by studying liquid democracy on multiple interconnected issues, putting forward two novel ideas: first, we propose two rules that start by resolving delegations and then make changes to the final votes and, second, we design polynomial algorithms to maintain vote consistency by eliciting agents priorities. The main open problem is whether PDC can be improved, since Proposition 9 shows that it does not use priorities in the best way. We conjecture that this cannot be done in polynomial time, but a result showing this impossibility is yet to be shown. Our result in Section 5 shows that specific constraints require specific treatment, and thus the choice of a consistent delegation rule is not trivial. Hence a prominent direction for future research is to specify our general setting on specific classes of constraints.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

Acknowledgments

The authors acknowledge the support of the ANR JCJC project SCONE (ANR 18-CE23-0009-01).

References [Armstrong and Larson, 2021] Ben Armstrong and Kate Larson. On the limited applicability of liquid democracy. In Appears at the 3rd Games, Agents, and Incentives Workshop (GAIW 2021). Held as part of the Workshops at the 20th International Conference on Autonomous Agents and Multiagent Systems, 2021. [Becker et al., 2021] Ruben Becker, Gianlorenzo D Angelo, Esmaeil Delfaraz, and Hugo Gilbert. Unveiling the truth in liquid democracy with misinformed voters. In International Conference on Algorithmic Decision Theory (ADT), 2021. [Boldi et al., 2011] Paolo Boldi, Francesco Bonchi, Carlos Castillo, and Sebastiano Vigna. Viscous democracy for social networks. Communications of the ACM, 2011. [Botan et al., 2019] Sirin Botan, Umberto Grandi, and Laurent Perrussel. Multi-issue opinion diffusion under constraints. In Proceedings of the 18th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2019. [Brill and Talmon, 2018] Markus Brill and Nimrod Talmon. Pairwise liquid democracy. In Proceedings of the Twenty Seventh International Joint Conference on Artificial Intelligence (IJCAI), 2018. [Brill et al., 2022] Markus Brill, Th eo Delemazure, Anne Marie George, Martin Lackner, and Ulrike Schmidt Kraepelin. Liquid democracy with ranked delegations. Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 2022. [Caragiannis and Micha, 2019] Ioannis Caragiannis and Evi Micha. A contribution to the critique of liquid democracy. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI), 2019. [Christoff and Grossi, 2017] Zo e Christoff and Davide Grossi. Binary voting with delegable proxy: An analysis of liquid democracy. In Proceedings Sixteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 2017. [Dey et al., 2021] Palash Dey, Arnab Maiti, and Amatya Sharma. On parameterized complexity of liquid democracy. In Algorithms and Discrete Applied Mathematics - 7th International Conference (CALDAM), 2021. [Dhillon et al., 2021] Amrita Dhillon, Grammateia Kotsialou, and Dimitris Xefteris. Information aggregation with delegation of votes. Center for Open Science, 2021. [Escoffier et al., 2019] Bruno Escoffier, Hugo Gilbert, and Ad ele Pass-Lanneau. The convergence of iterative delegations in liquid democracy in a social network. In Algorithmic Game Theory - 12th International Symposium (SAGT), 2019.

[Friedkin et al., 2016] Noah E. Friedkin, Anton V. Proskurnikov, Roberto Tempo, and Sergey E. Parsegov. Network science on belief system dynamics under logic constraints. Science, 354(6310):321 326, 2016. [Halpern et al., 2021] Daniel Halpern, Joseph Y Halpern, Ali Jadbabaie, Elchanan Mossel, Ariel D Procaccia, and Manon Revel. In defense of fluid democracy. ar Xiv preprint ar Xiv:2107.11868, 2021. [Harding, 2021] Jacqueline Harding. Proxy selection in transitive proxy voting. Social Choice and Welfare, pages 1 31, 2021. [Jain et al., 2021] Pallavi Jain, Krzysztof Sornat, and Nimrod Talmon. Preserving consistency for liquid knapsack voting. In 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2021. [Kahng et al., 2021] Anson Kahng, Simon Mackenzie, and Ariel Procaccia. Liquid democracy: An algorithmic perspective. Journal of Artificial Intelligence Research, 70:1223 1252, 2021. [Karp, 1972] Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations, pages 85 103. Springer, 1972. [Kotsialou and Riley, 2020] Grammateia Kotsialou and Luke Riley. Incentivising participation in liquid democracy with breadth-first delegation. AAMAS, 2020. [Lang et al., 2011] J erˆome Lang, Gabriella Pigozzi, Marija Slavkovik, and Leendert van der Torre. Judgment aggregation rules based on minimization. In Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 2011. [Markakis and Papasotiropoulos, 2021] Evangelos Markakis and Georgios Papasotiropoulos. An approval-based model for single-step liquid democracy. In Algorithmic Game Theory - 14th International Symposium (SAGT), 2021. [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. [Zhang and Grossi, 2022] Yuzhe Zhang and Davide Grossi. Tracking truth by weighting proxies in liquid democracy. Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2022.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)