# Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems +
## 4 Coordination Mechanism
### Monomial Server Costs with \(d<1\)
Our algorithm is based on defining two sets of constraints:

1. \(T\)_stability_ constraints, guaranteeing that \((p^{*},\xi)\) is a SE
2. \(B\)_cost-covered_ constraints, guaranteeing that \((p^{*},\xi)\) is feasible, that is, the cost all slots in \(A\) is covered

We first define the constraints, and then show they can be fulfilled. Specifically, if they cannot, then \(p^{*}\) is not optimal. Note that, in an instance with variable slot costs, the size of the input is \(\Omega(T)\), therefore, the algorithm is polynomial in the size of the input. Consider first deviations into a slot \(t\), where \(r_{1}\leq t<t_{1}\). Since the jobs are sorted by release times, and this sorting agrees with the sorting according to finish time, the constraint for avoiding a migration into \(t\) is \(\sum_{j=1}^{x}\xi_{j}\leq c_{t}\), where \(x\) is the number of jobs for which \(t\in I(j)\). In other words, for some prefixes of \(J\), we have a constraint regarding their total payment. Consider next deviations into a slot \(t\), where \(t_{i}+1\leq t<t_{i+1}\) for \(1\leq i<B\). A coordinated deviation into \(t\) may be performed by a coalition consisting of a possibly empty set of jobs assigned on \(t_{i}\) (moving right) and a possibly empty set of jobs assigned on \(t_{i+1}\) (moving left). By the sorting, the coalition consists of a _consequent_ set of jobs. Let \(\gamma\) be the index of leftmost job for which \(t\in I(j)\). Let \(x\) be the number of jobs for which \(t\in I(j)\). The constraint for avoiding a migration into \(t\) is \(\sum_{j=\gamma}^{+x-1}\xi_{j}\leq c_{t}\). Finally, we define the constraints that avoid a coordinated deviation into a slot \(t>t_{B}\). Each of theses constraints considers the total payments of some suffix of the jobs, that is, \(\sum_{j=\gamma}^{n}\xi_{j}\leq c_{t}\) for some \(\gamma\). Fulfillment of the above _stability_-constraints prevent beneficial deviations of any coalition. The constraints bound the total payment of every potential _maximal_ coalition, and this bound clearly applies to every subset of jobs of a potential maximal coalition. In addition, for every slot \(t_{i}\) in \(A\), we define a _cost-covered_ constraint \(\sum_{j\in P(i)}\xi_{j}\geq c_{t_{i}}\). The cost-covered constraints imply that the active slots in \(p\) are paid for. Given the complete set of stability and cost-covered constraints, we turn to present an algorithm for setting the payments such that all the constraints are fulfilled. During the algorithm, for every \(1\leq i\leq B\), \(P(i)\) is updated to be the set of jobs assigned to \(t_{i}\) whose payment is not determined yet. For every slot \(t\), let \(v_{t}\) denote the updated bound on the total payment of players that are assigned to or may migrate to slot \(t\) and whose payment is not determined yet. Initially, for all \(t\), \(v_{t}=c_{t}\). Consider the first job \(j_{1}\). It only participates in stability-constraints of type \(\sum_{j=1}^{x}\xi_{j}\leq c_{t}\). Recall that \(c_{min}^{1}\) is the minimal cost of a slot for which a stability-constraint that includes \(\xi_{1}\) exists. First, set \(\xi_{1}=\min(c_{t_{1}},c_{min}^{1})\). Next, apply the fact that \(\xi_{1}\) is fixed, by updating the constraints in the following way. For every \(t\in I(j_{1})\), let \(v_{t}=c_{t}-\xi_{1}\). The stability-constraint \(\sum_{j=1}^{x}\xi_{j}\leq c_{t}\) is replaced by a constraint \(\sum_{j=2}^{x}\xi_{j}\leq v_{t}\). Note that the new constraint still refers to a consequent set of jobs. In addition, the cost-covered constraint \(\sum_{j\in P(1)}\xi_{j}=c_{t_{1}}\) is replaced by \(\sum_{j\in P(1)\setminus\{1\}}\xi_{j}\geq v_{t_{1}}\). Finally, set \(P(1)=P(1)\setminus\{1\}\). We proceed in a similar way for \(k=2,\ldots,n\). Assume \(k\in P(i)\). Note that, when job \(k\) is considered, the value of \(\xi_{j}\) is already determined for every \(j<k\); therefore, job \(k\) participates only in constraints of type \(\sum_{j=k}^{k+x-1}\xi_{j}\leq v_{t}\).