{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:40:39Z","timestamp":1770741639079,"version":"3.49.0"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,8,11]],"date-time":"2020-08-11T00:00:00Z","timestamp":1597104000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,11]],"date-time":"2020-08-11T00:00:00Z","timestamp":1597104000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the computation and efficiency of pure Nash equilibria in combinatorial congestion games, where the strategies of each player <jats:italic>i<\/jats:italic> are given by the binary vectors of a polytope <jats:inline-formula><jats:alternatives><jats:tex-math>$$P_i$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>P<\/mml:mi>\n                    <mml:mi>i<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our main goal is to understand which structural properties of such <jats:italic>polytopal congestion games<\/jats:italic> enable us to derive an efficient equilibrium selection procedure to compute pure Nash equilibria with attractive social cost approximation guarantees. To this aim, we identify two general properties of the underlying <jats:italic>aggregation polytope<\/jats:italic><jats:inline-formula><jats:alternatives><jats:tex-math>$$P_N = \\sum _i P_i$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>P<\/mml:mi>\n                      <mml:mi>N<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:msub>\n                      <mml:mo>\u2211<\/mml:mo>\n                      <mml:mi>i<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:msub>\n                      <mml:mi>P<\/mml:mi>\n                      <mml:mi>i<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> which are sufficient for our results to go through, namely the <jats:italic>integer decomposition property<\/jats:italic> (<jats:italic>IDP<\/jats:italic>) and the <jats:italic>box-totally dual integrality property<\/jats:italic> (<jats:italic>box-TDI<\/jats:italic>). Our main results for polytopal congestion games satisfying IDP and box-TDI are as follows: (i) we show that pure Nash equilibria can be computed in polynomial time. In fact, we obtain this result through a general framework for separable convex function minimization, which might be of independent interest. (ii) We bound the inefficiency of these equilibria and show that this provides a tight bound on the price of stability. (iii) We also prove that these results extend to strong equilibria for the \u201cbottleneck variant\u201d of polytopal congestion games. Examples of polytopal congestion games satisfying IDP and box-TDI include common source network congestion games, symmetric totally unimodular congestion games, non-symmetric matroid congestion games and symmetric matroid intersection congestion games (in particular, <jats:italic>r<\/jats:italic>-arborescences and strongly base-orderable matroids).<\/jats:p>","DOI":"10.1007\/s10107-020-01546-6","type":"journal-article","created":{"date-parts":[[2020,8,11]],"date-time":"2020-08-11T15:05:26Z","timestamp":1597158326000},"page":"523-560","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Computation and efficiency of potential function minimizers of combinatorial congestion games"],"prefix":"10.1007","volume":"190","author":[{"given":"Pieter","family":"Kleer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guido","family":"Sch\u00e4fer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,11]]},"reference":[{"issue":"6","key":"1546_CR1","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/1455248.1455249","volume":"55","author":"H Ackermann","year":"2008","unstructured":"Ackermann, H., R\u00f6glin, H., V\u00f6cking, B.: On the impact of combinatorial structure on congestion games. J. ACM 55(6), 25:1\u201325:22 (2008)","journal-title":"J. ACM"},{"key":"1546_CR2","unstructured":"Aigner-Horev, E., Carmesin, J., Frohlich, J.O.: Infinite matroid union. (2012). arXiv:1111.0602"},{"issue":"5","key":"1546_CR3","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1137\/090748986","volume":"40","author":"S Aland","year":"2011","unstructured":"Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price of anarchy for polynomial congestion games. SIAM J. Comput. 40(5), 1211\u20131233 (2011)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1546_CR4","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1137\/070680096","volume":"38","author":"E Anshelevich","year":"2008","unstructured":"Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602\u20131623 (2008)","journal-title":"SIAM J. Comput."},{"key":"1546_CR5","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 57\u201366 (2005)","DOI":"10.1145\/1060590.1060599"},{"key":"1546_CR6","doi-asserted-by":"crossref","unstructured":"Baum, S.P., Trotter, L.E.: Integer rounding and polyhedral decomposition for totally unimodular systems. In: Henn, R., Korte, B., Oettli, W. (eds.) Optimization and Operations Research: Proceedings of a Workshop Held at the University of Bonn, October 2\u20138, 1977, pp. 15\u201323 (1978)","DOI":"10.1007\/978-3-642-95322-4_2"},{"issue":"3","key":"1546_CR7","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/s00453-010-9427-8","volume":"61","author":"I Caragiannis","year":"2011","unstructured":"Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing. Algorithmica 61(3), 606\u2013637 (2011)","journal-title":"Algorithmica"},{"key":"1546_CR8","unstructured":"Chan, H., Jiang, A.X.: Congestion games with polytopal strategy spaces. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence, pp. 165\u2013171 (2016)"},{"key":"1546_CR9","unstructured":"Chien, S., Sinclair, A.: Convergence to approximate Nash equilibria in congestion games. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 169\u2013178 (2007)"},{"issue":"2","key":"1546_CR10","first-page":"10:1","volume":"4","author":"G Christodoulou","year":"2016","unstructured":"Christodoulou, G., Gairing, M.: Price of stability in polynomial congestion games. ACM Trans. Econ. Comput. 4(2), 10:1\u201310:17 (2016)","journal-title":"ACM Trans. Econ. Comput."},{"key":"1546_CR11","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 67\u201373 (2005)","DOI":"10.1145\/1060590.1060600"},{"key":"1546_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2012.02.033","volume":"438","author":"G Christodoulou","year":"2012","unstructured":"Christodoulou, G., Mirrokni, V.S., Sidiropoulos, A.: Convergence and approximation in potential games. Theor. Comput. Sci. 438, 13\u201327 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"1546_CR13","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1287\/moor.1040.0098","volume":"29","author":"JR Correa","year":"2004","unstructured":"Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Selfish routing in capacitated networks. Math. Oper. Res. 29(4), 961\u2013976 (2004)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"1546_CR14","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/j.geb.2008.01.001","volume":"64","author":"JR Correa","year":"2008","unstructured":"Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: A geometric approach to the price of anarchy in nonatomic congestion games. Games Econ. Behav. 64(2), 457\u2013469 (2008)","journal-title":"Games Econ. Behav."},{"key":"1546_CR15","doi-asserted-by":"publisher","DOI":"10.7249\/R366","volume-title":"Linear Programming and Extensions","author":"GB Dantzig","year":"1963","unstructured":"Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)"},{"key":"1546_CR16","doi-asserted-by":"crossref","unstructured":"Del\u00a0Pia, A., Ferris, M., Michini, C.: Totally unimodular congestion games. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 577\u2013588 (2017)","DOI":"10.1137\/1.9781611974782.37"},{"key":"1546_CR17","doi-asserted-by":"crossref","unstructured":"de\u00a0Jong, J., Kern, W., Steenhuisen, B., Uetz, M.: The asymptotic price of anarchy for k-uniform congestion games. In: Approximation and Online Algorithms, pp. 317\u2013328 (2018)","DOI":"10.1007\/978-3-319-89441-6_23"},{"key":"1546_CR18","doi-asserted-by":"crossref","unstructured":"Edmonds, J.: Combinatorial Optimization\u2014Eureka, You Shrink! Papers Dedicated to Jack Edmonds, chap. Submodular Functions, Matroids, and Certain Polyhedra (2003)","DOI":"10.1007\/3-540-36478-1_2"},{"key":"1546_CR19","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Giles, R.: A min\u2013max relation for submodular functions on graphs. In: Studies in Integer Programming, Annals of Discrete Mathematics, vol.\u00a01, pp. 185\u2013204. Elsevier (1977)","DOI":"10.1016\/S0167-5060(08)70734-9"},{"issue":"3","key":"1546_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1273340.1273348","volume":"3","author":"E Even-Dar","year":"2007","unstructured":"Even-Dar, E., Kesselman, A., Mansour, Y.: Convergence time to Nash equilibrium in load balancing. ACM Trans. Algorithms 3(3), 1\u201332 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"1546_CR21","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C., Talwar, K.: The complexity of pure Nash equilibria. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 604\u2013612 (2004)","DOI":"10.1145\/1007352.1007445"},{"key":"1546_CR22","doi-asserted-by":"crossref","unstructured":"Feldman, M., Immorlica, N., Lucier, B., Roughgarden, T., Syrgkanis, V.: The price of anarchy in large games. In: Proceedings of the 48h Annual ACM Symposium on Theory of Computing, pp. 963\u2013976 (2016)","DOI":"10.1145\/2897518.2897580"},{"key":"1546_CR23","volume-title":"Flows in Networks","author":"DR Ford","year":"2010","unstructured":"Ford, D.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (2010)"},{"issue":"1","key":"1546_CR24","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s00224-009-9205-7","volume":"47","author":"D Fotakis","year":"2010","unstructured":"Fotakis, D.: Congestion games with linearly independent paths: convergence time and price of anarchy. Theory Comput. Syst. 47(1), 113\u2013136 (2010)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"1546_CR25","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49\u201365 (1987)","journal-title":"Combinatorica"},{"issue":"2","key":"1546_CR26","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1287\/moor.5.2.186","volume":"5","author":"S Fujishige","year":"1980","unstructured":"Fujishige, S.: Lexicographically optimal base of a polymatroid with respect to a weight vector. Math. Oper. Res. 5(2), 186\u2013196 (1980)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1546_CR27","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/j.orl.2015.04.002","volume":"43","author":"S Fujishige","year":"2015","unstructured":"Fujishige, S., Goemans, M., Harks, T., Peis, B., Zenklusen, R.: Congestion games viewed from m-convexity. Oper. Res. Lett. 43(3), 329\u2013333 (2015)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"1546_CR28","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1006\/jcss.1995.1022","volume":"50","author":"H Gabow","year":"1995","unstructured":"Gabow, H.: A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci. 50(2), 259\u2013273 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"7","key":"1546_CR29","doi-asserted-by":"publisher","first-page":"1199","DOI":"10.1016\/j.jcss.2008.07.001","volume":"74","author":"M Gairing","year":"2008","unstructured":"Gairing, M., L\u00fccking, T., Mavronicolas, M., Monien, B., Rode, M.: Nash equilibria in discrete routing games with convex latency functions. J. Comput. Syst. Sci. 74(7), 1199\u20131225 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"1546_CR30","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0377-2217(91)90300-K","volume":"54","author":"H Groenevelt","year":"1991","unstructured":"Groenevelt, H.: Two algorithms for maximizing a separable concave function over a polymatroid feasible region. Eur. J. Oper. Res. 54(2), 227\u2013236 (1991)","journal-title":"Eur. J. Oper. Res."},{"key":"1546_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)"},{"issue":"1","key":"1546_CR32","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s10107-012-0521-3","volume":"141","author":"T Harks","year":"2013","unstructured":"Harks, T., Hoefer, M., Klimm, M., Skopalik, A.: Computing pure nash and strong equilibria in bottleneck congestion games. Math. Program. 141(1), 193\u2013215 (2013)","journal-title":"Math. Program."},{"issue":"4","key":"1546_CR33","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1145\/96559.96597","volume":"37","author":"DS Hochbaum","year":"1990","unstructured":"Hochbaum, D.S., Shanthikumar, J.G.: Convex separable optimization is not much harder than linear optimization. J. ACM 37(4), 843\u2013862 (1990)","journal-title":"J. ACM"},{"key":"1546_CR34","unstructured":"Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., Sun, Q.: Fast and compact: a simple class of congestion games. In: Proceedings of the 20th National Conference on Artificial Intelligence, pp. 489\u2013494 (2005)"},{"key":"1546_CR35","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Proceedings of the 16th Annual Conference on Theoretical Aspects of Computer Science, pp. 404\u2013413 (1999)","DOI":"10.1007\/3-540-49116-3_38"},{"issue":"3","key":"1546_CR36","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.tcs.2008.06.045","volume":"406","author":"T L\u00fccking","year":"2008","unstructured":"L\u00fccking, T., Mavronicolas, M., Monien, B., Rode, M.: A new model for selfish routing. Theor. Comput. Sci. 406(3), 187\u2013206 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1546_CR37","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02591770","volume":"25","author":"C McDiarmid","year":"1983","unstructured":"McDiarmid, C.: Integral decomposition in polyhedra. Math. Program. 25(2), 183\u2013198 (1983)","journal-title":"Math. Program."},{"issue":"6","key":"1546_CR38","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0315059","volume":"15","author":"R Meyer","year":"1977","unstructured":"Meyer, R.: A class of nonlinear integer programs solvable by a single linear program. SIAM J. Control Optim. 15(6), 935\u2013946 (1977)","journal-title":"SIAM J. Control Optim."},{"key":"1546_CR39","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BFb0121104","volume":"26","author":"M Minoux","year":"1986","unstructured":"Minoux, M.: Solving integer minimum cost flows with separable convex cost objective polynomially. Math. Prog. Study 26, 237\u2013239 (1986)","journal-title":"Math. Prog. Study"},{"issue":"1","key":"1546_CR40","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1006\/game.1996.0044","volume":"14","author":"D Monderer","year":"1996","unstructured":"Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14(1), 124\u2013143 (1996)","journal-title":"Games Econ. Behav."},{"key":"1546_CR41","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic Game Theory","author":"N Nisan","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, New York (2007)"},{"issue":"1","key":"1546_CR42","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s10898-004-4313-z","volume":"33","author":"S Onn","year":"2005","unstructured":"Onn, S., Rothblum, U.G., Tangir, Y.: Edge-directions of standard polyhedra with applications to network flows. J. Glob. Optim. 33(1), 109\u2013122 (2005)","journal-title":"J. Glob. Optim."},{"key":"1546_CR43","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01737559","volume":"2","author":"RW Rosenthal","year":"1973","unstructured":"Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65\u201367 (1973)","journal-title":"Int. J. Game Theory"},{"issue":"2","key":"1546_CR44","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/S0022-0000(03)00044-8","volume":"67","author":"T Roughgarden","year":"2003","unstructured":"Roughgarden, T.: The price of anarchy is independent of the network topology. J. Comput. Syst. Sci. 67(2), 341\u2013364 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"1546_CR45","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/2806883","volume":"62","author":"T Roughgarden","year":"2015","unstructured":"Roughgarden, T.: Intrinsic robustness of the price of anarchy. J. ACM 62(5), 32 (2015)","journal-title":"J. ACM"},{"key":"1546_CR46","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)"},{"key":"1546_CR47","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency, vol. B, Matroids, trees, stable sets. Chapters 39\u201369. Algorithms and combinatorics. Springer (2003)"},{"key":"1546_CR48","doi-asserted-by":"crossref","unstructured":"Veinott, A.F., Dantzig, G.B.: Integral Extreme Points. Defense Technical Information Center (1968)","DOI":"10.1137\/1010063"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01546-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01546-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01546-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T02:52:37Z","timestamp":1633834357000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01546-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,11]]},"references-count":48,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1546"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01546-6","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,11]]},"assertion":[{"value":"10 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}