{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:44:09Z","timestamp":1740109449577,"version":"3.37.3"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T00:00:00Z","timestamp":1566172800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T00:00:00Z","timestamp":1566172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"3TU.AMI","award":["na"],"award-info":[{"award-number":["na"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Game Theory"],"published-print":{"date-parts":[[2020,3]]},"DOI":"10.1007\/s00182-019-00693-1","type":"journal-article","created":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T17:02:43Z","timestamp":1566234163000},"page":"321-344","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The quality of equilibria for set packing and throughput scheduling games"],"prefix":"10.1007","volume":"49","author":[{"given":"Jasper","family":"de Jong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4223-2435","authenticated-orcid":false,"given":"Marc","family":"Uetz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,8,19]]},"reference":[{"key":"693_CR1","unstructured":"http:\/\/www.snappcar.de . Retrieved (2017)"},{"key":"693_CR2","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.geb.2008.03.005","volume":"65","author":"N Andelman","year":"2009","unstructured":"Andelman N, Feldman M, Mansour Y (2009) Strong price of anarchy. Games Econ Behav 65:289\u2013317","journal-title":"Games Econ Behav"},{"issue":"1","key":"693_CR3","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s10878-013-9694-9","volume":"29","author":"A Angelucci","year":"2015","unstructured":"Angelucci A, Bil\u00f2 V, Flammini M, Moscardelli L (2015) On the sequential price of anarchy of isolation games. J Comb Optim 29(1):165\u2013181","journal-title":"J Comb Optim"},{"key":"693_CR4","doi-asserted-by":"crossref","unstructured":"Anshelevich E, DasGupta A, Kleinberg J, Tardos \u00c9, Wexler T, Roughgarden T (2004) The price of stability for network design with fair cost allocation. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), pp 295\u2013304","DOI":"10.1109\/FOCS.2004.68"},{"key":"693_CR5","first-page":"287","volume-title":"Contributions to the theory of games IV, Annals of Mathematics Studies 40","author":"RJ Aumann","year":"1959","unstructured":"Aumann RJ (1959) Acceptable points in general cooperative $$n$$-person games. In: Luce RD, Tucker AW (eds) Contributions to the theory of games IV, Annals of Mathematics Studies 40. Princeton University Press, Princeton, pp 287\u2013324"},{"key":"693_CR6","doi-asserted-by":"crossref","unstructured":"Awerbuch B, Azar Y, Epstein A (2005) The price of routing unsplittable flow. In: Proceedings of the 37th STOC, pp 57\u201366","DOI":"10.1145\/1060590.1060599"},{"key":"693_CR7","doi-asserted-by":"crossref","unstructured":"Bakker V, Bosman MGC, Molderink A, Hurink JL, Smit GJM (2010). Demand side load management using a three step optimization methodology. In: Proceedings of the 1st SmartGridComm, pp 431\u2013436","DOI":"10.1109\/SMARTGRID.2010.5622082"},{"key":"693_CR8","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1137\/S0097539799354138","volume":"31","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy A, Guha S, Naor J, Schieber B (2001) Approximating the throughput of multiple machines in real-time scheduling. SIAM J Comput 31:331\u201352","journal-title":"SIAM J Comput"},{"key":"693_CR9","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/A:1009822211065","volume":"4","author":"P Berman","year":"2000","unstructured":"Berman P, DasGupta B (2000) Multi-phase algorithms for throughput maximization for real-time scheduling. J Comb Optim 4:307\u2013323","journal-title":"J Comb Optim"},{"key":"693_CR10","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/s10878-010-9300-3","volume":"22","author":"V Bil\u00f2","year":"2011","unstructured":"Bil\u00f2 V, Flammini M, Monaco G, Moscardelli L (2011) On the performances of Nash equilibria in isolation games. J Comb Optim 22:378\u2013391","journal-title":"J Comb Optim"},{"issue":"1","key":"693_CR11","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/s00224-013-9529-1","volume":"56","author":"V Bil\u00f2","year":"2015","unstructured":"Bil\u00f2 V, Flammini M, Monaco G, Moscardelli L (2015) Some anomalies of farsighted strategic behavior. Theory Comput Syst 56(1):156\u2013180","journal-title":"Theory Comput Syst"},{"key":"693_CR12","unstructured":"Brethouwer J-T (2018) The quality of equilibria in generalized market sharing games. MSc thesis, University of Twente. https:\/\/essay.utwente.nl\/76986\/"},{"key":"693_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24804-0","volume-title":"Scheduling algorithms","author":"P Brucker","year":"2004","unstructured":"Brucker P (2004) Scheduling algorithms, 4th edn. Springer, Berlin","edition":"4"},{"key":"693_CR14","doi-asserted-by":"crossref","unstructured":"Buyya R, Ranjan R, Calheiros RN (2010) Intercloud: utility-oriented federation of cloud computing environments for scaling of application services. In: Hsu CH, Yang LT, Park JH, Yeo SS (eds.), Algorithms and Architectures for Parallel Processing, Lecture Notes in Computer Science 6081, pp 13\u201331","DOI":"10.1007\/978-3-642-13119-6_2"},{"key":"693_CR15","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1006\/jagm.2000.1155","volume":"39","author":"B Chandra","year":"2001","unstructured":"Chandra B, Halld\u00f3rsson MM (2001) Greedy local improvement and weighted set packing approximation. J Algorithms 39:223\u2013240","journal-title":"J Algorithms"},{"key":"693_CR16","doi-asserted-by":"crossref","unstructured":"Christodoulou G, Koutsoupias E (2005) The price of anarchy of finite congestion games. In: Proceedings of the 37th Annual ACM Symposium on the Theory of Computing (STOC 2005), pp 67\u201373","DOI":"10.1145\/1060590.1060600"},{"key":"693_CR17","doi-asserted-by":"crossref","unstructured":"Correa JR, de\u00a0Jong J, de\u00a0Keijzer B, Uetz M (2015) The curse of sequentiality in routing games. In: Markakis E, Sch\u00e4fer G (eds.) Web and internet economics (WINE 2015), Lecture Notes in Computer Science 9470, pp 258\u2013271","DOI":"10.1007\/978-3-662-48995-6_19"},{"key":"693_CR18","doi-asserted-by":"crossref","unstructured":"de\u00a0Jong J, Uetz M (2014) The sequential price of anarchy for atomic congestion games. In: Liu T-Y, Qi Q, Ye Y (eds.) Web and Internet Economics (WINE 2014), Lecture Notes in Computer Science 8877, pp 429\u2013434","DOI":"10.1007\/978-3-319-13129-0_35"},{"key":"693_CR19","doi-asserted-by":"crossref","unstructured":"de\u00a0Jong J, Uetz M, Wombacher A (2013) Decentralized throughput scheduling. In: Spirakis PG, Serna M (eds.) Algorithms and Complexity (CIAC 2013), Lecture Notes in Computer Science 7878, pp 134\u2013145","DOI":"10.1007\/978-3-642-38233-8_12"},{"key":"693_CR20","unstructured":"Farzad B, Olver N, Vetta A (2008) A priority-based model of routing Chicago. J. Theor Comput Sci (1)"},{"key":"693_CR21","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York"},{"key":"#cr-split#-693_CR22.1","doi-asserted-by":"crossref","unstructured":"Garing M (2009) Covering games: approximation through non-cooperation. In: Leonardi S","DOI":"10.1007\/978-3-642-10841-9_18"},{"key":"#cr-split#-693_CR22.2","unstructured":"(ed) Internet and Network Economics (WINE 2009), Lecture Notes in Computer Science 5929, pp 184-195"},{"key":"693_CR23","doi-asserted-by":"crossref","unstructured":"Goemans MX, Li L, Mirrokni VS, Thottan M (2004) Market Sharing Games Applied to Content Distribution in Ad-Hoc Networks. In: Proc. 5th ACM Symp. Mobile Ad Hoc Networking and Computing (MobiHoc 2004), pp 55-66","DOI":"10.1145\/989459.989467"},{"issue":"2","key":"693_CR24","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R Graham","year":"1979","unstructured":"Graham R, Lawler E, Lenstra J, Rinnooy Kan A (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5(2):287\u2013326","journal-title":"Ann Discrete Math"},{"key":"693_CR25","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-540-77294-1_5","volume-title":"Combinatorial and algorithmic aspects of networking (CAAN 2007), Lecture Notes in Computer Science","author":"T Harks","year":"2007","unstructured":"Harks T, Vegh L (2007) Selfish routing with online demands. In: Jansen J, Pralat P (eds) Combinatorial and algorithmic aspects of networking (CAAN 2007), Lecture Notes in Computer Science. Springer, Berlin, pp 27\u201345"},{"key":"693_CR26","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s00224-009-9187-5","volume":"45","author":"T Harks","year":"2009","unstructured":"Harks T, Heinz S, Pfetsch M (2009) Competitive online multicommodity routing. Theory Comput Syst 45:533\u2013545","journal-title":"Theory Comput Syst"},{"key":"693_CR27","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1016\/j.orl.2015.08.003","volume":"43","author":"R Hassin","year":"2014","unstructured":"Hassin R, Yovel U (2014) Sequential scheduling on identical machines. Oper Res Lett 43:530\u2013533","journal-title":"Oper Res Lett"},{"key":"693_CR28","doi-asserted-by":"crossref","unstructured":"Hayrapetyan A, Tardos \u00c9, Wexler T (2006) The effect of collusion in congestion games. In: Proceedings of the 38th Annual ACM Symposium on the Theory of Computing (STOC 2006), pp 89\u201398","DOI":"10.1145\/1132516.1132529"},{"key":"693_CR29","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00037-006-0205-6","volume":"15","author":"E Hazan","year":"2006","unstructured":"Hazan E, Safra S, Schwartz O (2006) On the complexity of approximating $$k-$$set packing. Comput Complex 15:20\u201339","journal-title":"Comput Complex"},{"key":"693_CR30","volume-title":"Approximation algorithms for NP-hard problems","author":"D Hochbaum","year":"1997","unstructured":"Hochbaum D (1997) Approximating covering and packing problems. Chap. 3. In: Hochbaum D (ed) Approximation algorithms for NP-hard problems. PWS Publishing Company, Boston"},{"key":"693_CR31","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations. The IBM research symposia series","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (eds) Complexity of computer computations. The IBM research symposia series. Springer, Berlin, pp 85\u2013103"},{"key":"693_CR32","doi-asserted-by":"crossref","unstructured":"Koutsoupias E, Papadimitriou CH (2009) Worst-case equilibria. Computer Science Review, vol 3, 65\u201369. (Preliminary version in Proc. 16th STACS, 1999)","DOI":"10.1016\/j.cosrev.2009.04.003"},{"key":"693_CR33","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"JK Lenstra","year":"1977","unstructured":"Lenstra JK, Rinnooy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Ann Discrete Math 1:343\u2013362","journal-title":"Ann Discrete Math"},{"key":"693_CR34","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s001820050086","volume":"27","author":"I Milchtaich","year":"1998","unstructured":"Milchtaich I (1998) Crowding games are sequentially solvable. Int J Game Theory 27:501\u2013509","journal-title":"Int J Game Theory"},{"key":"693_CR35","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/TSG.2010.2055904","volume":"1","author":"A Molderink","year":"2010","unstructured":"Molderink A, Bakker V, Bosman MGC, Hurink JL, Smit GJM (2010) Management and control of domestic smart grid technology. IEEE Trans Smart Grid 1:109\u2013119","journal-title":"IEEE Trans Smart Grid"},{"key":"693_CR36","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","volume":"15","author":"JM Moore","year":"1968","unstructured":"Moore JM (1968) An $$n$$ job, one machine sequencing algorithm for minimizing the number of late jobs. Manag Sci 15:102\u2013109","journal-title":"Manag Sci"},{"key":"693_CR37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic game theory","author":"N Nisan","year":"2007","unstructured":"Nisan N, Roughgarden T, Tardos \u00c9, Vazirani VV (2007) Algorithmic game theory. Cambridge University Press, Cambridge"},{"key":"693_CR38","unstructured":"Olver N (2006) The price of anarchy and a priority-based model of routing (MSc thesis), McGill University, Montr\u00e9al, Canada"},{"key":"693_CR39","doi-asserted-by":"crossref","unstructured":"Paccagnan D, Chandan R, Marden JR (2018) Distributed resource allocation through utility design \u2013 Part II: Applications to submodular, supermodular and set covering problems. ArXiV paper arXiv:1807.01343v1","DOI":"10.1109\/TAC.2019.2961995"},{"key":"693_CR40","doi-asserted-by":"crossref","unstructured":"Paccagnan D, Marden JR (2018) Distributed resource allocation through utility design \u2013 Part I: Optimizing the performance certificates via the price of anarchy. ArXiV paper arXiv:1807.01333v1","DOI":"10.1109\/TAC.2019.2961995"},{"key":"693_CR41","doi-asserted-by":"crossref","unstructured":"Paes Leme R, Syrgkanis V, Tardos \u00c9 (2012) The curse of simultaneity. In: Proc. 3rd Conference on Innovations in Theoretical Computer Science (ITCS 2012), ACM, pp 60\u201367","DOI":"10.1145\/2090236.2090242"},{"key":"693_CR42","doi-asserted-by":"crossref","unstructured":"Papadimitriou CH (2001) Algorithms, games, and the internet. In: Proc. 33rd Annual ACM Symposium on the Theory of Computing (STOC 2001), pp 749\u2013753","DOI":"10.1145\/380752.380883"},{"key":"693_CR43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46950-7","volume-title":"Game theory: a multi-leveled approach","author":"H Peters","year":"2015","unstructured":"Peters H (2015) Game theory: a multi-leveled approach, 2nd edn. Springer, Berlin","edition":"2"},{"key":"693_CR44","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T Roughgarden","year":"2002","unstructured":"Roughgarden T, Tardos \u00c9 (2002) How bad is selfish routing? J ACM 49:236\u2013259","journal-title":"J ACM"},{"key":"693_CR45","first-page":"301","volume":"121","author":"R Selten","year":"1965","unstructured":"Selten R (1965) Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetr\u00e4gheit: Teil 1: Bestimmung des dynamischen Preisgleichgewichts. Zeitschrift f\u00fcr die gesamte Staatswissenschaft 121:301\u2013324","journal-title":"Zeitschrift f\u00fcr die gesamte Staatswissenschaft"},{"key":"693_CR46","doi-asserted-by":"crossref","unstructured":"Skopalik A, V\u00f6cking B (2008) Inapproximability of pure Nash equilibria. In: Proc. 40th Annual ACM Symposium on the Theory of Computing (STOC 2008), pp 355\u2013364","DOI":"10.1145\/1374376.1374428"},{"key":"693_CR47","doi-asserted-by":"crossref","unstructured":"Vetta A (2002) Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In: Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp 416\u2013425","DOI":"10.1109\/SFCS.2002.1181966"}],"container-title":["International Journal of Game Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00182-019-00693-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00182-019-00693-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00182-019-00693-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T07:18:59Z","timestamp":1695107939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00182-019-00693-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,19]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["693"],"URL":"https:\/\/doi.org\/10.1007\/s00182-019-00693-1","relation":{},"ISSN":["0020-7276","1432-1270"],"issn-type":[{"type":"print","value":"0020-7276"},{"type":"electronic","value":"1432-1270"}],"subject":[],"published":{"date-parts":[[2019,8,19]]},"assertion":[{"value":"6 August 2019","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2019","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}