论文标题
扩大小组识别中操纵攻击的复杂性理论分析
Broadening the Complexity-theoretic Analysis of Manipulative Attacks in Group Identification
论文作者
论文摘要
在小组识别问题中，我们得到了一组个人，并被要求确定他们中有一个具有社会资格的子集。集合中的每个人都对谁应该被视为社会资格。根据这些相互观点，可以使用几种不同的规则来确定具有社会资格的子集。在操纵性攻击中，局外人试图利用所使用的规则的工作方式，目的是将选择过程的结果更改为他们的喜好。 近年来，小组识别中基于群体控制和基于贿赂的操纵攻击的复杂性一直是激烈研究的主题。但是，这张照片远非完整，还有许多与确切困难的问题或某些规则免于某些攻击有关的问题。 补充先前的结果，我们研究了小组微径回对于所谓的保护性问题实例的复杂性；也就是说，最初，来自建设性目标集的所有个人都已经具有社会资格。此外，我们通过删除个人的同意规则，共识开始的尊重规则和自由派尊重的规则来研究群体控制的放松变体。基于现有文献，我们还为迭代共识类型的三个新的社会规则形式化，并为这些规则提供了群体控制和贿赂问题的全面复杂性分析。
In the Group Identification problem, we are given a set of individuals and are asked to identify a socially qualified subset among them. Each individual in the set has an opinion about who should be considered socially qualified. There are several different rules that can be used to determine the socially qualified subset based on these mutual opinions. In a manipulative attack, an outsider attempts to exploit the way the used rule works, with the goal of changing the outcome of the selection process to their liking. In recent years, the complexity of group control and bribery based manipulative attacks in Group Identification has been the subject of intense research. However, the picture is far from complete, and there remain many open questions related to what exactly makes certain problems hard, or certain rules immune to some attacks. Supplementing previous results, we examine the complexity of group microbribery on so-called protective problem instances; that is, instances where all individuals from the constructive target set are already socially qualified initially. In addition, we study a relaxed variant of group control by deleting individuals for the consent rules, the consensus-start-respecting rule, and the liberal-start-respecting rule. Based on existing literature, we also formalize three new social rules of the iterative consensus type, and we provide a comprehensive complexity-theoretic analysis of group control and bribery problems for these rules.
