A Multivariate Complexity Analysis of Lobbying in Multiple Referenda
A Multivariate Complexity Analysis of Lobbying in Multiple Referenda
复制标题
多次公投中游说的多元复杂性分析
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Stefan Kratsch
中科院分区：
文献类型：
--
作者：
Robert Bredereck;Jiehua Chen;Sepp Hartung;R. Niedermeier;O. Suchý;Stefan Kratsch
我们扩展了Christian等人[经济设计评论2007]在多次公投中的游说方面的工作，首先对np完全游说问题的计算复杂性进行了更细粒度的分析。在这里，给定一个二进制矩阵，列表示要投票的问题，行对应于对每个问题进行二进制投票的选民。如果在相应的列中投票的多数为1，则该问题被批准。目标是通过将最小行数修改为全1行来批准所有问题。在我们的多元复杂性分析中，我们对游说的计算复杂性的本质提出了一个更全面的观点，根据要采用的各种问题参数化，提供了（参数化的）可跟踪性和难处理性结果。此外，我们还展示了关于游说的高效和有效预处理的不存在性结果，并引入了自然变体，如受限游说和部分游说。
We extend work by Christian et al. [Review of Economic Design 2007] on lobbying in multiple referenda by first providing a more fine-grained analysis of the computational complexity of the NP-complete Lobbying problem. Herein, given a binary matrix, the columns represent issues to vote on and the rows correspond to voters making a binary vote on each issue. An issue is approved if a majority of votes has a 1 in the corresponding column. The goal is to get all issues approved by modifying a minimum number of rows to all-1-rows. In our multivariate complexity analysis, we present a more holistic view on the nature of the computational complexity of Lobbying, providing both (parameterized) tractability and intractability results, depending on various problem parameterizations to be adopted. Moreover, we show non-existence results concerning efficient and effective preprocessing for Lobbying and introduce natural variants such as Restricted Lobbying and Partial Lobbying.