Manipulation of k-Coalitional Games on Social Networks

1 Introduction

Coalition formation is one of the fundamental research problems in multi-agent systems [Chalkiadakis et al., 2011]. Broadly speaking, coalition formation is concerned with partitioning a population of agents into disjointed teams (or coalitions) with the aim that some system-wide performance measure is maximized. Indeed, in many coalition formation games there is a central organizer that would like to maximize some objective.

One assumption that is usually made is that the utility function of the agents is known and given as an input. However, in some real-world scenarios the organizer obtains the information regarding the utility function directly from the agents. For example, when dividing students into classes, it is a common practice to ask the students about their social relationships [Alon, 2019], since a student is more satisfied if the number of friends she has within the class to which she is assigned is maximized. Similarly, when assigning workers to tasks, a manager would be interested in the interpersonal relationships between potential team members. Ideally, the agents would report their true social relationships so that the organizer will be able to choose the most appropriate coalition structure. However, there might be scenarios in which an agent is better off manipulating the organizer by misreporting his relationships.

Indeed, the problem of manipulation in the context of coalitional games has been studied recently [Wright and Vorobeychik, 2015; Flammini et al., 2017]. These studies have looked for strategyproof mechanisms for forming the coalitions, at the cost of non-optimal social welfare (SW). In this paper we propose a complementary approach. We study in which situations there might be an agent with an incentive to manipulate the organizer, and in which situations no agent has an incentive to manipulate the organizer, and thus a special strategyproof mechanism is not needed (see [Vall´ee et al., 2014] for a similar approach). This analysis is in the same vein as the works of [Gibbard, 1973] and [Satterthwaite, 1975] in the context of voting, that studied in which situations there might be a voter with an incentive to misreport her true vote.

We focus on k-coalitional games, where exactly k coalitions must be formed [Sless et al., 2018]. We assume that the agents' utilities depend on a social network that represents the social relationships among the agents. Specifically, the social network is modeled as an unweighted graph where the vertices are agents and the edges indicate friendship among the agents. The utility function of an agent is the number of friends she has within the coalition to which she is assigned. Actually, our model is a special case of simple Additively Separable Hedonic Games (ASHGs) [Bogomolnaia et al., 2002]. In addition, there is an organizer that would like to maximize some objective function, thus she needs to obtain the structure of the social network from the agents' reports regarding their friendships. In such situations, it is possible that one manipulative agent would like to misreport his friendship connections, in order to increase his utility. In particular, a Directed Undirected Add Remove Add Remove Max-Util Strict(F 3a)

Strict(F 2b)

Strict(F 3a)

Strict(F 2a)*

Max-Egal Strategyproof(T 2)

Strict(F 2e)

LB,UB(F 3b,3c), W-proof(T 1)

Strict(F 2f)

At-least-1 Strategyproof(T 3) LB(F 2g), UB-Proof(T 4)

Strict(F 3d)

LB(F 2g),UB-proof(T 4)

Table 1: Summary of the results. The parentheses near a result refer to the corresponding figure (F) or theorem (T). The results hold for both

full information and distance 2, except for the result with the * , which holds only for the full information case. Key: LB/UB/Strict = the

objective is subject to LB/UB/Strict-improvement, W-proof = the objective is weak-proof.

manipulator may hide some of his connections or he may add connections by reporting fake connections (with agents with which the manipulator does not have real connections).

Within these settings we study different objectives for the organizer and analyze their susceptibility or resistance to manipulation. Specifically, we study the objective of maximizing the utilitarian social welfare (Max-Util), maximizing the egalitarian social welfare (Max-Egal), and the At-least-1 objective, where the organizer is only interested in guaranteeing that every agent will have at least one friendship connection within her coalition. Moreover, we study different settings regarding the abilities and information that the manipulator has. Specifically, we study a manipulator that is able to report fake friendship connections (i.e. add edges) and a manipulator that is able to hide some of his friendship connections (i.e., remove edges). We study the situation in which the manipulator has full information regarding the structure of the network and situations in which the manipulator has limited information: he may be familiar only with his connections to his immediate neighbours in the social network (denoted distance 1), or he may also be familiar with their connections to other agents (denoted distance 2). (In both scenarios the manipulator knows about the existence of all agents in the social network, but not how they are connected.)

Table 1 summarizes our results for the full information and distance 2 settings. Overall, all of the objectives are susceptible to manipulation by removing edges, even in the case of distance 2. On the other hand, in some settings there are objectives that are resistant to manipulation by adding edges, even in the case of full information. Note that the results for distance 1 do not appear in the Table, since in almost all of the cases the objectives are resistant to manipulation.

2 RelatedWork

There are several studies that developed strategyproof mechanisms for forming coalitions. Dimitrov and Sung [2004] discussed ASHGs where agents have both positive and negative edges, and provided a strategyproof algorithm for finding stable outcomes. Rodr´ıguez- ´Alvarez [2009] analyzed strategyproof core stable solutions' properties. They showed that single lapping rules are necessary and sufficient for the existence of a unique core-stable partition. Aziz et al. [2013a] showed that the serial dictatorship mechanism is strategyproof with appropriate restrictions over the agents' preferences. Flammini et al. [2017] focused on the utilitarian SW in ASHGs and Fractional Hedonic Games, and proposed strategyproof mechanisms at the cost of non-optimal social welfare. Wright and Vorobeychik [2015] studied a model of ASHG that is very similar to our model, but instead of restricting the number of coalitions they restricted the size of each coalition. Within their model they proposed a strategyproof mechanism that achieves good and fair experimental performance, despite not having a theoretical guarantee. All of these works have looked for strategyproof mechanisms, while our approach is to study in which situations a strategyproof mechanism is indeed needed, and in which situations it is not needed since manipulation is impossible.

Our approach is similar to the approach of Vall´ee et al. [2014], who studied general hedonic games and Sybil attacks, i.e., manipulations, by adding false agents to the game. Vall´ee et al. showed that hedonic games with Nash stability as the solution concept are very robust to Sybil attacks, but when contractual individual stability is the solution concept then every game is manipulable. Recently, Alon [2019] considered the At-least-1 objective, and analyzed whether a group of manipulators can guarantee being in the same coalition in every game. Alon showed that such manipulation is almost always impossible.

3 Definitions

Let A = {a1, . . . , an} be a finite, non-empty set of agents, and let G = (A, E) be a graph with no self loops, representing the friendship connections between the agents. The set of immediate neighbours of ai in G is denoted by N(ai). We also refer to G as the social network. A coalition C ⊆ A is a subset of agents; we do not require that agents in a coalition form a connected component in the corresponding social network. Let u(ai,C) be the utility that agent ai would obtain from being in coalition C. This value is simply the sum of edges corresponding to the immediate neighbors of ai that are members of C. That is, u(ai, C) = |C ∩ N(ai)|.

We assume that there is a central organizer that would like to partition the agents into k coalitions in order to satisfy some objective, obj. Let Πk denote the set of partitions of A that contain exactly k non-empty subsets where 0 < k ≤ n. We refer to elements of Πk as coalition structures (CS), and typically use P, P ′ , . . . to denote such coalition structures. We assume that the utility of agent a depends only on the members of her coalition. Therefore, if P ∈ Πk, C ∈ P, and a ∈ C, then we use the notation u(a, P) to refer to u(a,C). Note that there may be several coalition structures that satisfy a given objective obj. We denote this set of coalitions as Oobj(G) ⊆ Πk and refer to them as solutions. In many cases we omit the reference to obj when it is clear.

