# Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems +
## 4 Coordination Mechanism
### Monomial Server Costs with \(d<1\)
: _For \(c(x)=x^{d}\) with \(d<1\) and common slot instances, our coordination mechanism induces games such that, for every optimal assignment \(s^{*}\), there exists a vector of payments \(\xi\) such that \((s^{*},\xi)\) is a NE._  
Proof. : An optimal assignment will clearly place all jobs on the same slot. Charging each job the fair share \(x^{d-1}\) results in a NE since \(x^{d-1}<1\) with 1 being the cost any job would have to pay to deviate to a different slot and open it. Another class of instances for which an optimal and stable solution can be computed efficiently is the class of Laminar instances. A real-time scheduling instance is _laminar_ if the intervals \(I(j)\) for all jobs \(j\) form a laminar family, i.e., for any two jobs \(j,j^{\prime}\in\mathcal{J}\), we have \(I(j)\cap I(j^{\prime})=\emptyset\) or \(I(j)\subset I(j^{\prime})\) or \(I(j^{\prime})\subset I(j)\). Since the job intervals are laminar, the jobs can be represented by a forest \(F\) of rooted trees, where each vertex in a tree in \(F\) corresponds to a job, and a vertex \(v(j)\) is an ancestor of a vertex \(v(j^{\prime})\) if and only if \(I(j^{\prime})\subset I(j)\). Define the level of each vertex in the forest as follows. Any root of a tree in the forest is at level \(1\). For all other vertices \(v\), the level of \(v\) is 1 plus the level of its parent. **Theorem 10**. : _Algorithm 2 produces a NE profile of optimal cost._```
1:Build the corresponding forest. 2:while there are unassigned jobs do
3: Let \(j\) be a node of maximal level. Assign \(j\) and all the jobs in the path connecting \(j\) and the root of its tree on any slot \(t\in I(j)\). 4: Let \(\xi_{j}=c(l_{t})\) 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 2** An algorithm for finding a NE schedule such that \(cost(s)=OPT\) for Laminar instances

Proof. : Consider the forest \(F\). It is defined such that for every two leaves, \(v_{1},v_{2}\), the intervals corresponding to the jobs \(v_{1}\) and \(v_{2}\) do not overlap. Thus, the social optimum is at least the number of leaves in \(F\). The profile produced by the algorithm is a social optimum because its cost is exactly the number of leaves in \(F\). We show it is a NE. Clearly, any job \(k\) for with \(\xi_{k}=0\) is stable. In addition, the only jobs with a positive payment correspond to leaves in \(F\). Since the intervals of different leaves do not overlap, for every leaf-job, \(j\), the only active slot in \(I(j)\) is the slot it is paying for; thus, \(j\) has no feasible migration. Earlier in the section we prove that our coordination mechanism reduces the PoA to a constant for common slot instances. On the contrary, we show that, for general instances, the PoA remains super-constant even for our mechanism. **Theorem 11**. : _For a game with \(n\) jobs and \(c(x)=x^{d}\) with \(d<1\), the worst case PoA of our mechanism is \(\Omega(n^{d(1-d)})\)._

Proof. : Consider a large number of jobs \(n\) such that \(n^{d}\) is integer. Our instance has \(n^{d}\) slots and \(n^{d}\) jobs \(1,2,\ldots,n^{d}\) such that job \(j\) can only be scheduled on slot \(j\). All other \(n-n^{d}\) jobs can be scheduled on any slot. Let \(s^{*}\) be the assignment where every one of the unrestricted jobs is scheduled in slot 1. We get:

\[C(s^{*})=\left(n-n^{d}+1\right)^{d}+\left(n^{d}-1\right)=\Theta\Big{(}n^{d} \Big{)}.\]

The first term of the sum comes from slot 1 and the second term comes from slots \(2,3,\ldots,n^{d}\) which hold one job each. Now consider the following NE \(s\). The unrestricted jobs are split equally among all slots, with each slot having \(n^{1-d}-1\) of them. The payments declared by the unrestricted jobs are 0 and the full cost of each slot is paid for by the corresponding restricted job. This outcome is a NE since the unrestricted jobs get to freeload while the restricted jobs can't move to a different slot and have to pay enough to keep their slot open and avoid the large cost of remaining unscheduled.