Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium
Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium
复制标题
两人竞争扩散博弈：图类和纳什均衡的存在
DOI：
10.1007/978-3-030-38919-2_52
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ryogo Yamaguchi
中科院分区：
文献类型：
--
作者：
Naoka Fukuzono;Tesshu Hanaka;Hironori Kiya;Hirotaka Ono;Ryogo Yamaguchi
竞争扩散博弈是由Alon等人提出的图上信息传播的博弈论模型。(2010)。在该模型中，玩家选择图形的一个初始顶点，玩家通过与该初始顶点连接的边来传播信息。如果一个尚未受任何信息影响的顶点收到玩家的信息，它就会受到该信息的影响，并将其扩散到相邻的顶点。同时接收两种或更多类型信息的顶点从此不会扩散任何类型的信息。玩家的目标是最大化受玩家信息影响的顶点数量。本文研究了弦上两人竞争扩散博弈的纯Nash均衡的存在性及其相关图。我们证明了块图、分裂图和区间图都是弦图的子类，它们都存在纯Nash均衡。另一方面，我们证明了在(强)弦图上存在一个不存在纯Nash均衡的例子；找到了纯Nash均衡存在的边界。
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.