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

There are many situations where one needs to identify a socially qualified subgroup among a group of individuals. For instance, consider a facility whose members want to form a working group for a specific task. In this example, all members have pairwise opinions about whether each member is qualified for the task or not. Another example is when a group of autonomous agents wants to select those among them who are best suited to perform a particular job. Again, the selection in this example is based on the mutual valuations of the agents. To deal with scenarios like these, the group identification model has been developed.

In the following, we assume that the reader is familiar with the basics of graph theory (vertices, edges, arcs) and computational complexity theory (polynomial-time solvability, NP-hardness). For a consult, we refer to West^[1] and Du et al.^[2].

In the group identification model, we are given a set of individuals, each of whom has an opinion about which individuals are qualified in a certain way and which are not. Crucially, each individual also has an opinion about themselves.

Throughout this paper, we use

N

to denote the given set of individuals. The pairwise opinions of the individuals are represented by a function

φ : N \times N \to {- 1, 1}

called profile over $N$ . For individuals

a, b \in N

, we write

φ (a, b) = 1

when

a

thinks

b

is qualified and say $a$ qualifies $b$ . We write

φ (a, b) = - 1

when

a

thinks

b

is not qualified and say $a$ disqualifies $b$ .

A group identification instance

(N, φ)

is best represented as a directed graph

G = (V, E)

where

V = N

and

(a, b) \in E

if and only if

φ (a, b) = 1

Example: Let

N = {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}}

be a set of five individuals and

φ

a profile over

N

defined as follows (

φ (a_{i}, a_{j})

is given by the matrix entry in the

i

-th row and

j

-th column):

\begin{array}{rrrrrr} a_{1} & a_{2} & a_{3} & a_{4} & a_{5} \\ a_{1} & 1 & 1 & 1 & - 1 & 1 \\ a_{2} & - 1 & - 1 & 1 & - 1 & 1 \\ a_{3} & - 1 & 1 & 1 & - 1 & - 1 \\ a_{4} & 1 & 1 & 1 & 1 & - 1 \\ a_{5} & - 1 & 1 & 1 & - 1 & - 1 \end{array}

The graph representation of the above instance looks as follows:

Figure 1: The arc from an individual X to an individual Y indicates that X qualifies Y.

To determine the subset of socially qualified individuals for a given group identification instance, a so-called social rule is applied. A social rule is a function

f

that, given a group identification instance

(N, φ)

, outputs a subset

f (N, φ) \subseteq N

which we refer to as socially qualified individuals of $N$ with respect to $f$ and $φ$ .

In the literature, the consensus-start-respecting (CSR) rule, the liberal-start-respecting (LSR) rule, and the consent rules have received particular attention^[3]^[4]^[5]. Therefore, we make these rules the subject of our analysis in this paper.

Consensus-start-respecting rule

f^{CSR}

: This rule determines the socially qualified individuals iteratively. In a first step, all individuals who are qualified by everyone are considered to be socially qualified. Then, in each iteration, any individual who is qualified by any of the currently socially qualified individuals is added to the set of socially qualified individuals. Once no new individuals can be added, the iterative process terminates.

More formally, the initial set of socially qualified individuals is defined as

K_{0}^{C} (N, φ) = {a \in N : φ (a^{'}, a) = 1 for all a^{'} \in N} .

And for each positive integer

i

, the set of socially qualified individuals in the

i

-th iteration is defined as

K_{i}^{C} (N, φ) = K_{i - 1}^{C} (N, φ) \cup {a \in N : \exists a^{'} \in K_{i - 1}^{C} (N, φ) s.t. φ (a^{'}, a) = 1} .

We define

f^{CSR} (N, φ) = K_{i}^{C} (N, φ)

for the smallest

i

with

K_{i}^{C} (N, φ) = K_{i - 1}^{C} (N, φ)

Applying the CSR rule to the example instance depicted in Figure [1], we initially have

K_{0}^{C} (N, φ) = {a_{3}}

since

a_{3}

is the only individual who is qualified by everyone. Because

a_{3}

qualifies

a_{2}

, we get

K_{1}^{C} (N, φ) = {a_{2}, a_{3}}

. Since

a_{2}

also qualifies

a_{5}

, we then get

K_{2}^{C} (N, φ) = {a_{2}, a_{3}, a_{5}}

