CS Paper Radar

Representation in Peer Selection: A Liquid Democracy Perspective

Davide Grossi, Grzegorz Lisowski, Georgios Papasotiropoulos

cs.GT ·submitted 2026-08-13 10:53 UTC · v1

Abstract

We study the peer selection problem in which a group of peers must select a fixed-size committee from among themselves. To this end, we introduce a class of approval-based preference profiles, inspired by delegation graphs in liquid democracy and the transitivity of trust therein, which we call ``liquid profiles''. Under this new domain restriction, each voter designates a single trusted agent and, in turn, approves all those trusted by that individual. After establishing relationships to standard restricted preference profiles and examining computational properties of liquid profiles, we focus on understanding how novel and established proportionality axioms behave in this domain and how they relate to one another. Then, we study their satisfaction under various voting rules, including new ones that are directly inspired by the structure of liquid profiles. Our findings reveal that particularly strong proportionality guarantees are attainable in this new domain, showing promise for applications to real-world peer selection problems via transitive delegations.

Closest papers

Nearest neighbours by meaning across the whole index.

Power in Liquid Democracy: A Network Centrality Approach

cs.GT cs.SI ·2026-08-13 ·Davide Grossi, Andreas Nitsche, Georgios Papasotiropoulos, Oskar Skibski, Piotr Skowron +1 more
similarity 0.70
Abstract

This paper develops a computationally tractable framework for measuring voters' power in collective decision-making platforms that support transitive and suspendable delegations---commonly known as liquid democracy. We employ Random Walk Decay centrality to capture how influence propagates through delegation networks, argue for its intuitive appeal in this context and its advantages over alternatives such as PageRank, and derive a natural axiomatic characterization within the class of power metrics. Moreover, we conceptualize how the framework can be extended into a practical tool for analyzing power distributions in such platforms, and propose and study, both axiomatically and algorithmically, methods for selecting representative slates of influential participants.

0.32

Liquid democracy under vote correlation: On the fallacies of averaging and the excluded middle

cs.GT ·2026-08-17 ·Seth Gilbert, Stefan Schmid, Santiago Schnell, Jakub Svoboda, Michelle Yeo
theory similarity 0.64
Abstract

Liquid democracy permits voters to vote directly or delegate their votes to others. Existing algorithmic analyses assign each voter a single scalar parameter, interpreted as an independent probability of voting for the ground truth. This representation is inadequate when delegation is fixed before public information changes different voters' reliability in different ways. In this work, we study a minimal common-signal model of this phenomenon. Delegation occurs before a public binary signal is realised, while voting occurs afterwards. Conditional on the signal, sink votes are independent, and each voter has a signal-specific competence; marginally, correctness events are correlated through the common signal. We show that delegation based on average competence is not a safe scalarisation: it can violate do-no-harm, and a beneficial delegation rule may send votes to voters with lower average competence. We present and analyse three novel delegation mechanisms for this setting. The first is a conservative intersection mechanism that delegates only to neighbours whose competence exceeds the delegator's by a prescribed margin in every signal state; the conservative intersection mechanism inherits all the guarantees of delegation in the scalar competence setting. The next mechanism is a confounded-set mechanism that enable the delegation to neighbours who are favoured in one state and worse by at most a prescribed tolerance in the other. For this mechanism, we prove expected-margin bounds, and identify the weight-dispersion and mechanism-concentration conditions needed to obtain majority-correctness guarantees. Finally, on bounded-in-degree graphs, a multi-round certified-path mechanism propagates nonnegative two-dimensional path certificates; it is acyclic, yields statewise terminal competence improvement, and gives uniform bounds on path length and terminal voting weight.

0.09

Proportional Representation in Temporal Voting with Ranked Preferences

cs.GT cs.AI ·2026-09-24 ·Noam Hazon, Leora Schmerler, Nicholas Teh
similarity 0.63
Abstract

