research-article

Near-Optimality in Covering Games by Exposing Global Information

Authors:

Maria-Florina Balcan,

Georgios Piliouras,

Jinwoo ShinAuthors Info & Claims

ACM Transactions on Economics and Computation (TEAC), Volume 2, Issue 4

Article No.: 13, Pages 1 - 22

https://doi.org/10.1145/2597890

Published: 28 October 2014 Publication History

Abstract

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.

References

[1]

E. Anshelevich, A. Dasgupta, É. Tardos, and T. Wexler. 2008. Near-optimal network design with selfish agents. Theory Comput. 4, 1, 77--109.

[2]

M. Balcan, S. Krehbiel, G. Piliouras, and J. Shin. 2012. Minimally invasive mechanism design: Distributed covering with carefully chosen advice. In Proceedings of the 51st IEEE Annual Conference on Decision and Control (CDC). 2690--2695.

[3]

M.-F. Balcan, A. Blum, and Y. Mansour. 2009. Improved equilibria via public service advertising. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 728--737.

Digital Library

[4]

M.-F. Balcan, A. Blum, and Y. Mansour. 2013. Circumventing the price of anarchy: Leading dynamics to good behavior. SIAM J. Comput. 42, 1, 230--264.

Digital Library

[5]

N. Buchbinder, L. Lewin-Eytan, J. S. Naor, and A. Orda. 2010. Non-Cooperative cost sharing games via subsidies. Theory Comput. Syst. 47, 1, 15--37.

Digital Library

[6]

E. Campos-Naóez, A. Garcia, and C. Li. 2008. A game-theoretic approach to efficient power management in sensor networks. Oper. Res. 56, 3, 552--561.

Digital Library

[7]

