CS Paper Radar

Multi-Winner Voting with Argumentative Ballots

Ryuta Arisaka, Hirotaka Ono

cs.GT cs.AI ·submitted 2026-08-24 13:39 UTC · v2

Abstract

We introduce multi-winner voting with argumentative ballots (MVArg) and investigate theoretical properties. As our conceptual contribution, we generalise approval ballots to argumentative ballots, thereby allowing voters to express defeasible preferences over candidates. We accordingly generalise voter cohesion and justified representation axioms JR, PJR and EJR. As our theoretical contribution, we establish several key results. First, MVArg is strictly more expressive than multi-winner voting with approval ballots (MV). Second, our notions of cohesion and justified representation are conservative generalisations of their counterparts in MV. Third, the MVArg counterpart of JR can always be satisfied, whereas the counterparts of PJR and EJR cannot always be. Fourth, although verifying whether a winner set satisfies the MVArg counterpart of JR is already coNP-hard, such a winner set can be constructed in polynomial time. All definitions, propositions, auxiliary lemmas and theorems have been formalised and mechanically checked in Lean 4.

Comment
Corrected Example 1, reflected the update to page 6's counts of winner sets proving axioms for the robust h. No definitions, propositions, lemmas, theorems are affected

Closest papers

Nearest neighbours by meaning across the whole index.

Full Justified Representation in Temporal Voting: Efficient Computation and Verification

cs.GT ·2026-09-22 ·Nicholas Teh
highly cited similarity 0.74
Abstract

In temporal voting, a fixed set of voters makes a collective decision in each of several rounds, and proportionality requires that groups with shared interests be represented across these decisions. Full justified representation (FJR) is among the strongest proportionality axioms known to be satisfiable in this setting, since it allows different members of a group to be satisfied by different selected candidates. However, whether an FJR outcome can be computed in polynomial time has remained open. We resolve this question by introducing temporal FJR+, a strengthening of both FJR and extended justified representation+ (EJR+) that can be computed and verified in polynomial time. The axiom measures a group's agreement in each round by the largest number of its members who approve a common candidate, and requires some member to attain the integer part of the group's proportional share of its best attainable average satisfaction, with a shortfall of at most one unit when this share is an integer. We show that verification reduces to counting approvals among the voters below each satisfaction threshold. For computation, we observe that local search for Proportional Approval Voting (PAV) can stop at an outcome violating FJR. Somewhat counterintuitively, the remedy is to subtract a small multiple of the minimum voter satisfaction from the PAV score: every FJR+ violation then admits a single-round change whose improvement guarantees polynomial running time. We further show that temporal FJR+ is strictly stronger than FJR and EJR+ combined, and coincides with lower quota on party-list preferences. Finally, temporal FJR+ and multiwinner FJR+ are incomparable in general, but coincide when approvals are static and each candidate-round pair is treated as a separate candidate.

0.32

Proportional Representation in Temporal Voting with Ranked Preferences

cs.GT cs.AI ·2026-09-24 ·Noam Hazon, Leora Schmerler, Nicholas Teh
similarity 0.73
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

Diverse Representation in Approval-Based Committee Voting

cs.GT ·2026-09-24 ·Julian Chingoma, Davide Grossi, Feline Lindeboom, Jan Maly
similarity 0.73
Abstract

The study of approval-based committee voting has so far focused predominantly on proportional representation. The canonical notion of diverse representation, based on the Chamberlin-Courant score, counts the number of voters with at least one representative in the committee, making it an individualistic notion. We develop a more comprehensive theory that instead requires the representation of many groups of voters, grounding it in the justified representation (JR) axiom, which we strengthen in two directions. First, we study the existing axioms of Strong JR (SJR) and Semi-Strong JR (SSJR), which consider the same cohesive groups as JR but demand stricter representation. We show that neither can be optimized efficiently on general domains (unless P = NP), but both can be on the Candidate Interval and Voter Interval domain. Second, to capture the unique and defining opinions of a group, we introduce Distinctive Representation (DR) and its local optimization variant, Local DR. We address satisfiability and computation time, and show (Local) DR to be distinct from known proportionality and diversity axioms. Experiments on real-world and synthetic data show that Local DR performs well on multiple empirical measures of diversity.

0.05

The Complexity of Justified Representation with Additive Utilities

cs.GT ·2026-09-02 ·Carmel Baharav, Jakob de Raaij, Agnès Totschnig
similarity 0.71
Abstract

