Pairwise Liquid Democracy

1 Introduction

Liquid democracy is based on the paradigm of delegative voting and can be seen as a middle ground between direct democracy and representative democracy (see, e.g., [Blum and Zuber, 2016; Behrens et al., 2014]). Under this paradigm, each voter can choose to either vote directly, or to select another voter acting as her delegate. Delegation is transitive, in the sense that the delegate can choose to delegate the vote further, resulting in delegation paths along which voting weight is accumulated. The voting weight of a voter who decides to actually vote is then given by the number of voters whodirectly or indirectly-delegated their vote to this voter.

Liquid democracy has been popularized by the German Pirate Party, which was one of the first organizations to employ the LiquidFeedback software [Behrens et al., 2014] for decision making within the party. Similar tools have been used in other political parties, such as the Spanish party Partido de Internet, the local Swedish party Demoex, and the Argentinian "Net Party" (Partido de la Red).

Liquid democracy is appealing due to the flexibility it offers to voters. In this paper, we aim to increase this flexibility further by introducing the concept of pairwise liquid democracy. Specifically, we consider ordinal elections, where each voter needs to rank-order a set of alternatives. This setting, which is standard in social choice theory, is in fact used in LiquidFeedback [Behrens et al., 2014, Chapter 14.12]. We propose that voters in an ordinal election can make use of delegations in a fine-grained manner, by specifying a partial order and then using several delegates to refine different parts of that partial order. We illustrate the idea with an example.

Example 1. Consider the alternatives a, b, c, d, and assume that a voter v feels strongly about a being the best alternative, but is not sure how the remaining three alternatives compare. Moreover, voter v trusts another voter v′ to know whether b is better than c (maybe b and c differ mainly in one aspect, on which v′ happens to be an expert) and voter v moreover thinks that the comparison between c and d could be best performed by a third voter v′′ (maybe v′′ has a lot of experience with both c and d). For the sake of the example, say that voter v′ decides that b is better than c and voter v′′ decides that c is better than d. Then, the resulting ranking of v, after taking the delegations into account, would be a ≻ b ≻ c ≻ d. 1

Notice the flexibility voter v used in her delegations, and how v′ and v′′ helped to refine her initial partial order. This flexibility is useful, e.g., for voters who (a) really care about the outcome of an election, but (b) do not feel well-informed or competent enough to compare certain pairs of alternatives. This flexibility, as might be suspected, comes at a price: Refining a partial order by delegating certain pairwise comparisons to different delegates might result in intransitive preference orders (see Figure 1 for a concrete example).

In this paper, we study such combinatorial complications, and discuss ways to overcome them. Specifically, we consider the problem of deciding whether a given delegation graph is consistent (i.e., whether, after taking into account delegations, all preference orders are transitive). For inconsistent delegation graphs, we then consider several approaches to cope with intransitive preference orders. Finally, we identify a rich family of voting rules which operate directly on such delegation graphs. These rules generalize standard voting rules and could be considered more appropriate for the pairwise liquid democracy setting.

An important appeal of liquid democracy is the flexibility it offers to participants. We argue that extending this flexibility further, specifically by allowing pairwise delegations, holds a significant potential for advancing the liquid democracy paradigm.

1 Note that, in this example, voter v did not explicitly delegate the comparison between b and d. In a sense, voter v got lucky that the decisions by her delegates v′ and v′′ resulted in a consistent ranking. Later we will concentrate on situations in which voters are required to delegate all pairwise comparisons that are not decided by themselves; we will see that this might result in certain inconsistencies.

RELATED WORK. While some of the ideas behind liquid democracy can be traced back to early works of [Dodgson, 1884] and [Miller, 1969], the idea has been mainly developed since the early 2000s (see, e.g., [Ford, 2002]). For an historical overview of the development of the idea, we refer to the surveys by [Ford, 2014] and [Behrens, 2017].

