Selfish Load Balancing

Motivation: servers without a scheduler

Load balancing is fundamental whenever tasks share resources. The classical version is an optimization problem: assign tasks to machines so the busiest machine is as lightly loaded as possible. But in, say, an Internet file-download service, each user picks the least-loaded server for itself, and nobody enforces a global assignment.

IntuitionThe central question

If every task is placed by a selfish agent seeking the least-loaded machine, how much worse is the busiest machine than under an optimal schedule — with identical or differently fast machines, and with or without randomized play?

This chapter differs from the rest of Part III in two ways:

Feature	Why it matters
Makespan objective (a max, not a sum)	nonutilitarian; captures efficiency and fairness together
Mixed equilibria analyzed as well as pure	explicitly measures the damage from uncoordinated randomization

The model

Makespan scheduling on uniformly related machines. There are machines $[m]$ with speeds $s_1,\dots,s_m$ and tasks $[n]$ with weights $w_1,\dots,w_n$ . An assignment is $A : [n]\to[m]$ .

DefinitionLoad and makespan

\ell_j = \sum_{i:\,A(i) = j} \frac{w_i}{s_j}, \qquad \mathrm{cost}(A) = \max_{j\in[m]} \ell_j.

Identical machines means $s_1 = \dots = s_m = 1$ .

The game

Agent $i$ controls task $i$ , and its pure strategies are the machines $[m]$ . Under assignment $A$ , agent $i$ pays $\ell_{A(i)}$ . Social cost is the makespan.

Mixed strategies. Let $p_i^j = \Pr[A(i) = j]$ and $x_i^j = \mathbb{1}[A(i) = j]$ . The profile $P = (p_i^j)$ induces a random assignment.

FormulaExpected load, social cost, and expected cost to an agent

\mathbb{E}[\ell_j] = \sum_{i} \frac{w_i\,p_i^j}{s_j}, \qquad \mathrm{cost}(P) = \mathbb{E}\Big[\max_j \ell_j\Big],

c_i^j = \mathbb{E}[\ell_j \mid A(i) = j] = \frac{w_i + \sum_{k\ne i} w_k p_k^j}{s_j} = \mathbb{E}[\ell_j] + (1 - p_i^j)\frac{w_i}{s_j}. \tag{20.1}

Component	Detail
Signature	$c_i^j : \text{profiles} \to \mathbb{R}_{\ge 0}$
Domain	everyone’s mixing probabilities
Codomain	the load agent $i$ expects to experience if it lands on machine $j$
Not the same as	$\mathbb{E}[\ell_j]$ : agent $i$ ‘s own weight is certainly there, but only counted with weight $p_i^j$ in the average

WarningYour cost exceeds the machine’s average load

Unless $p_i^j = 1$ , $c_i^j > \mathbb{E}[\ell_j]$ . You always see yourself on the machine. This gap drives several constructions below.

PropositionProposition 20.1 — mixed equilibrium

$P$ is a Nash equilibrium iff for all $i, j$ : $p_i^j > 0 \Rightarrow c_i^j \le c_i^k$ for every $k$ . Agents put probability only on machines minimizing their expected cost.

PropositionProposition 20.2 — pure equilibrium

$A$ is a pure Nash equilibrium iff $c_i^{A(i)} \le c_i^k$ for all $i, k$ : no task can lower its cost by moving alone.

Mixed equilibria exist by Nash’s theorem. Pure ones exist too, and are reached by improvement steps:

PropositionProposition 20.3 — pure equilibria always exist

Every load balancing game has a pure Nash equilibrium.

ProofImprovement steps lexicographically decrease the sorted load vector

Step 1: The potential. Sort loads in decreasing order, $(\lambda_1,\dots,\lambda_m)$ .

Step 2: One improvement step. A task moves from the machine at sorted position $j$ to the one at position $k$ . Necessarily $k > j$ : it moves to a less-loaded machine. Machine $j$ ‘s load drops. Machine $k$ ‘s new load is still below $\lambda_j$ , since otherwise the move wouldn’t help.

The key step: the number of machines with load $\ge \lambda_j$ strictly decreases, and all loads above $\lambda_j$ are unchanged. So the sorted vector gets lexicographically smaller. There are finitely many assignments, so improvement steps end at a pure equilibrium.

∎

RemarkConsequence: price of stability is 1

Start improvement steps from an optimal assignment. No step raises the makespan, so they end at a pure equilibrium that is also optimal. So only the price of anarchy is interesting here.

RemarkIt’s a routing game

Load balancing is weighted atomic selfish routing on $m$ parallel links with linear costs $c_j(x) = x/s_j$ (see routing-games; compare Theorem 18.15 on affine weighted instances). What differs is the objective: max rather than sum. (This connection is my gloss.)

