Sequential Phragm'en Guarantees 2-Approximate Core Stability
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Sequential Phragm'en Guarantees 2-Approximate Core Stability".
Jane: Here's the gist of the paper. Sequential Phragmén Guarantees 2-Approximate Core Stability is a research paper proving that a specific voting rule can always produce a committee that is at least 2-stable in approval-based committee elections, which improves upon previous guarantees and addresses the open problem of finding small values of lambda greater than 1 for which stability can be guaranteed The Problem Context Approval-based committee voting is a fundamental model where voters specify a subset of candidates they approve of, and the goal is to select a fixed-size committee that represents voter preferences For a nonempty subset of candidates T, the committee W is λ-stable if the total weight of voters who strictly prefer T is less than λ times the proportional share nT/k The exact core corresponds to lambda = 1 stability, which remains a major open problem in approval-based committee voting The Proposed Rule and Main Result The weighted sequential Phragmén rule is investigated as a natural weighted version of the classical sequential Phragmén voting rule The authors show that this rule always returns a 2-stable committee for arbitrary positive real voter weights, regardless of how ties between candidates are broken This result improves the 3.651-stability guarantee previously established by Gao, Sun, and Vondrák
EC 2026: Proof Structure and Key Lemmas The proof utilizes a purely combinatorial analysis that differs from Lindahl-equilibrium-and-rounding approaches The proof relies on several lemmas to establish the stability guarantee, including Lemma 1 which records basic accounting facts and justifies the water-filling interpretation Lemma 2 provides a central execution-history estimate by showing that the area lemma implies a bound on the blocking coalition's load Lemma 3 translates integer-valued utility comparisons into a bound on the coalition’s load, which is crucial for excluding factor-two blockers Implications and Future Directions The theorem provides an existence statement for the approximate core, showing that the 2-core of every finite weighted approval election is nonempty This result improves upon previous guarantees by achieving a factor of 2 stability The authors note that this proof uses unit-cost candidates and integer-valued approval utilities in an essential way, suggesting that adapting the load-update technique to non-unit candidate costs remains an open question They also question whether correlations between omitted candidates can strengthen the sum-of-squares estimate enough to beat factor two or reach the exact core Algorithm Description The weighted sequential Phragmén rule is implemented via Algorithm 1, which involves iteratively computing funding heights θl(c) for candidates not yet selected and choosing the candidate with the minimum height In each step, the loads of voters who approve the chosen candidate are raised to this common height The process continues until a committee of size k is formed Model Definition The model defines an instance by specifying a set of candidates C, voters N with positive weights wi, and approval sets Ai for each voter The approval utility ui(D) for voter i is defined as the number of candidates in D that voter i approves of, which is Ai ∩ D A committee W is λ-stable if no alternative T has a total weight strictly preferring it greater than λ times the proportional share nT/k The assumption is made that every candidate is approved by at least one voter, meaning S i∈N Ai = C Weighted Sequential Phragmén Implementation Details The funding height θl(c) of a candidate c is the unique solution to Fc,l(θl(c)) = 1, where Fc,l(x) is defined as X i:c∈Ai wi max
0, x − l i: The algorithm selects the candidate c in C excluding W that minimizes θl(c) After selection, the loads of approving voters are updated to max
l i, θl(c): This iterative process continues until W equals k The total weighted load increases by exactly one in each step, leading to the final bound L ≥ k/n Stability Proof Mechanics The stability proof studies the gaps between successive moments at which a voter's load increases The area lemma aggregates unused credit of unelected candidates, showing that for any set R and S, the weighted area is strictly less than 2RL Lemma 3 uses this to show that L wt(S) < H + p/2RL wt(S) under certain conditions The final contradiction arises from combining these bounds to exclude factor-two blockers via Lemma 4 Related Work Comparison Sequential Phragmén has been studied through proportional representation axioms, which protect specially structured cohesive groups In contrast, core stability quantifies over every coalition and every alternative set of candidates, rather than only structured cohesive groups as in proportional-representation notions The result complements this line of work by establishing a constant approximate-core-stability guarantee for sequential Phragmén Furthermore, the proof is combinatorial and draws directly on a single sequential water-filling execution, showing how the sequence of load updates controls ex-post group stability The result does not settle exact-core nonemptiness Corollary and Computational Aspect Corollary 1 states that the 2-core of every finite weighted approval election is nonempty Moreover, for rationally encoded voter weights, a 2-stable committee can be computed in polynomial time using weighted sequential Phragmén The proof shows that every execution allowed by the rule, including every choice among tied minimum-height candidates, has the desired stability guarantee This implies that for rationally encoded voter weights, a 2-stable committee can be computed in polynomial time using weighted sequential Phragmén The result is stronger than an existence result by showing that every execution allowed by the rule, including every choice among tied minimum-height candidates, has the desired stability guarantee Additional Related Work Context The authors contrast their work with other relaxations of core stability, such as those from Peters and Skowron
12: , which show factor-2 utility-based approximations or O(log k) guarantees for Equal Shares These guarantees differ from the λ-stability considered here, which instead relaxes the coalition-size threshold The authors also note that candidate costs would change both the one-unit payment identity and the scalar accounting, while general cardinal utilities would remove the integral one-unit gain in (13) The analysis excludes factor-two blockers by showing that equality in Lemma 4 is only possible when x = 0 and z = 2y Final Summary Statement
Title and authors: Tom: So we're looking at this paper titled "Sequential Phragmén Guarantees two-Approximate Core Stability <ref:2609.29646#pg1,Sequential Phragmén Guarantees 2-Approximate Core Stability>." Jane, what's the main takeaway here in plain English?
Jane: Basically, the authors are tackling a big problem in voting models where you have to pick a committee of size k from all the candidates. They're trying to find a rule that guarantees you get an approximate core, which is getting better than just knowing if an exact core even exists at all.
Lu: Exactly. The paper focuses on the weighted sequential Phragmén rule, which is a natural way to build this committee one candidate at a time while managing how much weight each voter has assigned to candidates. It's investigating whether this specific process always yields a two-stable committee of size k for any positive weights and any tie-breaking method.
Meng: But what does "two-stable" mean in practice? Is it better than the old guarantees we’ve seen, like the three point six five one stability mentioned by Gao, Sun, and Vondrák?
Tom: Right. So the core improvement here is that this rule always gives us a two-stable committee for any set of voter weights and any way you handle ties between candidates. It's a stronger guarantee than what we had before EC two thousand twenty-six <ref:2609.29646#pg1>.
Jane: That sounds like it addresses the open question about finding small values of lambda greater than one where stability can be guaranteed, because they’re showing that two is achievable with this specific rule.
Lu: The proof structure is interesting because it uses a combinatorial analysis rather than relying on methods like Lindahl equilibrium and rounding approaches. They use several lemmas to show how the iterative process controls the loads of voters who might try to block the committee.
Meng: What kind of numbers are we talking about in terms of complexity? If we want to actually deploy this, does it run fast? I mean, a committee selection process needs to be efficient.
Tom: The algorithm itself is described as iterative, where you compute these funding heights for candidates not yet in the committee and pick the one with the minimum height. Then you update the loads of voters who approve that candidate to this new common height. It continues until you have a committee of size k, and they state that each step increases the total weighted load by exactly one, leading to a final bound L greater than or equal to k over n.
Title and authors: Jane: That sounds like the mechanics of how the rule actually works for someone who doesn't know math. It sounds like a kind of balancing act where you keep choosing the next candidate based on which one has the lowest "funding height" until you fill your committee slots.
Lu: The stability proof relies on something called an area lemma, which aggregates unused credit from candidates not in the committee to show that this weighted area is less than two times some load measure. Then Lemma three uses that to bound the coalition's load, which is critical for excluding those potential blockers.
Meng: So if we look at this from a production standpoint, what are the practical implications of these bounds? Does this mean we can actually trust an AI system to select a committee based on this rule?
Tom: The corollary states that the two core of every finite weighted approval election is always nonempty. This means there's always at least one committee that satisfies the two stability condition, no matter what voters approve of.
Jane: And for rationally encoded voter weights, they also say you can compute this two-stable committee in polynomial time using this rule <ref:2609.29646#pg1>. That’s a huge plus because it moves it from a theoretical existence proof to something actually computable efficiently for real-world scenarios with rational inputs.
Lu: They also mentioned that the unit cost candidates are used in an essential way, and they flag that adapting the load-update technique to non-unit candidate costs is still an open question in their work.
Meng: That's a fair caution. If we move to real systems where candidates have different costs—like different levels of resource commitment—we might need a different kind of analysis for this load-update method.
Tom: Exactly, Meng. And they also questioned whether simply having correlations between omitted candidates could provide enough strengthening in the sum-of-squares estimate to beat the factor two stability or even reach that exact core we're aiming for.
Jane: So, to wrap up, this paper shows that by using the weighted sequential Phragmén rule, we can always find a committee guaranteed to be two-stable in an approval election. This is an improvement on previous guarantees and gives us a way to compute it efficiently if the voter weights are rational.
Title and authors: Lu: The main implication is proving that for this specific voting rule, the set of all committees satisfying the two stability condition is never empty. It solidifies a practical method for getting close to core stability in these approval-based settings.
Meng: For us on deployment, it means we have a concrete procedure with a polynomial time bound when inputs are rational, which is much better than just saying an approximate core exists somewhere theoretically.
Tom: So, the title of the paper is "Sequential Phragmén Guarantees two-Approximate Core Stability," and it establishes that this specific sequential rule always returns a two-stable committee for any positive voter weights and arbitrary tie-breaking <ref:2609.29646#pg1,Sequential Phragmén Guarantees 2-Approximate Core Stability>.
Jane: It’s a solid result for anyone interested in finding practical ways to select representative committees when dealing with weighted approvals. This gives us a better tool than we had before.
Lu: The work builds on previous research into lambda-stability, specifically showing that the factor can be pushed from something like three point six five one up to two using this new rule.
Meng: It's important to remember that this proof uses unit-cost candidates and integer-valued approval utilities in a specific way, so it might not directly translate if we introduce non-unit costs or more complex utility structures.
Tom: Right, and the paper does acknowledge those limitations. It doesn't claim to solve the exact core problem, just that it always finds something two-stable.
Jane: So, for listeners who don't read papers: this paper shows a specific way of choosing a committee that is guaranteed to be quite stable—two-stable—even when things are complex and weighted.
Lu: The real value here is showing how the sequence of load updates in the rule controls the ex post group stability, which is what we need for reliability.
Meng: For implementation, if we can compute this efficiently with rational weights, that’s a big win because it means an AI system could potentially support these kinds of weighted selection tasks quickly.
Tom: So, to sum up: the paper "Sequential Phragmén Guarantees two-Approximate Core Stability" proves that this specific voting rule always finds a committee guaranteed to be two-stable, and it can be computed in polynomial time for rational voter weights <ref:2609.29646#pg1,Sequential Phragmén Guarantees 2-Approximate Core Stability>.
Jane: It's a step forward in understanding how to get reliable committee selection in approval voting when you have different voter weights involved. We’ll see what other papers do next.
The paper's summary: Tom: So, this paper, "Sequential Phragmén Guarantees two-Approximate Core Stability," basically proves that there's a specific way to pick a committee—the weighted sequential Phragmén rule—and it always results in a committee that is two-stable.
Jane: Two-stable means we get a good approximation of the true core, which is that perfect one stability point we talked about earlier. It’s like getting close enough to the right answer without having to solve the whole impossible puzzle perfectly.
Lu: The main thing this paper does is show that this specific rule works for *any* positive voter weights and *any* way you break ties between candidates, which is a big deal because those tie-breaking rules are often messy in real elections.
Meng: So what’s the actual win here? Is it just that we can pick a committee that isn't totally broken? What does "two" actually mean in this context when it’s not one?
Tom: It means the total weight of voters who strictly prefer any alternative set of candidates is less than two times their proportional share of the total seats. It's a factor of two margin, which is better than what previous researchers could guarantee, which was three point six five one stability.
Jane: That’s a concrete improvement on the old numbers we saw in other work. It shows that this sequential process gives us more reliability when picking representatives from complex voting scenarios.
Lu: The authors use a really clever combinatorial analysis instead of relying on things like Lindahl equilibrium, which is why they can guarantee this stability without needing those other complicated setups.
Meng: I’m still wondering about the practical stuff. If we want to actually run an AI system to do this selection, does it stay fast? How much computational overhead are we talking about here?
Tom: The paper shows that when you use the weighted sequential Phragmén rule, you can compute this two-stable committee in polynomial time if your voter weights are rationally encoded. That’s a huge win for deploying these kinds of selection tools.
Jane: So, it’s not just a theoretical existence proof anymore; they give us an efficient algorithm that actually works for real-world inputs when the weights are rational.
Lu: And they also have this corollary which states that the two core is never empty at all, no matter what voters approve of. That’s a solid existence statement for approximate core stability.
Meng: Okay, so we have a method to find an approximate core efficiently for rational inputs, but what about when the voter weights aren't rational? Does this rule still work then?
Tom: The paper does have some caveats on that. They mention that while the algorithm works well with rationally encoded weights, adapting the load-update technique to non-unit candidate costs is still an open question for future work.
Jane: So, there’s a clear path forward for practical deployment with rational inputs, but there are still unknowns regarding more complex scenarios like non-unit costs.
Lu: They also questioned whether just having some correlation between candidates you didn't pick could be enough to get past that factor two stability threshold or even reach that exact core we want.
Tom: So, the big idea is this specific rule gives us a solid, computable guarantee of two-stability under a wide range of conditions, which is better than what we knew before.
Jane: This result helps us build more dependable committee selection systems when dealing with weighted approval voting models. We'll see if other papers can tackle the exact core problem next.
The paper's improvements: Tom: So we’re looking at how these authors suggest making the original paper on sequential Phragmén Guarantees even better, and they have a few ideas for improvement.
Jane: What’s the biggest suggestion they make about refining this specific rule? Is it about changing the stability number or something else entirely?
Lu: They point out that while this rule guarantees two-stability, it relies heavily on using unit cost candidates and integer values for approval utilities, which is a limitation.
Meng: So they’re saying the method is only as good as those specific inputs? That means if we move to real-world scenarios with different candidate costs, this exact load-update technique might not work as smoothly.
Tom: Exactly. They suggest that to make this more general, you have to figure out how to adapt that load-update technique so it handles non-unit candidate costs without breaking the whole mechanism.
Jane: That makes sense because in a real election, candidates don't all cost the same amount of something; they have different resource commitments.
Lu: They also raised a point about correlations between candidates you leave out, wondering if those could provide enough extra strength to beat that factor two stability or even hit that exact core we’re aiming for.
Tom: That’s interesting because it shifts the focus from just the voting rule itself to how much information we can use about voters who didn't vote for someone.
Jane: It suggests that maybe adding some context about why certain people didn't approve of a candidate could help us get closer to perfect stability.
Meng: From an engineering standpoint, I’m worried about that correlation stuff. If the estimation gets too messy with more variables, running the AI model to calculate those correlations might blow up the computational cost at scale.
Lu: Lalam confirms that based on the literature we have access to, they are fairly sure this direction of strengthening stability through external information is a plausible path for future research.
Tom: So, the improvement isn't just about tweaking one number; it’s about finding a more robust way to calculate those load updates when things get messy with costs and correlations.
Jane: It sounds like they are pushing the research toward creating a more flexible rule that can handle a wider variety of real-world election data.
Lu: Yes, the implication is that this paper sets up a clear roadmap for how future work should approach extending these types of stability guarantees beyond their current integer-valued constraints.
Tom: So, the next step isn't just running the model on rational weights; it’s figuring out how to generalize the core mechanism itself.
Jane: It’s a solid foundation, but they're clearly pointing toward a more adaptable system for complex voting environments.
Conclusion: Tom: So we’ve looked at how the paper "Sequential Phragmén Guarantees two-Approximate Core Stability" shows that this specific rule always finds a committee that is two-stable, which is an improvement over previous guarantees.
Jane: It really boils down to this: for any finite weighted approval election, there is always a way to pick your committee using the weighted sequential Phragmén rule that gives you a factor of two stability guarantee.
Lu: The main thing here is proving that this specific iterative process controls the ex post group stability, meaning it’s reliable in practice.
Meng: I think for deployment, the polynomial time computation for rational weights is what really matters right now; if we can run this fast on real traffic data that fits our model structure, that’s a practical win.
Lalam: I'm confident in my assessment; the mathematical machinery used in "Sequential Phragmén Guarantees two-Approximate Core Stability" strongly supports the claim of guaranteed two-stability for this rule.
Tom: It shows we can achieve a stronger approximation than before, moving from three point six five one stability up to two stability with this specific voting mechanism.
Jane: So, the implication is that for anyone building an approval system, adopting this sequential approach gives them a more reliable baseline than what they might have used previously.
Lu: The authors are also flagging that adapting the load-update technique to handle non-unit candidate costs is still an open question because of those specific integer values they relied on.
Meng: That’s a fair caveat; if we move to a more realistic system where candidates have different resource requirements, we’ll need a new analysis for that specific mechanism.
Lalam: I agree with Meng; the current proof is very tied to those unit costs and integer utilities, so extending it requires new mathematical tools.
Tom: So, the paper gives us a concrete tool—the weighted sequential Phragmén rule—that guarantees a two-stable outcome under many conditions.
Jane: It’s a step forward in understanding how we can get dependable committee selection when voter weights are involved in the decision process.
Lu: This work sets up a clear roadmap for future research on extending these stability guarantees beyond their current integer constraints and unit cost assumptions.
Meng: For the engineers out there, this means having a polynomial time algorithm ready to go if you can keep your input data structured rationally.
Lalam: I'm sure the literature will build on this foundation to tackle those more complex scenarios we discussed earlier regarding costs and correlations.
Rensselaer Polytechnic Institute · Beijing Normal University-Zhuhai · Beijing Normal-Hong Kong Baptist University
cs.GT
Submitted: 2026-09-11
Updated: 2026-11-10
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Importance score: 89/100
The gist: Sequential Phragmén Guarantees 2-Approximate Core Stability is a research paper proving that a specific voting rule can always produce a committee that is at least 2-stable in approval-based…
Key concepts
- Approval-based Committee Elections
- This is a voting model where voters select a subset of candidates they approve of. The goal is to form a fixed-size committee that best represents these voter preferences. Stability measures how well the selected committee reflects the collective preferences.
- $\lambda$-Stability
- A committee $W$ is $\lambda$-stable if no alternative set of candidates $T$ has a total weight strictly preferring it more than $\lambda$ times its proportional share of voters. The exact core corresponds to $\lambda=1$, which is the ideal, perfectly representative outcome.
- Weighted Sequential Phragmén Rule
- This is a specific algorithm used to select candidates iteratively. It works by assigning 'funding heights' to candidates and repeatedly choosing the candidate with the minimum height. Voters who approve that candidate have their loads raised, ensuring a structured selection process.
- Approximate Core Stability
- Since finding the exact core ($\lambda=1$) is hard, this concept deals with finding committees that are 'close' to perfect representation. The paper establishes a guarantee for $\lambda=2$, meaning the chosen committee is reliably close to the ideal outcome.
Terminology
Summary
Sequential Phragmén Guarantees 2-Approximate Core Stability is a research paper proving that a specific voting rule can always produce a committee that is at least 2-stable in approval-based committee elections, which improves upon previous guarantees and addresses the open problem of finding small values of lambda greater than 1 for which stability can be guaranteed
The Problem Context
Approval-based committee voting is a fundamental model where voters specify a subset of candidates they approve of, and the goal is to select a fixed-size committee that represents voter preferences For a nonempty subset of candidates T, the committee W is λ-stable if the total weight of voters who strictly prefer T is less than λ times the proportional share nT/k The exact core corresponds to lambda = 1 stability, which remains a major open problem in approval-based committee voting
The Proposed Rule and Main Result
The weighted sequential Phragmén rule is investigated as a natural weighted version of the classical sequential Phragmén voting rule The authors show that this rule always returns a 2-stable committee for arbitrary positive real voter weights, regardless of how ties between candidates are broken This result improves the 3.651-stability guarantee previously established by Gao, Sun, and Vondrák [EC 2026]
Proof Structure and Key Lemmas
The proof utilizes a purely combinatorial analysis that differs from Lindahl-equilibrium-and-rounding approaches The proof relies on several lemmas to establish the stability guarantee, including Lemma 1 which records basic accounting facts and justifies the water-filling interpretation Lemma 2 provides a central execution-history estimate by showing that the area lemma implies a bound on the blocking coalition's load Lemma 3 translates integer-valued utility comparisons into a bound on the coalition’s load, which is crucial for excluding factor-two blockers
Implications and Future Directions
The theorem provides an existence statement for the approximate core, showing that the 2-core of every finite weighted approval election is nonempty This result improves upon previous guarantees by achieving a factor of 2 stability The authors note that this proof uses unit-cost candidates and integer-valued approval utilities in an essential way, suggesting that adapting the load-update technique to non-unit candidate costs remains an open question They also question whether correlations between omitted candidates can strengthen the sum-of-squares estimate enough to beat factor two or reach the exact core
Algorithm Description
The weighted sequential Phragmén rule is implemented via Algorithm 1, which involves iteratively computing funding heights θl(c) for candidates not yet selected and choosing the candidate with the minimum height In each step, the loads of voters who approve the chosen candidate are raised to this common height The process continues until a committee of size k is formed
Model Definition
The model defines an instance by specifying a set of candidates C, voters N with positive weights wi, and approval sets Ai for each voter The approval utility ui(D) for voter i is defined as the number of candidates in D that voter i approves of, which is Ai ∩ D A committee W is λ-stable if no alternative T has a total weight strictly preferring it greater than λ times the proportional share nT/k The assumption is made that every candidate is approved by at least one voter, meaning S i∈N Ai = C
Weighted Sequential Phragmén Implementation Details
The funding height θl(c) of a candidate c is the unique solution to Fc,l(θl(c)) = 1, where Fc,l(x) is defined as X i:c∈Ai wi max[0, x − l i] The algorithm selects the candidate c in C excluding W that minimizes θl(c) After selection, the loads of approving voters are updated to max[l i, θl(c)] This iterative process continues until W equals k The total weighted load increases by exactly one in each step, leading to the final bound L ≥ k/n
Stability Proof Mechanics
The stability proof studies the gaps between successive moments at which a voter's load increases The area lemma aggregates unused credit of unelected candidates, showing that for any set R and S, the weighted area is strictly less than 2RL Lemma 3 uses this to show that L wt(S) < H + p/2RL wt(S) under certain conditions The final contradiction arises from combining these bounds to exclude factor-two blockers via Lemma 4
Related Work Comparison
Sequential Phragmén has been studied through proportional representation axioms, which protect specially structured cohesive groups In contrast, core stability quantifies over every coalition and every alternative set of candidates, rather than only structured cohesive groups as in proportional-representation notions The result complements this line of work by establishing a constant approximate-core-stability guarantee for sequential Phragmén Furthermore, the proof is combinatorial and draws directly on a single sequential water-filling execution, showing how the sequence of load updates controls ex-post group stability The result does not settle exact-core nonemptiness
Corollary and Computational Aspect
Corollary 1 states that the 2-core of every finite weighted approval election is nonempty Moreover, for rationally encoded voter weights, a 2-stable committee can be computed in polynomial time using weighted sequential Phragmén The proof shows that every execution allowed by the rule, including every choice among tied minimum-height candidates, has the desired stability guarantee This implies that for rationally encoded voter weights, a 2-stable committee can be computed in polynomial time using weighted sequential Phragmén The result is stronger than an existence result by showing that every execution allowed by the rule, including every choice among tied minimum-height candidates, has the desired stability guarantee
Additional Related Work Context
The authors contrast their work with other relaxations of core stability, such as those from Peters and Skowron [12], which show factor-2 utility-based approximations or O(log k) guarantees for Equal Shares These guarantees differ from the λ-stability considered here, which instead relaxes the coalition-size threshold The authors also note that candidate costs would change both the one-unit payment identity and the scalar accounting, while general cardinal utilities would remove the integral one-unit gain in (13) The analysis excludes factor-two blockers by showing that equality in Lemma 4 is only possible when x = 0 and z = 2y
Final Summary Statement
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved AI systems can be designed to select committees using weighted sequential Phragmén, which guarantees a 2-stable committee for any finite weighted approval election under arbitrary tie-breaking and for all positive voter weights.
-
The improved system can compute a 2-stable committee in polynomial time when voter weights are rationally encoded, offering an efficient algorithm for decision support in approval-based selection tasks.
-
The system can provide a stronger approximation guarantee than previously known results by improving the lambda-stability guarantee from 3.651 to 2, which enhances the reliability of representative committee formation in complex voting scenarios.
Abstract
We study approximately stable committee selection under approval preferences, following Cheng et al. [EC 2019] and Jiang, Munagala, and Wang [STOC 2020]. In an approval-based committee election, n voters each approve a subset of the candidates, and a committee of size k is selected. A size- k committee is λ-stable if, for every nonempty subset T of candidates, the number of voters who strictly prefer T is less than λ times the proportional share nT over k. We consider sequential Phragmén, a classical polynomial-time voting rule, and prove that it always returns a 2-stable committee. This implies that the 2-core is always nonempty and improves upon the 3.651-stability guarantee of Gao, Sun, and Vondrák [EC 2026]. The guarantee also extends to weighted voters and is tight even for unweighted elections: for every 1 at mostλ<2, sequential Phragmén can return a committee that is not λ-stable. Compared with the exact-core algorithm developed in concurrent work by Becker, Greger, and Peters [arXiv 2026], sequential Phragmén is simpler to implement, and our proof of its 2-stability is elementary.
Sources
- Core Existence in Approval-Based Committee Elections with up to Five Voter Types
- Computation of Approximately Stable Committees in Approval-based Elections
- Phragm'en's and Thiele's election methods
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments