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	P	P	P	P	P	NP-h	NP-h

Table 2: A summary of the known complexity results for constructive group control and bribery. In the table, "P" stands for "polynomial-time solvable", "NP-h" stands for "NP-hard", "I" stands for "immune", and "?" means that the complexity of the problem is open.

One of the results shown in the above table is that all consent rules

f^{(s, t)}

with

t = 1

are immune to Constructive Group Control by Deleting Individuals (CGCDI) and Constructive Group Control by Partitioning of Individuals (CGCPI). To see why this is the case, we can do a simple case analysis (cf. Yang et al.^[6:1] Theorem 2):

Let

a \in A^{+}

be an individual who is not socially qualified initially, i.e.

a \notin f^{(s, t)} (N, φ)

. We now show that it is impossible to turn

a

socially qualified by partitioning or deleting individuals when

t = 1

. We distinguish between two cases.

Case 1: $a$ qualifies themselves, i.e. $φ (a, a) = 1$	In this case, there are less than $s$ individuals in $N$ who qualify $a$ (because otherwise $a$ would already be socially qualified initially). Therefore, no matter how we partition the set $N$ or which individuals we delete from $N$ , we can never make the individual $a$ socially qualified.
Case 2: $a$ disqualifies themselves, i.e. $φ (a, a) = - 1$	Because $t = 1$ , $a$ is always socially disqualified, regardless of how we partition the set $N$ or which individuals we delete from $N$ .

In both of the above cases, it is impossible for the attacker to turn

a

socially qualified by partitioning or deleting individuals. The consent rules

f^{(s, t)}

with

t = 1

are therefore immune to these kinds of manipulative attacks.

3.2. Destructive Group Control and Bribery

We now turn to the destructive problems. The results for the three destructive group control problems and the bribery problem were shown by Erdélyi et al.^[7:1], and Boehmer et al.^[8:1] extended their results to the microbribery problem.

Table [3] lists all the known complexity results for destructive group control and bribery.

	Consent rules $f^{(s, t)}$						$f^{CSR}$	$f^{LSR}$
	$s = 1$		$s = 2$		$s \geq 3$
	$t = 1$	$t \geq 2$	$t = 1$	$t \geq 2$	$t = 1$	$t \geq 2$
DGCAI	I	NP-h	I	NP-h	I	NP-h	NP-h	I
DGCDI	I	I	P	P	NP-h	NP-h	P	P
DGCPI	I	I	NP-h	NP-h	NP-h	NP-h	?	P
DGB	P	NP-h	NP-h	NP-h	NP-h	NP-h	P	P
DGMB	P	P	P	P	P	P	P	P

Table 3: A summary of the known complexity results for destructive group control and bribery. In the table, "P" stands for "polynomial-time solvable", "NP-h" stands for "NP-hard", "I" stands for "immune", and "?" means that the complexity of the problem is open.

As shown in the above table,

f^{CSR}

-Destructive Group Control by Adding Individuals (DGCAI) is an NP-hard problem. This can be shown via a reduction from the so-called Restricted Exact Cover by 3-sets problem (RX3C). That is, given an instance of the RX3C problem, we construct an equivalent instance of the

f^{CSR}

-DGCAI problem, so if the latter could be solved efficiently, the same would be true for the former. The RX3C problem is known to be NP-hard^[9] and is defined as follows:

Restricted Exact Cover by 3-sets (RX3C)
Given:	A set $X$ of size $3 m$ (i.e. a size divisible by $3$ ) and a family $F$ of subsets of $X$ . Each subset $F \in F$ contains exactly three elements from $X$ and each element in $X$ is contained in exactly three subsets $F \in F$ .
Question:	Is there is a subfamily $F^{'} \subseteq F$ such that every element in $X$ is contained in exactly one subset in $F^{'}$ ?

To proof that

f^{CSR}

-DGCAI is NP-hard, we now show a reduction from RX3C to

f^{CSR}

-DGCAI (cf. Erdélyi et al.^[7:2] Theorem 5). Given a RX3C-instance

(X, F)

, we construct an equivalent instance of

f^{CSR}

-DGCAI:

We introduce one individual

a_{x}

for each element

x \in X

and let

N_{X} = {a_{x} : x \in X}

. We also introduce one individual

a_{F}

for each subset

F \in F

and let

N_{F} = {a_{F} : F \in F}

. We then let

N = N_{X} \cup N_{F}

and define the profile

φ

over

N

as follows:

