arXiv paper: Algorithms for Structured Elections under Thiele Voting Rules

A new preprint by Lassota and Sornat studies the computational difficulty of electing committees when voters cast approval ballots and outcomes are evaluated using Thiele voting rules (a class that includes Proportional Approval Voting, or PAV). The authors analyze how voter-approval patterns create dependencies among candidates and exploit that structure to design fixed-parameter tractable (FPT) algorithms for a restricted domain—the Voter Interval (VI) domain—where, after ordering voters suitably, each candidate appears in a contiguous block of approvals. They show that every Thiele rule on VI is FPT with respect to a parameter for which the general problem is NP-hard even at constant values. The work also gives a polynomial-time algorithm when each candidate receives at most two approvals, and an FPT algorithm parameterized by the total score of a winning committee, resolving two open questions from prior literature. The main open problem—the complexity of PAV on the VI domain—is not settled, but the paper advances understanding of its structure and tractability under related parameters. No new facts, performance claims, or practical implications beyond the stated theoretical F-