The complexity of bribery and control in group identification

摘要

The goal of this paper is to analyze the complexity of constructive/destructive bribery and destructive control in the framework of group identification. Group identification applies to situations where a group of individuals determine who among them are socially qualified. We consider consent rules, the consensus-start-respecting rule, and the liberal-start-respecting rule. Each consent rule is characterized by two positive integers s and t, and the socially qualified individuals are determined as follows. If an individual qualifies herself, then she is socially qualified if and only if there are in total at least s individuals qualifying her. Otherwise, she is NOT socially qualified if and only if there are in total at least t individuals disqualifying her. The liberal (resp. consensus)-start-respecting rule determines the socially qualified individuals recursively. In the first step, all individuals qualifying themselves (resp. qualified by all individuals) are socially qualified. Then, the procedure recursively adds individuals who are not socially qualified but are qualified by at least one socially qualified individual into the set of socially qualified individuals until no one can be added this way.