In recent years, liquid democracy has gained increasing attention from the scientific community. [Boldi et al., 2011] studied a variant of liquid democracy called viscous democracy, which uses a discount factor for dampening the impact of long delegation paths. Attempts to formally establish the virtues of liquid democracy have been undertaken by [GreenArmytage, 2015] and [Cohensius et al., 2017], who considered spatial voting models and showed that liquid democracy outperforms direct democracy under certain conditions. On the other hand, [Kahng et al., 2018] have established that liquid democracy with so-called local delegation mechanisms cannot truly outperform direct democracy with respect to the ability of recovering a ground truth.

Perhaps the most related work to our paper is that of [Christoff and Grossi, 2017], who consider delegative voting in the binary aggregation framework. In this setting, there are several binary issues and voters can delegate their vote on individual issues to different voters, potentially resulting in voter preferences that are not "individually rational" because they violate an integrity constraint. Our model of ordinal voting can be seen as a special case, where issues are pairwise comparisons between alternatives and the integrity constraint requires the transitivity of preferences. Focussing on the important special case of ordinal voting allows us to study specific problems, and to come up with specific solutions, that might not manifest in the more general framework.

2 Preliminaries

Let N = {1, . . . , n} be a finite set of n voters and A = {a, b, c, . . .} a finite set of |A| = m alternatives. The preferences of voter i ∈ N are modeled as an asymmetric 2 binary relation Ri ⊂ A×A. The interpretation of (a, b) ∈ Ri, which is denoted a ≻i b (or a ≻ b if i is obvious from the context), is that voter i strictly prefers alternative a over alternative b. A preference relation Ri is complete if a ≻i b or b ≻i a for every pair of distinct a, b ∈ A, and it is transitive if a ≻i b and b ≻i c implies a ≻i c for all distinct a, b, c ∈ A. For a preference relation Ri and a subset A′ ⊆ A of alternatives, we let Ri|A′ denote the restriction of Ri to A′ ×A′ .

A ranking (or linear order) over A is a transitive and complete preference relation and is denoted a1 ≻ a2 ≻ . . . ≻ am, with the understanding that aj ≻ a′j if and only if j < j ′ . A weak ranking over A is a transitive preference relation that can be described by an ordered partition (A1,A2, . . . ,Ak) and the assumption that a ≻ b if and only if there exits j and j ′ such that a ∈ Aj, b ∈ Aj ′ , and j < j ′ . For example, {a, b} ≻ c ≻ {d, e} denotes the weak ranking with

2 Asymmetry requires that (a, b) ∈ Ri implies (b, a) /∈ Ri for all a, b ∈ A. It also implies irreflexivity, i.e., (a, a) /∈ Ri for all a ∈ A.

Figure 1: Intransitive preferences due to pairwise delegations.

A1 = {a, b}, A2 = {c}, and A3 = {d, e}. Each set Ai in the ordered partition is called an indifference class.

A preference relation Ri contains a preference cycle if there exists a k ≥ 3 and alternatives a1, a2, . . . , ak such that a1 ≻i a2, a2 ≻i a3, ..., ak ≻i a1. A complete preference relation is transitive iff it does not contain a preference cycle.

A preference profile is a list R = (R1, . . . , Rn) containing a preference relation Ri for every voter i ∈ N. A preference profile R is complete (resp., transitive) if every preference relation in it is complete (respectively, transitive). A preference profile R′ = (R′1 , . . . ,R′n ) is an extension of a preference profile R = (R1, . . . , Rn) if Ri ⊆ R′i for all i ∈ N.

3 Pairwise Delegations

We introduce the model of pairwise liquid democracy, which strictly generalizes the standard liquid democracy paradigm.

Let P denote the set of all unordered pairs of distinct alternatives. For a pair {a, b} ∈ P, we usually write ab; in particular, ab and ba refer to the same unordered pair. Every voter i ∈ N divides the set P into two sets: the set of internal pairs Pint(i) and the set of external pairs Pext(i). For every internal pair ab, the voter specifies her (strict) preferences between the two alternatives in question (a ≻i b or b ≻i a). 3 For every external pair cd, the voter designates another voter j ∈ N \ {i} as the pairwise delegate for that pair. 4

