  Covering and packing problems can be modeled as games to encapsulate
interesting social and engineering settings. These games have a high Price of
Anarchy in their natural formulation. However, existing research applicable to
specific instances of these games has only been able to prove fast convergence
to arbitrary equilibria. This paper studies general classes of covering and
packing games with learning dynamics models that incorporate a central
authority who broadcasts weak, socially beneficial signals to agents that
otherwise only use local information in their decision-making. Rather than
illustrating convergence to an arbitrary equilibrium that may have very high
social cost, we show that these systems quickly achieve near-optimal
performance.
  In particular, we show that in the public service advertising model, reaching
a small constant fraction of the agents is enough to bring the system to a
state within a log n factor of optimal in a broad class of set cover and set
packing games or a constant factor of optimal in the special cases of vertex
cover and maximum independent set, circumventing social inefficiency of bad
local equilibria that could arise without a central authority. We extend these
results to the learn-then-decide model, in which agents use any of a broad
class of learning algorithms to decide in a given round whether to behave
according to locally optimal behavior or the behavior prescribed by the
broadcast signal. The new techniques we use for analyzing these games could be
of broader interest for analyzing more general classic optimization problems in
a distributed fashion.
