Scholarlink

<p>This paper studies the complexity of two microbribery problems under the model of group identification. In these problems, we are given a subset of distinguished individuals, and the questions are whether these individuals can be made socially qualified or whether they can be made exactly the socially qualified individuals, respectively, by modifying a limited number of entries in the qualifications-profile. For consent rules, the consensus-start-respecting rule, and the liberal-start-respecting rule, we obtain many NP-hardness results and polynomial-time solvability results. We also study the problems in <i>r</i>-profiles where each individual qualifies exactly&#xa0;<i>r</i> individuals.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Microbribery in Group Identification

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年4月9日

查看全文
  • Gábor Erdélyi,
  • Yongjie Yang

摘要

This paper studies the complexity of two microbribery problems under the model of group identification. In these problems, we are given a subset of distinguished individuals, and the questions are whether these individuals can be made socially qualified or whether they can be made exactly the socially qualified individuals, respectively, by modifying a limited number of entries in the qualifications-profile. For consent rules, the consensus-start-respecting rule, and the liberal-start-respecting rule, we obtain many NP-hardness results and polynomial-time solvability results. We also study the problems in r-profiles where each individual qualifies exactly r individuals.