Xujin Chen

本文基于 Grabisch 等人 2010 年提出的社交网络影响力博弈模型展开研究. 在一个强连通网络中, 每个顶点被称为一个（社交网络）成员, 每个成员都有一个位于 [0, 1] 中的数字表示他的初始观点, 并且该观点可以动态演变. 博弈在两个博弈人之间展开, 其分别具有固定的观点 0 和 1; 他们分别选择一个成员作为自己的影响目标, 使得其影响力通过网络中成员之间的相互作用而传播, 从而影响整个社交网络中所有成员的观点. 博弈人的目标是使全体成员的平均观点(值)尽可能接近自己的固有观点 (0 或 1). 本文引入一个新的影响力传播矩阵来刻画博弈人对成员的影响作用, ,当两个局中人具有相同影响力时, 给出了纳什均衡存在的充分条件, 并证明了在具有均匀权重的双向树网络中纳什均衡一定存在. 对网络实例特别是随机网络的模拟实验结果显示: 与 Grabisch 等人模型相比, 新的影响力传播矩阵放宽了一系列网络中纳什均衡的存在性条件.

In this paper, we are concerned with bounding agents’ residence times in the network for a broad class of atomic dynamic routings. We explore novel token techniques to circumvent direct analysis on complicated chain effects of dynamic routing choices. Even though agents may enter the network over time for an infinite number of periods, we prove that under a mild condition, the residence time of every agent is upper bounded (by a network-dependent constant plus the total number of agents inside the network at the entry time of the agent). Applying this result to three game models of atomic dynamic routing in the recent literature, we establish that the residence times of selfish agents in a series-parallel network with a single origin-destination pair are upper bounded at equilibrium, provided the number of incoming agents at each time point does not exceed the network capacity (i.e., the smallest total capacity of edges in the network whose removal separates the origin from the destination).

We propose a game model for selfish routing of atomic agents, who compete for use of a network to travel from their origins to a common destination as quickly as possible. We follow a frequently used rule that the latency an agent experiences on each edge is a constant transit time plus a variable waiting time in a queue. A key feature that differentiates our model from related ones is an edge-based tie-breaking rule for prioritizing agents in queueing when they reach an edge at the same time. We study both nonadaptive agents (each choosing a one-off origin–destination path simultaneously at the very beginning) and adaptive ones (each making an online decision at every nonterminal vertex they reach as to which next edge to take). On the one hand, we constructively prove that a (pure) Nash equilibrium (NE) always exists for nonadaptive agents and show that every NE is weakly Pareto optimal and globally first-in first-out. We present efficient algorithms for finding an NE and best responses of nonadaptive agents. On the other hand, we are among the first to consider adaptive atomic agents, for which we show that a subgame perfect equilibrium (SPE) always exists and that each NE outcome for nonadaptive agents is an SPE outcome for adaptive agents but not vice versa.