# Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems +
Footnote †: This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ([[https://creativecommons.org/licenses/by/cne%](https://creativecommons.org/licenses/by/cne%)]([https://creativecommons.org/licenses/by/cne%](https://creativecommons.org/licenses/by/cne%))  
depends on the number of jobs \(l_{t}\) that are to be processed in time slot \(t\). This generalized model captures many applications in cloud computing and data center optimization, and is the main focus of this work. As a concrete application, consider large computing clusters operated by large software companies, to which multiple users submit jobs for processing, paying for the use of computational resources through cost centers. Understanding the inefficiency caused due to selfish behaviour in such a system is an important goal, as well as suggesting various payment mechanisms that minimize this inefficiency. In the standard cost-sharing setting studied in [6], each of the jobs processed at time \(t\) assumes an equal share of the server cost \(c(l_{t})\) (or a proportional share for a more general setting where each job places a different load on the server). Given this rule, we would expect each job \(j\) to optimize for its individual cost share and declare the slot that minimizes the ratio of the server cost to the number of jobs (which is precisely the individual cost share) among all slots in its interval \([r_{j},d_{j})\). When this is true for every job, we have an assignment that is a _Nash equilibrium_ (NE). The inefficiency of a NE is captured by the _price of anarchy_ (PoA), which is the worst case ratio of the total cost in a NE assignment over the total cost in the optimal assignment. For the base case of unit server costs, we have \(c(0)=0\) and \(c(x)=1\) for every \(x>0\). The PoA of such games was shown by [PERSON] [6] to be \(\Theta(\sqrt{n})\) and the question of what happens when the server has a cost that depends on the load placed on it was posed as an open problem. A major part of our results focuses precisely on answering this question. We study cost functions of the form \(c(x)=x^{d}\) for some parameter \(d>0\). Note that for \(d<1\) the cost share function \(c(x)/x\) is monotonically decreasing and that for \(d>1\) it is monotonically increasing. The game we study here belongs to the class of _congestion games_[7], the PoA of which has received significant attention in the literature. Our games are equivalent to singleton congestion games with uniform resources arranged on a line and with strategy spaces that correspond to intervals on this line. We provide tight PoA bounds for the case of positive externalities (which is the best motivated case for our application of interest), i.e., \(d<1\), showing that the PoA is \(\Theta(n^{(1-d)/2})\). For \(d>1\), the upper bound for general congestion games shows the PoA does not depend on the number of jobs and is at most \(d^{\Theta(d)}\) (i.e., constant for fixed \(d\)). We observe that an early \(d^{\Theta(d)}\) lower bound instance [8] designed for routing games applies to our setting, showing that the PoA is in fact \(d^{\Theta(d)}\). Subsequently, we focus on the design of _coordination mechanisms_ for the problem in an effort to improve the PoA. A coordination mechanism [9] is a set of a priori rules the system designer can set without knowledge of the instance. A coordination mechanism can, for example, modify the cost shares of jobs, expand or restrict their strategy spaces, etc. The modified rules of the game under the coordination mechanism will change the set of NE outcomes, hopefully to the improvement of the PoA. We design a simple coordination mechanism that merely expands the strategy space of each job by asking them to declare not only a slot but also a payment. It is clear that this mechanism requires no knowledge of the specifics of the instance and is very simple to implement.