PAIRWISE DELEGATION GRAPHS. The collection of all internal and external pairs can be represented by a directed graph with n vertices, where each vertex vi corresponds to a voter i ∈ N. Every node vi ∈ N is labeled with the preferences over the internal pairs Pint(i) of voter i. A directed arc from vi to vj has a label ab ∈ P and corresponds to the external pair ab ∈ Pext(i) that voter i delegates to voter j. Notice that there could be parallel edges (if i delegates several pairs to j). We refer to such a graph as a pairwise delegation graph.

Pairwise delegation graphs can sometimes lead to intransitive preference relations, as the next example demonstrates.

Example 2. Consider the pairwise delegation graph G depicted in Figure 1 with n = 3 voters and alternatives a, b, c.

3 Internally specified preferences are assumed to be transitive.

4 We usually assume that each voter specifies every pair in P either as an internal pair or as an external pair. Sometimes, however, we consider instances (such as the one constructed in the proof of Theorem 2) without specifying explicitly whether certain pairs are internal or external. In those cases, such "unspecified" pairs can be arbitrarily set to either internal or external pairs without impacting the construction. A simple, general way of reducing an instance with unspecified pairs to one without such pairs is to add some additional, dummy voters: For each voter i containing at least one unspecified pair, add a voter i′ , initially with the same internal and external pairs as voter i, and add each unspecified pair of i as an external pair for both i and i′ , who delegate those pairs to each other. The modified instance preserves (weak) consistency (see Definitions 1 and 2).

Voter 1 internally declares the ranking a ≻1 b ≻1 c and voter 2 internally declares the ranking c ≻2 b ≻2 a. Voter 3 internally declares a ≻3 b, delegates bc to voter 1, and delegates ac to voter 2. As a result, the preference relation of voter 3 contains a preference cycle: a ≻3 b, b ≻3 c, c ≻3 a.

The following notation will be useful for the remainder of the paper. For a voter i ∈ N and an external pair ab ∈ Pext(i), let delab(i) denote the ultimate delegate of i with respect to ab; it can be found by following the path in G starting in vi and following the ab-labeled arcs. There are two possibilities: either the path leads to a voter j ∈ N \ {i} with ab ∈ Pint(j) or the path leads to a cycle (which we call an ab-cycle). In the former case, we let delab(i) = j (note that j is uniquely determined by G); in the latter case, we write delab(i) = ∅ and say that i has no ultimate delegate with respect to ab.

The arc-set of a pairwise delegation graph G is the union of (m2 ) arc-sets, each corresponding to a pair in P. For a pair ab ∈ P, the ab-graph is the subgraph of G containing only those arcs labeled ab. G does not contain pairwise delegation cycles if, for each ab ∈ P, G does not contain an ab-cycle.

FROM GRAPHS TO PREFERENCE PROFILES. For a pairwise delegation graph G, R(G) is the preference profile resulting from resolving all delegations. That is, for each voter i ∈ N and each external pair ab of i, we find the ultimate delegate delab(i) (if it exists) and add the corresponding ordered pair (either (a, b) or (b, a)) to Ri. If delab(i) = ∅ (implying that there is an ab-cycle), however, then neither (a, b) nor (b, a) is added to Ri. Indeed, whenever G contains pairwise delegation cycles, then some ultimate delegates are not defined and, consequently, R(G) is not complete.

A preference profile R respects a pairwise delegation graph G if for all voters i ∈ N and all ab ∈ Pext(i), Ri|ab = Rj |ab, where j is the voter that i delegates ab to. (If delab(i) = ∅, then Ri|ab = ∅.) By definition, R(G) respects G. Sometimes we are interested in complete and transitive preference profiles respecting G. The set of all such profiles is denoted by ˆR(G). Figure 1 illustrates that ˆR(G) may be empty. A necessary condition for a profile to be contained in ˆR(G) is to extend R(G). If G does not contain pairwise delegation cycles and ˆR(G) ̸= ∅, then ˆR(G) = {R(G)}.