. The individual

a_{5}

qualifies no further individuals, so we obtain the final result

f^{CSR} (N, φ) = {a_{2}, a_{3}, a_{5}}

Figure 2: The highlighted individuals are socially qualified with respect to the CSR rule.

Liberal-start-respecting rule

f^{LSR}

: This rule also determines the socially qualified individuals iteratively. Initially, all individuals who qualify themselves are considered to be socially qualified. Then, in each iteration, any individual who is qualified by any of the currently socially qualified individuals is added to the set of socially qualified individuals. Once no new individuals can be added, the iterative process terminates.

More formally, the initial set of socially qualified individuals is defined as

K_{0}^{L} (N, φ) = {a \in N : φ (a, a) = 1} .

And for each positive integer

i

, the set of socially qualified individuals in the

i

-th iteration is defined as

K_{i}^{L} (N, φ) = K_{i - 1}^{L} (N, φ) \cup {a \in N : \exists a^{'} \in K_{i - 1}^{L} (N, φ) s.t. φ (a^{'}, a) = 1} .

We define

f^{LSR} (N, φ) = K_{i}^{L} (N, φ)

for the smallest

i

with

K_{i}^{L} (N, φ) = K_{i - 1}^{L} (N, φ)

Applying the LSR rule to the example instance depicted in Figure [1], we initially have

K_{0}^{L} (N, φ) = {a_{1}, a_{3}, a_{4}}

since these three individuals each qualify themselves. Because

a_{1}

also qualifies

a_{2}

and

a_{5}

, we then get

K_{1}^{L} (N, φ) = {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}} = f^{LSR} (N, φ)

Figure 3: The highlighted individuals are socially qualified with respect to the LSR rule.

Consent rules

f^{(s, t)}

: A consent rule is specified by two parameters

s, t \in N

. For every individual

a \in N

, it holds:

•If $φ (a, a) = 1$ then $a \in f^{(s, t)} (N, φ)$ if and only if $| a^{'} \in N : φ (a^{'}, a) = 1 | \geq s$ .
•If $φ (a, a) = - 1$ then $a \notin f^{(s, t)} (N, φ)$ if and only if $| a^{'} \in N : φ (a^{'}, a) = - 1 | \geq t$ .

In other words, an individual who qualifies themselves is socially qualified if and only if at least

s - 1

other individuals also qualify them. And an individual who disqualifies themselves is socially disqualified if and only if at least

t - 1

other individuals also disqualify them.

For instance, applying the consent rule

f^{(2, 3)}

with

s = 2

and

t = 3

to the example instance depicted in Figure [1], the individuals

a_{1}

and

a_{3}

would be socially qualified because they qualify themselves and are qualified by at least one other individual (namely

a_{4}

). The individual

a_{5}

would be socially disqualified because they disqualify themselves and are disqualified by two other individuals (namely

a_{3}

and

a_{4}

). Finally,

a_{2}

would be socially qualified because all other individuals qualify

a_{2}

, and

a_{4}

would be socially disqualified because all other individuals disqualify

a_{4}

. Thus, the set of socially qualified individuals would be

f^{(2, 3)} (N, φ) = {a_{1}, a_{2}, a_{3}}

Figure 4: The highlighted individuals are socially qualified with respect to the consent rule using s=2 and t=3.

2. Introduction to Manipulative Attacks

In this paper, instead of trying to determine the socially qualified individuals, we mainly focus on manipulative attacks in group identification. In a manipulative attack, an outsider (called the 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.

There are different means which the attacker may use to reach their objective. In 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.

The precise steps the attacker must take to reach their objective depend on which social rule is used for evaluation. For each combination of a strategic objective, a means of manipulation, and a social rule, we can study the feasibility and the computational complexity of the corresponding problem. Sometimes, it is not possible for the attacker to reach their objective by the given means. In this case, we say that the used social rule is 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.

Throughout this paper, we use

A^{+}

to denote the constructive target set, i.e. the set of individuals the attacker wants to make socially qualified. Likewise, we use

A^{-}

to denote the destructive target set, i.e. the set of individuals the attacker wants to make socially disqualified. Naturally, we require that

A^{+} \cap A^{-} = \emptyset

2.1. Problem Definitions

We now provide formal definitions of the different problem settings. Recall that when

f

is a social rule,

f (N, φ)

denotes the subset of socially qualified individuals of

N

with respect to

f

and

φ

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

T \subseteq N

is initially considered in the group identification process. The attacker can then select up to

ℓ

individuals from

N ∖ T

to be added to

T

. This can be thought of as motivating additional individuals to participate in the process who otherwise would not have participated.

$f$ -Group Control by Adding Individuals (GCAI)
Given:	A set $N$ of individuals, a profile $φ$ over $N$ , three subsets $A^{+}, A^{-}, T \subseteq N$ with $A^{+} \cap A^{-} = \emptyset$ and $A^{+}, A^{-} \subseteq T$ , and a positive integer $ℓ$ .
Question:	Is there a subset $U \subseteq N ∖ T$ such that $\| U \| \leq ℓ$ and $A^{+} \subseteq f (T \cup U, φ)$ and $A^{-} \cap f (T \cup U, φ) = \emptyset$ ?
	In other words, is there a way to add at most $ℓ$ individuals from $N ∖ T$ to $T$ such that all individuals in $A^{+}$ become socially qualified and all individuals in $A^{-}$ become socially disqualified with respect to the social rule $f$ ?

In addition to the general

f

-GCAI problem, there are the three special variants

• $f$ -Constructive Group Control by Adding Individuals (CGCAI) where the set $A^{-}$ is dropped,
• $f$ -Destructive Group Control by Adding Individuals (DGCAI) where the set $A^{+}$ is dropped,
• $f$ -Exact Group Control by Adding Individuals (EGCAI) where we add the premise $A^{+} \cup A^{-} = T$ .

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

N

and allow the attacker to delete up to

ℓ

individuals from

N

. This can be thought of as preventing some individuals from participating in the selection process. However, the attacker is not allowed to delete individuals that are in

A^{+}

A^{-}

$f$ -Group Control by Deleting Individuals (GCDI)
Given:	A set $N$ of individuals, a profile $φ$ over $N$ , two subsets $A^{+}, A^{-} \subseteq N$ with $A^{+} \cap A^{-} = \emptyset$ , and a positive integer $ℓ$ .
Question:	Is there a subset $U \subseteq N ∖ (A^{+} \cup A^{-})$ such that $\| U \| \leq ℓ$ and $A^{+} \subseteq f (N ∖ U, φ)$ and $A^{-} \cap f (N ∖ U, φ) = \emptyset$ ?
	In other words, is there a way to delete at most $ℓ$ individuals from $N ∖ (A^{+} \cup A^{-})$ such that all individuals in $A^{+}$ become socially qualified and all individuals in $A^{-}$ become socially disqualified with respect to the social rule $f$ ?

In addition to the general

f

-GCDI problem, there are the two special variants

• $f$ -Constructive Group Control by Deleting Individuals (CGCDI) where the set $A^{-}$ is dropped,
• $f$ -Destructive Group Control by Deleting Individuals (DGCDI) where the set $A^{+}$ is dropped.

Note that there is no

f

-Exact Group Control by Deleting Individuals problem. The reason for this is that we only allow the attacker to delete individuals from

N ∖ (A^{+} \cup A^{-})

. Hence, the attacker would not be allowed to delete anyone when

A^{+} \cup A^{-} = N

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

U

and

N ∖ U

, and the socially qualified individuals are determined separately for both partitions. Subsequently, in the second stage of the selection, only individuals who survived the first stage are considered. Multi-stage selection procedures are common in many real-world scenarios (e.g. think of organizational units or electoral districts).

$f$ -Group Control by Partitioning of Individuals (GCPI)
Given:	A set $N$ of individuals, a profile $φ$ over $N$ , and two subsets $A^{+}, A^{-} \subseteq N$ with $A^{+} \cap A^{-} = \emptyset$ .
Question:	Is there a subset $U \subseteq N$ such that $A^{+} \subseteq f (V, φ)$ and $A^{-} \cap f (V, φ) = \emptyset$ where $V = f (U, φ) \cup f (N ∖ U, φ)$ ?
	In other words, is there a way to split the set of individuals into two partitions $U$ and $N ∖ U$ such that all individuals in $A^{+}$ become socially qualified and all individuals in $A^{-}$ become socially disqualified with respect to the social rule $f$ ?

In addition to the general

f

-GCPI problem, there are the three special variants

• $f$ -Constructive Group Control by Partitioning of Individuals (CGCPI) where the set $A^{-}$ is dropped,
• $f$ -Destructive Group Control by Partitioning of Individuals (DGCPI) where the set $A^{+}$ is dropped,
• $f$ -Exact Group Control by Partitioning of Individuals (EGCPI) where we add the premise $A^{+} \cup A^{-} = N$ .

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

ℓ

individuals to change their opinion. In this model, we assume that the attacker can arbitrarily alter the outgoing valuations of each bribed individual.

$f$ -Group Bribery (GB)
Given:	A set $N$ of individuals, a profile $φ$ over $N$ , two subsets $A^{+}, A^{-} \subseteq N$ with $A^{+} \cap A^{-} = \emptyset$ , and a positive integer $ℓ$ .
Question:	Is there a way to obtain a profile $φ^{'}$ over $N$ by changing the outgoing valuations in $φ$ of at most $ℓ$ individuals such that $A^{+} \subseteq f (N, φ^{'})$ and $A^{-} \cap f (N, φ^{'}) = \emptyset$ ?
	In other words, is there a way to bribe at most $ℓ$ individuals such that all individuals in $A^{+}$ become socially qualified and all individuals in $A^{-}$ become socially disqualified with respect to the social rule $f$ ?

In addition to the general

f

-GB problem, there are the three special variants

• $f$ -Constructive Group Bribery (CGB) where the set $A^{-}$ is dropped,
• $f$ -Destructive Group Bribery (DGB) where the set $A^{+}$ is dropped,
• $f$ -Exact Group Bribery (EGB) where we add the premise $A^{+} \cup A^{-} = N$ .

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

φ

separately. In total, the attacker is allowed to change up to

ℓ

entries (i.e. replace a

1

by a

- 1

, or a

- 1

by a

1

$f$ -Group Microbribery (GMB)
Given:	A set $N$ of individuals, a profile $φ$ over $N$ , two subsets $A^{+}, A^{-} \subseteq N$ with $A^{+} \cap A^{-} = \emptyset$ , and a positive integer $ℓ$ .
Question:	Is there a way to obtain a profile $φ^{'}$ over $N$ by changing the valuations in $φ$ for at most $ℓ$ pairs of individuals such that $A^{+} \subseteq f (N, φ^{'})$ and $A^{-} \cap f (N, φ^{'}) = \emptyset$ ?
	In other words, is there a way to change at most $ℓ$ entries in $φ$ such that all individuals in $A^{+}$ become socially qualified and all individuals in $A^{-}$ become socially disqualified with respect to the social rule $f$ ?

In addition to the general

f

-GMB problem, there are the three special variants

• $f$ -Constructive Group Microbribery (CGMB) where the set $A^{-}$ is dropped,
• $f$ -Destructive Group Microbribery (DGMB) where the set $A^{+}$ is dropped,
• $f$ -Exact Group Microbribery (EGMB) where we add the premise $A^{+} \cup A^{-} = N$ .

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

Table 1: An overview of the problem names and their acronyms used in this paper.

3. Computational Complexity of Group Control and Bribery

The study of manipulative attacks in group identification is mainly concerned with the computational complexity of the corresponding problems. In this section, we provide an overview of the known complexity results for group control and bribery. We consider all problems listed in Section 2.1 under each of the social rules defined in Section 1.1.

3.1. Constructive Group Control and Bribery

We begin with the constrictive problems. The results for the three constructive group control problems were all shown by Yang et al.^[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.

Table [2] lists all the known complexity results for constructive group control and bribery.

	Consent rules $f^{(s, t)}$						$f^{CSR}$	$f^{LSR}$
	$s = 1$			$s \geq 2$
	$t = 1$	$t = 2$	$t \geq 3$	$t = 1$	$t = 2$	$t \geq 3$
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

Manipulative Attacks in Group Identification

Abstract

1. Introduction to Group Identification

1.1. Social Rules

2. Introduction to Manipulative Attacks

2.1. Problem Definitions

2.2. Problem Acronyms Overview

3. Computational Complexity of Group Control and Bribery

3.1. Constructive Group Control and Bribery