Worked example: two machines, weights 2, 2, 1, 1

ExampleOptimal, worst pure, and a worse mixed equilibrium

Two identical machines. Tasks: two large (weight 2) and two small (weight 1).

Optimum: one large and one small per machine. Makespan 3.

Worst pure equilibrium: both large tasks on machine 1 (load 4), both small on machine 2 (load 2).

A small task moving would face $4 + 1 = 5$ .
A large task moving would face $2 + 2 = 4$ , no improvement.

So this is an equilibrium with makespan 4. Makespan $\ge 5$ can’t be an equilibrium: the other machine would have load $\le 1$ , and any task would move there.

Fully mixed equilibrium: every task picks each machine with probability $\tfrac12$ . Then $\mathbb{E}[\ell_j] = 3$ , and by (20.1):

a large task expects $3 + \tfrac12\cdot 2 = 4$ on either machine;
a small task expects $3 + \tfrac12\cdot 1 = 3.5$ on either.

By symmetry this is an equilibrium. Over the 16 equally likely outcomes:

Makespan	3	4	5	6
# outcomes	4	6	4	2

\mathrm{cost}(P) = \tfrac{1}{16}(3\cdot4 + 4\cdot6 + 5\cdot4 + 6\cdot2) = 4.25 > 4.

Mixed equilibria can be worse than every pure one.

Price of anarchy

DefinitionDefinition 20.4 — price of anarchy

For the class $\mathcal{G}(m)$ of instances with $m$ machines:

\mathrm{PoA}(m) = \max_{G\in\mathcal{G}(m)}\ \max_{P\in\mathrm{Nash}(G)} \frac{\mathrm{cost}(P)}{\mathrm{opt}(G)}.

The four variants restrict $\mathcal{G}(m)$ to identical speeds or not, and $\mathrm{Nash}(G)$ to pure profiles or not.

NotePure or mixed?

Pure fits systems where agents repeatedly make improvement moves until they settle.
Mixed fits one-shot play.
Mixed upper bounds are more robust, because mixed equilibria include the pure ones.

Pure equilibria, identical machines

Price of anarchy

The analysis mirrors Graham’s greedy list-scheduling bound of $2 - 1/m$ , and comes out slightly better.

TheoremTheorem 20.5 — PoA $2 - \frac{2}{m+1}$

Every pure equilibrium on $m$ identical machines has $\mathrm{cost}(A) \le \Big(2 - \frac{2}{m+1}\Big)\,\mathrm{opt}(G).$

ProofEvery other machine is at least half as full as the busiest

Step 1: The smallest task on the busiest machine. Let $j^*$ have maximum load and $i^*$ be its lightest task. WLOG $j^*$ holds at least two tasks; otherwise $\mathrm{cost}(A) = w_{i^*} \le \mathrm{opt}$ . So $w_{i^*} \le \tfrac12\mathrm{cost}(A)$ .

Step 2: The equilibrium condition. If some machine $j\ne j^*$ had $\ell_j < \ell_{j^*} - w_{i^*}$ , task $i^*$ would move there. So $\ell_j \ge \ell_{j^*} - w_{i^*} \ge \tfrac12\mathrm{cost}(A).$

Step 3: Average-load lower bound on OPT.

\mathrm{opt}(G) \ge \frac{\sum_i w_i}{m} = \frac{\sum_j \ell_j}{m} \ge \frac{\mathrm{cost}(A) + (m-1)\tfrac12\mathrm{cost}(A)}{m} = \frac{(m+1)\,\mathrm{cost}(A)}{2m}.

Step 4: Rearrange. $\mathrm{cost}(A) \le \frac{2m}{m+1}\,\mathrm{opt} = (2 - \frac{2}{m+1})\,\mathrm{opt}$ .

∎

NoteTight (Exercise 20.2)

For every $m$ , an instance with $2m$ tasks reaches exactly $2 - \frac{2}{m+1}$ . The two-machine example above is the case $m = 2$ : $4/3$ .

Convergence of best responses

The problem. Improvement steps always converge, but if convergence takes forever, a good equilibrium is of little use.

DefinitionMax-weight best-response policy

An agent is satisfied if it can’t lower its cost by moving. Repeatedly activate a heaviest unsatisfied agent and let it move to a least-loaded machine.

TheoremTheorem 20.6 — at most one activation per agent

On identical machines, from any assignment, the max-weight best-response policy reaches a pure equilibrium after each agent has been activated at most once.

ProofA satisfied agent is only threatened by lighter arrivals

Step 1: Two facts for identical machines.

An agent is satisfied iff the load of the other tasks on its machine is minimal.
A best response never lowers the minimum machine load. The machine left behind still has load above the target machine’s old load.

