The cost of selfishness for maximizing the minimum load on uniformly related machines

Abstract

Consider the following scheduling game. A set of jobs, each controlled by a selfish agent, are to be assigned to m uniformly related machines. The cost of a job is defined as the total load of the machine that its job is assigned to. A job is interested in minimizing its cost, while the social objective is maximizing the minimum load (the value of the cover) over the machines. This goal is different from the regular makespan minimization goal, which was extensively studied in a game theoretic context.

We study the price of anarchy (poa) and the price of stability (pos) for uniformly related machines. The results are expressed in terms of s, which is the maximum speed ratio between any two machines. For uniformly related machines, we prove that the pos is unbounded for s>2, and the poa is unbounded for s≥2. For the remaining cases we show that while the poa grows to infinity as s tends to 2, the pos is at most 2 for any s≤2.

1 Introduction

Job scheduling games have been widely studied in recent years. In this work, we consider the problem of maximizing the minimum load, seeing jobs as selfish agents who are only interested in their own costs. For applications of this problem and related models see Epstein et al. (2009), Koutsoupias and Papadimitriou (1999).

The model of scheduling on uniformly related machines is defined as follows. A set of n jobs J={1,2,…,n} is to be assigned to a set of m machines M={1,…,m}, where machine i has a speed s _i . If s _i =1 for i=1,…,m, then the machines are called identical. Without loss of generality, we assume 1=s ₁≤s ₂≤⋯≤s _m =s. The value s is called the speed ratio, and it is the maximum speed ratio between any pair of machines. The size of job k (for 1≤k≤n) is denoted by p _k . An assignment or schedule is a function $\mathcal {A}:J\rightarrow M$. Thus $\mathcal {A}(k)$, also denoted by $\mathcal {A}_{k}$, is the index of the machine that job k is assigned to. The load of machine i, which is also called the delay of this machine, is $L_{i}(\mathcal {A})=\sum_{k:\mathcal {A}_{k}=i} \frac{p_{k}}{s_{i}}$. The value, or the social value of a schedule $\mathcal {A}$ is the minimum delay of any machine, also known as the value of the cover. We denote it by $\mbox {\textsc {cover}}(\mathcal {A})$. We study the problem of maximizing the value of the cover (Deuermeyer et al. 1982). This problem is dual to the makespan scheduling problem (Graham 1969).

The non-cooperative machine covering game MC is characterized by a tuple $MC=\langle N,(\mathcal{M}_{k})_{k\in N}$, (c _k ) _k∈N 〉, where N is the set of atomic players. Each player k∈N controls a single job of size p _k >0 and selects the machine to which it will be assigned. We associate each player with the job it wishes to run, that is, N=J. The set of strategies $\mathcal{M}_{k}$ for each job k∈N is the set M of all machines, i.e., $\mathcal{M}_{k}=M$. Each job must be assigned to one machine, and preemption is not allowed (i.e., the set of choices of jobs result in a schedule as it is defined above). The outcome of the game is an assignment of jobs to the machines, where $\mathcal {A}_{k}$ for each 1≤k≤n is the index of the machine that job k chooses to run on. Let $\mathcal {S}$ denote the set of all possible assignments. The cost function of job k∈N is denoted by $c_{k}:\mathcal {S}\rightarrow \mathbb{R}$. The cost $c_{k}(\mathcal {A})$ charged from job k running on machine i in a given assignment $\mathcal {A}$ (a job k such that $\mathcal {A}_{k}=i$) is defined to be the load observed by machine i in this assignment, that is, $\displaystyle c_k(\mathcal {A})=L_i(\mathcal {A})$. The goal of each (selfish) job is to run on a machine with a load which is as small as possible. An assignment $\mathcal {A}$ is a (pure) Nash equilibrium (NE), if every job k satisfies the following. Let $i=\mathcal {A}_{k}$. There cannot exist a machine i′≠i for which $L_{i'}(\mathcal {A})+\frac{p_{k}}{s_{i'}}<L_{i}(\mathcal {A})$. That is, a schedule is an NE, if no job can obtain a lower cost by changing its strategy while all other jobs keep their strategies unchanged. For this selfish goal of players, a pure NE (with deterministic agent choices) always exists (Fotakis et al. 2009; Even-Dar et al. 2007).