In our setting the social network is formed based on self reports of the agents. That is, each agent ai is asked by the organizer to list all of her friendship connections. Formally, let R = {r1, . . . , rn} be the set of reports, where ri ⊆ A \ {ai}. In such a scenario there might be a manipulative agent m. We begin by assuming that m has full information regarding the social network (we relax this assumption in Section 5) and the objective of the central organizer, obj. Moreover, we assume that m is able to misreport his friendship connections and thus add non-existing edges connecting him to other agents or omit existing edges between him and other agents. We denote these two types of manipulators by m+ and m-, respectively. We did not consider a manipulator that is capable of both adding and removing edges since it does not add any new results: in all of our objectives only one capability is needed to show susceptibility to manipulation. Let Gm = (A,Em) be the resulting social network known to the organizer after the manipulation rm, and let N m(a) be the set of immediate neighbours of a in Gm. Note that if G is directed then we assume that m is able to add or remove only outgoing edges, i.e., add an edge (m, ai) /∈ E or remove an edge (m, ai) ∈ E. m is not able to add or remove incoming edges, i.e., add an edge (ai,m) /∈ E or remove an edge (ai,m) ∈ E. That is, N(a) = N m(a) for every agent a ̸= m. If G is undirected then a manipulation by adding edges is relevant when the organizer adds an edge (ai, aj) to G if either ai ∈ rj or aj ∈ ri. On the other hand, a manipulation by removing edges is relevant when the organizer adds an edge (ai, aj ) to G only when both ai ∈ rj and aj ∈ ri. When the context is clear we will sometimes refer to Gm as the manipulation.

Clearly, the goal of the manipulator is a successful manipulation. Indeed, in our setting there are several ways to define what a successful manipulation is, since there may be several coalition structures that satisfy obj in G and in Gm, but the utility of m might be different in each such coalition structure. Formally, given a network G and objective obj:

Definition 1. A manipulation rm is a lower bound improvement (LB-improvement) for a manipulator m if:

A manipulation rm is an upper bound improvement (UBimprovement) for a manipulator m if:

That is, LB-improvement eliminates coalition structures with low utility for the manipulator, while UB-improvement adds coalition structures with higher utility for the manipulator. For example, assume that for an objective obj and a graph G there are two possible CSs. That is, Oobj(G) = {P1, P2}. Moreover, assume that u(m, P1) = 1 and u(m, P2) = 2. If there exists a manipulation rm where Oobj(Gm) = {P2} (or any other P satisfying u(m, P) = 2) then Gm is a LB-improvement. If there exists a manipulation rm where Oobj (Gm) = {P1, P3} and u(m, P3) = 3 then Gm is an UBimprovement. LB-improvement can be considered risk aversion of some sort, while UB-improvement suits an optimistic manipulator looking for higher utilities.

There is a stronger variant of manipulation which is both LB- and UB-improvement. An even stronger variant is where every coalition structure is strictly better than every possible coalition structure that would have been generated with m's true preferences. Formally:

Definition 2. A manipulation rm is a weak-improvement for a manipulator m if it is both LB-improvement and UB-improvement for him. A manipulation rm is a strictimprovement for a manipulator m if:

Revisiting our example, a manipulation where Oobj(Gm) = {P3} is a strict-improvement. Note that the utility u(m, P) is always calculated over the original graph G with the manipulator's true neighbours. We refer to the different manipulations: LB, UB, weak, and strictimprovement, as manipulation types. Finally, we define the susceptibility and resistance to a manipulation type of a given objective.

Definition 3. An objective obj is subject to LB-improvement by manipulator m over (un)directed networks if there exists a (un)directed social network G and a manipulation rm such that rm is a LB-improvement for m. Otherwise, we say that obj is LB-proof against m.

The definitions for the other manipulation types are similar. When an objective is both LB- and UB-proof, we say that it is strategyproof. Figure 1 demonstrates the possible utility values of the manipulator for each manipulation type.

4 Full Information