J. Cardinal and M. Hoefer. 2006. Selfish Service Installation in Networks. In Proceedings of the 2nd International Conference on Internet and Network Economics (WINE'06). P. Spirakis, M. Mavronicolas, and S. Kontogiannis (Eds.), Lecture Notes in Computer Science, Vol. 4286, Springer, Berlin, 174--185.

Digital Library

[8]

J. Cardinal and M. Hoefer. 2010. Non-cooperative facility location and covering games. Theoret. Comput. Sci. 411, 16--18, 1855--1876.

Digital Library

[9]

V. Chvatal. 1979. A greedy heuristic for the set-covering problem. Math. Oper. Res. 4, 3, 233--235.

Digital Library

[10]

E. D. Demaine and M. Zadimoghaddam. 2010. Constant price of anarchy in network creation games via public service advertising. In Algorithms and Models for the Web-Graph (WAW). Lecture Notes in Computer Science, Vol. 6516, Springer, Berlin, 122--131.

[11]

X. Deng, T. Ibaraki, and H. Nagamochi. 1999. Algorithmic aspects of the core of combinatorial optimization games. Math. Oper. Res. 24, 751--766.

Digital Library

[12]

N. Devanur, M. Mihail, and V. Vazirani. 2005. Strategyproof cost-sharing mechanisms for set cover and facility location games. Decisi. Supp. Syst. 39, 1, 11--22.

Digital Library

[13]

B. Escoffier, L. Gourves, and J. Monnot. 2010. On the impact of local taxes in a set cover game. In Structural Information and Communication Complexity (SIROCCO). Lecture Notes in Computer Science, Vol. 6058, Springer-Verlag New York Inc, 2--13.

Digital Library

[14]

A. Fabrikant, A. Luthra, E. Maneva, C. Papadimitriou, and S. Shenker. 2003. On a network creation game. In Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing (PODC). ACM, 347--351.

Digital Library

[15]

Q. Fang and L. Kong. 2007. Core stability of vertex cover games. In Proceedings of the 3rd International Conference on Internet and Network Economics (WINE'07). Springer-Verlag, Berlin, 482--490.

Digital Library

[16]

M. Fox, G. Piliouras, and J. Shamma. 2012. Medium and long-run properties of linguistic community evolution. In Proceedings of the 9th International Conference on the Evolution of Language (Evolang IX). 110--118.

[17]

T. Harks and B. Peis. 2012. Resource buying games. In Proceedings of the European Symposium on Algorithms (ESA). 563--574.

Digital Library

[18]

M. Hoefer. 2011. Competitive cost sharing with economies of scale. Algorithmica 60, 4, 743--765.

Digital Library

[19]

N. Immorlica, M. Mahdian, and V. Mirrokni. 2008. Limitations of cross-monotonic cost-sharing schemes. ACM Trans. Algor. 4, 2, 24.

Digital Library

[20]

N. Immorlica, E. Markakis, and G. Piliouras. 2010. Coalition formation and price of anarchy in Cournot oligopolies. In Proceedings of the 6th International Conference on Internet and Network Economics (WINE'10). Springer-Verlag, Berlin, 270--281.

Digital Library

[21]

Y. Jin, J. Ok, Y. Yi, and J. Shin. 2013. On the impact of global information on diffusion of innovations over social networks. In Proceedings of the IEEE International Workshop on Network Science for Communication Networks (NETSCICOM). 3267--3272.

[22]

D. Kempe, J. Kleinberg, and É. Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'03). ACM, New York, 137--146.

Digital Library

[23]

D. Kempe, J. Kleinberg, and É. Tardos. 2005. Influential nodes in a diffusion model for social networks. In Proceedings of ICALP. Springer Verlag, 1127--1138.

Digital Library

[24]

R. Kleinberg, G. Piliouras, and É. Tardos. 2009. Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract. In Proceedings of the 41st annual ACM Symposium on Theory of Computing (STOC'09). ACM, New York, 533--542.

Digital Library

[25]

R. Kleinberg, G. Piliouras, and É. Tardos. 2011a. Load balancing without regret in the bulletin board model. Distrib. Comput. 24, 1, 21--29.

Digital Library

[26]

R. D. Kleinberg, K. Ligett, G. Piliouras, and É. Tardos. 2011b. Beyond the Nash equilibrium barrier. In Proceedings of the Innovations in Computer Science (ICS). 125--140.

[27]

E. Koutsoupias and C. Papadimitriou. 1999. Worst-case equilibria. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). Springer-Verlag, 404--413.

Digital Library

[28]

X. Li, Z. Sun, and W. Wang. 2005. Cost sharing and strategyproof mechanisms for set cover games. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). Vol. 3404. Springer, 218--230.

Digital Library

[29]

X. Li, Z. Sun, W. Wang, X. Chu, S. Tang, and P. Xu. 2010. Mechanism design for set cover games with selfish element agents. Theoret. Comput. Sci. 411, 1, 174--187.

Digital Library

[30]

K. Ligett and G. Piliouras. 2011. Beating the best Nash without regret. SIGecom Exch. 10, 1, 23--26.

Digital Library

[31]

R. Machado and S. Tekinay. 2007. Diffusion-based approach to deploying wireless sensors to satisfy coverage, connectivity and reliability. In Proceedings of the 4th Annual International Conference on Mobile and Ubiquitous Systems: Networking Services (MobiQuitous'07). 1--8.

Digital Library

[32]

D. Monderer and L. Shapley. 1996. Potential games. Games Econ. Behav. 14, 124--143.

[33]

U. Nadav and G. Piliouras. 2010. No regret learning in oligopolies: Cournot vs. Bertrand. In Proceedings of the 3rd International Conference on Algorithmic Game Theory (SAGT'10). Springer-Verlag, Berlin, 300--311.

Digital Library

[34]

N. Nisan, T. Roughgarden, É. Tardos, and V. V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press, New York.

Digital Library

[35]

G. Piliouras and J. S. Shamma. 2014. Optimization despite chaos: Convex relaxations to complex limit sets via Poincaré recurrence. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 861--873.

Digital Library

[36]

G. Piliouras, T. Valla, and L. A. Végh. 2012. LP-Based covering games with low price of anarchy. In Proceedings of the 8th International Conference on Internet and Network Economics (WINE'12). Springer-Verlag, Berlin, 184--197.

Digital Library

[37]

R. Raz and S. Safra. 1997. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the ACM Symposium on Theory of Computing (STOC). 475--484.

Digital Library

[38]

R. Rosenthal. 1973. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 1, 65--67.

Digital Library

[39]

N. Sadagopan, M. Singh, and B. Krishnamachari. 2006. Decentralized utility-based sensor network design. Mob. Netw. Appl. 11, 3, 341--350.

Digital Library

[40]

S. Schmid and R. Wattenhofer. 2006. Algorithmic models for sensor networks. In Proceedings of the 14th International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS). 51--54.

Digital Library

[41]

J. Shamma (Ed). 2008. Cooperative Control of Distributed Multiagent Systems. Wiley.

Digital Library

[42]

Y. Sharma and D. P. Williamson 2007. Stackelberg thresholds in network routing games or the value of altruism. In Proceedings of the ACM Conference on Electronic Commerce (EC). 93--102.

Digital Library

[43]

V. Zalyubovskiy, A. Erzin, S. Astrakov, and H. Choo. 2009. Energy-efficient area coverage by sensors with adjustable ranges. Sensors 9, 4, 2446--2460.

[44]

M. Zennaro, A. Bagula, D. Gascon, and A. B. Noveleta. 2010. Long distance wireless sensor networks: simulation vs reality. In Proceedings of the 4th ACM Workshop on Networked Systems for Developing Regions (NSDR'10). ACM, New York, 12:1--12:2.

Digital Library

Cited By

Riehl JCao M(2015)Control of Stochastic Evolutionary Games on Networks∗∗This work was supported in part by the European Research Council (ERCStG-307207).IFAC-PapersOnLine10.1016/j.ifacol.2015.10.31048:22(76-81)Online publication date: 2015
https://doi.org/10.1016/j.ifacol.2015.10.310

Index Terms

Near-Optimality in Covering Games by Exposing Global Information

Recommendations

Large Market Games with Near Optimal Efficiency
EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

As is well known, many classes of markets have efficient equilibria, but this depends on agents being non-strategic, i.e. that they declare their true demands when offered goods at particular prices, or in other words, that they are price-takers. An ...
Core-competitive Auctions
EC '15: Proceedings of the Sixteenth ACM Conference on Economics and Computation

One of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high value for the goods and a competitive outcome would have generated a significant revenue. A competitive outcome is one for which it is ...
LP-Based Covering Games with Low Price of Anarchy

We design a new class of vertex and set cover games, where the price of anarchy bounds match the best known constant factor approximation guarantees for the centralized optimization problems for linear and also for submodular costs. This is in contrast ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Economics and Computation

ACM Transactions on Economics and Computation Volume 2, Issue 4

October 2014

162 pages

ISSN:2167-8375

EISSN:2167-8383

DOI:10.1145/2684807

Editors:
Vincent Conitzer
Duke University
,
Preston McAfee
Microsoft

Issue’s Table of Contents

Copyright © 2014 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 October 2014

Accepted: 01 February 2014

Revised: 01 October 2013

Received: 01 December 2012

Published in TEAC Volume 2, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
203
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)2

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Riehl JCao M(2015)Control of Stochastic Evolutionary Games on Networks∗∗This work was supported in part by the European Research Council (ERCStG-307207).IFAC-PapersOnLine10.1016/j.ifacol.2015.10.31048:22(76-81)Online publication date: 2015
https://doi.org/10.1016/j.ifacol.2015.10.310

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents