{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:56Z","timestamp":1787337476778,"version":"build-2736575974"},"reference-count":54,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>Many natural games have a dramatic difference between the quality of their best and worst Nash equilibria, even in pure strategies. Yet, nearly all results to date on dynamics in games show only convergence to some equilibrium, especially within a polynomial number of steps. In this work we initiate a theory of how well-motivated multiagent dynamics can make use of global information about the game---which might be common knowledge or injected into the system by a helpful central agency---and show that in a wide range of interesting games this can allow the dynamics to quickly reach (within a polynomial number of steps) states of cost comparable to the best Nash equilibrium. We present several natural models for dynamics that can use such additional information and analyze their ability to reach low-cost states for two important and widely studied classes of potential games: network design with fair cost-sharing and party affiliation games (which include consensus and cut games). From the perspective of a central agency, our work can be viewed as analyzing how a public service advertising campaign can help \u201cnudge\u201d behavior into a good state, when players cannot be expected to all blindly follow along but instead view the information as an additional input into their dynamics. We show that in many cases, this additional information is sufficient for natural dynamics to quickly reach states of cost comparable to the best Nash equilibrium of the game.<\/jats:p>","DOI":"10.1137\/110821317","type":"journal-article","created":{"date-parts":[[2013,1,29]],"date-time":"2013-01-29T12:52:05Z","timestamp":1359463925000},"page":"230-264","source":"Crossref","is-referenced-by-count":19,"title":["Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior"],"prefix":"10.1137","volume":"42","author":[{"given":"Maria-Florina","family":"Balcan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avrim","family":"Blum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,1,29]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"H. Ackermann, H. R\u00f6glin, and B. V\u00f6cking,\n                      On the impact of combinatorial structure on congestion games\n                      , in Proceedings of the 47th FOCS, 2006.","DOI":"10.1109\/FOCS.2006.55"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"A. Agarwal, M. Charikar, K. Makarychev, and Y. Makarychev,\n                      ${O}(\\sqrt{\\log n})$ approximation algorithms for Min UnCut, Min $2$CNF deletion, and directed cut problems\n                      , in Proceedings of the 37th STOC, 2005.","DOI":"10.1145\/1060590.1060675"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"S. Albers, S. Eilts, E. Even-Dar, Y. Mansour, and L. Roditty,\n                      On Nash equilibria for a network creation game\n                      , in Proceedings of the 17th ACM-SIAM SODA, 2006.","DOI":"10.1145\/1109557.1109568"},{"key":"atypb4","unstructured":"N. Andelman, M. Feldman, and Y. Mansour,\n                      Strong price of anarchy\n                      , in Proceedings of the 18th ACM-SIAM SODA, 2007."},{"key":"atypb5","unstructured":"E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden,\n                      The price of stability for network design with fair cost allocation\n                      , in Proceedings of FOCS, 2004."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, A. Epstein, and A. Skopalik,\n                      Fast convergence to nearly optimal solutions in potential games\n                      , in Proceedings of ACM Conference on Electronic Commerce, 2008.","DOI":"10.1145\/1386790.1386832"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"M.F. Balcan, A. Blum, and Y. Mansour,\n                      Improved equilibria via public service advertising\n                      , in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2009.","DOI":"10.1137\/1.9781611973068.80"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"M.F. Balcan, A. Blum, and Y. Mansour,\n                      The price of uncertainty\n                      , in Proceedings of the 10th ACM Conference on Electronic Commerce, 2009.","DOI":"10.1145\/1566374.1566416"},{"key":"atypb10","first-page":"200","author":"Balcan M.-F.","year":"2010","journal-title":"Proceedings of ICS"},{"key":"atypb11","unstructured":"M.F. Balcan, S. Krehbiel, G. Piliouras, and J. Shin,\n                      Near Optimality in Covering and Packing Games by Exposing Global Information\n                      , CoRR abs\/1109.3606, 2011."},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"A. Blum, Hajiaghayi, K. Ligett, and A. Roth,\n                      Regret minimization and the price of total anarchy\n                      , in Proceedings of STOC, 2008.","DOI":"10.1145\/1374376.1374430"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"A. Blum and Y. Mansour,\n                      Learning, regret-minimization, and equilibria\n                      , in Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, eds., Cambridge University Press, Cambridge, UK, 2007.","DOI":"10.1017\/CBO9780511800481.006"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1006\/game.1993.1023"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/S0899-8256(02)00554-7"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/258128.258179"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. Charikar, H. Karloff, C. Mathieu, J. Naor, and M. Saks,\n                      Online multicast with egalitarian cost sharing\n                      , in Proceedings of the 20th SPAA, 2008.","DOI":"10.1145\/1378533.1378544"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"G. Christodoulou and E. Koutsoupias,\n                      The price of anarchy of finite congestion games\n                      , in Proceedings of the 37th STOC, 2005.","DOI":"10.1145\/1060590.1060600"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"G. Christodoulou, V. S. Mirrokni, and A. Sidiropoulos,\n                      Convergence and approximation in potential games\n                      , in Proceedings of the 23rd STACS, 2006.","DOI":"10.1007\/11672142_28"},{"key":"atypb20","first-page":"15","author":"Clarkson K. L.","year":"2006","journal-title":"MA"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"R. Cole, Y. Dodis, and T. Roughgarden,\n                      How much can taxes help selfish routing?\n                      , in Proceedings of ACM-EC, 2003.","DOI":"10.1145\/779928.779941"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"R. Cole, Y. Dodis, and T. Roughgarden,\n                      Pricing network edges for heterogeneous selfish users\n                      , in Proceedings of STOC, 2003.","DOI":"10.1145\/780615.780618"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1040.0098"},{"key":"atypb24","unstructured":"A. Czumaj and B. Voecking,\n                      Tight bounds for worst-case equilibria\n                      , in Proceedings of the 13th ACM-SIAM SODA, 2002."},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"E. D. Demaine, M.T. Hajiaghayi, H. Mahini, and M. Zadimoghaddam,\n                      The price of anarchy in network creation games\n                      , in Proceedings of the 17th SODA, 2006.","DOI":"10.1145\/1281100.1281142"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.625251"},{"key":"atypb27","first-page":"3","author":"Even-Dar E.","year":"2007","journal-title":"ACM Trans. Algorithms"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"A. Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou, and S. Shenker,\n                      On a network creation game\n                      , in Proceedings of the 22nd PODC, 2003.","DOI":"10.1145\/872035.872088"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"A. Fanelli, M. Flamminia, and L. Moscardelli,\n                      Speed of convergence in congestion games under best responce dynamics\n                      , in Proceedings of the 35th ICALP, 2008.","DOI":"10.1007\/978-3-540-70575-8_65"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0595"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/85.2.379"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0740"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.024"},{"key":"atypb34","unstructured":"J. Hannan,\n                      Approximation to bayes risk in repeated plays\n                      , in Contributions to the Theory of Games, M. Dresher, A. Tucker, and P. Wolfe, eds., Princeton University Press, Princeton, NJ, 1957, pp, 97-139."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00153"},{"key":"atypb36","first-page":"181","author":"Hart S.","year":"2001","journal-title":"Berlin"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"R. Kleinberg, G. Piliouras, and E. Tardos,\n                      Multiplicative updates outperform generic no-regret learning in congestion games\n                      , in Proceedings of the 41th STOC, 2009.","DOI":"10.1145\/1536414.1536487"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"D. Korzhyk, V. Conitzer, and R. Parr,\n                      Complexity of computing optimal stackelberg strategies in security resource allocation games\n                      , in Proceedings of the 24th AAAI, 2010.","DOI":"10.1609\/aaai.v24i1.7638"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias and C. H. Papadimitriou,\n                      Worst-case equilibria\n                      , in Proceedings of the 16th STACS, 1999, pp. 404-413.","DOI":"10.1007\/3-540-49116-3_38"},{"key":"atypb40","first-page":"465","author":"Littlestone N.","year":"1991","journal-title":"New York"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2012.03.006"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"atypb44","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 1997."},{"key":"atypb45","doi-asserted-by":"crossref","unstructured":"N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, eds.\n                      Algorithmic Game Theory\n                      , Cambridge University Press, Cambridge, UK, 2007.","DOI":"10.1017\/CBO9780511800481"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v30i1.2173"},{"key":"atypb47","first-page":"2","author":"Rosenthal R. W.","year":"1973","journal-title":"Internat. J. Game Theory"},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"T. Roughgarden,\n                      Intrinsic robustness of the price of anarchy\n                      , in Proceedings of STOC, 2009.","DOI":"10.1145\/1536414.1536485"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"Y. Sharma and D. P. Williamson,\n                      Stackelberg thresholds in network routing games or the value of altruism\n                      , in Proceedings of ACM Conference on Electronic Commerce, 2007.","DOI":"10.1145\/1250910.1250925"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-005-0465-4"},{"key":"atypb52","unstructured":"H. von Stackelberg,\n                      The Theory of the Market Economy\n                      , Oxford University Press, Oxford, UK, 1952."},{"key":"atypb53","doi-asserted-by":"crossref","unstructured":"B. Widrow and M. E. Hoff,\n                      Adaptive switching circuits\n                      , 1960 IRE WESCON Convention Record, 1960, pp. 96-104.","DOI":"10.21236\/AD0241531"},{"key":"atypb54","unstructured":"M. Zinkevich,\n                      Online convex programming and generalized infinitesimal gradient ascent\n                      , in Proceedings of the 20th International Conference on Machine Learning, 2003."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110821317","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:23Z","timestamp":1787335943000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110821317"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/110821317"],"URL":"https:\/\/doi.org\/10.1137\/110821317","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}