# pairwise_liquid_democracy__809d9367.pdf

Pairwise Liquid Democracy

Markus Brill1 and Nimrod Talmon2

1 TU Berlin, Berlin, Germany 2 Ben-Gurion University, Be er Sheva, Israel brill@tu-berlin.de, talmonn@bgu.ac.il

In a liquid democracy, voters can either vote directly or delegate their vote to another voter of their choice. We consider ordinal elections, and study a model of liquid democracy in which voters specify partial orders and use several delegates to reﬁne them. This ﬂexibility, however, comes at a price, as individual rationality (in the form of transitive preferences) can no longer be guaranteed. We discuss ways to detect and overcome such complications. Based on the framework of distance rationalization, we introduce novel variants of voting rules that are tailored to the liquid democracy context.

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 who directly or indirectly delegated their vote to this voter. Liquid democracy has been popularized by the German Pirate Party, which was one of the ﬁrst organizations to employ the Liquid Feedback 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 ﬂexibility it offers to voters. In this paper, we aim to increase this ﬂexibility further by introducing the concept of pairwise liquid democracy. Speciﬁcally, 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 Liquid Feedback [Behrens et al., 2014, Chapter 14.12]. We propose that voters in an ordinal election can make use of delegations in a ﬁne-grained manner, by specifying a partial

order and then using several delegates to reﬁne 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 ﬂexibility voter v used in her delegations, and how v and v helped to reﬁne her initial partial order. This ﬂexibility 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 ﬂexibility, as might be suspected, comes at a price: Reﬁning 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. Speciﬁcally, 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 ﬂexibility it offers to participants. We argue that extending this ﬂexibility further, speciﬁcally by allowing pairwise delegations,

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

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

holds a signiﬁcant potential for advancing the liquid democracy paradigm.

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 scientiﬁc 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 [Green Armytage, 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 speciﬁc problems, and to come up with speciﬁc solutions, that might not manifest in the more general framework.

2 Preliminaries

Let N = {1, . . . , n} be a ﬁnite set of n voters and A = {a, b, c, . . .} a ﬁnite set of |A| = m alternatives. The preferences of voter i N are modeled as an asymmetric2 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

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

v2 : c b a bc ac

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 proﬁle is a list R = (R1, . . . , Rn) containing a preference relation Ri for every voter i N. A preference proﬁle R is complete (resp., transitive) if every preference relation in it is complete (respectively, transitive). A preference proﬁle R = (R 1, . . . , R n) is an extension of a preference proﬁle 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 speciﬁes 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.

3Internally speciﬁed preferences are assumed to be transitive. 4We usually assume that each voter speciﬁes 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 unspeciﬁed pairs can be arbitrarily set to either internal or external pairs without impacting the construction. A simple, general way of reducing an instance with unspeciﬁed pairs to one without such pairs is to add some additional, dummy voters: For each voter i containing at least one unspeciﬁed pair, add a voter i , initially with the same internal and external pairs as voter i, and add each unspeciﬁed pair of i as an external pair for both i and i , who delegate those pairs to each other. The modiﬁed instance preserves (weak) consistency (see Deﬁnitions 1 and 2).

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

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 m 2 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 proﬁle resulting from resolving all delegations. That is, for each voter i N and each external pair ab of i, we ﬁnd 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 deﬁned and, consequently, R(G) is not complete. A preference proﬁle 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 deﬁnition, R(G) respects G. Sometimes we are interested in complete and transitive preference proﬁles respecting G. The set of all such proﬁles is denoted by ˆR(G). Figure 1 illustrates that ˆR(G) may be empty. A necessary condition for a proﬁle 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 ﬁrst 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.

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

v3 : {a, c} b

v4 : {a, c} b v5 : b {a, c}

bc ac ac bc

Figure 2: A weakly consistent pairwise delegation graph that is not consistent. There are two ways to ﬁx the ac-cycle: either set a c for all voters involved in (or delegating to) the cycle, resulting in intransitive preferences for voter 2; or set c a for all these voters, resulting in intransitive preferences for voter 6.

For example, the pairwise delegation graph in Figure 1 violates weak consistency. Weak consistency can be checked efﬁciently: It is sufﬁcient to observe that, for each voter i N and for each pair ab Pext(i), the ultimate delegate delab(i) can be computed efﬁciently, e.g., using a depth ﬁrst 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 proﬁle 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. Deﬁnition 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 ﬁxed in a way that does not result in intransitive individual preferences. In particular, proﬁles 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 deﬁned); 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

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

