Multi-Winner Voting with Approval Preferences

Martin Lackner; Piotr Skowron

Source-linked AI summary

Multi-Winner Voting with Approval Preferences

Martin Lackner, Piotr Skowron

arXiv:2007.01795v5Jul 3, 2020cs.GT

TL;DR

Multi-winner voting seeks representative fixed-size subsets of candidates across political and technical applications, but the available preference information is often approval-based. This book develops fundamental concepts and recent computational-social-choice results for approval-based committee rules, emphasizing axioms, algorithms, and applications; it also identifies specific scope boundaries, including incompatibility with rules lacking score-based committee rankings.

Problem
Multi-winner voting must identify representative subsets of alternatives from voters’ preferences across political and technical applications.
Method
The book studies approval-based committee rules through axiomatic analysis, algorithmic results, and relevant applications.
Results
The book presents fundamental concepts and results for approval-based committee voting and discusses recent advances in computational social choice.
Takeaways & Limitations
Approval preferences provide a simple binary representation of approved and disapproved candidates that makes ABC rules widely suitable for practical use.
Takeaways & Limitations
The external-constraints approach is incompatible with rules that do not naturally rank committees by scores, including seq-Phragmén and the Method of Equal Shares.

Abstract

from arXiv · show

Multi-winner voting is the process of selecting a fixed-size set of representative candidates based on voters' preferences. It occurs in applications ranging from politics (parliamentary elections) to the design of modern computer applications (collaborative filtering, dynamic Q&A platforms, diversifying search results). All these applications share the problem of identifying a representative subset of alternatives -- and the study of multi-winner voting is the principled analysis of this task. This book provides a thorough and in-depth look at multi-winner voting based on approval preferences. One speaks of approval preferences if voters express their preferences by providing a set of candidates they approve. Approval preferences thus separate candidates in approved and disapproved ones, a simple, binary classification. The corresponding multi-winner voting rules are called approval-based committee (ABC) rules. Due to the simplicity of approval preferences, ABC rules are widely suitable for practical use. Recent years have seen a rising interest in ABC voting. While multi-winner voting has been originally a topic studied by economists and political scientists, a significant share of recent progress has occurred in the field of computational social choice. This discipline is situated in the intersection of artificial intelligence, computer science, economics, and (to a lesser degree) political science, combining insights and methods from these distinct fields. The goal of this book is to present fundamental concepts and results for ABC voting and to discuss the recent advances in computational social choice. The main focus is on axiomatic analysis, algorithmic results, and relevant applications.

Approval-Based Committee Voting

Multi-winner voting selects a fixed-size representative committee from voters’ preferences, with applications spanning politics and technical systems. This section introduces approval-based committee voting, its uses, advantages, and limitations.

Multi-winner elections select exactly k candidates from voter preferences to form a representative committee.
Multi-winner rules apply to representative bodies, finalist selection, group recommendations, collaborative filtering, search diversification, public facilities, Q&A platforms, consensus protocols, and genetic programming.
Approval-based preferences represent each voter’s information as a subset of approved candidates, separating approved from non-approved candidates.
ABC voting rules select one or more committees from approval-based elections and are required here to be deterministic rather than randomised.
The field studies how ABC rules satisfy properties, how applications should choose among them, and how computational and axiomatic limitations can be addressed.
Approval ballots require less cognitive effort than complete rankings and provide a simple yet expressive model, but they cannot represent relations between candidates or distinguish neutral from negatively viewed candidates.
The model leaves voters free to choose how many candidates to approve, without assumptions about approval-ballot size.

2.1. THE FORMAL MODEL

The formal model defines approval-based committee rules as methods that choose size-k committees from approval profiles. Thiele methods provide a common score-based framework encompassing AV, CC, and PAV.

Committees and ABC Rules: An election instance consists of an approval profile and a desired committee size k, with voters and candidates derived from the profile.
Committees and ABC Rules: An ABC rule takes an election instance as input and outputs one or more winning committees, each being a size-k candidate subset.
Committees and ABC Rules: Resolute ABC rules return exactly one committee, while irresolute rules may return tied committees; the model treats rules as deterministic.
2.2 Thiele Methods: Multi-Winner Approval Voting selects the k candidates approved by the most voters, maximizing the sum of individual approval counts.
2.2 Thiele Methods: In the example, AV counts approvals as a: 8, b: 4, c: 4, d: 2, e: 1, f: 2, and g: 1, producing two tied committees.
2.2 Thiele Methods: Approval Chamberlin–Courant maximizes the number of voters receiving at least one approved candidate in the committee.
2.2 Thiele Methods: Thiele methods maximize summed voter satisfaction, where satisfaction depends only on the number of approved committee members through a non-decreasing function w with w(0)=0.
2.2 Thiele Methods: PAV uses harmonic-number satisfaction to model diminishing returns and balance large groups’ demands against satisfying smaller groups.

