# Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems +
## 4 Coordination Mechanism
### Unit Server Costs  
Lemma 4: _Let \((s,\xi)\) be a NE of our coordination mechanism in a game with unit server costs. Then, for every job \(j\), either \(\xi_{j}=0\) or every slot in \([r_{j},d_{j})\setminus s_{j}\) is unoccupied._  
Proof: Suppose \(\xi_{j}>0\). Then, by (2), we get that for any slot \(t\in[r_{j},d_{j})\setminus\{s_{j}\}\):  
\[1-\sum_{\vec{f}^{\prime}:s_{j}^{\prime}=t}\xi_{\vec{f}^{\prime}}\geq\xi_{j}>0. \tag{3}\]However, by Lemma 3, we know that either \(t\) is unoccupied or \(\sum_{j^{\prime}:s_{j^{\prime}}=t}\xi_{j^{\prime}}=1\). From this, and given (3), we get that \(t\) is unoccupied. The PoA of our coordination mechanism for unit server costs is 2. Proof. : Focus on a slot \(t\) and the set of jobs \(J(t)\) that use it in a given optimal assignment. The total cost paid by these jobs in the optimal assignment is 1. We show that the same set of jobs pay at most 2 in any NE \((s,\xi)\). We examine two cases. The first is the case when slot \(t\) is open in \((s,\xi)\). The jobs from \(J(t)\) that use \(t\) in \((s,\xi)\) pay at most 1, as given by Lemma 3 (they might be paying less than 1 as \(t\) might have additional jobs outside \(J(t)\)). The jobs in \(J(t)\) that use other slots pay 0, as given by Lemma 4 and the fact that all of these jobs have an occupied slot in their windows other than the one they are using, namely, slot \(t\). This proves that, in this case, the total payments of jobs in \(J(t)\) are at most 1. We now focus on the case when slot \(t\) is not open in \((s,\xi)\). We first show that the jobs from \(J(t)\) that are using slots larger than \(t\) are paying a total of at most 1. Focus on the smallest such slot \(t^{\prime}\). By the fact that, \((s,\xi)\) is a NE and using Lemma 3 we get that the total payments on \(t^{\prime}\) are 1. Now focus on any slot \(t^{\prime\prime}>t^{\prime}\) and any job \(j\in J(t)\) that uses \(t^{\prime\prime}\). Slot \(t^{\prime}\) must be in the window of job \(j\) as both \(t^{\prime\prime}\) and \(t\) satisfy this property and \(t^{\prime}\) lies between them. Then, by Lemma 4 we get that \(\xi_{j}=0\). This proves that the total payment over all jobs \(j\) that use slots larger than \(t\) is 1. The proof is symmetric for slots smaller than \(t\), which shows that for every slot \(t\) in an optimal solution and for the jobs \(J(t)\) using it, the total payment of the jobs \(J(t)\) in a NE is at most 2. This directly implies an upper bound of 2 for the PoA. The above analysis is tight, as demonstrated in the following game: There exist two jobs \(j_{1},j_{2}\). Job \(j_{1}\) can be scheduled at slots 1 or 2, whereas job \(j_{2}\) can be scheduled at slots 2 or 3. Assigning job \(j_{1}\) to slot 1, job \(j_{2}\) to slot 3, and setting \(\xi_{1}=\xi_{2}=1\) gives rise to a NE with total cost 2. It is easy to verify that this is a NE as each job has only one alternative slot, slot 2, where again they would have to pay a unit cost. The optimal assignment places both jobs in slot 2 for total cost 1, thus, the PoA is 2. We now present a simple algorithm for computing an optimal assignment \(p^{*}\) and determining payments \(\xi\) such that \((p^{*},\xi)\) is a strong Nash equilibrium (SE). Algorithm 1 produces a SE profile. ```
1: Sort the jobs such that \(d_{1}\leq d_{2}\leq\dots\leq d_{k}\)
2:while there are unassigned jobs do
3: Let \(j\) be the next unassigned job. Activate slot \(d_{j}\) and assign every job \(k\) such that \(d_{j}\subseteq I(k)\) in slot \(d_{j}\). 4: Let \(\xi_{j}=1\) and \(\xi_{k}=0\) for every job \(k\
eq j\) assigned in step 3. 5: Remove the assigned jobs from the instance. 6:endwhile
```  
**Algorithm 1** Optimal Coordination Mechanism algorithm for unit-cost  
Proof. : The only players with positive payment are those assigned in their due-date slot. Let \(j_{1},j_{2}\) be two jobs such that \(\xi_{j_{1}}>0\) and \(\xi_{j_{2}}>0\). Assume without loss of generality that \(d_{j_{1}}<d_{j_{2}}\).