TY - GEN

T1 - Two-Player Competitive Diffusion Game

T2 - 46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020

AU - Fukuzono, Naoka

AU - Hanaka, Tesshu

AU - Kiya, Hironori

AU - Ono, Hirotaka

AU - Yamaguchi, Ryogo

N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

PY - 2020

Y1 - 2020

N2 - The competitive diffusion game is a game-theoretic model of information spreading on a graph proposed by Alon et al. (2010). In the model, a player chooses an initial vertex of the graph, from which information by the player spreads through the edges connected with the initial vertex. If a vertex that is not yet influenced by any information receives information by a player, it is influenced by the information and it diffuses it to adjacent vertices. A vertex that simultaneously receives two or more types of information does not diffuse any type of information from then on. The objective of a player is to maximize the number of vertices influenced by the player’s information. In this paper, we investigate the existence of a pure Nash equilibrium of the two-player competitive diffusion game on chordal and its related graphs. We show that a pure Nash equilibrium always exists on block graphs, split graphs and interval graphs, all of which are well-known subclasses of chordal graphs. On the other hand, we show that there is an instance with no pure Nash equilibrium on (strongly) chordal graphs; the boundary of the existence of a pure Nash equilibrium is found.

AB - The competitive diffusion game is a game-theoretic model of information spreading on a graph proposed by Alon et al. (2010). In the model, a player chooses an initial vertex of the graph, from which information by the player spreads through the edges connected with the initial vertex. If a vertex that is not yet influenced by any information receives information by a player, it is influenced by the information and it diffuses it to adjacent vertices. A vertex that simultaneously receives two or more types of information does not diffuse any type of information from then on. The objective of a player is to maximize the number of vertices influenced by the player’s information. In this paper, we investigate the existence of a pure Nash equilibrium of the two-player competitive diffusion game on chordal and its related graphs. We show that a pure Nash equilibrium always exists on block graphs, split graphs and interval graphs, all of which are well-known subclasses of chordal graphs. On the other hand, we show that there is an instance with no pure Nash equilibrium on (strongly) chordal graphs; the boundary of the existence of a pure Nash equilibrium is found.

UR - http://www.scopus.com/inward/record.url?scp=85079084710&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85079084710&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-38919-2_52

DO - 10.1007/978-3-030-38919-2_52

M3 - Conference contribution

AN - SCOPUS:85079084710

SN - 9783030389185

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 627

EP - 635

BT - SOFSEM 2020

A2 - Chatzigeorgiou, Alexander

A2 - Dondi, Riccardo

A2 - Herodotou, Herodotos

A2 - Kapoutsis, Christos

A2 - Manolopoulos, Yannis

A2 - Papadopoulos, George A.

A2 - Sikora, Florian

PB - Springer

Y2 - 20 January 2020 through 24 January 2020

ER -