 # 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 and Du et al..
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$$N$NN to denote the given set of individuals. The pairwise opinions of the individuals are represented by a function $\phi :N×N\to \left\{-1,1\right\}$$\phi :N×N\to \left\{-1,1\right\}$varphi:N xx N rarr{-1,1}\varphi : N \times N \rightarrow \{ -1, 1 \} called profile over $N$$N$NN. For individuals $a,b\in N$$a,b\in N$a,b in Na,b \in N, we write $\phi \left(a,b\right)=1$$\phi \left(a,b\right)=1$varphi(a,b)=1\varphi(a,b) = 1 when $a$$a$aa thinks $b$$b$bb is qualified and say $a$$a$aa qualifies $b$$b$bb. We write $\phi \left(a,b\right)=-1$$\phi \left(a,b\right)=-1$varphi(a,b)=-1\varphi(a,b) = -1 when $a$$a$aa thinks $b$$b$bb is not qualified and say $a$$a$aa disqualifies $b$$b$bb.
A group identification instance $\left(N,\phi \right)$$\left(N,\phi \right)$(N,varphi)(N, \varphi) is best represented as a directed graph $G=\left(V,E\right)$$G=\left(V,E\right)$G=(V,E)G = (V, E) where $V=N$$V=N$V=NV = N and $\left(a,b\right)\in E$$\left(a,b\right)\in E$(a,b)in E(a, b) \in E if and only if $\phi \left(a,b\right)=1$$\phi \left(a,b\right)=1$varphi(a,b)=1\varphi(a, b) = 1.
Example: Let $N=\left\{{a}_{1},{a}_{2},{a}_{3},{a}_{4},{a}_{5}\right\}$$N=\left\{{a}_{1},{a}_{2},{a}_{3},{a}_{4},{a}_{5}\right\}$N={a_(1),a_(2),a_(3),a_(4),a_(5)}N = \{ a_1, a_2, a_3, a_4, a_5 \} be a set of five individuals and $\phi$$\phi$varphi\varphi a profile over $N$$N$NN defined as follows ($\phi \left({a}_{i},{a}_{j}\right)$$\phi \left({a}_{i},{a}_{j}\right)$varphi(a_(i),a_(j))\varphi(a_i, a_j) is given by the matrix entry in the $i$$i$ii-th row and $j$$j$jj-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}$$\begin{array}{r} {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}${:[,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]:}\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.

