Exact Price of Anarchy for Polynomial Congestion Games

Sebastian Aland · Dominic Dumrauf · Martin Gairing · Burkhard Monien · Florian Schoppmann

104 citations0/0 files storedSIAM Journal on Computing

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Applications Complexity and Algorithms in Graphs Optimization and Search Problems

Abstract

We show exact values for the worst-case price of anarchy in weighted and unweighted (atomic unsplittable) congestion games, provided that all cost functions are bounded-degree polynomials with nonnegative coefficients. The given values also hold for weighted and unweighted network congestion games.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 104 citations exist upstream.

References

1951Non-Cooperative Games 1996Potential Games 1973A class of games possessing pure-strategy Nash equilibria 1996Congestion Games with Player-Specific Payoff Functions 2003Bounding the inefficiency of equilibria in nonatomic congestion games 2005Selfish unsplittable flows 2007Tight bounds for worst-case equilibria 2003Approximate Equilibria and Ball Fusion

Cited by

2014Barriers to Near-Optimal Equilibria 2013The Price of Routing Unsplittable Flow 2014Weighted Congestion Games 2014Local smoothness and the price of anarchy in splittable congestion games 2015Learning and Efficiency in Games with Dynamic Population 2012Optimal Cost Sharing for Resource Selection Games 2012Intrinsic robustness of the price of anarchy

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.