操纵$K$-批准选举的复杂性

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
计算社会选择理论中的一个重要问题是代理人之间不良行为的复杂性，如选举系统中的控制、操纵和贿赂。这些类型的投票策略在个人层面上往往是诱人的，但对代理作为一个整体来说是灾难性的。因此，在难以确定这种战略的地方建立选举制度是一个重要目标。一组有趣的选举是评分协议。以前在这方面的工作表明，在涉及固定数目的候选人的情况下，滥用选举制度的复杂性，以及在博尔达等数目不限的候选人的情况下，滥用选举制度的复杂性。相反，我们将选举误用的计算复杂性的结果推广到无限多个计分协议在无限多个候选人上的情况，这是第一步。有趣的系统家族包括$k$-批准和$k$-否决选举，在这些选举中，选民将$k$-候选人从候选人集中区分开来。我们的主要结果是根据这些家庭的复杂性来划分这些家庭的问题。我们通过证明它们是多项式时间可计算的、NP困难的或与另一个感兴趣的问题等价的多项式时间来做到这一点。我们还证明了选举系统中的操纵和一些图论问题之间的惊人联系。
---
英文标题：
《The Complexity of Manipulating $k$-Approval Elections》
---
作者：
Andrew Lin
---
最新提交年份：
2012
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  An important problem in computational social choice theory is the complexity of undesirable behavior among agents, such as control, manipulation, and bribery in election systems. These kinds of voting strategies are often tempting at the individual level but disastrous for the agents as a whole. Creating election systems where the determination of such strategies is difficult is thus an important goal.   An interesting set of elections is that of scoring protocols. Previous work in this area has demonstrated the complexity of misuse in cases involving a fixed number of candidates, and of specific election systems on unbounded number of candidates such as Borda. In contrast, we take the first step in generalizing the results of computational complexity of election misuse to cases of infinitely many scoring protocols on an unbounded number of candidates. Interesting families of systems include $k$-approval and $k$-veto elections, in which voters distinguish $k$ candidates from the candidate set.   Our main result is to partition the problems of these families based on their complexity. We do so by showing they are polynomial-time computable, NP-hard, or polynomial-time equivalent to another problem of interest. We also demonstrate a surprising connection between manipulation in election systems and some graph theory problems.
---
PDF链接：
https://arxiv.org/pdf/1005.4159

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：复杂性 manipulation manipulating Generalizing Intelligence 作为 complexity 操纵 无限 such