Fine-Grained View on Bribery for Group Identification

1 Introduction

The University of Actual Truth (UAT) was paralyzed for months due to a heavy dispute of the scientists about who belongs to the group of true scientists. Starting a mediation process, the scientists quickly agreed that only a (true) scientist could know who qualifies as true scientist. After some literature research on group identification, they asked every scientist to report who they believe is qualified for being a true scientist. Based on these individual qualifications, they applied several group identification rules to find the group of true scientists. Unfortunately, each rule either decided that nobody is a true scientist or that all are true scientists. It is, however, obvious to everyone that the group of true scientists must be a proper non-empty subset of scientists.

As the next step, the UAT scientists computed their "degree of truthfulness" as follows. First of all, every department was invited to submit a proposal specifying who they believe the true scientists are. For every group of scientists being proposed by someone, they computed two different quality measures. For the rules that initially identified nobody as a true scientist, they defined the "truth distance" as the minimum number of scientists whose qualifications would need to be changed to make the proposed group part of the true scientists. For the rules that initially identified everyone as a true scientist, they defined the "margin of truth" as the minimum number of scientists whose qualifications would need to be changed to make no one from the proposed group a true scientist. Although they could not finally agree on the set of true scientists, the dispute was resolved because everyone was included in at least one proposed subset of scientists with minimum truth distance or maximum margin of truth.

The above example describes a problem that appears in many situations where one needs to identify a qualified group of individuals based only on the individuals' pairwise qualifications. To solve this task, group identification rules have been developed [Kasher and Rubinstein, 1997; Samet and Schmeidler, 2003]. Despite the simplicity of our example, it illustrates an important aspect of group identification rules: Group identification rules provide only a binary decision about the membership to a specific group while multiple degrees of certainty about the membership may be desired. In extreme cases (as in the example), the identified group might contain obviously too many or too few individuals. The distances that "solve" this issue in our example are concepts known in the literature, but usually motivated from a different viewpoint: "truth distance" corresponds to constructive bribery and "margin of truth" corresponds to destructive bribery. Herein, the classical bribery model assumes an external agent (with full knowledge over the individual qualifications) that aims to influence the outcome of the group identification process by convincing a limited number of individuals to change their qualifications. While the assumptions behind the classical bribery motivation may be questionable, we emphasize that computing bribery costs as a quality measure is very natural, as illustrated in our example.

Our Contributions

In this paper, we provide a more fine-grained view on computing bribery costs for group identification rules in three ways. First, we allow to combine constructive and destructive bribery. In particular, we allow to specify two sets A+ and A- of individuals that must be (resp. must not be) socially qualified after the bribery. This includes as a special case exact bribery, where one can specify the final socially qualified subgroup. Second, we consider a more finegrained concept of bribery costs called link bribery, where one counts the number of individual qualifications that need to be changed. So far, in the classical model, which we call agent bribery, the number of individuals that alter their qualifications is counted. Third, we complement the classical (P vs. NP) computational complexity landscape by providing a comprehensive analysis of the parameterized complexity focusing on naturally well-motivated parameters such as the bribery cost and the sizes of the sets A+ and A- as well as rule-specific parameters. We refer to Table 1 for an overview of our results and to Section 2 for formal definitions of the rules and parameters. Note that the results for constructive bribery depicted in Table 1b analogously hold for destructive bribery with switched roles of s and t [Erd´elyi et al., 2020].

Related Work

Faliszewski et al. [2009a] introduced bribery problems to the study of elections. Since then, multiple variants of bribery differing in the goal and the pricing of a bribery have been proposed [Faliszewski and Rothe, 2016]. For example, Faliszewski et al. [2009b] introduced microbribery, where the manipulator pays per flip in the preference profile of the given election. Microbribery is conceptually closely related to link bribery in the context of our problem. Furthermore, while Baumeister et al. [2011] already considered a variant of exact bribery in the context of judgment aggregation, we are not aware of any applications of the combined setting of constructive and destructive bribery that we propose in this paper.

Despite different initial motivations, bribery in elections is closely related to the concept margin of victory, where the goal is to measure the robustness of the outcome of an election or the 'distance' of a candidate from winning the election [Cary, 2011; Magrino et al., 2011]. While both concepts have been mostly studied separately, some authors have developed a unified framework [Xia, 2012; Faliszewski et al., 2017b].

Initially, the group identification problem has been mainly studied from a social choice perspective by an axiomatic analysis of the problem and some social rules (see, e.g., [Dimitrov, 2011; Kasher and Rubinstein, 1997; Samet and Schmeidler, 2003]). Possible applications of the group identification problem range from the identification of a collective identity [Kasher and Rubinstein, 1997] to the endowment of rights with social implications [Samet and Schmeidler, 2003]. Among the most important rules studied in the literature are the consent rule [Samet and Schmeidler, 2003] and the two iterative rules: consensus-start-respecting rule (CSR, [Kasher, 1993]) and liberal-start-respecting rule (LSR, [Kasher and Rubinstein, 1997]). Using the consent rule, which is parameterized by integers s and t, each agent qualifying himself is socially qualified if and only if at least s agents qualify him, and each agent disqualifying himself is socially disqualified if and only if at least t agents disqualify him. In iterative rules, some criterion is used to determine an initial set of socially qualified agents which is then iteratively extended by adding all agents who are qualified by at least one agent from the set of already socially qualified agents until convergence is reached. Under CSR, an agent is initially socially qualified if he is qualified by all agents, while, under LSR, all agents qualifying themselves are initially socially qualified.

Recently, Yang and Dimitrov [2018] and Erd´elyi et al. [2020] initiated the study of manipulation by an external agent in a group identification problem for the three mentioned social rules. Yang and Dimitrov [2018] considered the complexity of agent deletion, insertion and partition for constructive control, while Erd´elyi et al. [2020] extended their studies to destructive control. Moreover, Erd´elyi et al. [2020] analyzed the complexity of constructive agent bribery and destructive agent bribery. They proved that for both destructive and constructive bribery, for CSR and LSR, the related computational problems are polynomial-time solvable. Moreover, for constructive bribery, they proved that the computational problems for consent rules with t = 1 are also polynomialtime solvable. On the other hand, for t ≥ 2 and s ≥ 1, constructive bribery is already NP-complete. Finally, Erd´elyi et al. [2020] established a close relationship between constructive and destructive bribery by proving that every constructive bribery problem with f (s,t) can be converted into a destructive bribery problem with f (t,s) by flipping all qualifications.

The group identification problem is formally related to multiwinner voting [Faliszewski et al., 2017a]. However, multiwinner voting is of a different flavor both in terms of intended applications and studied social rules. Nevertheless, formally, group identification is equivalent to approvalbased multiwinner voting with a variable number of winners where the set of voters and candidates coincide. While (approval-based) multiwinner voting with a variable number of winners has been studied by, for example, Duddy et al. [2016], Kilgour [2016] and Faliszewski et al. [2017c], this setting has never been studied from a voting perspective. Moreover, so far, the work on bribery for (approvalbased) multwinner elections is limited to the setting where the number of winners is fixed [Bredereck et al., 2016; Faliszewski et al., 2017b]. Similar to our motivation, Faliszewski et al. [2017b] also studied how to measure margin of victory in approval-based multiwinner elections through the lens of bribery.

2 Preliminaries

