Manipulation of k-Coalitional Games on Social Networks

Naftali Waxman, Sarit Kraus, Noam Hazon

Abstract

This study explores the susceptibility of coalition formation games to strategic manipulation by individual agents. In scenarios where a central organizer partitions agents into $k$ teams based on a social network of friendships, agents may misreport their connections to secure a more favorable placement. We evaluate three organizational objectives: Utilitarian (Max-Util), Egalitarian (Max-Egal), and the "At-least-1" friendship guarantee. Our analysis categorizes manipulation potential based on agent capabilities (adding vs. removing edges), available network information (Distance 1, Distance 2, or Full Information), and graph directionality. We demonstrate that while "hiding" friends is a highly effective tactic, restricting agents to local network knowledge (Distance 1) significantly deters successful manipulation by making outcomes unpredictable and "unsafe."

Introduction

Coalition formation is a fundamental problem in multi-agent systems, often seen in practical settings like assigning students to project teams or employees to departments. A common goal is to maximize "happiness" based on existing social ties. However, when the partitioning algorithm is known, agents become strategic. A student might pretend not to be friends with someone to be moved to a group they prefer, or claim a false friendship to influence the organizer's decision. This paper formally investigates when and how such manipulations succeed.

Methodology and Problem Formulation

The researchers model the social network as a graph $G = (V, E)$, where $V$ represents agents and $E$ represents friendships. The utility of an agent is defined by the number of their friends in their assigned coalition—a classic Hedonic Game structure.

The study focuses on three objectives:

  1. Max-Util: Maximizing the sum of all agents' utilities.
  2. Max-Egal: Maximizing the utility of the agent with the fewest friends in their group.
  3. At-least-1: Ensuring every agent has at least one friend in their coalition.

To analyze manipulation, the authors introduce the concept of "safe" manipulation. A manipulation is considered safe if the agent is guaranteed not to be worse off, regardless of the unknown parts of the network, while retaining a possibility of improvement.

Figure 1: Visualization of utility bounds defining safe manipulation. An agent's report is 'safe' if the resulting utility range does not fall below the truthful baseline.

The authors use synthetic graph constructions, such as cliques and paths, to prove the existence of manipulation vulnerabilities across different scenarios.

Figure 4: Examples of graph structures (a-g) used to prove susceptibility or strategyproofness under various information and capability constraints.

Key Insights

The Power of Hiding

A primary finding is that removing real edges (hiding friends) is significantly more effective than adding fake ones. By appearing "lonelier," an agent can leverage Egalitarian or At-least-1 objectives to force the organizer to place them in a more utility-rich coalition.

Information as a Defense Mechanism

The most critical deterrent to manipulation is the lack of information.

  • Distance 1 Information: If an agent only knows their own immediate friends, they cannot accurately predict how a lie will affect the global partition. This uncertainty makes most manipulations "unsafe," as a lie could inadvertently lead to a worse outcome.
  • The Distance 2 Threshold: Knowing "friends of friends" provides a massive strategic advantage. In many cases, Distance 2 information is sufficient to manipulate the system as effectively as having full knowledge of the entire network.

Results and Fragility

The Max-Util objective proved to be the most fragile, remaining susceptible to manipulation in nearly every scenario where agents possessed at least Distance 2 information. In contrast, Max-Egal and At-least-1 showed greater resilience, particularly in directed networks where adding fake edges is strictly non-beneficial.

Crucially, the authors proved that all three objectives are generally 1-safe strategyproof. This implies that simply keeping the global social graph private (limiting agents to Distance 1 views) is a highly effective practical defense against strategic misreporting.

Conclusion

This work highlights the delicate balance between organizational efficiency and strategic stability. While sophisticated objectives like Max-Util are prone to gaming, the inherent uncertainty of local information acts as a natural stabilizer. Future research may extend these findings to coalitional manipulation (groups of agents lying together) and explore the computational complexity of finding optimal lies in weighted or signed networks.

Summary updated

Abstract

In many coalition formation games the utility of the agents depends on a social network. In such scenarios there might be a manipulative agent that would like to manipulate his connections in the social network in order to increase his utility. We study a model of coalition formation in which a central organizer, who needs to form k coalitions, obtains information about the social network from the agents. The central organizer has her own objective: she might want to maximize the utilitarian social welfare, maximize the egalitarian social welfare, or only guarantee that every agent will have at least one connection within her coalition. In this paper we study the susceptibility for manipulation of these objectives, given the abilities and information that the manipulator has. Specifically, we show that if the manipulator has very limited information, namely he is only familiar with his immediate neighbours in the network, then a manipulation is almost always impossible. Moreover, if the manipulator is only able to add connections to the social network, then a manipulation is still impossible for some objectives, even if the manipulator has full information on the structure of the network. On the other hand, if the manipulator is able to hide some of his connections, then all objectives are susceptible to manipulation, even if the manipulator has limited information, i.e., when he is familiar with his immediate neighbours and with their neighbours.
BibTeX
@inproceedings{waxman2021manipulation,
  author = {Naftali Waxman and Sarit Kraus and Noam Hazon},
  title = {{Manipulation of k-Coalitional Games on Social Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/63},
}
Figure