{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:20:13Z","timestamp":1760239213118,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T00:00:00Z","timestamp":1602720000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We introduce multidimensional congestion games, that is, congestion games whose set of players is partitioned into d+1 clusters C0,C1,\u2026,Cd. Players in C0 have full information about all the other participants in the game, while players in Ci, for any 1\u2264i\u2264d, have full information only about the members of C0\u222aCi and are unaware of all the others. This model has at least two interesting applications: (i) it is a special case of graphical congestion games induced by an undirected social knowledge graph with independence number equal to d, and (ii) it represents scenarios in which players have a type and the level of competition they experience on a resource depends on their type and on the types of the other players using it. We focus on the case in which the cost function associated with each resource is affine and bound the price of anarchy and stability as a function of d with respect to two meaningful social cost functions and for both weighted and unweighted players. We also provide refined bounds for the special case of d=2 in presence of unweighted players.<\/jats:p>","DOI":"10.3390\/a13100261","type":"journal-article","created":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T09:02:03Z","timestamp":1602752523000},"page":"261","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On Multidimensional Congestion Games"],"prefix":"10.3390","volume":"13","author":[{"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[{"name":"Department of Mathematics and Physics \u201cEnnio De Giorgi\u201d, University of Salento-Provinciale Lecce-Arnesano, P.O. Box 193, 73100 Lecce, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michele","family":"Flammini","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute-Viale Francesco Crispi 7, 67100 L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vasco","family":"Gallotti","sequence":"additional","affiliation":[{"name":"Department of Information Engineering Computer Science and Mathematics, University of L\u2019Aquila-Via Vetoio, Loc. Coppito, 67100 L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cosimo","family":"Vinci","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute-Viale Francesco Crispi 7, 67100 L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,10,15]]},"reference":[{"key":"ref_1","unstructured":"Beckmann, M.J., McGuire, C.B., and Winsten, C.B. (1956). Studies in the Economics of Transportation, Yale University Press."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01737559","article-title":"A Class of Games Possessing Pure-Strategy Nash Equilibria","volume":"2","author":"Rosenthal","year":"1973","journal-title":"Int. J. Game Theory"},{"key":"ref_3","first-page":"325","article-title":"Road Paper. Some Theoretical Aspects of Road Traffic Research","volume":"1","author":"Wardrop","year":"1952","journal-title":"Proc. Inst. Civ. Eng."},{"key":"ref_4","first-page":"767","article-title":"Correspondence. Some Theoretical Aspects of Road Traffic Research","volume":"1","author":"Wardrop","year":"1952","journal-title":"Proc. Inst. Civ. Eng."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1073\/pnas.36.1.48","article-title":"Equilibrium points in n-person games","volume":"36","author":"Nash","year":"1950","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_6","unstructured":"Koutsoupias, E., and Papadimitriou, C. (1999, January 4\u20136). Worst-case equilibria. Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS), LNCS 1653, Trier, Germany."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1602","DOI":"10.1137\/070680096","article-title":"The Price of Stability for Network Design with Fair Cost Allocation","volume":"38","author":"Anshelevich","year":"2008","journal-title":"SIAM J. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1137\/090748986","article-title":"Exact Price of Anarchy for Polynomial Congestion Games","volume":"40","author":"Aland","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1137\/070702370","article-title":"The Price of Routing Unsplittable Flow","volume":"42","author":"Awerbuch","year":"2013","journal-title":"SIAM J. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/2629666","article-title":"Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness","volume":"2","author":"Bhawalkar","year":"2014","journal-title":"ACM Trans. Econ. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1288","DOI":"10.1007\/s00224-017-9826-1","article-title":"A Unifying Tool for Bounding the Quality of Non-Cooperative Solutions in Weighted Congestion Games","volume":"62","year":"2018","journal-title":"Theory Comput. Syst."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1007\/s00453-010-9427-8","article-title":"Tight Bounds for Selfish and Greedy Load Balancing","volume":"61","author":"Caragiannis","year":"2011","journal-title":"Algorithmica"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"10:1","DOI":"10.1145\/2841229","article-title":"Price of Stability in Polynomial Congestion Games","volume":"4","author":"Christodoulou","year":"2016","journal-title":"ACM Trans. Econ. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1544","DOI":"10.1137\/18M1207880","article-title":"The Price of Stability of Weighted Congestion Games","volume":"48","author":"Christodoulou","year":"2019","journal-title":"SIAM J. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., and Koutsoupias, E. (2005, January 22\u201324). The Price of Anarchy of Finite Congestion Games. Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), Baltimore, MD, USA.","DOI":"10.1145\/1060590.1060600"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., and Koutsoupias, E. (2005, January 3\u20136). On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games. Proceedings of the 13th Annual European Symposium on Algorithms (ESA), LNCS 3669, Palma de Mallorca, Spain.","DOI":"10.1007\/11561071_8"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/s00453-010-9449-2","article-title":"On the Performance of Approximate Equilibria in Congestion Games","volume":"61","author":"Christodoulou","year":"2011","journal-title":"Algorithmica"},{"key":"ref_18","unstructured":"Bil\u00f2, V., and Vinci, C. (2017, January 4\u20136). On the Impact of Singleton Strategies in Congestion Games. Proceedings of the 25th Annual European Symposium on Algorithms (ESA), LIPIcs, Vienna, Austria."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"32:1","DOI":"10.1145\/2806883","article-title":"Intrinsic Robustness of the Price of Anarchy","volume":"62","author":"Roughgarden","year":"2015","journal-title":"J. ACM"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1016\/j.tcs.2005.09.024","article-title":"Selfish Unsplittable Flows","volume":"348","author":"Fotakis","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1287\/moor.1120.0543","article-title":"On the Existence of Pure Nash Equilibria in Weighted Congestion Games","volume":"37","author":"Harks","year":"2012","journal-title":"Math. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/s00224-011-9315-x","article-title":"Characterizing the Existence of Potential Functions in Weighted Congestion Games","volume":"49","author":"Harks","year":"2011","journal-title":"Theory Comput. Syst."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1016\/j.tcs.2009.10.007","article-title":"When Ignorance Helps: Graphical Multicast Cost Sharing Games","volume":"411","author":"Fanelli","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/s00453-010-9417-x","article-title":"Graphical Congestion Games","volume":"61","author":"Fanelli","year":"2011","journal-title":"Algorithmica"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/s00224-011-9355-2","article-title":"The Impact of Social Ignorance on Weighted Congestion Games","volume":"50","author":"Fotakis","year":"2012","journal-title":"Theory Comput. Syst."},{"key":"ref_26","unstructured":"Bil\u00f2, V., Flammini, M., and Gallotti, V. (July, January 30). On Bidimensional Congestion Games. Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), LNCS 7355, Reykjavik, Iceland."},{"key":"ref_27","first-page":"15:1","article-title":"Dynamic Taxes for Polynomial Congestion Games","volume":"7","author":"Vinci","year":"2019","journal-title":"ACM Trans. Econ. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"13:1","DOI":"10.1145\/1868237.1868251","article-title":"Taxes for linear atomic congestion games","volume":"7","author":"Caragiannis","year":"2010","journal-title":"ACM Trans. Algorithms"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1228","DOI":"10.1007\/s00224-018-9902-1","article-title":"On Stackelberg Strategies in Affine Congestion Games","volume":"63","author":"Vinci","year":"2019","journal-title":"Theory Comput. Syst."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1007\/s00224-008-9152-8","article-title":"Stackelberg Strategies for Atomic Congestion Games","volume":"47","author":"Fotakis","year":"2010","journal-title":"Theory Comput. Syst."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.trb.2008.05.010","article-title":"Hyperstar: A Multi-path Astar Algorithm for Risk Averse Vehicle Navigation","volume":"43","author":"Bell","year":"2009","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1016\/S0191-2615(01)00022-4","article-title":"Risk-averse User Equilibrium Traffic Assignment: An Application of Game Theory","volume":"36","author":"Bell","year":"2002","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_33","unstructured":"Yekkehkhany, A., Murray, T., and Nagi, R. (2020). Road Paper. Risk-Averse Equilibrium for Games. arXiv."},{"key":"ref_34","unstructured":"Yekkehkhany, A., and Nagi, R. (2020). Risk-Averse Equilibrium for Autonomous Vehicles in Stochastic Congestion Games. arXiv."},{"key":"ref_35","unstructured":"Bil\u00f2, V., Moscardelli, L., and Vinci, C. (2018, January 9\u201313). Uniform Mixed Equilibria in Network Congestion Games with Link Failures. Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), LIPIcs 107, Prague, Czech Republic."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1508","DOI":"10.1016\/j.dam.2011.01.019","article-title":"Congestion Games with Failures","volume":"159","author":"Penn","year":"2011","journal-title":"Discret. Appl. Math."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/j.geb.2009.03.004","article-title":"Congestion Games with Load-dependent Failures: Identical Resources","volume":"67","author":"Penn","year":"2009","journal-title":"Games Econ. Behav."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/10\/261\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:21:58Z","timestamp":1760178118000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/10\/261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,15]]},"references-count":37,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2020,10]]}},"alternative-id":["a13100261"],"URL":"https:\/\/doi.org\/10.3390\/a13100261","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,10,15]]}}}