Anonymous and Copy-Robust Delegations for Liquid Democracy
Authors: Markus Utke
Ulrike Schmidt-Kraepelin
Venue: NeurIPS 2023 spotlight (2023)
Keywords: liquid democracy
directed trees
parameterized markov chain
matrix tree theorem
axiomatic method

Abstract: Liquid democracy with ranked delegations is a novel voting scheme that unites the practicability of representative democracy with the idealistic appeal of direct democracy: Every voter decides between casting their vote on a question at hand or delegating their voting weight to some other, trusted agent. Delegations are transitive, and since voters may end up in a delegation cycle, they are encouraged to indicate not only a single delegate, but a set of potential delegates and a ranking among them. Based on the delegation preferences of all voters, a delegation rule selects one representative per voter. Previous work has revealed a trade-off between two properties of delegation rules called anonymity and copy-robustness. 

To overcome this issue we study two fractional delegation rules: Mixed Borda branching, which generalizes a rule satisfying copy-robustness, and the random walk rule, which satisfies anonymity. Using the Markov chain tree theorem, we show that the two rules are in fact equivalent, and simultaneously satisfy generalized versions of the two properties. Combining the same theorem with Fulkerson's algorithm, we develop  a polynomial-time algorithm for computing the outcome of the studied delegation rule. This algorithm is of independent interest, having applications in semi-supervised learning and graph theory.

Anonymous and Copy-Robust Delegations for Liquid Democracy"
Markus Utke
Ulrike Schmidt-Kraepelin
Department of Mathematics and Computer Science TU Eindhoven
Simons Laufer Mathematical Sciences Institute (SLMath)
Eindhoven, The Netherlands m. utuuutuue..t
Berkeley, CA, United States
uschmidt@sllatti org
Abstract
Liquid democracy with ranked delegations a novel voting scheme that unites the practicability of representative democracy with the idealistic appeal of direct democracy: Every voter decides between casting their vote on a question at hand delegating their voting weight to some other, trusted agent. Delegations are transitive, and since voters may end up in a delegation cycle, they are encouraged indicate not only single delegate, but set of potential delegates and ranking among them. Based on the delegation preferences of all voters, a delegation rule selects one representative per voter. Previous work has revealed trade-off between two properties of delegation rules called anonymity and copy-robustness.
To overcome this issue study two fractional delegation rules: MIXED BORDA BRANCHING, which generalizes a rule satisfying copy copytrobus,,ess, and the RAN- DOM WALK RULEF, which satisfies anonymity. Using the Markov chain tree theorem, we show that the two rules are in fact equivalent, and simultaneously sat- isfy generalized versions of the two properties. Combining the same theorem with Fulkerson's 's algorithm, we develop polynomial-úme algorithm for computing the outcome of the studied delegation rule. This algorithm is of independent interest, having applications in semi-supervised learning and graph theory.
1 Introduction
Today, democratic decision-making in legislative bodies, parties, and non-profit organizations is often done via one of two extremes: In representative democracy, the constituents elect representatives who are responsible for deciding upon all upcoming issues for a period of several years. In direcr democracy, the voters may vote upon every issue themselves. While the latter distinguished by its idealistic character, it may suffer from low voter turnout as voters do not feel sufficiently informed. Liquid democracy aims to provide the best of both worlds by letting voters decide whether they want to cast their opinion on an issue at hand, or prefer to delegate their voting weight to some other, trusted voter. Delegations are transitive, i.e.. if voter 01 delegates to voter U2, and 02 in turn delegates to voter U3, who casts its vote, then U3 receives the voting weight of both 01 and V2. Liquid democracy has been implemented, for example, by political parties [Kling et al., 2015] and Google [Hardt and Lopes, 2015]. From a theoretic viewpoint, liquid democracy has been studied intensively by the social choice community the last decade [Paulin, 2020].
Earlier works on liquid democracy [Christoff and Grossi, 2017, Brill, 2018] have pointed towards the issue of delegation cycles, e.g., the situation that occurs when voter V3 in the above example decides to delegate to voter U1 instead of casting its vote. If this happens, none of the three voters reaches a
Part of this research was carried out while both authors were aftiliated with TU Berlin and Universidad de Chile, and Markus Utke was affiliated with University of Amsterdam.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

casting voter via chain of trusted delegations, and therefore their voting weight would be lost. In order to reduce the risk of the appearance of such so-called isolated voters, several scholars suggested to allow voters to indicate buck-up delegations [Brill, 2018, Gölz et al., 2021, Kavitha et al., 2022] that may be used in case there is no delegation chain using only top-choice delegations. liquid democracy with ranked delegations [Brill et al., 2022, Colley et al., 2022, Kavitha et al., 2022], voters are assumed to indicate a set of trusted delegates together with a ranking (preference order) among them. In fact, Brill et al. [2022] showed empirically that in many random graph models, one to two back-up delegations per voter suffice in order to avoid the existence of isolated voters almost entirely,
Allowing the voters to indicate multiple possible delegations calls for a principled way to decide between multiple possible delegation chains. For example, consider Figure 1: Should voter vi weight be assigned to casting voter $1, via U1 's second-ranked delegation, or should it rather be assigned to voter 82 by following 01 's first-ranked delegation to voter 12, and then following v2 second-ranked delegation? Brill et al. [2022] introduced the concept of delegation rules, which take as input a delegation graph (i.e., digraph with rank function on the edges) and output an assignment of each (non-isolated) delegating voter to a casting voter. In order to navigate within the space of delegation rules, they apply the axiomatic method [Thomson, 2001], as commonly used in social choice theory. In particular, the authors argue that the following three axioms are desirable:
(i) Confluence: A delegation rule selects one path from every delegating voter to a casting voter and these paths are "consistent" with one another. That is, when the path of voter o1 reaches some other delegating voter v2, the remaining subpath of 0n coincides with the path of 02. This was argued to increase accountability of delegates [Brill al., 2022, Gölz et al., 2021].
(ii) Anonymity: A delegation rule should make decisions solely the structure of the graph, not on the identities of the voters, i.c. it should be invariant under renaming of the voters.
(iii) Copy-robustren
If a delegating voter v1 decides to cast her vote herself instead of delegat- ing, this should not change the sum of the voting weight assigned to dj 's representative and herself. This property was emphasized by practitioners [Behrens and Swierezek, 2015] to avoid manipulations in the system by delegating voters acting as casting voters but actually copying the vote of their former representative.
Figure I:
Example of a delegation graph. Delegating voters (U1 and U2) are indicated by circles and casting voters (81 and sy) by squares. Solid edges represent the first-ranked delegations and dashed edges second-ranked delegations.
For any pair of axioms (i) to (iii,, Brill et al. [2022] provide delegation rule that satisfics both of them. In contrast, we prove in Section 7 that there exists no delegation rule that satisfies all three properties simultaneously, thereby strengthening
impossibility result by Brill et al. [2022].
Our Contribution
We show that the above impossibility is due to the restriction that delegation rules may not distribute the voting weight of delegating voter more than one casting voter.
We generalize the definition of delegation rules to fractional delegation rules (Section 3) and provide generalizations of all three axioms above (Section 7).
We introduce natural variant of the BORDA BRANCHING rule [Brill al., 2022], which we call MIXED BORDA BRANCHING. We show that this rule is equivalent to the RANDOM WALK RULE, fractional delegation rule that has been suggested by Brill [2018].
In our main result, we build upon Fulkerson's ''s algorithm [Fulkerson, 1974] and the Markov chain tree theorem [Leighton and Rivest, 1986] and show the existence of a polynomial algorithm for MIXED BORDA BRANCHING. This algorithm is of independent interest, as it computes the probability of two nodes being connected, when sampling a min-cost branching in digraph uniformly random. This problem features in semi-super learning, under the name directed power watershed [Fita Sanmartin et al., 2021], a directed
2 Brill et al. [2022] show that there exists no delegation rule belonging to the subclass of sequence rules that both confluent and copy-robust. Any sequence rule is in particular anonymous.

---

variant of the power watershed [Couprie et al., 2010]. To the best of our knowledge, we provide the first efficient algorithm.
In Section 7, we show that the RANDOM WALK RULE (and thus MIXED BORDA BRANCH-- ING) satisfies the generalizations of all three axioms. We also formalize the impossibility for non-fractional delegation rules. Beyond that, we show that the RANDOM WALK RULE satisfies a generalization of further axiom (guru participation) which has been studied in the literature [Kotsialou and Riley, 2020, Colley et al., 2022, Brill et al., 2022] (Appendix C).
The proofs (or their completions) for results marked by (**) can be found in the appendix.
Related Work Liquid democracy. The idea to let agents rank potential delegates in liquid democracy was first presented by the developers of the liquid democracy platform Liquid Feedback [Behrens and Swierczek, 2015], who presented seven properties that cannot be satisfied Itnultaneuusly. Some of these properties, such as copy-robuse robustness and guru participation, have been picked up in the social choice literature [Kotsialou and Riley, 2020, Brill et al., 2022, Colley et al., 2022]. The connection of confluent delegation rules to branchings in a digraph was first emphasized by Kavitha et al. [2022] and later built upon in [Brill et al., 2022, Natsui and Takazawa, 2022]. We base our model on [Brill et al., 2022], as their model captures all rules and axioms from the literature. Fractional delegations were studied by Degrave [2014] and Bersetche [2022], however, here agents indicate desired distribution among their delegates instead of ranking. While the two approaches are orthogonal, we argue in Appendix B that they could be easily combined (and our algorithm could be adjusted).
Branchings and matrix free theorems. Our algorithm for computing MIXED BORDA BRANCIINGG is based on an algorithm for computing min-cost branchings in directed trees. This can be done, e.g.. via Edmond's 's algorithm [Edmonds, 1967] or Fulkerson's 's algorithm [Fulkerson, 1974]. The latter comes with a characterization of min-cost branchings in terms of dual certificates, which we utilize in Algorithm 2. We refer to Kamiyama [2014] for comprehensive overview on the literature of min-cost branchings. Our algorithm makes use of (a directed version of) the matrix tree theorem [Tutte, 1948], which allows to count directed trees in a digraph. An extension of this theorem is the Markov chain tree theorem [Leighton and Rivest, 1986], which we use for the construction of our algorithm as well as for proving the equivalence of MIXED BORDA BRANCHING and the RANDOM WALK RULE A comprehensive overview of the literature is given by Pitman and Tang [2018].
Semi-supervised learning. There is connection of our setting to graph-based semi-supervised learning. In particular, Algorithm 2 is related to the power watershed algorithm [Couprie et al., 2010] and the probabilistic watershed algorithm [Fita Sammartin et al., 2019, 2021]. We elaborate on this connection in Section 4.
2 Preliminaries
The main mathematical concepts used in this paper are directed graphs (also called digraphs), branchings, in-trees, and Markov chains, all of which we briefly introduce below. We assume that a digraph G has no parallel edges, and denote by VG) the set of nodes and by E(G) the of edges of G. We use (c) to indicate the set of outgoing edges of node VGG). i.e., (v) = {(v, u) F(G)). (U) {(u, E(G) u U, v E (G) \ UJ. A walk W is a node sequence (Wi...., (,,,,WWw) Www)). such that (W,, W 11) E E(G for E (1,.... [W| - 1}. We omit G if it is clear from the context.
J. For set of nodes U C V()), we define the outgoing cut of U by
Branchings and in-trees. Given digraph G, we say that B C E is a branching (or forest)) in G, if B is acyelic, and the out-degree of any node v E VG) in B is at most one, i.c., |B n 8 (v) < 1. Throughout the paper, we use the term branching to refer to maximum-cardiinlle branchings B maximizing [B] among all branchings in G. For given digraph G we define B(G) as the set of all (max marxinardinaltty) branchings and (G) as the set of all (max-cardinalitt) branchings in which node u E VGG) has a path to the node s E (G). For any branching B in any digraph G holds that |B| < [VG) - 1. If in fact [B] [V(G]] - 1, then B is also called an in-tree. For every in-tree T C E, there exists exactly one node u E ( without outgoing edge. In this case, we also say that v the sink of T and call T v-tree. For e E V(G), we let (G) be the set of v-trees in G.
branchings, ie..
Matrix tree theorem. For our main result we need to count the number of in-trees in a weighted digraph, which can be done with help of the matrix tree theorem. For digraph G with weight
3

---

function w : E + N, we define the weight of subgraph T S E as w(T) = IeeT w(e) and the weight of a collection of subgraphs T as w(T) = -TETWWle w()). Then, we define the Laplacian matrix of (G, w) as L = D A, where D is a diagonal matrix containing the weighted out-degree of any node v in the corresponding entry De,e and A is the weighted adjacency matrix, given as Au, = w(u,, v)) for any edge (u,,)) F and zero everywhere else. Moreover, we denote by I(v) the matrix resulting from L when deleting the row and column corresponding to v.
Lemma 1 (Matrix tree theorem [Tutte, 1948, De Leenheer, 2020]² ). Let (G, w) be weighted digraph and let L be its Laplacian matrix. Then,
der(T. II v<(e) wTT))
TET
If we interpret the weight of an edge as its multiplicity in a multigraph, then det(L(()) equals the total number of distinct v-trees.
Markoy Chains. A Markov chain is a tuple PG. where G is a digraph and the matrix P e [o. 1] VIxIVI encodes the transition probabilities. That is, the entry Pu,o indicates the probability with which the Markov chain moves from state to state in one timestep. For a given edge
e = (u, v) E E, we also write Pe to refer to Pu.v- For all v E V it holds that Eeest(v) P. = 1. Moreover, if (u,v). & E, we assume Pa.e- O. We define the matrix Q E [0, 1] as Q lim Ei PT. If (G, P) is an absorbing Markov chain, Qu corresponds to the probability for random walk starting in u to end in absorbing state v. In contrast, if G is strongly connected and P is positive for all edges in G, then Qu.v corresponds the relative number of times v is visited in an infinite random walk independent of the starting state [Grinstead and Snell, 1997].
3 Liquid Democracy with Fractional Delegations
A delegation graph G US, F)) is a digraph with cost function' c: F. N (called rank function before), representing the preferences of the voters over their potential delegates (lower numbers are preferred). Nodes correspond to voters and an edge (u, v) E E indicates that u accepts v as a delegate. By convention, the set of nodes S corresponds exactly to the sinks of the digraph, i.c. the set of nodes without outgoing edges. Thus, S captures the casting voters, and N the delegating voters. We assume for all v E N that they reach some element in S. A delegation rule maps any delegation graph to a fractional assignment, i.e., a matrix A [0, 1] 1 where, for every e E N, E S. the entry Au.e indicates the fraction of delegating voter v's weight that is allocated to casting voter s E S.6 For any E N we refer to any casting voter E S with Av,s 0 as representative of v. For assignment A, the voting weight of casting voter S is defined as (A) = 1+ EVEN Ag,s. A non-fractional delegation rule is special case of a delegation rule, that always returns assignments A E {0, 1).
The output of any -raffraciional, confluent delegation rule can be represented as branching: Any branching in the delegation graph consists of [N edges, and every delegating voter has a unique path to some casting voter. Brill al. [2022] suggested to select min- cost branchings, i.e., those minimizing Eee c(e). The authors call these objects Borda branchings and show that selecting them yields a copy-robust rule. As this rule inherently non-anonymous, we suggest to mix uniformly over all Borda branchings, hoping to gain anonymity without losing the other properties?. Formally, for given delegation graph c), let B² be the set of all Borda branchings and let B (G) be the set of all Borda branchings in which delegating voter E N is connected to casting voter & E S. MIXED BORDA BRANCHING returns the assignment defined as
MIXED BORDA BRANCHING.
A 1B. (B)
for all u E V.
'Tutte [1948] proves the theorem for digraphs, the weighted version can be found in [De Leenheer, 2020].
*We remark that in this paper cost functions and weight functions play different roles.
'If' this is not the case, such voter is isolated. i.e., there is no chain of trusted delegations to a casting voter. thus we cannot meaningfully assign its voting weight. We remove isolated nodes in preprocessing step. sensible delegation rule, this should only
'While this definition allows A > for any u E N, s E S. be the case if there exists a path from e to s. Confluence (detined in Section 7) implies this restriction.
Confluence and copy ropustobuss not directly inherited from the non- non-fractiona counterpart of the rule.

