管科系系列讲座第214期预告

时间：2018年8月21日（周二）13:30

地点：史带楼303

主持人：张显东教授

主讲嘉宾： Professor Bo Chen, Chair of Operations Research & Management Science, Warwick Business School, University of Warwick.

Title：A Tractable Network Game of Atomic Dynamic Flows

Abstract: Selfish routing, where agents compete in a network for traveling from their origins to destinations as fast as possible, is dynamic in nature. However, capturing such dynamics with a tractable model is challenging, especially when agents are atomic. We propose a network game model, which not only makes a good simulation of the dynamics, but also possesses some nice properties with theoretical and algorithmic tractability. Our edge-priority tie-breaking rule on congestion is key for tractability, which stands in contrast to previous related negative results in the literature.

We study Nash equilibrium (NE) for non-adaptive agents, who select and fix their own origin-destination paths simultaneously at the start. We constructively prove that an NE exists for multiple-origin single-destination networks. We characterize, supported by efficient algorithms, all NEs with many desirable properties, such as weak Pareto efficiency and global First-In-First-Out.

We further investigate an unexplored area of atomic dynamic routing games­—the subgame perfect equilibrium (SPE) for adaptive agents, who make an online decision at each nonterminal vertex they reach as to which next edge to take. We prove that, in a single-destination network, an SPE always exists, and that every NE of non-adaptive agents is realizable by some SPE of adaptive agents. This allows us to build a bridge between non-adaptive and adaptive models.

(An extended abstract of a preliminary version of this work appeared in the Proceedings of the ACM Conference on Economics and Computation EC'17 [Cao et al., 2017].

管理科学系

2018-7-27