🤖 AI

Proportional Committee Elections with Positive and Negative Votes

This paper investigates proportional committee elections in settings where voters can cast both positive and negative votes, proposing two distinct interpretations of negative voting to define new proportionality axioms and evaluating their satisfaction by variants of Phragmén's rule, PAV, and MES.

Original authors: Sonja Kraiczy, Georgios Papasotiropoulos, Grzegorz Pierczyński, Piotr Skowron

Published 2026-08-13

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Sonja Kraiczy, Georgios Papasotiropoulos, Grzegorz Pierczyński, Piotr Skowron

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where making group decisions isn't just about shouting "Yes!" but also about shouting "No!" loudly enough to be heard. This is the realm of computational social choice, a branch of science that uses math and computer algorithms to figure out how to turn a messy crowd of individual opinions into a single, fair group decision. You've probably seen this in action when a class votes on a field trip or a team picks a movie night. Usually, you just raise your hand for what you like. But what if you could also raise your hand to say, "Absolutely not that one"? That's the twist this paper explores: elections where people can approve candidates and veto them.

The core problem is proportionality. Think of it like slicing a pizza. If a group of friends makes up 40% of the party, they should get roughly 40% of the pizza slices, not just the leftovers the others didn't want. In classic voting, we know how to slice the pizza fairly when everyone only says "yes." But when people start saying "no," the math gets messy. If a group hates a candidate, does that mean they get a slice of the pizza to avoid that candidate, or does it just mean they get to eat their own slice of the "good" stuff? The paper asks: How do we design a voting system that is fair when people are using both thumbs-up and thumbs-down buttons?

This paper, titled "Proportional Committee Elections with Positive and Negative Votes," dives into this exact puzzle. The authors, a team of researchers from Oxford and the University of Warsaw, propose that there isn't just one way to interpret a "thumbs down." They argue that we need to look at negative votes through two different lenses, like wearing two different pairs of glasses.

Glasses One: The Symmetric View (The "Equal Weight" Lens)
In this first model, the authors imagine that for a voter, blocking a bad candidate is just as important as electing a good one. It's like a game of tug-of-war where pulling the rope to the left (vetoing) is just as strong as pulling it to the right (approving). To make the math work, they treat a "no" vote as if it were a "yes" vote for a ghost candidate that is the exact opposite of the real one. If you vote "no" on Candidate A, it's mathematically the same as voting "yes" for "Anti-A."

The researchers tested three famous voting rules against this model:

Phragmén's Rule: Think of this as a slow-motion auction where voters earn money over time to buy candidates. The authors found that if you adapt this rule to let voters spend their money to block candidates too, it works surprisingly well. It guarantees that large groups get a fair share of the "good" stuff and the "anti-stuff."
PAV (Proportional Approval Voting): This is a rule that tries to maximize total happiness. The authors proved that even with negative votes, PAV still gives groups a very high level of satisfaction, though not quite perfect. They showed mathematically that there's a tiny, unavoidable gap in perfection (a "loss" of about 1.5 points in satisfaction), but it's still very strong.
The "Wasted Effort" Problem: The authors discovered a funny flaw in these rules. Sometimes, a group might spend all their "voting energy" vetoing a candidate who was never going to win anyway. It's like a crowd shouting "No!" at a candidate who has zero supporters, just to feel powerful. In doing so, they accidentally run out of energy to support the candidate they actually like. The paper suggests a fix: only let voters veto candidates who are actually in the running.

Glasses Two: The Asymmetric View (The "Representation First" Lens)
The second model flips the script. Here, the authors argue that a "thumbs down" is different from a "thumbs up." In this world, your main goal is to get your people elected. Blocking a bad candidate is a bonus, but it doesn't count as "representation." It's like saying, "I want my friend on the team, and I want to make sure the bully doesn't get in, but my friend's seat is the real prize."

To handle this, the authors invented a new concept called an "Opposition Tax." Imagine that every time a candidate has a lot of people voting "no" against them, their price tag goes up. If a candidate is loved by 10 people but hated by 9, they become very expensive to elect. This forces the voting system to be careful.

