Presented at IJCAI-21, this research explores how the dynamics of time-varying networks fundamentally alter the strategic landscape of influence maximization. By transitioning from static to temporal graphs, the authors demonstrate that long-held assumptions about game-theoretic stability—specifically Nash equilibria—often collapse when network edges are allowed to appear or disappear over time.
The Shift to Temporal Reality
In real-world scenarios, networks are rarely static. Social connections evolve, and transportation routes open or close. However, traditional research into "influence maximization games"—where players compete to "color" or claim as many nodes as possible—typically assumes a fixed graph structure. This paper addresses the gap by generalizing two classic games to temporal graphs (sequences of graph layers over discrete time steps):
- Competitive Diffusion: Influence spreads step-by-step through neighbors, similar to a virus or rumor.
- Voronoi Games: Nodes are claimed by the player who is "closest" in terms of travel time.
The Equivalence Break
On static paths and cycles, Diffusion and Voronoi games are mathematically identical. A key insight of this work is that this equivalence breaks down in temporal settings. In Diffusion games, a player can effectively "block" an opponent's spread. In contrast, in Voronoi games, a player can "catch up" to an opponent if a faster path opens up at a later time step, even if they were initially blocked.
Impact of Edge Dynamics on Stability
The researchers categorized temporal graphs based on how their edge sets change:
- Monotonically Growing: Edges can appear but never disappear.
- Monotonically Shrinking: Edges can disappear but never appear.
They found that "Monotonically Shrinking" graphs are particularly unstable. In these environments, a Nash equilibrium (NE) often fails to exist because players are constantly incentivized to shift their starting positions to avoid being cut off from the network as edges vanish. Conversely, when edges only appear (Monotonically Growing), the games are much more likely to reach a stable state.
Key Results and Theoretical Map
The paper provides a comprehensive map of where Nash equilibria are guaranteed to exist across different graph topologies and temporal behaviors. Notably, while stability is often found in growing graphs, the authors provide a specific construction of a temporal path with only two layers where no Nash equilibrium exists for the diffusion game, highlighting the inherent volatility of temporal competition.
Limitations and Future Outlook
While this work establishes a foundation for temporal influence games, it focuses primarily on two-player scenarios and simple topologies like paths and cycles. Real-world social networks are far more complex, and the dynamics for $k$ players are likely to be even more volatile. Future research may explore alternative distance metrics, such as "fastest walks" (shortest duration) rather than the "foremost walks" (earliest arrival) used here, which could lead to entirely different strategic behaviors.
Summary updated