Abstract
Coordination games on directed graphs present significant computational challenges, as Nash equilibria may not exist and finding them is generally NP-complete. This work identifies specific directed graph structures—including chains of cycles and "partition-cycles"—where local search algorithms are guaranteed to reach a Nash equilibrium in polynomial time. By analyzing improvement paths and structural properties like weak acyclicity, the authors provide a roadmap for efficient equilibrium discovery in complex directed networks.
Introduction
In game theory, a coordination game occurs when players derive higher utility from aligning their choices with their neighbors, such as adopting a common technology, social platform, or fashion choice. When these interactions are modeled on networks, they are represented as games on graphs. While these games are well-behaved on undirected graphs—where a pure Nash equilibrium always exists and any sequence of "better" moves eventually leads to one—directed graphs introduce significant instability.
In directed networks, influence is often unidirectional (e.g., one user follows another's choices without reciprocity). In such settings, the mathematical guarantees of undirected graphs break down: Nash equilibria may not exist at all, and the problem of finding one is known to be NP-complete. This research addresses this gap by identifying "islands of tractability"—specific directed graph topologies where stable outcomes can still be guaranteed and reached efficiently using simple local search algorithms.
Methodology
The study employs a combination of graph theory and algorithmic game theory to analyze "improvement paths." An improvement path is a sequence of states where, at each step, one player (or a coalition) switches to a strategy that increases their individual or collective payoff. The model specifically considers weighted directed graphs where a player's payoff is the sum of weights from neighbors who chose the same "color" (strategy), plus an optional fixed bonus.
The authors' approach is constructive: rather than merely proving an equilibrium exists, they identify specific "schedulers"—ordered sequences of player moves—that are guaranteed to terminate in an equilibrium. They define and analyze several novel graph classes, such as "chains of cycles" and "partition-cycles," and investigate how structural features like edge weights and node bonuses impact the game's convergence.
Theoretical Insights
A central finding of the paper is that many complex directed structures exhibit "weak acyclicity." While some sequences of moves might cycle indefinitely, a game is weakly acyclic if there is at least one path from any starting point to an equilibrium. The authors prove that several complex directed structures possess this property.
The research also highlights the "Two-Bonus" limit, a fascinating insight into the minimality of instability. For a simple cycle, the presence of bonuses at three or more nodes can prevent an equilibrium from existing. However, if only two nodes have bonuses, the game is guaranteed to converge in $O(n)$ steps. Furthermore, the authors demonstrate a "propagation technique" where best-response moves travel through cycles or chains like a wave, eventually stabilizing the entire system. They also distinguish between individual moves and "c-improvement" (coalition) moves, showing that in many cases, allowing groups to move together can lead to "Strong Equilibria" that are resistant to group deviations.
Key Results
The paper establishes a hierarchy of graph classes and provides upper bounds for the time required to reach an equilibrium, where $n$ is the number of nodes and $m$ is the number of cycles. These results demonstrate that for structures like weighted DAGs and simple cycles with limited bonuses, convergence is linear. For more complex structures like chains of cycles, the convergence remains polynomial.
Crucially, the authors prove these results are near-optimal. Slight generalizations of these structures—such as adding a third bonus to a cycle or moving from open to closed weighted chains—can result in games where a Nash equilibrium may not exist at all, as demonstrated by specific counter-examples in the text.
Limitations and Future Work
Despite these advances, several open questions remain. The authors propose the "In-Degree Conjecture," which suggests that coordination games on unweighted graphs where every node has an in-degree of at most two are always "c-weakly acyclic." This remains unproven. Additionally, while the existence of polynomial-time schedulers is established for these classes, the efficiency of random move sequences (a "fair" random scheduler) is not yet known. Future research will also investigate the existence of finite coalition-improvement paths in weighted open chains and certain partition-cycles.
Summary updated