论文标题
在Chamberlin-Courant规则和Monroe规则下，多赢家选举的参数性顽固性
Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule
论文作者
论文摘要
回答Betzler等人的一个公开问题。 [Betzler等人，Jair'13]，我们解决了两个著名的代表投票规则下的多赢家确定问题的参数化复杂性：Chamberlin-Courant（Short CC）规则[Chamberlin和Courant，Apsr'83]和Monroe Rule [Monroe，APSR'95]。我们表明，在这两个规则下，问题是关于虚假陈述的总和$β$的问题，从而排除了任何$ f（β）\ cdot | i | i | i |^{o（1）} $ - 时间算法的存在，其中$ | i |表示输入实例的大小。
Answering an open question by Betzler et al. [Betzler et al., JAIR'13], we resolve the parameterized complexity of the multi-winner determination problem under two famous representation voting rules: the Chamberlin-Courant (in short CC) rule [Chamberlin and Courant, APSR'83] and the Monroe rule [Monroe, APSR'95]. We show that under both rules, the problem is W[1]-hard with respect to the sum $β$ of misrepresentations, thereby precluding the existence of any $f(β) \cdot |I|^{O(1)}$ -time algorithm, where $|I|$ denotes the size of the input instance.
