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.
When 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.
Moreover, 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.
To compute the delegation distribution efficiently, the authors propose a polynomial time algorithm that builds upon Fulkerson's algorithm.
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.
- The result on the possibility of confluence, anonymity and copy-robustness if we move to the realm of fractional delegations is nice to have.
- 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.
- 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.
“). 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.
- 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).
It 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.
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?
- What makes the Equivalence of Mixed Borda and Random Walk Rule surprising?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
No concerns, limitations are addressed in the appendix.