4 Detecting Intransitivities

Example 2 demonstrates that pairwise delegations can potentially yield intransitive preferences for individual voters, even when the internal pairs satisfy transitivity. Whether such intransitive preferences arise depends on the pairwise delegation graph in question, and it might not be straightforward to check whether a given graph yields intransitivities or not. Next, we analyze the detection of intransitivities from a computational complexity perspective. A first step in checking for inconsistencies in voters' preferences is to propagate pairwise comparisons along delegation arcs and check whether this results in violations of transitivity. If this is not the case, we call the pairwise delegation graph weakly consistent.

Definition 1 (weak consistency). A pairwise delegation graph G is weakly consistent if no preference relation in R(G) contains a preference cycle.

For example, the pairwise delegation graph in Figure 1 violates weak consistency.

Weak consistency can be checked efficiently: It is sufficient to observe that, for each voter i ∈ N and for each pair ab ∈ Pext(i), the ultimate delegate delab(i) can be computed efficiently, e.g., using a depth first search.

Observation 1. It can be checked in polynomial time whether a pairwise delegation graph is weakly consistent.

Even if pairwise delegations do not result in preference cycles, it could be the case that R(G) cannot be extended to a complete and transitive preference profile respecting all delegations. In other words, the set ˆR(G) may be empty even if G is weakly consistent. This is illustrated in Figure 2. The following stronger notion of consistency forbids such "hidden" inconsistencies.

Definition 2 (consistency). A pairwise delegation graph G is consistent if ˆR(G) ̸= ∅; i.e., if there exists a complete and transitive G-respecting extension of R(G).

Recall that each incompleteness of R(G) (i.e., each preference relation in R(G) for which some pairwise comparisons are unknown) is caused by a pairwise delegation cycle. Thus, a pairwise delegation graph is consistent if and only if, for every pairwise delegation cycle of G, the preferences over the respective pair can be "fixed" in a way that does not result in intransitive individual preferences. In particular, profiles in ˆR(G) have the property that all voters that are contained in an ab-cycle (and also those contained in an ab-path leading to that cycle) have identical preferences over ab (either a ≻ b or b ≻ a). In the absence of pairwise delegation cycles, R(G) is complete (as ultimate delegates are always defined); consequently, the two consistency notions coincide.

Proposition 1. A pairwise delegation graph not containing pairwise delegation cycles is weakly consistent if and only if it is consistent.

It turns out that, in contrast to checking weak consistency, checking consistency is computationally intractable.

Theorem 2. Deciding whether a given pairwise delegation graph is consistent is NP-complete.

Proof. Membership in NP follows directly from Proposition 1, by guessing the decisions made on the cycles. Next, we provide a reduction from the NP-hard problem 3SAT, in which we have a Boolean 3-CNF formula φ with m clauses Cj, j ∈ [m], over n variables xi, i ∈ [n], and shall decide whether φ is satisfiable. Given an instance φ of 3SAT, we create a pairwise delegation graph G as follows.

For each variable xi, i ∈ [n], we create a voter xi and two alternatives, ti and fi. For each clause Cj , j ∈ [m], we create a voter cj. If Cj = (xj1 ∨xj2 ∨xj3), then voter cj delegates the pair tj1fj1 to voter xj1, the pair tj2fj2 to voter xj2, and the pair tj3fj3 to voter xj3. The idea is that the decision of voter xi for the pair tifi shall correspond to the sign of the literal of xi: ti ≻ fi corresponds to a positive literal, while fi ≻ ti corresponds to a negative literal. The internal pairs of voter cj correspond to the signs of its literals. To explain how, we consider several cases, depending on its form; for notational simplicity, assume that Cj contains the variables x1, x2, and x3, and consider the form of its negation, ¬Cj:

• If ¬Cj = (x1 ∧ x2 ∧ x3), then cj internally decides f1 ≻ t2, f2 ≻ t3, and f3 ≻ t1.
• If ¬Cj = (x1 ∧ x2 ∧ ¬x3), then cj internally decides f1 ≻ t2, f2 ≻ f3, and t3 ≻ t1.
• If ¬Cj = (x1 ∧ ¬x2 ∧ ¬x3), then cj internally decides f1 ≻ f2, a2 ≻ f3, and t3 ≻ t1.
• If ¬Cj = (¬x1 ∧¬x2 ∧¬x3), then cj internally decides t1 ≻ f2, t2 ≻ f3, and t3 ≻ f1.

The idea is that, as satisfying ¬Cj would cause φ to be unsatisfied, the internal decisions of cj, combined with those decisions of the voters corresponding to the literals of Cj which would satisfy ¬Cj would cause a preference cycle in cj's preference relation. This finishes the reduction. An example is given in Figure 3. (Pairs not explicitly specified as either internal or external pair can be set arbitrarily without introducing preference cycles; see also Footnote 4.)

Correctness follows as any G-respecting complete extension of R(G) shall decide, for each xi, whether ti ≻ fi or fi ≻ ti; these decisions would propagate to the cj's, causing a preference cycle in each cj for which ¬Cj is satisfied.

Remark 1. There is an elegant SAT-formulation of the consistency problem. This is also of practical importance, as it allows the use of efficient SAT solvers. For each vertex v and each pair ab, define a binary variable va,b, with the intended meaning that va,b = 0 if a ≻v b in a complete extension of R(G), and va,b = 1 otherwise. For any delegation arc (v, u) labeled ab, we add an arc-clause: (ua,b → va,b) ∧ (ua,b → va,b). For each vertex v and each triplet of alternatives a, b, c we add the transitivity constraints: (va,b ∧ vb,c) → va,c and

(va,b ∧ vb,c) → va,c. The corresponding formula is satisfiable if and only if G is consistent; in this case, the variables encode a profile in ˆR(G).

5 Coping with Intransitivities

It is unfortunate that allowing pairwise delegations might result in intransitive preferences. In this section we suggest several ways of coping with this problem. In particular, we explore approaches to prevent intransitive preferences by restricting allowed delegations, ways to circumvent intransitive preferences by ignoring delegations, and the possibility of consolidating intransitive preferences into weak rankings. 5

5.1 Restricting Allowed Delegations

Intransitive preferences are the result of the flexibility of pairwise liquid democracy. It is therefore natural to consider restrictions to our general model, specifically tuning this flexibility to avoid such individually irrational outcomes.

Taken to the extreme, we might say that if a voter delegates some pair to another voter, then she shall delegate all (m2 ) pairs to that voter; indeed, this is a very cumbersome way to describe the standard (non-pairwise) delegation on which liquid democracy is based: Each voter can either specify her own ranking, or delegate her complete vote to another voter. A more flexible approach that still prevents intransitivities consists in letting each voter specify a weak ranking together with a list of delegates, one delegate for each indifference class of the weak ranking. The weak ranking of the voter would then be completed into a linear order by ranking the alternatives in each indifference class according to the preferences of the corresponding delegate. Assuming no pairwise delegation cycles, this approach is guaranteed to result in a complete and transitive preference profile. Note, however, that this approach restricts the freedom of voters to some extent: coming up with a weak ranking already requires a lot of internal decisions, and a voter might not be willing/competent to make those decisions.

5.2 Modifying Existing Delegations

Another approach to prevent intransitive preferences consists in modifying the delegation graph. Specifically, intransitivities can be circumvented by removing (ignoring) some pairwise delegations. E.g., recall the inconsistent pairwise delegation graph of Figure 1 and observe that removing any one of the two external pairs yields a consistent graph.

A natural objective is to make a pairwise delegation graph consistent by removing as few delegations as possible, as it would hopefully correspond to only a negligible change to the graph. This motivates the following computational problem, which we refer to as the consistency modification problem:

