# Manipulative Attacks in Group Identification

#### Abstract

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 this paper, we consider the consensus-start-respecting rule, the liberal-start-respecting rule, and the consent rules.

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, deleting, or partitioning individuals, as well as bribing individuals to change their opinion. In this paper, we provide an overview of the feasibility and the computational complexity of manipulative attacks in group identification.

## 1. Introduction to Group Identification

^{[1]}and Du et al.

^{[2]}.

*profile over*. For individuals

*. We write* qualifies

*.* disqualifies

**Example:**Let

### 1.1. Social Rules

*social rule*is applied. A social rule is a function

*socially qualified individuals of* with respect to and .

^{[3]}

^{[4]}

^{[5]}. Therefore, we make these rules the subject of our analysis in this paper.

**Consensus-start-respecting rule**

**Liberal-start-respecting rule**

**Consent rules**

- •If
then if and only if . - •If
then if and only if .

## 2. Introduction to Manipulative Attacks

*attacker*) tries to reach a certain strategic objective. There are four kinds of strategic objectives: With a

*constructive*objective, the attacker tries to ensure that certain individuals will be socially qualified. With a

*destructive*objective, the attacker tries to ensure that certain individuals will be socially disqualified. With an

*exact*objective, the attacker tries to precisely specify for each individual whether they should be socially qualified or not. Finally, in the most general setting (also called

*constructive+destructive*), the attacker tries to make certain individuals socially qualified and certain other individuals socially disqualified.

*group control*scenarios, the attacker can add, delete, or partition individuals. In

*group bribery*scenarios, the attacker can bribe individuals to change their opinion. Each strategic objective can be combined with each means of manipulation to form a group control (resp. group bribery) problem. For example, consider the

*Destructive Group Control by Deleting Individuals*problem: In this scenario, the attacker is allowed to delete a certain number of individuals from the set, with the goal of making certain individuals in the remaining set socially disqualified.

*immune*to the manipulative attack. Otherwise, we say that the social rule is

*susceptible*to the manipulative attack, and we then try to classify the problem as either polynomial-time solvable or NP-hard. When the problem is NP-hard, it is possible for the attacker to reach their objective, but computing the solution is generally difficult. This implies that the used social rule offers at least some protection against the manipulative attack.

### 2.1. Problem Definitions

**Group Control by Adding Individuals:**In this scenario, only a subset of individuals

Given: |
A set |

Question: |
Is there a subset |

In other words, is there a way to add at most |

- •
-Constructive Group Control by Adding Individuals (CGCAI) where the set is dropped, - •
-Destructive Group Control by Adding Individuals (DGCAI) where the set is dropped, - •
-Exact Group Control by Adding Individuals (EGCAI) where we add the premise .

**Group Control by Deleting Individuals:**In this scenario, we start with an initial set

Given: |
A set |

Question: |
Is there a subset |

In other words, is there a way to delete at most |

- •
-Constructive Group Control by Deleting Individuals (CGCDI) where the set is dropped, - •
-Destructive Group Control by Deleting Individuals (DGCDI) where the set is dropped.

**Group Control by Partitioning of Individuals:**In this scenario, the attacker can organize the evaluation procedure as a two-stage process. In the first stage of the selection, the individuals are split into two partitions

Given: |
A set |

Question: |
Is there a subset |

In other words, is there a way to split the set of individuals into two partitions |

- •
-Constructive Group Control by Partitioning of Individuals (CGCPI) where the set is dropped, - •
-Destructive Group Control by Partitioning of Individuals (DGCPI) where the set is dropped, - •
-Exact Group Control by Partitioning of Individuals (EGCPI) where we add the premise .

**Group Bribery:**In the bribery problems, the attacker can bribe up to

Given: |
A set |

Question: |
Is there a way to obtain a profile |

In other words, is there a way to bribe at most |

- •
-Constructive Group Bribery (CGB) where the set is dropped, - •
-Destructive Group Bribery (DGB) where the set is dropped, - •
-Exact Group Bribery (EGB) where we add the premise .

**Group Microbribery:**In the microbribery model, the attacker can also bribe individuals to change their opinion, but needs to pay for each changed entry in

Given: |
A set |

Question: |
Is there a way to obtain a profile |

In other words, is there a way to change at most |

- •
-Constructive Group Microbribery (CGMB) where the set is dropped, - •
-Destructive Group Microbribery (DGMB) where the set is dropped, - •
-Exact Group Microbribery (EGMB) where we add the premise .

### 2.2. Problem Acronyms Overview

Acronym | Problem Name |

CGB | Constructive Group Bribery |

CGCAI | Constructive Group Control by Adding Individuals |

CGCDI | Constructive Group Control by Deleting Individuals |

CGCPI | Constructive Group Control by Partitioning of Individuals |

CGMB | Constructive Group Microbribery |

DGB | Destructive Group Bribery |

DGCAI | Destructive Group Control by Adding Individuals |

DGCDI | Destructive Group Control by Deleting Individuals |

DGCPI | Destructive Group Control by Partitioning of Individuals |

DGMB | Destructive Group Microbribery |

EGB | Exact Group Bribery |

EGCAI | Exact Group Control by Adding Individuals |

EGCPI | Exact Group Control by Partitioning of Individuals |

EGMB | Exact Group Microbribery |

GB | Group Bribery |

GCAI | Group Control by Adding Individuals |

GCDI | Group Control by Deleting Individuals |

GCPI | Group Control by Partitioning of Individuals |

GMB | Group Microbribery |

## 3. Computational Complexity of Group Control and Bribery

### 3.1. Constructive Group Control and Bribery

^{[6]}. Erdélyi et al.

^{[7]}showed the results for the bribery problem, and Boehmer et al.

^{[8]}extended their results to the microbribery problem.

Consent rules |
||||||||

CGCAI | I | I | I | NP-h | NP-h | NP-h | NP-h | NP-h |

CGCDI | I | P | NP-h | I | P | NP-h | P | I |

CGCPI | I | NP-h | NP-h | I | NP-h | NP-h | ? | I |

CGB | P | NP-h | NP-h | NP-h | NP-h | NP-h | P | P |

CGMB | P | P | P | P | P | P | NP-h | NP-h |