tions, and work toward multiparameter analogs of Myerson’s Lemma.

Quantifying inefficiency
and the Price of anarchy

The truthful mechanisms examined earlier are—by design—strategically degenerate in that the best course of action of a participant (that is, truthtel-ling) does not depend on the actions taken by the others. When a designer cannot specify the rules of the game and directly dictate the allocation of resources—or when there is no central designer at all—dependencies between different participants’ optimal courses of action are generally unavoidable and preclude exact optimization of standard objective functions. This harsh reality motivates adopting an equilibrium concept—a rigorous proposal for the possible outcomes of a game with self-interested participants—and an approximation measure that quantifies the inefficiency of a game’s equilibria, to address the following basic question:

(Q2) When, and in what senses, are game-theoretic equilibria guaranteed to approximately optimize natural objective functions?

Such a guarantee implies that the benefit of imposing additional control over the system is small, and is particularly reassuring when implementing an optimal solution is infeasible (as in a typical Internet application).

Routing with Congestion. There are
no w numerous answers to question (Q2)
in different models. We describe one by
Roughgarden and Tardos, 37, 39 for a mod-
el of “selfish routing” originally pro-
posed for road traffic (see Beckmann4)
and subsequently adapted to commu-
nication networks (see Bertsekas and
Tsitsiklis5). This was the first general ap-
proximation bound on the inefficiency
of equilibria; the idea of quantifying
such inefficiency was explored previ-
ously in a scheduling model. 22

The price of anarchy (POA) of a selfish routing network is the ratio of the average user cost at equilibrium and in an optimal routing—4/3 in both of the networks in Figure 1. The closer the POA is to 1, the lesser the consequences of selfish behavior. Replacing the cost function of the second edge in Figure 1a by c2 (x) = xd for large d shows that the POA can

 

figure 1. two selfish routing networks with price of anarchy 4/3. one unit of selfish traffic travels from s to t. at equilibrium, all traffic travels on the bottom path and the zig-zag path, respectively. in an optimal solution, traffic is split equally between the two edges and between the two two-hop paths, respectively.

c(x) = 1

v
c(x) = x
c(x) = 1

c(x) = 0

s
t
s
t
c(x) = 1

c(x) = x
c(x) = x
w

(a) Pigou’s example
(b) Braess’ Paradox