021-55664888

扫描二维码关注
复旦大学管理学院

查看更多

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

 

时间:2018年8月21日(周二)13:30

地点:史带楼303

主持人:张显东教授

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

TitleA 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

快速链接

扫一扫,欢迎关注
复旦管院官方微信