file.pdf (175.85 kB)
Download fileImproved Equilibria via Public Service Advertising
journal contribution
posted on 1999-07-01, 00:00 authored by Maria-Florina Balcan, Avrim Blum, Yishay MonsourMany natural games have both high and low cost Nash
equilibria: their Price of Anarchy is high and yet their
Price of Stability is low. In such cases, one could hope to
move behavior from a high cost equilibrium to a low cost
one by a “public service advertising campaign” encouraging
players to follow the low-cost equilibrium, and if every
player follows the advice then we are done. However, the
assumption that everyone follows instructions is unrealistic.
A more natural assumption is that some players will follow
them, while other players will not. In this paper we consider
the question of to what extent can such an advertising
campaign cause behavior to switch from a bad equilibrium
to a good one even if only a fraction of people actually
follow the given advice, and do so only temporarily. Unlike
the “value of altruism” model, we assume everyone will
ultimately act in their own interest.
We analyze this question for several important and
widely studied classes of games including network design
with fair cost sharing, scheduling with unrelated machines,
and party affiliation games (which include consensus and
cut games). We show that for some of these games (such
as fair cost sharing), a random α fraction of the population
following the given advice is sufficient to get a guarantee
within an O(1/α) factor of the price of stability for any
α > 0. For other games (such as party affiliation games),
there is a strict threshold (in this case, α < 1/2 yields almost
no benefit, yet α > 1/2 is enough to reach near-optimal
behavior). Finally, for some games, such as scheduling,
no value α < 1 is sufficient. We also consider a “viral
marketing” model in which certain players are specifically
targeted, and analyze the ability of such targeting to influence
behavior using a much smaller number of targeted players.