Manipulation of k-Coalitional Games on Social Networks

Naftali Waxman, Noam Hazon, Sarit Kraus

Abstract

In coalition formation games, agent utility often depends on social network structures. This study examines how manipulative agents might misreport their connections to influence a central organizer's division of $k$ coalitions. We analyze objectives such as maximizing utilitarian social welfare, egalitarian social welfare, and ensuring minimal connectivity. Our findings reveal that while full network knowledge facilitates manipulation, limited "Distance 1" information (knowing only immediate neighbors) makes successful deception nearly impossible. Furthermore, hiding existing connections is a more potent strategy than fabricating new ones.

The Coalition Formation Problem

A central organizer often faces the task of partitioning a set of agents into $k$ disjoint teams. In Additively Separable Hedonic Games (ASHGs), an agent's happiness is the sum of their connections within their assigned group. Organizers typically aim for one of three goals:

  1. Max-Util: Maximizing the total happiness across all agents (utilitarian welfare).
  2. Max-Egal: Maximizing the utility of the least-satisfied agent (egalitarian welfare).
  3. At-least-1: Guaranteeing that every agent has at least one friend in their group.

Modeling Strategic Behavior

Agents may act strategically by reporting a modified version of their local network. This manipulation can take two forms: adding edges (faking friendships) or removing edges (hiding real ones). The success of a manipulation is measured by the resulting utility improvement for the agent relative to a truthful report.

Classification of utility improvements for a manipulator relative to a truthful report.

As illustrated in Figure 1, improvements are categorized based on whether they affect the lower bound (LB) or upper bound (UB) of an agent's potential utility. A "Strict-Improvement" occurs when the agent is guaranteed a better outcome regardless of the organizer's tie-breaking rules.

The Impact of Information and Edge Manipulation

The susceptibility of a system depends heavily on the manipulator's knowledge of the global network structure:

  • Full Information: Complete knowledge of the entire social graph.
  • Distance 2: Knowledge of immediate neighbors and their respective neighbors.
  • Distance 1: Knowledge restricted to immediate neighbors only.

The researchers utilized various synthetic graph structures to prove the existence or impossibility of manipulation under these constraints.

Synthetic graph scenarios used to prove susceptibility or strategyproofness across different objectives.

A key insight from these models is that hiding connections is more powerful than faking them. By removing edges, a manipulator can appear isolated, prompting a fairness-oriented organizer (like one using Max-Egal) to move them to a group where they actually have hidden friends. Conversely, adding fake edges is often ineffective, especially in directed networks.

Key Results

  • The Information Threshold: There is a sharp divide at Distance 1. At this level, "safe" manipulation is almost always impossible because the agent cannot predict how their lie will ripple through the organizer's global calculations. However, at Distance 2, agents can manipulate almost as effectively as with full information.
  • Objective Vulnerability: Max-Util is the most vulnerable objective, often susceptible to strict improvement via edge removal. Max-Egal and At-least-1 are more robust, particularly against agents who only add fake edges.
  • Network Type: Manipulation is generally easier in undirected networks, where a reported edge affects the utility of both connected agents, providing the manipulator with more leverage to influence the global outcome.

Conclusion and Future Directions

While theoretical susceptibility exists, the "Distance 1" results suggest that real-world coalition mechanisms are naturally resilient due to information asymmetry. Future work should address the computational complexity of finding these manipulations, as identifying the optimal "lie" may be NP-hard. Additionally, exploring weighted networks and the inclusion of "negative edges" (enemies) would bring the model closer to the complexities of human social dynamics.

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 simply guarantee that every agent will have at least one connection within her coalition. In this paper we study the susceptibility to 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 Noam Hazon and Sarit Kraus},
  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