2.3. SEQUENTIAL VARIANTS OF THIELE METHODS

Sequential Thiele methods construct committees incrementally by maximizing marginal score gains, while reverse sequential variants remove candidates with the smallest contribution. Examples show that these procedures can differ from their optimization-based counterparts and from one another.

Sequential and reverse sequential variants: Thiele methods optimize an objective function, whereas sequential procedures construct approximate committees when computing the optimum is computationally hard.Sequential methods add candidates; reverse sequential methods remove them.
Sequential and reverse sequential variants: Sequential Thiele methods start with an empty committee and add the candidate that maximizes the objective score in each round.Ties are resolved using a fixed tie-breaking order, and the procedure returns the committee after k rounds.
Sequential Thiele methods: For k = 2, PAV selects {a, c} with score 19, while seq-PAV selects {c, d} with score 18.5 after first choosing d by Approval Voting.The sequential rule chooses c in the second round because its score increase is 7.5.
Reverse sequential Thiele methods: Reverse sequential Thiele methods begin with all candidates and remove the candidate whose removal least decreases the objective score.Reverse sequential PAV can coincide with seq-PAV on some instances, but this does not hold in general.
Reverse sequential Thiele methods: Reverse sequential PAV can remove the highest-approval candidate: in the example, candidate a is removed despite having the highest approval score.Its marginal contribution is 1/2 + 4 · 1/3, while every other candidate contributes at least 2.
Monroe’s rule: Monroe assigns voters nearly equally among committee members and maximizes the number assigned to approved representatives.The example has k = 4 and n = 12, so each committee member receives exactly three voters; an optimal assignment scores 10.

2.6 Phragm´en-like Rules

Phragmén-like rules distribute voter loads or budgets to select committees. The Method of Equal Shares uses equal initial budgets and cost-sharing, while related examples show that different rules can produce different committees.

Method of Equal Shares: In its first phase, the Method of Equal Shares adds at most k candidates by selecting candidates whose approving voters can collectively pay one unit.For each eligible candidate, it minimizes the maximum individual payment ρ(c), then reduces the budgets of approving voters accordingly.
Method of Equal Shares: If fewer than k candidates are selected in the first phase, the Method of Equal Shares completes the committee in a second phase, for which seq-Phragmén is a recommended option.Many properties of the rule do not depend on the specific completion method.
Method of Equal Shares: The Method of Equal Shares gives each voter an equal initial budget and splits each selected candidate’s cost as equally as possible among approving voters.The rule is polynomial-time computable and is described as a variant of seq-Phragmén with upfront budgets.
Examples and comparisons: In one example, the Method of Equal Shares selects {a, b, c, d}, the only winning committee, and returns the same committee as seq-Phragmén.Candidates b, c, and d are selected after budget accumulation at specified times.
Examples and comparisons: In another example, seq-Phragmén selects {b, c, d}, illustrating that it and the Method of Equal Shares may produce different committees.The candidates are selected in the order c, b, d.
Other Phragmén-like rules: Eneström–Phragmén is based on a quota and selects candidates sequentially by weighted approval scores, adapting approving voters’ weights after each selection.The process continues until k candidates have been selected.

2.7. NON-STANDARD ABC RULES

Non-standard ABC rules depart from Approval Voting in the single-winner case, using alternative principles such as Hamming-distance minimization or satisfaction-based scoring. These rules can select candidates that are not the most approved, while MAV can also disregard unanimous choices.

