这篇论文把PAV等Thiele规则在Voter Interval域上的复杂度向前推了一步，还解决了两个开放问题，做计算社会选择的人可以看看。
该论文研究审批制委员会选举中Thiele投票规则的赢家确定问题，这类规则由固定权重向量参数化。作者基于选民审批关系分析最优解结构，为PAV等规则设计了Voter Interval（VI）域上的FPT算法。在VI域上，每个候选人被一段连续选民的区间批准，文中证明所有Thiele规则在该域上关于某个参数是FPT，而该参数在一般实例上即使取常数值也令问题NP难。论文还解决了PAV的两个开放问题：当每个候选人至多被两名选民批准时给出多项式时间算法，并以获胜委员会总分数为参数给出FPT算法。
Algorithms for Structured Elections under Thiele Voting Rules
We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by a fixed weight vector that specifies how a voter's satisfaction depends on the number of approved candidates elected. We first analyze the structure of optimal solutions based on the sets of voters who approve each candidate---that is, how voters' approval ballots induce dependencies between candidates---revealing constraints on a winning committee under any fixed Thiele voting rule. Using this, we design FPT algorithms for Proportional Approval Voting (PAV) and other Thiele rules on a natural restricted domain known as the Voter Interval (VI) domain---that is, after a suitable ordering of voters, each candidate is approved by a consecutive interval of voters. In particular, we show that every Thiele rule on VI is FPT with respect to a parameter for which the problem is NP-hard on general instances, even when the parameter takes constant values. Our results advance the understanding of the computational complexity of PAV on Voter Interval instances, which remains one of the central open questions in this area. We further resolve two open questions from the literature on PAV (and other Thiele voting rules) by providing a polynomial-time algorithm for instances where each candidate is approved by at most two voters, and an FPT algorithm parameterized by the total score of a winning committee.