# Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems +
## 4 Coordination Mechanism
### Monomial Server Costs with \(d<1\)
We get:

\[C(s)=n^{d}\left(n^{1-d}\right)^{d}=\Theta\Big{(}n^{2d-d^{2}}\Big{)}.\]

Taking the ratio \(C(s)/C(s^{*})\) completes the proof. ### Variable Load-Independent Slot Costs

In this section, we consider mechanisms for instances in which different slots may have different costs. Denote by \(c_{t}\) the cost of slot \(t\). Note that this cost is fixed and independent of the load on \(t\). Our main result is an algorithm that determines an assignment as well as payments for the players such that the resulting profile is a strong NE. **Theorem 12**. : _For arbitrary fixed activation costs, for any instance, it is possible to calculate a schedule \(p^{*}\) and vector of payments \(\xi\) such that \((p^{*},\xi)\) is a SE, and \(cost(p^{*})=cost(OPT)\)._

Proof. : We first remove from the instance jobs whose interval includes an interval of another job. Note that, if \(I(j_{2})\subseteq I(j_{1})\), then \(j_{1}\) can be temporarily removed from the instance. Once \((p^{*},\xi)\) are finalized, we set \(\xi_{j_{1}}=0\), and assign \(j_{1}\) on the same slot as \(j_{2}\). If \(I(j_{2})=I(j_{1})\), then one of the jobs is removed (with an arbitrary tie-breaking rule). Following the above preprocessing, the jobs in \(J\) can be sorted such that \(r_{1}\leq\dots\leq r_{n}\) and \(d_{1}\leq\dots\leq d_{n}\). An optimal solution, \(p^{*}\), can be computed for such instances using dynamic programming [6]. Given \(p^{*}\), we show how to split the activation costs among the jobs such that \((p^{*},\xi)\) is a SE. For a job \(j\), let \(c^{j}_{min}=min_{t\in\{r_{1}+1,\dots,d_{j}\}}c_{t}\) denote the cost of a cheapest slot in \(I(j)\). We turn to describe the players' payments. Let \(A=\{t_{1}<t_{2}<\dots<t_{B}\}\) be the set of active slots in \(p^{*}\). For every \(1\leq i\leq B\), let \(P(i)\) denote the set of jobs such that \(j\in P(i)\) if and only if \(A\cap I(j)=t_{i}\). That is, slot \(t_{i}\) is the only active slot in \(j\)'s interval. Since \(A\) is an optimal solution, \(P(i)\) is not empty, as, otherwise, \(t_{i}\) can be removed from \(A\), contradicting its optimality. The jobs in \(P(i)\) are going to pay for \(t_{i}\). For simplicity, we first describe an algorithm to determine payments such that the resulting profile is a NE. Then, we present an algorithm for SE. **Lemma 5**. : _It is possible to determine payments \(\xi\), such that \((p^{*},\xi)\) is a NE._

Proof. : For every \(j\in P(i)\), none of the other slots in \(A\) is feasible for \(j\). Thus, as long as its payment is at most \(c^{j}_{min}\), job \(j\) would not deviate from \(t_{i}\). By the optimality of \(p^{*}\), we have that \(c_{t_{i}}\leq\sum_{j\in P(i)}c^{j}_{min}\). Thus, it is possible to determine payments \(\xi_{j}\leq c^{j}_{min}\) and \(\sum_{j\in P(i)}\xi_{j}=c_{t_{i}}\). We turn to show how it is possible to split the activation cost of slot \(t_{i}\) among the jobs in \(P(i)\) such that the resulting profile is a SE. **Lemma 6**. : _It is possible to determine payments \(\xi\), such that \((p^{*},\xi)\) is a SE._

Proof. : We first set \(\xi_{j}=0\) for every job \(j\in J\setminus\cup_{i}P(i)\). For simplicity, we remove all these jobs from the input, and only consider the paying jobs--that are in \(\cup_{i}P(i)\). For every \(j\in P(i)\), no slot in \(A\setminus\{t_{j}\}\) is feasible for \(j\), therefore, \(j\in P(i)\) may deviate only to a slot \(t\) such that \(t_{i-1}+1\leq t\leq t_{i+1}-1\). By the preprocessing (removal of jobs whose interval includes an interval of another job), the sorting of the jobs in \(\cup_{i}P(i)\) according to their release times agrees also with their sorting according to finish times. In order for \(\xi\) to be a SE, for every potential deviation of a coalition \(\Gamma\), we bound the total payments of \(\Gamma^{\prime}s\) members. Specifically, the total payment of players that can potentially migrate to a slot \(t\) must be less than \(c_{t}\), as, otherwise, these players can form a coalition and split the payment for activating \(t\) in a way that all of them benefit.