Microbribery in Group Identification

Abstract

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 individ uals, 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.