So a satisfied agent can become unsatisfied only if someone moves onto its machine.

Step 2: Someone moves onto $i$ ‘s machine. Agent $k$ , activated after $i$ , moves to $j^*$ , where $i$ sits. Max-weight order gives $w_k \le w_i$ . With loads $\ell$ measured just after the move, $k$ ‘s best-response property gives $\ell_{j^*} \le \ell_j + w_k \le \ell_j + w_i \quad \forall j.$

The key step: $\ell_j + w_i$ is what $i$ would pay by moving to $j$ . So $i$ is still satisfied. Hence once an agent has best-responded, it never needs to move again.

∎

WarningOrder matters

Activating a minimum-weight unsatisfied agent can take exponentially many steps, even on identical machines (Even-Dar et al.).

With different speeds, the loss is no longer constant, but it grows very slowly.

DefinitionThe inverse gamma function

$\Gamma(k) = (k-1)!$ for positive integers $k$ , and $\Gamma^{-1}(m) = \Theta\!\left(\frac{\log m}{\log\log m}\right).$

Upper bound

TheoremTheorem 20.7 — PoA $O(\log m/\log\log m)$

Every pure equilibrium on uniformly related machines has $\mathrm{cost}(A) = O\!\left(\frac{\log m}{\log\log m}\right) \mathrm{opt}(G)$ .

Setup. Let $c = \lfloor \mathrm{cost}(A)/\mathrm{opt}(G)\rfloor$ . Sort machines by speed, $s_1 \ge \dots \ge s_m$ , into the list $L$ . For $k = 0,\dots,c-1$ , let $L_k$ be the longest prefix of $L$ in which every machine has load $\ge k\cdot\mathrm{opt}$ . So $L_0 = L$ , and the prefixes shrink as $k$ grows.

IntuitionThe layered picture

Heavily loaded machines must be the fast ones: a heavy task sitting on a slow, busy machine would jump to a fast, lightly loaded one. Each layer $L_{k+1}$ holds weight that the optimum must spread over the next layer $L_k$ . That forces $L_k$ to have at least $k+1$ times as many machines, and the factorial growth caps the number of layers.

ProofThe recurrence

|L_k| \ge (k+1)|L_{k+1}|

, and its solution

Step 1: $|L_{c-1}| \ge 1$ . Suppose not, so machine 1 (the fastest) has load $< (c-1)\,\mathrm{opt}$ . Take a task $i$ on a machine with load $\ge c\,\mathrm{opt}$ . Moving to machine 1 costs $< (c-1)\,\mathrm{opt} + \frac{w_i}{s_1} \le c\,\mathrm{opt},$ since $w_i/s_1 \le \mathrm{opt}$ : OPT must put $i$ somewhere, at best on the fastest machine. This contradicts equilibrium.

Step 2 (Lemma 20.8): tasks in $L_{k+1}$ are in $L_k$ under OPT. Let $q$ be the fastest machine outside $L_k$ , so $\ell_q < k\,\mathrm{opt}$ . Take a task $i$ with $A(i) \in L_{k+1}$ , so $\ell_{A(i)} \ge (k+1)\,\mathrm{opt}$ . If $w_i \le s_q\,\mathrm{opt}$ , moving to $q$ would cost $\ell_q + \frac{w_i}{s_q} < (k+1)\,\mathrm{opt} \le \ell_{A(i)},$ contradicting equilibrium. So $w_i > s_q\,\mathrm{opt}$ . Any machine $j \notin L_k$ has $s_j \le s_q$ , so placing $i$ there gives load $> \mathrm{opt}$ . Hence OPT puts $i$ in $L_k$ .

Step 3: Count weight. Machines in $L_{k+1}$ carry weight $\ge (k+1)\,\mathrm{opt}\,s_j$ each. OPT must fit all of it on $L_k$ at load $\le \mathrm{opt}$ :

\sum_{j\in L_{k+1}} (k+1)\,\mathrm{opt}\,s_j \le \sum_{j\in L_k} \mathrm{opt}\,s_j \;\Rightarrow\; \sum_{j\in L_{k+1}} k\,s_j \le \sum_{j\in L_k\setminus L_{k+1}} s_j.

Step 4: Compare speeds. Let $s^*$ be the slowest speed in $L_{k+1}$ . Machines in $L_{k+1}$ are at least that fast, and those in $L_k\setminus L_{k+1}$ at most that fast. So $k\,|L_{k+1}|\,s^* \le |L_k\setminus L_{k+1}|\,s^*$ , i.e. $|L_k| \ge (k+1)|L_{k+1}|$ .

