{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T05:48:08Z","timestamp":1743054488959,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031710322"},{"type":"electronic","value":"9783031710339"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-71033-9_20","type":"book-chapter","created":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T00:02:17Z","timestamp":1725321737000},"page":"353-370","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Price of\u00a0Anarchy in\u00a0Paving Matroid Congestion Games"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3356-6444","authenticated-orcid":false,"given":"Bainian","family":"Hao","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4717-816X","authenticated-orcid":false,"given":"Carla","family":"Michini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,31]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","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)","DOI":"10.1145\/1455248.1455249"},{"key":"20_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/11672142_17","volume-title":"STACS 2006","author":"S Aland","year":"2006","unstructured":"Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price of anarchy for polynomial congestion games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 218\u2013229. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11672142_17"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 295\u2013304 (2004)","DOI":"10.1109\/FOCS.2004.68"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 57\u201366. Association for Computing Machinery, New York (2005)","DOI":"10.1145\/1060590.1060599"},{"issue":"1","key":"20_CR5","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1137\/070702370","volume":"42","author":"B Awerbuch","year":"2013","unstructured":"Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. SIAM J. Comput. 42(1), 160\u2013177 (2013)","journal-title":"SIAM J. Comput."},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-15781-3_2","volume-title":"Algorithms \u2013 ESA 2010","author":"K Bhawalkar","year":"2010","unstructured":"Bhawalkar, K., Gairing, M., Roughgarden, T.: Weighted congestion games: price of anarchy, universal worst-case examples, and tightness. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol. 6347, pp. 17\u201328. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15781-3_2"},{"key":"20_CR7","unstructured":"Bil\u00f2, V., Vinci, C.: On the impact of singleton strategies in congestion games. In: Pruhs, K., Sohler, C. (eds.) 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol. 87, pp. 17:1\u201317:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl (2017)"},{"issue":"121","key":"20_CR8","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1090\/S0025-5718-1973-0419270-0","volume":"27","author":"JE Blackburn","year":"1973","unstructured":"Blackburn, J.E., Crapo, H.H., Higgs, D.A.: A catalogue of combinatorial geometries. Math. Comput. 27(121), 155-s95 (1973)","journal-title":"Math. Comput."},{"issue":"2","key":"20_CR9","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1017\/S000497270004140X","volume":"1","author":"RA Brualdi","year":"1969","unstructured":"Brualdi, R.A.: Comments on bases in dependence structures. Bull. Aust. Math. Soc. 1(2), 161\u2013167 (1969)","journal-title":"Bull. Aust. Math. Soc."},{"key":"20_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/11786986_28","volume-title":"Automata, Languages and Programming","author":"I Caragiannis","year":"2006","unstructured":"Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 311\u2013322. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11786986_28"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 67\u201373. Association for Computing Machinery, New York (2005)","DOI":"10.1145\/1060590.1060600"},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-319-89441-6_23","volume-title":"Approximation and Online Algorithms","author":"J de Jong","year":"2018","unstructured":"de Jong, J., Kern, W., Steenhuisen, B., Uetz, M.: The asymptotic price of anarchy for k-uniform congestion games. In: Solis-Oba, R., Fleischer, R. (eds.) WAOA 2017. LNCS, vol. 10787, pp. 317\u2013328. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-89441-6_23"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Del\u00a0Pia, A., Ferris, M., Michini, C.: Totally unimodular congestion games. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 577\u2013588. SIAM (2017)","DOI":"10.1137\/1.9781611974782.37"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure Nash equilibria. In: Proceedings of STOC 2004 (2004)","DOI":"10.1145\/1007352.1007445"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Fokkema, W.: The price of anarchy for matroid congestion games. In: ICALP 2023, Workshop on Congestion Games (2023)","DOI":"10.1007\/978-3-031-71033-9_21"},{"key":"20_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-540-79309-0_5","volume-title":"Algorithmic Game Theory","author":"D Fotakis","year":"2008","unstructured":"Fotakis, D.: Congestion games with linearly independent paths: convergence time and price of anarchy. In: Monien, B., Schroeder, U.-P. (eds.) SAGT 2008. LNCS, vol. 4997, pp. 33\u201345. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-79309-0_5"},{"key":"20_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-031-22832-2_1","volume-title":"Web and Internet Economics","author":"B Hao","year":"2022","unstructured":"Hao, B., Michini, C.: Inefficiency of pure nash equilibria in series-parallel network congestion games. In: Hansen, K.A., Liu, T.X., Malekian, A. (eds.) WINE 2022. LNCS, vol. 13778, pp. 3\u201320. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-22832-2_1"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Hao, B., Michini, C.: The price of anarchy in series-parallel network congestion games. Math. Program. 1\u201331 (2022)","DOI":"10.1007\/s10107-022-01803-w"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Hao, B., Michini, C.: Price of anarchy in paving matroid congestion games. Optimization (2024)","DOI":"10.1007\/978-3-031-71033-9_20"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Kleer, P., Sch\u00e4fer, G.: Potential function minimizers of combinatorial congestion games: efficiency and computation. In: Proceedings of the 2017 ACM Conference on Economics and Computation, EC 2017, pp. 223\u2013240. Association for Computing Machinery, New York (2017)","DOI":"10.1145\/3033274.3085149"},{"key":"20_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/3-540-49116-3_38","volume-title":"STACS 99","author":"E Koutsoupias","year":"1999","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404\u2013413. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-49116-3_38"},{"key":"20_CR22","unstructured":"Kraakman, Y.: The price of anarchy of symmetric and semi-symmetric uniform congestion games (2021)"},{"key":"20_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1007\/978-3-540-24749-4_48","volume-title":"STACS 2004","author":"T L\u00fccking","year":"2004","unstructured":"L\u00fccking, T., Mavronicolas, M., Monien, B., Rode, M.: A New Model for Selfish Routing. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 547\u2013558. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24749-4_48"},{"issue":"3","key":"20_CR24","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). Algorithmic Aspects of Global Computing","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"20_CR25","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1016\/j.ejc.2011.01.016","volume":"32","author":"D Mayhew","year":"2011","unstructured":"Mayhew, D., Newman, M., Welsh, D., Whittle, G.: On the asymptotic proportion of connected matroids. Eur. J. Combin. 32(6), 882\u2013890 (2011). Matroids, Polynomials and Enumeration","journal-title":"Eur. J. Combin."},{"issue":"2","key":"20_CR26","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/j.jctb.2007.07.005","volume":"98","author":"D Mayhew","year":"2008","unstructured":"Mayhew, D., Royle, G.F.: Matroids with nine elements. J. Combin. Theory Ser. B 98(2), 415\u2013431 (2008)","journal-title":"J. Combin. Theory Ser. B"},{"key":"20_CR27","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001","volume-title":"Matroid Theory","author":"J Oxley","year":"2011","unstructured":"Oxley, J.: Matroid Theory. Oxford University Press, Oxford (2011)"},{"key":"20_CR28","doi-asserted-by":"crossref","unstructured":"Pendavingh, R., van der Pol, J.: On the number of matroids compared to the number of sparse paving matroids. Electron. J. Combin. 22(2) (2015)","DOI":"10.37236\/4899"},{"key":"20_CR29","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. Internat. J. Game Theory 2, 65\u201367 (1973)","journal-title":"Internat. J. Game Theory"},{"issue":"2","key":"20_CR30","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). Special Issue on STOC 2002","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"20_CR31","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T Roughgarden","year":"2002","unstructured":"Roughgarden, T., Tardos, E.: How bad is selfish routing? J. ACM 49(2), 236\u2013259 (2002)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-71033-9_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T17:54:01Z","timestamp":1732730041000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-71033-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031710322","9783031710339"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-71033-9_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"31 August 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"SAGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmic Game Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Amsterdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sagt2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cwi.nl\/en\/groups\/networks-and-optimization\/events\/sagt-2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}