Picture a committee election where every voter simply ticks the names they like. Twenty candidates, five seats, a few thousand ballots. It looks like the kind of arithmetic a laptop should finish before you finish your coffee. Under one popular family of rules, it is not. Finding the winning committee is a problem that computer scientists have shown can blow up beyond any practical reach, and a good deal of research has gone into figuring out exactly when it does.
Alexandra Lassota and Krzysztof Sornat have added a set of answers. Their paper, posted to arXiv on 30 July 2026, studies winner determination under what are called Thiele voting rules. A conference version appeared at AAAI 2026.
The idea behind a Thiele rule is easier than the name suggests. Each voter hands in an approval ballot: a list of the candidates they would be happy to see elected. Once a committee is chosen, a voter's satisfaction depends only on how many of their approved candidates made it in. A fixed weight vector spells out that relationship. Give the first approved winner a weight of 1, the second another 1, and so on, and you get a rule that just counts total approvals. Make each additional winner count for less (1, then a half, then a third) and you get Proportional Approval Voting, or PAV, a rule designed so that a minority bloc gets representation roughly in proportion to its size rather than being shut out entirely by a slim majority.
PAV is the one people want to use, and it is also the one that is hard to compute. That tension is what the paper works on.
What the structure buys you
Lassota and Sornat start by looking at elections through the candidates' approval sets: for each candidate, which voters approved them. Those sets overlap, nest inside one another, or sit apart, and the authors show that this pattern of overlap alone constrains which committees can possibly be optimal, under any fixed Thiele rule. It is a structural result rather than an algorithm, but the algorithms are built on top of it.
The main application is to a restricted setting known as the Voter Interval domain. The condition is this: you can line the voters up in some order so that every candidate's supporters form one unbroken run. Think of voters arranged along a single axis of opinion, with each candidate appealing to a contiguous stretch of it and nobody outside that stretch. Real elections are messier, but this kind of one-dimensional structure is a standard idealization in the field, and whether PAV becomes tractable on it has been one of the area's central open questions.
On Voter Interval instances, the authors give algorithms that are fixed-parameter tractable, usually shortened to FPT. The term describes a specific and useful kind of efficiency. Instead of demanding that an algorithm be fast in every respect, you single out one quantity, the parameter, and accept a running time that may grow explosively in that parameter alone while staying polynomial in the size of the election. If the parameter stays small in practice, the algorithm is usable. The sharpest version of the result: every Thiele rule on Voter Interval instances is FPT with respect to a parameter for which the general problem is NP-hard even when that parameter is held at a constant. In other words, the structure is doing real work. Nail down the parameter without the interval structure and the problem is still intractable; add the structure and it yields.
The paper also resolves two questions left open in earlier literature. First, when each candidate is approved by at most two voters, PAV and other Thiele rules can be decided in polynomial time. Second, the problem is FPT when parameterized by the total score of a winning committee, meaning the summed satisfaction the rule assigns.
Why it matters
Proportional rules like PAV are not academic curiosities. Participatory budgeting, where residents vote on which local projects a city funds, uses approval-style ballots, and so do various forms of committee and board selection. The appeal of PAV is that it resists the pattern where 51 percent of voters take 100 percent of the seats. The obstacle to adopting it has partly been that computing the winner is hard, which pushes practitioners toward greedy approximations that do not carry the same guarantees.
What this paper offers is not a fast algorithm for arbitrary elections. That almost certainly does not exist. It offers something narrower and more honest: a map of which structural assumptions are enough to make the exact computation feasible, and a proof that one natural assumption, voters arranged along a single dimension, is one of them. The polynomial-time result for candidates with at most two approvers, and the score-parameterized algorithm, fill in two more coordinates on that map.
A caveat worth stating plainly. This is theory. The paper reports complexity results, not implementations or benchmarks on real ballots, and FPT running times can hide constants large enough to matter. The abstract makes no claim about practical speed. What it claims is that a line has been drawn where none was drawn before, on a question the field has been circling for years.