Non-standard ABC rules: Non-standard ABC rules differ from Approval Voting when k = 1, unlike most ABC rules.They are defined as rules that do not select the most-approved alternative in the single-winner setting.
Minimax Approval Voting: MAV selects committees that minimise the largest Hamming distance between any voter’s approval set and the committee.Hamming distance is the size of the symmetric difference between two sets.
Minimax Approval Voting: MAV can select an alternative approved by only one voter when that alternative minimizes voters’ maximum Hamming distance.In the example, MAV selects b or c rather than a, even though a is approved by more voters.
Minimax Approval Voting: Replacing MAV’s maximum operator with a sum yields Multi-Winner Approval Voting.The modification aggregates distances across voters instead of minimizing the largest individual distance.
Minimax Approval Voting: MAV may treat all size-1 committees as equally preferable despite one candidate being unanimously approved, revealing a shortcoming of the rule.The text states that considering the second-least satisfied voter can remedy this problem.
Satisfaction Approval Voting: SAV gives each voter one point and distributes it evenly among that voter’s approved candidates, so broader approval sets contribute less per candidate.SAV returns committees with maximum SAV-score and is not a Thiele method because approval-set size affects the score.
Satisfaction Approval Voting: SAV can select a candidate approved by only one voter when its score exceeds those of alternatives approved by more voters.In the example, a scores 1 while b, c, d, and e each score 3/4, so SAV selects {a}.
Axiomatic properties: ABC rules vary substantially in their axiomatic properties, including anonymity, neutrality, resoluteness, and Pareto efficiency.The chapter surveys these properties and summarizes rule behavior in Table 3.1.

3.3 Committee Monotonicity

Committee monotonicity requires winning committees to grow consistently when the committee size increases. It supports predictable enlargement and rankings, but can reduce flexibility and proportionality.

Committee monotonicity: Committee monotonicity requires a winning committee of size k to be a subset of the winning committee of size k + 1.The definition applies to resolute ABC rules, which select a single winning committee at each size.
Applications: Committee monotonicity makes the next item clear when a group can afford one additional item after purchasing k items.Without it, the size-k + 1 selection might include several items that were not previously selected.
Applications: A committee monotone rule can produce a candidate ranking for hiring processes where the number of positions is decided incrementally.The ranking indicates whom to hire when one, two, or more positions are available.
Trade-offs: Committee monotonicity can reduce voting-rule flexibility and is typically associated with lower proportionality, although the latter claim lacks a formal proof.When applications do not require monotonicity, setting the axiom aside may therefore be advantageous.
Rule analysis: AV, seq-PAV, seq-CC, rev-seq-PAV, seq-Phragmén, and SAV are committee monotone when ties are resolved using a fixed candidate order.Counterexamples for the remaining considered rules are given in Appendix A, Proposition A.2.

3.6 Strategic Voting

Strategic voting concerns whether voters can benefit by misrepresenting approval preferences. The section distinguishes two strategyproofness notions, identifies AV as exceptional among considered rules, and relates strategyproofness to proportionality.

Strategyproofness notions: Cardinality-strategyproofness compares the number of a voter’s approved candidates in the committee under truthful and altered profiles.It requires |R(A, k) ∩ A(i)| ≥ |R(A′, k) ∩ A(i)| for every i-variant.
Strategyproofness notions: Inclusion-strategyproofness prevents a voter’s approved candidates in the truthful outcome from being a strict subset of those under a misrepresentation.The definition allows voters to have more complex preferences than merely counting approved representatives.
Relationship between notions: Cardinality-strategyproofness is stronger because its cardinality inequality implies inclusion-strategyproofness.Thus every cardinality-strategyproof ABC rule is also inclusion-strategyproof.
Results for ABC rules: Only AV satisfies either mentioned strategyproofness axiom among the considered rules when made resolute by any candidate tiebreaking order.The other considered ABC rules satisfy neither axiom, while AV is not strategyproof under stronger non-dichotomous preferences.
Extensions and proportionality: Irresolute strategyproofness can be generalized through set extensions: SD-strategyproofness implies cardinality-strategyproofness, and AV satisfies it.The section also notes that even weak proportionality forms are incompatible with strategyproofness.
Extensions and proportionality: In the proportionality example, AV selects all ten candidates approved by 60% of voters and ignores a group representing 20%.A committee distributing seats across groups is presented as more proportional for representative-body selection.

4.2 Cohesive Groups

Cohesive-group proportionality asks how many representatives groups with shared approvals should receive. The chapter compares EJR and proportionality degree, showing that strong guarantees are achievable but involve trade-offs with computational tractability and committee properties.