We begin our analysis of the objectives and their susceptibility or resistance to the different types of manipulation. To show susceptibility to manipulation, we provide figures that depict the scenarios in which manipulation is possible. We use k = 2 in all of our proofs, but they can easily be extended for any k. We use the following notations: In all of the figures the vertex m represents the manipulator. A node is represented by a circle, and a rectangle with a number X represents a clique of X agents. An edge going to (from) a clique represents edges going to (from) all nodes in the clique. An edge going to (from) a clique with a number X represents X edges going to (from) arbitrarily chosen X nodes in the clique. If the graph is directed, then an undirected edge (a, b) represents two directed edges, (a, b) and (b, a). If we prove a result regarding an undirected graph and refer to a figure with a directed graph then every directed edge represents an undirected edge. Overall, Figure 3 provides scenarios for m+ and Figure 2 provides scenarios for m-. Therefore, the dotted edges in Figure 2 are the fake edges that are added by the manipulator, while the dotted edges in Figure 2 are the edges that are removed by the manipulator.

We note that almost all of the susceptibility results in the full information setting (except for Proposition 1) are derived by the results of susceptibility in the distance 2 setting (see Section 5.1). Therefore, in this section we mostly provide the results regarding resistance to manipulation.

4.1 Max-Util

Maximizing the utilitarian social welfare (Max-Util) is a very common objective in hedonic games [Aziz et al., 2015]. It was also studied from the perspective of graph theory, since finding a CS (with k coalitions) that maximizes the utilitarian SW is equivalent to finding a minimum k-cut [Brˆanzei and Larson, 2009]. Utilitarian SW is defined as the sum of the utilities of all agents. Formally, it is ∑ a∈Au(a, P ).

Max-Util is always susceptible to manipulation; in all of the situations that we consider, this objective is subject to strict-improvement. Recall that our susceptibility results are derived from the distance 2 setting. However, there is one situation in which the susceptibility to manipulation in the distance 2 setting is not known , and thus we show that even in this situation Max-Util is subject to strict-improvement.

Proposition 1. Max-Util is subject to strict-improvement by a manipulator m- over an undirected network.

Proof. Consider the network G as depicted in Figure 2a. Recall that k = 2. Clearly, the minimum 2-cut is obtained by cutting the upper clique ({a, b, c, d, e, f}) from the rest of the network, yielding a minimum 2-cut of size 3. The manipulator's utility is thus 5. By removing the dotted edges, the minimum 2-cut is obtained by cutting the lower clique ({n, o, p, q, r, s}), yielding a minimum cut of size 2. The manipulator's utility is strictly improved from 5 to 6.

4.2 Max-Egal

We now consider the objective of maximizing the egalitarian social welfare (Max-Egal), i.e., maximizing the utility of the agent that is worst off. Formally, it is min a∈A(u(a, P )). The objective egalitarian social welfare has also been studied in ASHGs [Peters, 2016; Aziz et al., 2013b]. Maximizing the egalitarian SWmight result in a decrease in the average utility of the agents (which is correlated to the utilitarian SW) but it tries to ensure that all of the agents will have some minimum utility. Now, let Eg(P,G) be the egalitarian SW of a coalition structure P in graph G. The following theorems show that Max-Egal is resistant to manipulation by adding edges. The intuition is that by adding edges the manipulator is not able to pretend to be the agent with the minimum utility, and he may increase the utility of the other agents by at most 1.

Theorem 1. Max-Egal is weak-proof against manipulator m+ over undirected networks.

Proof. Let

We will refer to the CS yielding u0 as P0. Assume by contradiction that Max-Egal is subject to weak-improvement. That is, there exists a manipulation rm and a CS P m ∈ O(Gm) such that u(m, P m) > u1. That is, P m /∈ O(G). In addition,

Since the manipulator can only add edges, it holds that Eg(P m,Gm) ≥ Eg(P0,G). Moreover, if Eg(P m,Gm) = Eg(P0,G) then P0 ∈ O(Gm), which is not possible according to inequality 1. Therefore, Eg(P m,Gm) > Eg(P0,G). Since the manipulator is able to add at most one new edge to every agent and G is undirected, then ∀a ∈ A \ {m},

In addition, u(m, P m) > u1 ≥ Eg(P0,G). Overall, ∀a ∈ A, u(a, P m) ≥ Eg(P0,G). That is, Eg(P m,G) ≥ Eg(P0,G), and thus P m ∈ O(G), which is a contradiction.

Theorem 2. Max-Egal is strategyproof against a manipulator m+ over directed networks.

Proof. Let

We will refer to the CS yielding u0 as P0. Note that for every P ∈ O(G) it holds that Eg(P,G) ≤ u0. Assume by contradiction that Max-Egal is subject to UB-improvement. That is, there exists a manipulation rm and a CS P m ∈ O(Gm) such that u(m, P m) > u1. That is, P m /∈ O(G).

Since the manipulator can only add edges, it holds that Eg(P m,Gm) ≥ Eg(P0,G). Moreover, if Eg(P m,Gm) = Eg(P0,G) then P0 ∈ O(Gm), which is not possible. Therefore, Eg(P m, Gm) > Eg(P0, G). Recall that in directed networks the utility of the other agents does not change. Therefore ∀a ∈ A \ {m},

In addition, u(m, P m) > u1 ≥ Eg(P0,G). Overall, ∀a ∈ A, u(a, P m) ≥ Eg(P0,G). That is, Eg(P m,G) ≥ Eg(P0, G), and thus P m ∈ O(G), which is a contradiction.

Now, assume by contradiction that Max-Egal is subject to LB-improvement. That is, there exists a manipulation rm such that

That is P0 /∈ O(Gm). Denote an arbitrary CS in O(Gm) as P m. It holds that Eg(P m,Gm) > Eg(P0,Gm) and Eg(P0, G) ≥ E(P m, G).

Again, in directed networks the utility of the other agents does not change. Therefore, if after the manipulation Eg(P m,Gm) > Eg(P m,G), it can only change by the utility of m. But u(a, P m) > u(a, P), hence even before the manipulation Eg(P m, Gm) > Eg(P m, G), in contradiction.

4.3 At-least-1

In the At-least-1 objective the organizer is only interested in ensuring that every agent will have a utility of at least 1. This objective is very general, and it may result in many possible CSs. It has mostly been studied in the context of graph theory [Stiebitz, 1996; Alon, 2006; Bang-Jensen et al., 2016].

Note that there are some instances where there is no CS that guarantees a utility of at least 1 to every agent. We call such an instance infeasible, and we then write O(G) = ∅. In infeasible instances we assume that the utility of all of the agents is 0. We show that, in contrast to the previous objectives, Atleast-1 is less susceptible to manipulations. Specifically, we show that an UB-improvement is almost always impossible, and LB-improvement is impossible by adding directed edges. The intuition is that adding edges is beneficial only if the network is undirected and the new edges transform an infeasible instance into a feasible instance, and by removing edges the manipulator is not able to introduce new solutions.

Theorem 3. At-least-1 is strategyproof against manipulator m+ over directed networks.

O(G) = ∅ then u1 = 0. Assume by contradiction that the At-least-1 objective is subject to UB-improvement. That is, there exists a manipulation rm and a coalition structure P m ∈ O(Gm) such that u(m, P m) > u1. That is P m /∈ O(G), and ∀a ∈ A, |N m(a)| ≥ 1. Since u1 ≥ 0 then u(m, P m) ≥ 1. In addition, recall that in a directed network, ∀a ∈ A \ {m},N(a) = N m(a), thus ∀a ∈ A \ {m}, u(a, P m) ≥ 1. Overall, ∀a ∈ A, u(a, P m) ≥ 1 and thus P m ∈ O(G), which is a contradiction.

Regarding LB-improvement, since the manipulator is only able to add edges then O(G) ⊆ O(Gm). Therefore, no LBimprovement is possible if O(G) ̸= ∅. If O(G) = ∅, then u1 = 0. Now, assume by contradiction that the At-least-1 objective is subject to LB-improvement. That is, there exists amanipulation rm for which min P∈O(Gm)({u(m, P)}) is at least

1. Since u1 = 0 that would imply an UB-improvement as well, which is impossible (as shown above).

Theorem 4. At-least-1 is UB-proof against manipulator mover directed and undirected networks.

Proof. Since m is only able to remove edges then for every manipulation rm it holds that O(Gm) ⊆ O(G). Therefore, max P∈O(G)({u(m, P)}) ≥ max P∈O(Gm)({u(m, P)}) and no UBimprovement is possible.

5 Limited Information

We now focus on more realistic settings, in which the manipulator is not familiar with the full structure of the network. Instead, we assume that the manipulator is either familiar only with his immediate neighbours in the network, or he may also be familiar with the neighbours of his immediate neighbours. Within this setting we need to revise our definitions of successful manipulations. Specifically, since the manipulator is familiar only with a partial network, we define suitable safe manipulations. Informally, a safe manipulation is a manipulation in which the manipulator is not worse off in all of the possible completions of the partial network, and there exists at least one completion of the partial network in which the manipulator is better off.

Formally, let A0 = {m}. Let G1 = (A,E1) be a graph, E1 ⊆ E, where (u, v) ∈ E1 if either u or v belongs to A0. Similarly, let A1 = {u : (u, v) ∈ E1 ∨ (v, u) ∈ E1}. Let G2 = (A,E2) be a graph, E2 ⊆ E, where (u, v) ∈ E2 if either u or v belongs to A1. Given d ∈ {1, 2}, a possible network Gd of Gd is a network Gd = (A,Ed) where Ed = Ed ∪E′ such that if (u, v) ∈ E′ then neither u and v belong to Ad-1. We assume that the manipulator is familiar with Gd and the objective obj. We denote the settings in which the manipulator is familiar with G1 (G2) by distance 1 (distance 2). Indeed, since the manipulator is always familiar with his immediate neighbours he can still add or remove edges as in the full information setting. However, since the manipulator is only familiar with Gd he needs to consider the effect of his manipulation on every possible network Gd. Given Gd and a manipulation rm, let Gdm be the possible network after the manipulation rm. We can now revise our definitions of successful manipulations. Given a partial network Gd and an objective obj:

Definition 4. A manipulation rm is a d-safe lower bound improvement for a manipulator m if for all possible networks Gd of Gd it holds that

and for at least one possible network Gd, rm is a LBimprovement.

An objective is subject to d-safe LB-improvement by manipulator m over (un)directed networks if there exists a (un)directed partial network Gd and a manipulation rm such that rm is a d-safe LB-improvement for m. Otherwise we say that obj is d-safe LB-proof against m.

The definitions for the other manipulation types are similar. Note that susceptibility to d-safe manipulation implies susceptibility to d'-safe manipulation for any d′ > d, as well as to the full information case. Similarly, resistance to manipulation in the full information setting implies resistance to manipulation in the limited information setting.

5.1 Distance 1

We analyze the three objectives and their susceptibility to safe manipulations in the setting of distance 1. Remarkably, even in this setting there are situations where a safe manipulation exists (Proposition 2). However, Theorem 5 shows that for most situations safe manipulation is impossible. The proof is based on extensive enumeration of networks, where we show that either no manipulation exists or there exists only an unsafe manipulation.

Proposition 2. Max-Egal against manipulator m- over directed networks and At-Least-1 against m+ over undirected networks are subject to 1-safe UB-improvement.

Proof. Figure 4e provides proof for Max-Egal. Clearly, AtLeast-1 is subject to UB-improvement by simply adding any

b

e f

o

r s

U/S

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

(b)

U/S

1

b

d

e

U/LB

2

(d)

U/UB

Egal uŶdireĐted: add UB possiďle Util uŶ/direĐted size: add

E/S

(f)

E/S

1/LB

Figure 2: Figures for the proofs of manipulations by m-. Key:U=Max-Util, E=Max-Egal, 1=At-least-1, S=strict-improvement, UB=UB-

improvement, LB=LB-improvement

12

m

20

10

10

(b)

E/LB

b

e

m

(a)

U/S

b

m

d

h

k

(c)

E/UB

c

f

a

e

i

j

1/S

Figure 3: Figures for the proofs of manipulations by m+. Key:U=Max-Util, E=Max-Egal, 1=At-least-1, S=strictimprovement, UB=UB-improvement, LB=LB-improvement

edge, as it can turn an infeasible instance into a feasible instance.

Theorem 5. All three objectives are 1-safe strategyproof except for the cases in Proposition 2.

Proof (partial). Max-Util. We show that Max-Util is 1-safe strategyproof against manipulators m- and m+ over undirected networks. We start with m-; If 0 < |N(m)| < n - 1, Figures 4a and 4b show that removing any edge is UB-unsafe and LB-unsafe, respectively. Clearly, the graphs in these Figures can be extended to any number of agents and any number of neighbours of the manipulator. For example, to extend figure 4b to arbitrary numbers of agents and neighbours do as following: Connect all of the manipulator's neighbours but one to form a clique (a, b, c in the example). Let the other agents form a clique of their own (e, f, g, h in the example). Lastly connect the manipulator's neighbour which is not in the clique (d in the example) to the other clique with only one edge. This way removing an edge is UB-unsafe.

If |N(m)| = n - 1, we first show that Max-Util is 1-safe UB-proof. If the manipulator removes only 1 edge then he cannot improve his upper bound at all. If the possible network was a complete graph with n nodes, then removing two edges or more is UB-unsafe. To see that Max-Util is 1-safe LBproof, look at a complete graph where one edge is missing

(an edge not connected to m). Removing any edge in that case can only lower the manipulator's LB.

Continuing with m+, if 0 < |N(m)| < n - 1 then Figures 4c,4d show that adding any edge is LB- and UB-unsafe respectively. Again, these examples can be extended to fit any number of agents and any number of neighbours the manipulator has. If |N(m)| = n - 1, the manipulator cannot add edges.

At-Least-1. For At-Least-1, we prove that the objective is 1-safe LB-proof against manipulator m-. Clearly, At-Least-1 is 1-safe LB-proof over undirected networks, since removing any edge might lead to an infeasible instance. For example, if the manipulator removes an edge from a neighbour that has a degree of one, this neighbour will have a degree of zero in every coalition structure, resulting in an infeasible instance.

Over directed networks, there are two possible cases. If there is an agent a such that (a,m), (m, a) ∈ E, then it is possible that the only feasible coalition structure P is where there is a coalition C ∈ P , C = {m, a}. Therefore, removing the edge (m, a) results in an infeasible instance. If there is an agent a such that (m, a) ∈ E but (a,m) /∈ E, then it is possible that there is an agent a′ such that (a, a′ ), (a′ ,m) ∈ E and the only feasible coalition structure p is where there is a coalition C ∈ P, C = {m, a, a′ }. Therefore, removing the edge (m, a) results in an infeasible instance.

b

d

h

j

b

d

e

b

d

g

i

c

d

q

d

m

a

b

c

f

h

eĐted: remove UB possiďle

a

m

d

e

a

m

d

e

b

f

c

g

h

(a) R/U/LB

b

f

c

g

h

(b) R/U/UB

a

c

f

b

d

g

h

(c) A/U/LB

b

f

c

g

h

(d) A/U/UB

Figure 4: Figures for the proofs of safe and unsafe manipulations, distance 1. Key:U=Max-Util, E=Max-Egal, UB=UB-improvement, LB=LB-improvement, R=Remove, A=Add

Due to space constraints, the complete proof, including the setting of Max-Egal, is provided in the full version of this paper [Waxman et al., 2021].

Distance 2

Unlike in the distance 1 setting, the results for the distance 2 setting are almost the same as the results in the full information setting. Indeed, all of the resistance results are derived by the resistance results in the full information setting. Therefore, in this section we provide only susceptibility results summarized in Table 2 where each entry represents a situation, what type of manipulation it is subject to, and a reference to a figure providing a proof. Note that the figures showcase a possible network. The partial network known to the manipulator can easily be derived from them. Overall, we show that, surprisingly, all of the results for the full information setting hold for the distance 2 setting, except for one case: when maximizing the utilitarian SW, with a m- manipulator over undirected networks. In this case, Proposition 1 shows that the objective is subject to strict-improvement with full information while Figures 2c and 2d only show that it is subject to 2-safe LB- and UB-improvement in the distance 2 setting. Indeed, we believe that the objective is 2-safe weakproof.

6 Discussion

In this section we discuss our results. We explain the different phenomena that we observe when comparing the results for the different settings. Our results indicate that manipulations over undirected networks are easier than manipulations over directed networks. This is due to the fact that in directed networks the manipulator can only influence his own utility. In undirected networks the manipulator can actually influence the utility of his neighbours, and this additional power enables the manipulation in additional situations. We can also observe that Max-Util is the easiest objective to manipulate when compared with Max-Egal and At-least-1. Indeed, Max-Util is inherently different from the other two objectives: when maximizing the utilitarian SW, the organizer is interested in the average utility, thus the organizer always takes into account the utility of the manipulator. In contrast, in the other two objectives the organizer is interested in the utility of the weakest agents, thus the organizer may not take

m

e

a

m

d

e

into account the utility of the manipulator (e.g., if the manipulator already has a utility of 5 in the At-least-1 objective). This characteristic of Max-Egal and At-least-1 objectives can also explain why it is easier to manipulate these objectives by removing edges rather than by adding edges: by removing edges the manipulator can pretend to be the weakest agent, affecting the organizer's choice of the coalition structure. Following this observation, we would expect that manipulating the At-least-1 objective will be harder than manipulating the Max-Egal objective: in At-least-1 the organizer is interested only in ensuring a minimum utility of 1 while in Max-Egal the organizer is also interested in maximizing the minimal utility. However, it turns out that At-least-1 can be manipulated by turning an infeasible instance into a feasible instance, thus there are situations in which At-least-1 is subject to strictimprovement while Max-Egal is weak-proof. Finally, we note that there is a significant difference between results for the settings of distance 1 and distance 2. In the setting of distance 1, the manipulator has very limited knowledge of the network. Therefore, it is hard for the manipulator to estimate the full effect of adding or removing edges, thus finding that a safe manipulation is impossible in most of the situations. Surprisingly, even though the manipulator is not familiar with the full structure of the network in the setting of distance 2, the additional information in this setting is sufficient for finding safe manipulations in many situations.

7 Conclusions and FutureWork

We have studied manipulation in the setting of a central organizer that would like to partition a social network into k coalitions. The organizer has a certain objective she would like to satisfy or maximize, whereas there is a manipulator that would like to maximize his utility, i.e., the number of friends within his coalition. We have distinguished between a manipulator who has full information regarding the structure of the social network, and a manipulator that is only familiar with the edges in close proximity to him. An important future research direction to explore is the complexity of finding a manipulation, given a specific objective. We would also like to extend our analysis to the setting with weighted social networks, or social networks with negative edges.

Acknowledgements

This work has been supported in part by the Israel Science Foundation under grant 1958/20, the Ministry of Science, Technology & Space, Israel and the EU project TAILOR under Grant 992215.