•All individuals in $N_{X}$ qualify all individuals in $N_{X}$ .
•For each individual $a_{x} \in N_{X}$ and each individual $a_{F} \in N_{F}$ , we let $a_{F}$ qualify $a_{x}$ if and only if $x \notin F$ .
•For all pairs of individuals $(a, a^{'}) \in N \times N$ not defined above, we let $a$ disqualify $a^{'}$ .

Finally, we set

A^{-} = T = N_{X}

and

ℓ = m

We now claim that there exists a successful bribery of cost at most

ℓ

in the constructed instance if and only if there exists an exact 3-set cover for

X

F

(

\Rightarrow

) Assume that

F^{'} \subseteq F

is an exact 3-set cover for

X

. We let

U = {a_{F} \in N_{F} : F \in F^{'}}

and add

U

to the set of individuals. Because

F^{'}

is an exact 3-set cover for

X

, every individual

a_{x} \in N_{X}

is disqualified by at least one individual in

U

. Thus, there is now no individual who is qualified by everyone, so the initial set of socially qualified individuals

K_{0}^{C} (N_{X} \cup U, φ)

is empty. From this, it follows that all individuals in

A^{-}

are now socially disqualified.

(

\Leftarrow

) Assume we are given a subset

U \subseteq N ∖ T

consisting of at most

ℓ = m

individuals such that all individuals in

A^{-}

become socially disqualified after adding

U

to the set of individuals. By construction, for each individual

a_{x} \in N_{X}

, there must be at least one individual in

U

who disqualifies

a_{x}

. This implies that

{F \in F : a_{F} \in U}

is an exact 3-set cover for

X

This concludes the proof of the NP-hardness of

f^{CSR}

-Destructive Group Control by Adding Individuals.

3.3. Exact Group Control and Bribery

Next, we turn to manipulative attacks where the attacker has an exact objective, i.e. they can precisely specify for each individual whether they should be socially qualified or not. The results for the exact group control problems are from Junker^[10], and the results for bribery and microbribery are by Boehmer et al.^[8:2].

Table [4] lists all the known complexity results for exact group control and bribery.

	Consent rules $f^{(s, t)}$				$f^{CSR}$	$f^{LSR}$
	$s = 1$		$s \geq 2$
	$t = 1$	$t \geq 2$	$t = 1$	$t \geq 2$
EGCAI	I	I if $A^{+} \neq \emptyset$ (NP-h else)	I if $A^{-} \neq \emptyset$ (NP-h else)	NP-h	NP-h	I if $A^{-} \neq \emptyset$ (NP-h else)
EGCPI	I	I	I if $A^{+} \neq \emptyset$	NP-h	?	I
EGB	P	NP-h	NP-h	NP-h	P	P
EGMB	P	P	P	P	P	P

Table 4: A summary of the known complexity results for exact group control and bribery. In the table, "P" stands for "polynomial-time solvable", "NP-h" stands for "NP-hard", "I" stands for "immune", and "?" means that the complexity of the problem is open.

Notably, the NP-hardness of

f^{CSR}

-Exact Group Control by Adding Individuals (EGCAI) follows directly from the NP-hardness of

f^{CSR}

-Destructive Group Control by Adding Individuals (DGCAI) which we have already seen in the previous section. This is because the DGCAI-instances constructed in the reduction have the destructive target set defined as

A^{-} = T

, i.e. the objective of the attacker is to make all individuals in

T

socially disqualified. Hence, the NP-hardness also holds when the attacker has an exact objective.

3.4. General Group Control and Bribery

Finally, we now consider the most general form of group control and bribery problems (sometimes referred to as constructive+destructive). The results for the group control problems are from Junker^[10:1], and the results for bribery and microbribery are by Boehmer et al.^[8:3].

Note that, when

A^{-} = \emptyset

(resp.

A^{+} = \emptyset

), the problems are simply equivalent to the constructive (resp. destructive) cases. For these problem instances, we refer to Tables [2] and [3]. Below, we only consider instances where both

A^{+}

and

A^{-}

are nonempty and the attacker tries to simultaneously make everyone in

A^{+}

socially qualified and everyone in

A^{-}

socially disqualified. Table [5] lists the known complexity results for group control and bribery restricted to such instances.

	Consent rules $f^{(s, t)}$						$f^{CSR}$	$f^{LSR}$
	$s = 1$	$s = 1$	$s \geq 2$	$s = 2$	$s = 2$	$s \geq 3$
	$t = 1$	$t \geq 2$	$t = 1$	$t = 2$	$t \geq 3$	$t \geq 2$
GCAI	I	I	I	NP-h	NP-h	NP-h	I	I
GCDI	I	I	I	P	NP-h	NP-h	?	I
GCPI	I	I	I	NP-h	NP-h	NP-h	?	I
GB	P	NP-h	NP-h	NP-h	NP-h	NP-h	P	P
GMB	P	P	P	P	P	P	NP-h	NP-h

Table 5: A summary of the known complexity results for general group control and bribery. In the table, "P" stands for "polynomial-time solvable", "NP-h" stands for "NP-hard", "I" stands for "immune", and "?" means that the complexity of the problem is open.

As can be seen in the above table, the Group Microbribery problem (GMB) is polynomial-time solvable for all consent rules

f^{(s, t)}

(cf. Boehmer et al.^[8:4] Observation 2). The reason for this is that, for each individual

a \in A^{+}

, there are only two ways to make

a

socially qualified: (1) have

a

qualify themselves and have at least

s - 1

other individuals also qualify

a

, or (2) have

a

disqualify themselves and have less than

t - 1

other individuals disqualify

a

. Both scenarios lead to the desired outcome of making

a

socially qualified, so we simply pick the one that requires less bribes. Likewise, for each individual

a \in A^{-}

, there are only two ways to make

a

socially disqualified: (1) have

a

disqualify themselves and have at least

t - 1

other individuals also disqualify

a

, or (2) have

a

qualify themselves and have less than

s - 1

other individuals qualify

a

. Again, both scenarios lead to the desired outcome of making

a

socially disqualified, so we simply pick the one that requires less bribes. Overall, the

f^{(s, t)}

-GMB problem can be solved in polynomial time with this approach.

4. Conclusion

In this paper, we have provided an introduction to manipulative attacks in group identification. We have listed all the currently known computational complexity results for the various problems and social rules. We have also given an insight into the approaches used to proof some of these results.

The study of manipulative attacks in group identification remains a hot topic in research. There are still some open cases (see the "?" entries in the tables above), and several papers with new findings have only recently been published^[11]^[12].

5. References

Douglas Brent West. "Introduction to graph theory". Prentice-Hall (2000). ↩︎
Ding-Zhu Du, Ker-I Ko. "Theory of computational complexity". John Wiley & Sons (2011). ↩︎
Dov Samet and David Schmeidler. "Between liberalism and democracy". In: Journal of Economic Theory 110.2 (2003), pp. 213–233. ↩︎
Dinko Dimitrov. "The social choice approach to group identification". In: Consensual Processes. Springer (2011), pp. 123–134. ↩︎
Alan D. Miller. "Group identification". In: Games and Economic Behavior 63.1 (2008), pp. 188–202. ↩︎
Yongjie Yang and Dinko Dimitrov. "How hard is it to control a group?" In: Autonomous Agents and Multi-Agent Systems 32.5 (2018), pp. 672–692. ↩︎ ↩︎
Gábor Erdélyi, Christian Reger, and Yongjie Yang. "The complexity of bribery and control in group identification". In: Autonomous Agents and Multi-Agent Systems 34.1 (2020), pp. 1–31. ↩︎ ↩︎ ↩︎
Niclas Boehmer, Robert Bredereck, Dušan Knop, and Junjie Luo. "Fine-grained view on bribery for group identification". In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (2020), pp. 67–73. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Teofilo F. Gonzalez. "Clustering to minimize the maximum intercluster distance". In: Theoretical Computer Science 38 (1985), pp. 293–306. ↩︎
Emil Junker. "Manipulative attacks and group identification". In: arXiv preprint arXiv:2203.16151 [cs.GT] (2022). ↩︎ ↩︎
Niclas Boehmer, Robert Bredereck, Dušan Knop, and Junjie Luo. "Finding small multi-demand set covers with ubiquitous elements and large sets is fixed-parameter tractable". In: arXiv preprint arXiv:2104.10124 [cs.DS] (2021). ↩︎
Yongjie Yang and Dinko Dimitrov. "Group control for procedural rules: parameterized complexity and consecutive domains". In: arXiv preprint arXiv:2203.16872 [cs.GT] (2022). ↩︎

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

3.2. Destructive Group Control and Bribery

3.3. Exact Group Control and Bribery

3.4. General Group Control and Bribery

4. Conclusion

5. References

Recommended for you

Report Article