12:54
官方账号arXiv cs.AI@Alexandra Lassota, Krzysztof Sornat
推荐理由：这篇论文把PAV等Thiele规则在Voter Interval域上的复杂度向前推了一步，还解决了两个开放问题，做计算社会选择的人可以看看。
计算社会选择
共 1 条相关 AI 资讯
7月31日
12:54
该论文研究审批制委员会选举中Thiele投票规则的赢家确定问题，这类规则由固定权重向量参数化。作者基于选民审批关系分析最优解结构，为PAV等规则设计了Voter Interval（VI）域上的FPT算法。在VI域上，每个候选人被一段连续选民的区间批准，文中证明所有Thiele规则在该域上关于某个参数是FPT，而该参数在一般实例上即使取常数值也令问题NP难。论文还解决了PAV的两个开放问题：当每个候选人至多被两名选民批准时给出多项式时间算法，并以获胜委员会总分数为参数给出FPT算法。