Two Influence Maximization Games on Graphs Made Temporal

Niclas Boehmer, Vincent Froese, Julia Henkel, Yvonne Lasars, Rolf Niedermeier, Malte Renken

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):

  1. Competitive Diffusion: Influence spreads step-by-step through neighbors, similar to a virus or rumor.
  2. 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.

Figure 1: Comparison of Diffusion and Voronoi dynamics on a temporal path. In the diffusion game (a), player 2 (red) is blocked by player 1 (blue). In the Voronoi game (b), player 2 is able to claim nodes on the right as new edges appear in later layers.

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.

Table 1: Summary of Nash Equilibrium (NE) existence results. Checkmarks indicate a guaranteed NE, while 'X' marks indicate that an NE is not guaranteed.

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

Abstract

To address the dynamic nature of real-world networks, we generalize competitive diffusion games and Voronoi games from static to temporal graphs, where edges may appear or disappear over time. This establishes a new direction of studies in the area of graph games, motivated by applications such as influence spreading. As a first step, we investigate the existence of Nash equilibria in competitive diffusion and Voronoi games on different temporal graph classes. Even when restricting our studies to temporal paths and cycles, this turns out to be a challenging undertaking, revealing significant differences between the two games in the temporal setting. Notably, both games are equivalent on static paths and cycles. Our two main technical results are (algorithmic) proofs for the existence of Nash equilibria in temporal competitive diffusion and temporal Voronoi games when the edges are restricted not to disappear over time.
BibTeX
@inproceedings{boehmer2021two,
  author = {Niclas Boehmer and Vincent Froese and Julia Henkel and Yvonne Lasars and Rolf Niedermeier and Malte Renken},
  title = {{Two Influence Maximization Games on Graphs Made Temporal}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/7},
}
Figure