Cohesive groups: An ℓ-cohesive group contains an ℓ/k-th fraction of voters and agrees on at least ℓ candidates, motivating a proportional entitlement to ℓ committee seats.Requiring every group member to receive ℓ representatives is identified as too strong.
EJR and proportionality degree: EJR requires every ℓ-cohesive group to contain at least one voter with ℓ representatives in the winning committee.The guarantee applies to each winning committee and each cohesive group.
EJR and proportionality degree: EJR implies a proportionality degree of ℓ−1, but the converse fails.A rule may achieve the ℓ−1 average-representation guarantee without satisfying EJR.
Rule comparisons: PAV has proportionality degree ℓ−1 and satisfies EJR.The proof derives both properties from the representation guarantee for cohesive groups.
Rule comparisons: EJR and proportionality degree ℓ−1 are achievable in polynomial time, but sequential PAV variants do not satisfy EJR.The Method of Equal Shares also satisfies EJR and is computable in polynomial time.
Hierarchy of guarantees: PJR is weaker than EJR and guarantees no proportionality degree better than f(ℓ)=1.The cited example has a PJR committee that fails EJR while another committee satisfies EJR and gives better proportionality degree.
Rule comparisons: For practical choices, PAV is presented as most proportional, the Method of Equal Shares as a polynomial-time alternative, and seq-Phragmén as a committee-monotone option.Seq-PAV can have better proportionality degree for reasonable committee sizes but satisfies neither PJR nor JR.

4.3 Laminar Proportionality and Priceability

The section contrasts PAV’s welfare-oriented proportionality with the power-oriented proportionality of Phragmén-like rules and the Method of Equal Shares. Priceability formalizes whether equal voter budgets can fund elected candidates without an affordable approved alternative remaining.

Contrasting proportionality: In Example 4.7, Phragmén’s sequential rule and the Method of Equal Shares give half the committee to each half of society, unlike PAV.The first three voters and the last three voters have disjoint approval sets, making the group-level contrast explicit.
Contrasting proportionality: PAV, Phragmén’s sequential rule, and the Method of Equal Shares implement different types of proportionality.PAV is primarily concerned with voter satisfaction, whereas Phragmén-like rules emphasize the justification of welfare through equal virtual budgets.
Related properties: Laminar proportionality and priceability are similar in spirit but logically independent.Neither property implies the other.
Priceability: Priceability requires equal voter budgets, payments only for approved candidates, unit payment for each elected candidate, and no affordable approved non-elected candidate.The definition distributes power to groups whose collective budget is sufficient to afford committee candidates.

4.3. LAMINAR PROPORTIONALITY AND PRICEABILITY

The analysis finds sharp incompatibilities among welfare-based proportionality, power-based proportionality, and core-like guarantees. Because exact core satisfaction is often unavailable, randomized and deterministic approximation methods provide alternative guarantees.

Priceability and laminar proportionality: PAV’s committee in Example 4.8 is not priceable because no common voter budget can simultaneously fund its elected candidates and prevent an affordable approved alternative.The contradiction arises whether the per-voter budget is at most 2 or greater than 2.
Priceability and laminar proportionality: Phragmén’s sequential rule and the Method of Equal Shares are laminar proportional and priceable, while no welfarist rule has either property.No rule satisfying the Pigou–Dalton principle of transfers is laminar proportional or priceable.
Priceability and laminar proportionality: Priceability implies proportional justified representation and coincides with the D’Hondt method on party-list profiles.A price system also gives an explicit, verifiable explanation of how voters’ virtual budgets support the committee.
The core: The core implies EJR, but exact core satisfaction remains unclear and motivates studying relaxed core notions.The implication follows because a core committee must give some member of every ℓ-cohesive group at least ℓ approved winners.
The core: No rule in Chapter 2 satisfies the core property, and no welfarist rule can satisfy it.PAV and the Method of Equal Shares are ruled out by known counterexamples despite satisfying relevant representation conditions.
Relaxations of the core: A lottery over committees always exists that satisfies the core in expectation, although polynomial-time computation is not known in general.For constant-size candidate groups, a polynomial-time algorithm computes an approximate lottery for every ϵ > 0.

4.5 Degressive and Regressive Proportionality

Degressive proportionality favors smaller groups, while regressive proportionality emphasizes large groups or individual merit. The section formalizes these ideas through diversity, individual excellence, axiomatic characterizations, and quantitative trade-offs.

Concepts: Degressive proportionality favors smaller groups with more representatives than linear proportionality, whereas regressive proportionality emphasizes large groups.Diversity is an extreme degressive form, while individual excellence is an extreme regressive form.
Applications: Degressive proportionality is relevant to deliberative democracy, where committees should represent many different opinions.The stated goal is to maximize the number of represented voters.
Applications: Regressive proportionality is appealing when committees select candidates or grants based on individual merit.Examples include contest finalists and funded grants judged by experts.
Formal approaches: The axiomatic approach mainly captures the extreme cases of diversity and individual excellence, while quantitative approaches address intermediate notions.Axiomatic characterizations extend from party-list profiles to the full approval-based domain under additional axioms.
Axiomatic results: The Approval Chamberlin–Courant rule uniquely satisfies the listed axioms with disjoint diversity, while Multi-Winner Approval Voting uniquely satisfies them with disjoint equality.Both uniqueness results concern non-trivial ABC ranking rules.
Quantitative trade-offs: p-geometric rules span the spectrum from Approval Voting to Approval Chamberlin–Courant and can target any desired utilitarian–representation compromise.The compromise is adjusted through the parameter p.

4.6. PROPORTIONALITY AND STRATEGIC VOTING

The book examines tensions between proportionality and strategic voting, including impossibility results and empirical trade-offs. It also surveys computational complexity and external-attribute constraints relevant to ABC rules.

Proportionality and strategic voting: Proportionality and strategyproofness are inherently incompatible for resolute ABC rules, even under weak formulations of the desired axioms.The stated impossibility assumes k ≥ 3, voter count divisible by k, and m ≥ k + 1.
Proportionality and strategic voting: AV is the only ABC scoring rule known to satisfy SD-strategyproofness.
Proportionality and strategic voting: Rules closer to AV are less manipulable, whereas proportionally oriented rules are more manipulable, with degressive proportionality the most manipulable.This trade-off was measured empirically as the fraction of profiles admitting an incentivized approval misreport.
Proportionality and external attributes: External-attribute proportionality is incompatible with rules lacking a natural score-based ranking of committees, including seq-Phragmén and the Method of Equal Shares.
Computational complexity: Two prominent Thiele methods, CC and PAV, are NP-hard, while AV is computable in polynomial time; broader concavity conditions also imply NP-hardness.Sequential and reverse sequential Thiele methods, Greedy Monroe, seq-Phragmén, the Method of Equal Shares, and SAV are polynomial-time computable.

5.2 How to Compute Winning Committees?

This section surveys methods for computing winning committees, distinguishing polynomial-time rules from NP-hard rules. It presents ILP, fixed-parameter, approximation, and structured-domain approaches for difficult cases.

Algorithmic approaches: Computing winning committees varies by rule: some algorithms follow directly from definitions, while NP-hard rules require specialized algorithmic methods.The discussed methods include integer linear programs, fixed-parameter algorithms, approximation algorithms, and structured-domain algorithms.
Integer linear programs: An ILP formulation for PAV uses variables encoding committee membership and voters’ approval counts, maximizes PAV-score, and enforces exactly k selected candidates.
Fixed-parameter algorithms: Parameterizing by committee size k yields mostly negative results, including W[2]-hardness for Monroe, CC, and MAV-related decision problems.
Fixed-parameter algorithms: Parameterizing by the number of voters n enables algorithms for CC and Monroe in time n^n · poly(m, n), alongside broader FPT results for many rules.
Approximation algorithms: Sequential w-Thiele achieves a 0.63-approximation for w-Thiele, with ratio 1 − (1 − 1/k)^k ≥ 1 − 1/e ≥ 0.63.
Approximation algorithms: MAV admits a PTAS, while PAV and CC have approximation algorithms with guarantees depending on parameters such as k and the maximum approval-set size.
Structured domains: Under CI or VI approval domains, MAV becomes polynomial-time solvable; Thiele methods and Monroe’s rule are polynomial-time solvable under CI domains.Whether the same holds for Thiele methods and Monroe’s rule under VI domains remains open.

5.4. THE ALGORITHMIC PERSPECTIVE ON STRATEGIC VOTING

The section connects strategic voting, robustness, and broader voting models to computational questions in ABC voting. It highlights rule-specific hardness, tractable cases, and extensions beyond fixed-size approval elections.