---

RANDOM WALK RULE. The second delegation rule was suggested in Brill [2018] and attributed to Vincent Conitzer. For any given delegation graph (G, and fixed E E (0, 1], we define a Markov chain on G, where the transition probability matrix p(f) E [0, 1]V(C)xV(() is defined as
co(u,e) for any (u, E E,
p(e) UFE
Eu
where E. = -((u))es+t E (X(U,)) is the natural normalization factor. The Markov chain (G, p(e)) is absorbing for every E E (0, 1] where the absorbing states are exactly S. The RANDOM WALK RULE returns the fractional assignment A defined as the limit of the absorbing probabilities, i.e.,
lim 1 T-000
E(Pooy))..
Au,a
lim
for all U E N
3,a
1=0
4 Connection to Semi-Supervised Learning
In graph-based semi-supervised learning, the input is directed or undirected graph, where nodes correspond to data points and edges correspond to relationships between these. A subset of the nodes is labeled and their labels are used to classify unlabeled data. Many algorithms compute fractional assignment of unlabeled data points towards labeled data points, which is then used to determine the predictions for unlabeled data. In the directed case, there exists one-to-one correspondence to our model: Delegating voters correspond to unlabeled data and casting voters correspond to labeled data.
Power Watershed. In the undirected case, the power watershed [Couprie et al., 2010] can be interpreted as an undirected analog of MIXED BORDA BRANCHING: For any pair of unlabeled data point and labeled data point y. the algorithm computes the fraction of min-cost undirected maximum forests that connect x to y. The authors provide a polynomial-ting outcome. On high level, our algorithm (Section 5) is reminiscent of theirs, i.e., both algorithms iteratively contract parts of the graph, leading to a hierarchy of subsets of the nodes. However, while the algorithm by Couprie et al. [2010] only needs to carry out computations at the upper level of the hierarchy, our algorithm has to carry out computations at each level of the hierarchy. We believe that the increased complexity of our algorithm is inherent to our problem and do not find this surprising: Even the classic min-cost spanning tree problem can be solved by a greedy algorithm and forms a Matroid, but this structure gets lost when moving to its directed variant.
algorithm for computing its
Directed Probabilistic Watershed. Fita Sanmartin et al. [2021] study a directed version of graph-based semi-supervised learning. The authors introduce the directed probabilistic watershed (DProbWS): Similar to our model, there exists a cost function e and a weight function w on the edges. In their case, these functions are linked by w(e) exp(-uu(ee). The paper studies a Gibbs distribution with respect to the weights, i.e., the probability of sampling a branching is proportional to its weight. The parameter controls the entropy of this function, i.e., for μ O, any branching is sampled with equal probability, while larger 1l places more probability on low cost branchings. The authors show: (i) For fixed μr, the fractional allocation induced by the Gibbs distribution can be computed by calculating the absorbing probabilities of a Markov chain. (ii) For the limit case + so, the defined distribution equals the uniform distribution over all min-cost branchings, i.c., the distribution that we study in this paper. In this limit case, the authors refer to the corresponding solution the directed power watershed. Hence, the authors have shown the equivalence of the directed power watershed and the limit of a parameterized Markov chain. Since this Markov chain only slightly differs from ours, this result is very close to our Theorem 5. As its proof very short and might be of interest for the reader, we still present it in Section 6. Importantly, Fita Sanmartin al. [2021] do not show how compute the outcome of the directed power watershed. In particular, the algorithm from (i) makes explicit use of the weight function on the edges (which depends on μ). Hence, the running time of the algorithm grows infinity in the limit case. We fill this gap by providing the (to the best of our knowledge) first polynomial-ting time algorithm for the directed power watershed. Maybe surprisingly. we need a significantly more complex approach solve the limit case: While the algorithm of Fita Sanmartin et al. [2021] solves one absorbing Markov chain, our algorithm derives hierarchical structure of subsets of the nodes by the structural insights provided by Fulkerson's 's algorithm, and solves several Markov chains for each of the hierarchy.
'This analogy holds for the variant of the power watershed when a parameter g 2 [Couprie al., 2010).
5

---

5 Computation of MIXED BORDA BRANCHING
Our algorithm for computing the outcome of MIXED BORDA BRANCHING is an extension of an algorithm by Fulkerson [1974] for computing an arbitrary min-cost branchings in digraph. The algorithm by Fulkerson follows a primal-dual approach and can be divided into two phases, where the first phase characterizes min-cost branchings with the help of family of subsets of the nodes, and the second phase then constructs one arbitrary min-cost branching. Building upon the first phase, show that, for every two nodes v E N and s E S, branchings that connect the two nodes by applying an extension of the matrix tree theorem [Tuttee 1948, De Leenheer, 2020] and the Markov chain tree theorem [Leighton and Rivest, 1986].
count the number of min-cost
Fulkerson's algorithm." The algorithm (described formally in Algorithm 1) maintains a function 2NUS - N and subset of the edges Ey C E. The set Ey captures edges that are right (w.r.t. y). i.e., those E satisfying
Σ
v(X) = c(e).
XCNUSieE6-
The algorithm takes as input delegation graph G together with cost function c: E + N.
Algorithm 1 Fulkerson's 's Algorithm [Fulkerson, 1974, Kamiyama, 2014]
1: Set x(x) = 0 for any set X N S except y v({s}) = 1 for any E S, E,= =0
2: while some node in N cannot reach any node in S in the graph (N US, E, do
3: let X C .N be strongly connected component in (N U Eg) with 8 (X) = 0
4: set y(X) to minimum value such that some edge in 8+ (X) tight, add tight edges Ey
5: F
[X [ NICNUP USIIII x(X) > 0}
6: return (F, Ey
Since c(e) 2 for all E. the output F contains all singleton sets induced by nodes in N U S. and beyond that subsets of N. In the following we show several structural insights that are crucial for the construction of our algorithm. While statements (ii) and (iii) have been proven in similar forms by Fulkerson [1974], we prove all of Lemma 2 in Appendix A for completeness.
Lemma 2 (+)) Let (G,c) be a delegation graph and let (F, Eyg y) be the output of Algorithm 1. Then:
(i) For every (G. c). the ouiput of the algorithm is unique, ie., it does not depend on the choice of the strongly connected component in line 3.
(ii) F is laminar, i.e., for any X,Y F it holds that either X KYY, Y X, X = 0.
(iii) Branching B in (G,c) is min-cost iff (a) B C Ey, and (b) BB n (x)(())) = 1 for all
X E F, N.
(iv) For every X E F, an in-tree T in G[X] EIJ), where E| = ((u E E u X), is min-cost iff (a) T S Ey. and (b) IT 2on++ (V) = for all E F such that Y C X.
Intuition and notation for Algorithm 2. For our algorithm, the crucial statements in Lemma 2 are (ii) and (iii. First, because F. forms a laminar family, there exists natural tree-like structure among the sets. We say that set F is a child of a set X F, i C X and there does not exist Z F, such that Y c Z C X. Moreover, for some X E F or X = N U S, we define Gx = (Vx, Ex) as the tight subgraph that restricted the node set X and contracts all children of X. Formally, Vx = [Y] Y is a child of } and Ex {(Y,
(u, r) E E,, E Y, E Y', and Y,Y' e )x}. In the following we first focus on the graph corresponding to the uppermost layer of the hierarchy, i.e., Gx for X = N U.S. Now, statement (iii) implies that every min-cost branching B in G leaves every child of X exactly once and only uses tight edges. Hence, if we project B to an edge set Ó in the contracted graph Gx. then B forms a branching in Gx. However, there may exist many min-cost branchings in G that map to the same branching in Gx. The crucial insight is that we can construct a weight function wx the edges of Gx, such that the weighted number of branchings in Gx equals the number of min-cost branchings in G. This function is constructed by calculating for every child
We slightly adjust the algorithm, as Fulkerson [1974] studies directed out- trees and assumes sink only.

---

2
U2
3
2
Y1
Y2
1a
(xi (Tr (Gx,) wxi (7y, (Gx,))
X1
Y1
2
(a) delegation graph (G, c) restricted the set XI.
(b) Digraph Gx, with edge weights wx,, Based on this imput, for E (1, 2), we calculate the total weight of all Y-trees in Gx i... wxx (Tr; (Gx,))
Nodes o E Yi are labeled with yy; (v) and nodes in E Y2 are labeled with (v). Recall, that by; (v) is the total number of min-cost v-trees in G[Yi].
3
12
X1
X2
+
X3
2
13
X
{
{82}
(c) graph (G, c) restricted Xi. Every node E
(d) example for (Gx, wx), where N.S. S. In the last iteration, this graph is translated into a Markov chain and the absorbing probabilities are returned.
X₃ is labeled with fx, (v), which was calculated by multiplying the weights from Figure 2a with the results from Figure 2h.
Figure 2: Two iterations of Algorithm 2. Costs are depicted by edge patterns (solid equals cost 1, dashed equals cost 2, and dotted equals cost 3) and weights are depicted by numbers on the edges.
Y of X and every node E Y. the number of min-coss v-trees inside the graph G[Y] (Y, E where E[Y] = ((u,v) E E' u, YJ. This number, denoted by (u)) can be computed by recursively applying the matrix tree theorem. Coming back to the graph Gx however, we need more powerful tool since we need compute the (relative) number of weighted branchings in Gx connecting any node to sink node. Thus, we introduce the Markov chain tree theorem (in slightly modified version so that it can deal with Markov chains induced by weighted digraphs).
For weighted digraph (G, w) we define the corresponding Markov chain (G', P) as follows: The digraph G' is derived from G by adding self-loops, and for (u, v) E(G") let
w(u,v)
+
P
Eessticy w(e)
if u
where A = maxvev Eee8 (u) w(e).
Lemma (Markov chain tree theorem (Leighton and Rivest (1986))). Consider weighted digraph (G, w) and the corresponding Markov chain (G', P) and let lim, -500 Pr. Then, the entries of the matrix Q are given by
Qu, EBEB IL Pe
EmeB,,. Ieen w(e) EneB,,. w(B) EBEB ILEB w(e) EBEB w(B)
LBEB
We formalize Algorithm 2, which takes as input a delegation graph (G, c) and, in contrast to the intuition above, works in a bottom-up fashion. We refer to Figure for an illustration.
Theorem ).). Algorithm 2 returns MIXED BORDA BRANCHING and runs in poly(n).
Proof sketch. The main part of the proof, shows by induction over the laminar hierarchy of F. that for every X F and E X, the value xx (v) equals the number of min-cost e-trees in G[X]. Given that this is true, one can show that w (By,(-) (Gx)) equals the number of min-cost branchings in G that connect any node in v Y to the sink s and that wx (B(Gx)) equals the number of all min-cost branchings in G. Hence,
utilize the Markov chain tree theorem on the graph G to compute

---

Algorithm 2 Computation of MIXED BORDA BRANCHING
1: compute (F, Ey. 1), set F' = [N S) and label its elements "unprocessed" Algorithm
2: ((v)(1) t- for all E UUS, label singletons as "processed"
3: do pick unprocessed X E F' for which all children are processed, label as "processed"
4: set wx (Y,Y") + Σ (u.))E ((Xxx) by (u), for all children Y and Y' of X
5: if N U then
6: for all children Y of do tx(x) wx (T ty (t) for all e Y else compute absorbing probability matrix Q for the Markov chain corresponding to (Gx,
7:
Lemma 1
8:
Lemma
9:
while + N US
10:
return for all v E N and s E S: Au,a + QY..[st, where Y, child of N U with E Y,
the outcome of MIXED BORDA BRANCHING.
As for the running time, the main observation is that the computation the number of branchings in a weighted digraph can be done in time logarithmic in the highest weight of an edge (and polynomial the number of edges). Since all of our weights are bounded by the maximum number of branchings in the original graph (which is bounded by IN)I)))), we can show the polynomial running time.
6 Equivalence of MIXED BORDA BRANCHING and RANDOM WALK RULE
With the help of the Markov chain tree theorem, as stated in Section 5, we can show the equivalence of the RANDOM WALK RULE and MIXED BORDA BRANCHING.
Theorem 5. Let (G, c) be a delegation graph and A and Å be the assignments returned by MIXED BORDA BRANCHING and the RANDOM WALK RULE, respectively. Then, A Å.
Proof. Let N and S, then,
EBEB., IEEB p!l)) lim
ela.e) EBEB.,, Ia
00
A lim E(ploly)) -00
= =lim 6-0
Eu
ΣBEB llen p(l)
5-00
EBes I( Eu
galu.s)
INEN (Ex) EBEB... co(B) 6--0
EBEB:
=lim
Au,o-
[ EBEB
ΣBEB.
We first use the definition of the RANDOM WALK RULE, and then apply the Markov chain tree theorem (Lemmaa 3) for fixed & E (0, 1] to obtain the second equality. For the third equality, we use the definition of p(e), and then factor out the normalization factor e. for every u E N. For doing so, is important note that for every V E N and s S, every branching in B.,, and every branching in B contains exactly one outgoing edge per node in N. We also remind the reader that c(B)= EeeB c(e). Finally, we resolve the limit in the fifth equality by noting that the dominant parts of the polynomials are those corresponding to min-cost (BORDA) branchings.
Given Theorem 5, we can interpret Algorithm 2 as algorithm computing limit absorbing probabili- ties of a class of parametric Markov chains. We explain this reinterpretation in Appendix B.
7 Axiomatic Analysis
In this section, we generalize and formalize the axioms mentioned in Section and show that the RANDOM WALK RULE (and hence MIXED BORDA BRANCHING) satisfies all of them. In particular, our version of confluence (copy-robustness, respectively) reduces to (is stronger than, respectively) the corresponding axiom for the ornftracionaal case by Brill et al. [2022] (see Appendix C.1). We first define anonymity, which prescribes that delegation rule should not make decisions based on the identity of the voters. Given digraph with cost function (G, c) and a bijection o VVG) V()), we define the graph ((GG c)) as
where V(G') = VGG), F((G) ((a(u),(()) (u, e
E(G)) and c' (d(a (v)) c(u, v) for each edge (u, E E(G).
8

---

Anonymity: For any delegation graph (G, c), any bijection o V(G) + V(G), and any v E N. E S, it holds that Au,. = A ((s)) where A and A' are the outputs of the delegation rule for (G,c) and ((G c)), respectively.
Theorem (*)) The RANDOM WALK RULE satisfies anonymity.
We now define copy-robustness, which intuitively demands that if a delegating voter E N decides to cast their vote instead, the total voting weight of v and all its representatives should not change. This lowers the threat of manipulation by a voter deciding whether to cast or delegate their vote depending on which gives them and their representatives more total voting weight. This axiom was introduced (under a different name) by Behrens and Swierezek [2015] and defined for non-fractional delegation rules in [Brill et al., 2022]. We strengthen 10 and generalize the version of Brill et al. [2022].
ropy-robustness: For every delegation graph (G, c) and delegating voter N, the following holds: Let (G,e) .)) be the graph derived from (G, e) by removing all outgoing edges of u, let A and Á be the output of the delegation rule for (G, c) and (G, c), respectively and let S. = {s E $ Au,s > 0} be the set of representatives of in (G, c). Then E.es, T. (A)= = == (A) + EsEs, (A))).
Theorem 7 (+)) The RANDOM WALK RULE satisfies copy-robustmess.
Proof sketch. We show a statement that is slightly stronger than the condition for copy-robustness. Namely, the voting weight of every casting voter from S \ S,, remains equal when v changes from being delegating voter to becoming a casting voter. Let (Gx, wx), with X N U S, be the contracted graph constructed in Algorithm for c). Analogously, let (Gx, x (xx be the contracted graph constructed for (G, c). In order to argue about their relation, we first show: If y and 9 are the functions returned by Algorithm 1 for G and G. respectively, then j(Y) = y(Y) for every set Y C 2/ not containing e, (((u)) = 1, and j(Y) = 0 for all other sets containing v. Now, let Y, be the node in Gx containing and let L/ C V xGx) be the subset of nodes in Gx that are not reachable from Y.. We argue that for any E S \ Se. the Markov chain induced by (Gx wx) can only reach {s} from a starting node in U. However, for all nodes in 44 all of their walks to any {s}, s E S \ S. are still existent in the graph (Gx, @xx. and still have the same weight. Hence, the voting weight of any E SS) S, remains unchanged when moving from G to G.
To capture the requirement that the voting weight of different voters is assigned to casting voters in a "consistent" way, Brill et al. [2022] define confluence as follows: delegation rule selects, for every voter u E N, one walk in the delegation graph starting in and ending in some sink E S, and assigns voter u to casting voter 8. A delegation rule satisfics confluence, if, as soon as the walk of u meets some other voter v, the remaining subwalk of equals the walk of v." Below, we provide a natural generalization of the property by allowing a delegation rule to specify a probability distribution over walks. Then, conditioned on the fact that the realized walk of some voter u meets voter v, the probability that u reaches some sink s E S should equal the probability that u reaches s.
For every delegation graph (G,c), there exists probability distribution fu for all v E N over the set of walks in that start in e and end in some sink, which is consistent with the assignment A of the delegation rule (i.e., Pw [s E W) Av,s for all E N, E 5), and,
Confluence:
Pw~suls E W| U E W = Pw~s. [s E W] for all u. E S.
Note that the requirement that Au..- = =P [s E W] implies that for any v E V and s E S we can have A > O only if there is a path from to in G.
Theorem 8 (*)) The RANDOM WALK RULE satisfies conftuence.
Proof sketch. One can verify that every delegation rule that can be formalized via a Markov chain on the delegation graph (G, e) satisfies confluence. In Section 5, we showed that the RANDOM WALK RULE can be computed by solving a Markov chain (Gx, P) on the contracted graph Gx (for X N U S). We utilize (Gx. P) to define probability distribution over walks in G that satisfies confluence: Every walk in G can be mapped to a walk in Gx (by ignoring edges inside children of X), but there may exist many walks in G that map to the same walk in Gx. We pick, for every walk
Brill et al. [2022] restrict the condition to voters that have a direct connection to their representative. Brill et al. [2022] assume paths instead of walks. The two definitions are equivalent (see Appendix C.I).
9

---

(G1,c:):
63
(G3, ea):
21
C2);
Figure 3: Situation in the proof of Theorem 9. Solid edges correspond to first-choice delegations, dashed edges to second-choice delegations.
W in Gx, one representative walk W in G and give it the same probability as W in (Gx; P). All other walks in G get zero probability. When picking the representative walks, we can ensure that for every two nodes u, V NUS, the probability that the walk of u reaches e equals the probability that Y, reaches Y, in [Gx, P). where Y, and Y, are the nodes in V (Gx) containing u and v, respectively. For the constructed probability distribution, we then show that the confluence condition is met. D
With the formal definition of confluence, anonymity, and copy-robustness we can now show that these properties altogether are impossible to achieve in the non-fractional case. Recall, that a non-fractional delegation rule defined as a delegation rule, that returns assignments A E {0, 1
Theorem 9. No non-fractional delegation rule satisfies confluence, anonymity, and ropyrrobustness.
Proof. Consider the graph cI) in Figure 3. There are four non-fractional assignments in (GI,ci); Both U₁ and U2 can either be assigned U3 or U4. Suppose a rule chooses assignment A with Avi.ea Ag2,s 1. This rule cannot satisfy confluence, as any walk from Uy 03 includes 21 and confluence requires 1 = Avz,e, = Fw [t's E W] = Pw [U' E W 21 E W] PW- [V3 E W]= = Api.es = O. Now, suppose a delegation rule chooses assignment A with A Apg,z 1. We define the bijection mapping V1 to 122 02 to 01, By to 1/ and 84 to v3-- (G and thus A',,'² A'22.0 = 1 in the assignment A' that the rule chooses for o((G), c)). This contradicts anonymity, since 1 = Av,.e * A' Ao(r)).((s))
Then, o (GG,,))
Ale O. We can make the same argument in the case of Ae, Aog. 24 = 1. For any rule satisfying anonymity and confluence the chosen assignment A must therefore have Au1, = AAg..4 = 1.
The above arguments are independent of the cost function so long we have c(V1, 02) c(U2, v1) and c(v1, Us) = c(v2, va). needed for the equality of o(( c)) and (G1,c). Thus, any rule satisfying anonymity and confluence must choose the assignment A with Ar,,o Avg.v, = 1 for (G2, o2). We modify (G1. c1) ) by making U/2 a casting voter (as in the definition of copy-robustness) and retrieve (G3, 03). Copy robustness requires that the assignment from e to 14 in G2 (which is zero) must be the same as the sum of assignments from e1 to 14 and V2. Thus, we have Au = 1 for the assignment A, that any confluent, anonymous, and copy-robust rule chooses for (G3, However, construct (G3, 0a) from (G2, 02) by making i3 casting voter. Then, analogously, copy-robustness requires A 1 for the assignment of (G3, leading contradiction.
also
Since the RANDOM WALK RULE (and thus MIXED BORDA BRANCHING) satisfies generalizations of the three axioms, the above impossibility is due to its restriction to non-fractional rules.
8 Concluding Remarks
We generalized the setting of liquid democracy with ranked delegations to allow for fractional delegation rules. Beyond that, we presented delegation rule that can be computed in polynomial time and satisfies number of desirable properties. A natural follow-up question is to understand the entire space of delegation rules satisfying these properties.
Fractional delegations have been recently implemented (see electric. vote) and studied by Degrave [2014] and Bersetche [2022]. In contrast to our setting, these approaches let agents declare a desired distribution over their delegates (instead of rankings). We remark that one could easily combine the two approaches by letting agents declare their desired split within each equivalence class of their ranking. Our algorithm can be extended for this setting (see Appendix B).
There exists a line of research which aims to understand liquid democracy from an epistemic viewpoint (Kahng et al., 2021, Caragiannis and Micha, 2019, Halpern et al., 2023]. Here, many of the negative results stem from the fact that voting weight is concentrated on few casting voters. Since, intuitively, ranked delegations can help to distribute the voting weight more evenly, would be interesting to study these through the epistemic lense
10

---

Acknowledgements
This work was supported by the Deutsche Forschungsgemeeinschhfff (under grant BR 4744/2-1), the Centro de Modelamiento Matemátiico (CMM) (under grant FB210005, BASAL funds for center of excellence from ANID-Chile), ANID-Chile (grant ACT210005), and the Dutch Research Council (NWO) (project number 639.023.81 VICI "Collective Information"), Moreover, this work was supported by the National Science Foundation under Grant No. Sloan Foundation under grant 22021-16778, while Ulrike Schmidt- Kraepelin was in residence at the Simons Laufer Mathematical Sciences Institute (formerly MSRI) Berkeley, California, during the Fall 2023 semester.
and by the Alfred P.
We would like to thank Markus Brill for suggesting the setting to us as well insightful discussions. Moreover, we thank Jannik Matuschke for helpful discussions on min-cost branchings. Also, we thank our colleagues from Universidad de Chile, Martin Lackner, and Théo Delemazure for their valuable feedback.
References
J. Behrens and B. Swierczek. Preferential delegation and the problem of negative voting weight. The Liquid Democracy Journal, 3:6-34, 2015.
F. Bersetche. A Voting Power Measure for Liquid Democracy with Multiple Delegation. Technical report, arXiv: 2209. 14128 [cs.MA], 2022.
M. Brill. Interactive democracy. In Proceedings of the 17th International Conference on Autoromous Agents and Multiagent Systems (AAMAS) Blue Sky Ideas track, pages 1183-1187. IFAAMAS, 2018.
M. Brill, T. Delemazure, A.-M. George, M. Lackner, and U. Schmidt-Kraepele Liquid democracy with ranked delegations. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 4884 4891. AAAI Press, 2022.
I. Caragiannis and E. Micha. A contribution to the critique of liquid democracy. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 1 116-122. ICCAI, 2019.
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.
R. Colley, U. Grandi, and A. Novaro. Unravelling multi-agent ranked delegations. Autonomous Agents and Multi-Agent Systems, 36(1):1-35, 2022.
C. Couprie, L. Grady, L. Najman, and H. Talbot. Power watershed: unifying graph-based optimization framework. IEEE transactions on pattern analysis and machine intelligence, 33(7): 2010.
De Leenheer. An Elementary Proof of a Matrix Tree Theorem for Directed Graphs. SIAM Review, 62(3):7 2020.
Degrave. Resolving multi-proxy transitive vote delegation. Technical report, arXiv: 1412.4039 [cs.MA], 2014.
J. Edmonds. Optimum branchings. Journal of Research of the National Bureau of Standards, 71(4): 233-240, 1967.
E. Fita Sanmartin, S. Damrich, and F. A. Hamprecht. Probabilistic Watershed: Sampling all spanning forests for seeded segmentation and semiisupervised learning. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
E. Fita Sanmartin, S. Damrich, and F. A. Hamprecht. Directed probabilistic watershed. In Advances in Neural Information Processing Systems (NeurIPS), pages 20076-20088 2021.
11

---

D. R. Fulkerson. Packing rooted directed cuts in weighted directed graph. Mathematical Program- ming, 6(1):1-13, 1974.
Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 2013, ISBN 978-1-107-03903-2.
P. Gölz, A. Kahng, S. Mackenzie, and A. D. Procaccia. The fluid mechanics of liquid democracy. ACM Transactions on Economics and Computation, 944::1-39, 2021.
C. M. Grinstead and J. L.. Snell. Introduction to Probability. American Mathematical Society, second edition, 1997.
E. M. Hahn, H. Hermanns, and L. Zhang. Probabilistic reachability for parametric Markov models. International Journal on Software Tools for Technology Transfer, 13(1):3-19, 2011.
D. Halpem, J. Halpern, A. Jadbabaie, E. Mossel, A. Procaccia, and M. Revel. In defense of liquid democracy. In Proceedings of the 24th ACM Conference on Economics and Computation (ACM- EC), 2023. Forthcoming.
S. Hardt and L. Lopes. Google votes: A liquid democracy experiment corporate social network. Technical report, Technical Disclosure Commons, 2015.
J. E. Hopcroft, J. D. Ullman, and A. V. Aho. Data structures and algorithms, volume 175. Addison- wesley Boston, 1983.
A. Kahng. Mackenzie, and A. D. Procaccia. Liquid democracy: An algorithmic perspective. Journal of Artificial Intelligence Research, 70:1223-1252, 2021.
N. Kamiyama. Arborescence problems in directed graphs: Theorems and algorithms. Interdisciplinary information sciences, 20(1):51-70, 2014.
T. Kavitha, T. Király, J. Matuschke, I. Schlotter, and U. Schmidt- Kraepelin. Schmidt-Kraepelin. Popular branchings and their dual certificates. Mathematical Programming, 192(1):223 221-222,,3222 2022.
C. Kling, Kunegis, H. Hartmann, M. Strohmeier, and S. Staab. Voting behaviour and power in online democracy: A study of liquidfeedback in germany's ' pirate party. In International Conference on Weblogs and Social Media, pages 208-217, 2015.
G. Kotsialou and Riley. Incentivising participation in liquid democracy with breadth first delegation. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 638 644. IFAAMAS, 2020.
Leighton and R. Rivest. Estimating a probability using finite memory. IEEE Transactions on Information Theory, 32(6):733-742, 1986.
K. Natsui and K. Takazawa. Finding popular branchings in weight- digraphs. In Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM), pages 303-314. Springer, 2022.
A. Paulin. Ten years liquid democracy research an overview. Central and Eastern European eDem and eGov Days, 2020.
J. Pitman and W. Tang. Tree formulas, mean first passage times and Kemeny's constant of a Markov chain. Bernoulli, 24(3):1942-1922. 2018
W. Thomson. On the axiomatic method and its recent applications to game theory and resource allocation. Social Choice and Welfare, 18(2):327-386, 2001.
W. Tutte. The dissection of equilateral triangles into equilateral triangles. 44(4):463-482 1948.
12

---

Appendix
A
Missing Proofs of Section 5
Lemma 2 (*)) Let (G,c) be a delegation graph and let Ey, be the output of Algorithm 1.
Then:
(i) For every (G. the output of the algorithm is unique, i.e., it does not depend on the choice of the strongly connected component in line 3.
(ii) F is laminar, i.e,, for any X,Y Y E F holds that either X C.Y, Y C X, or xny=0 0.
(iii) Branching B in (G,c) is min-cost iff (a) B S Bug and (b) B n (X)) = 1 for all REF,XÇI N.
(iv) For every X F, an in-tree T in G[X] E[X), where E|x] ((u,v) E E u X}, is min-cost iff (a) T C Ey. and (b) [T (n8+(() = for all Y E F such that Y c X.
Proof. Let (G,c) c) be a delegation graph and let Ey. be the output of Algorithm 1.
We start by proving statement (ii). The sets in F correspond exactly to those sets with positive y-value. Assume for contradiction that there exist two sets X, Y E with X Y o and none of the subsets is a subset of the other. Assume without loss of generality that X was selected before Y by the algorithm and let 1/1 and 1/2 be the status of the function y in each of the two situation. Then, by construction of the algorithm it holds that G1 (N U.S. E, is subgraph of G2 (N U S, E This is because once an edge is added to the set of tight edges (denoted by Ey) it remains this set. Since Y is strongly connected component in G2 without outgoing edge, it holds that for every 2 E X \ Y and 2' E XY, the node 2' does not reach in G2. However, this is a contradiction to the fact that X is strongly connected component in the graph G1, which concludes the proof of statement (ii).
We now turn to prove statement (i) and already assume that F is laminar. We fix an order of the selected strongly connected components line 3 of the algorithm. Then, suppose that for some other
choices in line 3, the algorithm returns some other output (F, Eg, 1). Note that F & F or Eg + E, implies that ò * y. Thus, it suffices assume for contradiction that ÿ + y. Then there must be smallest set X, that has y(X) # ((X) (without loss of generality we assume y(X) > ((X)). ). Let X' = x {X} } be the set of all strict subsets of X. Since defined X to be of minimal cardinality, we have y X') = ÿ (²) where y [x), and ý X denote the restriction of and ÿ to X, respectively. Because x(X
0, all children of X are strongly connected by tight edges with respect to y [ and have no tight edges pointing outside of X. Now, consider the iteration of the alternative run of the Algorithm 2, in which the algorithm added the last set in X' U (X). Since j(X) y(X), for every further iteration of the algorithm, a chosen set X' * X cannot contain any node in X (because otherwise X' cannot form strongly connected component without outgoing edge). However, since the nodes in X cannot reach a sink via tight edges, this is a contradiction to the termination of the algorithm.
We now prove statement (iii. The plan of attack is the following: First we define a linear program that captures the min-cost branchings in delegation graph. Second, we dualize the linear program and show that y (more precisely a minor variant of y) is an optimal solution to the dual IP, and third, utilize complementary slackness prove the claim. For given delegation graph (G,e) with VGG) = N U 5 we define the following linear program, also denoted by (L.P):
min
c(e)xF
Σ
Ie 2
VXCN
cEO+(X)
20
de E
13

---

We claim that every branching B in G induces a feasible solution to (LP). More precisely, given branching B, let
[1 = 0
e B if B.
Ze
The last constraint is trivially satisfied. Now, assume for contradiction that there exists X C N such that the corresponding constraint in (LP) is violated. In this case the nodes in X have no path towards some sink node in B, a contradiction to the fact that B is a (maximum cardinality) branching. In particular, this implies that the objective value of (LP) is at most the minimum cost of any branching in G (in fact the two values are equal, but we do not need to prove this at this point). We continue by deriving the dual of (LP), to which we refer to as (DLP):
max Σ 9X
XCN
Σ (X))
yx S c(e)
VEEE
yx 2 20
V
Now, let y be the function returned by Algorithm 1. We define J. which is intuitively restricted to all subsets on N, more precisely, (Xx) = yX) for all X S N. We claim that ý is feasible solution to (DLP). This can be easily shown by induction. More precisely, we fix any e E E and show that the corresponding constraint in (DLP) is satisfied throughout the execution of the algorithm. At the beginning of the algorithm y (and hence 2) is clearly feasible for (DLP). Now, consider any step in the algorithm and let be the selected strongly connected component. If e E 8+ (X), then we know that the constraint corresponding to is not tight (since X has no tight edge in its outgoing cut). Moreover, y is only increased up to the point that some edge in 8 (X) becomes tight (and not higher than that). Hence, after this round, the constraint for is still satisfied. If, on the other hand, e & 8+(x (X), then the left-hand-side of e's constraint remains equal when y (X) is increased. Hence, the constraint of e is still satisfied.
Next, we claim that there exists a branching B in G, such that for the resulting primal solution x, it holds that EeeF c(e)xte Xx The branching B will be constructed in a top-down fashion by moving along the laminar hierarchy of F. To this end let Gy be the contracted graph as defined in Algorithm 2. We start by setting X = U S. Since every node in N can reach some sink via tight edges, we also know that every node in Gx can reach some sink. Hence, branching in Gx has exactly one edge per node in Vx that not a sink. Let's pick such a branching Bx. We know that for every edge in Bx= (Y, 2) there exists some edge in the original graph G that is also tight, i.e., u E Y and v E Z such that (u, v) E Ey. For every edge in Bx pick an arbitrary such edge and add it to B. Now, pick arbitrary node Y VG By construction, we know that exactly one edge from B is included in (Y)) call this edge (u, v). Then, within the graph Gy, there exists exactly one node Z E V(GY), that contains We going search for Z-tree within Gy. We know that such a tree exists since Gy is strongly connected by construction. We follow the pattern from before, i.., finding Z-tree, mapping the edges back to the original graph (arbitrarily), and then continuing recursively. For proving our claim, it remains to show that Eee c(e)a.. = ExeN ((X). The crucial observation is that, by construction. every set in F = =F((ss |SE S) is left by exactly one edge in B. Hence, we can partition the set fF into sets UEEB Pec where Fe = {x E $ leE 8+ (X)). Moreover, observe that every edge in B is tight. As result we get that
Σ cee) CE
Σ Σ
x(x)
Σ i(X), XCN
CEB XEF.
proving the claim.
As a result, note that we found a primal solution B (precisely, the x induced by B). and a dual solution 9 having the same objective value. By weak duality, we can conclude that both solutions are in particular optimal. It only remains to apply complementary slackness to conclude the claim. To this end, let B be min-cost branching and x be the induced primal solution. By the argument above we know that x is optimal. Now, for any X S N for which ((X) > O (hence X E F), complementary slackness prescribes that the corresponding primal constraint is tight, i.e., Exc Te 1. Hence, the branching corresponding leaves the set X exactly once, and part (b) of statement (iii) is
14

---

satisfied. For statement (a) we apply complementary slackness in the other direction. That is, when Te > 0, this implies that the corresponding dual constraint is tight. implying that e has to be tight with respect to y and therefore also with respect to y (recall that y and y only differ with respect to the sink nodes).
We now turn to proving statement (iv). This is done almost analogously to statement (iii). Fix X F. In the following we argue about the min-cost in-trees in G[X] and how to characterize these via a linear program. To this end, we add a dummy sink node r to the graph G[X] and call the resulting graph G. More precisely, G = (X U (r), U
| u X)). The cost of any edge
ru, u E X is set to c" == max,eE(ca c(e) + 1, where it only important that this value is larger than any other cost in the graph. We define the following LP:
min
c(e)xe
eEB(G)
Σ eE6 (2)
Ie 21
XZVA
Te 20 0
Ve E E(G)
For every min-cost in-tree T in G[X] obtain feasible solution to (LP). To this end, let E X be the sink node of T and define π' T' {(u, r)). Then, translate 7 to its incidence vector œ. Given this observation, we again derive the dual of (LP), to which we refer to as (DLP):
max Σ
yZ
ZCX
Σ
yz S c(c)
EEE E(G)
ZCX)
_ Now, let y be the output of Algorithm for the original graph G. We derive ÿ 22 - IR as follows:
yz 2 0
0(Z) = y (Z)
if 2 X if 2 X
max
Ezex| (Z))
First, analogously to (iii), it can be verified that ý is feasible solution to (DLP). Moreover, again analogously (iii), there exists some min-cost r-tree in G and corresponding primal solution æ, such that E() c(e)x.. = Σzex 0x (This tree is derived by first chosing a tight edge towards the dummy root node and then again recurse over the laminar family F restricted to X.) This implies by weak duality that ý is an optimal solution to (DLP) and any min-cost r-tree in G is an optimal solution to (LP). As result, we can again apply complementary slackness in both directions: Let T be a min-cost in- tretree in G[X] with sink node u E X. Then let 7 TU {u, r)) the corresponding min-cost r-tree in G and x be the corresponding incidence vector. Then, complementary slackness implies that for any E F [[X] for which x. 0 (and hence E T)) it holds that the corresponding constraint in (DLP) is tight with respect to ÿ (and also y). This implies that e E Ey. On the other hand, for any Z X, if ûz > O, and hence X F, complementary slackness prescribes that the corresponding primal constraint is tight, and hence [T' ( 6 (2) = 1, concluding the proof. D
For the proof of the next theorem, we first explain how to compute the absorbing probabilities of an absorbing Markov chain P) and show related lemma that need in Appendix C. W.l.o.g. we assume that the states (G) are ordered such that the non-absorbing states N come first and the absorbing states S last. We can then write the transition matrix
D
C [is
P =
where is the N X |N| transition matrix from non-absorbing states to non-absorbing states and C. is the N |S| transition matrix from non-absorbing states absorbing states. I[s] denotes the |S| |S| identity matrix. The absorbing probability of an absorbing state E S, when starting random walk in state E N is then given as the entry in the row corresponding to v and the column corresponding to in the [|| x [S] matrix [4
D)- [Grinstead and Snell, 1997].
15

---

Lemma A.1. Adding self-loop to non non-absorbing state with probability p and scaling all other transition probabilities from that state by 1 p does not change the absorbing probabilities of an absorbing Markov-chain (G.
Proof. Let (D, C) and (D'
) be the transition matrices of the absorbing Markov chain before and after adding the self-loop. Let d,, d' Cu, cy be the rows of D, D', C, C", corresponding to state respectively. Then
d' = (1 - p)d, + pe?
c = (1 - p)c,
and d' du and c/ ct. for all #
We want to show that (4 - DC = (N - D')- Let Z = (4 - D. Then Z = (INN) - D''--'" C" if and only if Z = D'Z + C". Notice, that only the row corresponding to v in D' and C' differ from D and C' and therefore for all u +
d. + C.2 = d' Z c
where zu is the row of Z corresponding to u. The only thing left show is z, = d' + cy. We have
d.Z + c. = ((1 - p)d,, + pe.) 2 + (1 p)c, (1 p)d, + pe? + (1 p)c, = (1 pp)dd + cc,) + pe?
(1 p)z, + pzh
(since + CC+C= 2)
2
which concludes the proof.
Theorem 4 (*)) Algorithm 2 returns MIXED BORDA BRANCHING and runs in poly(n).
Proof. We start by showing by induction that the given interpretation of the weight function on the nodes is correct, i.e., for any V E N, tx (v) corresponds to the number of min-cost v-trees in the graph G[X]. The claim is clearly true for any singleton, since t(u (v) 1 and the number of v-trees in (Lv), 0) is one, i.e., the empty set is the only w-trees. Now, we fix some X F' and assume that the claim is true for all children of X. In the following, we fix v e X and argue that the induction hypothesis implies that the claim holds for x (v) as well.
For any node u E X, let Y. E F be the child of X containing node u. Moreover, let T (G[X]) (or short T,") be the set of min-cost v-trees in G[X]. and Ty, (Gx) (or short Ty.) be the set of Y,- trete in Gx. Lastly, for any E X, let T (G[Y.l) be the set of min-cost u-trees in G[Y In the following, we argue that there exists a many-to-on in Lemma 2, every min-cost in-tree T in G[X] (hence, T E TT)) leaves every child of X exactly once via a tight edge. Therefore, there exists a natural mapping to an element of Ty, by mapping every edge in T that connects two children of X to their corresponding edge in Gx. More precisely, T = ((Y,Y') E Ex | (Y) n (Y') + 0} is an Y.-tree in Gx and hence an element of Ty,,
mapping from T to Ty.. Note that, by statement (iv)
Next, we want to understand how many elements of T map to the same element in Ty,- Fix any I E Ty., We can construct elements of T, by combining (an extended version of) I with min-cost in-trees within the children of X, i..., with elements of the sets T (G[Yu]), E X. More precisely, for any edge (Y, Y') T, can independently chose any of the edges in (u, u') E Ey n (Y x Y") and combine it with any min-cost u-tree in the graph G[Y]. This leads to
II (Y (L,)"))
Σ E
by (v( br, (v) = ( III wx((Y by, (r. (v)
(YYYET
many different clements from To that map to T E Ty. Hence,
IT'I= = Σ II wy (v,YY)) by (v) = wx (v) = Lx(u),
TETY, (YYYET
where the last inequality follows from the definition of 1x(x) (v) in the algorithm. This proves the induction step, i.c., tx (x) corresponds to the number of min-cost v-trees in the graph G[X).
16

---

Now, let X = N, i.e. we are in the last iteration of the algorithm. Due to an analogous reasoning as before, there is a many-to-one mapping from the min-cost branchings in G to branchings in Gx. More precisely, for every branching B E Bo) (Gx), there exist
II (YYY)
wx "x Y") x (B)
branchings in G' that map to B. Hence, by the Markov chain tree theorem (Lemma 3), we get
Au,s = Qu, = (BEB).a)((x)) (x( EBEB;
EBEB(EX) wx Wx(BB EBEBI(G))
where xG'x P) is the Markov chain corresponding to Gx and Q = lim 1 + Pr. This equals the definition of MIXED BORDA BRANCHING.
Lastly, we argue about the running time of the algorithm. For a given delegation graph (G, c). let V(G), i.e., the number of voters. Algorithm can be implemented in O( That is because, the while loop runs for On) iterations (the laminar set family F can have at most 2n - 1 elements), and finding all strongly connected components in a graph can be done in (nn²) (e.g.. with Kosaraju's algorithm [Hopcroft et al., 1983]). Coming back to the running time of Algorithm 2, we note that the do- do-while loop runs for (nn) iterations, again, due the size of F. In line 7, the algorithm computes (n) times the number of weighted spanning trees with the help of Lemma 1 (Tutte [1948]). Hence, the task reduced to calculating the determinant of submatrix of the laplacian matrix. Computing an integer determinant can be done in polynomial time in n and log (M). if M an upper bound of all absolute values of the matrix 12, Note, that all values in every Laplacian (the out-degrees on the diagonals and the multiplicities in the other entries) as well as the results of the computation are apper-boundee by the total number of branchings in the original graph G (this follows from our argumentation about the interpretation of I (v) in the proof of Theorem 4), hence in particular by n". Therefore, the running time of each iteration of the do-while loop is polynomial in n. In the final step we compute the absorbing probabilities of the (scaled down version) of the weighted graph (Gx, wx) (where X = N U U.. For that, we need to compute the inverse of (n) x (n) matrix, which can be done using the determinant and the adjugate of the matrix. Computing these comes down to computing (n²) determinants, for which we argued before that it is possible in polynomial time Summarizing, this gives running time of Algorithm I in ((T log(n) + n² log(n log(n))) (log" (Iog(n 1))).)))))).
B Further Remarks on Section 6
Alternative Interpretation of Algorithm 2 We stated Algorithm 2 in terms of counting min-cost branchings. There exists a second natural interpretation that closer to the definition of the RANDOM WALK RULE, in which we want to compute the limit of the absorbing probabilities of a parametric Markov chain. We give some intuition on this reinterpretation of the algorithm with the example in Figure 2, and later extend this interpretation to a larger class of parametric Markov chains.
Intuitively speaking. every set X E F in the Markov chain (G, p(e)) corresponding to the delegation graph G is a strongly connected component whose outgoing edges have infinitely lower probability than the edges inside of X as E approaches zero. We are therefore interested in the behavior of an infinite random walk in G[X]. While in the branching interpretation, the node weight tx (1) can be interpreted as the number of min-cost u-arborescences in G[X], in the Markov chain interpretation think of (u) as an indicator of the relative time an infinite random walk spends in v (or the relative number of times v is visited) in the Markov chain given by the strongly connected graph G[X]. Consider the example iteration depicted in Figure 2a, where are given unprocessed X E F whose children Y1, Y2 are all processed. When contracting Y, and Y/ the weights on the edges should encode how likely a transition is from one set to another, which is achieved by summing over the relative time spent in each node with corresponding edge. We then translate the resulting
More precisely. it can be computed in O(n" ( log(nM) +n (ngM))))))))))) (log" n- (log log M)) [Gathen and Gerhard. 2013]
We argued this only for integer matrices, but we can transform the rational matrix into an integer one by scaling it up by factor which is bounded by n²"
17

---

graph (Figure 2b) into a Markov chain and again compute the relative time spend in each node. This computation is equivalent see Theorem 3). Indeed, we get a ratio of one to three for the time spend in Y1 and Y2. To compute ix (v) we multiply the known weight Ly, (v) by the newly calculated weight of p. In the example
calculating the sum of weights of all in-trees (up a scaling factor,
this means that since we know, we spend three times as much time in Y2 as in Y1 all weights of nodes in Y/ should be multiplied by three (see Figure 2c).
Extension of Algorithm 2 In addition, we remark that our algorithm could be extended to larger class of parametrie Markov chains, namely, all Markov chains (G, P(e)), where G is a graph in which every node has a path to some sink node, and, for every e E F(G), p!() is some rational fe(e) where both fe and ge are polynomials in & with positive coefficients. 14 fraction in i.e., (e))) Now, we can construct a cost function e on G, by setting c(e) Zee Ze + 1, where Tee is the smallest exponent in (s) and is the smallest exponent in ge (e). Note that, if c(e) < 1. then the Markov chain cannot be well defined for all E (0, 1]. Now, we run Algorithm 2 for the delegation graph (G, c) with the only one difference, i.e., the weight function wx also has to incorporate the coefficients of the polynomials fE) and ge()). More precisely, we define for every e E E, the number 9e as the ratio between the coefficient corresponding to the smallest exponent in fe and the coefficient corresponding to the smallest exponent in ge. Then, we redefine line 4 in the algorithm to be
w (Y,Y)
E
(u) K(,w)-
One can then verify with the same techniques in Section 5 and Section 6, that this algorithm returns the outcome of the above defined class of Markov chains.
C Missing Proofs and Further Results of Section 7
Theorem 6 (*). The RANDOM WALK RULE satisfies anonymity.
Proof. Given a delegation graph (G, c) and a bijection a : VVG) - V(G), we know that for
all v V(G) it holds that [ (v) 1 (a())) and c(v, w) = c' (o((v) for any edge (v, w) E (+)( where (G) a (G) In the corresponding Markov chains M, and M' we therefore get (v,w) = P'le)
(o()),((w)) (see Equation 1). Since through the bijection between the edges of the graph, we also get a bijection between all walks in the graph W and for every a E S and walk in W[s, v) there is corresponding walk in ([a(v), (s)) of the same probability. Therefore have
p(e)
Ap,s = lim
Σ
II
p(c) = lim
Σ
II pM(c) = Al Ao(())((s)
6-10
c0
WEW
(e) eeW
which concludes the proof.
Theorem 7 (+)) The RANDOM WALK RULE satisfies copy-robustness.
Proof. Let (G,c), v, (G,c), A. Á and S, be defined as in the definition of copy-robustness. Let (F.y) and (F, () be the set families and functions returned by Algorithm for G and é, respectively, In this proof, we restrict our view to the subgraphs of only tight edges, denoted by Gy = (N U.S Ey) and G.g (N) \ {v) UV U (v), Eg). respectively. Note, that this does not change the result of the RANDOM WALK RULE, since it is shown to be equal to MIXED BORDA BRANCHING, which only considers tight edges (in the contracted graph) itself.
First, we observe that the set S, is exactly the subset of S reachable by u in Gy- This is because the assignment A returned by the RANDOM WALK RULE is given as the absorbing probability of a Markov chain on the graph (Gx, wx) with X = N U S, computed by Algorithm 2. The graph is constructed from G, by number of contractions, which do not alter reachability, i.e. for E S the node {+} is reachable from the node Y, containing Gy. Since all edge weights xx are strictly positive, in the corresponding Markov chain all transition
Gx exactly if s is reachable from v in
"Thi class is reminiscent of class of parametric Markov chains studied by Hahn et al. [2011].
18

---

probabilities on the edges of Gx are strictly positive as well. This gives {s} strictly positive absorbing probability when starting a random walk in Y, exactly if s is reachable from u in Gy.
Our next observation is that f = F\ (Y E F o TOEEYUUUNN ((o)) (((v)) = 1 and y(Y) - (YY for all Y E FV {(u]]. Consider the computation of F in Algorithm 1. Since the output is unique (see Lemma 2 statement (i)), we can assume without loss of generality that after initializing F, all sets in {Y E F v & Y are added F first and then the remaining sets {Y E F | E Y.. In G the only edges missing are the outgoing edges from v, therefore, when applying Algorithm 1 to G all sets in {Y E F v & } can be added to f first (with ((Y) - yY)).. Note, that the set {v) with v((*} = was added to F in the initialization. We claim, that the algorithm terminates at that point. Suppose not, then there must be another strongly connected component X C N with 5+ (X) n Fig = (1. I E X then since u has no outgoing edges X = {v), which is already in F. & X then X would have already been added.
With these two observations, we can show the following claim: For every casting voter 8 E S S, the voting weight remains equal, when v turns into a casting voter, i.e., T. (A) = TT(A) Fix E S \ S, and let U C N be the set of nodes not reachable from in Gy- We know that f == (Y E F v E YY (v). which implies that for every node u E U the sets containing u are equal in F and F. i.e., (Y E F u Y) = (Y E F u YY). Therefore, the outgoing edges from any u E U are equal in Gg and Gg.. Since F S F, the edges in Gy are a subset of the edges in Gy and therefore the set U is not reachable from in Gg. When translating Gg into the Markov chain (Gg, ple)) (see Equation 1), we get for the probability of any tight out-edge e of and any > O. that p! p( where p(e) is the transition matrix induced by the original graph Gy. In the following we argue about the set of walks in Gg and Gg. To this end we define for every u E N, the set W(u, s] (Wju, s). respectively) as the set of walks in Gy (in Gg. respectively) that start in u and end in sink s. Since all walks from any u E U to contain only outgoing edges from nodes in U, we have W(,,s) s] = W(u, s). For any other voter w E N \ U we have WWw, s] = W(ur, s] = 0 and therefore
T. (A)
1+
Σ lim E
II
P(e)
p(e) =1
Σ NEt
lim
Σ
II
ple) - (A)
+00
We
WEWJu.e]eEW NEW
which concludes the proof of the claim.
Summarizing, we know that that for any casting voter E S So we have T. (A) =A),,, which directly implies that Exes, (A( = (A) + Exes, Ts (A)...
Theorem 8 (+)) The RANDOM WALK RULE satisfies conftuence.
Proof. Before proving the claim, we introduce notation. For any walk W in some graph G, and some node E (G), we define W[u to be the subwalk of W that starts at the first occasion of in W. For two nodes u, E VG), we define WIu, u] to be the subwalk of W that starts at the first occasion of and ends at the first occasion of v. (Note that W [v] and W [u, e] might be empty.) Now, for a set of walks W and u, v. 8 E V(G), we define Wly] { [v] W E W) and W(u. u] [W[,, v] W E W) Lastly, we define W(T., v2, s] = ( E W[ s] v E W W[,,)); We usually interpret a walk W as a sequence of nodes. In order to facilitate notation, we abuse notation and write V E W for some node E V(G) in order to indicate that u appears in W, and for an edge e E (GG), we write e E W to indicate that tail and head of e appear consecutively in W.
For the remainder of the proof we fix W to be the set of walks in the input delegation graph G starting in some node from N and ending in some sink node S. Moreover, let Gx be the graph at the end of Algorithm 2, i.e., Gx for X = N U.S. S. We fix W to be the set of walks which start in some node of Gx and end in some sink node of Gx (which are exactly the nodes in ({x) | E S)).
In the following, we define for every V E N probability distribution fo W[u] [0, 1]. such that witnesses the fact that the RANDOM WALK RULE is confluent. To this end, we define a mapping T+ W|Y1 + Wiu,, where Y. is the node in Gx that contains U. Given a walk W E WYY), we construct 7. (W) E WTo as follows: Let W = (1) .... (A), By construction of Gx we know that for every E {1...., k), the fact that (Y()), ((+1)) E Ex implies that there exists (6(0, a((+)) E with (()) e (0) and ((++)) ((+1), Moreover, we detine (1))) = v and ((n) s.
19

---

where {s} = (()) Under this construction it holds that al), b(0) E y() for all E {1,.... k), but the two nodes may differ. Therefore, we insert subwalks W connecting a to b(0) by using only nodes in (())) and visiting each of these nodes at least once. The final walk (W) is then defined by (a(1) W b(.)...,, a(m), W(n), ((m)). We remark that this mapping is injective, and it holds that W visits some node Y V(Gx) if and only if you (W) visits all nodes in Y.
Recall that the assignment A of the RANDOM WALK RULE can be computed via Markov chain (Gx, P) derived from the contracted graph (Gx, wx) (see Section and Section 6). where G'x is derived from Gx by adding self-loops. In Lemma A. we show that introducing (and thus removing) self-loops to states in absorbing Markov chain does not change its absorbing probabilities. We retrieve the Markov chain (Gx, P) by removing all self loops of all voters in N and rescaling the other probabilities accordingly. We then make use of this Markov chain in order to define fu over Wfu]. That is, for any W E W[u] let
(e(W) [[Leew P. if there exists W W[Y) such that 7o (W)) W
else.
Note that, the above expression is well defined since Tou is injective.
In the remainder of the proof, we show that f. witnesses the confluence of the RANDOM WALK RULE, First, show that fo is indeed consistent with the assignment A returned by RANDOM WALK RULE. That is, for any E N and s E S it holds that
ES =
E WEW[O.a]
fo(W)= = Σ II P. - Av,s
The second equality comes from the fact that % is injective and exactly those walks in W[Y,, {s} are mapped by To to walks in Wiu, s). Moreover, all walks in WfE, s] that have no preimage in W(Y., [*}] are vero-valued by f.- The last equality comes from the fact that A equals the probability that the Markov chain (G'x P) (equivalently, (Gx, P)) reaches {5} if started in Y, (see Section 5 and Section 6).
We now turn the second condition on the family of probability distributions fu, v N. That is, for
every u, V E N, 8 E S it holds that
Pw-s,lu W ASE
Σ
fa(W)=
Σ
II
P.
Σ
II
P.)(
II
P.)
WeW.Y.....o) eet
cEW[Y..(a]]
Σ
II
(c).(
IPp)
WeW Kil NeW
W+ neW
E
Σ
II:))
Σ
II)
E'E Y.. NEW
WeW (+)] New
Σ Σ
fa(W)
S.(W))
EE WeW
WEWLo.d
= Pw [V E W1. PP W].
The second equality follows from the same reason as above, i.e., Yo is injective, exactly those walks in W/Y., Yu, {s}] are mapped by % walks in W(u, v, s). and all walks in Wfu, v, s] that have no preimage in W[Y,, Y., {s}] are zero-valued by f.. The third inequality holds by the fact that every walk that is considered in the sum can be partitioned into W(..,, Y.] and [+]]. The fourth equality follows from factoring out by the subwalks. The fifth equality follows from the fact that every walk in W reaches some sink node eventually, and therefore, the additional factor in the first bracket sums up to one. Lastly, the sixth equality follows from the very same argument as before.
From the above equation we get in particular that for every U E N, E S it holds that
PW (s E W 1 W] Pw W AVAE W
Pw is E W].
PW E W]
20

---

This concludes the proof.
The next axiom was in its essence first introduced by Behrens and Swierczek [2015] and first given the name gurt-participation in Kotsialou and Riley [2020]. The idea is that a representative (the guru) of voter, should not be worse off if said voter abstains from the vote. Brill et al. [2022] define this property for non-fractional ranked delegations by requiring that any casting voter that was not representative of the newly abstaining voter should not loose voting weight. This definition translates well into the setting of fractional delegations where we can have multiple representatives per voter. For simplicity, we made slight modification the definition resulting in a slightly stronger axiom.
Previously, we stated the general assumption that every delegating voter in delegation graph (G, c) has a path to some casting voter in G. In this section we modify given delegation graphs by removing nodes edges, which may result in an invalid delegation graph not satisfying this assumption. To prevent this, we implicitly assume that after modifying a delegation graph, all nodes in N not connected any sink in S (we call them isolated) are removed from the graph.
Guru Participation: A delegation rule satisfies puru-participation if the following holds for every instance (G, e): Let (G, e) be the instance derived from (G,c) by removing a node e E -N (and all newly isolated nodes), let S, {s E S A.. > 0} be the set of representatives of v and let A and À be the assignments returned by the delegation rule for (G, and (G, c), respectively. Then
T (A) 2 (A)
Ss E SYS.
In particular, this implies
Σ SES.
(A) + S Σ (A(
HES.
In order to prove that the RANDOM WALK RULEE satisfies guru-participation we first show the following lemma, saying that the voting weight of no casting voter decreases, when the in-edges of another casting voter are removed from the graph.
Lemma C.1. For the RANDOM WALK RULE, removing the incoming edges of some casting voter E S (and all newly isolated voters) does not decrease the absolute voting weight of any casting voter s' ESS {s}.
Proof. Let (G, c) be delegation graph and s E S a sink. Let (G,c) be the delegation graph, where the in-edges of and all voters disconnected from casting voters are removed. Let p()) and p(e) be the transition matrices of the corresponding Markov chains Mj and M,. Then, for any E >> 0 and edge e in G we have p(s) < p(6)) Since no edge on path from any E N to any s' E S {s} was removed, we have WP, s'] = W(u, s') and p(e) > p(e) for every edge e in & and E > 0. Therefore, for the absolute voting weight of any s' E S {s} in G we get
Te. Tx (A) = 1 1 Σ lim Σ VEN
II
p(() 21 Σ
lim =0
Σ
II
p(c) (A)
WeW(v.o]eeW
VEN
WeWlo.st
which concludes the proof.
Using Lemma C.1 and the proof of Theorem 7, we can show that guru-participation is satisfied by the RANDOM WALK RULE by removing delegating voter step by step.
Theorem C.2. The RANDOM WALK RULE satisfies guru participation.
Proof. Let (G, e) be delegation graph and v E N delegating voter. We remove v from G in three steps. First, we remove all out-edges of u, making v casting voter and call the new delegation graph (G1, c). Then we remove the in-edges of e (and all newly isolated voters) and get (G2, c). Finally, we remove itself to retrieve (G, c) as in the definition of guru- pantuuaaatiiiaiioon. Let A. A,, A and Á be the assignments returned by the RANDOM WALK RULE for (g.c), c). (GI, c), (G2, c) and
MMor specifically, Brill et al. [2022] use the notion of relative voting weight between the casting voters in the definition of the axiom, which follows from our version of the axiom using absolute voting weight.
21

---

(G,c), respectively. From the proof of Theorem 7 we know that for every casting voter s E S S. the voting weight in the instances (G,e) e) and (C1, c) is equal, i.e. IT (A1) (A(A). From Lemma C.I it follows that the voting weight of these voters can only increase if also the in-edges of u are removed, i.e., (A2) 2 n. (A Finally, removing the now completely isolated (now casting) voter v does not change the absolute voting weight of any other voter and therefore (A) 2 To (A). O
C.1 Relation to the Axioms of Brill et al. [2022]
First, we remark that the definition of a non-fractioo cractractioaa delegation rule varies slightly from the definition of a delegation rule in Brill et al. [2022]. That is, Brill al. [2022] define the output of delegation rule as a mapping from each delegating voter to some path to a casting voter. Here, on the other hand, we define the output of non-fractional delegation rule of delegating voters to casting voters. Hence, the definition of a delegation rule by Brill et al. [2022] is slightly more restrictive than our definition, hence, ceteris paribus, the impossibility result holds in particular for the smaller set of delegation rules. In the following, we refer to our definition as non-fractional delegation rules and the definition of Brill et al. [2022] as con-fractional* delegation rules. We say that a non-fractional delegation rule is consistent to a non-fractional* delegation rule if, for any input, the assignment in the former corresponds to the induced assignment in the latter.
fon-ffactional) assignment
Next, consider the copy-robustness axioms. The axiom by Brill et al. [2022] for con-fractional* delegation rules differs to our copy-robustness axiom restricted to non-fractional delegation rules in two technicalities: First, Brill et al. [2022] consider the relative voting weight instead of the absolute voting weight. However, since the number of voters does not change from (G, c) to (G, c). this does not change the axiom. The other difference is that their axiom requires that the delegating voter v under consideration has direct path (in the output of the * delegation rule) to its assigned casting voter. Since a non-fractional delegation rule only outputs an assignment and no path, We relaxed this assumption. Hence, our copy-robustness axiom is slightly stronger than the one presented by Brill et al. [2022]. Nevertheless, it is easy to see that also the weaker version of the axiom is necessarily violated within the proof of the impossibility theorem when we utilize the definition of delegation rule by Brill et al. [2022].
Confluence Lastly, consider the confluence axiom. Brill et al. [2022] define their confluence axiom, which we denote by confluence* as follows: A non-fractional delegation rule satisfies confluence* if, for every delegating voter V E N exactly one outgoing edge of v appears within the union of paths returned by the delegation rule. In particular, this is equivalent to the fact that the union of the returned paths forms a branching in the delegation graph. We prove below that the two axioms are in fact equivalent (within the restricted domain of non-fractional delegation rules).
Proposition 1. A non-fractional* delegation rule satisfies confluence* if and only if there exists consistent non-fractional delegation rule that satisfies conftuence.
Proof. We start by proving the forward direction. Consider a n delegation rule that satisfies * We define consistent non-fractional delegation rule by simply returning the assignment induced by the returned paths instead of the paths. For showing that the rule satisfies confluence, we define the probability distributions fv: U E N by setting (-) = if and only W is the path returned for v by the delegation rule. All other probabilities are set to zero. Then, confluence* directly implies that the distributions fo, v E N witness confluence.
For the other direction, consider a non-fractional delegation rule satisfying confluence, and let fe, v E N be the probability distributions that witness this fact. Building upon that, we define branching in G that is consistent with the outcome of the delegation rule. Interpreting this branching as the output of non-fractional delegation rule then proves the claim. We construct the branching as follows: We first set B- = O. In the beginning, set all delegating voters to be "active", while all casting voters are "inactive". " Now, pick some arbitrary active voter E N and consider some arbitrary walk W that obtains non-zero probability by the distribution fc. Construct path P from W by cutting the walk in the first appearance of some inactive voter, and then short cutting all remaining cycles (if existent). Now, add all edges in P to B and set all delegating voters on P to be "inactive",, Note that, by confluence, for each newly inactive voter u E N it holds that the casting voter assigned by the delegation rule corresponds to the sink node at the end of the unique maximal path in B starting
22

---

from u. We continue this process until all voters are inactive. As result, we created branching that is consistent with the original delegation rule, hence, there exists a consistent non- con-fractional* delegation rule that implicitly returns branchings, i.e., is confluent.
D Broader Impact
We are aware of the fact that any delegation rule, and in particular the one suggested in this paper, may be implemented in liquid democracy system and could thereby have real world impact. In this paper, we chose the axiomatic method in order to evaluate the suggested rule in a principled way. While, with respect to the axioms considered in the literature very well, we want to point out that this is the very first paper introducing fractional delegation rules for ranked delegations. In particular, there is risk of some unforeseen disadvantages of the rule that could possibly be used for manipulations or lead to other negative societal effects. Therefore, think that further theoretical and also empirical research necessary before recommending our suggested delegation rule for (high-stake) real-world decision making.
far, our delegation rule performs
23


Reviews:
[{"review_id": "6gwrDI9t68", "reviewer": "Reviewer_vsDd", "summary": "This paper studies algorithms for assigning delegation weights in liquid democracy in the setting where participants indicate a set of trusted delegates, along with a ranking describing their preferences over these delegates. Notably, the algorithms it considers permit fractional delegations - i.e., voters have voting weight 1, and they can delegate it fractionally across multiple possible delegates.\nThe paper considers two algorithms for finding a delegation graph (i.e. an assignment of fractional delegations from voters who wish to delegates, to trusted delegates). These two algorithms are: (1) the random walk rule, a Markov-chain based rule proposed in past work;  and (2) the mixed Borda branching rule, which is a uniform average over all min-cost branchings, called “borda branchings”, where a branching occurs on a weighted digraph representing to which casting voters each voter is willing to delegate to. \n\nThe paper makes three main contributions: \n(1) Provides a polynomial-time algorithm for computing mixed Borda branching. This algorithm is an adaptation of Fulkerson’s algorithm, and relies on two of its canonical properties (as proven by Fulkerson). This algorithm is of independent interest to the direct power watershed problem. \n(2) Proves the equivalence of rules (1) and (2) above. \n(3) Shows that rule (1) (and therefore rule (2)) satisfies three axioms: confluence, anonymity, and copy-robustness — a combination of axioms identified in past work that cannot be simultaneously achieved with delegation rules that require voters to delegate their voting weight to a single delegate.\n", "questions": "Was it previously known whether the random walk rule satisfies these three axioms simultaneously?\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The high-level structure of the paper is clearly laid out\n\n- Some aspects of the paper’s analysis (e.g., axiom iii) are practically motivated, and the setting of liquid democracy in general is well-motivated\n\n- The authors made an effort to make the paper understandable, with multiple diagrams to aid explanations\n\n- The paper speaks to and builds on multiple aspects of the literature (e.g., random walk rule, existing axioms)\n\n- The technical results seem to holds, and there is sufficient technical exposition to understand why the results are true.", "weaknesses": "1) The potential impact of this paper is not clear entirely to me. What is the main technical challenge with proving the results and what makes it hard? Why are axioms (i) and (ii) important for a rule to satisfy in practice? \n\n2) I found it very hard to understand several phrases in the introduction. In many cases, it seems that the paper is assuming too much specific knowledge of the liquid democracy literature. For example:\n- Line 47: “(i.e., a digraph with a rank function on the edges)” what is a “rank function on edges”?\n- Line 51: In the explanation of confluence, what is a “subpath of v1”?\n- Line 64: “However, since none of the axioms connects the meaning of the ranks to the decisions of the delegation rule” I do not understand what this sentence means.\n- Line 66: “A single top-rank edge to a casting voter should always be chosen over any other delegation path.” I don’t understand what this sentence means.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q:** Was it previously known whether the random walk rule satisfies these three axioms simultaneously?\\\n**A:** No. For both copy-robustness and confluence, the question whether the random walk rule satisfies (reasonable generalizations of) the axioms were open. In particular, in order to prove the copy-robustness result, we heavily use both the equivalence towards Borda Branching (Theorem 5) as well as the algorithm for computing the Borda Branching outcome (Section 4). Lastly, the fact that the random walk rule satisfies anonymity -- while not explicitly mentioned in the literature -- is rather straightforward and should not come at a surprise. \n\n**Q:** What is the main technical challenge with proving the results and what makes it hard?\\\n**A:** The main technical contribution is threefold:  (a) the development of our algorithm and its proof of correctness (Algorithm 2, Theorem 4), (b) the copy-robustness proof (Theorem 7), and (c) the confluence proof (Theorem 8). We describe the main challenges below: \n(a) Two crucial building blocks that serve as the base of the development of the algorithm are two results coming from different research fields: (1) the Markov chain tree theorem, and (2) Fulkerson's algorithm. While the Markov chain tree theorem allows us to count branchings in graphs without costs, the Fulkerson's algorithm provides us with a tool to divide the graph with a cost function into subgraphs. As a result we were able to reduce the task of counting min-cost branchings in the original graph to the task of counting branchings in subgraphs. These subgraphs are not disjoint from on another and the counting has to be done along the hierarchy prescribed by Fulkerson's algorithm, leading to a delicate construction of the subgraphs, including a non-trivial choice of weight functions (not to be confused with cost functions). We also refer to our answer to question 2 of reviewer rGK4 for a detailed comparison between the complexity of our algorithm and the (undirected) Power Watershed. \n\n(b) The main challenge here is that copy-robustnesss is an axiom which is defined across multiple input instances. Hence, we needed to relate the output of our algorithm across different instances. To this end, we proved Lemma 2 (i), which is, to the best of our knowledge, new to our paper. \n\n(c) Here, the main challenge is that confluence prescribes the existence of a probability distribution over walks in the original graph, however, our algorithm for mixed Borda branching contracts the graph. Hence, we build upon a probability distribution over walks in the contracted graph, from which we then derive a distribution over walks in the original graph. \n\n**Q:** Why are axioms (i) and (ii) important for a rule to satisfy in practice? \n\n**A:** (i) Confluence is seen as desirable in order to guarantee the liability of voters for their delegations ([4]). The idea is that voters keep their delegations over time and can therefore evaluate their representative. Consider this simplified situation: If $v$ delegates directly to a set of casting voters and the delegation rule assigns some distribution over these representatives, then we can assume that $v$ takes responsibility for his/her delegation decision (at least over the long run). If now voter $w$ delegates only to $v$, then, confluence prescribes that $w$ receives the same fractional assignment to casting voters as $v$ received. The rationale for that is that $v$ delegates its vote to $w$ and therefore wants his/her voter to be treated as $w$'s vote itself. Otherwise, the liability of $v$ towards its delegation decision is worthless from the point of view of voter $w$. This idea naturally extends to more complicated situations. \n\n(ii) Anonymity is important due to fairness considerations. Consider the simple example given in the introduction of our paper. If $v_1$ would be assigned to $s_1$ (its second preferred delegate) while $v_2$ would be assigned to $s_1$ (via its first preferred delegate), then $v_1$ could complain arguing that the two voters -- despite being in a symmetric situation -- were not treated equally. \n\n**C:** I found it very hard to understand several phrases in the introduction. [...]\\\n**A:** We thank the reviewer for the feedback and will revise the introduction for the next version of the paper, in order to make it more accessible for a broader audience. Below, we clarify some of the unclear phrases. \n\n**Q** Line 47: “(i.e., a digraph with a rank function on the edges)” what is a “rank function on edges”?\\\n**A** In social choice, the term \"ranking\" is used interchangeably with the notion of a weak or total order (more precisely, a strict ranking corresponds to a total order and a weak ranking to a weak order). Any (weak or strict) ranking can be naturally represented by a function $r$ mapping the elements to be ranked (in our case edges) to the natural numbers with the interpretation that $e \\succeq e'$ if and only if $r(e) \\leq r(e')$. \n\n**Q:** Line 51: In the explanation of confluence, what is a “subpath of v1”?\\\n**A:** Here, we are considering a path $P$ starting in a voter $v_1$, going via a voter $v_2$, and then ending in some casting voter $s$. The ``remaining subpath of $v_1$'' then refers to the suffix of the path $P$ starting from the occurence of $v_2$ and ending in $s$. \n\n**C:** Line 64: “However, since none of the axioms connects the meaning [...]\\\n**A:** Our model assumes that delegations with a lower rank are preferred over delegations with a higher rank (we also use the term costs). However, the axioms (i)-(iii) do not reflect this interpretation. In particular, there exists a delegation rule satisfying the three axioms with the following, undesirable behavior: Consider a trivial instance with one voter that delegates to casting voter $s_1$ with rank 1, and to $s_2$ with rank 2. Then, the rule assigns the voting weight of the voter completely to $s_2$, which would clearly contradict the intention of the voter.\n"}, {"review_id": "obk3hlGVCl", "reviewer": "Reviewer_rGK4", "summary": "The paper studies liquid democracy where voters can delegate their votes to others instead of casting them directly. Within this framework, some voters act as casting voters, while others delegate their votes. Delegation rules determine how casting voters are chosen for each set of delegating voters. However, voters have preferences regarding whom they trust more to represent their votes.\nWhen the entire vote must be delegated, it becomes challenging to satisfy all of several desirable axioms simultaneously. Instead, the authors explore fractional/ probabilistic delegations, allowing a vote to be split across casting voters. They demonstrate that by employing the random walk rule, it is possible to recover the possibility of meeting all axioms.\nMoreover, the authors note that the distribution over branchings, ensuring that every delegating voter is connected to a casting voter, follows a uniform distribution over all minimum-cost branchings. This connection has also been previously observed in the work of Fita Sanmartin et al.\nTo compute the delegation distribution efficiently, the authors propose a polynomial time algorithm that builds upon Fulkerson's algorithm.", "questions": "- Can you provide an explanation for why Fita Sanmartin et al.'s claim about extending the Power watershed algorithm is incorrect or why it cannot be straightforwardly extended? How does the runtime of your algorithm compare to that of Power Watershed?\n- What makes the Equivalence of Mixed Borda and Random Walk Rule surprising?", "limitations": "No concerns, limitations are addressed in the appendix.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Fractional delegations are a natural extension and furthermore they are transparent in the sense that a voter can know what proportion of her vote was transferred to which casting voter.\n- The result on the possibility of confluence, anonymity and copy-robustness if we move to the realm of fractional delegations is nice to have. \n- The authors leverage results from graph theory and combinatorial optimization to obtain their results, hence introducing techniques from this literature to their community.", "weaknesses": "- Equivalence of Mixed Borda Branching and Random Walk rule: Given an understanding of the Markov chain rule, the equivalence between the Random Walk rule and Mixed Borda Branching seems immediate. The authors' claim of surprise at this equivalence is somewhat perplexing, as the connection should have been anticipated with knowledge of the Markov chain rule. It would have been more understandable if other authors had defined Mixed Borda without recognizing this link, but the authors themselves acknowledge that this interpretation has already been observed by Rita Sanmartin et al. Consequently, the discussion on equivalence could be shortened by referring to Rita Sanmartin et al.'s work rather than presenting it as a surprising result.\n- Algorithm 2 and Directed Powershed: Unfortunately, I cannot confirm whether the Directed Powershed algorithm is novel to this paper. It appears that Sanmartin et al. discuss an extension of the undirected version to address the directed case (Page 5: \"In section 5, we show how the Power Watershed can be generalized to directed graphs by means of the DProbWS.”, Page 8: \"In the ProbWS paper [12], it was proven that the Power Watershed [6] is equivalent to applying the ProbWS restricted to the minimum cost spanning forests. This restriction corresponds to the case of a Gibbs distribution of minimal entropy over the forests. In this section, we will prove the analogous result for the DProbWS: When the entropy of the Gibbs distribution over the directed in-forests (3.1) is minimal, then DProbWS is restricted to the minimum cost spanning in-forests (mSF). This permits us to define a natural extension of the Power Watershed to directed graphs.\n“). So they claim to leverage existing knowledge (Power Watershed: A Unifying Graph-Based Optimization Framework, 2010).  However, if the problem remains unsolved, a discussion of the Power Watershed algorithm and its limitations in extending to the directed case would be necessary. It is worth noting that Algorithm 2 has limitations in practicality, with a runtime of O(n^7) (up to log factors), while Power Watershed may offer better efficiency.\n- The anonymity gained through randomizing over mincost branchings seems not surprising,. It is unclear where the challenges lie in proving that the other properties still hold ( as the authors seem to demonstrate more general versions of the axioms).\n\nIt would be valuable to have an in-depth discussion of the supervised learning literature, as the problem of liquid democracy appears to be studied under different names with distinct requirements in various fields. Exploring the Power Watershed algorithm and its directed extension, along with providing a comprehensive explanation of the connections between different fields, would be a very useful contribution. This could introduce the supervised learning literature to the computational social choice community, while also allowing the supervised learning community to benefit from the axiomatic analysis conducted in this work. If the extension of power watershed algorithm to the directed from the literature turns out to be faulty or very unclear, I will increase my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "If accepted, we are happy to use the additional page to elaborate on the connection to semisupervised learning, in particular, by providing an in-depth discussion of [1] and [2]. \n## Q1\n**Short** Indeed, we think that some formulations in [1] are ambigious and give the impression that the paper would introduce an **algorithm** for finding the directed Power Watershed solution. Instead, the paper presents an algorithm (DProbWS), which is only well-defined for a fixed parameter $\\mu$ and shows that solving a parameterized version of DProbWS and then taking $\\mu \\rightarrow \\infty$ would lead to the directed Power Watershed solution. However, the question whether a parameterized version of DProbWS can be solved efficiently is completely left open. While [2] presents a similar result in the undirected case, they also present an efficient algorithm for the limit case. Thus, when [1] mention a \"generalization\" to directed graphs, we understand that this only refers to the former result but not to the presentation of an algorithm solving the limit case. \n\n**Detailed** The paper introduces a digraph $G=(U \\cup S,E)$ with a cost function $c$ on the edges and weight function: $$w(e) = e^{-\\mu c(e)}.$$For every $q \\in U,s \\in S$, the algorithm solves the linear system $L \\cdot x_q^s = -B_s$, and outputs $x_q^{s}$. Importantly, the matrix $L$ and the vector $B_s$ consist only of sums of $w(e), e \\in E$. Hence, when $\\mu \\rightarrow \\infty$, all elements of $L$ and $B_s$ may be zero (e.g., if all costs are positive), and the linear system may have infinitely many solutions. In Rem. 1 of [1], the authors acknowledge that the sum of weights of all branchings connecting any $q \\in U$ to $S$ needs to be non-zero in order for the algorithm to be well-defined. This is violated for $\\mu \\rightarrow \\infty$.\nWe cite Thm 5.1. from [1] in our words: If $\\mu \\rightarrow \\infty$, then $$x_q^{s} = \\frac{\\text{no.min-cost bran.connecting $q$  to $s$}}{ \\text{no.min-cost bran.}},$$ where $x_q^s$ is defined by DProbWS. Given that $x_q^{s}$ is not defined for $\\mu \\rightarrow \\infty$, we believe a more accurate variant of the statement would interpret $x_q^{s}$ as a function of $\\mu$ and state $$\\lim_{\\mu \\rightarrow \\infty} x_q^{s}(\\mu) = \\frac{\\text{no.min-cost bran. con. $q$ to $s$}}{\\text{no.min-cost bran.}}.$$\nThis is also shown in the proof.\n\nWhile DProbWS can compute $x_q^{s_1}(\\mu)$ for any $\\mu \\in \\mathbb{R}$, its running time increases in $\\mu$, as the running time of solving a linear system depends on the size of the input. Alternatively, one could compute the function $x_q^{s_1}(\\mu)$ and then take its limit. We thought along these lines, and tried to build upon alg. for parameterized Markov chains, however, all of the alg. that we found (e.g. [3]) have exponential running time.\n\n## Q2\n\n**Short** While the power watershed alg. [2] (PW) is similar in spirit to our algorithm, the fact that we consider directed trees with dedicated root nodes leads to a more complex algorithm with a higher running time. We believe that this complexity is inherent to the problem and, to some extent, unavoidable (see detailed answer). We don't find this surprising: Even the classic min-cost spanning tree problem can be solved by a greedy algorithm and forms a Matroid, but this structure gets lost when moving to its directed variant.\n\n**Detailed** Recall the goal of PW (our Alg. 2, respectively). Given an undirected (directed, resp.) graph $G=(N \\cup S, E)$ with cost function $c: E \\rightarrow \\mathbb{N}$, compute for every $v \\in N$, $s \\in S$, the value $x_{v,s}$ corresponding to the relative number of min-cost spanning forests aka MSF (min-cost branchings, resp.) in which $v$ reaches $s$. To illustrate the different complexities, we restrict ourselves to the special case when the subgraph induced by $N$, i.e., $G[N]$, contains one connected component (strongly con. comp., resp.), edges in $N \\times N$ have cost $1$ and edges in $N \\times S$ have cost $2$. \n\nUndirected Case: Any MSF in $G$ consists of a spanning tree in $G[N]$ and one edge from $N \\times S$. Importantly, any min-cost spanning tree in $G[N]$ combined with any edge from $N \\times S$ forms a MSF. Making use of this property, PW contracts all nodes in $N$ (without any additional computation), and then only needs to compare the number of edges in $N \\times \\{s\\}$ for each $s \\in S$ to compute $x_{v,s}$. \n\nDirected Case: This time, any min-cost branching in $G$ consists of an in-tree in $G[N]$ and one edge from $N \\times S$. However, since in-trees have dedicated root nodes, we cannot combine any in-tree in $G[N]$ with any edge in $N \\times S$. Hence, before contracting the set $N$, Alg. 2 needs to compute the relative number of in-trees rooted at each $v \\in N$ in order to calculate $x_{v,s}$ in the next step. \n\nComing back to the general case, while both algorithms construct a hierarchical structure of subgraphs, the crucial difference is that PW only carries out calculations at the top level of this hierarchy while Alg. 2 needs to carry out calculations at each level. This leads to a blow up of the running time (ignoring log factors) from $\\mathcal{O}(n^3)$ (to the best of our understanding) to $\\mathcal{O}(n^7)$. That said, our goal, given the broad scope of the paper, was to obtain an exact and poly-time alg. and our upper bound might be improved by a more involved analysis.\n## Q3\nWe agree that, for experts on Markov chains, Thm. 5 is unlikely to be surprising. However, this does not hold for people not being aware of the Markov chain tree theorem, and we expect this to be the case for large parts of the paper's audience. Thus, we think that Sec. 5 is of interest for many readers and by presenting the very short proof, we are upfront about the fact that the result follows easily from known results. That said, we agree weaken our statement to, e.g, \"while this result might be surprising for some readers, in fact, it follows rather easily by building upon...\"."}, {"review_id": "mzgLkYOJMR", "reviewer": "Reviewer_eBke", "summary": "The authors study liquid democracy with fractional (i.e., splittable) delegations. They extend previous work by Brill et al. on delegation rules that satisfy anonymity and copy-robustness, and demonstrate that two delegation rules (mixed Borda branching and the random walk rule) that were previously thought to be different and each satisfy one property are actually the same rule that satisfies (generalized versions of) both properties. Their algorithm for computing the outcome of the combined rule is also the first efficient algorithm for a problem in semi-supervised learning, the directed power watershed.", "questions": "1. Have you thought about ways of explaining the outcomes of MBB / RWR to users of liquid democracy systems? Are there intuitive ways of showing the flow of splittable votes through the network?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "+ The paper is well-written and easy to follow, and the problem they study is well-motivated in the context of liquid democracy.\n+ The algorithm is nontrivial and of independent interest to other communities in computer science. \n+ It's also nice to see that two previously-proposed rules are actually the same; it's extra satisfying that this rule happens to satisfy generalizations of two (really, four) axioms that were thought to be hard to simultaneously satisfy.", "weaknesses": "- My main hesitation with this paper is the use of fractional delegations in liquid democracy. One central tenet of LD is the ability to immediately remove a delegation from someone who cast a vote in a way you did not approve of, which becomes much more difficult with splittable delegations. Additionally, if you allow agents to know exactly where portions of their vote ended up, they will potentially be given a lot of information about the rest of the delegation network. \n- Typos: line 73: casting, line 166: copy-robust, not copy-robustness, line 342: lens", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "A possible explanation could be the following reinterpretation of the rules, motivated by the nature of the algorithm. In the last step of the algorithm we solve an absorbing Markov chain on a partially contracted delegation graph, where the outgoing edge probabilities of each contracted vertex depend on its inner structure of delegation preferences. The assignment of the rule will then be exactly the same for any voters contained in the same contracted vertex. The rule could therefore be interpreted (and explained) as a rule aggregating the lower delegation preferences of voter clusters that only delegate to one another with their higher preferences. We could then present the flow constructed from the Markov chain on the contracted graph as an explanation on how the aggregated delegation preferences are finally resolved into delegations. This flow is polynomial time computable, since it is a byproduct of the computation of the absorbing probabilities. A downside of this method is that it only offers a partial explanation since the aggregation of delegation preferences is not explained in detail. \n\nIf we want to construct a flow on the (uncontracted) delegation graph directly, there are multiple natural ways to do this for each delegating voters vote independently, depending whether we look at the rule from the mixed Borda branching or random walk perspective. However, these individual flows may be inconsistent with another, in the sense that the relative split of flow in a specific voter might be different in the flows of different voters. In fact, we can show that it is in general not possible to construct consistent flows that correspond to the assignment of our rule for all voters."}, {"review_id": "w2bgk2Nx6n", "reviewer": "Reviewer_rLuU", "summary": "This paper primarily examines two equivalent fractional delegation rules for Liquid Democracy (transitive delegate voting): Mixed Borda Branching and Random Walk Rule. The main contribution of this paper is the equivalence between these two rules in the generalized setting of fractional delegations. This result is complemented by an axiomatic analysis of the rules w.r.t. notions of anonymity, copy-robustness, confluence, and top-rank priority. ", "questions": "Q1: Am I correct in saying that ignoring the isolated voters ultimately violates copy-robustness?\n\nQ2: Am I correct that fractional delegation trivializes the axiom of confluence?", "limitations": "No further limitations.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The equivalence between the two delegation rules is non-obvious and a significant contribution. Moreover, the proof of equivalence is highly non-trivial. These results in Sections 4-5 are of considerable value. But I am not sure if those alone are enough to carry the paper (see Weaknesses). Although perhaps they are.", "weaknesses": "Unless I have misunderstood something, it doesn’t appear that the axiomatic analysis really solves, or resolves, any of the important issues discussed in the introduction. It circumvents them instead in a way that feels cheap.\n\n\nFirst, allowing fractional delegations clearly means confluence is no longer a constraint. The authors state essentially this in an incredibly oblique way in the proof of Theorem 8, “One can verify that every delegation rule that can be formalized via a Markov chain on the delegation graph (G,c) satisfies confluence.” Confluence requires that if v1 delegates to v2 that the remainder of their delegation path much be consistent. Suppose, for example, that v1 is the only voter delegating to v2, and v2’s delegation is split between v3 and v4. No we “send” ½ of v1’s vote and ½ of v2’s vote to v3, and the remaining ½ + ½ to v4. Of course, this is functionally equivalent to sending v1’s entire vote to v3 and v2’s entire vote to v4, violating confluence. In reality, the axiom of confluence wasn’t generalized, it is made irrelevant, because any delegation that violates confluence can be trivially converted to a fractional one that satisfies its relaxation. Whether we talk in terms of dividing vote tokens or probability distributions over delegations doesn’t matter, it’s the same principle. Similarly, simple path vs. walk makes no difference here. \n\nSecond, the authors state that the purpose of giving delegations as orderings is to prevent delegation cycles and isolated voters. In footnote 3 on page 4, the authors admit that they handle isolated voters by ignoring them entirely and removing them from the graph. However it is not discussed how this bears on the axioms. Ignoring such voters is the same as assigning them a voting weight of zero, whereas if they cast their vote directly they get a voting weight of at least one (and possibly more if other isolated voters delegate to them). This violates copy-robustness, but this violation does not appear to be mentioned.\n\n\nLastly, while this is a minor note, the authors should not say that they generalized the axioms, but rather that they relaxed the axioms. The authors generalized the class of delegation rules, and relaxed the axioms required.\n\nEdit:\nBased on the author(s) rebuttal, I have improved my understanding of the paper and its results.I no longer stand by my original criticism.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: Am I correct in saying that ignoring the isolated voters ultimately violates copy-robustness?\\\n**A:** No.\\\nBefore justifying our answer, we want to clarify the handling of isolated voters. The motivation for introducing ranked delegations is to mitigate the risk of having isolated voters, i.e., voters that cannot reach any casting voter through a chain of delegations. Of course even with ranked delegations there can still be isolated voters, however it was empirically shown (Brill et al. [2022]) that few backup delegations lead to almost no isolated voters in many random graph models. We remove remaining isolated voters from the instance as is standard in the liquid democracy literature, since there is no way of assigning them reasonable representatives. We can then assume for all our definitions that each delegating voter has a path to a casting voter in the delegation graph.\n\nThat said, the axiom copy-robustness captures the impossibility of manipulation by a delegating voter copying the vote of its representative(s). Assuming, this delegating voter knows its representative(s) chosen by some delegation rule, the voter could copy their vote instead of delegating. Copy-robustness then requires that this does not change the joint voting weight of the delegating voter and its representative(s), thus preventing manipulations of this type.\n\nSince an isolated voter has no representatives and therefore nobodies vote to copy, the described situation of an isolated voter deciding to being a casting voter instead does not classify as a manipulation and is therefore not (and should not be) captured by the copy-robustness axiom. In fact, in a model that includes isolated voters, an isolated voter increasing its voting weight by casting its vote would be expected (and desired) behavior. \\\n\n**Q2**: Am I correct that fractional delegation trivializes the axiom of confluence?\\\n**A:** No.\\\nBefore justifying our answer, we would like to emphasize that a delegation rule **assigns each delegating voter** a probability distribution over casting voters. Crucially, confluence captures a consistency across the distributions assigned to different casting voters. \\\nConsidering only the total voting weight of v3 and v4 in the example given by the reviewer and calling all delegation rules yielding this outcome 'functionally equivalent' contradicts our central definition of a delegation rule and also the idea of confluence to compare the voters individual assignments. This means that even though the two example assignments yield the same outcome in terms of total voting weight, the underlying delegation rules are different and can have different axiomatic properties. \n\nTo show the non-trivial nature of confluence on an example, assume that in the example given by the reviewer, voter v2's first preference for delegation is v3 and v4 is the second. In this extended example, top-rank priority alone would only require v2's vote to be delegated fully to v3. However, if we enforce confluence as well, then v1's vote must be delegated to v3 as well. \n\n**C:** Lastly, while this is a minor note, the authors should not say that they generalized the axioms, but rather that they relaxed the axioms. The authors generalized the class of delegation rules, and relaxed the axioms required.\\\n**A:** We would like to clarify exactly what we mean by 'generalizing' an axiom. The axioms we examined were defined on a model without fractional delegations, which we generalized to a model with fractional delegations, as recognized by the reviewer. Some of the axioms then needed adjustment to this new setting. We adjusted the axioms in a (to our perception) natural way, making sure that if applied to the special case of a non-fractional delegation rule, they correspond precisely to the original axioms. (For all axioms besides confluence this fact is easy to see. For confluence, we recently wrote a proof for this claim, which we are happy to provide upon request.) We therefore refer to the new axioms as 'generalized' in contrast to 'relaxed' which is the term we would use for an axiom that was weakened, i.e. that is implied by its original version. "}, {"review_id": "0gI0Tjre7d", "reviewer": "Reviewer_PkVV", "summary": "The paper studies fractional allocation rules when each agent indicates a ranking over the agents that agrees to represent her, to overcome impossibility results of deterministic rules. The authors consider two different rules which are shown that are equivalent. They also provide a polynomial time algorithm for finding the outcome of one of the two rules.", "questions": "See weaknesses above", "limitations": " The authors adequately addressed the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "-Very well-written paper\n\n-Interesting model \n\n-Natural extension of the axioms to fractional allocations\n\n-Technically involved and interesting results\n\n-Use of known lemmas in interesting and elegant ways\n\nFurther notes:\n\nLine 73: \"casting voter\"\n\nLine 134: I think you mean \"|B|=|V(G)|-1\"\n", "weaknesses": "The choice of  the top-rank priority axiom, while it is quite natural, seems a bit arbitrary. It would be nice to show what kind of other axioms would lead to the same impossibility result. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The choice of top-rank priority is motivated by the proof of the impossibility theorem for the non-fractional setting (Section 1). Consider the example instance with one delegating voter $v_1$ and three casting voters $s_1$, $s_2$, $s_3$, where $v_1$'s first delegation preference is $s_1$ and her second (and last) delegation preference is $s_2$. We show that any anonymous, confluent and copy-robust rule must assign $v_1$'s weight to $s_2$, which contradicts the idea of delegation preferences. The following versions of a fourth property can conclude the impossibility result, without changing any of the results of our paper.\n\n(i) In a situation where a voter $v$ has exactly one outgoing edge of rank one and exactly one of rank two, leading directly to casting voters $s_1$ and $s_2$, respectively, a delegation rule should assign all of $v$'s voting weight to $s_1$.\\\n(ii) In a situation where $v$ has exactly one outgoing edge of rank one and it leads directly to a casting voter $s_1$, a delegation rule should assign all of $v$'s voting weight to $s_1$.\\\n(iii) A delegation rule should distribute $v$'s voting weight only over casting voters reachable via a walk through the graph that starts with a rank one edge.\n\nWhile (i) is extremely specific to the situation in the proof of the impossibility result, (iii) is relatively general. At the same time it is debatable whether (iii) is a desired property, while this is quite clear for (i). Due to this trade-off between arbitrariness and certainty of desiredness we choose (ii) as the definition of top-ranked priority, being slightly more general than (i) while still certainly being desirable."}]

Author rebuttal:
We would like to express our sincere gratitude to the reviewers for taking the time to review our submission. In the following, we address each of the reviewer's comments and concerns individually. 

## References 
[1] Fita Sanmartin et al. "Directed Probabilistic Watershed." (2021)\
[2] Couprie et al. "Power watershed: A unifying graph-based optimization framework." (2010)\
[3] Hahn et al. "Probabilistic reachability for parametric Markov models." (2011)\
[4] Brill et al. "Liquid democracy with ranked delegations." (2022)

Meta-review: All reviewers are positive and some are excited about the paper. All felt that the paper tackles an important and provides approaches to get around impossibility results in liquid democracy.  This is a great paper for at least the AGT community. 

We hope the authors find the reviews helpful. Thanks for submitting to NeurIPS!
Decision: Accept (spotlight)