Abstract
We study competitive diffusion games on graphs introduced by Alon et al. [Citation1] to model the spread of influence in social networks. Extending results of Roshanbin [Citation8] for two players, we investigate the existence of pure Nash equilibriafor at least three players on different classes of graphs including paths, cycles, grid graphs and hypercubes; as a main contribution, we answer an open question proving that there is no Nash equilibriumfor three players on m × n grids with min {m, n} ≥ 5. Further, extending results of Etesami and Basar [Citation3] for two players, we prove the existence of pure Nash equilibriafor four players on every d-dimensional hypercube.
Acknowledgments
We thank Manuela Hopp for helpful discussions and implementations for the result on hypercubes. Laurent Bulteau was supported by the Alexander von Humboldt Foundation, Bonn, Germany. Vincent Froese was supported by the DFG, project DAMM (NI 369/13). Nimrod Talmon was supported by DFG Research Training Group “Methods for Discrete Structures” (GRK 1408).
Funding
Laurent Bulteau was supported by the Alexander von Humboldt Foundation, Bonn, Germany. Main work done while affiliated with TU Berlin. Vincent Froese was supported by the DFG, project DAMM (NI 369/13). Nimrod Talmon was supported by DFG Research Training Group Methods for Discrete Structures (GRK 1408). Main work done while affiliated with TU Berlin.