5 This list is by no means exhaustive. For instance, [Christoff and Grossi, 2017] suggest to avoid inconsistencies by employing an opinion diffusion approach [DeGroot, 1974]. Under this approach, a voter incorporates the decisions of delegates only if it does not introduce inconsistencies. Though we do not consider this idea further in this paper, we note that opinion diffusion can be applied on the level of pairwise comparisons of alternatives [Brill et al., 2016].

Given a pairwise delegation graph G and an integer b ≥ 0, can at most b arcs be removed from G in order to make G consistent?

The consistency modification problem can be defined for both weak consistency and consistency as the desired goal. The budget b plays an important role, as with a high enough budget any graph can be made consistent (e.g., the empty graph is always consistent). The problem is intractable.

Theorem 3. The consistency modification problem is NPcomplete, both for weak consistency and for consistency.

Proof sketch. NP-hardness follows from a straightforward reduction from Feedback Arc Set on Tournaments. Given a tournament T = (W, E), we construct a pairwise delegation graph G with voter set N = v∗ ∪ {ve : e ∈ E}. The set of alternatives is defined by the set W of vertices of T . Voter v∗ has only external pairs: for every directed edge e = (x, y) of the tournament T, voter v∗ delegates the pair xy to voter ve, who has only internal pairs, and in particular prefers x to y.

Now we can make G consistent (or weakly consistent) by removing b external pairs if and only if we can make T acyclic by removing b directed edges from E.

Remark 2. The consistency modification problem can be efficiently solved using MaxSAT solvers, by constructing the formula described in Remark 1, setting the weight of the arcclauses to 1, and setting the weight of other clauses to ∞. Indeed, a maximum weight MaxSAT solution corresponds to a solution of the consistency modification problem, with unsatisfied arc-clauses corresponding to deleted arcs.

5.3 Consolidating intoWeak Rankings

A further way to cope with intransitive voter preferences is to first "consolidate" those intransitivities into weak rankings, and then apply a voting rule which can cope with weak rankings. One way to accomplish this is by applying a tournament solution (e.g., the top cycle or the Copeland set), which takes an asymmetric and complete 6 binary relation on a set of alternatives as input and outputs a non-empty subset of alternatives [Laslier, 1997; Brandt et al., 2016]. These can be used iteratively to construct a weak rankings as follows: First, the tournament solution is applied to the set of all alternatives and the resulting subset of alternatives then defines the top-most indifference class of the weak ranking. These alternatives are then removed from consideration and the tournament solution is applied to the set of remaining alternatives to determine the next indifference class, and so on. This approach has been analyzed by [Bouyssou, 2004] and (for the special case of two indifference classes) [Yang, 2017].

6 Voting Rules for Delegation Graphs

The need to prevent, consolidate, or circumvent intransitivities can be rendered moot by employing a voting rule that accepts intransitive voter preferences. In particular, this is the case for all pairwise voting rules (a voting rule is pairwise 7 if it only depends on anonymized comparisons between pairs of alternatives). The motivation for this approach is rather straightforward: The premise of pairwise liquid democracy is that domain expertise in the form of high-accuracy pairwise comparisons should be exploited; and pairwise voting rules take all pairwise comparisons into account.

6 Completeness can be relaxed [Brandt et al., 2018]; therefore, this approach is feasible also for incomplete voter preferences resulting from pairwise delegation cycles.

An important example of a pairwise rule is Kemeny's rule [Kemeny, 1959], which enjoys a strong axiomatic foundation [Young and Levenglick, 1978] and has been established as the maximum likelihood estimator for a natural noise model [Young, 1995]. Under Kemeny's rule, for every ranking r we compute the minimum number of pairwise swaps that are necessary to transform the preference profile into one where all preference relations of voters coincide with r, and we pick the top-ranked alternative from the ranking r for which this number is the smallest.

