Individual Rationality in Topological Distance Games Is Surprisingly Hard

Argyrios Deligkas, Eduard Eiben, Dušan Knop, Šimon Schierreich

Abstract

In social choice and game theory, "Individual Rationality" (IR) is the baseline requirement for stability: every participant must derive at least zero utility to remain in the system. This paper investigates the computational complexity of finding IR assignments in Topological Distance Games, where agents' happiness is determined by their proximity to friends and enemies on a graph. We prove that finding such an assignment is NP-complete even in highly restricted settings, such as when the seating chart is a simple line or when enmity is extremely limited. Our work maps the boundary between rare polynomial-time cases and pervasive intractability.

Introduction

Imagine organizing a seating chart where some guests are "enemies" who provide negative utility. A guest's total happiness depends on their inherent feelings toward others, scaled by the distance between them in the seating topology. The fundamental question is: Does an assignment exist where everyone is willing to participate? This paper moves beyond traditional notions of stability to address the core existence of IR solutions.

Classical Complexity: The "Two-Enemy" Threshold

The authors identify a sharp dichotomy in the complexity of finding IR assignments based on the structure of the "Enmity Graph" (who hates whom).

As shown in the landscape below, the problem is solvable in polynomial time only if at most one agent has enemies (an "Out-Star" configuration). However, as soon as two people have enemies or the enmity structure becomes slightly more complex (e.g., an "In-Star" with two arcs), the problem immediately becomes NP-complete.

Complexity landscape for Individual Rationality based on enmity graph structures.

Even seating people in a simple line (path topology) does not alleviate the hardness. The paper demonstrates that with just three specific enmity relationships, the problem remains NP-complete on a path, defying the intuition that simple topologies lead to simple solutions.

Parameterized Complexity: The W[1]-Hard Wall

When considering the number of agents as a parameter, the news remains largely negative. For most configurations, the problem is W[1]-hard, suggesting that the computation time grows exponentially with the number of agents, making it practically unsolvable for large groups even if other parameters are fixed.

Parameterized complexity results for various game configurations.

The authors found one notable "oasis" of tractability: the problem is Fixed-Parameter Tractable (FPT) if the seating topology is a path and all enmity is directed toward a single "troublemaker" agent (Theorem 10). Outside of this specific case, finding an IR solution generally requires exhaustive search.

Conclusion

This research highlights that ensuring basic satisfaction in distance-based games is computationally "hard" in almost every realistic scenario. These findings suggest that future work should focus on approximate individual rationality or more restricted utility functions to find practical seating solutions in complex social environments.

Summary updated

BibTeX
@inproceedings{deligkas2024individual,
  author = {Argyrios Deligkas and Eduard Eiben and Dušan Knop and Šimon Schierreich},
  title = {{Individual Rationality in Topological Distance Games Is Surprisingly Hard}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure