Scheduling Games with Potential Penalties on the Move of Jobs

Abstract

This paper studies scheduling games with potential penalties on the move of jobs. There are a set of machines and a set of jobs. Each job could choose one machine and be processed by the chosen one. Jobs that try to change their original choice will incur additional costs, which is proportional to its processing time with proportional parameter $\delta \geqslant 0$. A schedule is a $\delta$-NE if no job has the incentive to change its choice unilaterally. The $\delta$-NE is a generation of Nash equilibrium, and its inefficiency can be measured by the $\delta$-PoA, which is also a generalization of the Price of Anarchy. For the game with the social cost of minimizing the makespan, the exact $\delta$-PoA for any number of machines and any $\delta \geqslant 0$ is obtained. For the game with the social cost of maximizing the minimum machine load, an upper bound on the $\delta$-PoA is presented, and tight bounds are given for $2\leqslant m\leqslant 11$ and any $\delta \geqslant 0$, where m is the number of machines.

1 Introduction

In recent years, scheduling games have gained more and more attention in the operations research and computer science community [1]. In contrast to the assumption of classical scheduling problems that all jobs are arranged by a central decision maker, every job is an independent decision maker who can decide the way how it is processed. This assumption adapts to the requirement of decentralized applications such as network economy and cloud services. One platform may have various resources with different performances and prices and provide services for multiple customers at the same time. However, the platform cannot or should not decide customers’ behavior, but let their customers be free to make choices. Each customer has the right to choose one of these resources based on their interests. The change in the decision-making body leads to distinct features from classical optimization problems.

Without a centralized arrangement, schedules occurring in scheduling games are usually determined by the decision of each job rather than a particular algorithm. One basic hypothesis of game theory is the rationality of the players [2]. That is, each decision maker will choose a strategy to minimize his cost. In the case of the scheduling game, each job could choose one machine from a set of parallel machines and be processed by the chosen one. The costs of the jobs are also determined by the choices of the jobs [3]. Since all the jobs are scheduled on the same set of machines, there is an interaction effect between the choices of the jobs. Each job will also seek the possibility of reducing its cost by changing its choice, i.e., moving from one machine to another. However, this kind of movement may not be endless. Under most circumstances, the choices of jobs will eventually form a steady schedule, which is known as a Nash equilibrium (NE) [3]. In the NE, no job will reduce its cost by changing its choice unilaterally. This kind of schedule is one of the main focuses of scheduling games.

Although each customer makes a decision based on its own cost, the platform has to pay attention to the overall interest, which is called social cost. It is not surprising that decentralized decisions will suffer losses on the social cost compared to centralized decisions. High loss indicates that the decision mechanism is not effective and requires to improve. Possible improvements include limiting the choice of jobs, guiding jobs in their choices through economic means, or even returning to centralized decisions.

The Price of Anarchy (PoA) is a kind of quantitative index that measures the inefficiency of the NE. The PoA of an instance is defined as the ratio between the social cost of a worst NE and the optimal social cost. The PoA of the game is the supremum value of the PoA of all instances. Analogous to the worst-case ratio of an approximation algorithm, PoA reflects the performance of an NE in the worst case in terms of social cost. To obtain the value of the PoA is one of the central roles of research on scheduling games.

Naturally, more complex scenarios exist in real situations. For example, it may not be very smooth to change the previous choice of the job. Sometimes the change of choice will produce extra cost or require additional time, so the job is preferred to keep the current choice. Under this circumstance, the scope of the steady schedule will be wider than the NE. The consequence is that the loss from the decentralized decision may be underestimated, which further influences the evaluation of the decision mechanism. So it is necessary to study the property of the new kind of equilibrium and to generalize the notion of the Price of Anarchy.

In this paper, we will study the scheduling game with additional penalties on the change of the choice of the players. There are a set of machines $\mathcal{M} = \{ M_1, M_2,\cdots , M_m \}$ and a set of jobs $\mathcal{J}=\{J_1, J_2, \cdots , J_n\}$. The processing time of job $J_j$ is $p_j$, $j=1,\cdots , n$. The player set of the game is $\mathcal{J}$, and every player $J_j\in \mathcal{J}$ has a strategy set that consists of all the machines. A strategy profile of the game is essentially a schedule in which every job is scheduled on one of the machines. A load of a machine is the sum of the processing times of all the jobs that choose this machine in the schedule. Given a penalty parameter $\delta \geqslant 0$, a profile $\sigma$ is a $\delta$-NE if the cost of any job in $\sigma$ is no larger than its new cost when it unilaterally moves to another machine. Suppose that $J_j$ is scheduled on $M_i$ in $\sigma$, and the schedule that $J_j$ unilaterally moves to $M_k$ is denoted $\sigma '$. Then, the cost of $J_j$ in $\sigma$ is the load of $M_i$ in $\sigma$, whereas its new cost is the load of $M_k$ in $\sigma '$ plus the penalty cost. Although there may be different settings on the penalty cost, we assume that the penalty cost of a job is proportional to its processing time with a proportional factor $\delta$. Two kinds of social costs are considered. The first is minimizing makespan, i.e., the maximal load of all the machines. The second is maximizing the minimum load of all the machines.

The inefficiency of the $\delta$-NE is measured by $\delta$-PoA, which is a generalization of the classical PoA [3]. For the games with the social cost of minimizing the makespan, the $\delta$-PoA of an instance is defined to be the ratio of the social cost of a $\delta$-NE, which has the largest social cost among all the $\delta$-NEs to the optimal social cost. For the games with the social cost of maximizing the minimum machine load, in reverse, the $\delta$-PoA of an instance is defined to be the ratio of the optimal social cost to the social cost of a $\delta$-NE, which has the smallest social cost among all the $\delta$-NEs. The $\delta$-PoA of the game is the supremum value of the $\delta$-PoA of all instances.

The framework of scheduling games and the notion of the Price of Anarchy were formulated by Koutsoupias and Papadimitriou in their seminar work [3]. For the scheduling game with the social cost of minimizing the makespan, the PoA is $\frac{2m}{m+1}$ [4, 5]. For the social cost of maximizing the minimum machine load, the PoA is $\frac{17}{10}$ for any number of machines [6]. When the number of machines is small, the bound of $\frac{7}{4}-\frac{1}{4\lfloor \frac{m}{2}\rfloor }$ is better and is tight when $2\leqslant m\leqslant 7$ [6]. Research on the PoA for other social costs and more sophisticated paradigms of scheduling games can be found in [7,8,9,10,11,12,13,14].

There are also some models of scheduling games that additional costs incurred by the move of jobs. For the scheduling game with migration cost [15], a set of jobs and a set of original machines, as well as an initial schedule, are given. Machines can either be removed, or be added, but not both. The processing time of a job will increase by a constant if it is scheduled on a machine that is different from the machine it is scheduled in the initial schedule. However, in their model, no penalty cost would occur if a job moves from one machine to the other machine, but both machines are different from the machine it is scheduled in the initial schedule. The concept of a steady schedule does not change, but whether a schedule is a NE or not heavily depended on the initial schedule. Remind that in our model, the penalty costs are virtual and only act as a disincentive to the change of choice.

A term similar to $\delta$-NE is $\varepsilon$-approximate NE [16,17,18]. An (additive or multiplicative) $\varepsilon$-approximate NE is a profile from which no player has the incentive to deviate so that it decreases its cost by more than $\varepsilon$, or by a factor larger than $1+\varepsilon$. However, in our model, the penalty cost is neither a constant, nor proportional to the new cost.

In this paper, we study the inefficiency of the equilibrium with potential penalty cost for the change of choice. For the game with the social cost of minimizing the makespan, we show the $\delta$-PoA is

$$\begin{aligned} \left\{ \begin{array}{ll} \max \left\{ \frac{m\lceil \alpha \rceil }{m\lceil \alpha \rceil -(m-1)(1+\delta )},\lfloor \alpha \rfloor \right\} , &{} 0\leqslant \delta <m-1,\\ m, &{} \delta \geqslant m-1, \end{array} \right. \end{aligned}$$

where $\alpha =1+\frac{m-1}{m}(1+\delta )$. The bound is tight for any $\delta$ and m. For the game with the social cost of maximizing the minimum machine load, we show the $\delta$-PoA is at most $\frac{1}{2\lfloor \frac{m}{2}\rfloor }\left( 1+\frac{2\lfloor \frac{m}{2}\rfloor }{1-\delta }+\frac{3\left( \lfloor \frac{m}{2}\rfloor -1\right) }{2-\delta }\right)$, and tight bounds are obtained for any $\delta$ and $m\leqslant 11$ (Ref. Fig. 1). A lower bound of $\frac{1}{12}+\frac{1}{1-\delta }+\frac{1}{2-\delta }+\frac{7}{12(6-\delta )}$ is also given for $m\geqslant 12$. As a corollary of our result, the PoA is $\frac{5}{3}$ up to 11 machines, and at least $\frac{121}{72}$ for more than 11 machines, which extends some results of [6] for a small number of machines.

Fig. 1

Left: The $\delta$-PoA for the game with the social cost of minimizing the makespan on 2(bottom), 4(middle), and 6(top) machines. Right: The $\delta$-PoA (solid line) for the game with the social cost of maximizing the minimum machine load on 2(bottom), 4(middle), and 6(top) machines, and an upper bound of the $\delta$-PoA (dashed line) on 12 machines

The paper is organized as follows: In Section 2, we present some preliminary results. In Sections 3 and 4, we prove upper and lower bounds on the $\delta$-PoA for the game with the social cost of minimizing the makespan and maximizing the minimum machine load, respectively.

2 Preliminaries

We first introduce some notations, which will be used throughout the paper. An instance I of the scheduling game can be represented by an ordered pair $I=(\mathcal {J}, \mathcal {M})$. A schedule of instance I is denoted $\sigma (I)$. We omit I if no confusion can arise. Given a subset $\mathcal {J}_0 \subseteq \mathcal {J}$, the total processing time of the jobs in $\mathcal {J}_0$ is denoted $P(\mathcal {J}_0)$. We abbreviate $P(\mathcal {J})$ to P. For any schedule $\sigma ^A(I)$, the subset of jobs that are scheduled on $M_i$ is denoted $\mathcal {J}_i^A(I)$, $i=1,\cdots ,m$. Let $n_i^A(I)=|\mathcal {J}_i^A(I)|$ and $L_i^A(I)=P(\mathcal {J}_i^A(I))$ be the number of jobs scheduled on $M_i$ and the load of $M_i$, respectively. Denote by $C^{A}_{\max }(I)$ and $C^{A}_{\min }(I)$ the maximum load (makespan) and the minimum load of all the machines, respectively. That is $C^{A}_{\max }(I)=\max \limits _{i=1,\cdots ,m} L_i^A(I)$ and $C^{A}_{\min }(I)=\min \limits _{i=1,\cdots ,m} L_i^A(I)$.

Let $\sigma ^\delta$ be an arbitrarily $\delta$-NE. W.l.o.g., we assume that $L_1^\delta \geqslant L_2^\delta \geqslant \cdots \geqslant L_m^\delta$. Denote by $J_{a_i}$, $J_{b_i}$, $J_{z_i}$ the job with the largest, the second largest, and the smallest processing time among $\mathcal {J}_i^\delta$, respectively. By the definition of the $\delta$-NE, for any $1\leqslant i,k\leqslant m$ and any $J_j \in \mathcal {J}^\delta _i$,

$$\begin{aligned} L^\delta _i \leqslant L^\delta _k +(1+\delta )p_j. \end{aligned}$$

(1)

In fact, assume that there exist i and k, $J_j \in \mathcal {J}^\delta _i$ and $L_i^\delta >L_k^\delta +(1+\delta )p_j$. If $J_j$ moves from $M_i$ to $M_k$, the new cost of $J_j$ is $L_k^\delta +p_j+\delta p_j$, which is smaller than its cost in $\sigma ^\delta$. It contradicts that $\sigma ^\delta$ is a $\delta$-NE.

Though (1) is also sufficient, we have a simpler criterion for whether a schedule $\sigma ^A$ is a $\delta$-NE or not. If $J_j\in \mathcal {J}_i^A$ and $n_i^A=1$, then $L^A_i=p_j\leqslant L^A_k +(1+\delta )p_j$ for any $k\ne i$. Hence, any job that scheduled on a machine separately has no incentive to move to another machine. If $L^A_i\leqslant L^A_k$, then $L^A_i \leqslant L^A_k +(1+\delta )p_j$ trivially holds for any $J_j\in \mathcal {J}_i^A$. It follows that no job has an incentive to move to a machine with an equal or larger load. Therefore, we have the following lemma.

Lemma 1

If for any $J_j\in \mathcal {J}^A_i$ where $n_i^A>1$ and $L_i^A>C^{A}_{\min }$, $L^A_i \leqslant C^{A}_{\min }+(1+\delta )p_j$, then $\sigma ^A$ is a $\delta$-NE.

From (1), it is clear that any NE is a $\delta$-NE for any $\delta \geqslant 0$, but the reverse is not true. Due to the existence of NE for the classical scheduling game [19], $\delta$-NE also exists for any $\delta \geqslant 0$. When $\delta =0$, $\delta$-NE degenerate to the classical NE. Moreover, for any $\delta _1<\delta _2$, $\delta _1$-NE is also a $\delta _2$-NE and thus $\delta _1$-PoA is no more than $\delta _2$-PoA. Note that 0-PoA is equal to the PoA.

Denote by $\sigma ^*$ and $\sigma ^{**}$ the optimal schedule with the social cost of minimizing the makespan and maximizing the minimum machine load, respectively. The $\delta$-PoA for the scheduling game on m machines with the social cost of minimizing the makespan is

$$\begin{aligned} U_{\delta , m}=\sup \left\{ \frac{C^{\delta }_{\max }(I)}{C^{*}_{\max }(I)}\mid I=(\mathcal {J}, \mathcal {M}), |\mathcal {M}|=m \right\} . \end{aligned}$$

The $\delta$-PoA for the scheduling game on m machines with the social cost of maximizing the minimum machine load is

$$\begin{aligned} V_{\delta , m}=\sup \left\{ \frac{C^{**}_{\min }(I)}{C^{\delta }_{\min }(I)}\mid I=(\mathcal {J}, \mathcal {M}), |\mathcal {M}|=m \right\} . \end{aligned}$$

The following lemma provides some basic bounds on the optimum.

Lemma 2

(Folklore) (i) $C^{*}_{\max } \geqslant \max \{\frac{P}{m}, \max \limits _{j=1,\cdots ,n} p_j\}$.

(ii) $C^{**}_{\min }\leqslant \frac{P}{m}$.

3 Minimizing the Makespan

In this section, we present the exact value of the $\delta$-PoA for the game with the social cost of minimizing the makespan.

Theorem 1

For the scheduling game on m identical machines with the social cost of minimizing the makespan, the $\delta$-PoA is

$$\begin{aligned} U_{\delta , m}=\left\{ \begin{array}{ll} \max \left\{ \frac{m\lceil \alpha \rceil }{m\lceil \alpha \rceil -(m-1)(1+\delta )},\lfloor \alpha \rfloor \right\} , &{} 0\leqslant \delta <m-1,\\ m, &{} \delta \geqslant m-1, \end{array} \right. \end{aligned}$$

where $\alpha =1+\frac{m-1}{m}(1+\delta )$.

Proof

We start from the relatively easy case of $\delta \geqslant m-1$. Obviously, $C^{\delta }_{\max } \leqslant P \leqslant m C^{*}_{\max }$ by Lemma 2(i), and thus, $U_{\delta , m}\leqslant m$. To show the bound is tight, consider an instance $I_1$ consisting of m jobs of processing time 1. Clearly, $C^{*}_{\max }(I_1)=1$. On the other hand, the schedule $\sigma ^1$ that all the jobs are scheduled on $M_1$ is a $\delta$-NE. In fact, note that $L_1^1=m$ and $L_i^1=0$ for any $i\ne 1$. Thus, $C^{1}_{\max }(I_1)=1$ and $C^{1}_{\min }(I_1)=0$. Since $L_1^1=m\leqslant 1+\delta =C^{1}_{\min }(I_1)+(1+\delta )$, $\sigma ^1$ is a $\delta$-NE by Lemma 1. Hence, $U_{\delta , m}\geqslant \frac{C^{1}_{\max }(I_1)}{C^{*}_{\max }(I_1)}=m$. Thus, $U_{\delta , m}=m$ for any $\delta \geqslant m-1$.

We assume $0\leqslant \delta <m-1$ in the rest of the proof. Note that

$$\begin{aligned} n_1^\delta p_{z_1}\leqslant C^{\delta }_{\max }=L_1^\delta \leqslant n_1^\delta p_{a_1}. \end{aligned}$$

(2)

Moreover, by (1),

$$\begin{aligned} L_1^\delta \leqslant L_i^\delta +(1+\delta )p_{z_1}, i>1. \end{aligned}$$

(3)

If $n_1^\delta >\frac{m-1}{m}(1+\delta )=\alpha -1$, by (3) and (2),

$$\begin{aligned} P= & {} \sum _{i=1}^m L_i^\delta =L_1^\delta +\sum _{i=2}^m L_i^\delta \geqslant L_1^\delta +(m-1)(L_1^\delta -(1+\delta )p_{z_1})\\= & {} mL_1^\delta -(m-1)(1+\delta )p_{z_1}\geqslant mL_1^\delta -\frac{(m-1)(1+\delta )}{n_1^\delta }L_1^\delta \\= & {} \left( m-\frac{(m-1)(1+\delta )}{n_1^\delta }\right) C^{\delta }_{\max }. \end{aligned}$$

Combining the above inequality with Lemma 2(i), we have

$$\begin{aligned} \frac{C^{\delta }_{\max }}{C^{*}_{\max }}\leqslant \frac{\frac{P}{m-\frac{(m-1)(1+\delta )}{n_1^\delta }}}{\frac{P}{m}}=\frac{m n_1^\delta }{m n_1^\delta -(m-1)(1+\delta )}. \end{aligned}$$

(4)

On the other hand,

$$\begin{aligned} \frac{C^{\delta }_{\max }}{C^{*}_{\max }}\leqslant \frac{L_1^\delta }{p_{a_1}}\leqslant n_1^\delta \end{aligned}$$

(5)

by Lemma 2(i) and (2).

Note that $\frac{m n_1^\delta }{m n_1^\delta -(m-1)(1+\delta )}$ is a monotone decreasing function of $n_1^\delta$. If $2\leqslant n_1^\delta \leqslant \lfloor \alpha \rfloor$, then by (5),

$$\begin{aligned} \frac{C^{\delta }_{\max }}{C^{*}_{\max }}\leqslant n_1^\delta \leqslant \lfloor \alpha \rfloor \leqslant \max \left\{ \frac{m\lceil \alpha \rceil }{m\lceil \alpha \rceil -(m-1)(1+\delta )},\lfloor \alpha \rfloor \right\} . \end{aligned}$$

If $n_1^\delta \geqslant \lceil \alpha \rceil$, then by (4),

$$\begin{aligned} \frac{C^{\delta }_{\max }}{C^{*}_{\max }}\leqslant & {} \frac{m n_1^\delta }{m n_1^\delta -(m-1)(1+\delta )}\leqslant \frac{m\lceil \alpha \rceil }{m\lceil \alpha \rceil -(m-1)(1+\delta )}\\\leqslant & {} \max \left\{ \frac{m\lceil \alpha \rceil }{m\lceil \alpha \rceil -(m-1)(1+\delta )},\lfloor \alpha \rfloor \right\} . \end{aligned}$$

Therefore,

$$\begin{aligned} U_{\delta , m}\leqslant \max \left\{ \frac{m\lceil \alpha \rceil }{m\lceil \alpha \rceil -(m-1)(1+\delta )},\lfloor \alpha \rfloor \right\} . \end{aligned}$$

We introduce two instances to show that the bound is tight. Note that $\alpha <m$ when $\delta <m-1$. Instance $I_2$ consists of $(m-\lfloor \alpha \rfloor )(m-1)+\lfloor \alpha \rfloor$ jobs, including $\lfloor \alpha \rfloor$ large jobs with processing times 1, and $(m-\lfloor \alpha \rfloor )(m-1)$ small jobs with processing times $\max \left\{ \frac{\lfloor \alpha \rfloor -1-\delta }{m-\lfloor \alpha \rfloor },0\right\}$. In a schedule $\sigma ^2$, all the large jobs are scheduled on $M_1$, and each of the remaining $m-1$ machines processes $m-\lfloor \alpha \rfloor$ small jobs. Clearly, $L_1^2=\lfloor \alpha \rfloor$ and $L_i^2= \max \{\lfloor \alpha \rfloor -1-\delta ,0\}$, $i=2,\cdots ,m$. Thus $C^{2}_{\max }(I_2)=\lfloor \alpha \rfloor$ and $C^{2}_{\min }(I_2)=\max \{\lfloor \alpha \rfloor -1-\delta ,0\}$. Moreover, since

$$\begin{aligned} L_1^2=\lfloor \alpha \rfloor \leqslant \max \{\lfloor \alpha \rfloor -1-\delta ,0\}+(1+\delta )= C^{2}_{\min }(I_2)+(1+\delta ), \end{aligned}$$

$\sigma ^2$ is a $\delta$-NE by Lemma 1.

In another schedule $\sigma '$, each large job is scheduled on a machine separately. Each of the remaining $m-\lfloor \alpha \rfloor$ machines processes $m-1$ small jobs. Since $\lfloor \alpha \rfloor \leqslant 1+\frac{m-1}{m}(1+\delta )$, $m\geqslant m\lfloor \alpha \rfloor -(m-1)(1+\delta )$ and thus

$$\begin{aligned} (m-1)\frac{\lfloor \alpha \rfloor -1-\delta }{m-\lfloor \alpha \rfloor }\leqslant \frac{(m-1)(\lfloor \alpha \rfloor -1-\delta )}{m\lfloor \alpha \rfloor -(m-1)(1+\delta )-\lfloor \alpha \rfloor }=1. \end{aligned}$$

The loads of all the machines in $\sigma '$ are no more than 1. Therefore, $C^{*}_{\max }(I_2)\leqslant 1$ and $U_{\delta , m}\geqslant \frac{C^{2}_{\max }(I_2)}{C^{*}_{\max }(I_2)}\geqslant \lfloor \alpha \rfloor$.

Instance $I_3$ consists of $(2\,m-\lceil \alpha \rceil )(m-1)+\lceil \alpha \rceil$ jobs, including $\lceil \alpha \rceil$ large jobs with processing time 1, $(m-\lceil \alpha \rceil )(m-1)$ small jobs with processing time $\frac{1}{m-1}$, and $m(m-1)$ tiny jobs with processing time $\frac{(\lceil \alpha \rceil -1-\delta )(m-1)-(m-\lceil \alpha \rceil )}{m(m-1)}$. Since $\lceil \alpha \rceil \geqslant 1+\frac{m-1}{m}(1+\delta )$,

$$\begin{aligned} (\lceil \alpha \rceil -1-\delta )(m-1)-(m-\lceil \alpha \rceil )=m\lceil \alpha \rceil -m-(m-1)(1+\delta )\geqslant 0 \end{aligned}$$

and thus the instance is well-defined.

In a schedule $\sigma ^3$, all the large jobs are scheduled on $M_1$, and each of the remaining $m-1$ machines processes $m-\lceil \alpha \rceil$ small jobs and m tiny jobs. Clearly,

$$\begin{aligned} L_1^3= & {} \lceil \alpha \rceil ,\\ L_i^3= & {} \frac{m-\lceil \alpha \rceil }{m-1}+\frac{(\lceil \alpha \rceil -1-\delta )(m-1)-(m-\lceil \alpha \rceil )}{m-1}\\= & {} \lceil \alpha \rceil -1-\delta , i=2,\cdots ,m. \end{aligned}$$

Thus, $C^{3}_{\max }(I_3)=\lceil \alpha \rceil$ and $C^{3}_{\min }(I_3)=\lceil \alpha \rceil -1-\delta$. Moreover, since

$$\begin{aligned} L_1^3=\lceil \alpha \rceil =(\lceil \alpha \rceil -1-\delta )+(1+\delta )= C^{3}_{\min }(I_3)+(1+\delta ), \end{aligned}$$

$\sigma ^3$ is a $\delta$-NE by Lemma 1.

In another schedule $\sigma '$, each of the first $\lceil \alpha \rceil$ machines processes a large job and $m-1$ tiny jobs. Each of the remaining $m-\lceil \alpha \rceil$ machines processes $m-1$ small jobs and $m-1$ tiny jobs. The loads of all the machines in $\sigma '$ are

$$\begin{aligned} 1+\frac{(\lceil \alpha \rceil -1-\delta )(m-1)-(m-\lceil \alpha \rceil )}{m}=\frac{m\lceil \alpha \rceil -(m-1)(1+\delta )}{m}. \end{aligned}$$

Therefore, $C^{*}_{\max }(I_3)=\frac{m\lceil \alpha \rceil -(m-1)(1+\delta )}{m}$ and $U_{\delta , m}\geqslant \frac{C^{3}_{\max }(I_3)}{C^{*}_{\max }(I_3)}\geqslant \frac{m\lceil \alpha \rceil }{m\lceil \alpha \rceil -(m-1)(1+\delta )}$.

4 Maximizing the Minimum Machine Load

In this section, we present lower and upper bounds on the $\delta$-PoA for the game with the social cost of maximizing the minimum machine load. Unlike the game with the social cost of minimizing the makespan, the $\delta$-PoA is unbounded for any $m\geqslant 2$.

Theorem 2

For the scheduling game on m identical machines with the social cost of maximizing the minimum machine load, the $\delta$-PoA is infinity when $\delta \geqslant 1$.

Proof

Consider the instance $I_1$ consisting of m jobs of processing time 1. Clearly, $C^{**}_{\min }(I_1)=1$. On the other hand, the schedule $\sigma '$ that two jobs are scheduled on $M_1$, one job is scheduled on $M_i$, $2\leqslant i\leqslant m-1$, and none of the jobs is scheduled on $M_m$ is a $\delta$-NE. In fact, note that $L'_1=2$, $L'_m=0$ and $L'_i=1$ for any $1<i<m$. Thus, $C'_{\min }(I_1)=0$. Since $L'_1 =2\leqslant 1+\delta =C'_{\min }(I_1)+(1+\delta )$, $\sigma '$ is a $\delta$-NE by Lemma 1. Hence, $V_{\delta ,m}=\infty$.

According to Theorem 2, we assume that $0<\delta <1$ in the rest of the section. We first show some further properties on the $\delta$-NE. Remind that $L_1^\delta \geqslant L_2^\delta \geqslant \cdots \geqslant L_m^\delta$, and $J_{a_i}$, $J_{b_i}$, $J_{z_i}$ is the job with the largest, the second largest and the smallest processing time among $\mathcal {J}_i^\delta$, respectively. Let $\mathcal {M}_{II}=\{M_i|1\leqslant i\leqslant m-1 \text { and } n_i^\delta =2\}$ and $\mathcal {M}_{III}=\{M_i|1\leqslant i\leqslant m-1 \text { and } n_i^\delta =3\}$ be the subsets of $\mathcal {M} {\setminus } \{M_m\}$ consisting of machines that process 2 and 3 jobs in $\sigma ^\delta$, respectively. Denote by $\mathcal {J}_{II}=\bigcup \limits _{M_i\in \mathcal {M}_{II}} \mathcal {J}_i^\delta$ and $\mathcal {J}_{III}=\bigcup \limits _{M_i\in \mathcal {M}_{III}} \mathcal {J}_i^\delta$ the subsets of jobs that are processed on the machines of $\mathcal {M}_{II}$ and $\mathcal {M}_{III}$, respectively. Clearly, $|\mathcal {J}_{II}|=2|\mathcal {M}_{II}|$ and $|\mathcal {J}_{III}|=3|\mathcal {M}_{III}|$.

Lemma 3

If $n_i^\delta \geqslant 2$ for some $1\leqslant i\leqslant m-1$, then $L_i^\delta \leqslant \frac{n_i^\delta }{n_i^\delta -1-\delta }L_m^\delta$ and $L_i^\delta -p_{z_i}\leqslant \frac{n_i^\delta -1}{n_i^\delta -1-\delta }L_m^\delta$. Specifically, $p_j\leqslant \frac{1}{1-\delta }L_m^\delta$ for any $J_j\in \mathcal {J}_{II}$.

Proof

Since $\sigma ^\delta$ is a $\delta$-NE, $n_i^\delta p_{z_i}\leqslant L_i^\delta \leqslant L_m^\delta +(1+\delta )p_{z_i}$ by (1). Thus, $p_{z_i}\leqslant \frac{1}{n_i^\delta -1-\delta }L_m^\delta$. Hence, $L_i^\delta \leqslant L_m^\delta +(1+\delta )p_{z_i}\leqslant \frac{n_i^\delta }{n_i^\delta -1-\delta }L_m^\delta$ and $L_i^\delta -p_{z_i}\leqslant L_m^\delta +\delta p_{z_i}\leqslant \frac{n_i^\delta -1}{n_i^\delta -1-\delta }L_m^\delta$.

If $n_i^\delta =2$, then $p_{z_i}\leqslant p_{a_i}=L_i^\delta -p_{z_i}\leqslant \frac{1}{1-\delta }L_m^\delta$. Therefore, $p_j\leqslant \frac{1}{1-\delta }L_m^\delta$ for any $J_j\in \mathcal {J}_{II}$.

Next we show that the $\delta$-PoA is non-decreasing for the number of machines.

Lemma 4

$V_{\delta ,m} \leqslant V_{\delta ,m+1}$.

Proof

Let $I = (\mathcal {J}, \mathcal {M})$ be an arbitrary instance with $|\mathcal {M}| = m$, and $\sigma ^\delta (I)$ be an arbitrary $\delta$-NE of I. Consider an instance $I' = (\mathcal {J}', \mathcal {M}')$ with $m+1$ machines, where $\mathcal {J}' = \mathcal {J}\cup \{J_{n+1}\}$ and $\mathcal {M}' = \mathcal {M}\cup \{M_{m+1}\}$. The processing time of $J_{n+1}$ is $p_{n+1} = C_{\min }^{**}(I)$.

Obviously, $C_{\min }^{**}(I') \geqslant C_{\min }^{**}(I)$, as we can easily obtain a feasible schedule $\sigma '$ of $I'$ with $C_{\min }'(I') = C_{\min }^{**}(I)$ based on $\sigma ^{**}(I)$. That is

$$\begin{aligned} \mathcal {J}'_i(I') = \mathcal {J}_i^{**}(I), i=1,\cdots ,m, \mathcal {J}'_{m+1}(I') = \{J_{n+1}\}. \end{aligned}$$

On the other hand, let $\sigma ^\delta (I')$ be a schedule of $I'$ such that

$$\begin{aligned} \mathcal {J}^\delta _i(I') = \mathcal {J}_i^\delta (I), i=1,\cdots ,m, \mathcal {J}^\delta _{m+1}(I') = \{J_{n+1}\}. \end{aligned}$$

Note that

$$\begin{aligned} L_{m+1}^\delta (I') =p_{n+1} = C_{\min }^{**}(I) \geqslant C_{\min }^\delta (I) = L_m^\delta (I) = L_m^\delta (I'). \end{aligned}$$

Thus, $C_{\min }^\delta (I') = C_{\min }^\delta (I)=L_m^\delta (I)$. Since $\sigma ^\delta (I)$ is a $\delta$-NE of I, for any $1\leqslant i\leqslant m$, and $J_j\in \mathcal {J}^\delta _i(I') = \mathcal {J}^\delta _i(I)$,

$$\begin{aligned} L_i^\delta (I') = L_i^\delta (I) \leqslant L_m^\delta (I)+(1+\delta )p_j = C_{\min }^\delta (I')+(1+\delta )p_j. \end{aligned}$$

By Lemma 1, $\sigma ^\delta (I')$ is a $\delta$-NE of $I'$, and $\frac{C_{\min }^{**}(I')}{C_{\min }^\delta (I')} \geqslant \frac{C_{\min }(I)}{C_{\min }^\delta (I)}$. By the arbitrariness of I and $\sigma ^\delta$, we have $V_{\delta ,m+1} \geqslant V_{\delta ,m}$.

Lemma 4 indicates that the $\delta$-PoA for m machines is no less than the $\delta$-PoA for fewer machines. However, the ratio between the social cost of an optimal schedule and a $\delta$-NE will not exceed the $\delta$-PoA for $m-1$ machines in some circumstances, as we will see in the next lemma.

Lemma 5

Suppose that $\sigma ^\delta (I)$ and $\sigma '(I)$ is a $\delta$-NE and a feasible schedule of I, respectively. If there exists $k\ne m$ such that $\mathcal {J}^\delta _k(I) \subseteq \mathcal {J}'_k(I)$, then $\frac{C'_{\min } (I)}{C^\delta _{\min } (I)} \leqslant V_{\delta , m-1}$.

Proof

Let $I^-=(\mathcal {J}^-, \mathcal {M}^-)$ be an instance with $m-1$ machines, where $\mathcal {J}^- = \mathcal {J}{\setminus }\mathcal {J}^\delta _k(I)$ and $\mathcal {M}^- = \mathcal {M}{\setminus }\{M_k\}$. Construct a schedule $\sigma ^\delta (I^-)$ of $I^-$ based on $\sigma ^\delta (I)$ such that $\mathcal {J}_i^\delta (I^-) = \mathcal {J}_i^\delta (I)$ for any $i \ne k$. Obviously, $\sigma ^\delta (I^-)$ is a $\delta$-NE of $I^-$ and

$$\begin{aligned} C^\delta _{\min }(I^-) = \underset{i \ne k}{\min }L_i^\delta (I^-) = \underset{i \ne k}{\min }L_i^\delta (I) = \underset{i =1,2,\cdots ,m}{\min }L_i^\delta (I) = C^\delta _{\min }(I), \end{aligned}$$

(6)

where the third equality is due to $k\ne m$.

Next we provide another schedule $\sigma '(I^-)$ of $I^-$ based on $\sigma '(I)$. Let

$$\begin{aligned} \mathcal {J}'_m(I^-) = \mathcal {J}'_m(I) \cup (\mathcal {J}'_k(I) \setminus \mathcal {J}_k^\delta (I)), \mathcal {J}'_i(I^-) = \mathcal {J}'_i(I), i \ne k,m. \end{aligned}$$

Then, $L'_i(I^-) \geqslant L'_i(I)$ for any $i \ne k$. Hence,

$$\begin{aligned} C_{\min }^{**}(I^-) \geqslant C_{\min }'(I^-) = \underset{i \ne k}{\min }L_i'(I^-) \geqslant \underset{i \ne k}{\min }L'_i(I) \geqslant \underset{i=1,2,\cdots ,m}{\min }L'_i(I) = C'_{\min }(I).\nonumber \\ \end{aligned}$$

(7)

By (6), (7) and the fact that $\sigma ^\delta (I^-)$ is a $\delta$-NE of instance $I^-$ with $m-1$ machines,

$$\begin{aligned} \frac{C'_{\min }(I)}{C^\delta _{\min }(I)} \leqslant \frac{C^{**}_{\min }(I^-)}{C^\delta _{\min }(I^-)} \leqslant V_{\delta ,m-1}. \end{aligned}$$

In the next lemma, we provide two specific situations that meet the condition of Lemma 5. It significantly simplifies the proof of the $\delta$-PoA in companion with Lemma 4.

Lemma 6

• (i) If there exists $i \ne m$ such that $n_i^\delta = 1$, then $\frac{C^{**}_{\min } (I)}{C^\delta _{\min } (I)} \leqslant V_{\delta , m-1}$.

• (ii) If there exists a machine that processes at least two jobs of $\mathcal {J}_{II}$ in $\sigma ^{**}$, then $\frac{C^{**}_{\min } (I)}{C^\delta _{\min } (I)} \leqslant V_{\delta , m-1}$.

Proof

• (i) If there exists $i \ne m$ such that $n_i^\delta = 1$, then $\mathcal {J}_i^\delta =\{J_{a_i}\}$. Since $J_{a_i}$ must be processed on some machine in $\sigma ^{**}$, we can assume that $\mathcal {J}_i^\delta \subseteq \mathcal {J}_i^{**}$ by renumbering the indexes of the machines of $\sigma ^{**}$. Hence, $\frac{C^{**}_{\min } (I)}{C^\delta _{\min } (I)} \leqslant V_{\delta , m-1}$ by Lemma 5.

• (ii) Construct an instance $I^+=(\mathcal {J}^+,\mathcal {M})$ whose job set has a one-to-one map to the job set of $I=(\mathcal {J},\mathcal {M})$. For any $J_j \in \mathcal {J}_{II}$, the corresponding job $J_j^+$ has a processing time $\frac{1}{1-\delta }L_m^\delta (I)$. For any $J_j \notin \mathcal {J}_{II}$, the corresponding job $J_j^+$ has the same processing time as $J_j$. By Lemma 3, $p_j^+ \geqslant p_j$ for any j.

Let $\sigma ^\delta (I^+)$ be a schedule of $I^+$ such that $\mathcal {J}_i^\delta (I^+) = \mathcal {J}_i^\delta (I)$ for any i. Since $p_j^+ = p_j$ for any $J_j \notin \mathcal {J}_{II}$, $L_i^\delta (I^+)=L_i^\delta (I)$ for any $M_i\notin \mathcal {M}_{II}$. Thus, $L_m^\delta (I^+)=L_m^\delta (I)\leqslant L_i^\delta (I)\leqslant L_i^\delta (I^+)$ for any $i\ne m$. It follows that $C_{\min }^\delta (I^+)=C_{\min }^\delta (I)=L_m^\delta (I)$. For any $M_i\in \mathcal {M}_{II}$,

$$\begin{aligned} L_i^\delta (I^+)=\frac{2}{1-\delta }L_m^\delta (I) = L_m^\delta (I)+(1+\delta )\frac{1}{1-\delta }L_m^\delta (I)=C_{\min }^\delta (I^+)+(1+\delta )\frac{1}{1-\delta }L_m^\delta (I). \end{aligned}$$

Hence, $\sigma ^\delta (I^+)$ is also a $\delta$-NE of $I^+$ by the fact that $\sigma ^\delta (I)$ is a $\delta$-NE of I and Lemma 1.

Let $\sigma '(I^+)$ be a schedule of $I^+$ such that $\mathcal {J}'_i(I^+) = \mathcal {J}_i^{**}(I)$ for any i. Clearly, $C^{**}_{\min }(I) \leqslant C'_{\min }(I^+)$. Recall that all the jobs of $I^+$ correspond to the jobs of $\mathcal {J}_{II}$ have the same processing time. Since there exists a machine which processes at least two jobs of $\mathcal {J}_{II}$ in $\sigma ^{**}(I)$, we have $\mathcal {J}_i^\delta (I^+) \subseteq \mathcal {J}'_i(I^+)$ for some $M_i\in \mathcal {M}_{II}$ by renumbering the indexes of the jobs correspond to the jobs of $\mathcal {J}_{II}$ and the machines in $\sigma '$. Therefore, $\frac{C_{\min }^{**}(I)}{C_{\min }^\delta (I)}\leqslant \frac{C'_{\min } (I^+)}{C^\delta _{\min } (I^+)} \leqslant V_{\delta , m-1}$ by Lemma 5.

By Lemmas 4 and 6(i), to prove that the $\delta$-PoA for m machines does not exceed $V_{\delta , m}$, it is sufficient to assume that $n_i^\delta \geqslant 2$ for any $1\leqslant i\leqslant m-1$. Under such circumstance, it is easy to obtain an upper bound of $V_{\delta , m}$ by Lemma 3, as we will show in Lemma 8. However, the upper bound is too crude to be tight. With the help of Lemma 6(ii), we get a tighter and still universal upper bound in Theorem 3. It matches the lower bound of $V_{\delta , m}$ up to 7 machines. To obtain the tight bound for more machines, a careful investigation on the jobs of $\mathcal {J}_{III}$ is required, which forms the last and the most technical part of the paper.

For simplicity of notation, denote $\omega _i=\frac{1}{i-\delta }$ for any $i\geqslant 1$. Clearly,

$$\begin{aligned} (i+1)\omega _i=\frac{i+1}{i-\delta }=1+\frac{1+\delta }{i-\delta }=1+(1+\delta )\omega _i. \end{aligned}$$

(8)

We list some simple algebraic properties of $\omega _i$ below.

Lemma 7

• (i) $\omega _1\geqslant 2\omega _2 \geqslant 3\omega _3 \geqslant 4\omega _4\geqslant 6\omega _6\geqslant 1$.

• (ii) For any $k\geqslant 1$, $1+k\omega _1 \geqslant 2(k+1)\omega _2$. For any $k\geqslant 2$, $1+2k\omega _2 \geqslant 3(k+1)\omega _3$ and $1+k\omega _2 \geqslant 2(k+2)\omega _4$.

• (iii) $\frac{1}{2}+\omega _1\leqslant \frac{1}{4}+\omega _1+\omega _3\leqslant \frac{1}{4}+\omega _1+\frac{3}{4}\omega _2\leqslant \frac{1}{6}+\omega _1+\omega _2$.

• (iv) $\frac{1}{10}+\omega _1+\frac{3}{5}\omega _2+\frac{4}{5}\omega _3\leqslant \frac{1}{8}+\omega _1+\frac{3}{4}\omega _2+\frac{1}{2}\omega _3\leqslant \frac{1}{6}+\omega _1+\omega _2$.

• (v) For any $m\geqslant 2$, $1+6\omega _1+3\left( m-4\right) \omega _2\leqslant 1+8\omega _1+3\left( m-6\right) \omega _2+4\omega _3$.

• (vi) For any $m\leqslant 12$, $\frac{1}{m}+\frac{m-1}{m}\omega _1+\frac{4}{3}\omega _2\leqslant \frac{1}{12}+\frac{11}{12}\omega _1+\frac{4}{3}\omega _2\leqslant \frac{1}{6}+\omega _1+\omega _2$.

• (vii) For any $m\geqslant 8$, $\frac{1}{m}\left( 1+8\omega _1+3\left( m-6\right) \omega _2+4\omega _3\right) \leqslant \frac{1}{8}+\omega _1+\frac{3}{4}\omega _2+\frac{1}{2}\omega _3\leqslant \frac{1}{6}+\omega _1+\omega _2$.

• (viii) For any $m\geqslant 9$, $\frac{1}{m}\left( 1+8\omega _1+3(m-5)\omega _2\right) \leqslant \frac{1}{9}+\frac{8}{9}\omega _1+\frac{4}{3}\omega _2\leqslant \frac{1}{6}+\omega _1+\omega _2$.

• (ix) $\frac{1}{9}+\omega _1+\frac{8}{9}\omega _2+\frac{4}{9}\omega _4\leqslant \frac{1}{6}+\omega _1+\omega _2$.

• (x) $\frac{1}{11}+\frac{10}{11}\omega _1+\frac{12}{11}\omega _2+\frac{4}{11}\omega _3\leqslant \frac{1}{11}+\frac{10}{11}\omega _1+\frac{4}{3}\omega _2\leqslant \frac{1}{6}+\omega _1+\omega _2$.

Proof

(i) and (ii) can be proved by direct algebraic calculation. (iii) can be proved by (i). Both inequalities of (iv) are equivalent to $1+6\omega _2 \geqslant 12\omega _3$, which is valid according to (ii). (v) can be proved by $2\omega _1+4\omega _3 \geqslant 2\omega _1+1\geqslant 6\omega _2$, which is valid according to (i) and (ii). The first inequality of (vi) can be proved by (i), and the second inequality of (vi) is equivalent to $1+\omega _1 \geqslant 4\omega _2$, which is valid according to (ii). The first inequalities of both (vii) and (viii) can be proved by $1+8\omega _1 \geqslant 18\omega _2$, which is valid according to (ii). The second inequalities of (vii) and (viii) can be proved by (iv) and (vi), respectively. (ix) is equivalent to $1+2\omega _2 \geqslant 8\omega _4$, which is valid according to (ii). The first and second inequality of (x) can be proved by (i) and (vi), respectively.

Lemma 8

If $n_i^\delta \geqslant 2$ for any $1\leqslant i\leqslant m-1$, then

$$\begin{aligned} \frac{C^{**}_{\min }}{C^{\delta }_{\min }}\leqslant & {} \frac{1}{m}\left( 1+2|\mathcal {M}_{II}|\omega _1+3|\mathcal {M}_{III}|\omega _2+4(m-1-|\mathcal {M}_{II}|-|\mathcal {M}_{III}|)\omega _3\right) \\\leqslant & {} \frac{1}{m}\left( 1+2|\mathcal {M}_{II}|\omega _1+3(m-1-|\mathcal {M}_{II}|)\omega _2\right) \leqslant \frac{1}{m}\left( 1+2(m-1)\omega _1\right) . \end{aligned}$$

Proof

By Lemmas 2(ii), 3 and 7(i),

$$\begin{aligned} \frac{C^{**}_{\min }}{C^{\delta }_{\min }}\leqslant & {} \frac{\frac{P}{m}}{L_m^\delta }=\frac{1}{m}\frac{\sum _{i=1}^m L_i^\delta }{L_m^\delta }=\frac{1}{m}\frac{L_m^\delta +\sum _{i=1}^{m-1} L_i^\delta }{L_m^\delta }\leqslant \frac{1}{m}\left( 1+\sum _{i=1}^{m-1}\frac{n_i^\delta }{n_i^\delta -1-\delta }\right) \\= & {} \frac{1}{m}\left( 1+\sum _{M_i\in \mathcal {M}_{II}}\frac{n_i^\delta }{n_i^\delta -1-\delta }+\sum _{M_i\in \mathcal {M}_{III}}\frac{n_i^\delta }{n_i^\delta -1-\delta }\right. \\{} & {} \left. +\sum _{M_i\in \mathcal {M}\setminus (\mathcal {M}_{II}\cup \mathcal {M}_{III}\cup \{M_m\})}\frac{n_i^\delta }{n_i^\delta -1-\delta }\right) \\\leqslant & {} \frac{1}{m}\left( 1+2|\mathcal {M}_{II}|\omega _1+3|\mathcal {M}_{III}|\omega _2+4(m-1-|\mathcal {M}_{II}|-|\mathcal {M}_{III}|)\omega _3\right) \\\leqslant & {} \frac{1}{m}\left( 1+2|\mathcal {M}_{II}|\omega _1+3(m-1-|\mathcal {M}_{II}|)\omega _2\right) \leqslant \frac{1}{m}\left( 1+2(m-1)\omega _1\right) . \end{aligned}$$

For any $0<\delta <1$ and $m\geqslant 2$, define

$$\begin{aligned} V'_{\delta ,m}=\frac{1}{2\lfloor \frac{m}{2}\rfloor }\left( 1+2\lfloor \frac{m}{2}\rfloor \omega _1+3\left( \lfloor \frac{m}{2}\rfloor -1\right) \omega _2\right) . \end{aligned}$$

(9)

Set $V'_{\delta ,1}=1$. We will show that $V'_{\delta ,m}$ is an improved upper bound of $V_{\delta ,m}$. As a preparation, we present some properties of the $V'_{\delta ,m}$.

Lemma 9

• (i) If m is an even number, then $V'_{\delta ,m}=V'_{\delta ,m+1}\leqslant V'_{\delta ,m+2}$.

• (ii) $V'_{\delta ,m}\geqslant \frac{1}{m}\left( 1+2\lfloor \frac{m}{2}\rfloor \omega _1+3\left( m-\lfloor \frac{m}{2}\rfloor -1\right) \omega _2\right)$.

Proof

(i) Since m is an even number, $\lfloor \frac{m}{2}\rfloor =\lfloor \frac{m+1}{2}\rfloor$. Obviously, $V'_{\delta ,m}=V'_{\delta ,m+1}$. By (9) and Lemma 7(i),

$$\begin{aligned} V'_{\delta ,m}- V'_{\delta ,m+2}= & {} \frac{1}{m}\left( 1+m\omega _1+3\left( \frac{m}{2}-1\right) \omega _2\right) -\frac{1}{m+2}\left( 1+ (m+2)\omega _1+\frac{3m}{2}\omega _2\right) \\= & {} \frac{2}{m(m+2)}+3\omega _2\left( \frac{\frac{m}{2}-1}{m}-\frac{\frac{m}{2}}{m+2}\right) =\frac{2}{m(m+2)}\left( 1-3\omega _2\right) \leqslant 0. \end{aligned}$$

(ii) If m is an even number, then $V'_{\delta ,m}=\frac{1}{m}\left( 1+2\lfloor \frac{m}{2}\rfloor \omega _1+3\left( m-\lfloor \frac{m}{2}\rfloor -1\right) \omega _2\right)$ by (9). Otherwise, $\lfloor \frac{m}{2}\rfloor =\lfloor \frac{m-1}{2}\rfloor =\frac{m-1}{2}$. By (9) and Lemma 7(ii),

$$\begin{aligned}{} & {} V'_{\delta ,m-1}-\frac{1}{m}\left( 1+2\lfloor \frac{m}{2}\rfloor \omega _1+3\left( m-\lfloor \frac{m}{2}\rfloor -1\right) \omega _2\right) \\{} & {} \quad = \frac{1}{m-1}\left( 1+(m-1)\omega _1+\frac{3}{2}\left( m-3\right) \omega _2\right) -\frac{1}{m}\left( 1+(m-1)\omega _1+\frac{3}{2}\left( m-1\right) \omega _2\right) \\{} & {} \quad = \frac{1}{m(m-1)}\left( 1+(m-1)\omega _1-\frac{3}{2}\left( m+1\right) \omega _2\right) \geqslant \frac{2m-\frac{3}{2}(m+1)}{m(m-1)}\omega _2 =\frac{m-3}{2m(m-1)}\omega _2\geqslant 0. \end{aligned}$$

Therefore, $V'_{\delta ,m}= V'_{\delta ,m-1}\geqslant \frac{1}{m}\left( 1+2\lfloor \frac{m}{2}\rfloor \omega _1+3\left( m-\lfloor \frac{m}{2}\rfloor -1\right) \omega _2\right)$ by (i).

Theorem 3

For the scheduling game on m identical machines with the social cost of maximizing the minimum machine load, the $\delta$-PoA is at most $V'_{\delta ,m}$ when $\delta <1$, and the bound is tight for $2\leqslant m \leqslant 7$.

Proof

We will prove that $V'_{\delta ,m}$ is an upper bound on the $\delta$-PoA for m machines by induction on m. Obviously, $V_{\delta ,1}=V'_{\delta ,1}=1$. Assume that the $\delta$-PoA is at most $V'_{\delta ,k}$ for any $k<m$ machines.

If there exists $i \ne m$ such that $n_i^\delta = 1$, then $\frac{C^{**}_{\min }}{C^{\delta }_{\min }}\leqslant V_{\delta , m-1}\leqslant V'_{\delta , m-1}\leqslant V'_{\delta , m}$ by Lemmas 6(i) and 9(i). Therefore, we assume that $n_i^\delta \geqslant 2$ for any $1\leqslant i\leqslant m-1$. If $|\mathcal {M}_{II}|\leqslant \lfloor \frac{m}{2}\rfloor$, then by Lemmas 8, 7(i) and 9(ii),

$$\begin{aligned} \frac{C^{**}_{\min }}{C^{\delta }_{\min }}\leqslant & {} \frac{1}{m}\left( 1+2|\mathcal {M}_{II}|\omega _1+3(m-1-|\mathcal {M}_{II}|)\omega _2\right) \\ {}\leqslant & {} \frac{1}{m}\left( 1+2\lfloor \frac{m}{2}\rfloor \omega _1+3\left( m-\lfloor \frac{m}{2}\rfloor -1\right) \omega _2\right) \leqslant V'_{\delta ,m}. \end{aligned}$$

If $|\mathcal {M}_{II}|\geqslant \lfloor \frac{m}{2}\rfloor +1$, then $|\mathcal {J}_{II}|\geqslant m+1$. Thus there exists a machine which processes at least two jobs of $\mathcal {J}_{II}$ in $\sigma ^{**}$. By Lemmas 6(ii) and 9(i), $\frac{C^{**}_{\min }}{C^{\delta }_{\min }}\leqslant V_{\delta ,m-1}\leqslant V'_{\delta ,m-1}\leqslant V'_{\delta ,m}$. The proof of the first part of the theorem is completed by induction.

The remaining part of the proof includes instances to show the bound is tight for $2\leqslant m \leqslant 7$. To prove the tightness of $m=2$, consider an instance $I_4$ consisting of two large jobs of processing time $\omega _1$ and two small jobs of processing time $\frac{1}{2}$. Clearly, $C^{**}_{\min }(I_4)=\frac{1}{2}+\omega _1$. On the other hand, consider a schedule $\sigma ^4$ that the two large jobs are scheduled on $M_1$ and the two small jobs are scheduled on $M_2$, which is an $\delta$-NE. Clearly, $L_1^4=2\omega _1>1=L_2^4$. Thus, $C^{4}_{\min }(I_4)=1$. By (8) and Lemma 1, $\sigma ^4$ is a $\delta$-NE. Hence, $\frac{C^{**}_{\min } (I_4)}{C^4_{\min } (I_4)} \geqslant \frac{1}{2}+\omega _1$, and $V_{\delta ,2}=V'_{\delta ,2}=\frac{1}{2}+\omega _1$. The tightness of $m=3$ can be obtained by Lemmas 4 and 9(i).

To prove the tightness of $m=4$, consider an instance $I_5$ consisting of four large jobs of processing time $\omega _1$, four small jobs of processing time $\omega _2$, and four tiny jobs of processing time $\frac{1}{4}(1-\omega _2)$. In the optimal schedule, each machine processes a large job, a small job and a tiny job. Thus, $C^{**}_{\min }(I_5)=\omega _1+\omega _2+\frac{1}{4}(1-\omega _2)=\frac{1}{4}+\omega _1+\frac{3}{4}\omega _2$.

On the other hand, consider a schedule $\sigma ^5$ that two large jobs are scheduled on each of the first two machines $M_1$ and $M_2$, three small jobs are scheduled on $M_3$, and the remaining jobs are scheduled on $M_4$. Clearly, by Lemma 7(i),

$$\begin{aligned} L_1^5=L_2^5=2\omega _1\geqslant 3\omega _2=L_3^5>1=\omega _2+4\cdot \frac{1}{4}(1-\omega _2)=L_4^5. \end{aligned}$$

Thus, $C^{5}_{\min }(I_5)=1$. By (8) and Lemma 1, $\sigma ^5$ is a $\delta$-NE. Hence, $\frac{C^{**}_{\min } (I_5)}{C^5_{\min } (I_5)} \geqslant \frac{1}{4}+\omega _1+\frac{3}{4}\omega _2$, and $V_{\delta ,4}=V'_{\delta ,4}=\frac{1}{4}+\omega _1+\frac{3}{4}\omega _2$. The tightness of $m=5$ can be obtained by Lemmas 4 and 9(i).

To prove the tightness of $m=6$, consider an instance $I_6$ consisting of six large jobs of processing time $\omega _1$, six small jobs of processing time $\omega _2$, and six tiny jobs of processing time $\frac{1}{6}$. In the optimal schedule, each machine processes a large job, a small job and a tiny job. Thus, $C^{**}_{\min }(I_6)=\frac{1}{6}+\omega _1+\omega _2$.

On the other hand, consider a schedule $\sigma ^6$ that two large jobs are scheduled on each of the first three machines $M_1$, $M_2$ and $M_3$, three small jobs are scheduled on each machine of $M_4$ and $M_5$, and the tiny jobs are scheduled on $M_6$. Clearly, by Lemma 7(i),

$$\begin{aligned} L_1^6=L_2^6=L_3^6=2\omega _1\geqslant 3\omega _2=L_4^6=L_5^6>1=L_6^6. \end{aligned}$$

Thus $C^{6}_{\min }(I_6)=1$. By (8) and Lemma 1, $\sigma ^6$ is a $\delta$-NE. Hence, $\frac{C^{**}_{\min } (I_6)}{C^6_{\min } (I_6)} \geqslant \frac{1}{6}+\omega _1+\omega _2$, and $V_{\delta ,6}=V'_{\delta ,6}=\frac{1}{6}+\omega _1+\omega _2$. The tightness of $m=7$ can be obtained by Lemmas 4 and 9(i).

In fact, $\frac{1}{6}+\omega _1+\omega _2$ is also the $\delta$-PoA for $8\leqslant m\leqslant 11$ machines, but is strict smaller than $V'_{\delta ,m}$. In order to get an upper bound smaller than $V'_{\delta ,m}$, we need more accurate estimates of the optimum than Lemma 2(ii), which can be achieved by examining the processing times of the jobs of $\mathcal {J}_{III}$ and the machines they are scheduled on in $\sigma ^{**}$.

Denote by $\mathcal {M}^{**}_0$ and $\mathcal {M}^{**}_1$ the subset of machines that process 0 and 1 jobs of $\mathcal {J}_{III}$ in $\sigma ^{**}$, respectively. Then

$$\begin{aligned} |\mathcal {M}^{**}_1|\geqslant 2m-|\mathcal {J}_{III}|-2|\mathcal {M}^{**}_0|. \end{aligned}$$

(10)

In fact, if $|\mathcal {M}^{**}_1|\leqslant 2\,m-|\mathcal {J}_{III}|-2|\mathcal {M}^{**}_0|-1$, there are at least $m-(2m-|\mathcal {J}_{III}|-2|\mathcal {M}^{**}_0|-1)-|\mathcal {M}^{**}_0|$ machines each of which processes at least two jobs of $\mathcal {J}_{III}$ in $\sigma ^{**}$. Then

$$\begin{aligned} |\mathcal {J}_{III}|\geqslant & {} 2(m-(2m-|\mathcal {J}_{III}|-2|\mathcal {M}^{**}_0|-1)-|\mathcal {M}^{**}_0|)\\ {}{} & {} +(2m-|\mathcal {J}_{III}|-2|\mathcal {M}^{**}_0|-1)=|\mathcal {J}_{III}|+1, \end{aligned}$$

a contradiction.

Though $L_i^\delta =p_{a_i}+p_{b_i}+p_{z_i}\leqslant 3\omega _2 L_m^\delta$ for any $M_i\in \mathcal {M}_{III}$ by Lemma 3, we cannot assert that $p_j\leqslant \omega _2 L_m^\delta$ for any $J_j\in \mathcal {J}_{III}$. To get an effective upper bound on the total processing time of a subset of $\mathcal {J}_{III}$, further classification of $\mathcal {J}_{III}$ is necessary. Let $\mathcal {J}_{IIIa}=\bigcup \limits _{M_i\in \mathcal {M}_{III}} \{J_{a_i}\}\subseteq \mathcal {J}_{III}$. Clearly, $|\mathcal {J}_{IIIa}|=|\mathcal {M}_{III}|=\frac{1}{3}|\mathcal {J}_{III}|$. For any job $J_{a_i}\in \mathcal {J}_{IIIa}$, both $J_{b_i}$ and $J_{z_i}$ are called slave jobs of $J_{a_i}$, and $\{J_{b_i}, J_{z_i}\}$ is called a companion pair of $J_{a_i}$. Meanwhile, $J_{a_i}$ is called the master job of $J_{b_i}$ or $J_{z_i}$.

In the next three lemmas, we give upper bounds on the total processing time of a subset of $\mathcal {J}_{III}$ in various situations. Together with the upper bound on the processing time of jobs of $\mathcal {J}_{II}$, we are able to derive upper bounds on the total processing time of jobs that are processed on a certain subset of machines in $\sigma ^{**}$, and then get more precise upper bounds on the $C^{**}_{\min }$.

Lemma 10

Suppose that $\mathcal {J}_{0} \subseteq \mathcal {J}_{III}$.

• (i) If for any job of $\mathcal {J}_{IIIa} \cap \mathcal {J}_{0}$, at least one of its slave job is also in $\mathcal {J}_{0}$, then $P(\mathcal {J}_{0})\leqslant |\mathcal {J}_{0}|\omega _2 L_m^\delta$.

• (ii) If $\mathcal {J}_{0}$ does not contain any companion pair, then $P(\mathcal {J}_{III}{\setminus } \mathcal {J}_{0})\leqslant |\mathcal {J}_{III}{\setminus } \mathcal {J}_{0}|\omega _2L_m^\delta$.

Proof

By Lemma 3, for any $M_i\in \mathcal {M}_{III}$, $p_{a_i}+p_{b_i}=L_i^\delta -p_{z_i}\leqslant 2\omega _2 L_m^\delta$ and thus $p_{z_i}\leqslant p_{b_i}\leqslant \omega _2 L_m^\delta$. Therefore, unless $\mathcal {J}_{0}$ contains some job of $\mathcal {J}_{IIIa}$ but does not contain any of its slave job, any two jobs of $\mathcal {J}_{0}$ has a total processing time of no more than $2\omega _2 L_m^\delta$. This clearly leads to (i). If $\mathcal {J}_{0}$ does not contain any companion pair, then whenever $\mathcal {J}_{III}\setminus \mathcal {J}_{0}$ contains a job of $\mathcal {J}_{IIIa}$, it also contains at least one of its slave jobs. (ii) can be proved by (i).

Lemma 11

If $\mathcal {J}_i^{**}$ contains a companion pair $\{J_{b_{j}}, J_{z_{j}}\}$, then $P(\mathcal {J}_{III}{\setminus } \mathcal {J}_i^{**})\leqslant (|\mathcal {J}_{III}|-3)\omega _2 L_m^\delta +p_{a_j}$, and there exists $M_k\in \mathcal {M}{\setminus } \{M_{i}\}$ such that $P(\mathcal {J}_{III}{\setminus } (\mathcal {J}^{**}_i\cup \mathcal {J}^{**}_k))\leqslant (|\mathcal {J}_{III}|-3)\omega _2 L_m^\delta$.

Proof

By Lemma 10(i),

$$\begin{aligned} P(\mathcal {J}_{III}\setminus \mathcal {J}_i^{**})\leqslant & {} P(\mathcal {J}_{III}\setminus \{J_{b_{j}}, J_{z_{j}}\})=P(\mathcal {J}_{III}\setminus \{J_{a_{j}}, J_{b_{j}}, J_{z_{j}}\})+p_{a_j}\\ {}\leqslant & {} (|\mathcal {J}_{III}|-3)\omega _2 L_m^\delta +p_{a_j}. \end{aligned}$$

If $\{J_{a_{j}}, J_{b_{j}}, J_{z_{j}}\} \subseteq \mathcal {J}_i^{**}$, then for any $M_k\in \mathcal {M}{\setminus } \{M_{i}\}$,

$$\begin{aligned} P(\mathcal {J}_{III}\setminus (\mathcal {J}^{**}_i\cup \mathcal {J}^{**}_k))\leqslant P(\mathcal {J}_{III}\setminus \mathcal {J}_i^{**})\leqslant P(\mathcal {J}_{III}\setminus \{J_{a_{j}}, J_{b_{j}}, J_{z_{j}}\})\leqslant (|\mathcal {J}_{III}|-3)\omega _2 L_m^\delta . \end{aligned}$$

Otherwise, assume that $J_{a_{j}}\in \mathcal {J}_k^{**}$, then

$$\begin{aligned} P(\mathcal {J}_{III}\setminus (\mathcal {J}^{**}_i\cup \mathcal {J}^{**}_k))\leqslant P(\mathcal {J}_{III}\setminus \{J_{a_{j}}, J_{b_{j}}, J_{z_{j}}\})\leqslant (|\mathcal {J}_{III}|-3)\omega _2 L_m^\delta . \end{aligned}$$

Lemma 12

(i) Suppose that $\mathcal {M}^S\subseteq \mathcal {M}^{**}_1$. If $\lceil \frac{1}{2}(|\mathcal {M}^S|-|\mathcal {J}_{IIIa}|)\rceil \leqslant |\mathcal {J}_{IIIa}|\leqslant |\mathcal {M}^S|$, then there exists a subset $\mathcal {M}'\subseteq \mathcal {M}^S$ with $|\mathcal {M}'|=\lceil \frac{3}{2}(|\mathcal {M}^S|-|\mathcal {J}_{IIIa}|)\rceil$ such that the total processing time of the jobs of $\mathcal {J}_{III}$ that are processed on $\mathcal {M}'$ is no more than $|\mathcal {M}'|\omega _2 L_m^\delta$.

(ii) If $2|\mathcal {J}_{IIIa}|\leqslant m-|\mathcal {M}^{**}_0|\leqslant 3|\mathcal {J}_{IIIa}|$, then there exists a subset $\mathcal {M}'\subseteq \mathcal {M}^{**}_1$ with $|\mathcal {M}'|=3m-2|\mathcal {J}_{III}|-3|\mathcal {M}^{**}_0|$ such that the total processing time of the jobs of $\mathcal {J}_{III}$ that are processed on $\mathcal {M}'$ is no more than $|\mathcal {M}'|\omega _2 L_m^\delta$.

Proof

(i) The subset $\mathcal {M}'$ can be constructed as follows. Initially set $\mathcal {M}'=\varnothing$. Obviously, there are $|\mathcal {M}^S|-|\mathcal {J}_{IIIa}|$ machines of $\mathcal {M}^S$ that do not process any job of $\mathcal {J}_{IIIa}$. Add these machines to $\mathcal {M}'$ and denote the set of the remaining $|\mathcal {J}_{IIIa}|$ machines of $\mathcal {M}^S$ by $\mathcal {M}^C$. Select $\lceil \frac{1}{2}(|\mathcal {M}^S|-|\mathcal {J}_{IIIa}|)\rceil$ jobs from the jobs of $\mathcal {J}_{III}$ that are processed on the machines of $\mathcal {M}^S \setminus \mathcal {M}^C$, such that no two jobs belong to the same companion pair. Since $|\mathcal {M}^S|-|\mathcal {J}_{IIIa}|$ jobs of $\mathcal {J}_{III}\setminus \mathcal {J}_{IIIa}$ belong to at least $\lceil \frac{1}{2}(|\mathcal {M}^S|-|\mathcal {J}_{IIIa}|)\rceil$ different companion pairs, the selection is feasible and the subset of the selected jobs is denoted $\mathcal {J}'$. For each job of $\mathcal {J}'$, if its master job is processed on a machine of $\mathcal {M}^C$, add this machine to $\mathcal {M}'$ and delete it from $\mathcal {M}^C$. If its master job is not processed on the machines of $\mathcal {M}^C$, select an arbitrary machine of $\mathcal {M}^C$ that does not process any job of $\mathcal {J}_{IIIa}$, and add the machine to $\mathcal {M}'$ and delete it from $\mathcal {M}^C$. Since $|\mathcal {M}^C|=|\mathcal {J}_{IIIa}|\geqslant \lceil \frac{1}{2}(|\mathcal {M}^S|-|\mathcal {J}_{IIIa}|)\rceil$, the required machines can always be found. At the end of the process, there are $\lceil \frac{3}{2}(|\mathcal {M}^S|-|\mathcal {J}_{IIIa}|)\rceil$ machines in $\mathcal {M}'$. For any job of $\mathcal {J}_{IIIa}$ that is processed on the machines of $\mathcal {M}'$, at least one of its slave jobs is also processed on the machines of $\mathcal {M}'$. By Lemma 10(i), the total processing time of the jobs of $\mathcal {J}_{III}$ that are processed on $\mathcal {M}'$ is no more than $|\mathcal {M}'|\omega _2 L_m^\delta$.

(ii) By (10), $|\mathcal {M}^{**}_1|\geqslant 2\,m-|\mathcal {J}_{III}|-2|\mathcal {M}^{**}_0|$. Let $\mathcal {M}^S$ be an arbitrary subset of $\mathcal {M}^{**}_1$ with $|\mathcal {M}^S|=2m-|\mathcal {J}_{III}|-2|\mathcal {M}^{**}_0|$. By (i), there exists a subset $\mathcal {M}'\subseteq \mathcal {M}^S$ with

$$\begin{aligned} |\mathcal {M}'|= & {} \lceil \frac{3}{2}(|\mathcal {M}^S|-|\mathcal {J}_{IIIa}|)\rceil =\lceil \frac{3}{2}(2m-|\mathcal {J}_{III}|-2|\mathcal {M}^{**}_0|-|\mathcal {J}_{IIIa}|)\rceil \\ {}= & {} 3m-2|\mathcal {J}_{III}|-3|\mathcal {M}^{**}_0|, \end{aligned}$$

and the total processing time of the jobs of $\mathcal {J}_{III}$ that are processed on $\mathcal {M}'$ is no more than $|\mathcal {M}'|\omega _2 L_m^\delta$.

So far we have done all the preparation, we will show the exact value of the $\delta$-PoA for $8\leqslant m \leqslant 11$ in two theorems.

Theorem 4

For the scheduling game on 8 and 9 identical machines with the social cost of maximizing the minimum machine load, the $\delta$-PoA is $\frac{1}{6}+\frac{1}{1-\delta }+\frac{1}{2-\delta }$ when $\delta <1$.

Proof

Note that $V_{\delta ,7}=\frac{1}{6}+\omega _1+\omega _2$ by Theorem 3. We only need to show that $V_{\delta ,m}\leqslant \frac{1}{6}+\omega _1+\omega _2$ for $8\leqslant m\leqslant 9$. If there exists $i \ne m$ such that $n_i^\delta = 1$, or there exists at least a machine which processes at least two jobs of $\mathcal {J}_{II}$ in $\sigma ^{**}$, then $\frac{C^{**}_{\min } (I)}{C^\delta _{\min } (I)} \leqslant V_{\delta , m-1}$ by Lemma 6(i) and Lemma 6(ii). Assume in the following that $n_i^\delta \geqslant 2$ for any $1\leqslant i\leqslant m-1$ and each machine processes at most one job of $\mathcal {J}_{II}$ in $\sigma ^{**}$. Thus, $|\mathcal {M}_{II}|\leqslant \lfloor \frac{m}{2}\rfloor =4$.

If $|\mathcal {M}_{II}|\leqslant 3$, then by Lemmas 8 and 7(i)(v)(vii),

$$\begin{aligned} \frac{C^{**}_{\min }}{C^{\delta }_{\min }}\leqslant & {} \frac{1}{m}\left( 1+2|\mathcal {M}_{II}|\omega _1+3(m-1-|\mathcal {M}_{II}|)\omega _2\right) \\ {}\leqslant & {} \frac{1}{m}\left( 1+6\omega _1+3(m-4)\omega _2\right) \leqslant \frac{1}{6}+\omega _1+\omega _2. \end{aligned}$$

If $|\mathcal {M}_{II}|=4$ and $|\mathcal {M}_{III}|\leqslant m-6$, then by Lemmas 8 and 7(i)(vii),

$$\begin{aligned} \frac{C^{**}_{\min }}{C^{\delta }_{\min }}\leqslant & {} \frac{1}{m}\left( 1+2|\mathcal {M}_{II}|\omega _1+3|\mathcal {M}_{III}|\omega _2+4(m-1-|\mathcal {M}_{II}|-|\mathcal {M}_{III}|)\omega _3\right) \\\leqslant & {} \frac{1}{m}\left( 1+8\omega _1+3(m-6)\omega _2+4\omega _3\right) \leqslant \frac{1}{6}+\omega _1+\omega _2. \end{aligned}$$

We are left with the case of $|\mathcal {M}_{II}|=4$ and $|\mathcal {M}_{III}|=m-5$. Then, $\mathcal {J}=\mathcal {J}_{m}^\delta \cup \mathcal {J}_{II}\cup \mathcal {J}_{III}$ and $|\mathcal {J}_{II}|=8$, $|\mathcal {J}_{III}|=3(m-5)$.

For the case of $m=8$, each machine processes exactly one job of $\mathcal {J}_{II}$ with processing time of no more than $\omega _1 L_m^\delta$ in $\sigma ^{**}$. Since $|\mathcal {J}_{III}|=9$, there must be a machine, say $M_1$, which processes at least two jobs of $\mathcal {J}_{III}$ in $\sigma ^{**}$. If $\mathcal {J}_1^{**}$ does not contain any companion pair, then by Lemma 10(ii), $P(\mathcal {J}_{III}{\setminus } \mathcal {J}_1^{**})\leqslant |\mathcal {J}_{III}{\setminus } \mathcal {J}_1^{**}|\omega _2 L_m^\delta \leqslant 7\omega _2 L_m^\delta$. Even if all the jobs of $\mathcal {J}_{m}^\delta$ are processed on $\mathcal {M}{\setminus } \{M_{1}\}$, we still have

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{7}\sum _{i=2}^{8}L_i^{**}\leqslant \frac{1}{7}\left( L_m^\delta +7\omega _1 L_m^\delta +7\omega _2 L_m^\delta \right) =\frac{1}{7}\left( 1+7\omega _1 +7\omega _2 \right) L_m^\delta \\ {}\leqslant & {} \left( \frac{1}{6}+\omega _1 +\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

If $\mathcal {J}_1^{**}$ contains a companion pair, then there exists a machine, say $M_8$, such that $P(\mathcal {J}_{III}{\setminus } (\mathcal {J}^{**}_1\cup \mathcal {J}^{**}_8))\leqslant 6\omega _2 L_m^\delta$ by Lemma 11. Thus even if all the jobs of $\mathcal {J}_{m}^\delta$ are processed on $\mathcal {M}{\setminus } \{M_{1},M_{8}\}$, we still have

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{6}\sum _{i=2}^{7}L_i^{**}\leqslant \frac{1}{6}\left( L_m^\delta +6\omega _1 L_m^\delta +6\omega _1 L_m^\delta \right) =\frac{1}{6}\left( 1+6\omega _1 +6\omega _2 \right) L_m^\delta \\ {}= & {} \left( \frac{1}{6}+\omega _1+\omega _2\right) C^{\delta }_{\min }. \end{aligned}$$

Combining the above analysis with $V_{\delta ,7}=\frac{1}{6}+\omega _1+\omega _2$, we have $V_{\delta ,8}=\frac{1}{6}+\omega _1+\omega _2$.

For the case of $m=9$, by Lemmas 2(ii), 10(i) and 7(vi),

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{P}{9}\leqslant \frac{1}{9}\left( L_m^\delta +8\omega _1 L_m^\delta +12\omega _2 L_m^\delta \right) \\ {}= & {} \left( \frac{1}{9}+\frac{8}{9}\omega _1+\frac{4}{3}\omega _2\right) L_m^\delta \leqslant \left( \frac{1}{6}+\omega _1+\omega _2\right) C^{\delta }_{\min }. \end{aligned}$$

Combining the above analysis with $V_{\delta ,8}=\frac{1}{6}+\omega _1+\omega _2$, we have $V_{\delta ,9}=\frac{1}{6}+\omega _1+\omega _2$.

Theorem 5

For the scheduling game on 10 and 11 identical machines with the social cost of maximizing the minimum machine load, the $\delta$-PoA is $\frac{1}{6}+\frac{1}{1-\delta }+\frac{1}{2-\delta }$ when $\delta <1$.

Proof

Note that $V_{\delta ,9}=\frac{1}{6}+\omega _1+\omega _2$ by Theorem 4. We only need to show that $V_{\delta ,m}\leqslant \frac{1}{6}+\omega _1+\omega _2$ for $10\leqslant m\leqslant 11$. If there exists $i \ne m$ such that $n_i^\delta = 1$, or there exists at least a machine which processes at least two jobs of $\mathcal {J}_{II}$ in $\sigma ^{**}$, then $\frac{C^{**}_{\min } (I)}{C^\delta _{\min } (I)} \leqslant V_{\delta , m-1}$ by Lemma 6(i) and Lemma 6 (ii). Assume in the following that $n_i^\delta \geqslant 2$ for any $1\leqslant i\leqslant m-1$ and each machine processes at most one job of $\mathcal {J}_{II}$ in $\sigma ^{**}$. Thus $|\mathcal {M}_{II}|\leqslant \lfloor \frac{m}{2}\rfloor =5$.

If $|\mathcal {M}_{II}|\leqslant 4$, then by Lemmas 8 and 7(i)(viii),

$$\begin{aligned} \frac{C^{**}_{\min }}{C^{\delta }_{\min }}\leqslant & {} \frac{1}{m}\left( 1+2\omega _1|\mathcal {M}_{II}|+3\omega _2(m-1-|\mathcal {M}_{II}|)\right) \leqslant \frac{1}{m}\left( 1+8\omega _1+3(m-5)\omega _2\right) \\ {}\leqslant & {} \frac{1}{6}+\omega _1+\omega _2. \end{aligned}$$

Therefore, we assume that $|\mathcal {M}_{II}|=5$ in the rest of the proof.

First consider the case of $m=10$. Then each machine processes exactly one job of $\mathcal {J}_{II}$ with processing time of no more than $\omega _1 L_m^\delta$ in $\sigma ^{**}$. We distinguish several subcases according to the value of $|\mathcal {M}_{III}|$.

If $|\mathcal {M}_{III}|\leqslant 2$, then by Lemmas 8 and 7(iv),

$$\begin{aligned} \frac{C^{**}_{\min }}{C^{\delta }_{\min }}\leqslant & {} \frac{1}{10}\left( 1+2\omega _1|\mathcal {M}_{II}|+3\omega _2 |\mathcal {M}_{III}|+4\omega _3 (m-1-|\mathcal {M}_{II}|-|\mathcal {M}_{III}|)\right) \\\leqslant & {} \frac{1}{10}\left( 1+10\omega _1+6\omega _2+8\omega _3\right) =\frac{1}{10}+\omega _1+\frac{3}{5}\omega _2+\frac{4}{5}\omega _3\leqslant \frac{1}{6}+\omega _1+\omega _2. \end{aligned}$$

If $|\mathcal {M}_{III}|=3$, then let $k<m$ and $M_{k}\notin \mathcal {M}_{II} \cup \mathcal {M}_{III}$. Thus $\mathcal {J}=\mathcal {J}_{m}^\delta \cup \mathcal {J}_{k}^\delta \cup \mathcal {J}_{II}\cup \mathcal {J}_{III}$ and $L_{k}^\delta \leqslant 4\omega _3 L_m^\delta$ by Lemma 3. Consider the assignment of 9 jobs of $\mathcal {J}_{III}$ in $\sigma ^{**}$. If $|\mathcal {M}^{**}_0|\geqslant 4$, then even if all the jobs of $\mathcal {J}_{m}^\delta \cup \mathcal {J}_{k}^\delta$ are processed on $\mathcal {M}^{**}_0$, we still have

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{|\mathcal {M}^{**}_0|}\sum _{M_i\in \mathcal {M}^{**}_0} L_i^{**}\leqslant \frac{1}{|\mathcal {M}^{**}_0|}\left( L_m^\delta +4\omega _3 L_m^\delta +|\mathcal {M}^{**}_0|\omega _1 L_m^\delta \right) \\\leqslant & {} \left( \frac{1}{4}+\omega _1+\omega _3\right) L_m^\delta \leqslant \left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }, \end{aligned}$$

by Lemma 7(iii). If $2\leqslant |\mathcal {M}^{**}_0|\leqslant 3$, by Lemma 12(ii), there exists a subset $\mathcal {M}'\subseteq \mathcal {M}^{**}_1$ with $|\mathcal {M}'|=3m-2|\mathcal {J}_{III}|-3|\mathcal {M}^{**}_0|=12-3|\mathcal {M}^{**}_0|$ such that the total processing time of the jobs of $\mathcal {J}_{III}$ that are processed on $\mathcal {M}'$ is no more than $|\mathcal {M}'|\omega _2 L_m^\delta$. By Lemma 7(i)(iii), even if all the jobs of $\mathcal {J}_{m}^\delta \cup \mathcal {J}_{k}^\delta$ are processed on $\mathcal {M}'\cup \mathcal {M}^{**}_0$, we still have

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{12-2|\mathcal {M}^{**}_0|}\sum _{M_i\in \mathcal {M}'\cup \mathcal {M}^{**}_0} L_i^{**} \\\leqslant & {} \frac{1}{12-2|\mathcal {M}^{**}_0|}\left( L_m^\delta +4\omega _3 L_m^\delta +(12-2|\mathcal {M}^{**}_0|)\omega _1 L_m^\delta +(12-3|\mathcal {M}^{**}_0|)\omega _2 L_m^\delta \right) \\= & {} \left( \omega _1+\omega _2+\frac{1}{12-2|\mathcal {M}^{**}_0|}\left( 1+4\omega _3-|\mathcal {M}^{**}_0|\omega _2 \right) \right) L_m^\delta \\\leqslant & {} \left( \omega _1+\omega _2+\frac{1}{8}\left( 1+4\omega _3-2\omega _2 \right) \right) L_m^\delta \\= & {} \left( \frac{1}{8}+\omega _1+\frac{3}{4}\omega _2+\frac{1}{2}\omega _3\right) L_m^\delta \leqslant \left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

Therefore, it is sufficient to assume that $|\mathcal {M}^{**}_0|=1$ and each machine of $\mathcal {M}\setminus \{M_{10}\}$ processes exactly one job of $\mathcal {J}_{III}$ in $\sigma ^{**}$. We further discuss below the number of jobs of $\mathcal {J}_{k}^\delta$ and the machines that they are processed on in $\sigma ^{**}$.

If $n_{k}^\delta \geqslant 5$, then by Lemma 3, $L_{k}^\delta -p_{z_{k}}\leqslant 4\omega _4 L_m^\delta$. If no job of $\mathcal {J}_{k}^\delta$ is processed on $\mathcal {M}{\setminus } \{M_{10}\}$ in $\sigma ^{**}$, then by Lemma 10(i),

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{9}\sum _{i=1}^{9} L_i^{**}\leqslant \frac{1}{9}\left( L_m^\delta +9\omega _1 L_m^\delta +9\omega _2 L_m^\delta \right) =\left( \frac{1}{9}+\omega _1+\omega _2\right) L_m^\delta \\ {}\leqslant & {} \left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

Otherwise, assume that some jobs of $\mathcal {J}_{k}^\delta$ are processed on $M_1$ in $\sigma ^{**}$. Then, the total processing time of the jobs of $\mathcal {J}_{k}^\delta$ that are processed on $\mathcal {M}\setminus \{M_{1}\}$ is no more than $4\omega _4 L_m^\delta$. By Lemmas 10(i) and 7(ix),

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{9}\sum _{i=2}^{10} L_i^{**}\leqslant \frac{1}{9}\left( L_m^\delta +4\omega _4 L_m^\delta +9\omega _1 L_m^\delta +8\omega _2 L_m^\delta \right) \\= & {} \left( \frac{1}{9}+\omega _1+\frac{8}{9}\omega _2+\frac{4}{9}\omega _4\right) L_m^\delta \leqslant \left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

We are left with the case of $n_{k}^\delta =4$.

If no job of $\mathcal {J}_{k}^\delta$ is processed on $M_{10}$ in $\sigma ^{**}$, then there exist at least 5 machines of $\mathcal {M}\setminus \{M_{10}\}$ that do not process any job of $\mathcal {J}_{k}^\delta$, and 3 machines among them, say $M_7, \cdots , M_{9}$, process jobs of $\mathcal {J}_{III}$ with a total processing time of no more than $3\omega _2 L_m^\delta$ by Lemma 12(i). Then by Lemma 7(iii),

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{4}\sum _{i=7}^{10} L_i^{**}\leqslant \frac{1}{4}\left( L_m^\delta +4\omega _1 L_m^\delta +3\omega _2 L_m^\delta \right) =\left( \frac{1}{4}+\omega _1+\frac{3}{4}\omega _2\right) L_m^\delta \\ {}\leqslant & {} \left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

If exactly one job of $\mathcal {J}_{k}^\delta$ is processed on $M_{10}$ in $\sigma ^{**}$, then there are 6 machines of $\mathcal {M}\setminus \{M_{10}\}$ that do not process any job of $\mathcal {J}_{k}^\delta$, and 5 machines among them, say $M_5, \cdots , M_{9}$, process jobs of $\mathcal {J}_{III}$ with a total processing time of no more than $5\omega _2 L_m^\delta$ by Lemma 12(i). If $p_{a_{k}}\leqslant \omega _2 L_m^\delta$, then

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{6}\sum _{i=5}^{10} L_i^{**}\leqslant \frac{1}{6}\left( L_m^\delta +\omega _2 L_m^\delta +6\omega _1 L_m^\delta +5\omega _2 L_m^\delta \right) =\left( \frac{1}{6}+\omega _1+\omega _2\right) L_m^\delta \\ {}= & {} \left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

Otherwise, we have

$$\begin{aligned} \omega _2 L_m^\delta +2p_{z_{k}}< p_{a_{k}}+2p_{z_{k}}\leqslant L_{k}^\delta -p_{z_{k}}\leqslant L_m^\delta +\delta p_{z_{k}} \end{aligned}$$

(11)

by (1). Thus,

$$\begin{aligned} p_{z_{k}}\leqslant \frac{1}{2-\delta }(1-\omega _2)L_m^\delta =\omega _2(1-\omega _2)L_m^\delta =\omega _2\left( 1-\frac{1}{2-\delta }\right) L_m^\delta \leqslant \frac{1}{2}\omega _2 L_m^\delta . \end{aligned}$$

Combining the above inequality with (11), we have

$$\begin{aligned} L_{k}^\delta -p_{z_{k}}\leqslant L_m^\delta +\delta p_{z_{k}}\leqslant L_m^\delta +\frac{1}{2}\delta \omega _2 L_m^\delta =\left( 1+\frac{1}{2}\delta \omega _2\right) L_m^\delta = \left( \frac{1}{2}+\omega _2\right) L_m^\delta . \nonumber \\ \end{aligned}$$

(12)

Assume that $M_1$ processes at least one job of $\mathcal {J}_{k}^\delta$ in $\sigma ^{**}$. By Lemma 10(i), the total processing time of jobs of $\mathcal {J}_{III}$ that are processed on $\mathcal {M}\setminus \{M_1\}$ is no more than $8\omega _2 L_m^\delta$. Then by (12),

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{9}\sum _{i=2}^{10} L_i^{**}\leqslant \frac{1}{9}\left( L_m^\delta +L_{k}^\delta -p_{z_{k}}+9\omega _1 L_m^\delta +8\omega _2 L_m^\delta \right) \\\leqslant & {} \frac{1}{9}\left( 1+\frac{1}{2}+\omega _2+9\omega _1 +8\omega _2 \right) L_m^\delta =\left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

If at least two jobs of $\mathcal {J}_{k}^\delta$ are processed on $M_{10}$ in $\sigma ^{**}$, then there are at least 7 machines of $\mathcal {M}\setminus \{M_{10}\}$ that do not process any job of $\mathcal {J}_{k}^\delta$, and 6 machines among them, say $M_4, \cdots , M_{9}$, process jobs of $\mathcal {J}_{III}$ with a total processing time of no more than $6\omega _2 L_m^\delta$ by Lemma 12(i). Then,

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{6}\sum _{i=4}^{9} L_i^{**}\leqslant \frac{1}{6}\left( L_m^\delta +6\omega _1 L_m^\delta +6\omega _2 L_m^\delta \right) =\left( \frac{1}{6}+\omega _1+\omega _2\right) L_m^\delta \\ {}= & {} \left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

If $|\mathcal {M}_{III}|=4$, consider the assignment of 12 jobs of $\mathcal {J}_{III}$ in $\sigma ^{**}$. If $|\mathcal {M}^{**}_0|\geqslant 2$, then by Lemma 7(iii),

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{|\mathcal {M}^{**}_0|}\sum _{M_i\in \mathcal {M}^{**}_0} L_i^{**}\leqslant \frac{1}{|\mathcal {M}^{**}_0|}\left( L_m^\delta +|\mathcal {M}^{**}_0|\omega _1 L_m^\delta \right) \leqslant \left( \frac{1}{2}+\omega _1\right) L_m^\delta \\ {}\leqslant & {} \left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

If $|\mathcal {M}^{**}_0|\leqslant 1$, by Lemma 12(ii), there exists a subset $\mathcal {M}'\subseteq \mathcal {M}^{**}_1$ with $|\mathcal {M}'|=3m-2|\mathcal {J}_{III}|-3|\mathcal {M}^{**}_0|=6-3|\mathcal {M}^{**}_0|$ such that the total processing time of the jobs of $\mathcal {J}_{III}$ that are processed on $\mathcal {M}'$ is no more than $|\mathcal {M}'|\omega _2 L_m^\delta$. By Lemma 7(i), we have

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{6-2|\mathcal {M}^{**}_0|}\sum _{M_i\in \mathcal {M}'\cup \mathcal {M}^{**}_0} L_i^{**}\\ {}\leqslant & {} \frac{1}{6-2|\mathcal {M}^{**}_0|}\left( L_m^\delta +(6-2|\mathcal {M}^{**}_0|)\omega _1 L_m^\delta +(6-3|\mathcal {M}^{**}_0|)\omega _2 L_m^\delta \right) \\= & {} \left( \omega _1+\omega _2+\frac{1}{6-2|\mathcal {M}^{**}_0|}\left( 1-|\mathcal {M}^{**}_0|\omega _2 \right) \right) L_m^\delta \leqslant \left( \frac{1}{6}+\omega _1+\omega _2\right) L_m^\delta \\ {}= & {} \left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

So far, all the cases of $m=10$ have been discussed. Combining the above analysis with $V_{\delta ,9}=\frac{1}{6}+\omega _1+\omega _2$, we have $V_{\delta ,10}=\frac{1}{6}+\omega _1+\omega _2$.

Next consider the case of $m=11$. We assume that each machine of $\mathcal {M}\setminus \{M_{11}\}$ processes a job of $\mathcal {J}_{II}$ with processing time no more than $\omega _1 L_m^\delta$ in $\sigma ^{**}$. If $|\mathcal {M}_{III}|\leqslant 4$, then by Lemmas 8 and 7(x),

$$\begin{aligned} \frac{C^{**}_{\min }}{C^{\delta }_{\min }}\leqslant & {} \frac{1}{11}\left( 1+2\omega _1|\mathcal {M}_{II}|+3\omega _2 |\mathcal {M}_{III}|+4\omega _3 (m-1-|\mathcal {M}_{II}|-|\mathcal {M}_{III}|)\right) \\\leqslant & {} \frac{1}{11}\left( 1+10\omega _1+12\omega _2+4\omega _3\right) \leqslant \frac{1}{6}+\omega _1+\omega _2. \end{aligned}$$

In the following, we assume that $|\mathcal {M}_{III}|=5$. Thus, $\mathcal {J}=\mathcal {J}_{m}^\delta \cup \mathcal {J}_{II}\cup \mathcal {J}_{III}$ and $|\mathcal {J}_{III}|=15$.

If there exists $M_i\in \mathcal {M}_{III}$, such that $p_{a_i}\geqslant \frac{4}{3}\omega _2 L_m^\delta$, then by Lemma 3, $p_{z_i}\leqslant p_{b_i}\leqslant \frac{2}{3}\omega _2 L_m^\delta$ and $L_i^\delta =L_i^\delta -p_{z_i}+p_{z_i}\leqslant 2\omega _2 L_m^\delta +\frac{2}{3}\omega _2 L_m^\delta =\frac{8}{3}\omega _2 L_m^\delta$. Thus, by Lemmas 2(ii), 10(i) and 7(x),

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{P}{11}\leqslant \frac{1}{11}\left( L_m^\delta +P(\mathcal {J}_{II})+P(\mathcal {J}_{III}\setminus \mathcal {J}_{i}^\delta )+L_i^\delta \right) \\ {}\leqslant & {} \frac{1}{11}\left( L_m^\delta +10\omega _1 L_m^\delta +12\omega _2 L_m^\delta + \frac{8}{3}\omega _2 L_m^\delta \right) \\= & {} \frac{1}{11}\left( 1+10\omega _1+\frac{44}{3}\omega _2\right) L_m^\delta \leqslant \left( \frac{1}{6}+\omega _1+\omega _2\right) C^{\delta }_{\min }. \end{aligned}$$

Hence, we assume in the following that $p_{a_i}<\frac{4}{3}\omega _2 L_m^\delta$ for any $M_i\in \mathcal {M}_{III}$.

Suppose that there exists a machine of $\mathcal {M}{\setminus } \{M_{11}\}$, say $M_1$, which processes at least two jobs of $\mathcal {J}_{III}$ in $\sigma ^{**}$. If $\mathcal {J}_1^{**}$ does not contain any companion pair, then $P(\mathcal {J}_{III} {\setminus } \mathcal {J}_1^{**})\leqslant 13\omega _2 L_m^\delta \leqslant \frac{40}{3}\omega _2 L_m^\delta$ by Lemma 10(ii). Otherwise, $P(\mathcal {J}_{III} {\setminus } \mathcal {J}_1^{**})\leqslant 12\omega _2 L_m^\delta +\frac{4}{3}\omega _2 L_m^\delta =\frac{40}{3}\omega _2 L_m^\delta$ by Lemma 11. Therefore, by Lemma 7(vi),

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{10}\sum _{i=2}^{11} L_i^{**}\leqslant \frac{1}{10}\left( L_m^\delta +9\omega _1 L_m^\delta +\frac{40}{3}\omega _2 L_m^\delta \right) \\= & {} \frac{1}{10}\left( 1+9\omega _1+\frac{40}{3}\omega _2\right) L_m^\delta \leqslant \left( \frac{1}{6}+\omega _1+\omega _2\right) C^{\delta }_{\min }. \end{aligned}$$

We are left with the case that each machine of $\mathcal {M}{\setminus } \{M_{11}\}$ processes at most one job of $\mathcal {J}_{III}$ in $\sigma ^{**}$. Then, $\mathcal {M}^{**}_0\cup \mathcal {M}^{**}_1=\mathcal {M}{\setminus } \{M_{11}\}$. If $|\mathcal {M}^{**}_0|\geqslant 2$, then by Lemma 7(iii),

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{|\mathcal {M}^{**}_0|}\sum _{M_i\in \mathcal {M}^{**}_0} L_i^{**}\leqslant \frac{1}{|\mathcal {M}^{**}_0|}\left( L_m^\delta +|\mathcal {M}^{**}_0|\omega _1 L_m^\delta \right) \leqslant \left( \frac{1}{2}+\omega _1\right) L_m^\delta \\ {}\leqslant & {} \left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

If $|\mathcal {M}^{**}_0|=1$, then by Lemma 12(i), there are 6 machines of $\mathcal {M}{\setminus } \{M_{11}\}$, say $M_5, \cdots , M_{10}$, process jobs of $\mathcal {J}_{III}$ with a total processing time of no more than $6\omega _2 L_m^\delta$. Thus,

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{6}\sum _{i=5}^{10} L_i^{**}\leqslant \frac{1}{6}\left( L_m^\delta +6\omega _1 L_m^\delta +6\omega _2 L_m^\delta \right) \\ {}= & {} \left( \frac{1}{6}+\omega _1+\omega _2\right) L_m^\delta =\left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

If $|\mathcal {M}^{**}_0|=0$, then by Lemma 12(i), there are 8 machines of $\mathcal {M}{\setminus } \{M_{11}\}$, say $M_3, \cdots , M_{10}$, process jobs of $\mathcal {J}_{III}$ with a total processing time of no more than $8\omega _2 L_m^\delta$. Thus

$$\begin{aligned} C^{**}_{\min }\leqslant & {} \frac{1}{8}\sum _{i=3}^{10} L_i^{**}\leqslant \frac{1}{8}\left( L_m^\delta +8\omega _1 L_m^\delta +8\omega _2 L_m^\delta \right) =\left( \frac{1}{8}+\omega _1+\omega _2\right) L_m^\delta \\ {}\leqslant & {} \left( \frac{1}{6}+\omega _1+\omega _2 \right) C^{\delta }_{\min }. \end{aligned}$$

All the cases of $m=11$ have been discussed. Combining the above analysis with $V_{\delta ,10}=\frac{1}{6}+\omega _1+\omega _2$, we have $V_{\delta ,11}=\frac{1}{6}+\omega _1+\omega _2$.

At the end of the paper, we present a lower bound for $m\geqslant 12$ machines.

Theorem 6

For the scheduling game on $m\geqslant 12$ identical machines with the social cost of maximizing the minimum machine load, the $\delta$-PoA is at least $\frac{1}{12}+\frac{1}{1-\delta }+\frac{1}{2-\delta }+\frac{7}{12(6-\delta )}$ when $\delta <1$.

Proof

Consider an instance $I_7$ consisting of 12 huge jobs of processing time $\omega _1$, 12 large jobs of processing time $\omega _2$, 5 medium jobs of processing time $\frac{1}{12}+\frac{7}{12}\omega _6$, 7 small jobs of processing time $\omega _6$, and 7 tiny jobs of processing time $\frac{1}{12}-\frac{5}{12}\omega _6$. In the optimal schedule, each of the first 5 machines processes a huge job, a large job and a medium job. Each of the last 7 machines processes a huge job, a large job, a small job and a tiny job. Thus, $C^{**}_{\min }(I_7)=\frac{1}{12}+\omega _1+\omega _2+\frac{7}{12}\omega _6$.

On the other hand, consider a schedule $\sigma ^7$ that two huge jobs are scheduled on each machines of $M_1, \cdots , M_6$, three large jobs are scheduled on each machine of $M_7, \cdots , M_{10}$. All the small jobs are processed on $M_{11}$, and the medium and the tiny jobs are scheduled on $M_{12}$. Clearly, by Lemma 7(i),

$$\begin{aligned} L_1^7=\cdots =L_6^7=2\omega _1\geqslant 3\omega _2=L_7^7=\cdots =L_{10}^7>L_{11}^7>1=7\omega _6=L_{12}^7. \end{aligned}$$

Thus, $C^{7}_{\min }(I_7)=1$. By (8) and Lemma 1, $\sigma ^7$ is a $\delta$-NE. Hence, $\frac{C^{**}_{\min } (I_7)}{C^7_{\min } (I_7)} \geqslant \frac{1}{12}+\omega _1+\omega _2+\frac{7}{12}\omega _6$, and $V_{\delta ,m}\geqslant \frac{1}{12}+\frac{1}{1-\delta }+\frac{1}{2-\delta }+\frac{7}{12(6-\delta )}$ for $m\geqslant 12$.