Step 5: Solve. $m = |L_0| \ge 1\cdot2\cdots(c-1)\cdot|L_{c-1}| \ge (c-1)! = \Gamma(c)$ . So $c \le \Gamma^{-1}(m)$ .

∎

Matching lower bound

TheoremTheorem 20.9 — PoA $\Omega(\log m/\log\log m)$

For every $m$ there is an instance with $n \le m$ tasks and a pure equilibrium with cost $\ge \big(\tfrac12\Gamma^{-1}(m) - 2 - o(1)\big) \mathrm{opt}(G)$ .

ExampleThe layered construction

Let $q = \Gamma^{-1}(m/3) - 1 \ge \Gamma^{-1}(m) - 2 - o(1)$ . Build groups $G_0,\dots,G_q$ :

Group	# machines	speed	tasks per machine (weight)	load
$G_k$	$q!/k!$	$2^k$	$k$ tasks of weight $2^k$	$k$

Fits in $m$ machines: $\sum_k q!/k! \le 3\cdot q! = 3\,\Gamma(q+1) \le m$ , using $\sum_k 1/k! \le e < 3$ . Spare machines get speed 1 and no tasks.

It’s an equilibrium. A task in $G_k$ pays $k$ .

Moving to $G_j$ with $j \ge k$ : load already $\ge k$ , so no gain.
Moving to $G_j$ with $j < k$ : new load $j + 2^{k-j} \ge j + (k-j+1) = k+1$ , using $2^t \ge t+1$ .
Spare machines behave like $G_0$ (load $2^k \ge k+1$ ).

Its cost is $q$ .

OPT $\le 2$ . Shift each group’s tasks down one level. $G_k$ holds $k\cdot q!/k! = q!/(k-1)! = |G_{k-1}|$ tasks, so each machine of $G_{k-1}$ gets exactly one task, of weight $2^k$ on speed $2^{k-1}$ : load 2.

graph LR
  GQ["G_q: q tasks each, load q"] -->|"OPT shifts tasks down"| GQ1["G_q-1"]
  GQ1 -->|"shift down"| DOTS["..."]
  DOTS -->|"shift down"| G0["G_0: load 2 each in OPT"]

IntuitionWhy the construction is stable

Every task sits in a coordinated but locally optimal spot. Moving down to a slower group costs at least one more unit of load. The only way to balance is a coordinated shift of all tasks one level down, which no single agent can do.

Computing pure equilibria

On related machines, it is open whether a short sequence of improvement steps always exists, and whether one can be found efficiently. A centralized algorithm does work:

AlgorithmLPT (largest processing time first)

Insert tasks in nonincreasing weight order, each on a machine minimizing its cost at insertion time.

TheoremTheorem 20.10 — LPT outputs a pure equilibrium

On uniformly related machines, LPT computes a pure Nash equilibrium.

ProofInduction on insertions; later tasks are lighter

Suppose the partial assignment of tasks $1..t-1$ is an equilibrium. Task $t$ joins machine $j^*$ . Only tasks already on $j^*$ could become unhappy. Let $i < t$ be one of them. With loads $\ell$ after inserting $t$ , and $w_t \le w_i$ :

\ell_{j^*} \le \ell_j + \frac{w_t}{s_j} \le \ell_j + \frac{w_i}{s_j} \quad\forall j.

The first inequality holds because $t$ chose $j^*$ to minimize its cost. The right-hand side is $i$ ‘s cost of moving to $j$ , so $i$ stays satisfied.

∎

Algorithm	Guarantee	Equilibrium?
LPT, identical	$\frac43 - \frac{1}{3m}$ (Graham)	yes
LPT, related	$\frac53$ (Friesen)	yes
PTAS (Hochbaum–Shmoys), related	$1+\epsilon$	not necessarily
PTAS + Nashification (Feldmann et al.)	$1+\epsilon$	yes

DefinitionNashification

Efficiently transform any assignment into a Nash equilibrium without increasing the makespan. Combined with the PTAS, it gives a $(1+\epsilon)$ -optimal pure equilibrium in polynomial time. (Exact optimum is NP-hard even on identical machines.)

Mixed equilibria, identical machines

Fully mixed equilibria and balls into bins

DefinitionFully mixed profile

Every agent puts positive probability on every machine. On identical machines, the unique fully mixed Nash equilibrium is $p_i^j = 1/m$ .

For unit tasks on identical machines, (20.1) gives every agent the same expected cost on every machine, $c_i^j = n/m + (1 - 1/m)$ . This is exactly balls into bins (compare inefficiency-of-equilibria). The optimal makespan is $\lceil n/m\rceil$ .

PropositionProposition 20.11 — maximum occupancy

