{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:49:32Z","timestamp":1787503772654,"version":"build-2736575974"},"reference-count":43,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,3,25]],"date-time":"2021-03-25T00:00:00Z","timestamp":1616630400000},"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 study cost-sharing games in real-time scheduling systems where the server\u2019s activation cost in every time slot is a function of its load. We focus on monomial cost functions and consider both the case when the degree is less than one (inducing positive congestion effect for the jobs) and when it is greater than one (inducing negative congestion effect for the jobs). For the former case, we provide tight bounds on the price of anarchy, and show that the price of anarchy grows to infinity as a polynomial of the number of jobs in the game. For the latter, we observe that existing results provide constant and tight (asymptotically in the degree of the monomial) bounds on the price of anarchy. We then turn to analyze payment mechanism with arbitrary cost-sharing, that is, when the strategy of a player includes also its payment. We show that our mechanism reduces the price of anarchy of games with n jobs and unit server costs from \u0398(n) to 2. We also show that, for a restricted class of instances, a similar improvement is achieved for monomial server costs. This is not the case, however, for unrestricted instances of monomial costs, for which we prove that the price of anarchy remains super-constant for our mechanism. For systems with load-independent activation costs, we show that our mechanism can produce an optimal solution which is stable against coordinated deviations.<\/jats:p>","DOI":"10.3390\/a14040103","type":"journal-article","created":{"date-parts":[[2021,3,25]],"date-time":"2021-03-25T02:54:03Z","timestamp":1616640843000},"page":"103","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems"],"prefix":"10.3390","volume":"14","author":[{"given":"Eirini","family":"Georgoulaki","sequence":"first","affiliation":[{"name":"National and Kapodistrian University of Athens, 157 72 Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kostas","family":"Kollias","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, CA 94042, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tami","family":"Tamir","sequence":"additional","affiliation":[{"name":"The Interdisicplinary Center, Herzliya 46150, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,3,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/1735223.1735245","article-title":"Energy-efficient algorithms","volume":"53","author":"Albers","year":"2010","journal-title":"Commun. ACM"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1137\/S0097539799354138","article-title":"Approximating the Throughput of Multiple Machines in Real-Time Scheduling","volume":"31","author":"Guha","year":"2001","journal-title":"SIAM J. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/s00453-013-9807-y","article-title":"A Model for Minimizing Active Processor Time","volume":"70","author":"Chang","year":"2014","journal-title":"Algorithmica"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/1067309.1067324","article-title":"Algorithmic problems in power management","volume":"36","author":"Irani","year":"2005","journal-title":"SIGACT News"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/s10951-014-0411-z","article-title":"Real-time scheduling to minimize machine busy times","volume":"18","author":"Khandekar","year":"2015","journal-title":"J. Sched."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Tamir, T. (2018, January 15\u201317). Cost-Sharing Games in Real-Time Scheduling Systems. Proceedings of the Web and Internet Economics\u201414th International Conference, WINE 2018, Oxford, UK.","DOI":"10.1007\/978-3-030-04612-5_28"},{"key":"ref_7","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_8","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., and Epstein, A. (2005, January 22\u201324). The price of routing unsplittable flow. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA.","DOI":"10.1145\/1060590.1060599"},{"key":"ref_9","unstructured":"Christodoulou, G., Koutsoupias, E., and Nanavati, A. (2004, January 12\u201316). Coordination Mechanisms. Proceedings of the Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland."},{"key":"ref_10","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_11","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.cosrev.2009.04.003","article-title":"Worst-case equilibria","volume":"3","author":"Koutsoupias","year":"2009","journal-title":"Comput. Sci. Rev."},{"key":"ref_12","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_13","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, Baltimore, MD, USA.","DOI":"10.1145\/1060590.1060600"},{"key":"ref_14","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_15","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/2629666","article-title":"Weighted Congestion Games: The Price of Anarchy, Universal Worst-Case Examples, and Tightness","volume":"2","author":"Bhawalkar","year":"2014","journal-title":"ACM Trans. Econ. Comput."},{"key":"ref_16","unstructured":"Goemans, M.X., Mirrokni, V.S., and Vetta, A. (2005, January 23\u201325). Sink Equilibria and Convergence. Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), Pittsburgh, PA, USA."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"21:1","DOI":"10.1145\/2781678","article-title":"Restoring Pure Equilibria to Weighted Congestion Games","volume":"3","author":"Kollias","year":"2015","journal-title":"ACM Trans. Econ. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1252","DOI":"10.1287\/moor.2014.0651","article-title":"Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games","volume":"39","author":"Gopalakrishnan","year":"2014","journal-title":"Math. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Gairing, M., Kollias, K., and Kotsialou, G. (2015, January 6\u201310). Tight Bounds for Cost-Sharing in Weighted Congestion Games. Proceedings of the Automata, Languages, and Programming\u201442nd International Colloquium, ICALP 2015, Kyoto, Japan. Part II.","DOI":"10.1007\/978-3-662-47666-6_50"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1230","DOI":"10.1287\/opre.2016.1512","article-title":"Optimal Cost-Sharing in General Resource Selection Games","volume":"64","author":"Gkatzelis","year":"2016","journal-title":"Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Klimm, M., and Schmand, D. (2015, January 20\u201322). Sharing Non-anonymous Costs of Multiple Resources Optimally. Proceedings of the Algorithms and Complexity\u20149th International Conference, CIAC 2015, Paris, France.","DOI":"10.1007\/978-3-319-18173-8_20"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Marden, J.R., and Philips, M. (2017, January 24\u201326). Optimizing the price of anarchy in concave cost sharing games. Proceedings of the 2017 American Control Conference, ACC 2017, Seattle, WA, USA.","DOI":"10.23919\/ACC.2017.7963768"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1287\/opre.1120.1137","article-title":"Distributed Welfare Games","volume":"61","author":"Marden","year":"2013","journal-title":"Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"8:1","DOI":"10.1145\/2841228","article-title":"Network Cost-Sharing without Anonymity","volume":"4","author":"Roughgarden","year":"2016","journal-title":"ACM Trans. Econ. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1799","DOI":"10.1137\/08072721X","article-title":"Designing Network Protocols for Good Equilibria","volume":"39","author":"Chen","year":"2010","journal-title":"SIAM J. Comput."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1287\/moor.1120.0567","article-title":"Optimal Cost Sharing for Resource Selection Games","volume":"38","author":"Harks","year":"2013","journal-title":"Math. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1287\/opre.2015.1363","article-title":"Optimal Coordination Mechanisms for Unrelated Machine Scheduling","volume":"63","author":"Azar","year":"2015","journal-title":"Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1007\/s00453-012-9650-6","article-title":"Efficient Coordination Mechanisms for Unrelated Machine Scheduling","volume":"66","author":"Caragiannis","year":"2013","journal-title":"Algorithmica"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.geb.2013.03.011","article-title":"Decentralized utilitarian mechanisms for scheduling games","volume":"92","author":"Cole","year":"2015","journal-title":"Games Econ. Behav."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1589","DOI":"10.1016\/j.tcs.2008.12.032","article-title":"Coordination mechanisms for selfish scheduling","volume":"410","author":"Immorlica","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"77","DOI":"10.4086\/toc.2008.v004a004","article-title":"Near-Optimal Network Design with Selfish Agents","volume":"4","author":"Anshelevich","year":"2008","journal-title":"Theory Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.geb.2008.07.002","article-title":"Strong equilibrium in cost sharing connection games","volume":"67","author":"Epstein","year":"2009","journal-title":"Games Econ. Behav."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"5298","DOI":"10.1016\/j.tcs.2011.05.049","article-title":"Exact and approximate equilibria for optimal group network formation","volume":"412","author":"Anshelevich","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/s00224-011-9317-8","article-title":"Price of Stability in Survivable Network Design","volume":"49","author":"Anshelevich","year":"2011","journal-title":"Theory Comput. Syst."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1137\/090752699","article-title":"Terminal Backup, 3D Matching, and Covering Cubic Graphs","volume":"40","author":"Anshelevich","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1855","DOI":"10.1016\/j.tcs.2010.02.005","article-title":"Non-cooperative facility location and covering games","volume":"411","author":"Cardinal","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1007\/s00453-007-9014-9","article-title":"Non-Cooperative Tree Creation","volume":"53","author":"Hoefer","year":"2009","journal-title":"Algorithmica"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s00182-011-0312-8","article-title":"Strategic cooperation in cost sharing games","volume":"42","author":"Hoefer","year":"2013","journal-title":"Int. J. Game Theory"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Georgoulaki, E., Kollias, K., and Tamir, T. (2020, January 16\u201318). Equilibrium Inefficiency in Resource Buying Games with Load-Dependent Costs. Proceedings of the Algorithmic Game Theory\u201413th International Symposium, SAGT 2020, Augsburg, Germany.","DOI":"10.1007\/978-3-030-57980-7_6"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Aumann, R. (1959). Acceptable Points in General Cooperative n-Person Games. Contributions to the Theory of Games, Princeton University Press.","DOI":"10.1515\/9781400882168-018"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.geb.2008.03.005","article-title":"Strong price of anarchy","volume":"65","author":"Andelman","year":"2009","journal-title":"Games Econ. Behav."},{"key":"ref_42","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_43","doi-asserted-by":"crossref","unstructured":"Suri, S., T\u00f3th, C.D., and Zhou, Y. (2004, January 27\u201330). Selfish Load Balancing and Atomic Congestion Games. Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA\u201904, Barcelona, Spain.","DOI":"10.1145\/1007912.1007941"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/103\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:40:45Z","timestamp":1760161245000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,25]]},"references-count":43,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,4]]}},"alternative-id":["a14040103"],"URL":"https:\/\/doi.org\/10.3390\/a14040103","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,25]]}}}