# Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems +
## 4 Coordination Mechanism  
In this section, we design a coordination mechanism that applies a simple modification to the game, without knowing anything about the instance, and significantly improves the PoA. For the case of constant (unit) costs, we show that the PoA is brought down to 2. For \(c(x)=x^{d}\) with \(d<1\), we prove that the PoA is improved from super-constant to constant for the class of instances which have a single slot occupied in the optimal solution. This class includes instances with a common release time or a common deadline for all jobs, as well as instances with a batch of jobs centered around a common slot. We prove that, without this restriction, the PoA for \(c(x)=x^{d}\) with \(d<1\) remains super-constant even under our mechanism. Note that for \(d>1\) the PoA is known to be constant even without applying any coordination mechanism.  
Our mechanism changes the strategy space of each job \(j\), from being simply a slot \(s_{j}\in[r_{j},d_{j})\), to a pair \((s_{j},\xi_{j})\) where \(s_{j}\in[r_{j},d_{j})\) is again the declared slot and \(\xi_{j}\geq 0\) is a payment. The mechanism will open slot \(t\) under strategies \((s,\xi)\) if and only if:  
\[\sum_{j:s_{j}=t}\xi_{j}\geq c(l_{t}(s)),\]  
i.e., if the jobs selecting slot \(s\) cover the server cost with their declared payments. We assume every job \(j\) has an infinite cost for not being processed (i.e., when slot \(s_{j}\) is not opened), an assumption that is implicitly present in the base model as well, since jobs do not have the option of staying out of the game. In this framework, the NE condition asserts that each \((s_{j},\xi_{j})\) are such that:  
\[\sum_{\vec{f}^{\prime}:s_{j}=s_{j}}\xi_{\vec{f}^{\prime}}\geq c(l_{s_{j}}(s))\]  
\[\text{and }\xi_{j}\leq\max\left\{0,c(l_{t}(s)+1)-\sum_{\vec{f}^{\prime}:s_{j}=t} \xi_{\vec{f}^{\prime}}\right\},\forall t\in[r_{j},d_{j})\setminus\{s_{j}\} \tag{1}\]  
\[\text{and }\xi_{j}\leq\max\left\{0,c(l_{s_{j}}(s))-\sum_{\vec{f}^{\prime}:s_{j}=s_ {j}\vec{f}^{\prime}\
eq j}\xi_{\vec{f}^{\prime}}\right\}.\]  
The first inequality guarantees slot \(s_{j}\) is open, the second that there is no slot \(t\) that job \(j\) can move to, pay the minimum needed to open it (or keep it open), and get a lower payment, and the third that the job should pay as much as necessary to keep its current slot open.  
Lemma 3: _Every NE \((s,\xi)\) of our coordination mechanism is such that for every occupied slot \(t\) we have \(\sum_{j:s_{j}=t}\xi_{j}=c(l_{t}(s))\)._  
Proof: Suppose this is not the case. Then, there exists some \(t\) such that:  
\[\sum_{j:s_{j}=t}\xi_{j}>c(l_{t}(s)).\]  
Consider any job \(j\) such that \(s_{j}=t\) and \(\xi_{j}>0\). Clearly, such a job must exist. We get:  
\[\sum_{\vec{f}^{\prime}:s_{j}=s_{j}}\xi_{\vec{f}^{\prime}}>c(l_{s_{j}}(s))\Rightarrow \xi_{j}>c(l_{s_{j}}(s))-\sum_{\vec{f}^{\prime}:s_{j}=s_{j}\vec{f}^{\prime} \
eq j}\xi_{\vec{f}},\]  
which violates (1) and gives a contradiction.  
Using Lemma 3, we may simplify the NE condition (1) as:  
\[\sum_{\vec{f}^{\prime}:s_{j}=s_{j}}\xi_{\vec{f}^{\prime}}=c(l_{s_{j}}(s))\text { and }\xi_{j}\leq c(l_{t}(s)+1)-\sum_{\vec{f}^{\prime}:s_{j}=t}\xi_{\vec{f}^{\prime}},\forall t\in[r_{j},d_{j})\setminus\{s_{j}\}. \tag{2}\]