Near Optimality in Covering and Packing Games by Exposing Global Information

Details Near Optimality in Covering and Packing Games by Exposing Global Information Near Optimality in Covering and Packing Games by Exposing Global Information

2011-09-16

arxiv.org/abs/1109.3606v1

Computer Science

Computer Science and Game Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Near Optimality in Covering and Packing Games by Exposing Global Information does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Near Optimality in Covering and Packing Games by Exposing Global Information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Near Optimality in Covering and Packing Games by Exposing Global Information will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-534935