CS 684 Algorithmic Game Theory Scribe: Paul EastlundInstructor: Eva Tardos August 31, 2005Now we’re going to look at a non-atomic game version of the load-balancing game we saw before.The game will not have discrete units; it will be more like a fluid model. For the elements of ourgame, we still have:• a set M of machines 1,...,m• response time functions ri(L) such that, for all i, riis strictly monotonic andcontinuous• job types 1,...,n• total loads pjfor each job type j• subsets Sj⊂ M for each job type jFor our solution, we are looking for an assignment xijfor each (job type, machine) pair such thatxijmeasures the amount of load that job type j assigns to machine i. Any such assignment thatis a solution must satisfy the following requirements:• ∀jPi∈Sjxij= pj• ∀j, i xij≥ 0• if i is not in Sj, xij= 0We need to work out a measure of quality for a solution. For us to manage that, we need to definethe load on a machine i:Li=PjxijIn the atomic version of this game, we talked about various measures of quality. Some of thesemeasures dealt with “the response time of a job.” Jobs have now been replaced with “job types,”and “the response time of a job type” is meaningless. Job types are disjoint entities. They arecomprised of infintesimal selfish jobs. There is no one response time for a job type.To get some idea of the ramifications of this, let’s return to an example we saw earlier:r (L)=Lp =1p =1r (L)=21212Figure 1: A Nash equlibrium with unit size jobs.If this game were discrete, this would be one of several equilibria, as we saw before. The onedissatisfied unit of job had no recourse. If it switched over to the faster machine, that machinewould become just as slow as its current machine, and it would reap no benefit. Now that the gamer (L)=Lp =1p =1r (L)=21212Figure 2: The only Nash equlibrium with nonatomic jobs.is nonatomic, infintesimal elements of load on the slower machine can switch to the faster machinewithout increasing its load all the way to “2.” The inevitable result is the only Nash equilibriumin the new, non-atomic game:Whereas before, the necessary condition for a Nash equilibrium was∀i, j xij> 0 → ∀(k ∈ Sj) ri(Li) ≤ rk(Lk+ pj)Now, not all of pjmust make the jump to k at the same time; only an infintesimally smallamount must. As the unit that we’re dealing with shrinks to infintesimal, the new equilibriumcondition approaches:∀i, j xij> 0 → ∀(k ∈ Sj) ri(Li) ≤ rk(Lk)We can omit the change in Lk, as it shrinks to infintesimal, because we know rkto be continuous– so any difference rk(Lk+ δ) − rk(Lk) must shrink to infintesimal with δ.Now, the questions we need to ask (and answer) are:1. Does a Nash equilibrium exist?2. How good is it?For now, we’re going to claim that Nash equilibria do always exist, but punt on the proof andgo on to answer question 2. In answering it, we’re going to take, as our measure of quality, theworst response time experienced by any unit of load: r = maxi:Li>0ri(Li).Theorem 1 A Nash equilibrium in the non-atomic load balancing game minimizes the maximumresponse time over all solutions.Proof. For any solution, there is at least one (but possibly more than one) machine withthe maximum response time experienced by any unit of load. Note that some machines, with noload assigned to them, might experience an even greater load. For a solution x, with maximumexperienced response time r, let A(x) be the set of machines i with ri(Li) ≥ r. Let B(x) be alljobs j for which xij> 0 for some i in A(x).Lemma 2 In a Nash equilibrium, all jobs in B(x) assign all of their load to machines within A(x)This should be obvious. Take a job j with some load assigned to a machine k outside of A(x).We know, by the definition of A(x), that rk(Lk) < r. But then, this fails to meet the conditionsfor a Nash, because, for this xij> 0 where i is one of the machines in A(x) that j assigns load to,there exists a k ∈ Sjsuch that rk(Lk) < ri(Li). Thus we have a contradiction, and the lemma isproved. We also notice that j ∈ B(x) ⇒ Sj⊆ A(x).Now let’s compare a Nash to any other solution. Our Nash has assignments xijand loadsLi, whereas the other solution has assignments x∗ijand loads L∗i. But x∗still has all of the loadPj∈B(x)pjassigned within the group A(x). Since the sum of the loads in A in this solution mustbe at least as great as the sum of the loads in the Nash, there must be some machine i in A suchthat L∗i≥ Li. In this case, we know that ri(L∗i) ≥ ri(Li) and thus that this other solution is atleast as bad as the