Adv Syst Sci Appl 2017; 4:61–77 Published online at http://ijassa.ipu.ru/ojs/ijassa/article/view/518 Price of Anarchy for Maximizing the Minimum Machine Load Yulia. V. Chirkova Institute of Applied Mathematical Research, Karelian Research Centre RAS, Petrozavodsk, Russia Abstract: The maximizing the minimum machine delay game (or cover game) with uniformly related machines is considered. Players choose machines with different speeds to run their jobs trying to minimize job’s delay, i.e. the chosen machine’s completion time. The social payoff is the minimal delay over all machines. For the general case of N machines we found the lower bound for Price of Anarchy (PoA), and for the case of 3 machines we found its exact value. We proved that the PoA does not change or increases when an additional third machine is included into the system with two machines. Also we propose a method of computation the PoA value and illustrate it for 3 machines. Keywords: Nash equilibrium, maximizing the minimum load, cover game, price of anarchy 1. INTRODUCTION Load balancing represents a major problem in networks and distributed computing systems, since load optimization guarantees efficient resource utilization. Modern systems such as telecommunication networks, cloud computing systems, GRID, etc. consist of independent components, in many cases without their centralized control. Particularly, users located at nodes and data transmission protocols do not interact with each other for maintaining a certain load level. Furthermore, in practice they demonstrate egoistic behavior with respect to free resources. And global optimization methods often become inapplicable due to the infeasibility of realizing optimal resource utilization plans in such systems (server request schedules, capacity norms of data transmission channels and so on). The game-theoretic approach allows treating load balancing as a game, where players have egoistic behavior and can reach some equilibrium state such that none of them benefits from unilateral deviation from a chosen strategy. System efficiency is assessed by comparing the above equilibria with the global optimum. The present paper focuses on the maximizing the minimum machine delay game (or cover game) [1–3] also known as the scheduling problem [4] in the form of a game equivalent to the KP-model (see [5, 6]) with parallel different-capacity channels where system optimization is the maximizing the minimum machine delay [1–3] instead of the minimization the maximum machine delay (makespan). It is necessary to distribute several jobs of various volumes among machines of nonidentical speeds. The volume of a job is its completion time on a free unit- speed machine. Machine load is the total volume of jobs executed by a given machine. The ratio of machine load and speed defines its delay, i.e., the job completion time at this machine. Each player chooses a machine for its job striving to minimize job’s delay. Players have egoistic behavior and reach a Nash equilibrium, viz., a job distribution such that none of them benefits from unilateral change of a chosen machine. In the sequel, we study pure strategies Nash equilibria only; as is well-known [7, 8], such an equilibrium always exists ∗Corresponding author: julia@krc.karelia.ru http://ijassa.ipu.ru/ojs/ijassa/article/view/518 62 Y.V. CHIRKOVA in the described class of games. The system payoff (also called the social payoff) is the minimum delay over all machines for an obtained job distribution. The price of anarchy [1] (PoA) is defined as the maximum ratio of the optimal social payoff and the social payoff in the worst-case Nash equilibrium. The problem where the system tries to maximize the minimum delay over all machines appears from the concept of a fair resource sharing and efficient routing of traffic. The paper [1] first in the equilibrium efficiency studying for such model gives motivations coming from issues of Quality of Service, fair resource allocation, and fair queuing. The base idea is that each system component must be loaded as much as possible and not to idle. Consider an example where each player pays the system a value which equals his delay for his job processing. Fair system should not have privileged players who pay rather less than others due to successful machine choose. Also such system should not have machines providing small or zero payoff. According to the earlier publications, the PoA in the maximizing the minimum machine delay games with pure strategies can be estimated by • for N ≥ 2 machines with speeds 1 ≤ · · · ≤ s [1] the price of anarchy is not limited if s ≥ 2; • the price of anarchy is closed to and no more than 1.7 for any number of homogeneous machines [1, 9]; • the price of anarchy equals{ 2+s (1+s)(2−s) for 1 ≤ s ≤ √ 2, 2 s(2−s) for √ 2 < s < 2 for two machines with speeds 1 ≤ s [2]; • the price of anarchy equals 2 + s 2(2− s) for 1 ≤ s < 2 for three machines with speeds 1 = 1 ≤ s [2]; • the price of anarchy equals 1+s s for 1 ≤ s ≤ s0, 2+s (1+s)(2−s) for s0 < s ≤ √ 2, 2 s(2−s) for √ 2 < s < 2 in the hierarchical model of two machines with speeds 1 ≤ s and two types of jobs where first machine can process both types jobs and second machine can process only second type jobs [3]. Here s0 is the largest root of the equation 1+s s = 2+s (1+s)(2−s) . In what follows, we derive a lower estimate for the PoA in the case of N ≥ 3 machines. Also we present the exact value of the PoA for 3 machines with speeds 1 ≤ r ≤ s < 2:{ 2+s (1+r)(2−s) for rs ≤ 2, 2 r(2−s) for rs > 2. Moreover we show that the PoA increases or does not change under new machine inclusion into the system of two machines. In the case of N machines, a computing algorithm of the exact PoA value is proposed based on solving a series of linear programming problems. The algorithm is described for the case of 3 machines and is implemented numerically in the form of a program which draws the curves of the PoA as a function of the fastest machine and compares them with the curves of the corresponding estimates. Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) PRICE OF ANARCHY FOR MAXIMIZING THE MINIMUM MACHINE LOAD 63 2. THE MODEL Consider a system S = S(N, v) composed of N machines operating with speeds v1 = 1 ≤ · · · ≤ vN = s. Note that such choose of machine speeds does not contradict with generality since one always can normalize speeds dividing them by the speed of the slowest machine. The system is used by a set of players U = U(n,w): each of n players chooses an appropriate machine for its job execution. For player j, the volume of job equals wj , j = 1, . . . , n. Denote by W = n∑ j=1 wj the total volume of all jobs. Free machine i with speed vi executes a job of volume w during the time w/vi. Study the following pure strategies game Γ =< S(N, v), U(n,w), λ >. Each player can choose any machine. The strategy of player j is machine lj selected by this player for its job execution. Then the strategy profile in the game Γ represents the vector L = (l1, . . . , ln). The load of machine i, i.e., the total volume of all jobs assigned to the machine is defined by δi(L) = ∑ j=1,...,n:lj=i wj . The delay of machine i takes the form λi(L) = ∑ j=1,...,n:lj=i wj/vi = δi(L) vi . Actually, this quantity is the same for all players selecting a given machine. We suppose that the goal of the system is minimizing of the least busy machine idling, that is maximizing of its working time or delay on it. The social payoff is described by the minimum delay over all machines: SC(L) = min i=1,...,N λi(L). Designate by OPT = OPT (S, U) = max L is a profile in Γ(S,U,λ) SC(L) the optimal payoff (the social payoff in the optimal case) where maximization runs over all admissible strategy profiles in the game Γ(S, U, λ). A strategy profile L such that none player benefits from unilateral deviation (change of the machine chosen in L for its job execution) is a pure strategies Nash equilibrium. To provide a formal definition, let L(j → i) = (l1, . . . , lj−1, i, lj+1, . . . , ln) signify the profile obtained from a profile L if player j replaces machine lj chosen by it in the profile L for another machine i, whereas the rest players use the same strategies as before (remain invariable). Definition 2.1: A strategy profile L is said to be a pure strategies Nash equilibrium iff each player chooses a machine with the minimum delay, i.e., for each player j = 1, . . . , n we have the inequality λlj(L) ≤ λi(L(j → i)) for all machines i = 1, . . . , N . Definition 2.2: The price of anarchy in the system S is the maximum ratio of the social payoff in the optimal case and the social payoff in the worst-case Nash equilibrium: PoA(S) = max U OPT (S, U) min L is a Nash equilibrium in Γ(S,U,λ) SC(L) . Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) 64 Y.V. CHIRKOVA 3. THE GENERAL CASE OF N MACHINES In this section we give the following assumptions and results which will be employed in further analysis. Consider a system composed of N ≥ 2 machines operating with speeds v1 = 1 ≤ · · · ≤ vN = s. If the number of jobs n is less than the number of machines N then obviously the social payoff is zero in any profile. In this case we assume by definition that the ratio of an optimal payoff to an equilibrium payoff is 1. Further we suppose that n ≥ N . If s ≥ 2 then the price of anarchy is infinite [1]. Therefore, we assume 1 ¡ s ¡ 2 in the following. If the number of jobs n is more than or equals the number of machines N then obviously all machines are loaded in an optimal profile. Moreover in this case all machines are loaded in any equilibrium. The optimal social payoff is not larger than the social payoff in the case when the whole volume of jobs is distributed among machines proportionally to their speeds so that all machines have an identical delay: OPT ≤ W N∑ i=1 vi . (3.1) Further we determine estimates for equilibrium delays and volumes for some jobs processed on machines. We also restate the proof for results taken from cited papers for the sake of completeness. Lemma 3.1: [2] If the number of jobs n is not less than the number of machinesN then in any equilibrium the load of any machine is more than zero. Proof Consider an arbitrary equilibrium profile L. Suppose that some machine i has zero load. Then there is a machine k receiving not more than two jobs. Since v1 = 1 ≤ · · · ≤ vN = s < 2 then vi > vk 2 . Let wk be the minimal job volume on k. If it moves to an idle machine i then its load becomes equal wk vi < 2wk vk ≤ λk(L), that is less comparing with its load in the profile L. Denote the number of jobs on some machine k in a profile L by nk. Lemma 3.2: [2] Suppose that L is a Nash equilibrium profile and SC(L) = λi(L). If nk > vk vi then λk(L) ≤ nkvi nkvi−vk λi(L) for any machine k. Proof Let w be the job with the smallest volume on some machine k. Then w ≤ vk nk λk(L). Since L is an equilibrium then λk(L) ≤ λi(L) + w vi ≤ λi(L) + vk nkvi and thus λk(L) ≤ nkvi nkvi−vk λi(L). Lemma 3.3: Suppose that L is an equilibrium profile and SC(L) = λi(L) and consider an arbitrary machine k. If nk ≥ 2 and 1 ≤ vk vi < 2 then the volume wj of any job j on the machine k is at most vivk 2vi−vk λi(L). Moreover the total volume of remaining jobs on k is also no more than vivk 2vi−vk λi(L). Proof Let the machine k receive two or more jobs and w be the minimal job volume on k. Then Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) PRICE OF ANARCHY FOR MAXIMIZING THE MINIMUM MACHINE LOAD 65 the total volume of remaining jobs on k equals vkλk(L)− w. Since L is an equilibrium then λk(L) = vkλk(L) vk ≤ λi(L) + w vi and thus vkλk(L)− w ≤ vkλi(L) + ( vk vi − 1 ) w ≤ vkλi(L) + ( vk vi − 1 ) wj:lj=k ≤ vkλi(L) + ( vk vi − 1 ) (vkλk(L)− w). Then w ≤ wj:lj=k ≤ vkλk(L)− w ≤ vivk 2vi−vk λi(L). The next theorem determines the lower estimate for the price of anarchy in the system of N ≥ 3 machines. The estimate is determined by speeds of 3 machines in the system: the first one and the second one which are the slowest, and the last one which is the fastest. Theorem 3.1: For the system composed of N ≥ 3 machines having speeds v1 = 1 ≤ v2 = r ≤ v3 ≤ · · · ≤ vN = s < 2 the price of anarchy is at least est(r, s) = min{ 2 + s (1 + r)(2− s) , 2 r(2− s) }. (3.2) Proof As far as we need to prove the lower estimate it suffices to present examples of systems providing ratios of the optimal payoff and the worst-case equilibrium payoff given in the theorem condition. Suppose that in the system each machine i has a speed vi for each i = 1, . . . , N . 1. Let first rs ≤ 2. Then est(r, s) = 2+s (1+r)(2−s) . Consider the set of jobs: w1 = w2 = (1 + r)s, wi3 = vi(2 + s), where i = 3 . . . , N , w4 = 2r − s, w5 = 2− rs. In the equilibrium LmachineN receives jobsw1 andw2, each machine i− 1 receives each jobwi3, i = 3 . . . , N , jobs w4 and w5 are assigned to machine 1. We need to show that L is really an equilibrium and find the system payoff. The loads of machines N and 1 equal 2s(1 + r) and (1 + r)(2− s) respectively. The load of each machine i = 2, . . . , N − 1 equals vi+1(2 + s). Since λN(L) = 2(1 + r) > (1 + r)(2− s) = λ1(L) and λi(L) = vi+1(2+s) vi ≥ (1 + r)(2− s) = λ1(L), i = 2, . . . , N − 1, due to 2 + s > 1 + r, vi+1 ≥ vi and 2− s ≤ 1, then machine 1 has the smallest delay which equals its load. Denote the delay of machine i as λji (L) = λi(L) + wj vi in the case where some job j deviates from the profile L and moves to machine i from another machine. No one of jobs w1 or w2 moves to machine i, i = 2, . . . , N − 1, since λN(L) = 2(1 + r) ≤ (2 + s) + (1 + r) ≤ vi+1(2+s)+s(1+r) vi = λ1 i (L) = λ2 i (L). Also no one of them moves to machine 1, since λN(L) = 2(1 + r) = (1 + r)(2− s) + s(1 + r) = λ1 1(L) = λ2 1(L). Each of jobs wi3, i = 3, . . . , N , has not reason to move to machine N due to λi−1(L) = vi(2+s) vi−1 ≤ 2(1 + r) + vi(2+s) s = λi3N(L), that is equivalent to the inequality (s− vi−1)vi(2 + s) ≤ 2svi−1(1 + r) which holds true since s− vi−1 < 1, 2 + s < 4 2 s vi vi−1(1 + r) ≥ 4. Also no one of jobs wi3, i = 3, . . . , N , moves to machine j > i− 1 since λi−1(L) = vi(2+s) vi−1 < 2vi(2+s) vj ≤ (vi+vj)(2+s) vj = λi3j (L). Moreover, job wi3 does not move to slower machine 1 or j < i− 1, and no one job from machine 1 moves to another machine because the delay on machine 1 is minimal. Therefore, the given profile is an equilibrium with the social payoff (1 + r)(2− s). Consider the profile where each job wi3, i = 3, . . . , N belongs to machine i, jobs w1 and w4 are assigned to machine 2 and machine 1 receives jobsw2 andw5. The social payoff equals 2 + s in this profile, so, OPT ≥ 2 + s. 2. Let now rs > 2. Then est(r, s) = 2 r(2−s) . Consider the set of jobs: w1 = w2 = rs, wi3 = 2vi, i = 3, . . . , N , w4 = r(2− s). In the equilibrium L jobs w1 and w2 belong to Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) 66 Y.V. CHIRKOVA machine N , each job wi3, i = 3, . . . , N is assigned to machine i− 1, machine 1 receives job w4. We show that it is an equilibrium indeed and find the system payoff. Since λN(L) = 2r > r(2− s) = λ1(L) and λi(L) = 2vi+1 vi ≥ r(2− s) = λ1(L), i = 2, . . . , N − 1, due to 2 vi ≥ 1, vi+1 ≥ r and 2− s < 1, then machine 1 has the smallest delay which equals r(2− s). Job w1 or w2 does not move to machine i, i = 2, . . . , N − 1, since λN(L) = 2r = r + r ≤ 2vi+1+rs vi = λ1 i (L) = λ2 i (L), and also to machine 1 due to λN(L) = 2r = r(2− s) + rs = λ1 1(L) = λ2 1(L). No one of jobs wi3, i = 3, . . . , N , moves to machine N since λi−1(L) = 2vi vi−1 ≤ 2r + 2vi s = λi3N(L) due to 2vi(s−vi−1) s ≤ 2rvi. Also no one of jobs wi3, i = 3, . . . , N , moves to machine j > i− 1, since λi−1(L) = 2vi vi−1 ≤ 4vi vj ≤ 2(vi+vj) vj = λi3j (L). Moreover, job wi3 does not move to slower machine 1 or j < i− 1. No one job on machine 1 moves to other machines with not smaller delay. Hence, the given profile L is an equilibrium with the social payoff r(2− s). Consider the profile where each job wi3, i = 3, . . . , N , is assigned to machine i, jobs w1 and w4 belong to machine 2, and job w2 to machine 1. The social payoff equals 2 for this profile, thus, OPT ≥ 2. In both considered cases the ratio of the optimal payoff and the equilibrium payoff equal est(r, s), hence, the price of anarchy is not less than this estimate. From the obtained estimate (3.2) we see that when the speed of the fastest machine increases and comes closer to the value of 2, the lower estimate of the price of anarchy grows infinitely. Hence, we obtain the following corollary from the theorem 3.1. Corollary 3.1: For the system composed of N ≥ 3 machines having speeds v1 = 1 ≤ v2 = r ≤ v3 ≤ · · · ≤ vN = s < 2 the price of anarchy tends to infinity as s→ 2− 0. According to the following result, for PoA evaluation it suffices to consider only games, where the optimal social payoff equals 1. Theorem 3.2: For the system S, the price of anarchy constitutes PoA(S) = max U1:OPT (S,U1)=1 1 min L is a Nash equilibrium in Γ(S,U1,λ) SC(L) . Proof We show that one can normalize job volumes in any game Γ(S, U, λ) such that the optimal social payoff becomes equal 1 and the ratio of the optimal social payoff and the worst-case equilibrium payoff does not change its value. Assume that L is the worst-case equilibrium in the game Γ(S, U, λ) with an arbitrary set of players U(n,w). For each player j, the volume of its job equals wj , and the vector LOPT gives the optimal strategy profile in this game. Let SC and OPT be the social payoff in the profile L and the optimal social payoff, respectively. The ratio of the optimal and worst-case equilibrium social payoff is defined by OPT SC . So long as L represents an equilibrium, then for any player j we obtain that ∑ k=1,...,n:lk=lj wk vlj ≤ ∑ k=1,...,n:lk=i wk+wj vi for any machine i. Now, explore the game with the same set of machines and players, where each player j has the job of volume wj OPT . The social payoff in the profiles L and LOPT constitutes SC OPT and 1, respectively. By virtue of the linear homogeneity of machine delays in their loads, the profiles L and LOPT form the worst-case equilibrium and optimal profiles, respectively, in the new game. Particularly, the profile L is an equilibrium in the new game, since for any player Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) PRICE OF ANARCHY FOR MAXIMIZING THE MINIMUM MACHINE LOAD 67 j the inequality ∑ k=1,...,n:lk=lj wk vljOPT ≤ ∑ k=1,...,n:lk=i wk+wj viOPT holds true for any machine i. Imagine that L is any non-worst-case equilibrium in the new game. Then the game admits an equilibrium L′ with social payoff SC′ OPT such that the social payoff in the profile L′ is less than that in the profile L, i.e., SC′ OPT < SC OPT . However, in the initial game the profile L′ corresponds to the social payoff SC ′ < SC, and the equilibrium L′ is worse than its counterpart L. Similarly, LOPT gives the optimal profile in the new game. Then the ratio of the optimal and the worst- case equilibrium social payoff in the new game also equals OPT SC . Consequently, any game Γ(S, U, λ) corresponds to a game Γ(S, U1, λ) with normalized job volumes such that OPT (S, U1) = 1. Moreover, the ratio of the optimal and the worst- case equilibrium social payoff is same in both games. Hence, for PoA evaluation it suffices to consider only games with unit optimal social payoff. 4. THE CASE OF 3 MACHINES As a matter of fact, the exact PoA value in the two-machine model was found in the paper [2]. Consider the case of 3 machines in the system S. Without loss of generality, throughout this section we believe that the machines have speeds v1 = 1 ≤ v2 = r ≤ v3 = s, i.e., machine 1 is the slowest one, machine 2 has medium speed and machine 3 is the fastest one. Lemma 4.1: For the system S composed of 3 machines having speeds v1 = 1 ≤ v2 = r ≤ v3 = s the inequality OPT ≤ W−wk 1+r holds true for any job k with the volume wk. Proof Suppose that there is such job of the volume wk assigned to machine i in the optimal profile L, that OPT > W−wk 1+r . Then all optimal delays on machines exceed W−wk 1+r . Moreover, it is clear that λi(L) ≥ wk vi . Hence, W = viλi(L) + vjλj(L) + vlλl(L) > wk + (vj + vl) W−wk 1+r ≥ wk + (1 + r)W−wk 1+r = W . Lemma 4.2: For the system S composed of 3 machines having speeds v1 = 1 ≤ v2 = r ≤ v3 = s, if two jobs of volumes wk1 and wk2 are assigned to the same machine in the optimal profile, then OPT ≤ W−wk1−wk2 1+r . Proof Assume for the sake of contradiction that OPT > W−wk1−wk2 1+r and jobs of volumes wk1 and wk2 are assigned to machine i in the optimal profile. Then all optimal delays on machines exceed W−wk1−wk2 1+r and λi(L) ≥ wk1+wk2 vi . Then W = viλi(L) + vjλj(L) + vlλl(L) > wk1 + wk2 + (vj + vl) W−wk1−wk2 1+r ≥ wk1 + wk2 + (1 + r) W−wk1−wk2 1+r = W . Theorem 4.1: For the system S composed of 3 machines having speeds v1 = 1 ≤ v2 = r ≤ v3 = s < 2 the price of anarchy does not exceed est(r, s) = min{ 2+s (1+r)(2−s) , 2 r(2−s)}. Proof In the proof we consider cases with a certain number of jobs assigned to each of two the most loaded machines having the largest delay. For each case we show that the price of anarchy estimate presented in the theorem condition is true. Suppose that L is an equilibrium profile Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) 68 Y.V. CHIRKOVA and SC(L) = λi(L), that is machine i has the smallest delay. Explore different cases of an equilibrium L. 1. Each of machines j and l receives one job. In the optimal profile these two jobs occupy at most two machines. Thus, there is some machine k in the optimal profile, taking partially or wholly the equilibrium load of machine i and nothing else. That is OPT ≤ viλi(L) vk ≤ sλi(L). By lemma 8.1 s ≤ est(r, s). 2. Machine j receives nj ≥ 2 jobs, machine l receives nl = 1 job. By lemma 3.2 λj(L) ≤ 2vi 2vi−vjλi(L). By lemma 4.1 OPT ≤ viλi(L)+ 2vivj 2vi−vj λi(L) 1+r = λi(L) 2v2i+vivj (1+r)(2vi−vj) . a) Assume first that vi ≥ vj . Then 2v2 i + vivj ≤ 3v2 i , since this expression increases by vj . Also 2vi − vj ≥ vi, so long as this expression decreases by vj . Then OPT ≤ λi(L) 3vi 1+r ≤ λi(L) 3s 1+r ≤ λi(L)est(r, s) by lemma 8.2. b) Suppose now that vi < vj . Then by lemma 8.3 2v2i+vivj (1+r)(2vi−vj) < 2+s (1+r)(2−s) . Explore now two cases. In the first case assume that vi = r and vj = s. Here by lemma 8.4 2r2+rs (1+r)(2r−s) < 2 r(2−s) . In the second case vi = 1. By lemma 3.3 wk ≤ vk 2−vk λi(L) ≤ s 2−sλi(L) and vjλj(L)− wk ≤ s 2−sλi(L) for any job of volume wk assigned to machine j. If all jobs assigned to machine j in the profile L remain there in the optimal profile, two cases are possible. If a single job assigned to machine l in the equilibrium keeps its position in the optimal profile, then the load of machine i can only decrease with system’s transition from the equilibrium to the optimal profile. If this single job leaves machine l, then in the optimal profile machine l receives the load at most λi(L) coming from machine i. In both cases OPT ≤ λi(L). If jobs move from machine j only to machine l with system’s transition from the equilibrium to the optimal profile, similar two cases are possible. If a single job assigned to machine l in the equilibrium remains there in the optimal profile, then the load of machine i can only decrease with transition to the optimal profile. Then OPT ≤ λi(L). If this single job leaves machine l, then in the optimal profile machine l can receive the load at most λi(L) + s 2−sλi(L) coming from machines i and j. Then OPT ≤ λi(L) 1+ s 2−s vl ≤ λi(L) 1+ s 2−s r = λi(L) 2 r(2−s) . If some jobs move from machine j to machine i with system’s transition from the equilibrium to the optimal profile, we obtain the same two cases. If a single job assigned to machine l in the equilibrium remains there in the optimal profile, then machine j receives the load at most λi(L) + s 2−sλi(L) consisting from the load remaining on j and possibly coming from i. Then OPT ≤ λi(L) 1+ s 2−s vj ≤ λi(L) 1+ s 2−s r = λi(L) 2 r(2−s) . If this single job leaves machine l, then in the optimal profile machine l can receive the load at most λi(L) + s 2−sλi(L) coming from machines i and j. 3. Each of machines j and l receives exactly two jobs: nj = nl = 2. The total number of jobs assigned to machines j and l is four, the number of machines is three, so in the optimal profile at least two of these jobs (wk1 and wk2) become assigned to the same machine. Then by lemma 4.2 OPT ≤ W−wk1−wk2 1+r = viλi(L)+wk3+wk4 1+r , where wk3 wk4 remaining two jobs assigned to machines j and l. Consider machine k ∈ {j, l}. If vi ≤ vk, then by lemma 3.3 the volume of any of jobs assigned to machine k does not exceed λi(L) vivk 2vi−vk . Let now vi > vk. L is an equilibrium, therefore λk(L) ≤ λi(L) + w vi , where w is the smallest volume job assigned to machine k. Thus, w ≥ viλk(L)− viλi(L). By lemma 3.2 Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) PRICE OF ANARCHY FOR MAXIMIZING THE MINIMUM MACHINE LOAD 69 λk(L) ≤ λi(L) 2vi 2vi−vk ≤ 2λi(L), 2vi − vk ≥ vi, w ≤ λi(L). Another job of the largest volume assigned to machine k has the volume vkλk(L)− w ≤ vkλk(L) = viλi(L)− (vi − vk)λk(L) ≤ viλi(L)− (vi − vk)λi(L) = vkλi(L) ≤ rλi(L) ≤ λi(L) rs 2r−s ≤ λi(L) s 2−s . a) Let vi = s, then OPT ≤ λi(L) s+2r 1+r ≤ λl(L) 3s 1+r ≤ λi(L)est(r, s) by lemma 8.2. b) Let vi = r, then OPT ≤ λi(L) r+2 rs 2r−s 1+r = λi(L) 2r2+rs (1+r)(2r−s) ≤ λi(L)est(r, s) by lemma 8.3. c) Let vi = 1, then OPT ≤ λi(L) r+2 s 2−s 1+r = λi(L) 2+s (1+r)(2−s) . From the other side so long as the number of machines equals three there are surely two machines α and β receiving at most one job from considered four jobs and, perhaps, some part of the load of machine i. Then OPT does not exceed the minimal delay over these machines: OPT ≤ min α6=β {λi(L) 2 vα(2−s) , λi(L) 2 vβ(2−s)} ≤ min{λi(L) 2 1(2−s) , λi(L) 2 r(2−s)} = λi(L) 2 r(2−s) . 4. Machines j and l receive the following job allocation: nj ≥ 2, nl ≥ 3. By lemma 3.2 λj(L) ≤ λi(L) 2vi 2vi−vj and λl(L) ≤ λi(L) 3vi 3vi−vl . Thus in accordance with the estimate (3.1), OPT ≤ λi(L) vi+ 2vivj 2vi−vj + 3vivl 3vi−vl 1+r+s ≤ λi(L)est(r, s) by lemma 8.5 and lemma 8.6. The next theorem is a special case of theorem 3.1 for the system of three machines. Theorem 4.2: For the system S composed of 3 machines having speeds v1 = 1 ≤ v2 = r ≤ v3 = s < 2 is at least est(r, s) = min{ 2+s (1+r)(2−s) , 2 r(2−s)}. Then we obtain from theorems 4.1 and 4.2 an exact value of the price of anarchy for the tree-machine system. Theorem 4.3: For the system S composed of 3 machines having speeds v1 = 1 ≤ v2 = r ≤ v3 = s < 2 the price of anarchy exactly equals { 2+s (1+r)(2−s) for rs ≤ 2, 2 r(2−s) for rs > 2. The exact PoA value allows establishing a possibility for PoA increase under new machine inclusion into the system, i.e., in a situation resembling the Braess paradox [10–13] when system’s power increasing leads to its performance characteristic degradation. The next statement illustrates that the price of anarchy increases or does not change under new machine inclusion into the system of two machines. Theorem 4.4: For the system S composed of two machines having speeds 1 ≤ s the price of anarchy does not decrease with adding a new machine of speed 1 ≤ q < 2. Proof 1. Suppose that new machine has a speed of q ≤ s. If qs ≤ s2 < 2 then the price of anarchy does not decrease since 2+s (1+s)(2−s) ≤ 2+s (1+q)(2−s) . If s2 > 2 and qs ≤ 2 then that does not decrease due to 2 s(2−s) ≤ 2+s (1+s)(2−s) ≤ 2+s (1+q)(2−s) . Consequently, we have the same if s2 > 2 and qs > 2 since 2 s(2−s) ≤ 2 q(2−s) . 2. Suppose now that new machine is more powerful than existing in the system, s < q < 2. If qs ≤ 2, then s2 ≤ 2, and the price of anarchy does not decrease since 2+s (1+s)(2−s) ≤ 2+q (1+s)(2−q) . If qs > 2 s2 ≤ 2, then that does not decrease due to 2+s (1+s)(2−s) ≤ 2 s(2−s) ≤ 2 s(2−q) . Also if qs > 2 and s2 > 2, we obtain the same because of 2 s(2−s) ≤ 2 s(2−q) . Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) 70 Y.V. CHIRKOVA 5. EVALUATING THE PRICE OF ANARCHY In the previous section, we have derived an analytic expression for the price of anarchy in the three-machine model, where the fastest machine possesses a rather high speed. In what follows, we suggest a computing method for the price of anarchy on the example of the system of 3 machines which is similar to a corresponding method for the load balance game [14]. This method can be generalized to systems composed of more machines. But such generalization increases the number of linear programming problems to-be-solved and the number of associated variables and imposed constraints. Particularly the N -machine model requires N ! linear programming problems each of which includes (2N − 1)N−1 subproblems with N2 variables. Consider the following system of linear equations in the components of the vectors a = (a1, a2, a3), b = (b1, b2, b3), c = (c1, c2, c3). a1+a2+a3 vi ≤ b1+b2+b3+ min k=1,2,3:ak>0 ak vj a1+a2+a3 vi ≤ c1+c2+c3+ min k=1,2,3:ak>0 ak vl b1+b2+b3 vj ≤ c1+c2+c3+ min k=1,2,3:bk>0 bk vl a1+a2+a3 vi ≥ b1+b2+b3 vj ≥ c1+c2+c3 vl max k=1,2,3 ak > 0 max k=1,2,3 bk > 0 ak, bk, ck ≥ 0, k = 1, 2, 3. (5.3) This system describes a set of hyperplanes passing through the point (0, 0, 0, 0, 0, 0, 0, 0, 0) in the 9-dimensional space, and the solution set represents a domain in the space bounded by the hyperplanes. The above system is feasible, as far as, e.g., the triplet a1 = a2 = a3 = αsi, b1 = b2 = b3 = αsj and c1 = c2 = c3 = αsl makes its solution for all α > 0. Furthermore, the solution set is unbounded, since α can be arbitrarily large. Study the system S composed of 3 machines having speeds 1 ≤ r ≤ s and n players. Let L indicate a Nash equilibrium in the system S such that machine i is slowest in this profile having the greatest delay, machine j has a medium delay and machine l is fastest. Suppose that in the equilibrium L machine i receives the total volume of jobs defined by∑ k=1,...,n:lk=i wk = a1 + a2 + a3 and the corresponding volumes for machines j and l equal∑ k=1,...,n:lk=j wk = b1 + b2 + b3 and ∑ k=1,...,n:lk=l wk = c1 + c2 + c3, respectively. The volume of jobs on each machine is somehow divided into three parts so that each component of the three-dimensional vectors a, b and c is either zero or positive and includes at least one job. Lemma 5.1: Let L be a Nash equilibrium in the game involving three machines i, j and l and n players such that λi(L) ≥ λj(L) ≥ λl(L),∑ k=1,...,n:lk=i wk = a1 + a2 + a3,∑ k=1,...,n:lk=j wk = b1 + b2 + b3,∑ k=1,...,n:lk=l wk = c1 + c2 + c3. Here for all k = 1, 2, 3 component ak equals zero or the volume of at least one job on machine i, component bk equals zero or the volume of at least one job on machine j, and component Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) PRICE OF ANARCHY FOR MAXIMIZING THE MINIMUM MACHINE LOAD 71 ck equals zero or the volume of at least one job on machine l. Then the set of the vectors a, b and c is the solution of the system (5.3). Proof Suppose that L represents a Nash equilibrium and λi(L) ≥ λj(L) ≥ λl(L). The lemma 3.1 claims that λk(L) > 0, k = i, j, l. In this case, the following inequalities take place: ∑ k=1,...,n:lk=i wk vi ≤ ∑ k=1,...,n:lk=j wk+ min k=1,...,n:lk=i,wk>0 wk vj∑ k=1,...,n:lk=i wk vi ≤ ∑ k=1,...,n:lk=l wk+ min k=1,...,n:lk=i,wk>0 wk vl∑ k=1,...,n:lk=j wk vj ≤ ∑ k=1,...,n:lk=l wk+ min k=1,...,n:lk=j,wk>0 wk vl∑ k=1,...,n:lk=i wk vi ≥ ∑ k=1,...,n:lk=j wk vj ≥ ∑ k=1,...,n:lk=l wk vl . Since each nonzero quantity ak (k = 1, 2, 3) equals the volume of at least one job on machine i, then we naturally have that min k:ak>0 ak ≥ min k:lk=i,wk>0 wk that provides satisfaction of the first and the second inequality of the system (5.3). Similarly, min k:bk>0 bk ≥ min k:lk=j,wk>0 wk. This means satisfaction of the system (5.3). Lemma 5.2: Any solution of the system (5.3) defines a Nash equilibrium L in the game involving the system S composed of 3 machines i, j and l and players whose jobs correspond to the nonzero components of the vectors a, b and c and the delays are sorted in the order λi(L) ≥ λj(L) ≥ λl(L). Proof Assume that the set of the vectors a, b and c gives the solution of the system (5.3). Consider the game with 3 machines i, j and l. Let each nonzero component of the vectors a, b and c specify the job volume of a regular player. Consider a profile L such that the jobs of volumes ak > 0, bk > 0 and ck are assigned to machines i, j and l, respectively. So long as all inequalities (5.3) hold true, the profile L gives the desired Nash equilibrium. The following result is immediate. Theorem 5.1: Any Nash equilibrium L in the game involving the system S composed of 3 machines i, j and l and n players corresponds to a Nash equilibrium L′ in the game involving the same system S and at most 9 players, where each machine receives no more than 3 jobs and the delays on all machines in L and L′ do coincide. Proof Consider a Nash equilibrium L in the game with the system S of 3 machines and n players. Number the machines so that λi(L) ≥ λj(L) ≥ λl(L). According to Lemma 5.1, for any Nash equilibrium in the game involving the system S and any number of players there exist a corresponding solution a, b, c of the system (5.3). By virtue of Lemma 5.2, this solution determines a Nash equilibrium L′ in the game with the system S such that the nonzero components of the vectors a, b and c specify the job volumes on machines i, j and l, respectively. By definition, the element sum of the vector a represents the load of machine i in a profile L. Hence, delays on machine i coincide in both equilibria L and L′. Similarly, for machines j and l the delays in the equilibrium L coincide with the corresponding delays in the equilibrium L′. Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) 72 Y.V. CHIRKOVA This theorem claims that it is sufficient to consider only games, where in an equilibrium each machine receives at most three jobs and the equilibrium solves the system (5.3). And the domain of the social payoff coincides with the value domain of games with an arbitrary number of players. Imagine that the components of the vectors a, b and c are chosen as follows. In the optimal profile yielding the maximum social payoff, machines i, j and l receive the total volumes of jobs a1 + b1 + c1, a2 + b2 + c2 and a3 + b3 + c3, respectively, and the lowest delay can be on each of them. Furthermore, by Theorem 3.2, the volumes of jobs are assumed to be normalized so that in the optimal profile the maximum delay among all machines equals 1. In our case, this means that a1 + b1 + c1 ≥ vi, a2 + b2 + c2 ≥ vj, a3 + b3 + c3 ≥ vl, and at least one of these inequalities holds as an equality. Lemma 5.3: Solution of the linear programming problem LPP (vi, vj, vl) :  c1 + c2 + c3 → min (r1) a1+a2+a3 vi ≤ b1+b2+b3+ min k:ak>0 ak vj (r2) a1+a2+a3 vi ≤ c1+c2+c3+ min k:ak>0 ak vl (r3) b1+b2+b3 vj ≤ c1+c2+c3+ min k:bk>0 bk vl (r4) a1+a2+a3 vi ≥ b1+b2+b3 vj ≥ c1+c2+c3 vl (r5) max k=1,2,3 ak > 0 (r6) max k=1,2,3 bk > 0 (r7) ak, bk, ck ≥ 0, k = 1, 2, 3 (r8) a1 + b1 + c1 ≥ vi (r9) a2 + b2 + c2 ≥ vj (r10) a3 + b3 + c3 ≥ vl (5.4) with respect to the components of the vectors a, b and c provides the minimal social payoff in a Nash equilibrium among all games, where in an equilibrium at most 3 jobs are assigned to each machine, i, j and l indicate the numbers of the machines in the descending order of their delays and the optimal social payoff makes up 1. Proof Due to Lemma 5.2, any solution of inequalities (r1)− (r7) in the problem LPP (vi, vj, vl) defines an equilibrium in the game with 3 machines, where each machine receives at most 3 jobs and i, j, and l are the numbers of machines in the descending order of their delays The goal function in this game is bounded above only by the hyperplanes corresponding to inequalities (r8)− (r10). Actually, inequalities (r1)− (r7) admit arbitrarily small non- negative values of the goal function, including zero. Therefore, the minimum is reached on one of the boundaries answering to the last three inequalities. This guarantees that one of them is satisfied as an equality, ergo the optimal payoff in the game corresponding to the solution of the problem LPP (vi, vj, vl) equals 1. Consequently, exact PoA evaluation for the system S composed of 3 machines calls for solving a series of linear programming methods LPP (vi, vj, vl) for all permutations (1, r, s). And the minimum solution among them yields the value of PoA(S). In other words, it is possible to establish the following fact. Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) PRICE OF ANARCHY FOR MAXIMIZING THE MINIMUM MACHINE LOAD 73 Theorem 5.2: For the system S composed of 3 machines having speeds v1 = 1 ≤ v2 = r ≤ v3 = s < 2, the price of anarchy constitutes PoA(S), which is the inverse value of 1 PoA(S) = min (vi,vj ,vl) are permutations of (1,r,s){ c1+c2+c3 vl |a, b, c is a solution of LPP (vi, vj, vl) } , where LPP (vi, vj, vl) is the linear programming problem (5.4). Proof According to Lemma 5.3, the solution of the problem (5.4) gives the minimum social payoff in a Nash equilibrium, where i, j and l are the numbers of the machines in the descending order of their delays, among all games such that in an equilibrium each machine receives at most 3 jobs and the optimal payoff equals 1. The minimum solution among the problems for all admissible permutations (1, r, s) as the values of (vi, vj, vl) provides the minimum social payoff in a Nash equilibrium among all games, where in an equilibrium at most 3 jobs are assigned to each machine and the optimal payoff equal 1. By Theorem 5.1, for any equilibrium in the game involving the system S of 3 machines and an arbitrary number of players, it is possible to construct a corresponding equilibrium in the game with the same machines and a set of at most 9 players, where each machine receives no more than 3 jobs and the social payoff coincides for both equilibria. Thus, for PoA evaluation it suffices to consider only games, where in an equilibrium each machine has at most 3 jobs. Using Theorem 3.2, we finally obtain that for PoA evaluation it suffices to consider only games, where the social payoff in the optimal profile equal 1. 6. COMPUTING EXPERIMENTS To estimate the price of anarchy in the three-machine model, we have developed a program implementation of PoA evaluation method presented in the previous section. This program allows to compare visually the theoretic PoA value and its exact value constructed by solving a series of linear programming problems. Moreover the program provides the possibility to see the PoA dynamics for the machine number N > 3 where no any theoretic PoA estimates are obtained. The parameters of the system S act as the options in the program; by assumption, the speed of machine 1 equals 1, whereas an exact value and a certain range are specified for the speeds of machines 2 and 3, respectively. In this case, users can study the PoA dynamics under variations in the speed of one machine. The figures 6.1 and 6.2 present examples of PoA estimates for different values of speeds of machine 2 and 3. At the fig. 6.1 the speed of machine 2 is r = 1.1, and the speed of machine 3 is s ∈ [r, 2). At the fig. 6.2 the speed of the fastest machine 3 is s = 1.7 and the speed of machine 2 is r ∈ [1, s]. Here we can see that theoretical and computed values of PoA coincide. The next example is more interesting. Consider the system of four machines with speeds v1 = 1 ≤ v2 = q ≤ v3 = r ≤ v4 = s < 2. Figures 6.3 and 6.4 present PoA comparing with the lower PoA estimate (3.2), which in fact is PoA for the system composed of 3 machines with speeds 1 ≤ r ≤ s < 2. Fig. 6.3 presents PoA for the following cases. At the area A the value of q changes in the range [1, r], r = 1.3, s = 1.5. At the area B q = 1.3, the value of r changes in the range [q, s], s = 1.5. At the area C q = 1.3, r = 1.5, s value changes in the range [r, 2). In these cases PoA value for four-machine system coincide with its lower estimate (3.2). Fig. 6.4 presents the PoA dynamics for those systems where machine speeds differ rather little, that is normalized speeds are closed to 1. In this case one can see that the PoA value Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) 74 Y.V. CHIRKOVA 1 2 3 4 5 6 7 8 9 10 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2 s Fig. 6.1. PoA for the system S, where r = 1.1, s ∈ [r, 2). 4 4.5 5 5.5 6 6.5 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 r Fig. 6.2. PoA for the system S, where s = 1.7, r ∈ [1, s]. 1 2 3 4 5 6 7 8 9 10 1 1.2 1.4 1.6 1.8 2 q r s A B C Fig. 6.3. PoA for the four-machine system S. presented by the thin curve exceeds its estimate (3.2) presented by the bold curve. Both curves coincide under machine speeds increasing. At the area A the value of q changes in the range [1, r], r = 1.05, s = 1.1. At the area B q = 1.05, the value of r changes in the range [q, s], s = 1.1. At the area C q = 1.05, r = 1.1, the value of s changes in the range [r, 1.3). Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) PRICE OF ANARCHY FOR MAXIMIZING THE MINIMUM MACHINE LOAD 75 1 1.5 2 2.5 3 1 1.05 1.1 1.15 1.2 1.25 1.3 q r s A B C Fig. 6.4. PoA for the four-machine system S with small speeds 7. CONCLUSION This paper has explored the service system composed of N machines and n players and derived the lower estimate for the price of anarchy in the maximizing the minimum machine delay game (or cover game). The three-machine model has been analyzed in detail. Here we have determined the exact value of the price of anarchy and showed that the PoA increases or does not change under new machine inclusion into the system of two machines. Also we have proposed a computing algorithm of the exact PoA value. The algorithm can be generalized to systems with more machines, but this increases the number of linear programming problems to-be-solved and the number of associated variables and imposed constraints. And finally, we have implemented the algorithm as a program and conducted numerical experiments for comparing the obtained estimates of the PoA with its exact value. The results of these experiments have demonstrated the correctness of the derived estimates. For the case of four- machine system computing experiments demonstrate partial PoA coinciding for three and four-machine systems, the analytic confirmation of this fact needs further investigations. ACKNOWLEDGEMENTS This work was supported by the Mathematical Sciences Branch of the Russian Academy of Sciences and by the Russian Foundation for Basic Research (project no. 16-51-55006), and by the Russian Humanitarian Scientific Foundation (project no. 15-02-00352 a). 8. APPENDIX This appendix contains supporting lemmas which are used in proofs in section 4. Lemma 8.1: For any real r, s such that 1 ≤ r ≤ s < 2 we have s ≤ min{ 2+s (1+r)(2−s) , 2 r(2−s)}. Proof 2 r(2−s) ≥ 2 s(2−s) ≥ s, since s3 − 2s2 + 2 = s(s− 1)2 + (2− s) > 0. 2+s (1+r)(2−s) ≥ 2+s (1+s)(2−s) ≥ s, since s3 − s2 − s+ 2 > s3 − 2s2 + 2 = s(s− 1)2 + (2− s) > 0. Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) 76 Y.V. CHIRKOVA Lemma 8.2: For any real r, s such that 1 ≤ r ≤ s < 2 we have 3s 1+r ≤ min{ 2+s (1+r)(2−s) , 2 r(2−s)}. Proof First, 3s ≤ 2+s 2−s , due to 3s2 − 5s+ 2 = (s− 1)(3s− 2) > 0. Second, 3s 1+r ≤ 2 r(2−s) , since 6rs− 3rs2 − 2− 2r = r(6s− 3s2 − 2)− 2 = r(1− 3(s− 1)2)− 2 ≤ r − 2 < 0. Lemma 8.3: For vi < vj , vi, vj ∈ {1, r, s}, where real r, s are such that 1 ≤ r ≤ s < 2, we have 2v2i+vivj 2vi−vj ≤ 2+s 2−s . Proof If vi < vj , then 2v2i+vivj 2vi−vj decreases by vi and increases by vj , since 4v2 i − 4vivj − v2 j < 0 and vi(2vi − vj) + 2v2 i + vivj > 0. Lemma 8.4: For any real r, s such that 1 ≤ r ≤ s < 2 we have 2r2+rs (1+r)(2r−s) < 2 r(2−s) . Proof The inequality in the condition is equivalent to f(r, s) = −r2s2 − 2s(r3 − r2 − r − 1) + 4(r3 − r2 − r) < 0, chech if it holds true. Show that f ′r(r, s) = −2rs2 + 2(2− s)(3r2 − 2r − 1) < 0, then f(r, s) ≤ f(1, s) = −s2 + 4s− 4 = −(2− s)2 < 0. For each fixed s the function f ′r(r, s) is a parabola with branches directed upwards. Thus, its largest value is achieved on one of two ends of the interval r ∈ [1, s]. At the left end f ′r(1, s) = −2s2 < 0. At the right end f ′r(s, s) = −8s3 + 16s2 − 6s− 4 = −8s(s− 1)2 − 2(2− s) < 0. Lemma 8.5: For vi 6= vj 6= vl, vi, vj, vl ∈ {1, r, s}, where real r, s are such that 1 ≤ r ≤ s < 2, we have f(vi, vj, vl) = vi + 2vivj 2vi−vj + 3vivl 3vi−vl ≤ 1 + 2s 2−s + 3s 3−s . Proof The function f(vi, vj, vl) obviously increases by vj and vl, hence f(vi, vj, vl) ≤ vi + 2svi 2vi−s + 3svi 3vi−s = g(vi). Show that g(vi) decreases by vi. The derivative g′vi(vi) = 1− 2s2 (2vi−s)2 − 3s2 (3vi−s)2 increases by vi and, therefore, does not exceed g′vi(s) = 1− 2− 3 4 < 0. Then g(vi) ≤ g(1) = 1 + 2s 2−s + 3s 3−s . Lemma 8.6: For any real r, s such that 1 ≤ r ≤ s < 2 we have 1+ 2s 2−s+ 3s 3−s 1+r+s ≤ min{ 2+s (1+r)(2−s) , 2 r(2−s)}. Proof We show first that 1 + 2s 2−s + 3s 3−s ≤ (1+r+s)(2+s) (1+r)(2−s) . The right part of the inequality decreases by r, thus it suffices to show that 1 + 2s 2−s + 3s 3−s ≤ (1+2s)(2+s) (1+s)(2−s) . This is equivalent to s ≤ s2, that holds true under s ≥ 1. Show now that 1 + 2s 2−s + 3s 3−s ≤ 2(1+r+s) r(2−s) . The right part of the inequality decreases by r, so it suffices to show that 1 + 2s 2−s + 3s 3−s ≤ 2(1+2s) s(2−s) . This inequality is equivalent to −4s3 + 11s2 − 4s− 6 = −s(2s− 3)2 − (2− s)(3− s) < 0. Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) PRICE OF ANARCHY FOR MAXIMIZING THE MINIMUM MACHINE LOAD 77 REFERENCES 1. Epstein L., Kleiman E., & van Stee R. (2009) Maximizing the minimum load: the cost of selfishness. In Proceedings of the 5th International Workshop on Internet and Network Economics, LNCS 5929, 232-243. 2. Tan Z., Wan L., Zhang Q. & Ren W. (2012) Inefficiency of equilibria for the machine covering game on uniform machines. Acta Informatica, 49 (6), 361–379. 3. Wu Y., Cheng T. C. E. & Ji M. (2015) Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines. Information Processing Letters, 115 (11), 838–844. 4. Andelman N., Feldman M. & Mansour Y. (2007) Strong price of anarchy. In Proc. of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 189–198. 5. Koutsoupias E., Papadimitriou C. H. (1999) Worst-case Equilibria. In Proc. of STACS 1999, 1563, 404–413. 6. Lücking T., Mavronicolas M., Monien B., Rode M., Spirakis P. & (2003) Vrto I. Which is the Worst-case Nash Equilibrium? In Proc. of the 26th International Symposium on Mathematical Foundations of Computer Sciencem, LNCS 2747, 551–561. 7. Even-Dar E., Kesselman A. & Mansour Y. (2003) Convergence time to Nash equilibria. In Proc. of the 30th International Colloquium on Automata, Languages and Programming (ICALP2003), 502–513. 8. Fotakis D., Kontogiannis S. C., Koutsoupias E., Mavronicolas M. & Spirakis P. G. (2002) The structure and complexity of Nash equilibria for a selfish routing game. In Proc. of the 29th International Colloquium on Automata, Languages and Programming (ICALP2002), 123–134. 9. Chen X., Epstein L., Kleiman E. & van Stee R. (2013) Maximizing the minimum load: The cost of selfishness. Theoretical Computer Science, 482, 9–19. 10. Murchland J. D. (1970) Braess’s paradox of traffic flow. Transportation Research, 4, 391–394. 11. Roughgarden T. & Tardos É. (2002) How bad is selfish routing? Journal of the ACM, 49 (2), 236–259. 12. Korilis Y. A., Lazar A. A. & Orda A. (1999) Avoiding the Braess paradox in non- cooperative networks. Journal of Apllied Probability, 36 (1), 211–222. 13. Mazalov, V. V. (2014) Mathematical Game Theory and Applications. New York, NY: Wiley. 14. Chirkova Yu. V. (2015) Price of anarchy in machine load balancing game. Automation and Remote Control, 76 (10), 1849–1864. Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) Introduction The model The general case of N machines The case of 3 machines Evaluating the price of anarchy Computing experiments Conclusion Appendix