We study proportional representation in temporal voting, where one candidate is selected in each round. While prior work has focused on approval ballots, we consider ranked preferences, which may change over time. A natural approach treats each voter's top candidates as approved, but the right cutoff may differ across voters and rounds. We therefore require proportionality to hold for every admissible choice of cutoffs, whether fixed and common, common but varying across rounds, or set individually for each voter in each round. Combining these interpretations with temporal versions of justified representation (JR), proportional JR (PJR), extended JR (EJR), and proportionality for solid coalitions (PSC) gives us a hierarchy of axioms. We ask which of these axioms can be guaranteed, and with how much knowledge of the future. Unlike with approval ballots, no version of EJR can be guaranteed, and for the other axioms, flexibility in the cutoffs comes at a price. With a fixed common cutoff, JR, PJR, and PSC can be guaranteed, but only by rules that see all preferences in advance. Once the cutoff may vary across rounds, even such rules cannot guarantee JR or PSC for groups that agree in only some rounds. For groups that agree in every round, however, knowing only the number of rounds suffices for PJR in polynomial time, and PSC needs no knowledge of the future at all. Under individual cutoffs, no version of JR or PJR can be guaranteed, yet a rule as simple as serial dictatorship achieves PJR up to an additive loss that no rule can improve on, however much it knows. Natural preference restrictions restore exact guarantees. Finally, we show that checking our axioms is often coNP-complete; but perhaps surprisingly, a stronger axiom can be easier to check.

0.27

Proportional Representation for Almost-Solid Coalitions and the Proportional Veto Core for Rankings

cs.GT ·2026-11-19 ·Evi Micha, Fatih Erdem Kizilkaya
similarity 0.62
Abstract

A proportional ranking should give groups of voters representation commensurate with their size at every prefix. Proportionality for solid coalitions (PSC) provides this guarantee to groups whose members rank the same set of candidates above all others. How much representation should a group receive when a few outside candidates disrupt that agreement? We extend the proportional veto core to rankings through candidatewise and setwise guarantees. We show that setwise veto protection is equivalent to robust Rank-PSC under reversal of both the voters' preferences and the collective ranking. Robust Rank-PSC extends representation guarantees to almost-solid coalitions at every prefix. Each distinct outside candidate that disrupts a coalition's agreement reduces its guaranteed representation by at most one, and this bound is tight. Using reverse-sequential variants of Ordered Phragmén and STV, we construct rankings satisfying robust Rank-PSC$+$ in polynomial time. This stronger axiom preserves the guarantee after deleting any suffix of the collective ranking and restricting voters' preferences to the remaining candidates. Verifying robust Rank-PSC is coNP-complete, whereas verifying robust Rank-PSC$+$ takes polynomial time. We also introduce Rank-Aligned PJR$+$, which requires the first $r$ candidates of the collective ranking to satisfy PJR$+$ when each voter approves their top $r$ candidates. We give a polynomial-time algorithm that meets this requirement simultaneously for every $r$. For fixed-size committees, the Expanding Approvals Rule guarantees Rank-PJR$+$ but can violate robust PSC regardless of how ties are broken or payments are assigned. We give a modification that satisfies both guarantees for any prescribed committee size.

0.14

Condorcet-Winning Sets and Peer Selection in Planar Metric Elections

cs.GT cs.CG ·2026-08-27 ·Gabriel de Azevedo, Ulysse Hennebelle
theory similarity 0.61
Abstract

