Most rules for electing a committee start by fixing its size: pick exactly $k$ winners from a pool of candidates, given each voter's set of approved candidates. In many real decisions the right number of winners is itself unknown. Examples include how many projects to fund, how many features to keep, and how many items to show a user. Fixing $k$ either pads the outcome with weak candidates or cuts strong ones. Social choice theory explains well which fixed-size rules are principled. The relevant result is axiomatic characterization, which shows that a short list of fairness properties singles out exactly one family of rules. That theory is silent once the size varies. The authors of the main approval-voting characterization say so directly: their axioms "assume a fixed committee size ($k$) and do not yet enforce consistency across different values of $k$" (Refined Characterizations of Approval-Based Committee Scoring Rules).
This note proposes to close that gap with a concrete conjecture and to tie the resulting rules to a known algorithm. The conjecture is that the standard axioms, posed over committees of every size, characterize rules that score each committee as a sum over voters of a function of three counts: how many candidates the voter approves, how large the committee is, and how many of the voter's approved candidates it contains. Adding one cross-size axiom should then narrow this family to "Thiele rules with a seat price." A Thiele rule gives each voter a diminishing reward for each additional approved winner; proportional approval voting is the best-known example. The seat price is a fixed charge per seat. Every rule in this narrowed class has a natural algorithm: greedy selection that stops when the next candidate's marginal gain drops below the price. We will show what this algorithm guarantees in theory, how it compares with what is provably achievable, and whether letting the size adjust to the vote makes greedy committees less fragile.
Core Claim
Let $C$ be the set of $m$ candidates. Each voter $i$ approves a set $A_i \subseteq C$. A rule may now return any committee $S \subseteq C$. The first claim, Conjecture A, is that four axioms posed over all subsets of $C$ characterize the class of size-free approval committee scoring rules. The axioms are anonymity, neutrality, consistency, and continuity, each restated so it applies to committees of every size. The class is
$$ \mathrm{score}(S) = \sum_i s\big(|A_i|,\ |S|,\ |A_i \cap S|\big), $$
where $s$ is any real-valued function and the rule returns the committees with the highest score. Neutrality is what reduces a voter's contribution to these three counts.
The second claim, Conjecture B, adds two axioms. The first is independence of losers, which says a winning committee stays winning if voters withdraw approvals from candidates outside it. The second is a new seat separability axiom. It says that whether a size-$k$ committee beats a size-$k'$ committee is decided by the fixed-size comparison plus a term that depends only on $k$ and $k'$. Together, these should force
$$ \mathrm{score}(S) = \sum_i w\big(|A_i \cap S|\big) - n\, h(|S|), $$
where $w$ is a Thiele weight function, $n$ is the number of voters, and $h$ is a size charge. Requiring that every additional seat cost the same per voter makes $h(k) = \lambda k$, where $\lambda$ is the per-voter seat price.
When $w$ is concave, the first term is a monotone submodular function of $S$. "Submodular" means each added candidate contributes less the more candidates are already chosen. For this class, greedy selection stopped at the price behaves as follows. Greedy's marginal gains never increase, so stopping at the first gain below $n\lambda$ selects the best prefix of the greedy sequence. Comparing that prefix with the size of the optimal committee $S^\ast$, the standard $(1-1/e)$ argument (Maximizing the spread of influence through a social network) gives
$$ \textstyle\sum_i w(|A_i\cap S|) - n\lambda|S| \;\ge\; (1-1/e)\sum_i w(|A_i\cap S^\ast|) - n\lambda|S^\ast|. $$
Bodek and Feldman studied maximizing a submodular function plus a linear term. They proved that no polynomial-time algorithm beats a $(1-e^{-\beta},\beta)$ guarantee for monotone submodular functions with non-positive linear terms (Maximizing Sums of Non-monotone Submodular and Linear Functions). The bound above matches their frontier at $\beta=1$. This is the general guarantee, which is known. The research question is whether the specific structure of approval elections lets one do better. Chamberlin–Courant, where each voter counts only whether at least one approved candidate wins, is a coverage problem and probably cannot. Proportional approval voting, with its harmonic weights, plausibly can.
Three points distinguish this from existing work. Freeman, Kahng and Pennock study elections with a variable number of winners. In their model voters also gain when unapproved candidates are rejected, and they prove a 0.5 ceiling for deterministic rules (Proportionality in Approval-Based Elections With a Variable Number of Winners). They do not characterize rules, and their utility model differs from ours, so their ceiling neither contradicts nor transfers to our setting. Xiao and Sikdar relax the size for Chamberlin–Courant by allowing committees somewhat larger than $k$ to compete with the best size-$k$ committee, and they prove $O(\log n)$ bounds (Size-Relaxed Committee Selection under the Chamberlin-Courant Rule). That is a computational result about violating a fixed size, not a theory in which size is part of the outcome. Bodek and Feldman supply the optimization frontier but have no voters and no axioms.
Research Program
The theory has three parts.
The first part proves Conjecture A by redoing the separating-hyperplane argument of Axiomatic characterization of committee scoring rules. That argument splits profiles into regions where each committee wins and separates them with hyperplanes. In the fixed-size proof, these regions are indexed by the size-$k$ committees. In ours they are indexed by all subsets of $C$. Neutrality then groups voter types by the three counts, not by two. The likely obstacle is continuity: committees of different sizes may never be exactly tied. We expect to need a mild richness condition, such as allowing arbitrary multiplicities of each ballot type, which the original proof also uses.
The second part proves Conjecture B. We will also test whether seat separability is genuinely needed. To do so, we will look for a rule that satisfies the other axioms but whose size charge interacts with how many candidates each voter approves. The ballot-size-weighted rules of Refined Characterizations of Approval-Based Committee Scoring Rules are the natural candidates for such a rule.
The third part concerns guarantees. We will characterize, for each concave $w$, the best bi-criteria guarantee that the price-stopped greedy achieves. We will try to show strict improvement over $(1-1/e,1)$ for proportional approval voting, or else prove matching hardness. Separately, we will check whether stopping at the price preserves a size-adaptive version of justified representation. Justified representation requires that any group of voters large enough to "pay for" a seat at price $\lambda$, and agreeing on some candidate, gets at least one approved winner.
The empirical part asks whether letting the size adjust changes how greedy committees fail. Faliszewski, Gawron and Kusek showed that greedy Chamberlin–Courant, greedy proportional approval voting, and Phragmén's sequential rule are maximally fragile at fixed $k$: one approval edit can replace the entire committee (Robustness of Greedy Approval Rules). Under price stopping, the same edit can also change the committee's size. This could either absorb the cascade or add a new failure mode. We do not know which, and the experiments are designed to tell.
Baselines
The naive reference point is approval thresholding. It elects every candidate whose approval count exceeds the price, which is the price-stopped rule with linear $w$, that is, plain approval voting. It is the simplest rule that sets its own size. If our rules cannot beat it on proportionality, the diminishing-returns structure adds nothing. It is run on identical profiles, with the price matched so that both rules face the same per-seat cost.
The randomized reference is the Proportional Random Rule. It includes each candidate independently with probability equal to that candidate's approval share, and is reported to achieve a tight 29/32 approximation of average satisfaction (Proportionality in Approval-Based Elections With a Variable Number of Winners). We will evaluate it under its own metric and ours, averaged over 200 draws. A deterministic rule that matches it on our cohesive-group satisfaction measure would count as a win.
The strongest fixed-size heuristic is the Removal heuristic of Effective Heuristics for Committee Scoring Rules. It starts from all candidates and repeatedly drops the one contributing least. Both it and the Banzhaf heuristic are reported to "consistently stay within 10% of the optimal score," and Removal also avoids greedy's tendency to cluster winners at the center. We adapt it to a seat price by recording the full removal sequence and keeping the best-scoring point, so it gets the same objective and the same compute as our greedy. Beating it means a better objective ratio against the exact optimum, or equal objective with better robustness.
The strongest algorithm with a guarantee is randomized double greedy from Maximizing Sums of Non-monotone Submodular and Linear Functions. It considers each candidate once and adds or discards it based on the gain from each direction. Its reported guarantee is $(\alpha, 1-\alpha/2)$ for $\alpha \le 1/2$. The exact optimum, computed by integer programming on instances with $m \le 30$, serves as the ceiling.
The ablation that isolates the key ingredient is fixed-size greedy at the size chosen afterward. For each profile, we run ordinary greedy with $k$ set to whatever size the price-stopped rule picked on the unperturbed profile. We then perturb the profile and compare the two rules. Any robustness difference must then come from letting the size adjust, not from the committee merely being smaller.
On fragility, the strongest reported numbers come from the participatory-budgeting study Robustness of Participatory Budgeting Outcomes. Its metric is the 50%-winner threshold: the smallest noise level at which the winning set changes in at least half of simulated trials. It reports a median of 12% for greedy approval voting and 7% for the Method of Equal Shares on less robust instances. For the resampling-model experiments of Robustness of Greedy Approval Rules, no reported numeric result was found on Lacuna; results there appear only as trend plots.
Why not just…?
Why not just run fixed-$k$ greedy for every $k$, subtract the seat cost, and take the best? This alternative is not a competitor; it is the same algorithm. Greedy's committees are nested, and with concave $w$ its marginal gains never increase. The best-of-$k$ sweep is therefore identical to stopping at the price. We accept this, and it changes the claim. The contribution is not a new algorithm. It is the proof that this obvious procedure is the natural greedy method for a class pinned down by axioms, together with its exact guarantee and its behavior under perturbation. The experiments report the sweep and price stopping as one method so that no difference is credited where none exists.
Why not just threshold candidates independently, or use the Proportional Random Rule? Independent thresholding is approval voting. Approval voting rewards each candidate's individual support and ignores whether a group of voters already has representatives, so it fails the diversity and proportionality goals described in Properties of multiwinner voting rules. The Proportional Random Rule fixes this on average but is randomized, which many budgeting and electoral settings cannot accept. The Euclidean experiments test this directly: if thresholding leaves voter clusters with no approved winner at the same per-seat cost, it falls short.
Why not just use simulated annealing with a size penalty? It may well find good committees. However, a random search is not one fixed rule, so it cannot satisfy consistency across electorates. Consistency is the axiom that defines the scoring-rule class (Axiomatic characterization of committee scoring rules). Deterministic heuristics are also reported to match annealing within about 10% (Effective Heuristics for Committee Scoring Rules). We include annealing with equal wall-clock time on the small instances only to measure the objective gap.
Proposed Experiments
The synthetic experiments follow the resampling model of Robustness of Greedy Approval Rules. Each election has 100 voters and 100 candidates, with approval probability $p \in \{0.1, 0.3\}$ and dispersion $\phi \in \{0.25, 0.5, 0.75, 1.0\}$, averaged over 200 elections per setting. The seat price $\lambda$ is swept so that the average chosen size covers the range around 10, the fixed size used in that paper. We add impartial-culture elections, where approvals are drawn uniformly at random, and the two-dimensional Euclidean model from Effective Heuristics for Committee Scoring Rules, where voters approve nearby candidates. The real-data experiments use approval elections from Pabulib. On Pabulib we run two variants: uniform seat prices, and the actual project costs used as a linear price, which is the setting Bodek and Feldman study.
We measure four things. The first is the objective ratio against the exact optimum on small instances. The second is the fraction of voters in cohesive groups that receive their deserved representation. The third is the fraction of the committee replaced after a single added or removed approval, including changes in size. The fourth is the 50%-winner threshold on Pabulib.
Three checks would decide the question. First, does price-stopped greedy proportional approval voting stay strictly above $(1-1/e)$ on every instance where the exact optimum is computable? If so, that supports the conjectured improvement for proportional approval voting. If not, it points toward matching hardness. Second, in the Euclidean model, does the chosen size track the number of voter clusters, while thresholding over-selects candidates near the center? Third, against the fixed-size ablation, does adjustable size raise the median 50%-winner threshold above the reported 12% for greedy approval voting, or does it lower the threshold through size changes? Either robustness outcome is informative. The theoretical work on Conjectures A and B proceeds regardless of how the experiments turn out.
References
- Refined Characterizations of Approval-Based Committee Scoring Rules
- Maximizing the spread of influence through a social network
- Maximizing Sums of Non-Monotone Submodular and Linear Functions: Understanding the Unconstrained Case
- Proportionality in Approval-Based Elections With a Variable Number of Winners
- Size-Relaxed Committee Selection under the Chamberlin-Courant Rule
- Axiomatic characterization of committee scoring rules
- Robustness of Greedy Approval Rules
- Effective Heuristics for Committee Scoring Rules
- Robustness of Participatory Budgeting Outcomes: Complexity and Experiments
- Properties of multiwinner voting rules
- Pabulib: A Participatory Budgeting Library