{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:01:36Z","timestamp":1787320896378,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Control Optim."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We study the repeated, nonatomic congestion game, in which multiple populations of players share resources and make, at each iteration, a decentralized decision on which resources to utilize. We investigate the following question: given a model of how individual players update their strategies, does the resulting dynamics of strategy profiles converge to the set of Nash equilibria of the one-shot game? We consider in particular a model in which players update their strategies using algorithms with sublinear discounted regret. We show that the resulting sequence of strategy profiles converges to the set of Nash equilibria in the sense of Ces\u00e0ro means. However, convergence of the actual sequence is not guaranteed in general. We show that it can be guaranteed for a class of algorithms with a sublinear discounted regret and which satisfy an additional condition. We call such algorithms AREP (approximate replicator) algorithms, as they can be interpreted as a discrete-time approximation of the replicator equation, which models the continuous-time evolution of population strategies, and which is known to converge for the class of congestion games.<\/jats:p>","DOI":"10.1137\/140980685","type":"journal-article","created":{"date-parts":[[2015,4,21]],"date-time":"2015-04-21T12:28:52Z","timestamp":1429619332000},"page":"1056-1081","source":"Crossref","is-referenced-by-count":43,"title":["Online Learning of Nash Equilibria in Congestion Games"],"prefix":"10.1137","volume":"53","author":[{"given":"Walid","family":"Krichene","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Drigh\u00e8s","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexandre M.","family":"Bayen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,4,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"atypb2","unstructured":"J.Y. Audibert and S. Bubeck,\n                      Minimax policies for adversarial and stochastic bandits\n                      , in Proceedings of COLT, 2009."},{"key":"atypb3","first-page":"45","author":"Awerbuch B.","year":"2004","journal-title":"New York"},{"key":"atypb4","first-page":"1","author":"Benai\u0308m M.","year":"1999","journal-title":"New York"},{"key":"atypb5","first-page":"45","author":"Blum A.","year":"2006","journal-title":"New York"},{"key":"atypb6","first-page":"79","author":"Blum A.","year":"2007","journal-title":"UK"},{"key":"atypb7","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, UK, 2010."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1561\/2200000024"},{"key":"atypb9","unstructured":"S. Bubeck, V. Perchet, and Philippe Rigollet,\n                      Bounded Regret in Stochastic Multi-armed Bandits\n                      , CoRR abs\/1302.1611, 2013."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"N. Cesa-Bianchi and G. Lugosi,\n                      Prediction, Learning, and Games\n                      , Cambridge University Press, Cambridge, UK, 2006.","DOI":"10.1017\/CBO9780511546921"},{"key":"atypb11","first-page":"323","author":"Fischer S.","year":"2004","journal-title":"New York"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.3390\/g4040561"},{"key":"atypb13","unstructured":"D. H. Fremlin,\n                      Measure Theory\n                      , vol. 4, Torres Fremlin, Colchester, UK, 2000."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0738"},{"key":"atypb15","first-page":"2369","volume":"8","author":"Gyo\u0308rgy A.","year":"2007","journal-title":"J. Mach. Learn. Res."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2009.01.007"},{"key":"atypb17","unstructured":"H. K. Khalil,\n                      Nonlinear Systems\n                      , Macmillan, New York, 1992."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.2612"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"R. Kleinberg, G. Piliouras, and E. Tardos,\n                      Multiplicative updates outperform generic no-regret learning in congestion games: Extended abstract\n                      , in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 533-542.","DOI":"10.1145\/1536414.1536487"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias and C. Papadimitriou,\n                      Worst-case equilibria\n                      , in Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, 1999, pp. 404-413.","DOI":"10.1007\/3-540-49116-3_38"},{"key":"atypb21","first-page":"256","author":"Littlestone N.","year":"1989","journal-title":"IEEE"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"M. Muresan,\n                      A Concrete Approach to Classical Analysis\n                      , Springer, New York, 2009.","DOI":"10.1007\/978-0-387-78933-0"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"atypb25","first-page":"461","author":"Roughgarden T.","year":"2007","journal-title":"UK"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.2000.2696"},{"key":"atypb28","first-page":"325","author":"Wardrop J. G.","year":"1952","journal-title":"London"},{"key":"atypb29","unstructured":"J. W. Weibull,\n                      Evolutionary Game Theory\n                      , MIT Press, Cambridge, MA, 1997."}],"container-title":["SIAM Journal on Control and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140980685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:02:08Z","timestamp":1787317328000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140980685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140980685"],"URL":"https:\/\/doi.org\/10.1137\/140980685","relation":{},"ISSN":["0363-0129","1095-7138"],"issn-type":[{"value":"0363-0129","type":"print"},{"value":"1095-7138","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}