Multi-player Diffusion Games on Graph Classes

Laurent Bulteau, Vincent Froese, Nimrod Talmon

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 [7] for two players, we investigate the existence of pure Nash equilibria for at least three players on different classes of graphs including paths, cycles, and grid graphs. As a main result, we answer an open question proving that there is no Nash equilibrium for three players on $$m\times n$$ grids with $$\min \{m,n\}\ge 5$$ .
BibTeX
@inproceedings{bulteau2016multi,
  author = {Laurent Bulteau and Vincent Froese and Nimrod Talmon},
  title = {{Multi-player Diffusion Games on Graph Classes}},
  booktitle = {Internet Math},
  year = {2016},
  url = {https://openreview.net/forum?id=fhI1BH74wI},
}

Loading related content...

Figure