Throwing $n$ balls uniformly and independently into $m$ bins, the expected maximum occupancy is $\Theta\!\left(\frac{\ln m}{\ln\!\big(1 + \frac{m}{n}\ln m\big)}\right).$

Regime	Expected max	Ratio to $n/m$
$n \ge m\log m$	$\Theta(n/m)$	$O(1)$
$n \le m^{1-\epsilon}$	$\Theta(1)$	$O(1)$
$n = m$	$\Theta(\log m/\log\log m)$	$\Theta(\log m/\log\log m)$ , the worst case

TheoremTheorem 20.12 — PoA $\Omega(\log m/\log\log m)$ , mixed, identical

With $n = m$ unit tasks, the fully mixed equilibrium has cost $\Theta(\log m/\log\log m)$ , while OPT $= 1$ .

The fully mixed Nash equilibrium conjecture is false

WarningMaximum randomization ≠ worst equilibrium

It is natural to guess that the fully mixed equilibrium, which randomizes the most, is always the worst. It isn’t.

ExampleCounterexample

$m = 2^{2k}$ , so $\sqrt m$ and $\log m$ are integers.

$\sqrt m$ large tasks of weight 1.
$(m - \sqrt m)\log m$ small tasks of weight $1/\log m$ .

Fully mixed equilibrium: $\sqrt m \le m^{1-\epsilon}$ large balls give $O(1)$ per bin. About $m\log m$ small balls give $O(\log m)$ per bin, times weight $1/\log m$ , which is $O(1)$ . So the makespan is $O(1)$ .

Segregated equilibrium: large tasks uniform over group A (the first $\sqrt m$ machines), small tasks uniform over group B (the rest).

Large task: cost on A is $1 + (1 - 1/\sqrt m) < 2$ ; on B it is $1 + 1 = 2$ . It prefers A.
Small task: cost on B is $< 1 + 1/\log m$ ; on A it is $1 + 1/\log m$ . It prefers B.

So this is an equilibrium, with $\sqrt m$ balls into $\sqrt m$ bins in group A, giving makespan $\Theta(\log m/\log\log m)$ . That is a factor $\Theta(\log m/\log\log m)$ worse than the fully mixed equilibrium.

IntuitionWhy concentration beats spreading

Collisions hurt most when balls and bins are equal in number. The segregated equilibrium creates exactly that regime among the heavy tasks, while the fully mixed one drowns them in too many bins.

Upper bound

TheoremTheorem 20.13 — PoA $O(\log m/\log\log m)$ , mixed, identical

Every mixed equilibrium on identical machines has $\mathrm{cost}(P) = O\!\left(\frac{\log m}{\log\log m}\right) \mathrm{opt}(G)$ .

The proof has two steps: (1) bound the maximum expected load; (2) show the expected maximum exceeds it by at most $O(\log m/\log\log m)$ .

LemmaLemma 20.14 — weighted Chernoff bound

If $X_1,\dots,X_N$ are independent with values in $[0,z]$ and $X = \sum X_i$ , then $\Pr[X \ge t] \le \left(\frac{e\,\mathbb{E}[X]}{t}\right)^{t/z}.$

NoteCited

See Mitzenmacher–Upfal (2005) for derivations.

ProofExpected loads are small, and tails are Chernoff-thin

Step 1: Maximum expected load. Adapt Theorem 20.5, with $i^*$ the lightest task having positive probability on a machine $j^*$ of maximum expected load, and expected loads throughout. This gives $\mathbb{E}[\ell_j] \le (2 - \frac{2}{m+1})\mathrm{opt} < 2\,\mathrm{opt}$ for all $j$ .

Step 2: Tail of one machine. Every task weighs at most opt. By Lemma 20.14,

\Pr[\ell_j \ge t] \le \left(\frac{2e\,\mathrm{opt}}{t}\right)^{t/ \mathrm{opt}}.

Step 3: Pick the threshold. Let $\tau = 2\,\mathrm{opt}\,\frac{\ln m}{\ln\ln m}$ . For large $m$ , $\frac{e\ln\ln m}{\ln m} \le \frac{1}{\sqrt{\ln m}}$ and $\le e^{-1}$ , so

\Pr[\ell_j \ge \tau + x] \le \Big(\tfrac{1}{\sqrt{\ln m}}\Big)^{2\ln m/ \ln\ln m} e^{-x/\mathrm{opt}} = \frac{1}{m}\,e^{-x/\mathrm{opt}}.

Step 4: Integrate with a union bound.

\mathrm{cost}(P) = \int_0^\infty \Pr\Big[\max_j\ell_j \ge t\Big]dt \le \tau + \int_0^\infty\sum_j \Pr[\ell_j \ge \tau + x]\,dx \le \tau + \int_0^\infty e^{-x/\mathrm{opt}}dx = \tau + \mathrm{opt}.

