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:
- Max-Util: Maximizing the sum of all agents' utilities.
- Max-Egal: Maximizing the utility of the agent with the fewest friends in their group.
- 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.
The authors use synthetic graph constructions, such as cliques and paths, to prove the existence of manipulation vulnerabilities across different scenarios.
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