Proportional Committee Elections with Positive and Negative Votes

arXiv:2503.01985 · cs.GT, cs.AI · Submitted 2026-08-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Proportional Committee Elections with Positive and Negative Votes".

Jane: The paper was written by Sonja Kraiczy, Georgios Papasotiropoulos, Grzegorz Pierczyński and Piotr Skowron from University of Oxford and University of Warsaw.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the channel, everyone. Today we’re digging into a fresh paper from arXiv with the rather hefty title, “Proportional Committee Elections with Positive and Negative Votes.” Jane, I have to say, just reading that title got me excited.

Jane: Oh, absolutely, Tom. And it’s a great title because it tells you exactly what’s missing from most voting systems we talk about. We usually assume you either vote for someone or you don’t. This paper says, what if you can actively vote *against* someone?

Tom: Right. And it’s not just a theoretical exercise. The authors—Kraiczy, Papasotiropoulos, Pierczyński, and Skowron—they point out that real platforms like Reddit, Stack Exchange, and even participatory budgeting in cities like Madrid already let people downvote or veto projects.

Jane: And that’s the gap. We have all this real-world data with negative votes, but the voting rules we use to pick winners are still mostly designed for a world where you only say yes or stay silent.

Tom: Exactly. So the paper’s core question is: how do we keep things *fair* and *proportional* when people can both approve and disapprove? And I love that they don’t just give one answer. They give two.

Jane: Two interpretations of what a negative vote even means. That’s the real meat of it. One model says blocking a candidate you hate is just as valuable as electing one you love. The other says your right to be represented is separate from your right to block things.

Tom: And that distinction changes everything about how you design the rule. It’s not just a tweak. It’s a whole different philosophy of what fairness means.

Jane: Right. And they’ve got the math to back it up. They take classic rules like Phragmén, PAV, and the Method of Equal Shares, and they show how to adapt them to this new world.

Tom: I’m already hooked. Let’s get into the actual summary and see what they found.

Summary: Tom: So, Jane, we’ve got the setup. Now let’s talk about what the paper actually *does*. The summary is dense, but the big picture is that they’re building a whole new framework for proportionality.

Jane: And the key word there is *proportionality*. That means if a group of voters makes up forty percent of the population, they should roughly get forty percent of the influence on the outcome. That’s the fairness guarantee.

Tom: But with negative votes, it gets messy. Imagine a group of voters who all approve the same set of candidates. In a normal election, they’d deserve a certain number of seats. But what if another group actively disapproves those same candidates?

Jane: Right, that’s the conflict. The paper introduces this idea of *cohesiveness*. A group is “l-cohesive” if they have enough common ground—both in what they approve and what they disapprove—to claim l seats.

Tom: And they use that to define new axioms, which are basically the rules of fairness. They’ve got one for the symmetric model, where blocking is as good as electing, and one for the asymmetric model, where representation is the priority.

Jane: The results are the exciting part. For the symmetric model, they show that a variant of Phragmén’s rule gives a solid guarantee—it satisfies something called Proportional Justified Representation. And PAV, which is usually hard to analyze, gets a near-optimal guarantee on average satisfaction.

Tom: That’s a big deal. PAV is notoriously tricky. They had to invent new proof techniques to handle the fact that adding a candidate might mean removing a “virtual” negative candidate. It’s not a simple one-for-one swap anymore.

Jane: And for the asymmetric model, they introduce a clever trick called an “opposition tax.” If a candidate has a lot of people voting against them, their cost goes up. So the supporters have to spend more of their voting budget to get them elected.

Tom: That’s such a clean idea. It naturally prioritizes candidates with broad support and makes it harder for a small group to push through someone everyone else hates.

Jane: And they show that this “tax” version of the Method of Equal Shares and Phragmén’s rule satisfies their new axioms. But here’s the kicker—they also prove that PAV, in its natural form, just can’t be fixed for the asymmetric model.

Tom: That’s a strong negative result. It means the choice of rule really depends on which interpretation of negative votes you believe in. There’s no one-size-fits-all solution.

Jane: Exactly. And that’s what makes this paper so important. It’s not just giving you a new rule. It’s giving you a map of the whole landscape.

Tom: So we’ve got the map. Now let’s talk about the improvements they suggest and what that means for real systems.

Improvements: Tom: Okay, so we’ve got the theory. But what does this mean for someone actually building a voting system? That’s where the improvements come in.

