Two Influence Maximization Games on Graphs Made Temporal

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

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 2-player competitive diffusion and Voronoi games on different temporal graph classes. Even when restricting our studies to temporal trees 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 trees and cycles. Our two main technical results are (algorithmic) proofs for the existence of Nash equilibria in 2-player competitive diffusion and temporal Voronoi games when the edges are restricted not to disappear over time.

Introduction

Most research on graph games—where players compete to "color" or influence as many nodes as possible—assumes the network is static. However, real-world networks, such as social media or transport systems, are inherently dynamic; connections are made and broken constantly. This paper addresses the challenge of influence maximization in these dynamic environments by generalizing two classic game types to temporal graphs:

  1. Competitive Diffusion Games: Influence spreads step-by-step through neighbors (e.g., viral marketing).
  2. Voronoi Games: Vertices are claimed based on which player is "closest" in terms of travel time (e.g., facility location).

The central question is whether a Nash equilibrium (NE)—a state where no player can improve their score by changing their starting position—always exists in these temporal versions. While the answer is "yes" for static trees and cycles, the temporal setting introduces significant complexity and breaks the traditional equivalence between these two game types.

Comparison of temporal diffusion and Voronoi games on the same temporal graph.

Methodology

The authors define a temporal graph as a fixed set of vertices with an edge set that evolves over discrete time steps. They utilize the concept of a foremost walk—the path that reaches a destination at the earliest possible time—to define temporal distance. To prove the existence of Nash equilibria, several novel structural concepts are introduced:

  • Nice Vertices: Centroids of reachable vertices that maximize the set size in diffusion games.
  • Paramount Vertices: Vertices that are lexicographically "better" over time than other starting positions in Voronoi games.
  • Boundary Components: A method to partition the graph based on where a player can "catch up" to an opponent.

The study is primarily theoretical, relying on mathematical proofs and worst-case complexity analysis across abstract graph classes like temporal paths, trees, and cycles. The proofs are constructive, leading to algorithms that find equilibria in linear or quadratic time relative to the number of vertices ($n$) and the graph's lifetime ($\tau$).

Key Insights and Results

A major finding is the breaking of equivalence. On static trees and cycles, Diffusion and Voronoi games are mathematically equivalent. However, temporal dynamics break this equivalence; a strategy optimal for one game may fail in the other once edges appear or disappear.

The study highlights that monotonicity acts as a "safety" feature. Nash equilibria are much more likely to exist in monotonically growing temporal graphs (where edges only appear). Conversely, disappearing edges introduce instability; even a simple path may lack a NE if an edge disappears, as players risk being "cut off" while trying to claim sections of the graph.

Summary of Nash Equilibrium existence in temporal diffusion and Voronoi games across various graph classes.

Quantitative Highlights: * Diffusion on Growing Cycles: A Nash equilibrium can be found in $O(\tau \cdot n)$ time. * Voronoi on Growing Cycles: A Nash equilibrium can be found in $O(n^2)$ time. * Temporally Connected Trees: For diffusion games, an equilibrium can be found in linear time $O(n)$.

Discussion and Future Work

While this work provides a foundational map for 2-player temporal graph games, several limitations remain. The results are strictly for 2-player scenarios; dynamics for 3 or more players are likely more chaotic and may not guarantee equilibria. Additionally, the study focuses on paths, trees, and cycles, leaving more complex structures like temporal grids for future exploration. The authors also suggest that "non-strict" temporal walks (allowing multiple edges per time step) could be a fruitful area for future study, though they conjecture their results for growing trees would remain robust.

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 2-player competitive diffusion and Voronoi games on different temporal graph classes. Even when restricting our studies to temporal trees 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 trees and cycles. Our two main technical results are (algorithmic) proofs for the existence of Nash equilibria in 2-player 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},
}

Loading related content...

Figure