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