Selfishness need not be bad

DOI10.1287/OPRE.2020.2036MaRDI QIDQ4994166zbMATH OpenOpenAlexFDO

Authors Zijun Wu, Rolf H. Möhring, Yanyan Chen, Dachuan Xu

Publication date 17 June 2021

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.07464

zbMATH Keywords

price of anarchyselfish routingrouting gameuser behaviornonatomic congestion gamestatic traffic

Mathematics Subject Classification ID

Potential and congestion games (91A14)

Abstract: We investigate the price of anarchy (PoA) in non-atomic congestion games when the total demand $T$ gets very large. First results in this direction have recently been obtained by cite{Colini2016On, Colini2017WINE, Colini2017arxiv} for routing games and show that the PoA converges to 1 when the growth of the total demand $T$ satisfies certain regularity conditions. We extend their results by developing a Wuuu{new} framework for the limit analysis of Wuuuu{the PoA that offers strong techniques such as the limit of games and applies to arbitrary growth patterns of $T$.} Wuuu{We} show that the PoA converges to 1 in the limit game regardless of the type of growth of $T$ for a large class of cost functions that contains all polynomials and all regularly varying functions. % For routing games with BPR Wuu{cost} functions, we show in addition that socially optimal strategy profiles converge to Wuu{equilibria} in the limit game, and that PoA$$, where $$ is the degree of the Wuu{BPR} functions. However, the precise convergence rate depends crucially on the the growth of $T$, which shows that a conjecture proposed by cite{O2016Mechanisms} need not hold.

Recommendations

• A convergence analysis of the price of anarchy in atomic congestion games
• When is selfish routing bad? The price of anarchy in light and heavy traffic
• The asymptotic behavior of the price of anarchy
• On the price of anarchy of highly congested nonatomic network games
• Price of anarchy for highly congested routing games in parallel networks

Cites work

• scientific article; zbMATH DE number 1754580 (Why is no real title available?)
• scientific article; zbMATH DE number 4000257 (Why is no real title available?)
• A class of games possessing pure-strategy Nash equilibria
• A note on two problems in connexion with graphs
• Algorithmic Game Theory
• Bounding the inefficiency of equilibria in nonatomic congestion games
• Computing network tolls with support constraints
• How bad is selfish routing?
• Intrinsic robustness of the price of anarchy
• Introduction to the inefficiency of equilibria
• On the Inefficiency of Equilibria in Congestion Games
• On the price of anarchy of highly congested nonatomic network games
• Routing games
• Selfish Routing in Capacitated Networks
• System-Optimal Routing of Traffic Flows with User Constraints in Networks with Congestion
• The asymptotic behavior of the price of anarchy
• The price of anarchy is independent of the network topology
• The “Price of Anarchy” Under Nonlinear and Asymmetric Costs
• Traffic assignment problem for a general network
• When is selfish routing bad? The price of anarchy in light and heavy traffic
• Worst-case equilibria

Cited in

(9)

• A game-theoretic perspective of deep neural networks
• scientific article; zbMATH DE number 1260839 (Why is no real title available?)
• A convergence analysis of the price of anarchy in atomic congestion games
• A game-theoretic analysis of deep neural networks
• On the price of anarchy of highly congested nonatomic network games
• Nonatomic non-cooperative neighbourhood balancing games
• Impure altruism and impure selfishness
• The price of anarchy in routing games as a function of the demand
• Coping with selfish on-going behaviors

This page was built for publication: Selfishness need not be bad

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4994166)