In our scheduling model, the coordination ratio, or price of anarchy (poa) (Roughgarden 2005) is the worst case ratio between the social value (i.e., the minimum delay of any machine, or the value of the cover) of an optimal schedule, denoted by opt, and the social value of any NE. If both these values are 0 then we define the poa to be 1. The price of stability (pos) (Anshelevich et al. 2008) is the worst case ratio between the social value of an optimal solution, and the social value of the best NE. Similarly, if both these values are 0 then we define the pos to be 1. The poa and pos can be defined for one game (a specific instance of jobs and machines), but also for the complete set of games, or for subclasses of games. We let poa(m,s) and pos(m,s) denote the poa and pos, respectively, for games with m uniformly related machines where 1=s ₁≤s ₂≤⋯≤s _m =s. We also let poa(m)=poa(m,1), and pos(m)=pos(m,1), that is, the poa and the pos for all games on identical machines, as functions of the number of machines.

The non-selfish version of the problem has been well studied (known by different names such as “machine covering” and the “Santa Claus problem”) in the computer science literature (see e.g. Deuermeyer et al. 1982; Bansal and Sviridenko 2006; Ebenlendr et al. 2005; Epstein et al. 2011). Various game-theoretic aspects of max-min fairness in resource allocation games were considered, but unlike the makespan minimization problem for which the poa and the pos were extensively studied (see Koutsoupias and Papadimitriou 1999; Czumaj and Vöcking 2007; Mavronicolas and Spirakis 2007), these measures were not previously considered for the uncoordinated machine covering problem in the setting of selfish jobs and uniformly related machines. A different model, where machines are selfish rather than jobs (with the same social goal function) was studied recently in Epstein and van Stee (2010), Dhangwatnotai et al. (2011), Epstein et al. (2012).

In Epstein et al. (2009), we considered the problem for identical machines. We showed that the pos is equal to 1 for every game. Additionally, we showed close bounds on the poa for the complete set of games, namely, that it is at least 1.691 and at most 1.7. For small numbers of machines we showed that $\mbox {\textsc {poa}}(2)=\mbox {\textsc {poa}}(3)=\frac{3}{2}$ and $\mbox {\textsc {poa}}(4)=\frac {13}{8}$.

In contrast to these results, we can show that for uniformly related machines even the pos for the complete set of instances is unbounded. This holds already for pos(2,s) such that s>2, and poa(2,s) is unbounded already for s≥2. The same property holds for m machines and the same speed ratios, that is pos(m,s) is unbounded for any m≥2 and s>2, and poa(m,s) is unbounded for any m≥2 and s≥2. We present examples proving these last properties (see also Epstein et al. 2009). We show that pos(m,s) is at most 2 if s≤2, and $\mbox {\textsc {poa}}(m,s)=\varTheta(\frac{1}{2-s})$ if s<2. These results are very different from the situation for the makespan minimization social goal. For that problem, the pos is 1 for every game. Czumaj and Vöcking (2007) showed that the overall poa is $\varTheta(\frac{\log m}{\log \log m})$ (see also Feldmann et al. 2003; Koutsoupias and Papadimitriou 1999). Note that for identical machines, the results given in Epstein et al. (2009) are more similar to the situation for makespan minimization, where the pos is 1 for every game, and the poa(m) is constant (Finn and Horowitz 1979; Schuurman and Vredeveld 2007).

Kleiman (2011) provided additional results for two machines. First, it is shown in this dissertation that we can restrict our analysis of poa(2,s) to instances involving no more than four jobs. Thus, we only need to consider a small number of cases corresponding to the identity of non-zero sized jobs, and to the machine which defines the value of the objective function in the worst NE. For each of these cases a linear program (LP) is formulated whose optimal objective function value is equal to poa(2,s) for any s (or for some subinterval of s, depending on the case) for a suitable subclass of instances. The function poa(2,s) for each resulting subinterval is the maximum of these values. It is possible to find the tight values by presenting a primal optimal solution and a dual optimal solution for each of these linear programs (and their dual programs). The idea for this analysis is motivated by the classic paper by Graham (1969), where a similar approach to analyze the performance of an algorithm for a variant of the makespan minimization problem for m identical machines was used. Kleiman (2011) also presented upper bounds for pos(2,s) showing that it is at most $\frac{3}{2}$ (for s≤2).

2 The case s≥2

We show that for sufficiently large speed ratios, sup _s≥1 poa(m,s) and sup _s≥1 pos(m,s) are unbounded for any m≥2. Recall that 1=s ₁≤⋯≤s _m =s. The following result was already claimed in Epstein et al. (2009); here we present a full proof.

Theorem 1

For any m≥2 and s>2, pos(m,s)=∞. For any m≥2 and s≥2, poa(m,s)=∞.

Proof

Consider a set of uniformly related machines with speed ratio s. We show that if s>2, then the ratio between cover(opt) the value of the cover of any NE is unbounded, and if s≥2, then the ratio between cover(opt) the minimum value of the cover of any NE is unbounded. This is slightly stronger than the statement, since we show the property for every set of m machines rather than for one specific set of m machines.

Assume s>2, and consider an instance that contains m jobs, each of size s. It is not hard to see that for this input cover(opt)=1. We show that any assignment where each job is assigned to a distinct machine is not an NE. Such assignments are the only ones for which the value of the cover is positive. In fact, in such an assignment, the job assigned to the first machine has cost s, while if it moves to the m-th machine, its load becomes $\frac{2s}{s}=2<s$. Thus, any NE assignment has a value of 0 and the claim follows.

Assume s=2, and consider the assignment $\mathcal {A}$ (of the job set defined above) where each machine is assigned a single job, except that the first machine has no jobs, and the m-th machine has two jobs. It is not difficult to see that this is an NE. Each job assigned to the m-th machine will not move to the first machine since it will have the same cost after moving. It would not move to another machine since it would be assigned there together with another job, and this machine is not faster than its current machine. A job assigned to any machine out of 2,3,…,m−1 would not move to the first machine, since it is not faster. Moving to a machine which has at least one job assigned to it would result in load of at least 2, while the current load of the machine of this job is at most 2. Thus, we have presented an instance for which cover(opt)=1 and $\mbox {\textsc {cover}}(\mathcal {A})=0$, which implies the claim for s=2. □

3 The price of anarchy for s≤2

Next, we characterize the situation in all other cases, which were not considered in the previous section. We can show that if we let ε=2−s, then poa(m,s) grows with 1/ε. For the upper bound, we define a weight function g(x) to be applied on sizes of jobs.

The next claim is obvious.

Claim 2

Let I be a set of jobs. The total size of jobs in I is at least 1 if and only if their total weight is at least 1. In addition, if their total weight is strictly larger than 1, then |I|≥2.

Theorem 3

Let 0<ε<1. Then $\mbox {\textsc {poa}}(m,2-\varepsilon )=\varTheta(\frac{1}{\varepsilon })$.

Proof

Consider an instance with cover(opt)=1, and an arbitrary NE assignment $\mathcal {A}$ for this instance. Let P be the least loaded machine in $\mathcal {A}$, and let W denote the total weight of jobs assigned to P (if no job is assigned to P, then W=0). Recall that s _P denotes the speed of machine P. We use Claim 2 to analyze the input. If W≥1, then the total size of jobs is at least 1, thus the load of P is at least $\frac{1}{s_{P}} \geq \frac{1}{2}$.

If W<1, then since every machine in opthas a load of at least 1 and all speeds are at least 1, each such machine has a total size of jobs of at least 1 and thus weight of at least 1 as well. Therefore, the total weight of all jobs is at least m. Therefore, as W<1, there exists a machine in $\mathcal {A}$ with a total weight of jobs strictly above 1, and thus at least two jobs assigned to it. Denote this machine by Q (and its speed by s _Q ).

Let p denote the total size of jobs assigned to P and let q denote the total size of jobs assigned to Q. Since the total weight of jobs assigned to Q is above 1, we have q≥1. Let a be the size of a smallest size job assigned to Q (and thus q≥2a). Since the job of size a has no incentive to move to machine P, we have $\frac{p+a}{s_{P}} \geq \frac{q}{s_{Q}}$ or equivalently, $\frac{p}{s_{P}}>\frac{q}{s_{Q}}-\frac{a}{s_{P}}\geq \frac{q}{2-\varepsilon }-a$, using 1≤s _P and s _Q ≤2−ε.

If $a\geq \frac{1}{3}$, then using q≥2a we have $\frac{q}{2-\varepsilon }-a\geq \frac{2a-2a+a\varepsilon }{2-\varepsilon } \geq \frac{\varepsilon }{6}$. If $a < \frac{1}{3}$, then we have $\frac{q}{2-\varepsilon }-a\geq \frac{1}{6}$, since q≥1. Thus the load of P is Ω(ε), and since cover(opt)=1, we have a ratio of $O(\frac{1}{\varepsilon })$.

For the lower bound, consider an instance with m identical large jobs, each of size s=2−ε, and one small job of size ε. We analyze the schedule which assigns one large job to each machine, except for machine m which receives two such jobs, and machine 1 which receives the small job.

Similar to the proof of Theorem 1, the large jobs assigned to machines 2,3,…,m−1 have no incentive to move. Similarly, the jobs assigned to machine m have no incentive to move to any machine, except for possibly the first machine. We have $\frac{2s}{s}=2 = s+\varepsilon$, and therefore these jobs do not have an incentive to move. Finally, the small job would not move since every machine except for machine 1 is already loaded by at least 1. For this instance, cover(opt)≥1, while $\mbox {\textsc {cover}}(\mathcal {A})=\varepsilon$. □

4 The price of stability for s≤2

In this section we show that pos(m,s) is finite for any m≥2 and any s≤2. For this purpose we use a well-known algorithm for scheduling, called lpt (see Graham 1969). This algorithm sorts the jobs in a non-increasing order of their sizes, and greedily assigns each job to the machine which would have a smaller load (taking the speed into account) as a result of assignment of the job. We use a special case of lpt which acts as follows. In a case of a tie (that is, if according to the assignment rule, a job could be assigned to multiple machines, each of which would have the same load if the job is assigned to it), it prefers a machine with a smaller load before the assignment. If there are multiple machines having the same load before the assignment, then it assigns the job to the machine which has the largest index among the candidate machines (recall that machines are sorted by non-decreasing speed).

Claim 4

For any sorted input, if there are at least m jobs in the input, then for s≤2, lpt assigns the i-th job (for 1≤i≤m) to machine m−i+1.

Proof

Consider a sorted input, where the size of the j-th job is denoted by p _j , and we have p ₁≥p ₂≥⋯≥p _m . We show the claim by induction. We prove that the first job is assigned to the m-th machine. At the time of its arrival all machines have load zero. Thus the algorithm chooses one of the fastest machines, and machine m is one of them. If there is a unique fastest machine, then this is machine m. Otherwise, if there are multiple fastest machines, then the fastest machine of largest index is chosen, and this is machine m as well. Assume now that jobs 1,2,…,k−1 (2≤k≤m) have been assigned as claimed. Consider the k-th job (of size p _k ). If the machine to which this job is assigned is chosen among the machines of indices 1,2,…,m−k+1, then (as these machines received no jobs so far) this is a machine of maximum speed out of these machines. This is machine m−k+1 is there is a unique such machine, and if there are multiple such machines, then machine m−k+1 is one of them, and it has the maximum index among such machines. Otherwise, if the job is assigned to one of the machines m−k,…,m, then the resulting load must be strictly smaller than the load that would have resulted from assigning job k to machine m−k+1 (since machines with smaller load before the assignment are preferred). Assume by contradiction that the job is assigned to machine ℓ>m−k+1. By the inductive hypothesis, this machine has exactly one job at this time, which is job m−ℓ+1. The resulting load would become $\frac{p_{m-\ell+1}+p_{k}}{s_{\ell}} \geq p_{k}$ (since p _m−ℓ+1≥p _k and s _ℓ ≤2). The load resulting from assigning the job to machine m−k+1 is $\frac{p_{k}}{s_{m-k+1}}\leq p_{k}$, which is a contradiction. □

It is known that for scheduling games on uniformly related machines with the same selfish goal of the players as here, lptproduces an NE schedule (Fotakis et al. 2009). Given the tie-breaking rule, for a given sorted list of jobs, and a sorted list of machines, this algorithm has exactly one possible output for each input. The value of the pos is upper-bounded by its approximation ratio (for our goal function). This is one of the tools which we use in order to derive an upper bound on the pos.

Theorem 5

