{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T05:30:52Z","timestamp":1770528652248,"version":"3.49.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T00:00:00Z","timestamp":1414454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1101283 and CCF-0953192"],"award-info":[{"award-number":["CCF-1101283 and CCF-0953192"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-09-1-0751"],"award-info":[{"award-number":["N00014-09-1-0751"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-09-1-0538 and FA9550-09-1-0420"],"award-info":[{"award-number":["FA9550-09-1-0538 and FA9550-09-1-0420"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2014,10,28]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>\n            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\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) times the optimal social cost, and we prove that the system quickly converges to an equilibrium with social cost of this same order.\n          <\/jats:p>","DOI":"10.1145\/2597890","type":"journal-article","created":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T12:40:29Z","timestamp":1414500029000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Near-Optimality in Covering Games by Exposing Global Information"],"prefix":"10.1145","volume":"2","author":[{"given":"Maria-Florina","family":"Balcan","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sara","family":"Krehbiel","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georgios","family":"Piliouras","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinwoo","family":"Shin","sequence":"additional","affiliation":[{"name":"Korea Advanced Institute of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,10,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a004"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 51st IEEE Annual Conference on Decision and Control (CDC). 2690--2695","author":"Balcan M.","unstructured":"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 . 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."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM","author":"Balcan M.-F.","unstructured":"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. 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."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/110821317"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9197-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1070.0435"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_17"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.02.005"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_2_1_10_1","volume-title":"Lecture Notes in Computer Science","volume":"6516","author":"Demaine E. D.","unstructured":"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. 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."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.3.751"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2004.08.004"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13284-1_2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872088"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 3rd International Conference on Internet and Network Economics (WINE'07)","author":"Fang Q.","unstructured":"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. 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."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 9th International Conference on the Evolution of Language (Evolang IX). 110--118","author":"Fox M.","unstructured":"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 . 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."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_49"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9367-3"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1361192.1361201"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 6th International Conference on Internet and Network Economics (WINE'10)","author":"Immorlica N.","unstructured":"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. 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."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the IEEE International Workshop on Network Science for Communication Networks (NETSCICOM). 3267--3272","author":"Jin Y.","unstructured":"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 . 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."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_91"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536487"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0129-5"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the Innovations in Computer Science (ICS). 125--140","author":"Kleinberg R. D.","year":"2011","unstructured":"R. D. Kleinberg , K. Ligett , G. Piliouras , and \u00c9. Tardos. 2011 b. Beyond the Nash equilibrium barrier . In Proceedings of the Innovations in Computer Science (ICS). 125--140 . R. D. Kleinberg, K. Ligett, G. Piliouras, and \u00c9. Tardos. 2011b. Beyond the Nash equilibrium barrier. In Proceedings of the Innovations in Computer Science (ICS). 125--140."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). Springer-Verlag, 404--413","author":"Koutsoupias E.","unstructured":"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 . 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."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_18"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.09.024"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1978721.1978727"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MOBIQ.2007.4451041"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_33_1","volume-title":"Bertrand. In Proceedings of the 3rd International Conference on Algorithmic Game Theory (SAGT'10)","author":"Nadav U.","unstructured":"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. 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."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"N. Nisan T. Roughgarden \u00c9. Tardos and V. V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press New York.   N. Nisan T. Roughgarden \u00c9. Tardos and V. V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press New York.","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 861--873","author":"Piliouras G.","unstructured":"G. Piliouras and J. S. Shamma . 2014. Optimization despite chaos: Convex relaxations to complex limit sets via Poincar\u00e9 recurrence . In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 861--873 . G. Piliouras and J. S. Shamma. 2014. Optimization despite chaos: Convex relaxations to complex limit sets via Poincar\u00e9 recurrence. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 861--873."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35311-6_14"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11036-006-5187-8"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 14th International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS). 51--54","author":"Schmid S.","unstructured":"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 . 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."},{"key":"e_1_2_1_41_1","volume-title":"Cooperative Control of Distributed Multiagent Systems","author":"J.","unstructured":"J. Shamma (Ed). 2008. Cooperative Control of Distributed Multiagent Systems . Wiley . J. Shamma (Ed). 2008. Cooperative Control of Distributed Multiagent Systems. Wiley."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250925"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.3390\/s90402446"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1836001.1836013"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2597890","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2597890","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:50Z","timestamp":1750230050000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2597890"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,28]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,10,28]]}},"alternative-id":["10.1145\/2597890"],"URL":"https:\/\/doi.org\/10.1145\/2597890","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,28]]},"assertion":[{"value":"2012-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}