Abstract: We study competitive diffusion games on graphs introduced by Alon et al. [1] to model the spread of influence in social networks. Extending results of Roshanbin [8] for two players, we investigate the existence of pure Nash equilibria for at least three players on different classes of graphs including paths, cycles, grid graphs and hypercubes; as a main contribution, we answer an open question proving that there is no Nash equilibrium for three players on (m x n) grids with min(m, n) >= 5. Further, extending results of Etesami and Basar [3] for two players, we prove the existence of pure Nash equilibria for four players on every d-dimensional hypercube.
Introduction
Competitive diffusion games serve as a mathematical framework for modeling how competing influences—such as viral marketing campaigns or political ideologies—spread through a social network. In these games, players simultaneously select a starting node (an "influencer"). Influence then propagates to neighboring nodes in discrete time steps. A critical mechanic is "disenchantment": if a node is reached by multiple competing influences at the exact same time, it becomes neutral and is removed from the game.
The central question is the existence of a pure Nash equilibrium (PNE): a configuration of starting nodes where no single player can increase the number of nodes they influence by unilaterally changing their position. While two-player dynamics are well-understood, this research explores the significantly more complex interactions that arise with three or more players across various graph topologies.
Paths and Cycles: The Power of Pairing
On linear structures like paths ($P_n$) and cycles ($C_n$), the authors demonstrate that stability is often achieved through a "pairing" strategy. By positioning themselves in pairs, players can effectively block each other's expansion, creating a balanced partition of the graph's nodes.
The study provides a complete characterization for these classes: a PNE exists for any number of players $k$ on any cycle. On paths, a PNE also exists for any $k$, with one notable exception: the case of exactly three players on a path of length $n \ge 6$. In this scenario, the system is inherently unstable; a player will always find it advantageous to "jump" over an opponent or shift their position to capture more territory, preventing the game from reaching a resting state.
The 3-Player Grid Problem
A primary contribution of this paper is the resolution of a long-standing open question regarding grid graphs ($G_{m \times n}$). The authors prove that for any grid where both dimensions are at least 5, no PNE exists for three players.
The proof utilizes a exhaustive case-by-case analysis of relative player positions. The authors show that whether players are clustered together or spread far apart, the 2D geometry of the grid always offers a "better" move for at least one player. If players are distant, one can move closer to an opponent to "steal" their peripheral nodes. If they are close, the disenchantment rules and the grid's connectivity allow a player to reposition and gain a larger share of the total nodes. This inherent instability suggests that three-way competition on a 2D lattice is fundamentally chaotic.
Stability in High Dimensions: Hypercubes
In contrast to the instability found on grids, the high dimensionality and symmetry of hypercubes ($H_d$) allow for stable multi-player configurations. Extending previous work on 2-player hypercube games, the authors prove that a PNE always exists for four players on any $d$-dimensional hypercube.
This stability is achieved by leveraging the graph's symmetry: by choosing two adjacent nodes and their exact bit-complements (the nodes at the maximum Hamming distance), the four players create a perfectly balanced four-way split of the hypercube. This result highlights how the topology of a network—not just the number of players—dictates the possibility of a stable competitive outcome.
Conclusion and Future Work
This research significantly advances the theory of competitive diffusion by mapping the boundaries of stability in multi-player games. While the 3-player grid problem is now settled, several questions remain, including the existence of equilibria for exactly three players on hypercubes and the formal proof for 4-player instability on larger grids. These findings suggest that the stability of influence in social networks is a delicate balance between the number of competitors and the underlying connectivity of the population.
Summary updated