# Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems +
## 4 Coordination Mechanism
### Monomial Server Costs with \(d<1\)
Let \(v_{min}^{k}\) be the minimal bound on a slot for which a constraint that includes \(\xi_{k}\) exists. Set \(\xi_{k}=\min(v_{t_{i}},v_{min}^{k})\). Next, we apply the fact that \(\xi_{k}\) is fixed by updating the constraints in the following way: For every \(t\in I(k)\), let \(v_{t}=v_{t}-\xi_{k}\). The stability-constraint \(\sum_{j=k}^{x+k-1}\xi_{j}\leq v_{t}\) is replaced by a constraint \(\sum_{j=k+1}^{x+k-1}\xi_{j}\leq v_{t}-\xi_{k}\). Note that the new constraint still refers to a consequent set of jobs. In addition, the cost-covered constraint of slot \(t_{i}\) is replaced by \(\sum_{j\in P(i)\setminus\{k\}}\xi_{j}\geq v_{t}\). Finally, set \(P(i)=P(i)\setminus\{k\}\). The process fails if, for some \(i\), after all jobs in \(P(i)\) are considered, the cost-covered constraint of slot \(t_{i}\) is not fulfilled. that is, \(v_{t_{i}}>0\). We show that in this case \(p^{*}\) is not optimal. Assume by contradiction that \(t_{i}\) is a slot whose cost is not covered. For every \(k\in P(i)\), the value of \(\xi_{k}\) was determined such that some stability-constraint it tight. Specifically, if \(\xi_{k}=v_{min}^{k}\), then job \(k\), possibly together with jobs preceding it, covers the cost of the slot corresponding to \(v_{min}^{k}\). Thus, the jobs currently on \(t_{i}\) can be reassigned on slots whose total cost can be fully covered by jobs in \(P(i-1)\cup P(i)\), and is less than \(c_{t_{i}}\). This is a contradiction to the optimality of \(p^{*}\). Thus, the cost-covered constraint for all the active slots in \(A\) are fulfilled, implying that \((p^{*},\xi)\) is feasible. Since all the stability constraints that correspond to preventing all possible coordinated deviations are fulfilled, \((p^{*},\xi)\) is a SE. We conclude that, given a social optimum schedule \(p^{*}\), it is possible to determine payments such that \((p^{*},\xi)\) is a SE. Recall that Theorem 3.1 states that SPoA = 1 for every game with fixed activation costs. Algorithm 1 implies that an optimal solution that is stable against coordinated deviations not only exists, but can also be computed efficiently. ## 5 Conclusions and Open Problems

In this work, we tackle the problem of load-dependent server costs in real-time scheduling systems, a question that was posed as an open problem by [PERSON] [6]. We precisely characterize the price of anarchy for monomial cost functions. Furthermore, we come up with a novel coordination mechanism that achieved a spectacular improvement of the price of anarchy in the original model of unit server costs and in a restricted subclass of instances in our extended model. There are several follow-up questions that emerge from our work. These include extending our results to wider classes of cost functions and settling the PoA gap between the constant bounds for \(d>1\). Most importantly, it is interesting to see whether coordination mechanisms of the type that we define here can yield similar improvements in other settings. Our mechanism relies on the simple idea of offloading the cost sharing aspect of the problem to the jobs themselves. This induces a setting where any deviation is charged the marginal contribution of the job on the new slot. Variants of the mechanism that impose, e.g., upper bounds on the cost share of a job/player might prove useful in these endeavors (for instance, such a modification would break the bad example in Lemma 11). Another direction for future work is to study games with variable-length jobs, in which every job is associated with a processing time \(p_{j}\) and should select its processing interval \([t_{j,1},t_{j,2})\subseteq[r_{j},d_{j})\) such that \(t_{j,2}-t_{j,1}=p_{j}\). The cost of processing a job is the total cost of its process. The resulting game is no longer a singleton game but is more structured than arbitrary congestion games. Conceptualization, E.G., K.K. and T.T. ; Formal analysis, E.G., K.K. and T.T. ; Writing--original draft, E.G., K.K. and T.T. All authors have read and agreed to the published version of the manuscript.