For m≥2, if s≤2, then pos(m,s)≤2.

Proof

We will show that for every set of uniformly related machines with speed ratio s, the ratio between the value of the cover in an optimal solution and the value of the cover in the best NE is no larger than 2.

In this proof we will neglect instances for which the value of the optimal cover is zero; for every such instance every NE is an optimal solution. By normalizing all remaining instances, we may assume the optimal cover of an instance has a value of 1. We will call such instances valid instances. It is sufficient to analyze the pos on valid instances.

Suppose that at least one valid counterexample instance (ordered sets of jobs and machines, where the speeds of machines are in [1,2]) exists for some m≥2, for which the value of the cover of every NE is strictly below 1/2. Thus, since lpt always creates an NE schedule, for such an instance lpt creates a schedule in which there is at least one machine with load strictly below 1/2. We conclude that there exists a valid instance for which lpt creates a schedule with at least one machine of load strictly below 1/2. We call such an instance a counterexample for lpt. In what follows, we only discuss counterexamples for lpt. Let m denote the number of machines in one such counterexample.

Consider all valid instances for m machines (of speeds in [1,2]), for which the value of the cover of the schedule created by lpt is strictly below 1/2 (as explained above, this set is non-empty). Let T be the infimum total size of jobs among all valid counterexamples for the considered number of machines m. Given the machine speeds and the value of the optimal cover, the total size of the jobs in all counterexamples is at least m, and thus such a positive infimum value must exist. Let I be a counterexample for which the total size of all the jobs is at most T+1/(16m). We assume that the jobs of I are sorted such that p ₁≥p ₂≥… , and that lpt is applied on the jobs in this order (of indices). Consider the NE assignment $\mathcal {A}$ which is defined by the lpt assignment of the jobs in I. We will derive a contradiction from the property that there is a machine of load strictly below $\frac{1}{2}$ in $\mathcal {A}$. This will be done by defining an alternative valid instance I′, which is fairly similar to I, but the total size of jobs in it will be strictly below T. We will show that the value of the cover created by applying lpt on the alternative instance is the same as the one for I (that is, the same as in $\mathcal {A}$), while the value of the cover of an optimal solution remains 1. This will contradict the choice of T, since I′ is a valid instance for m machines where the value of the cover in the schedule created by lpt is strictly below $\frac{1}{2}$, but the total size of jobs is below T.

Claim 6

The input I satisfies 0<p _m <1.

Proof

Since the value of the optimal cover is 1, there are at least m jobs of positive sizes. On the other hand, assume by contradiction p _m ≥1. By Claim 4, lpt assigns a job of an index in {1,2,…,m} to every machine. Specifically, we find that the load of machine i will be at least $\frac{p_{m-i+1}}{s_{i}} \geq \frac{1}{2}$, since p _m−i+1≥1, and s _i ≤2. This contradicts the assumption that the value of the cover of $\mathcal {A}$ is strictly below 1/2. □

Let P be the least loaded machine in $\mathcal {A}$. By assumption, the load of P is less than 1/2. We show in the next claim that the set of machines with loads at least 1 remains fixed once the first m jobs have been assigned (until lpt terminates), and other machines will have loads below 1 in $\mathcal {A}$.

Claim 7

During the run of lpt on I, the set of machines with load at least 1 is fixed after the first m jobs have been assigned. These machines do not receive further jobs.

Proof

By the definition of lpt, P received one of the m largest jobs (by Claim 4). After this and until lpt is done, P had load of less than 1/2 (since this is its final load). Jobs of indices m+1,… have sizes no larger than the first job assigned to P, so any additional single job that P could have received after its first job would increase the load of P to less than 1. This means that no assignment of any later job j increases a load of any machine to at least 1 once each machine has a job, because lpt would assign such a job j to P instead. For the same reason, a machine which already has a load of at least 1 cannot receive any later job. □

We next show that there is a machine in $\mathcal {A}$ with load at least 1+1/(4m). Let Q′ be a machine of maximum load in $\mathcal {A}$.

Claim 8

Q′ has load at least 1+1/(4m), and Q′>1.

Proof

To prove the first claim, assume by contradiction that it does not hold, and every machine has load less than 1+1/(4m), whereas P has load less than 1/2. Based on $\mathcal {A}$, the total size of all jobs is at most

