# Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems +
## 4 Coordination Mechanism
### Monomial Server Costs with \(d<1\)  
We first restrict ourselves to instances such that the optimal solution uses a single slot. Clearly, this is the case if and only if there is some slot that is included in the interval of every job in the instance. This is the case, for example, when the jobs have common release times or deadlines. Note that by the instance in Lemma 2 (or simple modifications of it for the case of a common release time or a common deadline) we get that the PoA is infinite in the original game. In the next theorem, we prove that our coordination mechanism reduces the PoA to a constant for every \(d<1\) for the instances under consideration which we call _common slot instances_. For common slot instances and \(c(x)=x^{d}\) with \(d<1\), the PoA of our coordination mechanism is \(\Theta(1)\). Proof. : For simplicity of exposition, suppose that, in a given game, we shift time so that the only slot used by the optimal solution \(s^{*}\) is slot \(0\). Let \(s\) be a NE of the game. For simplicity and without loss of generality (due to symmetry), suppose the non-negative slots have a larger or equal cost compared to the negative slots in \(s\). If the number of non-negative slots used in \(s\) is \(1\), then a bound of \(2\) on the PoA of the instance follows trivially, so we assume there are at least \(2\) non-negative slots used in the game. Let \(t\) and \(t^{\prime}\) be used slots in \(s\) such that \(0<t<t^{\prime}\). Let \(x\) be the number of jobs on \(t\) and \(y\) the number of jobs on \(t^{\prime}\). Observe that \(t\) must lie in the allowed interval of all jobs using \(t^{\prime}\) since \(0<t<t^{\prime}\) and these jobs use \(t^{\prime}\) in \(s\) and \(0\) in \(s^{*}\). This means each of these jobs has the option to move to \(t\) and pay the marginal contribution \(c(x+1)-c(x)\). In addition, note that, by Lemma 3, at least one of the jobs on \(t^{\prime}\) has to pay, in \(s\), the average cost share \(c(y)/y\). The above, combined with the equilibrium condition (2), imply:  
\[c(x+1)-c(x)\geq\frac{c(y)}{y}. \tag{4}\]  
Note that:  
\[ \begin{array}{ll}c(x+1)-c(x)&=(x+1)^{d}-x^{d}\\ &=x^{d-1}\frac{\left(1+\frac{1}{x}\right)^{d}-1}{\frac{1}{x}}\\ &\leq x^{d-1}\lim_{x\rightarrow+\infty}\frac{\left(1+\frac{1}{x}\right)^{d}-1 }{\frac{1}{x}}\\ &=dx^{d-1},\end{array}  \tag{5}\]where the inequality follows by \(d<1\). Combining (4) with (5), we get:  
\[dx^{d-1}\geq y^{d-1}\Rightarrow y\geq d^{\frac{1}{d-1}}x.\]  
This suggests that every slot \(t\) must have at least \(d^{1/(d-1)}\) (which is always larger than \(e\)) times the number of jobs as every other slot in \([0,t)\). This in turn implies that as we move from the largest slot closer and closer to 0, the number of jobs decreases by at least a factor \(d^{1/(d-1)}\). We write \(\alpha=d^{1/(d-1)}\). Then, if \(h\) is the number of jobs on the last occupied slot, we get that the cost on non-negative slots is at most:  
\[\sum_{j=0}^{+\infty}\biggl{(}\frac{h}{\alpha^{j}}\biggr{)}^{d}=h^{d}\sum_{j=0} ^{+\infty}\biggl{(}\frac{1}{\alpha^{d}}\biggr{)}^{j}=\frac{h^{d}}{1-\frac{1}{ \alpha^{d}}}=\frac{h^{d}}{1-d^{d/(1-d)}}.\]  
Recall that we assume the non-negative slots have at least as much cost as the negative ones, meaning the total cost of \(s\) is at most:  
\[C(s)\leq\frac{2h^{d}}{1-d^{d/(1-d)}}.\]  
By the fact that we have \(h\) jobs on the largest slot, there at least \(h\) jobs in the game and we get:  
\[C(s^{*})\geq h^{d}.\]  
Taking the ratio gives:  
\[\frac{C(s)}{C(s^{*})}\leq\frac{2}{1-d^{d/(1-d)}},\]  
which is a constant for every given \(d\). **Remark 2**. : _For \(c(x)=\sqrt{x}\) and for common slot instances with \(n\) jobs, our coordination mechanism reduces the PoA from \(4n^{1/4}/3\) to at most \(4\)._  
We note that for common slot instances there always exists a NE. In fact, again, we prove that any optimal solution can be a NE with the correct payment vector. **Theorem 9**.