{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T09:09:06Z","timestamp":1749114546428,"version":"3.37.3"},"reference-count":23,"publisher":"EDP Sciences","issue":"2","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":11,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,1,21]]},"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:p>This article investigates the efficiency of Nash equilibria in a utilitarian scheduling game, where each job, acting as an agent, strategically selects a machine for its processing. The study focuses on a uniform parallel machine environment, employing the Weighted Shortest Processing Time rule as the local policy and the total weighted completion time as the social goal. We establish upper and lower bounds for the Price of Anarchy, offering valuable insights for this scheduling game.<\/jats:p>","DOI":"10.1051\/ro\/2024017","type":"journal-article","created":{"date-parts":[[2024,1,23]],"date-time":"2024-01-23T19:57:35Z","timestamp":1706039855000},"page":"1093-1103","source":"Crossref","is-referenced-by-count":2,"title":["Price of Anarchy in uniform parallel machines scheduling game with weighted completion time as social goal"],"prefix":"10.1051","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1213-3217","authenticated-orcid":false,"given":"Felipe T.","family":"Mu\u00f1oz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco A.","family":"Parra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,3,12]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Abed F., Correa J.R. and Huang C.-C., Optimal coordination mechanisms for multi-job scheduling games, in Algorithms-ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8\u201310, 2014. Proceedings 21. Springer Berlin Heidelberg (2014) 13\u201324.","DOI":"10.1007\/978-3-662-44777-2_2"},{"key":"R2","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1287\/opre.2015.1363","volume":"63","author":"Azar","year":"2015","journal-title":"Oper. Res"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Bhattacharya S., Im S., Kulkarni J. and Munagala K., Coordination mechanisms from (almost) all scheduling policies, in Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS). ACM, NY, USA (2014) 121\u2013134.","DOI":"10.1145\/2554797.2554811"},{"key":"R4","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1016\/j.orl.2005.08.003","volume":"34","author":"Brueggemann","year":"2006","journal-title":"Oper. Res. Lett"},{"key":"R5","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1007\/s00453-010-9427-8","volume":"61","author":"Caragiannis","year":"2011","journal-title":"Algorithmica"},{"key":"R6","doi-asserted-by":"crossref","first-page":"3327","DOI":"10.1016\/j.tcs.2009.01.005","volume":"410","author":"Christodoulou","year":"2009","journal-title":"Theor. Comput. Sci"},{"key":"R7","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.geb.2013.03.011","volume":"92","author":"Cole","year":"2015","journal-title":"Games Econ. Behav"},{"key":"R8","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1002\/nav.21497","volume":"59","author":"Correa","year":"2012","journal-title":"Nav. Res. Logist"},{"key":"R9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1186810.1186814","volume":"3","author":"Czumaj","year":"2007","journal-title":"ACM Trans. Algorithms"},{"key":"R10","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1287\/mnsc.11.2.268","volume":"11","author":"Eastman","year":"1964","journal-title":"Manage. Sci"},{"key":"R11","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"Graham","year":"1979","journal-title":"Ann. Discrete Math"},{"key":"R12","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1111\/j.1937-5956.2007.tb00271.x","volume":"16","author":"Heydenreich","year":"2007","journal-title":"Prod. Oper. Manage"},{"key":"R13","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.disopt.2018.08.001","volume":"31","author":"Hoeksma","year":"2019","journal-title":"Discrete Optim"},{"key":"R14","doi-asserted-by":"crossref","first-page":"1589","DOI":"10.1016\/j.tcs.2008.12.032","volume":"410","author":"Immorlica","year":"2009","journal-title":"Theor. Comput. Sci"},{"key":"R15","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1137\/0215081","volume":"15","author":"Kawaguchi","year":"1986","journal-title":"SIAM J. Comput"},{"key":"R16","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.cosrev.2009.04.003","volume":"3","author":"Koutsoupias","year":"2009","journal-title":"Comput. Sci. Rev"},{"key":"R17","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/j.ejor.2012.02.001","volume":"220","author":"Lee","year":"2012","journal-title":"Eur. J. Oper. Res"},{"key":"R18","doi-asserted-by":"crossref","first-page":"1079","DOI":"10.1051\/ro\/2022045","volume":"56","author":"Mu\u02dcnoz","year":"2022","journal-title":"RAIRO: Oper. Res"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Rahn M. and Sch\u00a8afer G., Bounding the inefficiency of altruism through social contribution games, in International Conference on Web and Internet Economics. Springer Berlin Heidelberg, Berlin, Heidelberg (2013) 391\u2013404.","DOI":"10.1007\/978-3-642-45046-4_32"},{"key":"R20","unstructured":"Rivera O.L., Cotas para el precio de la anarqu\u00eda de juegos de Scheduling. Undergraduate thesis, Universidad de Chile, Chile (2012). https:\/\/repositorio.uchile.cl\/handle\/2250\/111965."},{"key":"R21","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"Smith","year":"1956","journal-title":"Nav. Res. Logist. Q"},{"key":"R22","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1016\/j.ipl.2010.02.003","volume":"110","author":"Yu","year":"2010","journal-title":"Inf. Process. Lett"},{"key":"R23","doi-asserted-by":"crossref","first-page":"949","DOI":"10.1007\/s11590-018-1285-3","volume":"13","author":"Zhang","year":"2019","journal-title":"Optim. Lett"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024017\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T09:10:48Z","timestamp":1710234648000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3]]},"references-count":23,"journal-issue":{"issue":"2"},"alternative-id":["ro220520"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024017","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,3]]}}}