since s _P ≥1, and s _i ≤2 for all i. On the other hand, since cover(opt)=1, the total size of all the jobs must be at least $\sum_{i=1}^{m} s_{i}$. This is a contradiction.

If Q′=1, then since by Claims 4 and 7 the load of machine 1 is above 1 already after it receives job m, we have p _m ≥(1+1/(4m))s ₁>1. This contradicts Claim 6. □

Let 1≤Q≤m−1 be such that m−Q+1 is a machine in $\mathcal {A}$ with load of at least $1+\frac{1}{4m}$. Such a machine exists by Claim 8. Let $x=p_{Q} \geq (1+\frac{1}{4m})\cdot s_{m-Q+1} \geq 1+\frac{1}{4m}$. We modify I into an instance I′ as follows. The instance contains a job of size $x-\frac{1}{8m}$ instead of job Q, while the other jobs are not modified. The sorted order for I′ is based on the ordering for I, with the only change that the job of reduced size being moved to its proper position. If there are at least two possible positions, that is, I contains at least one job of size $x-\frac{1}{8m}$, then the job of reduced size is inserted to be the last job in the ordering out of jobs of size $x-\frac{1}{8m}$. We will show that the value of the optimal cover for I′ is at least 1. Thus, since I′ results from I by decreasing the size of a job, the value of the optimal cover for I′ cannot be above 1, and it will follow that the value of the optimal cover for I′ is exactly 1, which will imply that I′ is a valid instance.

Lemma 9

Consider an optimal schedule opt for I (whose value of the cover is 1). There exists a schedule for I′ whose value of cover is at least 1.

Proof

We show how to modify opt into the required schedule for I′. Seeing this schedule as a schedule for I′, since the only difference between I and I′ is the size of Q, the only machine of load below 1 may be the machine on which Q is scheduled.

Case 1. Job Q is assigned to a machine i∈{1,…,m−Q+1} in opt.

We use the same schedule for I′, and show that the load of machine i is at least 1 even with the modified size of Q. In this schedule the load of i is at least $\frac{x-\frac{1}{8m}}{s_{i}} \geq \frac{x-\frac{1}{8m}}{s_{m-Q+1}}=\frac{x}{s_{m-Q+1}}-\frac{1}{8m\cdot s_{m-Q+1}}\geq 1+\frac{1}{4m}-\frac{1}{8m}>1$, since s _i ≤s _m−Q+1, $\frac{x}{s_{m-Q+1}} \geq 1+\frac{1}{4m}$, and s _m−Q+1≥1.

Case 2. Job Q is assigned to a machine i′∈{m−Q+2,…,m} in opt, but there exists a job j<Q assigned to a machine i∈{1,…,m−Q+1} in opt.

Create a schedule for I′ which is identical to opt, and swap the locations of Q and j. As in the previous case, the machine i that receives Q will have load above 1 in this schedule. Since p _j ≥x, the load of machine i′ is at least its load in opt (for I).

Case 3. Jobs 1,…,Q are assigned to machines m−Q+2,…,m in opt.

The number of these machines is Q−1, while the number of jobs is Q. Thus, there exists a machine i∈{m−Q+2,…,m} which has at least two jobs out of jobs 1,…,Q in opt.

Case 3.1. Job Q is assigned to i.

We use opt as a schedule for I′. The load of i in this schedule is at least $\frac{x+(x-\frac{1}{8m})}{s_{i}} \geq \frac{2+\frac{3}{8m}}{s_{i}}$, as the size of every job in {1,…,Q−1} is at least $x \geq 1+\frac{1}{4m}$. Using s _i ≤2 we find that the load of i is above 1.

Case 3.2. Job Q is assigned to a machine i′≠i, i′∈{m−Q+2,…,m}.

Machine i has job j<Q (and at least one other job out of 1,…,Q−1). We create a schedule from opt by swapping the locations of jobs Q and j. The load of the machine i′ which receives j instead of Q is at least its load in opt (for I), since p _j ≥x. Machine i has two jobs of the two sizes $x-\frac{1}{8m}$, and at least x. As in Case 3.1, its load is above 1. □

Let $\mathcal {A}'$ be the schedule resulting from running lpt on I′.

Claim 10

