Individual Rationality in Topological Distance Games is Surprisingly Hard

Argyrios Deligkas, Eduard Eiben, Dusan Knop, Simon Schierreich

Introduction

Finding a seating arrangement where every participant is satisfied sounds like a simple logistical task. However, in the context of Topological Distance Games (TDGs), this problem becomes a computational nightmare. While previous research in algorithmic game theory has focused on "jump stability"—ensuring no agent wants to move to an empty seat—this paper investigates a more fundamental requirement: Individual Rationality (IR). IR asks whether every participant gains non-negative utility from the arrangement; if not, they would simply choose not to participate.

The Problem: Individual Rationality in TDGs

In a TDG, agents are placed on a floor plan (a topology). An agent's utility is determined by their relationships with others (the enmity graph) and the distance between them. The authors explore the computational complexity of finding an assignment where every agent is rationally satisfied (utility $\ge 0$). They aim to identify the "cut-off" point where this problem shifts from being solvable in polynomial time to being NP-complete or W[1]-hard.

Complexity Landscape

The core of the paper is a rigorous mapping of the complexity landscape for IR in TDGs. The difficulty of the problem is highly sensitive to the structure of the enmity graph and the topology of the space.

Summary of the computational complexity results for Individual Rationality in TDGs.

As shown in the figure above, the authors demonstrate a sharp dichotomy. If the enmity graph is restricted to an "Out-Star" (where only one person has enemies), the problem is solvable in polynomial time. However, if even two people have enemies (an "In-Star" with $\ge 2$ arcs), the problem immediately becomes NP-complete. This hardness persists even under extreme restrictions, such as arranging agents on a simple path topology.

Key Insights and Results

Through mathematical proofs and complexity reductions from problems like Bin Packing and Independent Set, the authors provide several key insights:

  • The Enmity Graph Dominates: The complexity is driven more by the web of "enemies" than the physical layout. The transition from one troublemaker to two is the primary threshold for intractability.
  • Paths Aren't Simple: Seating people in a straight line does not simplify the problem; it remains W[1]-hard even when parameterized by the number of agents.
  • Tractability via Twin-Width: In a rare positive result, the authors use the twin-width parameter to find islands of tractability. If the topology has a simple structure (low twin-width) and the influence of distant agents is capped, the problem becomes Fixed-Parameter Tractable (FPT).
  • The Role of Distance: Hardness often stems from the "distance factor function," which allows enemies to negatively impact an agent's utility even from a distance.

Conclusion and Future Work

The findings are largely negative, showing that ensuring IR is significantly harder than achieving stability notions previously studied. Future research may explore the intersection of jump stability and IR, or investigate whether specific real-world social network structures provide natural parameters that make IR easier to achieve in practice. For now, the question of whether an individually rational solution even exists for most natural instances remains an open challenge.

Summary updated

BibTeX
@inproceedings{deligkas2024individual,
  author = {Argyrios Deligkas and Eduard Eiben and Dusan Knop and Simon Schierreich},
  title = {{Individual Rationality in Topological Distance Games is Surprisingly Hard}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure