Atomic Dynamic Flow Games: Adaptive vs. Nonadaptive Agents

Zhigang Cao, Bo Chen (), Xujin Chen () and Changjun Wang ()
Additional contact information
Bo Chen: Warwick Business School, University of Warwick, Coventry CV4 7AL, United Kingdom
Xujin Chen: Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China
Changjun Wang: Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; College of Mathematics, Faculty of Science, Beijing University of Technology, Beijing 100124, China

Operations Research, 2021, vol. 69, issue 6, 1680-1695

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 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.

Keywords: selfish atomic routing; deterministic queuing; adaptive routing; subgame perfect equilibrium; Nash equilibrium (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2105 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:6:p:1680-1695

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().