论文标题
操纵攻击和小组身份证
Manipulative Attacks and Group Identification
论文作者
论文摘要
小组识别问题要求根据成对估值在一组个人之间确定一个具有社会资格的亚组。有几种不同的规则可用于确定社会资格认证状况。在这项工作中，我们考虑同意规则，共识的尊重规则以及自由派探索的规则。 在群体识别的背景下，操纵攻击是局外人试图通过某些操纵手段来影响选择过程的结果。这些手段包括添加，删除或划分个人，以及贿赂个人改变意见。 在这项工作中，我们概述了小组识别中的操纵攻击以及部分配置文件的群体识别。特别是，我们研究了相应问题的计算复杂性。这项工作中介绍的大多数结果都是从文献中汇总的，但我们还显示了以前未研究的问题的结果。其中包括二进制配置文件和三元配置文件中的一般和精确的组控制，以及$ r $ profiles中的建设性组控制。对于许多考虑的问题，我们还研究了参数化的复杂性。
The group identification problem asks to identify a socially qualified subgroup among a group of individuals based on their pairwise valuations. There are several different rules that can be used to determine the social qualification status. In this work, we consider the consent rules, the consensus-start-respecting rule, and the liberal-start-respecting rule. In the context of group identification, a manipulative attack is the attempt by an outsider to influence the outcome of the selection process through certain means of manipulation. These means include adding, removing, or partitioning individuals, as well as bribing individuals to change their opinion. In this work, we provide an overview of manipulative attacks in group identification as well as group identification with partial profiles. In particular, we study the computational complexity of the corresponding problems. Most results presented in this work are aggregated from the literature, but we also show results for previously unstudied problems; these include general and exact group control in binary profiles and in ternary profiles, as well as constructive group control in $r$-profiles. For many considered problems, we also study the parameterized complexity.
