Preserving Consistency in Multi-Issue Liquid Democracy

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], 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 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.

1 Non-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.

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 ∣≈ Γ 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 ∣≈ Γ. 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).

2 Here 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.

3 Brill and Talmon [2018] also define a weaker notion of consistency. Both are equivalent to our definition on acyclic profiles.

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 Γ:

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′ fromB. 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:

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 fromXB following the order of priorities. We now define some notation

4 Jain 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.

Algorithm 1 Priority delegation changing (PDC)

1: Input: B, ≺i for all i ∈ N 2: t = 0 3: FindX0 = ˆ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)) ∣≈ Γ 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×mmatrix 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 X1Ej = 1. Then the delegation on the second priority issue k is not consistent, thus, X1Ek = 0. As in X0 , E does not have any votes, F's votes can only be added in the second iteration. Thus, X2F = (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: FindX0 = ˆB 3: FindXB 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)) ∣≈ Γ then vote(X0 , i, j) := vote(X0 ,XB ij , i) 8: else vote(X0 , i, j) := 1 - vote(X0 , XB ij , j) 9: X :=X0

using PDC, PVC then changes E's vote to X0E = (1, 0). However, for F, it first tries X0Fk = 1 in accordance with F's priorities, which is consistent, entailing that X0Fj = 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 XtBijj = ∆. 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 ∣≈ Γ 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 ∣≈ Γ for all i ∈ N. It then iteratively adds votes fromXB if they can be completed 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).

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 ∑nt=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 =

(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)(m1), 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):

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

The set deliF (B) identifies the issues on which the votes of agent i in F(B) differ from their delegate's vote, whereas diriF (B) identifies the issues on which the votes of agent i in the outcome F(B) differ to their votes in XB . Note 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 ciF (B) to ciF ′ (B) (denoted by ciF (B) ⪰top i ciF ′(B)) if topi (ciF (B)) ⪯i topi (ciF ′ (B)), where topi (c) gives the highest element of c with respect to ≺i. Thus, top-preferring ciF (B) to ciF ′(B) entails that the top issue whose delegation is ignored using F has a lower priority than the top issue using F ′ . Let cBF = (c1F (B), · · ·, cnF (B)), and cBF ′ ⪯top N c′BF if and only if ciF ′ (B) ⪯top i ciF (B) for every i ∈ N.

The following proposition shows that PVC respects issues with higher priorities than its minimisation counterpart MVC.

Proof. We assume for a contradiction that there exists a profile B such that dirBMVC ⪯̸top N dirBPVC . Therefore, there is an agent i ∈ N such that topi (diriMVC (B)) ≺i topi (diriPVC (B)). Suppose that topi (diriMVC (B)) is i's k th priority and that topi (diriPVC (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 ∣≈ Γ. 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 ∣≈ Γ, then any X′ ⊆ Xi is such that X′ ∣≈ Γ, 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 delBMDC ⪯top N delBPDC and delB′ PDC ⪯top N delB′ MDC .

Proof. First we give B such that delBMDC ⪯top N delBPDC . 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, delF PDC (B) = {j, k}. MDC returns X′F = (0, 1, 1), where only the delegation on issue i is changed, thus delF MDC (B) = {i}. All agents T ∈ N\{F} are direct voters, hence delT MDC (B)=delT PDC (B)=∅. As topF (delF MDC ) ≺F topF (delF PDC ), we can conclude that delBMDC ⪯top N delBPDC .

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, delC PDC (B′ ) = delD PDC (B′ ) = delE PDC (B′ ) = ∅, whereas, delF PDC (B′ )={i, j}. MDC however lets XF=(0, 1, 1) where delF MDC (B′ )={k}. As topF (delF MDC (B′ )) ≺F topF (delF PDC (B′ )), we have that delB′ PDC ⪯top N delB′ 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 | ∑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) = ∑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.

Acknowledgments

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