However, pairwise voting rules-like all standard voting rules-have a drawback when applied to the pairwise liquid democracy setting: they ignore the structure of the pairwise delegation graph. Motivated by this observation, we initiate the study of so-called liquid voting rules, which take pairwise delegation graphs as input. Since pairwise delegation graphs can be viewed as generalizations of preference profiles (a preference profile corresponds to a pairwise delegation graph without external arcs), liquid voting rules generalize standard voting rules. In the following, we propose a generic way to "liquidize" voting rules. Our approach relies on the concept of distance rationalization.

6.1 Distance Rationalization

Distance rationalization (DR) is a very general framework in social choice theory [Elkind and Slinko, 2016]. Intuitively, a voting rule is distance rationalizable if there is a "distance function" and a "consensus class" such that winning alternatives coincide with consensus alternatives of the closest consensus profile, measuring closeness by the distance function.

Formally, a distance function is a metric on preference relations 8 and a consensus class C is a pair (R,W) where R is a set of preference profiles and W is a function mapping every R ∈ R to a winning alternative. The intuition is that the winner W(R) of a consensus profile R ∈ R is "obvious." A voting rule is (d, C)-distance rationalizable for distance d and consensus class C = (R,W) if, for every profile R, the rule selects the winner W(R′ ) of the consensus profile R′ ∈ R that is closest to R according to d. If several closest consensus profiles exist, then all corresponding consensus winners will be tied winners. For instance, Kemeny's rule is (d, C)-distance rationalizable for d being the swap distance (aka bubble sort distance) and C = (E,W) being the unanimous consensus class, consisting of all complete and transitive preference profiles in which all preference relations are identical.

7 Pairwise voting rules are also known as C2 functions [Fishburn, 1977] or weighted tournament solutions [Fischer et al., 2016].

8 That is, we consider what [Elkind and Slinko, 2016] call votewise distances. A distance function d on the set of preference relations naturally extends to a distance function on the set of preference profiles by letting d(R, R′ ) = ∑i∈N d(Ri, R′i).

6.2 Liquid Distance Rationalization

We generalize the DR framework by incorporating operations on pairwise delegation graphs. The basic idea is as follows. While the standard DR framework considers only the space of preference profiles and defines distance functions and consensus classes within that space, the liquid DR framework also considers the space G of all pairwise delegation graphs. These two spaces are related via the mappings R(·) and ˆR(·) defined in Section 3. Specifically, the distance function is defined on G, whereas the consensus classes remain in the space of preference profiles. Applying function ˆR(·) allows us to transfer the notion of consensus to the graph space.

Definition 3. Let C = (R,W) a consensus class. A pairwise delegation graph G is a consensus graph if ˆR(G) ∩ R ̸= ∅.

That is, a consensus graph is a pairwise delegation graph G whose corresponding preference profile R(G) can be extended to a consensus preference profile. The function W can be extended to consensus graphs by letting W(G) = W(R), where R ∈ ˆR(G) ∩R. (If | ˆR(G) ∩R| > 1, then all corresponding consensus winners are contained in W(G).)

We are now ready to define liquid distance rationalizability.

Definition 4. Let d be a distance function on G and C = (R,W) a consensus class. A liquid voting rule is (d, C)-distance rationalizable if, for any pairwise delegation graph G, the rule selects the winner(s) W(G′ ) of the consensus graph G′ that is closest to G according to d. (If several closest consensus graphs exist, then all corresponding consensus winners tie as winners.)

That is, a liquid distance rationalizable voting rule takes as input a pairwise delegation graph G and finds a closest graph G′ such that ˆR(G′ ) contains a consensus profile; the rule then outputs the consensus winner of this profile. 9

A natural distance function on G counts the number of swaps of internal pairs that are needed to transform one graph to another. The appeal of this distance function, denoted dint, has to do with delegations: If some voters delegate a pair ab to a voter i, and we swap voter i's internal pair ab, then this swap will be propagated-by pairwise delegations-to all voters having i as their ultimate ab-delegate. Thus, a single pairwise swap of an internal pair might lead to many swaps of that pair in other voters. It might therefore be possible to "reach" a consensus graph G′ by making only few internal swaps.

6.3 Liquid Voting Rules

An interesting example of a distance rationalizable liquid voting rule can be obtained by combining the distance function dint with the unanimous consensus class. We call the resulting liquid voting rule LiquidKemeny; it can be seen as an adaptation of Kemeny's rule to the pairwise liquid democracy setting. LiquidKemeny takes a pairwise delegation graph and, for every ranking r, computes the minimum number of pairwise swaps of internal pairs such that the resulting graph can be extended to a profile in which all preference relations are identical to r. The rule then selects the top-ranked alternative of the ranking r for which this number is smallest. That is, in this liquid variant of Kemeny's rule, we do not count all disagreements between a ranking and preference relations of voters, but rather only those disagreements between a ranking and the internal pairs of voters. Figure 4 illustrates this rule.

9 Since the output of a liquid distance rationalizable voting rule may depend on the structure of the pairwise delegation graph, such rules generally violate the one man-one vote property as discussed by [Christoff and Grossi, 2017].

There are other rules that can be distance rationalized with the swap distance [Elkind and Slinko, 2016]. For each such rule, we can immediately define their liquid version by generalizing the domain to the space of pairwise delegation graphs and replacing the swap distance with dint. For instance, this approach yields liquid versions of Dodgson's rule and Borda's rule. Whenever the delegation graph is empty, the liquid version of a rule coincides with the original version.

Remark 3. The distance function dint is based on the implicit assumption that the "cost" of swapping an internal pair of a voter does not depend on the number of other voters to which this swap will be propagated through delegations. This, however, violates the intuition that swapping pairs for voters with many delegations should be more costly than doing so for a voter who attracts only few delegations. Indeed, the appeal of pairwise liquid democracy is closely connected to the promise of effective utilization of expert knowledge, thus it can be argued that the preferences of voters attracting many delegations should be given increased attention. This argument can be accounted for by augmenting dint with a cost function cG : N × P → R+ that, with respect to a pairwise delegation graph G, assigns a cost for swapping each internal pair of each voter. Intuitively, a high value of cG(i, ab) means that the opinion of voter i on the pairwise comparison between a and b is valued highly. In fact, the rules we have considered can be recovered by defining the cost function appropriately: Let #d(i, ab) denote the number of voters that have voter i as their ultimate ab-delegate, and observe that setting cG(i, ab) = 1 corresponds to LiquidKemeny, while setting cG(i, ab) = #d(i, ab) corresponds to the standard version of Kemeny's rule. A middle ground could be based on cost functions that take the length of delegation paths (or other structural properties of G) into account. An interesting way to do that has been proposed by [Boldi et al., 2011].

7 Conclusion and Outlook

We proposed a generalized model of liquid democracy where voters can delegate pairwise comparisons, and explored approaches to deal with the possibility of intransitive preferences that might arise as a result of the increased flexibility that the model offers. We described a generalization of distance rationalization and suggested a framework for constructing "liquid voting rules" working directly on delegation graphs. Next we mention some directions for future research.

The most immediate direction is to study further liquid voting rules and their properties, e.g., by considering metrics on delegation graphs (including graph edit distances [Gao et al., 2010]), or by "liquidizing" other classes of voting rules (e.g., generalized scoring rules [Xia, 2013]).

Further, one could consider other generalizations of liquid democracy. A particularly interesting approach is "statement voting" [Zhang and Zhou, 2017], where voters can specify delegation rules (e.g., "I delegate to j unless j delegates further"), resulting in an even greater flexibility.

Acknowledgments

This material is based upon work supported by a Feodor Lynen research fellowship of the Alexander von Humboldt Foundation and by the Deutsche Forschungsgemeinschaft under grant BR 4744/2-1. We would like to thank the anonymous referees for valuable feedback.