# Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems +
## 3 Monomial Cost Functions  
### Decreasing Cost Shares: \(d<1\)  
In this section, we analyze the PoA for the case when the cost function equals \(x^{d}\) with \(d<1\), for which the cost share \(c(x)/x\) is strictly decreasing. The main result of the section is the following theorem, which we prove in the two subsequent lemmas. **Theorem 1**. : _For games with \(n\) jobs and cost function \(c(x)=x^{d}\) with \(d<1\), the worst case PoA is \(\Theta(n^{(1-d)/2})\)._  
**Lemma 1**. : _Given a game with \(n\) jobs and cost function \(c(x)=x^{d}\) with \(d<1\), for any NE \(s\) and any optimal assignment \(s^{*}\) we get:_  
\[\frac{C(s)}{C(s^{*})}=O\Big{(}n^{\frac{1-d}{2}}\Big{)}.\]  
Proof. : Consider an optimal assignment \(s^{*}\) and focus on a slot \(t\) that holds \(l_{t}(s^{*})=l_{t}\) jobs in \(s^{*}\). We write \(J(t)\) for the set including these \(l_{t}\) jobs. The jobs in \(J(t)\) have a cost of \(c(l_{t})\) in \(s^{*}\), and we wish to bound the cost they can have in any given NE \(s\). We begin by proving the claim that, in the NE \(s\) and for any positive integer \(x\), there exist at most two slots that have \(x\) jobs and include jobs from \(J(t)\). We prove this claim by contradiction. Suppose there are at least three slots with \(x\) jobs that host jobs from \(J(t)\). Pick any such three slots and let \(t^{\prime}\) be the median. If \(t^{\prime}\geq t\), then we have at least two slots that are greater than or equal to \(t\) and hold \(x\) jobs including some from \(J(t)\), otherwise we have at least two slots that are less than or equal to \(t\) with this property. We treat the case when there are two slots that are greater than or equal to \(t\). The other case is symmetric. Call these slots \(t^{\prime}\) and \(t^{\prime\prime}\) with \(t^{\prime\prime}>t^{\prime}\). Consider some job \(j\in J(t)\) that uses \(t^{\prime\prime}\) in \(s\). The allowed interval of \(j\) includes \(t\), since it is scheduled on it in \(s^{*}\), and \(t^{\prime\prime}\), since it is scheduled on it in \(s\). Since \(t\leq t^{\prime}<t^{\prime\prime}\), it follows that \(t^{\prime}\) is also in the allowed interval for \(j\). However, we can observe that \(j\) has an incentive to deviate from \(t^{\prime\prime}\) to \(t^{\prime}\) and improve its cost from \(c(x)/x\) to \(c(x+1)/(x+1)\). This contradicts the fact that \(s\) is a NE and proves our original claim that at most two slots can have jobs from \(J(t)\) and exactly \(x\) jobs. Given the above, we return to the task of upper bounding the total payments of jobs in \(J(t)\) in \(s\). By the claim in the previous paragraph, at most \(2x\) jobs from \(J(t)\) can pay \(c(x)/x\) in \(s\). This means at most two jobs can pay the maximum \(c(1)/1\), at most four jobs the second highest \(c(2)/2\), etc. It follows that the total payments in \(s\) of the jobs in \(J(t)\) are upper bounded by:  
\[\sum_{j=1}^{h_{t}}2c(j),\]  
where \(h_{t}\) is the smallest integer such that \(h_{t}^{2}+h_{t}\geq l_{t}\). Then, the ratio of the total cost paid by the jobs in \(J(t)\) in \(s\) over the same cost in \(s^{*}\) is at most:  
\[\frac{\sum_{j=1}^{h_{t}}2c(j)}{c(l_{t})}.\]Suppose \(t\) is in fact the slot that maximizes this ratio, meaning the above expression is an upper bound on the PoA. We get:  
\[\frac{C(s)}{C(s^{*})} \leq\frac{\sum_{j=1}^{h_{t}}2c(j)}{c(l_{t})}=\frac{\sum_{j=1}^{h_{t }}2j^{d}}{l_{t}^{d}}\] \[\leq\frac{\int_{0}^{h_{t}+1}x^{d}dx}{l_{t}^{d}}\leq\frac{2(h_{t}+1 )^{1+d}}{(1+d)l_{t}^{d}}\] \[\leq\frac{2(h_{t}+1)^{1+d}}{(1+d)h_{t}^{d}(h_{t}-1)^{d}}\] \[=O\Big{(}h_{t}^{1-d}\Big{)}=O\Big{(}h_{t}^{1\frac{1-d}{2}}\Big{)} =O\Big{(}n^{\frac{1-d}{2}}\Big{)}.\]  
This completes the proof of the upper bound.