In ranked-choice voting, a Condorcet-winning set is a group of candidates for which no outside candidate is preferred to every member of the group by a majority of voters. We study Condorcet-winning sets in planar metric elections, where voters rank candidates according to their distance under a given norm. We formulate general metric elections, peer selection, and the one-round Voronoi game as instances of a two-player Stackelberg game and place these problems in a common hierarchy. We also introduce a new variant, which we call strong peer selection. Our main result concerns peer selection under the $\ell_1$ and $\ell_\infty$ norms. We prove that every planar instance admits a Condorcet-winning set of size at most three, even under strong peer selection. This follows from a new result for strong rectangular $\varepsilon$-nets. We show that, for every set of points in the plane, one can choose at most three input points that intersect every axis-parallel rectangle containing more than half of the points, improving the previous threshold of $9 / 16$ due to Ashok et al. Under the $\ell_2$ norm, we prove that every planar metric election admits a Condorcet-winning set of size at most four, improving on the general bound of five due to Song et al. Finally, we give new norm-independent bounds for the one-round Voronoi game.

0.22

Rewarding Informed Voting in PoS Governance

cs.GT econ.TH ·2026-10-06 ·Juan Beccuti, Manvir Schneider
similarity 0.61
Abstract

We study reward design for delegated representatives who acquire costly information and vote on a binary governance proposal. Effort improves both private information and delegated voting weight. We show that no payment rule can make sincere voting strictly optimal at every positive effort profile under a non-neutral prior, while fixed budgets limit accuracy in large symmetric committees. We then compare proportional sharing with a conditional rule that rewards only members of a sufficiently large winning coalition. Unlike proportional sharing, which supports sincere voting only through indifference, the conditional rule makes sincere voting strictly optimal at symmetric positive effort profiles. It supports sincere equilibria with the same effort as proportional sharing and, under suitable reward-cost conditions, with strictly higher effort and decision accuracy. Insincere equilibria may nevertheless coexist.

0.21

SAGE: Optimal-Stopping Peer Selection for Decentralised Federated Learning

cs.DC cs.LG ·2026-09-20 ·Ke Xiao, Qiyuan Wang, Christos Anagnostopoulos
similarity 0.61
Abstract · 12 pages, 3 figures, 3 tables

Decentralised federated learning replaces server aggregation with peer-to-peer model exchange, making collaborator selection a local decision under uncertainty. Fixed probe budgets waste effort on easy choices yet fall short when peers are hard to distinguish. We propose SAGE (Sequential Anchor-Gated Exchange), an optimal-stopping peer selector under a one-model-bearing-exchange budget. A receiver scores candidate neighbours on receiver-owned anchor evidence and selects once an advantage is certified. It continues probing only while further evidence repays its cost, and otherwise falls back to random gossip. We show that the stopping problem admits an optimal rule attained at a finite stage, and that the anchor schedule is order-optimal in the peer-risk gap and the confidence level. We further show that the selector never returns a peer worse than random gossip with high probability, and prove that no such guarantee holds for selectors that commit without a certificate. A separability threshold follows, below which no probing budget improves on gossip. Experiments span two image benchmarks, two graph families and three heterogeneity levels. Selectors that always act on their evidence lose to gossip in every configuration tested. SAGE-OS matches gossip on 75.5% less evidence than a fixed budget, at half the communication overhead of two published selectors. The operative decision is not which peer to rank first, but whether the evidence justifies ranking at all.

0.33

Robust Proportionality Axioms for Additive Utilities

cs.GT ·2026-10-11 ·Piotr Skowron
similarity 0.61
Abstract

We study the model of participatory budgeting, in which a subset of candidates is selected subject to a budget constraint. Voters express their preferences by assigning a numerical utility to each candidate. Our focus is on formal analysis of proportionality, a central notion of fairness in multi-winner elections. Intuitively, proportionality means that each group of voters should influence the election outcome roughly in proportion to its size. Recent "plus" axioms of proportionality are particularly appealing notions: they are verifiable in polynomial time, and they provide strong representation guarantees without requiring groups of voters to have cohesive preferences. However, their existing formulations are restricted to approval-based preferences. We generalise extended justified representation plus (EJR+), and Core plus (Core+) to general additive utilities. Our approach builds on a payment-based interpretation of proportionality: candidates' costs are shared among their supporters, with the aim of balancing voters' total payments.

0.33