Selfishness need not be bad

DOI10.1287/OPRE.2020.2036zbMATH Open1467.91008arXiv1712.07464OpenAlexW3123472234MaRDI QIDQ4994166FDOQ4994166

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

Publication date: 17 June 2021

Published in: Operations Research (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

price of anarchyselfish routingrouting gameuser behaviornonatomic congestion gamestatic traffic

Mathematics Subject Classification ID

Potential and congestion games (91A14)

Cites Work

• A note on two problems in connexion with graphs
• Algorithmic Game Theory
• Bounding the inefficiency of equilibria in nonatomic congestion games
• Worst-case equilibria
• Computing network tolls with support constraints
• Title not available (Why is that?)
• Selfish Routing in Capacitated Networks
• The price of anarchy is independent of the network topology
• A class of games possessing pure-strategy Nash equilibria
• How bad is selfish routing?
• Traffic assignment problem for a general network
• Routing games
• System-Optimal Routing of Traffic Flows with User Constraints in Networks with Congestion
• Introduction to the inefficiency of equilibria
• The “Price of Anarchy” Under Nonlinear and Asymmetric Costs
• On the Inefficiency of Equilibria in Congestion Games
• Title not available (Why is that?)
• On the Price of Anarchy of Highly Congested Nonatomic Network Games
• The Asymptotic Behavior of the Price of Anarchy
• Intrinsic Robustness of the Price of Anarchy
• When is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic

Cited In (8)

• A game-theoretic perspective of deep neural networks
• Title not available (Why is that?)
• A convergence analysis of the price of anarchy in atomic congestion games
• A game-theoretic analysis of deep neural networks
• 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)