### 1.1. Social Rules

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$$f$ff that, given a group identification instance $\left(N,\phi \right)$$\left(N,\phi \right)$(N,varphi)(N, \varphi), outputs a subset $f\left(N,\phi \right)\subseteq N$$f\left(N,\phi \right)\subseteq N$f(N,varphi)sube Nf(N, \varphi) \subseteq N which we refer to as socially qualified individuals of $N$$N$NN with respect to $f$$f$ff and $\phi$$\phi$varphi\varphi.
In the literature, the consensus-start-respecting (CSR) rule, the liberal-start-respecting (LSR) rule, and the consent rules have received particular attention. Therefore, we make these rules the subject of our analysis in this paper.
Consensus-start-respecting rule ${f}^{\text{CSR}}$${f}^{\text{CSR}}$f^("CSR")f^{\text{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}^{\text{C}}\left(N,\phi \right)=\left\{a\in N:\phi \left({a}^{\mathrm{\prime }},a\right)=1\text{for all}{a}^{\mathrm{\prime }}\in N\right\}.$K_(0)^("C")(N,varphi)={a in N:varphi(a^('),a)=1" for all "a^(')in N}.K^{\text{C}}_0(N, \varphi) = \{a \in N : \varphi(a^\prime, a) = 1 \text{ for all } a^\prime \in N\}.
And for each positive integer $i$$i$ii, the set of socially qualified individuals in the $i$$i$ii-th iteration is defined as
${K}_{i}^{\text{C}}\left(N,\phi \right)={K}_{i-1}^{\text{C}}\left(N,\phi \right)\cup \left\{a\in N:\mathrm{\exists }\text{}{a}^{\mathrm{\prime }}\in {K}_{i-1}^{\text{C}}\left(N,\phi \right)\text{s.t.}\phi \left({a}^{\mathrm{\prime }},a\right)=1\right\}.$K_(i)^("C")(N,varphi)=K_(i-1)^("C")(N,varphi)uu{a in N:EEa^(')inK_(i-1)^("C")(N,varphi)" s.t. "varphi(a^('),a)=1}.K^{\text{C}}_i(N, \varphi) = K^{\text{C}}_{i-1}(N, \varphi) \cup \{a \in N : \exists~ a^\prime \in K^{\text{C}}_{i-1}(N, \varphi) \text{ s.t. } \varphi(a^\prime, a) = 1\}.
We define ${f}^{\text{CSR}}\left(N,\phi \right)={K}_{i}^{\text{C}}\left(N,\phi \right)$${f}^{\text{CSR}}\left(N,\phi \right)={K}_{i}^{\text{C}}\left(N,\phi \right)$f^("CSR")(N,varphi)=K_(i)^("C")(N,varphi)f^{\text{CSR}}(N, \varphi) = K^{\text{C}}_i(N, \varphi) for the smallest $i$$i$ii with ${K}_{i}^{\text{C}}\left(N,\phi \right)={K}_{i-1}^{\text{C}}\left(N,\phi \right)$${K}_{i}^{\text{C}}\left(N,\phi \right)={K}_{i-1}^{\text{C}}\left(N,\phi \right)$K_(i)^("C")(N,varphi)=K_(i-1)^("C")(N,varphi)K^{\text{C}}_i(N, \varphi) = K^{\text{C}}_{i-1}(N, \varphi).
Applying the CSR rule to the example instance depicted in Figure , we initially have ${K}_{0}^{\text{C}}\left(N,\phi \right)=\left\{{a}_{3}\right\}$${K}_{0}^{\text{C}}\left(N,\phi \right)=\left\{{a}_{3}\right\}$K_(0)^("C")(N,varphi)={a_(3)}K^{\text{C}}_0(N, \varphi) = \{ a_3 \} since ${a}_{3}$${a}_{3}$a_(3)a_3 is the only individual who is qualified by everyone. Because ${a}_{3}$${a}_{3}$a_(3)a_3 qualifies ${a}_{2}$${a}_{2}$a_(2)a_2, we get ${K}_{1}^{\text{C}}\left(N,\phi \right)=\left\{{a}_{2},{a}_{3}\right\}$${K}_{1}^{\text{C}}\left(N,\phi \right)=\left\{{a}_{2},{a}_{3}\right\}$K_(1)^("C")(N,varphi)={a_(2),a_(3)}K^{\text{C}}_1(N, \varphi) = \{ a_2, a_3 \}. Since ${a}_{2}$${a}_{2}$a_(2)a_2 also qualifies ${a}_{5}$${a}_{5}$a_(5)a_5, we then get ${K}_{2}^{\text{C}}\left(N,\phi \right)=\left\{{a}_{2},{a}_{3},{a}_{5}\right\}$${K}_{2}^{\text{C}}\left(N,\phi \right)=\left\{{a}_{2},{a}_{3},{a}_{5}\right\}$K_(2)^("C")(N,varphi)={a_(2),a_(3),a_(5)}K^{\text{C}}_2(N, \varphi) = \{ a_2, a_3, a_5 \}. The individual ${a}_{5}$${a}_{5}$a_(5)a_5 qualifies no further individuals, so we obtain the final result ${f}^{\text{CSR}}\left(N,\phi \right)=\left\{{a}_{2},{a}_{3},{a}_{5}\right\}$${f}^{\text{CSR}}\left(N,\phi \right)=\left\{{a}_{2},{a}_{3},{a}_{5}\right\}$f^("CSR")(N,varphi)={a_(2),a_(3),a_(5)}f^{\text{CSR}}(N, \varphi) = \{ 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}^{\text{LSR}}$${f}^{\text{LSR}}$f^("LSR")f^{\text{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}^{\text{L}}\left(N,\phi \right)=\left\{a\in N:\phi \left(a,a\right)=1\right\}.$${K}_{0}^{\text{L}}\left(N,\phi \right)=\left\{a\in N:\phi \left(a,a\right)=1\right\}.$K_(0)^("L")(N,varphi)={a in N:varphi(a,a)=1}.K^{\text{L}}_0(N, \varphi) = \{a \in N : \varphi(a, a) = 1\}.
And for each positive integer $i$$i$ii, the set of socially qualified individuals in the $i$$i$ii-th iteration is defined as
${K}_{i}^{\text{L}}\left(N,\phi \right)={K}_{i-1}^{\text{L}}\left(N,\phi \right)\cup \left\{a\in N:\mathrm{\exists }\text{}{a}^{\mathrm{\prime }}\in {K}_{i-1}^{\text{L}}\left(N,\phi \right)\text{s.t.}\phi \left({a}^{\mathrm{\prime }},a\right)=1\right\}.$K_(i)^("L")(N,varphi)=K_(i-1)^("L")(N,varphi)uu{a in N:EEa^(')inK_(i-1)^("L")(N,varphi)" s.t. "varphi(a^('),a)=1}.K^{\text{L}}_i(N, \varphi) = K^{\text{L}}_{i-1}(N, \varphi) \cup \{a \in N : \exists~ a^\prime \in K^{\text{L}}_{i-1}(N, \varphi) \text{ s.t. } \varphi(a^\prime, a) = 1\}.
We define ${f}^{\text{LSR}}\left(N,\phi \right)={K}_{i}^{\text{L}}\left(N,\phi \right)$${f}^{\text{LSR}}\left(N,\phi \right)={K}_{i}^{\text{L}}\left(N,\phi \right)$f^("LSR")(N,varphi)=K_(i)^("L")(N,varphi)f^{\text{LSR}}(N, \varphi) = K^{\text{L}}_i(N, \varphi) for the smallest $i$$i$ii with ${K}_{i}^{\text{L}}\left(N,\phi \right)={K}_{i-1}^{\text{L}}\left(N,\phi \right)$${K}_{i}^{\text{L}}\left(N,\phi \right)={K}_{i-1}^{\text{L}}\left(N,\phi \right)$K_(i)^("L")(N,varphi)=K_(i-1)^("L")(N,varphi)K^{\text{L}}_i(N, \varphi) = K^{\text{L}}_{i-1}(N, \varphi).
Applying the LSR rule to the example instance depicted in Figure , we initially have ${K}_{0}^{\text{L}}\left(N,\phi \right)=\left\{{a}_{1},{a}_{3},{a}_{4}\right\}$${K}_{0}^{\text{L}}\left(N,\phi \right)=\left\{{a}_{1},{a}_{3},{a}_{4}\right\}$K_(0)^("L")(N,varphi)={a_(1),a_(3),a_(4)}K^{\text{L}}_0(N, \varphi) = \{ a_1, a_3, a_4 \} since these three individuals each qualify themselves. Because ${a}_{1}$${a}_{1}$a_(1)a_1 also qualifies ${a}_{2}$${a}_{2}$a_(2)a_2 and ${a}_{5}$${a}_{5}$a_(5)a_5, we then get ${K}_{1}^{\text{L}}\left(N,\phi \right)=\left\{{a}_{1},{a}_{2},{a}_{3},{a}_{4},{a}_{5}\right\}={f}^{\text{LSR}}\left(N,\phi \right)$${K}_{1}^{\text{L}}\left(N,\phi \right)=\left\{{a}_{1},{a}_{2},{a}_{3},{a}_{4},{a}_{5}\right\}={f}^{\text{LSR}}\left(N,\phi \right)$K_(1)^("L")(N,varphi)={a_(1),a_(2),a_(3),a_(4),a_(5)}=f^("LSR")(N,varphi)K^{\text{L}}_1(N, \varphi) = \{ a_1, a_2, a_3, a_4, a_5 \} = f^{\text{LSR}}(N, \varphi).
Figure 3: The highlighted individuals are socially qualified with respect to the LSR rule.
Consent rules ${f}^{\left(s,t\right)}$${f}^{\left(s,t\right)}$f^((s,t))f^{(s, t)}: A consent rule is specified by two parameters $s,t\in \mathbb{N}$$s,t\in \mathbb{N}$s,t inNs, t \in \mathbb{N}. For every individual $a\in N$$a\in N$a in Na \in N, it holds:
• If $\phi \left(a,a\right)=1$$\phi \left(a,a\right)=1$varphi(a,a)=1\varphi(a, a) = 1 then $a\in {f}^{\left(s,t\right)}\left(N,\phi \right)$$a\in {f}^{\left(s,t\right)}\left(N,\phi \right)$a inf^((s,t))(N,varphi)a \in f^{(s, t)}(N, \varphi) if and only if $|{a}^{\mathrm{\prime }}\in N:\phi \left({a}^{\mathrm{\prime }},a\right)=1|\ge s$$|{a}^{\mathrm{\prime }}\in N:\phi \left({a}^{\mathrm{\prime }},a\right)=1|\ge s$|a^(')in N:varphi(a^('),a)=1| >= s|{a^\prime \in N : \varphi(a^\prime, a) = 1}| \geq s.
• If $\phi \left(a,a\right)=-1$$\phi \left(a,a\right)=-1$varphi(a,a)=-1\varphi(a, a) = -1 then $a\notin {f}^{\left(s,t\right)}\left(N,\phi \right)$$a\notin {f}^{\left(s,t\right)}\left(N,\phi \right)$a!inf^((s,t))(N,varphi)a \not\in f^{(s, t)}(N, \varphi) if and only if $|{a}^{\mathrm{\prime }}\in N:\phi \left({a}^{\mathrm{\prime }},a\right)=-1|\ge t$$|{a}^{\mathrm{\prime }}\in N:\phi \left({a}^{\mathrm{\prime }},a\right)=-1|\ge t$|a^(')in N:varphi(a^('),a)=-1| >= t|{a^\prime \in N : \varphi(a^\prime, a) = -1}| \geq t.
In other words, an individual who qualifies themselves is socially qualified if and only if at least $s-1$$s-1$s-1s-1 other individuals also qualify them. And an individual who disqualifies themselves is socially disqualified if and only if at least $t-1$$t-1$t-1t-1 other individuals also disqualify them.
For instance, applying the consent rule ${f}^{\left(2,3\right)}$${f}^{\left(2,3\right)}$f^((2,3))f^{(2, 3)} with $s=2$$s=2$s=2s=2 and $t=3$$t=3$t=3t=3 to the example instance depicted in Figure , the individuals ${a}_{1}$${a}_{1}$a_(1)a_1 and ${a}_{3}$${a}_{3}$a_(3)a_3 would be socially qualified because they qualify themselves and are qualified by at least one other individual (namely ${a}_{4}$${a}_{4}$a_(4)a_4). The individual ${a}_{5}$${a}_{5}$a_(5)a_5 would be socially disqualified because they disqualify themselves and are disqualified by two other individuals (namely ${a}_{3}$${a}_{3}$a_(3)a_3 and ${a}_{4}$${a}_{4}$a_(4)a_4). Finally, ${a}_{2}$${a}_{2}$a_(2)a_2 would be socially qualified because all other individuals qualify ${a}_{2}$${a}_{2}$a_(2)a_2, and ${a}_{4}$${a}_{4}$a_(4)a_4 would be socially disqualified because all other individuals disqualify ${a}_{4}$${a}_{4}$a_(4)a_4. Thus, the set of socially qualified individuals would be ${f}^{\left(2,3\right)}\left(N,\phi \right)=\left\{{a}_{1},{a}_{2},{a}_{3}\right\}$${f}^{\left(2,3\right)}\left(N,\phi \right)=\left\{{a}_{1},{a}_{2},{a}_{3}\right\}$f^((2,3))(N,varphi)={a_(1),a_(2),a_(3)}f^{(2, 3)}(N, \varphi) = \{ 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}^{+}$${A}^{+}$A^(+)A^+ to denote the constructive target set, i.e. the set of individuals the attacker wants to make socially qualified. Likewise, we use ${A}^{-}$${A}^{-}$A^(-)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}^{-}=\mathrm{\varnothing }$${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$A^(+)nnA^(-)=O/A^+ \cap A^- = \emptyset.

### 2.1. Problem Definitions

We now provide formal definitions of the different problem settings. Recall that when $f$$f$ff is a social rule, $f\left(N,\phi \right)$$f\left(N,\phi \right)$f(N,varphi)f(N, \varphi) denotes the subset of socially qualified individuals of $N$$N$NN with respect to $f$$f$ff and $\phi$$\phi$varphi\varphi.
Group Control by Adding Individuals: In this scenario, only a subset of individuals $T\subseteq N$$T\subseteq N$T sube NT \subseteq N is initially considered in the group identification process. The attacker can then select up to $\ell$$\ell$\ell individuals from $N\setminus T$$N\setminus T$N\\TN \setminus T to be added to $T$$T$TT. This can be thought of as motivating additional individuals to participate in the process who otherwise would not have participated.
 $f$$f$ff$f$-Group Control by Adding Individuals (GCAI) Given: A set $N$$N$NN$N$ of individuals, a profile $\phi$$\phi$varphi\varphi$\phi$ over $N$$N$NN$N$, three subsets ${A}^{+},{A}^{-},T\subseteq N$${A}^{+},{A}^{-},T\subseteq N$A^(+),A^(-),T sube NA^+, A^-, T \subseteq N${A}^{+},{A}^{-},T\subseteq N$ with ${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$A^(+)nnA^(-)=O/A^+ \cap A^- = \emptyset${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$ and ${A}^{+},{A}^{-}\subseteq T$${A}^{+},{A}^{-}\subseteq T$A^(+),A^(-)sube TA^+, A^- \subseteq T${A}^{+},{A}^{-}\subseteq T$, and a positive integer $\ell$$\ell$ℓ\ell$\ell$. Question: Is there a subset $U\subseteq N\setminus T$$U\subseteq N\setminus T$U sube N\\TU \subseteq N \setminus T$U\subseteq N\setminus T$ such that $|U|\le \ell$$|U|\le \ell$|U| <= ℓ|U| \leq \ell$|U|\le \ell$ and ${A}^{+}\subseteq f\left(T\cup U,\phi \right)$${A}^{+}\subseteq f\left(T\cup U,\phi \right)$A^(+)sube f(T uu U,varphi)A^+ \subseteq f(T \cup U, \varphi)${A}^{+}\subseteq f\left(T\cup U,\phi \right)$ and ${A}^{-}\cap f\left(T\cup U,\phi \right)=\mathrm{\varnothing }$${A}^{-}\cap f\left(T\cup U,\phi \right)=\mathrm{\varnothing }$A^(-)nn f(T uu U,varphi)=O/A^- \cap f(T \cup U, \varphi) = \emptyset${A}^{-}\cap f\left(T\cup U,\phi \right)=\mathrm{\varnothing }$? In other words, is there a way to add at most $\ell$$\ell$ℓ\ell$\ell$ individuals from $N\setminus T$$N\setminus T$N\\TN \setminus T$N\setminus T$ to $T$$T$TT$T$ such that all individuals in ${A}^{+}$${A}^{+}$A^(+)A^+${A}^{+}$ become socially qualified and all individuals in ${A}^{-}$${A}^{-}$A^(-)A^-${A}^{-}$ become socially disqualified with respect to the social rule $f$$f$ff$f$?
In addition to the general $f$$f$ff-GCAI problem, there are the three special variants
• $f$$f$ff-Constructive Group Control by Adding Individuals (CGCAI) where the set ${A}^{-}$${A}^{-}$A^(-)A^- is dropped,
• $f$$f$ff-Destructive Group Control by Adding Individuals (DGCAI) where the set ${A}^{+}$${A}^{+}$A^(+)A^+ is dropped,
• $f$$f$ff-Exact Group Control by Adding Individuals (EGCAI) where we add the premise ${A}^{+}\cup {A}^{-}=T$${A}^{+}\cup {A}^{-}=T$A^(+)uuA^(-)=TA^+ \cup A^- = T.
Group Control by Deleting Individuals: In this scenario, we start with an initial set $N$$N$NN and allow the attacker to delete up to $\ell$$\ell$\ell individuals from $N$$N$NN. 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}^{+}$A^(+)A^+ or ${A}^{-}$${A}^{-}$A^(-)A^-.
 $f$$f$ff$f$-Group Control by Deleting Individuals (GCDI) Given: A set $N$$N$NN$N$ of individuals, a profile $\phi$$\phi$varphi\varphi$\phi$ over $N$$N$NN$N$, two subsets ${A}^{+},{A}^{-}\subseteq N$${A}^{+},{A}^{-}\subseteq N$A^(+),A^(-)sube NA^+, A^- \subseteq N${A}^{+},{A}^{-}\subseteq N$ with ${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$A^(+)nnA^(-)=O/A^+ \cap A^- = \emptyset${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$, and a positive integer $\ell$$\ell$ℓ\ell$\ell$. Question: Is there a subset $U\subseteq N\setminus \left({A}^{+}\cup {A}^{-}\right)$$U\subseteq N\setminus \left({A}^{+}\cup {A}^{-}\right)$U sube N\\(A^(+)uuA^(-))U \subseteq N \setminus (A^+ \cup A^-)$U\subseteq N\setminus \left({A}^{+}\cup {A}^{-}\right)$ such that $|U|\le \ell$$|U|\le \ell$|U| <= ℓ|U| \leq \ell$|U|\le \ell$ and ${A}^{+}\subseteq f\left(N\setminus U,\phi \right)$${A}^{+}\subseteq f\left(N\setminus U,\phi \right)$A^(+)sube f(N\\U,varphi)A^+ \subseteq f(N \setminus U, \varphi)${A}^{+}\subseteq f\left(N\setminus U,\phi \right)$ and ${A}^{-}\cap f\left(N\setminus U,\phi \right)=\mathrm{\varnothing }$${A}^{-}\cap f\left(N\setminus U,\phi \right)=\mathrm{\varnothing }$A^(-)nn f(N\\U,varphi)=O/A^- \cap f(N \setminus U, \varphi) = \emptyset${A}^{-}\cap f\left(N\setminus U,\phi \right)=\mathrm{\varnothing }$? In other words, is there a way to delete at most $\ell$$\ell$ℓ\ell$\ell$ individuals from $N\setminus \left({A}^{+}\cup {A}^{-}\right)$$N\setminus \left({A}^{+}\cup {A}^{-}\right)$N\\(A^(+)uuA^(-))N \setminus (A^+ \cup A^-)$N\setminus \left({A}^{+}\cup {A}^{-}\right)$ such that all individuals in ${A}^{+}$${A}^{+}$A^(+)A^+${A}^{+}$ become socially qualified and all individuals in ${A}^{-}$${A}^{-}$A^(-)A^-${A}^{-}$ become socially disqualified with respect to the social rule $f$$f$ff$f$?
In addition to the general $f$$f$ff-GCDI problem, there are the two special variants
• $f$$f$ff-Constructive Group Control by Deleting Individuals (CGCDI) where the set ${A}^{-}$${A}^{-}$A^(-)A^- is dropped,
• $f$$f$ff-Destructive Group Control by Deleting Individuals (DGCDI) where the set ${A}^{+}$${A}^{+}$A^(+)A^+ is dropped.
Note that there is no $f$$f$ff-Exact Group Control by Deleting Individuals problem. The reason for this is that we only allow the attacker to delete individuals from $N\setminus \left({A}^{+}\cup {A}^{-}\right)$$N\setminus \left({A}^{+}\cup {A}^{-}\right)$N\\(A^(+)uuA^(-))N \setminus (A^+ \cup A^-). Hence, the attacker would not be allowed to delete anyone when ${A}^{+}\cup {A}^{-}=N$${A}^{+}\cup {A}^{-}=N$A^(+)uuA^(-)=NA^+ \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$$U$UU and $N\setminus U$$N\setminus U$N\\UN \setminus 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$$f$ff$f$-Group Control by Partitioning of Individuals (GCPI) Given: A set $N$$N$NN$N$ of individuals, a profile $\phi$$\phi$varphi\varphi$\phi$ over $N$$N$NN$N$, and two subsets ${A}^{+},{A}^{-}\subseteq N$${A}^{+},{A}^{-}\subseteq N$A^(+),A^(-)sube NA^+, A^- \subseteq N${A}^{+},{A}^{-}\subseteq N$ with ${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$A^(+)nnA^(-)=O/A^+ \cap A^- = \emptyset${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$. Question: Is there a subset $U\subseteq N$$U\subseteq N$U sube NU \subseteq N$U\subseteq N$ such that ${A}^{+}\subseteq f\left(V,\phi \right)$${A}^{+}\subseteq f\left(V,\phi \right)$A^(+)sube f(V,varphi)A^+ \subseteq f(V, \varphi)${A}^{+}\subseteq f\left(V,\phi \right)$ and ${A}^{-}\cap f\left(V,\phi \right)=\mathrm{\varnothing }$${A}^{-}\cap f\left(V,\phi \right)=\mathrm{\varnothing }$A^(-)nn f(V,varphi)=O/A^- \cap f(V, \varphi) = \emptyset${A}^{-}\cap f\left(V,\phi \right)=\mathrm{\varnothing }$ where $V=f\left(U,\phi \right)\cup f\left(N\setminus U,\phi \right)$$V=f\left(U,\phi \right)\cup f\left(N\setminus U,\phi \right)$V=f(U,varphi)uu f(N\\U,varphi)V = f(U, \varphi) \cup f(N \setminus U, \varphi)$V=f\left(U,\phi \right)\cup f\left(N\setminus U,\phi \right)$? In other words, is there a way to split the set of individuals into two partitions $U$$U$UU$U$ and $N\setminus U$$N\setminus U$N\\UN \setminus U$N\setminus U$ such that all individuals in ${A}^{+}$${A}^{+}$A^(+)A^+${A}^{+}$ become socially qualified and all individuals in ${A}^{-}$${A}^{-}$A^(-)A^-${A}^{-}$ become socially disqualified with respect to the social rule $f$$f$ff$f$?
In addition to the general $f$$f$ff-GCPI problem, there are the three special variants
• $f$$f$ff-Constructive Group Control by Partitioning of Individuals (CGCPI) where the set ${A}^{-}$${A}^{-}$A^(-)A^- is dropped,
• $f$$f$ff-Destructive Group Control by Partitioning of Individuals (DGCPI) where the set ${A}^{+}$${A}^{+}$A^(+)A^+ is dropped,
• $f$$f$ff-Exact Group Control by Partitioning of Individuals (EGCPI) where we add the premise ${A}^{+}\cup {A}^{-}=N$${A}^{+}\cup {A}^{-}=N$A^(+)uuA^(-)=NA^+ \cup A^- = N.
Group Bribery: In the bribery problems, the attacker can bribe up to $\ell$$\ell$\ell individuals to change their opinion. In this model, we assume that the attacker can arbitrarily alter the outgoing valuations of each bribed individual.
 $f$$f$ff$f$-Group Bribery (GB) Given: A set $N$$N$NN$N$ of individuals, a profile $\phi$$\phi$varphi\varphi$\phi$ over $N$$N$NN$N$, two subsets ${A}^{+},{A}^{-}\subseteq N$${A}^{+},{A}^{-}\subseteq N$A^(+),A^(-)sube NA^+, A^- \subseteq N${A}^{+},{A}^{-}\subseteq N$ with ${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$A^(+)nnA^(-)=O/A^+ \cap A^- = \emptyset${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$, and a positive integer $\ell$$\ell$ℓ\ell$\ell$. Question: Is there a way to obtain a profile ${\phi }^{\mathrm{\prime }}$${\phi }^{\mathrm{\prime }}$varphi^(')\varphi^\prime${\phi }^{\mathrm{\prime }}$ over $N$$N$NN$N$ by changing the outgoing valuations in $\phi$$\phi$varphi\varphi$\phi$ of at most $\ell$$\ell$ℓ\ell$\ell$ individuals such that ${A}^{+}\subseteq f\left(N,{\phi }^{\mathrm{\prime }}\right)$${A}^{+}\subseteq f\left(N,{\phi }^{\mathrm{\prime }}\right)$A^(+)sube f(N,varphi^('))A^+ \subseteq f(N, \varphi^\prime)${A}^{+}\subseteq f\left(N,{\phi }^{\mathrm{\prime }}\right)$ and ${A}^{-}\cap f\left(N,{\phi }^{\mathrm{\prime }}\right)=\mathrm{\varnothing }$${A}^{-}\cap f\left(N,{\phi }^{\mathrm{\prime }}\right)=\mathrm{\varnothing }$A^(-)nn f(N,varphi^('))=O/A^- \cap f(N, \varphi^\prime) = \emptyset${A}^{-}\cap f\left(N,{\phi }^{\mathrm{\prime }}\right)=\mathrm{\varnothing }$? In other words, is there a way to bribe at most $\ell$$\ell$ℓ\ell$\ell$ individuals such that all individuals in ${A}^{+}$${A}^{+}$A^(+)A^+${A}^{+}$ become socially qualified and all individuals in ${A}^{-}$${A}^{-}$A^(-)A^-${A}^{-}$ become socially disqualified with respect to the social rule $f$$f$ff$f$?
In addition to the general $f$$f$ff-GB problem, there are the three special variants
• $f$$f$ff-Constructive Group Bribery (CGB) where the set ${A}^{-}$${A}^{-}$A^(-)A^- is dropped,
• $f$$f$ff-Destructive Group Bribery (DGB) where the set ${A}^{+}$${A}^{+}$A^(+)A^+ is dropped,
• $f$$f$ff-Exact Group Bribery (EGB) where we add the premise ${A}^{+}\cup {A}^{-}=N$${A}^{+}\cup {A}^{-}=N$A^(+)uuA^(-)=NA^+ \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 $\phi$$\phi$varphi\varphi separately. In total, the attacker is allowed to change up to $\ell$$\ell$\ell entries (i.e. replace a $1$$1$11 by a $-1$$-1$-1-1, or a $-1$$-1$-1-1 by a $1$$1$11).
 $f$$f$ff$f$-Group Microbribery (GMB) Given: A set $N$$N$NN$N$ of individuals, a profile $\phi$$\phi$varphi\varphi$\phi$ over $N$$N$NN$N$, two subsets ${A}^{+},{A}^{-}\subseteq N$${A}^{+},{A}^{-}\subseteq N$A^(+),A^(-)sube NA^+, A^- \subseteq N${A}^{+},{A}^{-}\subseteq N$ with ${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$A^(+)nnA^(-)=O/A^+ \cap A^- = \emptyset${A}^{+}\cap {A}^{-}=\mathrm{\varnothing }$, and a positive integer $\ell$$\ell$ℓ\ell$\ell$. Question: Is there a way to obtain a profile ${\phi }^{\mathrm{\prime }}$${\phi }^{\mathrm{\prime }}$varphi^(')\varphi^\prime${\phi }^{\mathrm{\prime }}$ over $N$$N$NN$N$ by changing the valuations in $\phi$$\phi$varphi\varphi$\phi$ for at most $\ell$$\ell$ℓ\ell$\ell$ pairs of individuals such that ${A}^{+}\subseteq f\left(N,{\phi }^{\mathrm{\prime }}\right)$${A}^{+}\subseteq f\left(N,{\phi }^{\mathrm{\prime }}\right)$A^(+)sube f(N,varphi^('))A^+ \subseteq f(N, \varphi^\prime)${A}^{+}\subseteq f\left(N,{\phi }^{\mathrm{\prime }}\right)$ and ${A}^{-}\cap f\left(N,{\phi }^{\mathrm{\prime }}\right)=\mathrm{\varnothing }$${A}^{-}\cap f\left(N,{\phi }^{\mathrm{\prime }}\right)=\mathrm{\varnothing }$A^(-)nn f(N,varphi^('))=O/A^- \cap f(N, \varphi^\prime) = \emptyset${A}^{-}\cap f\left(N,{\phi }^{\mathrm{\prime }}\right)=\mathrm{\varnothing }$? In other words, is there a way to change at most $\ell$$\ell$ℓ\ell$\ell$ entries in $\phi$$\phi$varphi\varphi$\phi$ such that all individuals in ${A}^{+}$${A}^{+}$A^(+)A^+${A}^{+}$ become socially qualified and all individuals in ${A}^{-}$${A}^{-}$A^(-)A^-${A}^{-}$ become socially disqualified with respect to the social rule $f$$f$ff$f$?
In addition to the general $f$$f$ff-GMB problem, there are the three special variants
• $f$$f$ff-Constructive Group Microbribery (CGMB) where the set ${A}^{-}$${A}^{-}$A^(-)A^- is dropped,
• $f$$f$ff-Destructive Group Microbribery (DGMB) where the set ${A}^{+}$${A}^{+}$A^(+)A^+ is dropped,
• $f$$f$ff-Exact Group Microbribery (EGMB) where we add the premise ${A}^{+}\cup {A}^{-}=N$${A}^{+}\cup {A}^{-}=N$A^(+)uuA^(-)=NA^+ \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.. Erdélyi et al. showed the results for the bribery problem, and Boehmer et al. extended their results to the microbribery problem.
Table  lists all the known complexity results for constructive group control and bribery.
 Consent rules ${f}^{\left(s,t\right)}$${f}^{\left(s,t\right)}$f^((s,t))f^{(s, t)}${f}^{\left(s,t\right)}$ ${f}^{\text{CSR}}$${f}^{\text{CSR}}$f^("CSR")f^{\text{CSR}}${f}^{\text{CSR}}$ ${f}^{\text{LSR}}$${f}^{\text{LSR}}$f^("LSR")f^{\text{LSR}}${f}^{\text{LSR}}$ $s=1$$s=1$s=1s=1$s=1$ $s\ge 2$$s\ge 2$s >= 2s \geq 2$s\ge 2$ $t=1$$t=1$t=1t=1$t=1$ $t=2$$t=2$t=2t=2$t=2$ $t\ge 3$$t\ge 3$t >= 3t \geq 3$t\ge 3$ $t=1$$t=1$t=1t=1$t=1$ $t=2$$t=2$t=2t=2$t=2$ $t\ge 3$$t\ge 3$t >= 3t \geq 3$t\ge 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}^{\left(s,t\right)}$${f}^{\left(s,t\right)}$f^((s,t))f^{(s, t)}