CS Paper Radar

Diverse Representation in Approval-Based Committee Voting

Julian Chingoma, Davide Grossi, Feline Lindeboom, Jan Maly

cs.GT ·submitted 2026-09-24 10:07 UTC · v2

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.

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.76
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

Approval-Based Multiwinner Voting with Candidate Qualities

cs.GT ·2026-09-08 ·Niclas Boehmer, Chris Dong, Luca Kreisel, Markus Utke
similarity 0.75
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

Multi-Winner Voting with Argumentative Ballots

cs.GT cs.AI ·2026-08-24 ·Ryuta Arisaka, Hirotaka Ono
similarity 0.73
Abstract · Corrected Example 1, reflected the update to page 6's counts of winner sets proving axioms for the robust h. No definitions, propositions, l…

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.

0.24

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

Proportional Representation in Temporal Voting with Ranked Preferences

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

Jointly Satisfying Pareto Optimality and Justified Representation is NP-Hard in Approval-Based Multiwinner Voting

cs.GT econ.TH ·2026-09-08 ·Chris Dong
similarity 0.66
Abstract · 6 pages

An open problem in approval-based multiwinner voting concerns whether we can efficiently compute committees that satisfy both justified representation and Pareto optimality. We answer this question negatively by proving that, on the domain of all profiles, outputting a committee satisfying both axioms is NP-hard. An initial proof was found by ChatGPT Astra. This was then verified and rewritten by the author.

0.47

Veto Proportionality in Multiwinner Voting with Ranked Preferences

cs.GT ·2026-11-14 ·Haris Aziz, Yuhang Guo, Patrick Lederer
similarity 0.66
Abstract · Abstract shortened due to arXiv length restrictions

Proportional representation in committee voting with ranked preferences requires voter groups to influence the selected committee in proportion to their size. Existing axioms, such as proportionality for solid coalitions (PSC), demand that like-minded groups of voters are entitled to elect a fair number of candidates to the committee. However, in applications where voters are collectively affected by the entire committee, it may be equally important that no group is confronted with a disproportionate number of candidates that it regards as undesirable. Motivated by this, we initiate the study of veto proportionality in committee elections with ranked preferences. Our central notion, the proportional multiwinner veto core (PMVC), generalizes Moulin's proportional singlewinner veto core to multiwinner elections by allowing groups of voters to partially veto sets of candidates. We analyze how the PMVC relates to existing fairness notions and design rules that are guaranteed to select committees from the PMVC. Specifically, we first introduce a duality framework that connects inclusion- and exclusion-based fairness notions and show, e.g., that the dual axiom of the PMVC strengthens PSC. We further show that STV satisfies the dual axiom of the PMVC, which also implies the existence of committees in the PMVC. Subject to a strengthening of committee monotonicity, we characterize the rules that always return committees in the PMVC as sequential adaptations of singlewinner voting rules that always select from the proportional singlewinner veto core. By our duality framework, this also gives rise to a new class of rules that satisfy PSC. We further prove that the dual axiom of the PMVC and RankPJR+ are jointly satisfiable, thereby pushing the frontier of fairness guarantees that can always be attained. Finally, we show that deciding whether a given committee belongs to the PMVC is coNP-complete.

0.09

Multi-Winner Elections: Justified Representation, Strategyproofness, and Risk-Avoiding Truthfulness

cs.GT ·2026-08-15 ·Yizhou Ai, Biaoshuai Tao
theory similarity 0.64
Abstract · 35 pages

We study approval-based multi-winner elections with Justified Representation (JR) when voters strategically report their ballots. We prove that there does not exist a strategy-proof mechanism that outputs JR committees, even when the mechanism can be randomized and only Ex-Ante strategyproofness is required. The impossibility already holds with three voters, four candidates, and target committee size three, even when the mechanism may select fewer than three candidates. It applies to every common strictly increasing cardinality-based utility function and scales to every target size $k\geq3$, every number of voters divisible by $k$, and every candidate-set size at least $k+1$. Motivated by our negative results, we then ask for weaker strategy-proof guarantees under voters' partial information. We use the notion of Risk-Avoiding Truthfulness and its RAT-Degree proposed by Hartman, Segal-Halevi, and Tao (EC'25), the number of other voters whose information a manipulator must know before a safe and profitable deviation is possible. Standard proportional rules, such as Greedy Approval Voting, Proportional Approval Voting, and the Method of Equal Shares, have poor performances under the RAT-Degree metric (with low RAT-Degrees). Finally, for $n$ voters, we construct a JR mechanism with RAT-Degree at least $n-5$, without a polynomial-time bound. We then use the same idea together with algebraic ballot encodings to obtain a polynomial-time JR mechanism with RAT-Degree at least $n-7$. When voters also have immutable private identifiers and both the identifiers and ballots of unknown voters are unobserved, we obtain a polynomial-time JR mechanism with RAT-Degree at least $n-1$ for $2\le k<m$. This degree is exactly $n-1$ when $k\ge3$ and $k$ divides $n$.

0.38