Near-Optimality in Covering Games by Exposing Global Information

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 177
  • Download : 0
Mechanism design for distributed systems is fundamentally concerned with aligning individual incentives with social welfare to avoid socially inefficient outcomes that can arise from agents acting autonomously. One simple and natural approach is to centrally broadcast nonbinding advice intended to guide the system to a socially near-optimal state while still harnessing the incentives of individual agents. The analytical challenge is proving fast convergence to near optimal states, and in this article we give the first results that carefully constructed advice vectors yield stronger guarantees. We apply this approach to a broad family of potential games modeling vertex cover and set cover optimization problems in a distributed setting. This class of problems is interesting because finding exact solutions to their optimization problems is NP-hard yet highly inefficient equilibria exist, so a solution in which agents simply locally optimize is not satisfactory. We show that with an arbitrary advice vector, a set cover game quickly converges to an equilibrium with cost of the same order as the square of the social cost of the advice vector. More interestingly, we show how to efficiently construct an advice vector with a particular structure with cost O(log n) times the optimal social cost, and we prove that the system quickly converges to an equilibrium with social cost of this same order.
Publisher
ACM
Issue Date
2014-10
Language
English
Citation

ACM Transactions on Economics and Computation, v.2, no.4, pp.1 - 22

ISSN
2167-8375
DOI
10.1145/2597890
URI
http://hdl.handle.net/10203/201133
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0