An Axiomatic Analysis of Proportionality Notions in Approval-Based Multiwinner Voting Conference: ; ;
Chris Dong, Jannik Peters · 2026
Read An Axiomatic Analysis of Proportionality Notions in Approval-Based Multiwinner Voting Conference: ; ; by Chris Dong, Jannik Peters (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-04612.txt.
Introduction
Chris Dong and Jannik Peters bring an axiom-based method to the study of proportionality in committee elections. In these elections, voters approve candidates. Many notions of fair representation have been proposed for approval-based multiwinner voting. But the case for choosing one notion over another has been poorly understood.
They define axioms that a good notion of this kind should satisfy. They then characterise two prominent recent notions through those axioms. The analysis shows a classical one-way growth rule is the key feature. It separates the newer notions from the earlier ones. They also introduce witness-based notions. In that framework, a guarantee of this kind is backed by an explicit witness. This broadens the axiom-based picture.
Catalog record
| CREATOR | Chris Dong, Jannik Peters |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 164 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.04612
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Axiomatic Analysis of Proportionality Notions in Approval-Based Multiwinner Voting Conference: ; ; Chris Dong, Jannik Peters Abstract . Even though proportional representation is a fundamental goal in multiwinner voting and a plethora of proportionality notions has been introduced, the normative justifications for choosing one notion over another remain poorly understood. We address this by introducing the axiomatic study of proportionality notions in the approval-based multiwinner voting setting. That is, we define axioms (or desirable properties) that “good” proportionality notions should possess. Using these axioms, we then provide axiomatic characterizations of two prominent recently introduced notions: PJR+ and EJR+ ( 18 , ACM EC’23) . Our characterization proceeds in two parts. Firstly, we provide a characterization of refinements of PJR+ and EJR+. That is, we define axioms such that any notion satisfying these axioms must imply PJR+ (or EJR+, respectively). In particular, the fundamental axiom distinguishing PJR+ and EJR+ from their predecessors PJR and EJR is the classical axiom of monotonicity. Secondly, we introduce our framework of witness-based proportionality notions, that is, proportionality notions that certify “misrepresentation” via a witness set of misrepresented voters. In this class, we provide characterizations of PJR+ and EJR+ as the strongest (assuming certain axioms). Thus, by putting both directions together we obtain exact characterizations of both notions. Among our results, it may be worth highlighting that any notion satisfying mild conditions (monotonicity, independence of losers, robustness to fully satisfied voters, and lower quota) refines PJR+. In this sense, PJR+ turns out to be the canonical minimal requirement that one may impose on proportionality. 1. Introduction The multiwinner voting problem ( 28 ) considers the selection of a fixed-size set of candidates given the preferences of voters. An important objective for multiwinner voting is proportional representation , i.e., the selected subset of candidates should reflect the voters’ preferences in a proportional manner. Indeed, proportionality is a natural way of ensuring fairness in many variations of the multiwinner voting setting. For instance, civic participation platforms are interested in curating a “home page” that represents user viewpoints proportionally on the platform ( 47 ) . In participatory budgeting elections, each possible group of voters should be able to spend money proportional to its size ( 44 ) . In many real-world elections, the chosen candidates should proportionally represent the electorate. For instance, Scotland uses the proportional STV voting rule to select councilors in local government elections ( 10 ) . Across all these applications, a key challenge is to find appropriate formalizations of proportionality: when can we argue that the elected candidates sufficiently or insufficiently represent the voters? We study these questions in a setting with dichotomous voter preferences, commonly referred to as approval-based committee (ABC) voting ( 39 ) . Here, each voter approves or disapproves each candidate, and hence their preferences are represented by the subset of candidates that they approve. Apart from the apportionment setting , in which the candidates are partitioned into parties and each voter approves of (only) one party ( 9 ) , the ABC voting setting is arguably the multiwinner voting setting with the simplest preference structure. Therefore, understanding proportionality in ABC voting is key to gaining an intuition for stronger or more general settings. Indeed, proportionality in ABC voting has recently served as the backbone for developing proportionality guarantees (or proportional voting rules) in various settings. For instance, 18 and 36 showed how to lift proportional fairness from ABC voting to ordinal preferences and proportional clustering, respectively. 44 generalized both fairness notions and the Method of Equal Shares (MES) voting rule to participatory budgeting, with MES even being used in real-world participatory budgeting elections. A significant part of the research on proportionality in ABC voting has focused on the development of proportionality notions. 1 1 1 Also known as proportionality axioms. To avoid confusion, throughout the paper, we will only use the term proportionality notion and reserve the term axiom for the (not necessarily proportionality-related) concepts used to characterize proportionality notions. These notions are binary properties that, for a given election, partition the set of committees into two: those that are proportional according to the notion and those that are not. By evaluating voting rules using these notions, one can then judge the quality of the rules. If a rule always outputs committees that satisfy the notion, it is viewed as being proportional. Consequently, proportionality notions are both useful for distinguishing between existing rules and for inspiring the design of new rules. In turn, many different proportionality notions have been proposed over the last few years ( 1 ; 45 ; 33 ; 19 ; 37 ) ; some of these notions build on top of each other and create a logical hierarchy, while others observe that previous notions did not capture all facets of proportionality and formalize underexplored aspects. Most of the proposed notions have the goal of preventing underrepresentation : each group of voters should obtain at least as many candidates on the committee as they deserve. When does a group of voters deserve any representation? A recurring approach is that of cohesiveness: a group of voters deserves representation proportional to its size and how many candidates it approves unanimously. 1 and 48 initiated this line of proportionality notions by introducing the extended justified representation (EJR) and proportional justified representation (PJR) notions. However, 18 criticized both notions for relying on a strong form of cohesiveness: a group is eligible for representation by \ell candidates only if the group is sufficiently large and its voters share at least \ell commonly approved candidates. In both synthetic and real-world instances, the intersections of approval ballots usually turn out to be too small. As a consequence, on many profiles, there are only a few groups of voters eligible for representation and thus PJR and EJR are undemanding in many instances. To address this issue, 18 propose variants of these notions, called PJR+ and EJR+. The difference between the notions being that a group of voters can already be eligible for representation by multiple candidates if they unanimously approve a single candidate not contained in the committee. Indeed, by focusing on single candidates and thus reducing the amount of cohesiveness required, PJR+ and EJR+ are more discriminating in simulations than their predecessors, and further have the added benefit of being verifiable in polynomial time. Both of these benefits, however, are primarily pragmatic, and have not been sufficient to establish a clear, normative case for only using PJR+ and EJR+. Notably, there currently is no consensus on whether to use PJR and EJR ( 23 ; 22 ; 2 ) , or their strengthened versions PJR+ and EJR+ ( 26 ; 12 ; 35 ) ; with different papers adopting different choices, often without an explicit justification. Considering the growing body of proportionality notions, we ask: is there a principled perspective that establishes PJR+ and EJR+ as the canonical way to strengthen PJR and EJR? 1.1. Our Contribution To address this problem, we initiate the study of analyzing proportionality notions via the axiomatic method . A central approach of social choice is to axiomatically characterize voting rules. Our main conceptual contribution is to model proportionality notions themselves as (set-valued) voting rules that map