The key step: the $m$ machines each contribute a tail of $1/m$ beyond $\tau$ , so the union bound costs only an additive opt.

∎

This case combines both effects: a layered speed structure and collisions. The combination costs only a little more.

TheoremTheorem 20.15 — PoA $O(\log m/\log\log\log m)$

Every mixed equilibrium on uniformly related machines has $\mathrm{cost}(P) = O\!\left(\frac{\log m}{\log\log\log m}\right) \mathrm{opt}(G)$ .

Setup. Normalize $\mathrm{opt} = 1$ . Let $c = \lfloor\max_j\mathbb{E}[\ell_j]\rfloor$ .

Layers with expected loads. Define prefixes $L_k$ as in Theorem 20.7 but using $\mathbb{E}[\ell_j] \ge k$ . The same recurrence gives $c \le \Gamma^{-1}(m)$ . Set $C = \max\{c+1, \frac{\ln m}{\ln\ln m}\} = \Theta(\frac{\ln m}{\ln\ln m})$ .
Split each machine’s tasks. $T_j^{(1)}$ are tasks with $p_i^j \ge \frac14$ , and $T_j^{(2)}$ are those with $p_i^j \in (0,\frac14)$ . Correspondingly $\ell_j = \ell_j^{(1)} + \ell_j^{(2)}$ .

DerivationHigh-probability tasks are deterministic-ish

\ell_j^{(1)} \le \sum_{i\in T_j^{(1)}}\frac{w_i}{s_j} \le 4\sum_{i\in T_j^{(1)}} \frac{w_i\,p_i^j}{s_j} = 4\,\mathbb{E}[\ell_j^{(1)}] \le 4C. \tag{20.2}

This holds with certainty: each such task counts at most $4\times$ its expected contribution.

For $T_j^{(2)}$ we need Chernoff, which needs a weight bound. Group the machines as $G_k = L_k\setminus L_{k+1}$ (and $G_{c-1} = L_{c-1}$ ), and let $s(k)$ be the fastest speed in $G_k$ .

LemmaLemma 20.16 — speeds double every two layers

$s(k+2) \ge 2\,s(k)$ for $0 \le k \le c-4$ .

ProofA light task on a deep layer would escape to

G_k

Step 1: A light task deep in the layers. Some task $i$ with $w_i \le s(k+2)$ has positive probability on a machine in $L_{k+3}$ . OPT must move expected load off $L_{k+3}$ , onto machines no faster than $s(k+2)$ , and only light enough tasks fit there at load $\le 1$ .

Step 2: Its equilibrium cost is $\ge k+3$ , since it is in the support of a machine with expected load $\ge k+3$ .

Step 3: If speeds didn’t double. Suppose $s(k) > s(k+2)/2$ . On the fastest machine of $G_k$ , whose expected load is $< k+1$ , task $i$ would pay $< k + 1 + \frac{w_i}{s(k)} < k + 1 + \frac{2w_i}{s(k+2)} \le k + 3.$ That contradicts equilibrium.

∎

LemmaLemma 20.17 — low-probability tasks are light

For $i \in T_j^{(2)}$ : $w_i \le 12\,s_j$ .

ProofCompare with a machine two layers up

Let $j \in G_k$ . Since $\mathbb{E}[\ell_j] \ge k$ and $1 - p_i^j \ge \frac34$ , $c_i^j \ge k + \frac{3w_i}{4s_j}.$

Case $k \ge c-3$ . If $w_i > 12 s_j$ , then $c_i^j > k + 9 \ge c + 6$ . But $i$ can go to the fastest machine for about $c + O(1)$ : its expected load is $< c+1$ , plus at most $w_i/s_1 \le 1$ . This contradicts equilibrium.

Case $k \le c-4$ . Let $q$ be the fastest machine of $G_{k+2}$ . By Lemma 20.16, $s_q \ge 2s(k) \ge 2s_j$ , so $c_i^q \le k + 3 + \frac{w_i}{2s_j}$ . Equilibrium ( $p_i^j > 0$ ) gives $c_i^j \le c_i^q$ :

k + \frac{3w_i}{4s_j} \le k + 3 + \frac{w_i}{2s_j} \;\Rightarrow\; w_i \le 12\,s_j.

∎

ProofTheorem 20.15 — assemble

Step 1: Chernoff for $\ell^{(2)}_j$ . Each summand lies in $[0, 12]$ and $\mathbb{E}[\ell^{(2)}_j] \le C$ , so $\Pr[\ell_j^{(2)} \ge \alpha C] \le (e/\alpha)^{\alpha C/12}$ .

