Bounding Residence Times for Atomic Dynamic Routings

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

Mathematics of Operations Research, 2022, vol. 47, issue 4, 3261-3281

Abstract: In this paper, we are concerned with bounding agents’ residence times in the network for a broad class of atomic dynamic routings. We explore novel token techniques to circumvent direct analysis on complicated chain effects of dynamic routing choices. Even though agents may enter the network over time for an infinite number of periods, we prove that under a mild condition, the residence time of every agent is upper bounded (by a network-dependent constant plus the total number of agents inside the network at the entry time of the agent). Applying this result to three game models of atomic dynamic routing in the recent literature, we establish that the residence times of selfish agents in a series-parallel network with a single origin-destination pair are upper bounded at equilibrium, provided the number of incoming agents at each time point does not exceed the network capacity (i.e., the smallest total capacity of edges in the network whose removal separates the origin from the destination).

Keywords: Primary: 91A43; Secondary: 91A50; 05C21; atomic dynamic routing; residence time; token technique; selfish routing; Nash equilibrium (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1242 (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:ormoor:v:47:y:2022:i:4:p:3261-3281

Access Statistics for this article

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