A machine has load of at least 1 in $\mathcal {A}$ if and only if it has load of at least 1 in $\mathcal {A}'$. A machine of load below 1 has the same set of jobs in both $\mathcal {A}$ and $\mathcal {A}'$.

Proof

By Claim 4 (which holds for any run of lpt), the first m jobs are assigned to m distinct machines for both schedules. Clearly, the job whose size was reduced may be assigned later by lpt (for I′ compared to I), as its position in the sorted order may change, and thus this job may be assigned to a machine of a smaller index in $\mathcal {A}'$. Note that in this discussion p _j still refers to the size of job j in I, and the jobs indices are as in I. Let 1≤r≤m be such that $p_{j} \geq x-\frac{1}{8m}$ for j≤r, and $p_{j} < x-\frac{1}{8m}$ for j>r. We have r≥Q, since for j≤Q, $p_{j} \geq p_{Q} > x-\frac{1}{8m}$, and r<m since $x-\frac{1}{8m} \geq 1+\frac{1}{4m}-\frac{1}{8m}>1$, while p _m <1 by Claim 6. Thus, in the new ordering of jobs, the job of modified size is still one of the m−1 first jobs, but it may be assigned to a machine of lower index (in $\mathcal {A}'$), as explained above. Specifically, in $\mathcal {A}'$, for 1≤j≤Q−1, machine m−j+1 has job j, machine m−r+1 has the job of modified size (job Q), for Q≤j≤r−1, machine m−j+1 has job j+1, and for r+1≤j≤m, machine m−j+1 has job j.

By Claim 7, the set of machines of load at least 1 in $\mathcal {A}$ is determined for I by the machines having such a load after the first m jobs were assigned. Consider the assignment of the first m jobs by lpt for I and for I′. We will show that after the first m jobs were scheduled, the machines m−r+1,…,m−Q+1 have loads of at least 1 in both schedules. Each remaining machine receives exactly the same job (with the same size) in both schedules. The speed of every machine m−r+1≤i≤m−Q+1 satisfies s _i ≤s _m−Q+1. In both schedules, these machines receive jobs of sizes at least $x-\frac{1}{8m}$; these are jobs Q,…,r (where job Q has a different size in I′). Since $\frac{x}{s_{m-Q+1}} \geq 1+\frac{1}{4m}$, we find $\frac{x-\frac{1}{8m}}{s_{m-Q+1}} \geq 1+\frac{1}{4m}-\frac{1/(8m)}{s_{m-Q+1}} > 1$, since s _m−Q+1≥1. Using s _i ≤s _m−Q+1 for m−r+1≤i≤m−Q+1 we find $\frac{x-\frac{1}{8m}}{s_{i}} >1$, and thus no matter which job of size at least $x-\frac{1}{8m}$ is assigned to which machine, all these machines have loads above 1.

We prove that the assignment of the remaining jobs (after the first m jobs) by lpt is identical for the two inputs. Assume by contradiction that it is not, and let k>m be the first job assigned differently. Since in $\mathcal {A}$, machine P has load below $\frac{1}{2}$ at termination, this is also the case after the first m jobs have been assigned. Machine P cannot be one of the machines m−r+1≤i≤m−Q+1, since they have load above 1 in both schedules after m jobs have been assigned. Thus, P has the same job (with the same size) in both $\mathcal {A}$ and $\mathcal {A}'$ after m jobs have been assigned. Jobs m+1,…,k−1 are assigned in $\mathcal {A}'$ as in $\mathcal {A}$, so the load of P remains below $\frac{1}{2}$ just before k is assigned (in both schedules). Similar to the proof of Claim 7, k cannot be assigned to a machine of load of at least 1 (neither for I nor for I′), and thus it is assigned to one of the machines that have exactly the same jobs in both schedules at that time. Since the algorithm has a fixed tie-breaking rule, it must act in the same way for both I and I′, which means that k is assigned as in $\mathcal {A}$, which is a contradiction. □

Thus, we find that machine P has load below $\frac{1}{2}$ in $\mathcal {A}'$ as well. A contradiction was reached, and thus we have proved the theorem.  □

We note that unlike poa(m,s) which continuously grows from constant values to infinite values as a function of s, pos(m,s) jumps from a constant value for s=2 to ∞ for s>2.