Strategic voting: For a single manipulator, Subset-Manipulation is polynomial-time solvable for AV but NP-hard for SAV and coNP-hard for PAV.Utility-Manipulation is also computationally hard for SAV and PAV under a given tie-breaking order.
Strategic voting: Coalition manipulation is computationally hard across all studied variants for the ℓ-Bloc rule.The rule requires each voter to approve exactly ℓ candidates.
Robustness: Op-Robustness asks whether b Add, Remove, or Swap operations can change an ABC rule’s outcome.
Robustness: Robustness is computationally hard for PAV and CC but polynomial-time solvable for AV and SAV.
Related models: Approval ballots correspond to two-level rankings, but proportionality concepts do not easily generalize to weak orders with ties.The text identifies systematic consolidation of approval-based and ranking-based literatures as requiring further work.
Applications: In participatory budgeting, candidates have costs and selected projects must fit a budget; the Method of Equal Shares preserves adapted proportionality properties.

6.8 Proportional Rankings

Committee-monotonic ABC rules can induce proportional rankings whose prefixes remain proportional, extending multi-winner voting to ranked recommendations and search results. The section also identifies open questions about proportionality, computation, and strategic behavior.

Proportional rankings: A resolute committee-monotonic ABC rule yields a candidate ranking by successively adding candidates while retaining previous committee members.
Proportional rankings: Proportional committee-monotonic rules such as seq-Phragmén and seq-PAV produce rankings whose every prefix is proportional.Such rankings are desirable for recommendation lists and search results that accommodate different user types.
Proportional rankings: Dynamic proportional rankings account for previously selected alternatives, a setting motivated by repeatedly choosing questions on dynamic Q&A platforms.
Open problems: A major open question is whether any ABC rule satisfies both EJR and committee monotonicity; current results provide only partial answers.
Open problems: The literature seeks finer-grained analyses beyond worst-case axioms because synthetic preference distributions can be simplistic and real election data are scarce.
Open problems: Open questions include generalizing Monroe’s representation constraint, developing apportionment-agnostic proportionality notions, and characterizing further ABC rules axiomatically.
Open problems: Verifying whether a committee belongs to the core is coNP-complete, although this does not rule out polynomial-time algorithms for finding a core committee.

Appendix A

Appendix A adds proofs and counterexamples that were not found in the published literature, using alphabetic candidate tiebreaking by default where needed.

The appendix supplies proofs and counterexamples absent from the published literature.
ABC rules requiring candidate tiebreaking use alphabetic tiebreaking by default.

A.1 Additional Proofs from Chapter 3

The appendix establishes which approval-based committee rules satisfy or fail major efficiency, monotonicity, and strategyproofness properties, with counterexamples illustrating the failures. It also gives a positive characterization of Greedy Monroe under a divisibility condition.

Pareto efficiency: Thiele methods with strictly increasing w-functions and SAV satisfy strong Pareto efficiency, whereas CC and MAV fail it.
Committee monotonicity: CC, PAV, Monroe, leximax-Phragmén, and MAV fail committee monotonicity, including an example where Equal Shares selects {a, c, e} for k = 3 but {a, b, c, d} for k = 4.
Monotonicity with additional voters: Thiele methods, rev-seq-PAV, MAV, and SAV satisfy support monotonicity with additional voters, while Monroe, Greedy Monroe, and Equal Shares fail candidate monotonicity with additional voters.
Monotonicity without additional voters: AV and SAV satisfy support monotonicity without additional voters, but none of the listed rules satisfy both support and candidate monotonicity without additional voters.
Strategyproofness: AV with a fixed candidate tiebreaking order satisfies cardinality-strategyproofness and inclusion-strategyproofness, whereas the other listed rules fail inclusion-strategyproofness.
Strategyproofness: Concrete manipulations show that CC, seq-PAV, seq-CC, rev-seq-PAV, Equal Shares, MAV, and related rules can change committees after favorable ballot changes.

A.2 Additional Proofs from Chapter 4

The appendix analyzes proportionality and apportionment properties of ABC rules, proving positive guarantees for Greedy Monroe and impossibility or separation results for other rules. It also shows that Greedy Monroe matches largest remainders only when committee size divides the number of voters.

Apportionment: If k divides n, Greedy Monroe extends the largest remainders method, assigning initial seats by floors and remaining seats by decreasing remainders.
Apportionment: When k does not divide n, Greedy Monroe and Monroe do not extend the largest remainders method.
Representation guarantees: Greedy Monroe satisfies justified representation.
Proportionality: An ABC rule with proportionality degree f_R(ℓ) = ℓ−1 may fail extended justified representation.
Impossibility results: No ABC rule can satisfy both perfect representation and weak Pareto efficiency.
Proportionality: SAV and MAV have proportionality degree 0, while the Method of Equal Shares has a bounded proportionality degree established by lower- and upper-bound arguments.