Information Processing Letters 112 (2012), 59-60.
A comment on pure-strategy Nash equilibria in competitive diffusion games
by Reiko Takehara, Masahiro Hachimori, Maiko Shigeno
Abstract
In [N. Alon, M. Feldman, A.D. Procaccia, M. Tennenholtz, A note on competitive diffusion
through social networks, Inform. Process. Lett. 110 (2010) 221-225], the authors introduced
a game-theoretic model of diffusion process through a network. They showed a relation between
the diameter of a given network and existence of pure Nash equilibria in the game. Theorem 1
of their paper says that a pure Nash equilibrium exists if the diameter is at most two.
However, we have an example which does not admit a pure Nash equilibrium even if the diameter is two.
Hence we correct the statement of Theorem 1 of their paper.