Jane: And one of the most interesting parts is when they talk about *wasted vetoes*. This is a real problem they identify. Imagine a group spends their voting power to block a candidate that had no chance of winning anyway.

Tom: Right. They use a great example. Three voters approve candidate *b* and disapprove *a*. Two voters approve *c*. The group that hates *a* spends their budget blocking it, but *a* had no supporters. So they waste their influence, and the other group wins.

Jane: It’s like spending all your money on a security system for a house that no one was going to break into anyway. You’ve protected nothing, and now you can’t afford the furniture you actually wanted.

Tom: That’s the perfect analogy. So the paper proposes a fix called *Counterfactual Veto Deletion*. The idea is to only count a veto if it actually changes the outcome. If a candidate wouldn’t win anyway, your veto against them shouldn’t count against your budget.

Jane: But here’s the catch—they prove that neither Phragmén nor PAV can be made “counterfactually stable” in all cases. There’s no perfect way to decide which vetoes matter.

Tom: So they offer two workarounds. One is a greedy algorithm that deletes vetoes until it can’t anymore without breaking the fairness guarantee. The other is a sequential version of Phragmén that checks, at the moment of each veto, whether that veto is actually pivotal.

Jane: It’s a pragmatic approach. You can’t always get the perfect answer, but you can get a good one that avoids the worst waste.

Tom: And then there’s the asymmetric model’s improvement—the opposition tax. That’s not just a theoretical trick. It has a direct practical impact. It means a candidate with one hundred supporters and ninety opponents costs ten times more than a candidate with one hundred supporters and no opponents.

Jane: That changes the incentive structure completely. It makes it much harder for a vocal minority to block something the majority wants, while still giving that minority a real voice.

Tom: And the paper even discusses the downside. In the asymmetric model, voting against a candidate costs you nothing. So you might be tempted to vote against everything you’re neutral on, just to make your preferred candidates more likely to win.

Jane: Right, that’s a strategic voting problem. They suggest limiting the number of negative votes per person, which is actually what platforms like Stack Overflow do with downvotes.

Tom: So we’ve got the theory, the fixes, and the practical concerns. Let’s wrap this up and see what the big takeaway is for the world.

Conclusion: Tom: Alright, let’s pull it all together. We’ve been talking about “Proportional Committee Elections with Positive and Negative Votes,” and honestly, this feels like a foundational paper.

Jane: It really does. It takes a problem that exists in the real world—people voting against things—and gives us the mathematical tools to handle it fairly.

Tom: And the biggest takeaway for me is that there’s no single right answer. The symmetric model is perfect for aggregating opinions, like on social media or for public statements. The asymmetric model is better for representative bodies, like city councils or participatory budgeting.

Jane: That’s the key insight. You have to match the voting rule to the goal of the election. If you want to know what people think, use the symmetric model. If you want to elect people to represent you, use the asymmetric model.

Tom: And they’ve given us the rules to do both. Phragmén and the Method of Equal Shares with the opposition tax for the asymmetric case, and the adapted PAV and Phragmén for the symmetric case.

Jane: Plus, they’ve identified the pitfalls. We know PAV can’t work for the asymmetric model, and we know that wasted vetoes are a real problem that needs careful handling.

Tom: This paper is going to be a reference point for years to come. Anyone designing a voting system with negative votes—whether it’s for a city, a company, or an online platform—is going to need to read this.

Jane: Absolutely. It’s not just theory. It’s a practical guide for making collective decisions fairer in a world where people have strong opinions in both directions.

Tom: Well said, Jane. That’s a wrap on this one. Thanks to everyone for listening, and we’ll see you on the next paper.

Sonja Kraiczy, Georgios Papasotiropoulos, Grzegorz Pierczyński, Piotr Skowron

University of Oxford · University of Warsaw

cs.GT, cs.AI

Submitted: 2026-08-12

DOI: 10.1145/3821539.3827792

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 80/100

The gist: This paper, "Proportional Committee Elections with Positive and Negative Votes," by Sonja Kraiczy, Georgios Papasotiropoulos, Grzegorz Pierczyński, and Piotr Skowron, addresses the problem of

Key concepts

