Motivation

Load balancing on identical parallel links is the example Koutsoupias and Papadimitriou used to define the price of anarchy: the ratio of the social cost of a Nash equilibrium to the social optimum (Koutsoupias–Papadimitriou 2009). Theorem 3 of the journal version is the two-link case. It is the first sharp bound in that paper, and the later two-speed bound is proved by the same comparison.

Setting

There are $n$ agents and $m$ identical links. Agent $i$ has traffic $w_i$ and chooses a link. A pure profile $s$ assigns each agent a link. The load of link $j$ is the sum of the traffics sent there, and the cost of an agent is the load of its own link. A mixed profile $p$ gives, for each agent $i$ and link $j$, a probability $p_i^j$. Agents randomize independently.

The social cost is the expected makespan: the expected value of the maximum link load. The social optimum $\mathrm{opt}$ is the least makespan over pure assignments. The contribution probability $q_i$ is the probability that agent $i$ sits on the lexicographically first link of maximum load. The collision probability of agents $i$ and $k$ is $t_{ik}=\sum_j p_i^j p_k^j$.

Agents are Fin n and links are Fin m, numbered from 0. Payoffs are minus costs, so a Nash equilibrium is a mixed Nash equilibrium of that payoff game.

Formalization targets

Theorem 3

$$\mathrm{cost}(p)\le \frac{3}{2}\,\mathrm{opt}$$

for every Nash equilibrium $p$ on $m=2$ identical links, and every positive traffic vector. This is the goal.

Expected cost

$$c_i=w_i+\sum_{k\ne i}t_{ik}w_k$$

for a mixed profile. This is an identity in the proof of Theorem 3, not a Nash fact.

Social cost

$$\mathrm{cost}=\sum_i q_i w_i .$$

Equation (7)

$$q_i+q_k\le 1+t_{ik}\qquad(i\ne k).$$

Significance

The $\tfrac{3}{2}$ bound is what the paper proves for two identical links, and it is tight. The two identities are the rewrite the proof treats as immediate: social cost as a weighted sum of contribution probabilities, and an agent's expected cost as its own traffic plus collisions. Formalizing them records those rewrites as statements with the side conditions the prose leaves implicit, in particular that $p$ is a profile of lotteries and that $m\ge 1$ wherever a maximum load is taken.

The statements of this mission are the ones already published under WorstCaseEq.Identical. This proposal gathers them. It does not replace them.

Difficulty

The bound is not the definition of the ratio. Expanding the expectation produces a sum over pure profiles, and the lexicographic choice of the maximum link is there so that exactly one link is credited. Treating $q_i$ as the probability of an arbitrary maximum link makes (7) the wrong inequality. Positivity of the traffics is a hypothesis of Theorem 3, not of the two identities.

Formalization scope

The model is the published definition WorstCaseEq_Identical_Model, on top of agt_games. Social cost and contribution probabilities require m nonempty. The expected-cost identity requires a mixed profile and does not require a Nash equilibrium. Theorem 3 fixes $m=2$ and requires every traffic to be positive.

A development that hard-codes two agents, or that proves the bound only for pure equilibria, is not this theorem.

Selected references

Elias Koutsoupias and Christos Papadimitriou, Worst-case equilibria, Computer Science Review 3 (2009), 65–69. doi:10.1016/j.cosrev.2009.04.003. Theorem 3 and its proof, PDF pp. 2–5.