A convergence analysis of the price of anarchy in atomic congestion games

dc.contributor.authorWu, Zijun
dc.contributor.authorMöhring, Rolf H.
dc.contributor.authorRen, Chunying
dc.contributor.authorXu , Dachuan
dc.date.accessioned2023-03-29T08:12:20Z
dc.date.available2023-03-29T08:12:20Z
dc.date.issued2022-06-28
dc.description.abstractWe analyze the convergence of the price of anarchy (PoA) of Nash equilibria in atomic congestion games with growing total demand T. When the cost functions are polynomials of the same degree, we obtain explicit rates for a rapid convergence of the PoAs of pure and mixed Nash equilibria to 1 in terms of 1/T and dmax/T, where dmax is the maximum demand controlled by an individual. Similar convergence results carry over to the random inefficiency of the random flow induced by an arbitrary mixed Nash equilibrium. For arbitrary polynomial cost functions, we derive a related convergence rate for the PoA of pure Nash equilibria (if they exist) when the demands fulfill certain regularity conditions and dmax is bounded as T→∞. In this general case, also the PoA of mixed Nash equilibria converges to 1 as T→∞ when dmax is bounded. Our results constitute the first convergence analysis for the PoA in atomic congestion games and show that selfish behavior is well justified when the total demand is large.en
dc.description.sponsorshipTU Berlin, Open-Access-Mittel – 2022
dc.identifier.eissn1436-4646
dc.identifier.issn0025-5610
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/18688
dc.identifier.urihttps://doi.org/10.14279/depositonce-17496
dc.language.isoen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subject.ddc510 Mathematikde
dc.subject.otheratomic congestion gamesen
dc.subject.otherpure and mixed Nash equilibriaen
dc.subject.otherprice of anarchyen
dc.subject.otherinefficiency of equilibriaen
dc.titleA convergence analysis of the price of anarchy in atomic congestion gamesen
dc.typeArticle
dc.type.versionpublishedVersion
dcterms.bibliographicCitation.doi10.1007/s10107-022-01853-0
dcterms.bibliographicCitation.journaltitleMathematical Programming
dcterms.bibliographicCitation.originalpublishernameSpringer Nature
dcterms.bibliographicCitation.originalpublisherplaceHeidelberg
dcterms.rightsHolder.referenceCreative-Commons-Lizenz
tub.accessrights.dnbfree
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::FG Kombinatorische Optimierung und Graphenalgorithmen
tub.publisher.universityorinstitutionTechnische Universität Berlin

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
Wu_etal_convergence_2022.pdf
Size:
925.76 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.23 KB
Format:
Item-specific license agreed upon to submission
Description:

Collections