----------------------------------------------------------------------------------------------------

             Department of Systems Engineering and Engineering Management
                     The Chinese University of Hong Kong

----------------------------------------------------------------------------------------------------

Date: Friday, May 7, 2021, 16:30 to 17:30

Title: Atomic Dynamic Flows: Adaptive versus Non-adaptive Agents

Speaker: Professor Bo Chen, University of Warwick

Abstract:

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 fast 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 non-adaptive agents (each choosing a one-off origin-destination path simultaneously at the very beginning) and adaptive ones (each making an online decision at every non-terminal 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 non-adaptive 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 non-adaptive 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 non-adaptive agents is an SPE outcome for adaptive agents, but not vice versa.

Biography:

Professor Bo Chen, Fellow of the Academy of Social Sciences (FAcSS), Chair of Operational Research and Management Science, University of Warwick, UK. He holds a Ph.D. in Operations Research (Erasmus University Rotterdam, The Netherlands) and a Higher Doctorate D.Sc. (University of Warwick, UK). He is Fellow of the UK Operational Research Society and Fellow of the UK Institute of Mathematics and Its Applications. His main research interests include combinatorial optimization, scheduling and transportation, and game theory with mechanism design. Further information can be found on his institutional home page through this link: https://www.wbs.ac.uk/about/person/bo-chen