How to Put Through Your Agenda in Collective Binary Decisions
How to Put Through Your Agenda in Collective Binary Decisions
复制标题
DOI：
10.1145/2837467
复制
发表时间：
2013-11
期刊：
影响因子：
--
通讯作者：
N. Alon;Robert Bredereck;Jiehua Chen;Stefan Kratsch;R. Niedermeier;G. Woeginger
中科院分区：
文献类型：
--
作者：
N. Alon;Robert Bredereck;Jiehua Chen;Stefan Kratsch;R. Niedermeier;G. Woeginger
我们考虑以下决策情况：一个选民必须就一组提案找到协议，每个提案都必须接受或拒绝。投票 - 反对剩下的人。所有选民（或严格的大多数选民）接受这项选票，我们表明，在负面方面，这两个问题都是NP的完整，在积极方面，他们是固定参数相对于总数关于选民的总数，我们研究了进一步的自然参数，并研究了它们对这两个问题的计算复杂性的影响，从而提供了障碍和棘手的结果。在选民人数方面，公认投票最差的案例大小的组合界限。
We consider the following decision-making scenario: a society of voters has to find an agreement on a set of proposals, and every single proposal is to be accepted or rejected. Each voter supports a certain subset of the proposals—the favorite ballot of this voter—and opposes the remaining ones. He accepts a ballot if he supports more than half of the proposals in this ballot. The task is to decide whether there exists a ballot approving a specified number of selected proposals (agenda) such that all voters (or a strict majority of them) accept this ballot. We show that, on the negative side, both problems are NP-complete, and on the positive side, they are fixed-parameter tractable with respect to the total number of proposals or with respect to the total number of voters. We look into further natural parameters and study their influence on the computational complexity of both problems, thereby providing both tractability and intractability results. Furthermore, we provide tight combinatorial bounds on the worst-case size of an accepted ballot in terms of the number of voters.