Symmetric Model
This model assumes that blocking a candidate you dislike is as valuable as electing one you like. It is suitable for situations where the goal is to aggregate opinions, such as on social media or public statements.
Asymmetric Model
This model prioritizes the right to representation over the right to block things. It is better suited for representative bodies like city councils or participatory budgeting, and introduces an 'opposition tax' to adjust costs based on opposition.
Wasted Vetoes
This occurs when a group spends voting power blocking a candidate who had no chance of winning anyway. The paper proposes Counterfactual Veto Deletion as a fix, though it notes that perfect prevention is not always possible.
Opposition Tax
In the asymmetric model, this mechanism increases the cost for a candidate based on how many people vote against them. This makes it harder for a small group to block someone while still giving that minority voice.

Terminology

Summary

This paper, Proportional Committee Elections with Positive and Negative Votes, by Sonja Kraiczy, Georgios Papasotiropoulos, Grzegorz Pierczyński, and Piotr Skowron, addresses the problem of selecting up to k winners among a set of m candidates based on voters' preferences, where voters can approve, disapprove, or abstain on each candidate. The paper's central focus is on achieving proportional representation in this more expressive setting, which is a common feature on online polling platforms and beyond.

The paper's main conceptual contribution is proposing two distinct interpretations of negative votes, resulting in different perspectives of proportionality. The first is the symmetric utility model, where preventing the election of disapproved candidates is as important to voters as electing approved ones. The second is the asymmetric utility model, where approvals and disapprovals are treated separately, with each receiving its own fairness guarantees.

For each approach, the authors introduce suitable axioms capturing proportionality and examine their satisfiability by appropriate variants of Phragmén's rule, Proportional Approval Voting rule (PAV), and the Method of Equal Shares (MES).

In this model, a voter derives one unit of utility both from including an approved candidate in the winning committee and from excluding a disapproved candidate from it. To capture this, the authors introduce virtual negative candidates: for every c in C, a counterpart c is added. An outcome P may contain virtual negative candidates, where selecting c represents rejecting candidate c. Feasibility requires that P contains at most one of c and c for every c in C, and that P C is a committee of size at most k.

The authors introduce the notion of-cohesiveness for this model. A group S is-cohesive if S/n (D S + (k, A S)), and strongly-cohesive if S/n times (k, A S + D S). Here, A S and D S are the sets of candidates commonly approved and disapproved by S, respectively.

Phragmén's Rule: The authors adapt Phragmén's rule to this setting, where voters continuously earn money and can spend it to elect candidates or to block those they oppose. They prove the following theorem:

Theorem 1. Let W be an outcome returned by Phragmén's rule. For each strongly-cohesive set of voters S the following conditions are satisfied:

(PJR) i in S A i i in S D i W,

(proportionality degree) avgsat S(W)- 1 over 2.

PAV Rule: The PAV rule is extended straightforwardly by selecting a feasible outcome W that maximizes sum i in V f(W (A i D i)), where f(x) = sum j=1 x 1/j. The main technical contribution is the following theorem:

Theorem 2. Consider an election E and let W be an outcome of PAV. For each-cohesive S V:

avgsat S(W) (1 - epsilon) - 3/2, where epsilon:= 2 over k + 4.

The proof of this theorem is complex and involves considering a series of possible swaps that replace certain candidates in the committee W with candidates outside W. The authors note that "in the original setting, swaps simply involve replacing candidates one for one; an approach that fails in our setting. This is because adding a candidate c to the committee may require not just removing an arbitrary candidate from W, but also addressing the presence of a 'virtual candidate' c, which represents the exclusion of c from W." They show that the additive constant of 3/2 is necessary:

Theorem 4. For every eta > 0, there exists an election E, an-cohesive group S, and a PAV outcome W such that avgsat S(W) < - 3/2 + eta.

Counterfactual Veto Deletion: The authors identify a phenomenon where voters may expend their influence trying to block candidates that have no chance of being elected, which can inadvertently reduce their effective impact on the outcome for candidates they support. They formalize this issue by introducing notions capturing outcome-relevant negative votes. They propose the Counterfactual Veto Deletion (CVD) axiom, which ensures that vetoes are ignored only if the corresponding candidates are not selected anyway, and the Maximal Veto Deletion (MVD) axiom, which ensures vetoes are justified only when they are pivotal for excluding a candidate. They show that neither PAV nor Phragmén's rule is counterfactually stable in general:

Proposition 6. There exists an election E such that, for every T C, neither PAV nor Phragmén's rule is counterfactually stable at T.

They then propose two weaker approaches: Inclusion-Maximal Veto Deletion (IMVD), which is always achievable via a greedy algorithm, and a Sequential Counterfactual Phragmén rule that performs a counterfactual check before each veto.

In this model, voters' satisfaction depends only on the election of approved candidates, while disapprovals serve to hinder a candidate's selection. The authors introduce two axioms:

EJPR (Extended Justified Positive Representation): A set of voters S is-positively-cohesive if there exists a set of at least candidates T such that T A S and S - D c times n/k for every candidate c in T. An outcome W provides EJPR if for each-positively-cohesive group S there exists a voter i in S such that A i W. PJPR is the analogous proportional version.

Group Veto: For a set of candidates T, let ap(T) be the set of voters that approve at least one candidate from T. A set of voters S is (, T) -negatively-cohesive if T D S and S ap(T) - times n/k. An outcome W provides Group Veto if for each (, T) -negatively-cohesive group it holds W T.

The authors propose Tax-MES and Tax-Phragmén, which introduce an opposition tax that increases the cost of disapproved candidates. For each candidate c with more supporters than opponents, the price is set to p(c):= A c over A c - D c. They prove:

Theorem 8. Tax-MES satisfies EJPR and Group Veto. Tax-Phragmén satisfies PJPR and Group Veto.

Impossibility for PAV: The authors show that PAV cannot be adapted to satisfy EJPR in the asymmetric setting. This limitation extends to the entire family of generalized Thiele rules:

Theorem 9. No generalized Thiele rule induced by a scoring function f such that f(z, s) < f(z, 0) for some (z, s) in N squared, satisfies EJPR.

The paper concludes that our two formal approaches capture fundamentally different interpretations of negative votes, and the appropriate choice between them is context-dependent. The symmetric model is most natural for aggregating opinions fairly (e.g., legislation, statements), while the asymmetric model is better suited for settings where selected candidates provide representation (e.g., participatory budgeting). The authors note that moving beyond binary approval ballots gives rise to genuinely new proportionality questions, affecting both the choice of axioms and the design of voting rules.

Improvements for AI systems

Based on the paper, here are specific improvements that can be made to AI systems, particularly those involved in collective decision-making, recommendation, and content moderation:

Current AI systems (e.g., recommendation engines, content ranking algorithms) typically use simple net-approval scoring (upvotes minus downvotes), which the paper proves leads to unfair outcomes that ignore minority preferences.

Improvement: Integrate the Method of Equal Shares with Opposition Tax (Tax-MES) or Tax-Phragmén into AI-driven aggregation systems. These rules:

  • Guarantee proportional representation for groups of like-minded users (satisfy EJPR/PJPR)

  • Prevent large coalitions from overwhelming minority groups

  • Handle both approvals and disapprovals simultaneously

  • Run in polynomial time

Specific capability: For a content platform with 10,000 users voting on 100 proposals (selecting 10 winners), Tax-MES would ensure that a 40% minority group gets approximately 4 representatives, even if the majority disapproves of their choices—something current net-score systems fail to do.

Current AI systems treat all downvotes equally, even when the downvoted item would never be selected anyway. This wastes users' voting budget and reduces their influence on items they actually care about.

Current AI systems (e.g., Pol.is, deliberation platforms) treat agree and disagree asymmetrically, often using net agreement scores that the paper shows are unfair.

Current AI systems allow any candidate with majority support to be selected, even if a large minority strongly opposes it.

Current AI systems lack formal fairness guarantees when users express both positive and negative preferences.

Current AI systems using PAV face NP-hard optimization problems, making them impractical for large-scale applications.

Abstract

In the classic committee election setting each voter approves a subset of candidates and the goal is to select k winners based on these preferences. A central focus of recent research in the area has been to achieve proportional representation. In this work, we explore notions of proportionality in a more expressive setting that allows voters to vote against candidates---a common feature on online polling platforms and beyond. We propose two conceptually distinct interpretations of negative votes, resulting in different perspectives of proportionality. In the first, preventing the election of disapproved candidates is as important to voters as electing approved ones. In the second, approvals and disapprovals are treated separately, with each receiving its own fairness guarantees. For each approach, we introduce suitable axioms capturing proportionality and examine their satisfiability by appropriate variants of Phragm'en's rule, Proportional Approval Voting rule (PAV), and the Method of Equal Shares (MES).

Sources

Related papers