Two Influence Maximization Games on Graphs Made Temporal

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

doi:10.24963/ijcai.2021/7

Two Influence Maximization Games on Graphs Made Temporal

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

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 45-51.

https://doi.org/10.24963/ijcai.2021/7

Keywords

Agent-based and Multi-agent Systems: Noncooperative Games
Agent-based and Multi-agent Systems: Algorithmic Game Theory

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.

Niclas Boehmer, Vincent Froese, Julia Henkel, Yvonne Lasars, Rolf Niedermeier, and Malte Renken. 2021. Two Influence Maximization Games on Graphs Made Temporal. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 45–51. https://doi.org/10.24963/ijcai.2021/7

@inproceedings{ijcai2021p7,
  title     = {Two Influence Maximization Games on Graphs Made Temporal},
  author    = {Boehmer, Niclas and Froese, Vincent and Henkel, Julia and Lasars, Yvonne and Niedermeier, Rolf and Renken, Malte},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {45--51},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/7},
  url       = {https://doi.org/10.24963/ijcai.2021/7},
}

TY  - CPAPER
TI  - Two Influence Maximization Games on Graphs Made Temporal
AU  - Boehmer, Niclas
AU  - Froese, Vincent
AU  - Henkel, Julia
AU  - Lasars, Yvonne
AU  - Niedermeier, Rolf
AU  - Renken, Malte
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 45
EP  - 51
DO  - 10.24963/ijcai.2021/7
UR  - https://doi.org/10.24963/ijcai.2021/7
ER  -