• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Cao, Zhigang (Cao, Zhigang.) | Chen, Bo (Chen, Bo.) | Chen, Xujin (Chen, Xujin.) | Wang, Changjun (Wang, Changjun.)

Indexed by:

SSCI EI Scopus SCIE

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.

Keyword:

adaptive routing selfish atomic routing Nash equilibrium subgame perfect equilibrium deterministic queuing

Author Community:

  • [ 1 ] [Cao, Zhigang]Beijing Jiaotong Univ, Sch Econ & Management, Beijing 100044, Peoples R China
  • [ 2 ] [Chen, Bo]Univ Warwick, Warwick Business Sch, Coventry CV4 7AL, W Midlands, England
  • [ 3 ] [Chen, Xujin]Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
  • [ 4 ] [Wang, Changjun]Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
  • [ 5 ] [Chen, Xujin]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
  • [ 6 ] [Wang, Changjun]Beijing Univ Technol, Coll Math, Fac Sci, Beijing 100124, Peoples R China

Reprint Author's Address:

  • [Wang, Changjun]Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China;;[Wang, Changjun]Beijing Univ Technol, Coll Math, Fac Sci, Beijing 100124, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

OPERATIONS RESEARCH

ISSN: 0030-364X

Year: 2021

Issue: 6

Volume: 69

Page: 1680-1695

2 . 7 0 0

JCR@2022

ESI Discipline: ENGINEERING;

ESI HC Threshold:87

JCR Journal Grade:2

Cited Count:

WoS CC Cited Count: 5

SCOPUS Cited Count: 6

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:700/6457656
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.