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.
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