They adapted MES (Method of Equal Shares) and Phragmén's Rule with this tax.
The result? These "taxed" rules successfully ensure that big groups get their fair share of representatives and that groups with strong opposition can successfully block the candidates they hate.
However, they found that PAV (the happiness-maximizer) breaks completely in this model. The math proves that you cannot tweak PAV to satisfy both the need for representation and the need for blocking. It's a dead end for this specific way of thinking.

The Bottom Line
The paper doesn't just say "here is a new rule." It proves that the way we interpret a "no" vote changes everything. If you care about balancing "good" and "bad" equally, use the Symmetric model with the adjusted Phragmén or PAV rules. If you care more about making sure your group gets seats at the table, use the Asymmetric model with the "Opposition Tax" rules.

The authors also point out that while we have great rules for these scenarios, there are still open questions. For instance, can we make the PAV rule perfectly efficient in the first model? They suspect the tiny gap in perfection is real, but they haven't proven it's impossible to close. And in the second model, they admit their rules sometimes have to stop early to work, leaving some seats empty, which is a problem they hope future researchers will solve.

Ultimately, this work is a roadmap. It shows us that when we add the complexity of "no" votes to our democracy, we can't just use the old maps. We need new tools, new taxes, and new ways of thinking to make sure everyone gets a fair slice of the pizza, whether they are eating it or just trying to keep the crust away.

=== SUMMARY ===

Technical Summary: Proportional Committee Elections with Positive and Negative Votes

1. Problem Statement

The paper addresses the problem of proportional committee elections in a setting where voters can express positive votes (approvals), negative votes (disapprovals/vetoes), or abstain. While proportional representation is a well-studied topic in classic approval voting (where voters only approve candidates), the introduction of negative votes creates significant conceptual and technical challenges.

The core difficulty lies in defining proportionality when voters have the power to block candidates. A straightforward approach, such as selecting candidates based on net approval scores (approvals minus disapprovals), fails to provide fair representation. As illustrated in the paper's motivating example, a simple net-score rule may elect candidates that a large minority strongly opposes, or conversely, fail to elect candidates that a minority supports because the majority's disapproval outweighs the minority's approval. The paper seeks to formalize proportionality in this ternary voting setting and evaluate standard voting rules (Phragmén's rule, Proportional Approval Voting (PAV), and the Method of Equal Shares (MES)) under these new conditions.

2. Methodology and Framework

The authors propose two distinct utility models to interpret the meaning of negative votes, leading to different axiomatic definitions of proportionality and rule adaptations.

2.1 The Symmetric Utility Model

In this model, a voter derives equal utility from electing an approved candidate and excluding a disapproved candidate.

Formalization: The authors introduce "virtual negative candidates" ( $\neg c$ ) for every real candidate $c$ . A feasible outcome must select exactly one of $\{c, \neg c\}$ for each candidate, subject to a constraint that at most $k$ positive candidates are selected.
Proportionality Axioms: The paper defines $\ell$ -cohesiveness for a group of voters $S$ $S$ . A group is $\ell$ $ℓ$ -cohesive if its size relative to the electorate justifies a proportional share of the "common satisfaction" derived from both commonly approved candidates ( $A_S$ $A_{S}$ ) and commonly disapproved candidates ( $D_S$ $D_{S}$ ).
- Proportional Justified Representation (PJR): Ensures the group as a whole obtains a proportional share of representation.
- Proportionality Degree: Guarantees a high average satisfaction for the group.
Rule Adaptations:
- Phragmén's Rule: Adapted to allow voters to spend their accumulating budgets to either elect a candidate or veto (purchase the negative counterpart of) a candidate.
- Proportional Approval Voting (PAV): Adapted to maximize the sum of harmonic scores based on the total number of "satisfied" candidates (either elected positives or excluded negatives).

2.2 The Asymmetric Utility Model

In this model, voters care primarily about being represented by elected candidates. Disapprovals serve only to hinder the election of unwanted candidates but do not generate direct utility equivalent to electing a preferred one.

Formalization: Positive and negative votes are treated separately. The right to representation is distinct from the right to block.
Proportionality Axioms:
- Extended Justified Positive Representation (EJPR) / PJPR: Analogous to standard EJR/PJR but adjusted for the presence of opposing voters. A group $S$ is $\ell$ -positively-cohesive if it is large enough to overcome the veto power of opposing voters and still claim $\ell$ representatives.
- Group Veto: A new axiom ensuring that if a sufficiently large group disapproves of a set of candidates $T$ , the number of candidates from $T$ elected is limited.
Rule Adaptations:
- Tax-MES and Tax-Phragmén: These rules introduce an "opposition tax." The cost of electing a candidate $c$ is increased based on the ratio of its supporters to its opponents ( $p(c) = |A_c| / (|A_c| - |D_c|)$ ). This makes it more expensive for supporters to elect candidates that face strong opposition, effectively balancing the influence of negative votes.

3. Key Contributions and Results

3.1 Results in the Symmetric Utility Model

Phragmén's Rule: The authors prove that the adapted Phragmén's rule satisfies PJR and provides a strong guarantee on the proportionality degree (average satisfaction) for strongly $\ell$ -cohesive groups. The rule runs in polynomial time.
Proportional Approval Voting (PAV): The paper provides a technical proof that PAV offers near-optimal proportionality guarantees. Specifically, for any $\ell$ $ℓ$ -cohesive group, the average satisfaction is at least $(1 - \epsilon)\ell - 3/2$ $(1 - ϵ) ℓ - 3/2$ , where $\epsilon$ $ϵ$ is a small term dependent on $k$ $k$ .
- Tightness: The authors demonstrate via a counterexample that the additive constant of $3/2$ is necessary; PAV cannot guarantee an average satisfaction of $\ell - 1$ in this setting.
Outcome-Relevant Vetoes: The authors identify a phenomenon where voters may "spend" influence to block candidates who had no chance of winning anyway, inadvertently reducing their ability to elect preferred candidates. They propose Counterfactual Veto Deletion (CVD) and Maximal Veto Deletion (MVD) to address this. They show that standard PAV and Phragmén are not "counterfactually stable" (i.e., they do not naturally satisfy these deletion properties) but propose sequential refinements (e.g., Sequential Counterfactual Phragmén) to mitigate wasted veto influence.

3.2 Results in the Asymmetric Utility Model

Tax-MES and Tax-Phragmén: The authors show that adapting MES and Phragmén with an opposition tax allows them to satisfy EJPR (for Tax-MES) or PJPR (for Tax-Phragmén) simultaneously with the Group Veto axiom.
Impossibility for Thiele Rules: A significant negative result is presented regarding Generalized Thiele Rules (the class including PAV). The authors prove that no generalized Thiele rule can satisfy EJPR while also respecting negative votes (i.e., providing a negative guarantee like Group Veto). This implies that PAV cannot be naturally extended to the asymmetric setting to satisfy both positive and negative fairness criteria simultaneously.

4. Significance and Claims

The paper claims to be the first to provide theoretical guarantees for proportional representation in committee elections with both positive and negative votes. Previous work in this area (e.g., Talmon and Page) relied on simulations and did not establish axiomatic satisfaction for standard rules.

The authors emphasize that their work highlights a fundamental distinction in how negative votes should be interpreted:

Symmetric: Where blocking is as valuable as electing. This is suitable for aggregating opinions (e.g., selecting statements or policies).
Asymmetric: Where blocking is a defensive mechanism, but representation is the primary goal. This is suitable for electing representatives (e.g., participatory budgeting or legislative bodies).

The paper concludes that moving beyond binary approval ballots introduces genuinely new proportionality questions that require different axiomatic frameworks and rule designs. It identifies open problems, such as closing the gap in PAV's proportionality guarantee in the symmetric model, extending the analysis to intersections of matroids, and designing efficiently computable rules that are counterfactually stable.