Group Identification. Given a set of agents A = {a1, . . . , an} and a so-called qualification profile ϕ: A×A→ {-1, 1}, the group identification problem asks to return a subset of socially qualified agents using some social rule f. We write f(A, ϕ) to denote the set of agents that are socially qualified in the group identification problem (A, ϕ) according to f. All agents which are not socially qualified are called socially disqualified. For two agents a, a′ ∈ A, we say that a qualifies a′ if ϕ(a, a′ ) = 1; otherwise, we say that a disqualifies a′ . For each agent a ∈ A, let Q+ϕ (a) = {a′ ∈ A | ϕ(a′ , a) = 1} denote the set of agents qualifying a and Q-ϕ (a) = {a′ ∈ A | ϕ(a′ , a) = -1} the set of agents disqualifying a in ϕ. Let A∗ = {a ∈ A | ∀a′ ∈ A : ϕ(a′ , a) = 1} be the set of agents who are qualified by everyone. For every group identification problem, A and ϕ induce a so-called qualification graph GA,ϕ = (A, E) with (a, a′ ) ∈ E if and only if ϕ(a, a′ ) = 1. For two agents a, a′ , we say that there exists a path from a to a′ in (A, ϕ) if there exists a path from a to a′ in GA,ϕ.

Table 1: Overview of our results. Additionally, in Theorem 4, we prove that CONST-f CSR /f LSR LINK BRIBERY is FPT wrt. |A+|. In Theorem 3, we prove W[2]-hardness of CONST-f CSR /f LSR LINK BRIBERY wrt. ℓ. Results with a † were proven by Erd´elyi et al. [2020].

Now, we define social rules considered in this paper: For the liberal-start-respecting rule (f LSR ), we start with the set K1 = {a ∈ A | ϕ(a, a) = 1} and compute the set of socially qualified agents iteratively for i = 2, . . . using

Notice that we always have Ki-1 ⊆ Ki. We stop the process when Ki-1 = Ki and output Ki.

For the consensus-start-respecting rule (f CSR ), we start with the set K1 = A∗ and for i = 2, . . . we use Equation (1) to compute iteratively the set of socially qualified agents. Note that it is also possible to compute the set of socially qualified agents under f LSR and f CSR as the set of agents that correspond to vertices in the qualification graph that are reachable from vertices with a self-loop and with incoming arcs from all vertices, respectively.

The consent rule (f (s,t) ) with parameters s and t with s + t ≤ n + 2 determines the set of socially qualified agents as follows: If ϕ(a, a) = 1 for an agent a ∈ A, then a is socially qualified if and only if |Q+(a)| ≥ s . If ϕ(a, a) = -1 for an agent a ∈ A, then a is socially disqualified if and only if |Q-(a)| ≥ t .

Bribery Variants. In the most general form of bribery, which we call CONSTRUCTIVE+DESTRUCTIVE (CONST.+DEST.) bribery, we are given a group identification problem (A, ϕ) and a social rule f together with two groups of agents A+ and A- and a budget ℓ. The task is then to alter the qualification profile ϕ such that in the altered profile ϕ′ all agents in A+ are socially qualified, i.e., A+ ⊆ f(A, ϕ′ ), and all agents in A- are socially disqualified, i.e., A- ⊆ A \ f(A, ϕ′ ). The cost of the bribery (computed as specified below) is not allowed to exceed ℓ.

We also consider the following three special cases of CONST+DEST-BRIBERY:

CONSTRUCTIVE (CONST.) Given a set A+ ⊆ A of agents find a bribery such that A+ ⊆ f(A, ϕ′ ).

DESTRUCTIVE (DEST.) Given a set A- ⊆ A of agents find a bribery such that A- ⊆ A \ f (A, ϕ′ ).

EXACT Given a set A+ ⊆ A of agents find a bribery such that A+ = f (A, ϕ′ ).

We now specify the cost of a bribery: In AGENT BRIBERY, the cost of a bribery is equal to the number of agents whose opinions are modified. Consequently, we ask whether it is possible to achieve the specified goal by altering the preferences of at most ℓ agents, where the briber is allowed to change the preferences of each agent in an arbitrary way. On the other hand, in LINK BRIBERY, the cost of a bribery is equal to the number of single qualifications changed. Therefore, we ask whether it is possible to achieve the specified goal by altering at most ℓ qualifications, that is, flipping at most ℓ entries in ϕ.

3 Iterative Rules

Agent Bribery. For agent bribery, the already known positive results for constructive bribery and destructive bribery extend to constructive+destructive bribery. The algorithm for the general problem, however, is more involved than the known ones, as "positive" and "negative" constraints need to be taken into account. The general idea of the algorithm is to bribe the agents that form a minimum separator between the agents in A+ and the agents in A- in the qualification graph such that they qualify themselves and all agents in A+.

Theorem 1. CONST+DEST-f CSR /f LSR AGENT BRIBERY is solvable in polynomial time.

Proof. In the following, we prove the theorem for f LSR . The proof for f CSR works similar. Let L = {a ∈ A- | ϕ(a, a) = 1} be the set of all agents in A- who qualify themselves. We first bribe all agents a ∈ L such that they disqualify everyone. To determine which further agents we want to bribe, we try to find a minimum separator between the nodes A+ and Ain the qualification graph G. To this end, we introduce one source node σ into G and connect σ to all nodes in A+ and nodes with a self-loop. Moreover, we merge all nodes in Ainto one sink node τ . Subsequently, we calculate a minimum (σ, τ)-separator A′ , which can be done in polynomial time [Even, 1975].

If A′ = ∅ and all agents a ∈ A+ are already socially qualified, we are done. If A′ = ∅ and this is not the case, we bribe an arbitrary agent a ∈ A+ and make him qualify all agents in A+ (including himself) and disqualify all other agents. Now, all agents in A+ are socially qualified, and since A′ = ∅, all agents in A- are socially disqualified.

If A′ ̸= ∅, as the existence of a (σ, τ)-path in the constructed graph implies that some agent in A- will be socially qualified as soon as we make all agents in A+ socially qualified, we need to bribe at least |A′ | more agents to destroy all (σ, τ )-paths.

In fact, we bribe all agents in A′ such that they qualify themselves and all agents in A+ and disqualify all other agents. Let G′ be the resulting underlying graph which is obtained from G by deleting all edges corresponding to qualifications that got deleted and adding edges corresponding to qualifications that got inserted. By construction, there is no (σ, τ)-path in G′ . In the modified qualification profile, all agents in A+ are socially qualified, as they are qualified by at least one agent a ∈ A′ qualifying himself. We claim that no agent in A- can be socially qualified. Assume that there exists an agent a- ∈ A- that is socially qualified. Then, there exists a path from some agent a∗ which qualifies himself to a- in the altered instance. If a∗ ̸∈ A′ , then such a path implies that there exists an (σ, τ)-path in G′ which cannot be the case. If a∗ ∈ A′ , since a∗ only qualifies agents from A+ and himself, there is also a path from some agent in A+ to ain the altered instance. This also implies that there needs to exist an (σ, τ)-path in G′ which cannot be the case.

From this it immediately follows that agent bribery is also polynomial-time solvable for all other considered variants including the previously unstudied case of exact bribery.

Corollary 1. EXACT-/CONST-/DEST-f CSR /f LSR AGENT BRIBERY is solvable in polynomial time.

Link Bribery. We now turn to the setting of link bribery and settle the complexity of the related decision problem for all problem variants considered in this paper. We start by proving that the problem is polynomial-time solvable for destructive bribery and exact bribery. For destructive bribery, similar to Theorem 1, we separate the agents that are initially socially qualified from the agents in A- in the qualification graph. However, here, as we pay per changed qualification, we need to calculate a minimum cut.

Theorem 2. DEST-f CSR /f LSR LINK BRIBERY and EXACTf CSR /f LSR LINK BRIBERY are solvable in polynomial time.

Proof. We exemplarily prove the theorem for DESTf LSR LINK BRIBERY: We start by bribing all agents from Awho qualify themselves such that they all disqualify themselves. Let G be the qualification graph of the altered instance. We now consider a slightly modified version of G and calculate a minimum cut to solve the problem. First of all, we add a source node σ to G and connect σ to all nodes with a self-loop. Additionally, we introduce a sink node τ and n2 + 1 dummy nodes. We connect every node from A- to all dummy nodes and all dummy nodes to the sink τ. Now, we compute a minimum (σ, τ)-cut E′ ⊆ E, which can be done in polynomial time [Karger and Stein, 1996], and remove the corresponding qualifications from the qualification profile: If (a, a′ ) ∈ E′ for some a, a′ ∈ A, we make a disqualify a′ . If (σ, a) ∈ E′ for some a ∈ A, we make a disqualify himself. No edge starting or ending in some dummy node will be in E′ , as such an edge can never be part of a minimum cut. After this bribery, no agent a- ∈ A- is socially qualified, as the absence of a (σ, τ)-path implies that there does not exist a path from an agent qualifying himself to a- in the altered qualification profile. On the other hand, the described bribery is optimal, as the existence of a (σ, τ)-path always implies that at least one agent in A- is socially qualified in the end.

In contrast to this, the corresponding problem for constructive bribery is NP-complete. This difference in the complexity of the problem for constructive bribery and destructive bribery is somewhat surprising, as their complexity is the same in the case of agent bribery. We show the hardness of CONST-f CSR /f LSR LINK BRIBERY by a reduction from SET COVER, which is NP-complete and W[2]-hard with respect to the requested size of the cover. The general idea of the reduction is to introduce one agent for each element (these form the set A+) and for each set, where each set-agent qualifies the agents corresponding to the elements in the set.

Theorem 3 (∗). CONST-f CSR /f LSR LINK BRIBERY is NPcomplete and W[2]-hard with respect to ℓ.

Apart from the parameter budget ℓ, which might be small in most applications as only agents which are close to the boundary of being socially (dis)qualified might be interested in their precise margin, another natural parameter is the set of agents we want to make socially qualified, i.e., |A+|. This parameter may also be not too large in most applications, as one is usually only interested in the classification of a limited number of agents. In contrast to the negative parameterized result for ℓ, utilizing that SET COVER is FPT with respect to the size of the universe, it is possible to prove that CONSTf CSR /f LSR LINK BRIBERY is FPT with respect to |A+| by reducing this problem to an instance of SET COVER and applying the algorithm from Fomin et al. [2004].

Theorem 4 (∗). CONST-f CSR /f LSR LINK BRIBERY is FPT with respect to |A+|.

The hardness results for constructive bribery imply that constructive+destructive bribery is also NP-hard and W[2]- hard with respect to ℓ. Utilizing a slightly more involved reduction from EXACT COVER BY 3 SETS, it is even possible to show that the NP-hardness of constructive+destructive bribery extends to the case where the briber is only allowed to delete qualifications. This is surprising, as destructive bribery alone is polynomial-time solvable.

Proposition 1 (∗). CONST+DEST-f CSR /f LSR LINK BRIBERY remains NP-complete even if the briber is only allowed to delete qualifications.

A remaining question is to pinpoint the parameterized complexity of constructive+destructive bribery with respect to |A+| + |A-|. Despite the fact that the FPT result for constructive bribery suggests that it may be possible to prove FPT for this case, we were not even able to prove that this problem lies in XP, leaving this as an open problem for future work.

4 Consent Rule

Link Bribery. CONST+DEST-f (s,t) LINK BRIBERY is polynomial-time solvable. For each a+ ∈ A+ \ f(A, ϕ), the optimal strategy is to make him qualify himself and to make s - |Q+ϕ (a+)| agents from Q-ϕ (a+) qualify him. For A-, we proceed analogously. Thereby, all problem variants for link bribery are polynomial-time solvable.

Agent Bribery. Erd´elyi et al. [2020] proved that constructive agent bribery is NP-complete for all s ≥ 1 and t ≥ 2 by a reduction from VERTEX COVER in which they set A+ = A. This implies the following:

Observation 1. EXACT-/CONST+DEST-f (s,t) AGENT BRIBERY is polynomial-time solvable for s = t = 1. For all other values of s and t, this problem is NP-complete.

Studying bribery problems for the consent rule, s and t are natural parameters to consider, as at least one of these parameters may be small in most applications: In problems where socially qualified agents acquire a privilege, t should be small, while for problems where social qualification implies some obligation or duty, s should be small. However, the hardness result of Erd´elyi et al. [2020] for constructive bribery directly implies that this problem is para-NP-hard with respect to s + t. The reduction has no implications on the parameterized complexity of the problem with respect to ℓ and |A+|. In the following, we conduct a parameterized analysis of CONST-f (s,t) AGENT BRIBERY with respect to s, t, ℓ and |A+|, before we explain how to adapt our results to the other three variants considered.

Erd´elyi et al. [2020] further proved that CONSTf (s,t) AGENT BRIBERY is in XP with respect to s if t = 1. However, they left open whether this problem is FPT or W[1]- hard with respect to s. Moreover, there exists a trivial brute force XP-algorithm for ℓ, while it is again open whether the problem is FPT or W[1]-hard with respect to ℓ. We answer both questions negatively in the following theorem:

Theorem 5. CONST-f (s,t) AGENT BRIBERY is W[1]-hard with respect to s + ℓ even if t = 1.

Proof. We reduce from INDEPENDENT SET (G = (V,E), k), which is W[1]-hard with respect to k. Given an instance of the problem, in the group identification problem, we insert for each vertex v ∈ V , one vertex-agent av and, for each edge {u, v} ∈ E, one edge-agent au,v and one designated dummy agent ˜au,v. We set A+ = {au,v, ˜au,v | {u, v} ∈ E}. All dummy agents qualify only themselves. For each {u, v} ∈ E, au,v qualifies ˜au,v and himself, while he is only qualified by the two agents au and av. We set s = k + 2, t = 1 and ℓ = k. Note that all dummy agents need at least k additional qualifications to be socially qualified, while all edge-agents need at least k - 1 additional qualifications.

⇒: Assume that V ′ ⊆ V is an independent set of size k in G. Then, we bribe all vertex-agents that correspond to the agents in V ′ and let them qualify everyone. Thereby, every edge-agent gains at least k - 1 additional qualifications, as every edge-agent was qualified by at most one agent av with v ∈ V ′ before the bribery. Moreover, as no vertex-agent qualifies a dummy agent, all dummy agents gain k qualifications.

⇐: Assume we are given a successful bribery A′ ⊆ A consisting of k agents. We claim that only vertex-agents can be part of A′ . Assuming that for some {u, v} ∈ E either au,v or ˜au,v are part of A′ , ˜au,v cannot be socially qualified after the bribery, as he gained at most k - 1 qualifications over the bribery. It additionally holds that, for each {u, v} ∈ E, at most one of av and au can be part of A′ , as au,v gained at least k - 1 additional qualifications by the bribery. Thereby, A′ consists of k vertex-agents which initially do not qualify the same edge-agent twice. From this it follows that V ′ = {v ∈ V | av ∈ A′ } is an independent set of size k in G.

This reduction relies crucially on the fact that no nonvertex-agent can be bribed. This is ensured by the dummy agents for which the number of qualifications they are missing to become socially qualified is equal to the given budget. In fact, if we are given an instance of the problem with parameters s, ℓ and t = 1 and we can bound the number of agents a for which it holds that ℓ = s - |Q+(a)| by some function g in s, we can solve the problem in time g(s)O(n2 ) using a recursive branching algorithm.

From Theorem 5 it follows that combining ℓ with parameters s and t is not enough to achieve fixed-parameter tractability. The only case that is left open is the case where we treat s as a constant. Here, parameterizing the problem by ℓ is not enough to achieve fixed-parameter tractability even in the restricted case where s = 1. This can be shown by a reduction from DOMINATING SET where we introduce for each vertex a vertex-agent, which we include in the set A+. All vertexagents qualify everyone except themselves and their neighbors. Moreover, we insert additional dummy agents such that every agent gets the same number of disqualifications.

Theorem 6 (∗). CONST-f (s,t) AGENT BRIBERY is W[2]- hard with respect to ℓ even if s = 1.

Parameterizing the problem by ℓ + t, however, while treating s as a constant, the problem becomes, in fact, fixedparameter tractable:

Theorem 7. CONST-f (s,t) AGENT BRIBERY is FPT with respect to ℓ + t (treating s as a constant).

Proof sketch. We give a proof sketch for the special case where s = 1. For each a ∈ A, let ya = max(0, |Q-(a)| - (t - 1)), i.e., ya is the number of additional qualifications a needs to get to become socially qualified without qualifying himself. Let A′ be the set of agents that we bribe (it is always rational to make all agents in A′ qualify everyone). For every a ∈ A+ with ya > ℓ, it needs to hold that a ∈ A′ . More generally, for all a ∈ A+, either a ∈ A′ or a ya-subset of Q-(a) needs to be part of A′ . These ideas give rise to Algorithm 1. This algorithm called as CalcB(A,ϕ,A+,∅,ℓ) returns a successful bribery A′ if one exists.

The depth of the recursion is bounded by ℓ. Moreover, the branching factor is bounded by |Q-(a∗ )| + 1. As for every a∗ it needs to hold that ya ≤ ℓ, it follows that |Q-(a∗ )| ≤ ℓ+(t-1). Thereby, the overall running time of the algorithm lies in O(n2 (ℓ + t)ℓ ).

For s ≥ 1, the same underlying reasoning applies. However, here, in the case where we want to make an agent a ∈ A+ qualifying himself (either in the case where ya > ℓ or in the branching in line 8), we additionally need to branch over bribing all max(0, s - |Q+(a)|)-subsets of Q-(a) to make a socially qualified in the end.

Algorithm 1 CalcB(A,ϕ, A+, A′ ,p)

Input: Agents A, qualification profile ϕ, subset of agents A+ and A′ , maximal depth of recursion p

Output: Set of agents A′ to bribe

• 1: for a ∈ A+ with ya - |A′ ∩Q-(a)| > p do
• 2: A′ = A′ ∪ {a}; A+ = A+ \ {a}; p = p-1;
• 3: for a ∈ A+ with a ∈ A′ or |A′ ∩Q-(a)| ≥ ya do
• 4: A+ = A+ \ {a};
• 5: if p < 0 then return Reject
• 6: if A+ = ∅ then return A′
• 7: Pick an arbitrary a∗ ∈ A+
• 8: for a ∈ {a∗ } ∪ (Q-(a∗ ) \ A′ ) do
• 9: return CalcB(A,ϕ, A+, A′ ∪ {a}, p - 1)

Finally, analyzing the influence of the number of agents that should be made socially qualified on the complexity of the problem, it turns out that restricting this parameter is more powerful than restricting ℓ, as the problem is FPT with respect to |A+| for arbitrary s and t.

Theorem 8. CONST-f (s,t) AGENT BRIBERY is FPT with respect to |A+|.

Proof. We reduce to an ILP with |A+| + 1 constraints: First, we guess the subset ˜ A+ ⊆ A+ of agents from A+ which qualify themselves in the end. We make all agents a ∈ ˜ A+ qualify everyone and all agents a ∈ A+ \ ˜ A+ disqualify themselves and qualify everyone else (we lower the budget ℓ accordingly). Now, for every agent a ∈ A, we introduce a variable xa ∈ {0, 1} (with xa = 1 if and only if we are going to bribe a). We have two types of conditions based on ˜ A+:

Finally, we require ∑a∈A xa ≤ ℓ. If the above ILP is feasible, then there exists a successful bribery (given by xa = 1). We bribe all a ∈ A\(A+ \ ˜ A+) with xa = 1 to qualify everyone including themselves and all a ∈ A+ \ ˜ A+ with xa = 1 to qualify everyone excluding themselves. In the bribed instance, for every agent a ∈ ˜ A+, we have ϕ(a, a) = 1 and at least s agents qualify a, and for every agent a ∈ A+ \ ˜ A+, we have ϕ(a, a) = -1 and at most t - 1 agents disqualify a. We use the algorithm of Eisenbrand and Weismantel [2018] to solve the above ILP in time O(n|A+||A+|2 ).

By Lemma 1 of Erd´elyi et al. [2020], all results from above naturally extend to DEST-f (s,t) AGENT BRIBERY where s and t switch roles. Moreover, it is also possible to extend some of our results to constructive+destructive bribery by a slight adaption of Theorem 8 and Theorem 6:

Corollary 2 (∗). CONST+DEST-f (s,t) AGENT BRIBERY is FPT with respect to |A+| + |A-|. CONST+DESTf (s,t) AGENT BRIBERY parameterized by ℓ + t is W[2]-hard even if s is one and also W[2]-hard with respect to ℓ+s even if t is one.

Aiming for positive results, parameterizing constructive+destructive bribery by just one of |A+| and |A-| is not enough, as the problem is even NP-hard for s = 2 and t = 1 and A+ = ∅, which follows from the reduction from Erd´elyi et al. [2020] mentioned at the beginning of this section.

Finally, we consider exact bribery. Here, the two W[2]- hardness results from the previous corollary, which follow from Theorem 5, extend to this setting, as it is possible to precisely specify the desired outcome of the group identification problem in the reduction in Theorem 5. While parameterizing the problem by |A+|+|A-| is not meaningful in this context, as discussed above, one of |A+| and |A-| combined with s and t is not enough to achieve any positive results.

5 Conclusion

We extended the research on bribery in group identification by considering a new model for bribery cost and two new bribery goals. Moreover, we described how it is possible to use bribery as a method to calculate the margin of victory or distance from winning in a group identification problem. We showed that for all considered rules both quantities can be computed efficiently if the number of agents whose social qualification we want to change is small. Moreover, we identified some further cases where the general problem is polynomial-time solvable: For both LSR and CSR, we observed that every bribery involving destructive constraints somehow splits the qualification graph into two parts. As in agent bribery it is easy to make multiple agents socially qualified at the same time, this observation gives rise to a polynomial-time algorithm for the most general variant of constructive+destructive bribery. For link bribery, it is possible to use this observation to construct a polynomial-time algorithm for destructive bribery. However, the corresponding question for constructive bribery is NP-hard.

For the consent rule, link bribery turns out to be solvable in a straightforward way. In contrast to this, for agent bribery, finding an optimal bribery corresponds to finding a set of agents fulfilling certain covering constraints. This task makes the problem para-NP-hard with respect to s + t [Erd´elyi et al., 2020] and W[1]-hard with respect to ℓ even for t = 1 or s = 1. We proved that in the constructive setting, the rule parameter t is slightly more powerful than the rule parameter s in the sense that the problem is still hard parameterized by s+ℓ even if t = 1, while becoming fixed-parameter tractable parameterized by t + ℓ for constant s.

Acknowledgments

NB was supported by the DFG project MaMu (NI 369/19). DK is partly supported by the OP VVV MEYS funded project CZ.02.1.01/0.0/0.0/16 019/0000765 "Research Center for Informatics"; part of the work was done while DK was affiliated with TU Berlin and supported by project MaMu (NI 369/19). JL was supported by the DFG project AFFA (BR 5207/1 and NI 369/15). This work was started at the research retreat of the TU Berlin Algorithms and Computational Complexity group held in September 2019.