Introduction
In many social and organizational settings—such as choosing a seat at a banquet, an office in a building, or a desk in a classroom—an individual's utility depends on two primary factors: the identity of those nearby and their physical proximity. Existing game-theoretic models often fail to capture this intersection. Hedonic games focus on group membership but ignore internal positioning; social distance games examine network distances while ignoring physical layout; and Schelling games typically consider only binary "types" of agents.
This paper introduces Topological Distance Games (TDGs), a framework designed to bridge these gaps by placing agents on a physical topology graph and modeling their utility based on weighted relationships and distances.
The TDG Framework
In a TDG, agents are placed on a topology graph representing the physical layout. An agent’s utility is calculated as the sum of their feelings toward every other agent, scaled by a "distance factor"—typically the reciprocal of the distance between them in the graph. The primary objective is to identify "jump stable" assignments, where no agent can increase their utility by moving to an empty node.
The authors utilize a combination of discrete mathematics, algorithm design, and computational complexity analysis to explore these games. Key tools include potential functions for proving existence in symmetric cases and reductions from problems like MAX CUT to establish hardness.
Key Insights and Stability
Symmetry and Potential Games
The research highlights that symmetry is a stabilizer. When relationships are symmetric (i.e., agent A feels the same about agent B as B feels about A), a stable state is guaranteed to exist. In these scenarios, the game functions as a "potential game," where every beneficial move by an individual increases a global potential score. However, finding this stable state is PLS-complete, suggesting that large systems may take an impractically long time to reach equilibrium naturally.
The Role of Friendship Structures
The structure of the "friendship graph"—the network of who likes whom—is a critical determinant of stability. If this network is acyclic (forming a hierarchy without circular friendships), a jump stable assignment is guaranteed to exist and can be found in polynomial time, even if the physical topology is complex.
Conversely, in asymmetric scenarios, stability is not guaranteed. Even with only two agents, a stable state might not exist (Proposition 4.1). Furthermore, the geometry of the topology graph itself dictates stability; while paths often guarantee stability for agents with few friends, structures like trees or cycles can cause stability to vanish even with simple friendship networks.
Computational Complexity and Dynamics
The paper establishes several key results regarding the complexity of TDGs:
- General Complexity: Deciding if a stable state exists for a general TDG is NP-complete (Theorem 4.7).
- Convergence: In acyclic friendship graphs with non-negative utilities, agents jumping to better spots will eventually converge to a stable state, though the process may require an exponential number of jumps (Theorems 5.1, 5.2).
Conclusion and Future Directions
While this work provides a robust foundation for understanding how social relationships and physical distance interact, it focuses primarily on jump stability. Future research could expand into other stability notions, such as swap stability (where agents trade places) or envy-freeness. Additionally, extending the model to weighted topology graphs or dynamic layouts where the physical environment changes remains an open and promising challenge.
Summary updated