{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:38:23Z","timestamp":1787341103285,"version":"build-2736575974"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M008118\/1"],"award-info":[{"award-number":["EP\/M008118\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/L011018\/1"],"award-info":[{"award-number":["EP\/L011018\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer $d$ we construct rather simple games with cost functions of degree at most $d$ which have a PoS of at least $\\varOmega(\\Phi_d)^{d+1}$, where $\\Phi_d\\sim d\/\\ln d$ is the unique positive root of the equation $x^{d+1}=(x+1)^d$. This almost closes the huge gap between $\\varTheta(d)$ and $\\Phi_d^{d+1}$. Our bound extends also to network congestion games. We further show that the PoS remains exponential even for singleton games. More generally, we provide a lower bound of $\\varOmega((1+1\/\\alpha)^d\/d)$ on the PoS of $\\alpha$-approximate Nash equilibria for singleton games. All our lower bounds hold for mixed and correlated equilibria as well. On the positive side, we give a general upper bound on the PoS of $\\alpha$-approximate Nash equilibria, which is sensitive to the range $W$ of the player weights and the approximation parameter $\\alpha$. We do this by explicitly constructing a novel approximate potential function, based on Faulhaber's formula, that generalizes Rosenthal's potential in a continuous, analytic way. From the general theorem, we deduce two interesting corollaries. First, we derive the existence of an approximate pure Nash equilibrium with PoS at most $(d+3)\/2$; the equilibrium's approximation parameter ranges from $\\varTheta(1)$ to $d+1$ in a smooth way with respect to $W$. Second, we show that for unweighted congestion games, the PoS of $\\alpha$-approximate Nash equilibria is at most $(d+1)\/\\alpha$.<\/jats:p>","DOI":"10.1137\/18m1207880","type":"journal-article","created":{"date-parts":[[2019,10,24]],"date-time":"2019-10-24T11:16:08Z","timestamp":1571915768000},"page":"1544-1582","source":"Crossref","is-referenced-by-count":16,"title":["The Price of Stability of Weighted Congestion Games"],"prefix":"10.1137","volume":"48","author":[{"given":"George","family":"Christodoulou","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Gairing","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2382-1779","authenticated-orcid":true,"given":"Yiannis","family":"Giannakopoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,10,24]]},"reference":[{"key":"atypb1","unstructured":"M. Abramowitz and I. A. Stegun,\n                      Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables\n                      , 10th ed., Dover, New York, 1964,http:\/\/people.math.sfu.ca\/~cbm\/aands\/."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/1455248.1455249"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/090748986"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/070701376"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/070680096"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/070702370"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"J. Bernoulli,\n                      Ars conjectandi, opus posthumum. Accedit Tractatus de seriebus infinitis, et epistola gallic\u00e9 scripta de ludo pilae reticularis\n                      , impensis Thurnisiorum, fratrum, Basile\\ae, 1713,https:\/\/books.google.de\/books?id=ebdcNfPz8l8C.","DOI":"10.5479\/sil.262971.39088000323931"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/2629666"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9826-1"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9411-6"},{"key":"atypb11","first-page":"10","volume":"17","author":"Bil\u00f2 V.","year":"2017","journal-title":"Germany"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"V. Bil\u00f2, M. Flammini, and L. Moscardelli,\n                      The price of stability for undirected broadcast network design with fair cost allocation is constant\n                      , Games Econom. Behavior, to appear,https:\/\/doi.org\/10.1016\/j.geb.2014.09.010.","DOI":"10.1016\/j.geb.2014.09.010"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9427-8"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"I. Caragiannis, A. Fanelli, N. Gravin, and A. Skopalik,\n                      Efficient computation of approximate pure Nash equilibria in congestion games\n                      , in Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science, Palm Springs, CA, 2011,https:\/\/doi.org\/10.1109\/focs.2011.50.","DOI":"10.1109\/FOCS.2011.50"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/2614687"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9128-8"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/2841229"},{"key":"atypb18","first-page":"67","author":"Christodoulou G.","year":"2005","journal-title":"New York"},{"key":"atypb19","first-page":"59","author":"Christodoulou G.","year":"2005","journal-title":"Berlin"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9449-2"},{"key":"atypb21","first-page":"10","volume":"150","author":"Christodoulou G.","year":"2018","journal-title":"Czech Republic"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"J. H. Conway and R. K. Guy,\n                      The Book of Numbers\n                      , Springer, New York, 1996,https:\/\/doi.org\/10.1007\/978-1-4612-4072-3.","DOI":"10.1007\/978-1-4612-4072-3"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0322"},{"key":"atypb24","first-page":"604","author":"Fabrikant A.","year":"2004","journal-title":"New York"},{"key":"atypb25","unstructured":"J. Faulhaber,\n                      Academia Algebr\\ae: Darinnen die miraculosische Inventiones zu den h\u00f6chsten Cossen weiters continuirt und profitiert werden\n                      , Johann Ulrich Sch\u00f6nigs, Augspurg, 1631,https:\/\/books.google.de\/books?id=0pw_AAAAcAAJ."},{"key":"atypb26","first-page":"191","author":"Feldotto M.","year":"2017","journal-title":"Cham"},{"key":"atypb27","first-page":"608","author":"Fiat A.","year":"2006","journal-title":"Berlin"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.024"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.01.004"},{"key":"atypb30","first-page":"142","author":"Goemans M.","year":"2005","journal-title":"PA"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"R. L. Graham, D. E. Knuth, and O. Patashnik,\n                      Concrete Mathematics: A Foundation for Computer Science\n                      , Addison-Wesley, Reading, MA, 1989.","DOI":"10.1063\/1.4822863"},{"key":"atypb32","unstructured":"C. Hansknecht, M. Klimm, and A. Skopalik,\n                      Approximate pure Nash equilibria in weighted congestion games\n                      , in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2014), Leibniz International Proceedings in Informatics (LIPIcs) 28, K. Jansen, J. D. P. Rolim, N. R. Devanur, and C. Moore, eds., Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany, 2014, pp. 242-257,https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2014.242."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0543"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9315-x"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-012-0322-1"},{"key":"atypb36","first-page":"263","volume":"12","author":"C. G.","year":"1834","journal-title":"J. Reine Angew. Math."},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1993-1197512-7"},{"key":"atypb38","first-page":"404","author":"Koutsoupias E.","year":"1999","journal-title":"New York"},{"key":"atypb39","first-page":"607","author":"Lee E.","year":"2013","journal-title":"New York"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1940.11991015"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016770831869"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"D. S. Mitrinovi\u0107,\n                      Analytic Inequalities\n                      , Springer, Berlin, Heidelberg, 1970,https:\/\/doi.org\/10.1007\/978-3-642-99970-3.","DOI":"10.1007\/978-3-642-99970-3"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"N. Nisan, T. Roughgarden, \u00c9. Tardos, and V. Vazirani, eds.\n                      Algorithmic Game Theory\n                      , Cambridge University Press, Cambridge, UK, 2007.","DOI":"10.1017\/CBO9780511800481"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1216584"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030104"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1145\/2806883"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2003.06.004"},{"key":"atypb51","first-page":"86","author":"Schulz A. S.","year":"2003","journal-title":"Philadelphia"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1207880","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:05:36Z","timestamp":1787339136000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1207880"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":51,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1207880"],"URL":"https:\/\/doi.org\/10.1137\/18m1207880","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}