Step 2: Threshold. Let $\tau = 24\,C\,\frac{\ln\ln m}{\ln\ln\ln m} = \Theta(\frac{\ln m}{\ln\ln\ln m})$ . For large $m$ , the base is at most $(\ln\ln m)^{-1/2}$ and at most $e^{-2}$ . Together with $C \ge \frac{\ln m}{\ln\ln m}$ , this gives $\Pr[\ell_j^{(2)} \ge \tau + x] \le \frac1m\,e^{-x/6}.$

Step 3: Union bound and integrate. $\mathbb{E}[\max_j\ell_j^{(2)}] \le \tau + 6$ . (20.3)

Step 4: Combine.

\mathrm{cost}(P) = \mathbb{E}\Big[\max_j\ell_j\Big] \le \max_j \ell_j^{(1)} + \mathbb{E}\Big[\max_j\ell_j^{(2)}\Big] \le 4C + \tau + 6 = O\!\left(\frac{\log m}{\log\log\log m}\right).

∎

IntuitionWhy only $\log\log m/\log\log\log m$ more

The layering already caps expected loads at $C \approx \log m/\log\log m$ . Collisions then add a balls-into-bins factor. But with expected loads already that large (many balls per bin, in Proposition 20.11 terms), the extra factor is only $\Theta(\log\log m/\log\log\log m)$ .

TheoremTheorem 20.18 — matching lower bound

For every $m$ there is an instance with $n \le m$ tasks and a mixed equilibrium with $\mathrm{cost}(P) = \Omega\!\left(\frac{\log m}{\log\log\log m}\right) \mathrm{opt}(G)$ .

ProofRandomize the middle layer of the Theorem 20.9 construction

Step 1: Randomize one group. Take $k = \lceil q/2\rceil$ and $M = |G_k| = q!/k! \ge (q/2)^{q/2}$ , so $\log M = \Theta(q\log q) = \Theta(\log m)$ . The $kM$ tasks of $G_k$ (each of weight $2^k$ ) now pick a machine of $G_k$ uniformly. Everything else stays as in $A$ .

Step 2: Still an equilibrium. A randomized task expects $c_i^j = k + (1 - \frac1M) < k+1$ on $G_k$ , and moving to another group costs $\ge k+1$ (Theorem 20.9).

Step 3: Cost. OPT is still 2. The makespan is at least the maximum occupancy among $G_k$ ‘s machines: $N = kM$ balls into $M$ bins. By Proposition 20.11,

\Theta\!\left(\frac{\ln M}{\ln(1 + \frac1k\ln M)}\right) = \Theta\!\left(\frac{\log m}{\log\log\log m}\right),

since $k = \Theta(\log m/\log\log m)$ makes $\frac1k\ln M = \Theta(\log\log m)$ .

∎

Summary

ImportantTable 20.1 — price of anarchy of load balancing games

	Identical	Uniformly related
Pure	$2 - \frac{2}{m+1}$	$\Theta\!\left(\frac{\log m}{\log\log m}\right)$
Mixed	$\Theta\!\left(\frac{\log m}{\log\log m}\right)$	$\Theta\!\left(\frac{\log m}{\log\log\log m}\right)$

All bounds are tight. Apart from pure/identical, the price of anarchy grows only sublogarithmically in $m$ . This gives a first game-theoretic explanation of why uncoordinated systems share resources fairly efficiently.

NoteOpen problems and directions

Short improvement sequences on related machines. Does one always exist from every assignment, and can it be found efficiently? The author considers this central, since equilibria matter only if they are reached quickly.
Other dynamics: strategic or coordinated rules, or evolutionary dynamics (Chapter 29), converging fast to exact or approximate equilibria.
Richer models: realistic cost functions, other social costs.
Coordination mechanisms (Christodoulou et al.): design machine scheduling policies so that selfishness hurts less. Simple policies cut the PoA from logarithmic to constant (see inefficiency-of-equilibria).

Quick reference

