Atomic Dynamic Flow Games: Adaptive vs. Nonadaptive Agents
研究了原子智能体自私路由的博弈模型，智能体从起点到共同终点竞争网络资源，排队规则基于边级平局打破。证明了非自适应智能体的纳什均衡存在性及性质，并首次考虑自适应智能体，证明子博弈完美均衡存在且非自适应均衡是自适应均衡的子集。
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.