c1: t1 f2; t2 t3; f3 f1 c2: f3 f4; t4 f5; t5 t3

x1 : x2 : x3 : x4 : x5 :

t1f1 t2f2 t3f3 t3f3 t4f4 t5f5

Figure 3: Example for the reduction described in the proof of Theorem 2, corresponding to φ = C1 C2, where C1 = x1 x2 x3 and C2 = x3 x4 x5.

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 satisﬁable. 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 unsatisﬁed, 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 ﬁnishes the reduction. An example is given in Figure 3. (Pairs not explicitly speciﬁed 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 satisﬁed.

Remark 1. There is an elegant SAT-formulation of the consistency problem. This is also of practical importance, as it allows the use of efﬁcient SAT solvers. For each vertex v and each pair ab, deﬁne 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 satisﬁable if and only if G is consistent; in this case, the variables encode a proﬁle 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 ﬂexibility of pairwise liquid democracy. It is therefore natural to consider restrictions to our general model, speciﬁcally tuning this ﬂexibility 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 m 2 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 ﬂexible 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 proﬁle. 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. Speciﬁcally, 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 modiﬁcation problem:

5This list is by no means exhaustive. For instance, [Christoff and Grossi, 2017] suggest to avoid inconsistencies by employing an opinion diffusion approach [De Groot, 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].

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

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 modiﬁcation problem can be deﬁned 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 modiﬁcation 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 deﬁned 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 modiﬁcation problem can be efﬁciently solved using Max SAT 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 Max SAT solution corresponds to a solution of the consistency modiﬁcation problem, with unsatisﬁed arc-clauses corresponding to deleted arcs.

5.3 Consolidating into Weak Rankings A further way to cope with intransitive voter preferences is to ﬁrst 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 complete6 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 deﬁnes 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

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

case for all pairwise voting rules (a voting rule is pairwise7 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. 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 proﬁle 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 proﬁles (a preference proﬁle 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 proﬁle, measuring closeness by the distance function. Formally, a distance function is a metric on preference relations8 and a consensus class C is a pair (R, W) where R is a set of preference proﬁles and W is a function mapping every R R to a winning alternative. The intuition is that the winner W(R) of a consensus proﬁle R R is obvious. A voting rule is (d, C)-distance rationalizable for distance d and consensus class C = (R, W) if, for every proﬁle R, the rule selects the winner W(R ) of the consensus proﬁle R R that is closest to R according to d. If several closest consensus proﬁles 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 proﬁles in which all preference relations are identical.

7Pairwise voting rules are also known as C2 functions [Fishburn, 1977] or weighted tournament solutions [Fischer et al., 2016]. 8That 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 proﬁles by letting d(R, R ) = P

i N d(Ri, R i).

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

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 proﬁles and deﬁnes 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( ) deﬁned in Section 3. Speciﬁcally, the distance function is deﬁned on G, whereas the consensus classes remain in the space of preference proﬁles. Applying function ˆR( ) allows us to transfer the notion of consensus to the graph space.

Deﬁnition 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 proﬁle R(G) can be extended to a consensus preference proﬁle. 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 deﬁne liquid distance rationalizability.

Deﬁnition 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 ﬁnds a closest graph G such that ˆR(G ) contains a consensus proﬁle; the rule then outputs the consensus winner of this proﬁle.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 Liquid Kemeny; it can be seen as an adaptation of Kemeny s rule to the pairwise liquid democracy setting. Liquid Kemeny 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

9Since 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].

v1 : a {b, c}

v2 : a {b, c}

v3 : a {b, c}

v4 : {b, c} a

v5 : {b, c} a

v6 : {b, c} a

v8 : c a b bc bc bc

Figure 4: A pairwise delegation graph G with 9 voters. Liquid Kemeny selects alternative c, because G can be turned into a consensus graph G via 8 pairwise swaps of internal pairs. The corresponding consensus proﬁle satisﬁes c i a i b for all i N. No other consensus graph can be reached with at most 8 pairwise internal swaps. (For comparison: Kemeny s rule, applied to the proﬁle R(G), selects winner a. The optimal ranking is a b c and 10 pairwise swaps are necessary to transform R(G) into a unanimous proﬁle.)

be extended to a proﬁle 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. There are other rules that can be distance rationalized with the swap distance [Elkind and Slinko, 2016]. For each such rule, we can immediately deﬁne 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 c G : 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 c G(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 deﬁning 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 c G(i, ab) = 1 corresponds to Liquid Kemeny, while setting c G(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].

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

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 ﬂexibility 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 ﬂexibility.

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.

[Behrens et al., 2014] J. Behrens, A. Kistner, A. Nitsche, and B. Swierczek. The Principles of Liquid Feedback. 2014.

[Behrens, 2017] J. Behrens. The origins of liquid democracy. The Liquid Democracy Journal, 5, 2017.

[Blum and Zuber, 2016] C. Blum and C. I. Zuber. Liquid democracy: Potentials, problems, and perspectives. Journal of Political Philosophy, 24(2):162 182, 2016.

[Boldi et al., 2011] P. Boldi, F. Bonchi, C. Castillo, and S. Vigna. Viscous democracy for social networks. Communications of the ACM, 54(6):129 137, 2011.

[Bouyssou, 2004] D. Bouyssou. Monotonicity of ranking by choosing : A progress report. Social Choice and Welfare, 23(2):249 273, 2004.

[Brandt et al., 2016] F. Brandt, M. Brill, and P. Harrenstein. Tournament solutions. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 3. Cambridge University Press, 2016.

[Brandt et al., 2018] F. Brandt, M. Brill, and P. Harrenstein. Extending tournament solutions. Social Choice and Welfare, 2018. Forthcoming.

[Brill et al., 2016] M. Brill, E. Elkind, U. Endriss, and U. Grandi. Pairwise diffusion of preference rankings in social networks. In Proceedings of the 25th International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 130 136, 2016.

[Christoff and Grossi, 2017] Z. Christoff and D. Grossi. Binary voting with delegable proxy: An analysis of liquid democracy. In Proceedings of the 16th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), pages 134 150, 2017.

[Cohensius et al., 2017] G. Cohensius, S. Mannor, R. Meir, E. Meirom, and A. Orda. Proxy voting for better outcomes. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 858 866, 2017. [De Groot, 1974] M. H. De Groot. Reaching a consensus. Journal of the American Statistical Association, 69(345):118 121, 1974. [Dodgson, 1884] C. L. Dodgson. The Principles of Parliamentary Representation. Harrison and Sons, 1884. [Elkind and Slinko, 2016] E. Elkind and A. Slinko. Rationalizations of voting rules. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 8. Cambridge University Press, 2016. [Fischer et al., 2016] F. Fischer, O. Hudry, and R. Niedermeier. Weighted tournament solutions. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 4. Cambridge University Press, 2016. [Fishburn, 1977] P. C. Fishburn. Condorcet social choice functions. SIAM Journal on Applied Mathematics, 33(3):469 489, 1977. [Ford, 2002] B. Ford. Delegative democracy. Unpublished manuscript. Available at http://www.brynosaurus. com/deleg/deleg.pdf, 2002. [Ford, 2014] B. Ford. Delegative democracy revisited. Blog post, 2014. [Gao et al., 2010] X. Gao, B. Xiao, D. Tao, and X. Li. A survey of graph edit distance. Pattern Analysis and applications, 13(1):113 129, 2010. [Green-Armytage, 2015] J. Green-Armytage. Direct voting and proxy voting. Constitutional Political Economy, 26(2):190 220, 2015. [Kahng et al., 2018] A. Kahng, S. Mackenzie, and A. D. Procaccia. Liquid democracy: An algorithmic perspective. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 1095 1102. AAAI Press, 2018. [Kemeny, 1959] J. G. Kemeny. Mathematics without numbers. Daedalus, 88:577 591, 1959. [Laslier, 1997] J.-F. Laslier. Tournament Solutions and Majority Voting. Springer-Verlag, 1997. [Miller, 1969] J. C. Miller. A program for direct and proxy voting in the legislative process. Public Choice, 7(1):107 113, 1969. [Xia, 2013] L. Xia. Generalized scoring rules: a framework that reconciles Borda and Condorcet. ACM SIGecom Exchanges, 12(1):42 48, 2013. [Yang, 2017] Y. Yang. Approval voting with intransitive preferences. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1769 1771, 2017. [Young and Levenglick, 1978] H. P. Young and A. Levenglick. A consistent extension of Condorcet s election principle. SIAM Journal on Applied Mathematics, 35(2):285 300, 1978. [Young, 1995] H. P. Young. Optimal voting rules. Journal of Economic Perspectives, 9(1):51 64, 1995. [Zhang and Zhou, 2017] B. Zhang and H. Zhou. Brief announcement: Statement voting and liquid democracy. In Proceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC), pages 359 361, 2017.

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