Object	Statement	Note
Load	$\ell_j = \sum_{A(i)=j} w_i/s_j$	makespan $= \max_j\ell_j$
Expected cost (20.1)	$c_i^j = \mathbb{E}[\ell_j] + (1-p_i^j)w_i/s_j$	exceeds $\mathbb{E}[\ell_j]$ unless $p = 1$
Props 20.1–20.2	support ⊆ cost-minimizing machines	mixed / pure
Prop 20.3	pure equilibria exist	sorted loads decrease lexicographically
PoS	$= 1$	improvement steps from OPT
Example (2, 2, 1, 1)	OPT 3, worst pure 4, fully mixed 4.25	mixed can be worse
Thm 20.5	pure, identical: $\le 2 - \frac{2}{m+1}$	tight (Exercise 20.2)
Thm 20.6	max-weight best response: each agent moves at most once	min-weight: exponential
$\Gamma^{-1}(m)$	$\Theta(\log m/\log\log m)$	$\Gamma(k) = (k-1)!$
Thm 20.7	pure, related: $O(\log m/\log\log m)$	$\lvert L_k\rvert \ge (k+1)\lvert L_{k+1}\rvert$
Lemma 20.8	tasks on $L_{k+1}$ lie in $L_k$ under OPT	heavy tasks need fast machines
Thm 20.9	matching lower bound	groups $q!/k!$ at speed $2^k$
Thm 20.10	LPT gives a pure equilibrium	$5/3$ related, $4/3 - 1/(3m)$ identical
Nashification	any assignment → equilibrium, same makespan	+ PTAS ⇒ $(1+\epsilon)$
Fully mixed	$p_i^j = 1/m$ , unique on identical machines	balls into bins
Prop 20.11	max occupancy $\Theta\big(\ln m/\ln(1 + \frac mn\ln m)\big)$	worst at $n = m$
Thm 20.12	mixed, identical: $\Omega(\log m/\log\log m)$
FMNE conjecture	false	segregated large/small tasks
Lemma 20.14	$\Pr[X\ge t] \le (e\,\mathbb{E}X/t)^{t/z}$	weighted Chernoff
Thm 20.13	mixed, identical: $O(\log m/\log\log m)$	$\max\mathbb{E} < 2$ opt, then Chernoff + union
Lemmas 20.16–20.17	speeds double every 2 layers; $w_i \le 12s_j$ for $p < 1/4$
Thm 20.15	mixed, related: $O(\log m/\log\log\log m)$	$4C + \tau + 6$
Thm 20.18	matching lower bound	randomize layer $q/2$

Facts to keep to hand

Two independent sources of inefficiency. Coordinated but local: pure equilibria on related machines are local optima under single-task moves, and the layered speed structure costs $\log m/\log\log m$ . Uncoordinated collisions: mixed equilibria cost the balls-into-bins factor $\log m/\log\log m$ . Their combination costs only an extra $\log\log m/\log\log\log m$ .
Every mixed upper bound has the same two steps. First bound the maximum expected load by rerunning the pure argument with expectations. Then bound expected maximum / maximum expected with a weighted Chernoff bound plus a union bound. The union bound is affordable because each machine’s tail beyond $\tau$ is $\le 1/m$ .
Chernoff needs a weight cap, and the cap comes from equilibrium. On identical machines it is $w \le \mathrm{opt}$ . On related machines, tasks with $p \ge 1/4$ are bounded deterministically, and those with $p < 1/4$ are light ( $w \le 12s_j$ ) because Lemma 20.16’s doubling offers a cheaper machine two layers up.
Every pure upper bound is “a light task would move.” Theorem 20.5: the lightest task on the busiest machine. Theorem 20.7 and Lemma 20.8: tasks on deep layers must be heavy relative to faster free machines, and that forces factorial growth of the layers.
Your own weight is always on your machine. The $(1-p_i^j)w_i/s_j$ term in (20.1) creates the example’s 4.25, keeps the segregated equilibrium stable, and makes randomized tasks in Theorem 20.18 pay $< k+1$ .
Maximum randomization is not the worst case. Concentrating equally many heavy balls and bins beats spreading everything.
Order matters for best responses. Heaviest-first converges in $n$ steps on identical machines, lightest-first can take exponential time, and on related machines the question is open. Offline, LPT is heaviest-first by design and yields an equilibrium.

References

Nisan, Roughgarden, Tardos, Vazirani, Algorithmic Game Theory — chapter 20 (Vöcking)

Related

Motivation: servers without a scheduler

The model

The game

Worked example: two machines, weights 2, 2, 1, 1

Price of anarchy

Pure equilibria, identical machines

Price of anarchy

Convergence of best responses

Upper bound

Matching lower bound

Computing pure equilibria

Mixed equilibria, identical machines

Fully mixed equilibria and balls into bins

The fully mixed Nash equilibrium conjecture is false

Upper bound

Summary

Quick reference

References

Mentioned in

Related

Motivation: servers without a scheduler

The model

The game

Worked example: two machines, weights 2, 2, 1, 1

Price of anarchy

Pure equilibria, identical machines

Price of anarchy

Convergence of best responses

Pure equilibria, uniformly related machines

Upper bound

Matching lower bound

Computing pure equilibria

Mixed equilibria, identical machines

Fully mixed equilibria and balls into bins

The fully mixed Nash equilibrium conjecture is false

Upper bound

Mixed equilibria, uniformly related machines

Summary

Quick reference

References

Mentioned in