We study the computational complexity of satisfying proportional representation -- in particular proportional, extended, and fully justified representation (PJR, EJR, and FJR) -- in participatory budgeting and committee elections with additive utilities. First, we give a complete picture of the complexity of the axioms for a constant number of voters or voter types. Second, we show that even for committee elections with integer utilities bounded above by a small constant, satisfying FJR is intractable, giving the first strong NP-hardness result for a justified representation axiom. Third, we extend the Expanding Approvals Rule to committee elections with additive utilities and show that it satisfies PJR. Lastly, we show that no sequential voting rule can improve on the known positive result, thus proving that novel, substantially different voting rules are needed to surpass these boundaries. Beyond their theoretical merit, our results carry practical importance, as multi-winner voting with additive utilities has recently been gaining prominence in online deliberation and real-world participatory budgeting.

0.29

Approval-Based Multiwinner Voting with Candidate Qualities

cs.GT ·2026-09-08 ·Niclas Boehmer, Chris Dong, Luca Kreisel, Markus Utke
similarity 0.69
Abstract · 47 pages

We initiate the study of a new model of approval-based multiwinner voting in which each candidate carries an exogenous quality score, capturing, for instance, the reliability of the candidate or their relevance to the context of the selection. Quality scores break with the standard assumption of approval-based multiwinner voting that candidates are fully defined by the set of their supporters. We rethink what proportional representation means in the presence of quality scores. For this, we introduce a threshold-based and a value-based family of axioms, analyze their relationships, satisfiability, and computational complexity, and present rules that achieve the strongest jointly satisfiable combinations of our proportionality axioms. We then analyze the compatibility of proportionality with the natural goal of maximizing the summed quality of the selected candidates. While imposing standard proportionality notions can lead to an almost complete loss of quality, we show that under a new class of reciprocal axioms, which scale a group's entitlement by the quality of its commonly approved candidate(s), there always exist proportional committees retaining at least 3/4 of the optimal summed quality, and such committees can be computed by our voting rules at no additional computational cost.

0.25

Approval-Based Apportionment: Like Portioning, Approximately like Committee Voting

cs.GT ·2026-08-27 ·Paul Gölz, Hannane Yaghoubizade
similarity 0.66
Abstract

We study approval-based apportionment, a variant of committee elections in which candidates ("parties") can be selected several times. We show that the proportionality axioms EJR, EJR+, and FJR coincide, and so do PJR, PJR+, and FPJR; that Lindahl priceability, an axiom implying core stability, is equivalent to a notion of approximate optimality with respect to the proportional approval voting (PAV) score; and that locally PAV-optimal committees are priceable. Approval-based apportionment (where a candidate receives an integer number of seats) lies between committee elections (zero or one seat) and portioning (a fractional number of seats). We formally connect portioning and apportionment by giving a construction that lifts axioms from apportionment to portioning and preserves implications between them. Several of our new implications between apportionment axioms are natural from a portioning perspective, leading us to believe that apportionment sits closer to portioning than to committee elections. None of them holds in committee elections, but several extend approximately, which makes apportionment a fruitful setting for conjecturing approximate relationships in approval-based committee elections.

0.44

Robust Proportionality Axioms for Additive Utilities

cs.GT ·2026-10-11 ·Piotr Skowron
similarity 0.66
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

Rules Before Oracles: Auditable, User-Configurable Argument Selection for Deliberative Polling

cs.AI cs.CRcs.CYcs.GT+1 ·2026-08-25 ·Muntaser Syed, Markus Zanker, Marius Silaghi
code/data similarity 0.65
Abstract

In a deliberative poll, once submissions outnumber what anyone will read, some mechanism chooses which arguments each voter sees, acquiring much of the decision; practice delegates it to opaque learned rankers, so a voter cannot recompute or contest the exposure that shaped their vote. We ask whether it can be a published rule over publicly recomputable evidence with parameters held by the voter, treating legibility as an admissibility condition on usable mechanisms, not an objective traded against accuracy. We formalise a poll over bipolar justification sets, judging a slate by reason coverage, the order it arrives in, and captured endorsement mass; we give seven checkable criteria for a civic recommender and a rule meeting them: a one-hop reversed endorsement flow parameterised by a relation-weight function. An agentic simulator records every slate at every vote, over about 17,000 seed-paired runs. Served slates fall 0.035 short of a label-reading ceiling upper-bounding every selection procedure, opaque ones included: any unconstrained ranker's advantage is bounded and small. On coverage alone, with non-degenerate authoring, the rule is indistinguishable from a random slate, a null due to an order-blind, charity-blind instrument; on the other two it leads at every prefix by a margin widening with adversarial pressure and dominates on mass by a factor of 3.3. Once a realistic fraction of submissions carries no reasons, the coverage margin returns and grows. Label-homogeneous flooding collapses completeness from 0.81 to 0.34 under a flat weight policy, only to 0.44 under author-count normalisation, making the weight function a security control worth 10% of completeness. The choice between ranking arms is a position on a coverage-versus-mass frontier, not a fact, the kind of choice only a legible rule can hand to the person it affects. It maps onto an open-source peer-to-peer platform.

0.25