{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:12Z","timestamp":1750220592520,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T00:00:00Z","timestamp":1620604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Faculty Research Award"],"award-info":[{"award-number":["Faculty Research Award"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Yahoo","award":["FREP Award"],"award-info":[{"award-number":["FREP Award"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["617951"],"award-info":[{"award-number":["617951"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF","award":["CCF-1101429, CCF-1320854, CCF-1527084 and CCF-1535972"],"award-info":[{"award-number":["CCF-1101429, CCF-1320854, CCF-1527084 and CCF-1535972"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            This article studies the equilibrium states that can be reached in a network design game via\n            <jats:italic>natural<\/jats:italic>\n            game dynamics. First, we show that an arbitrarily interleaved sequence of arrivals and departures of players can lead to a polynomially inefficient solution at equilibrium. This implies that the central controller must have some control over the timing of agent arrivals and departures to ensure efficiency of the system at equilibrium. Indeed, we give a complementary result showing that if the central controller is allowed to restore equilibrium after every set of arrivals\/departures via\n            <jats:italic>improving moves<\/jats:italic>\n            , then the eventual equilibrium states reached have exponentially better efficiency.\n          <\/jats:p>","DOI":"10.1145\/3434425","type":"journal-article","created":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T22:20:53Z","timestamp":1620685253000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Timing Matters"],"prefix":"10.1145","volume":"9","author":[{"given":"Shuchi","family":"Chawla","sequence":"first","affiliation":[{"name":"Computer Sciences Department, University of Wisconsin - Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"Computer Science Department, Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohit","family":"Singh","sequence":"additional","affiliation":[{"name":"H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seeun William","family":"Umboh","sequence":"additional","affiliation":[{"name":"School of Computer Science, The University of Sydney, NSW Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,5,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/090748986"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/070701376"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198522"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680096"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.021"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/110821317"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198524"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 29th ACM Symposium on Theory of Computing. ACM, 344--353","author":"Berman Piotr","year":"1997","unstructured":"Piotr Berman and Chris Coulston . 1997 . On-line algorithms for Steiner tree problems . In Proceedings of the 29th ACM Symposium on Theory of Computing. ACM, 344--353 . Piotr Berman and Chris Coulston. 1997. On-line algorithms for Steiner tree problems. In Proceedings of the 29th ACM Symposium on Theory of Computing. ACM, 344--353."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219265911002824"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.74"},{"volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201908)","author":"Charikar Moses","key":"e_1_2_1_11_1","unstructured":"Moses Charikar , Howard J. Karloff , Claire Mathieu , Joseph Naor , and Michael E. Saks . 2008. Online multicast with egalitarian cost sharing . In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201908) . 70--76. Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, and Michael E. Saks. 2008. Online multicast with egalitarian cost sharing. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201908). 70--76."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2007.070813"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9128-8"},{"key":"e_1_2_1_14_1","volume-title":"7th International Workshop, WAOA 2009","author":"Christodoulou George","year":"2009","unstructured":"George Christodoulou , Christine Chung , Katrina Ligett , Evangelia Pyrga , and Rob van Stee . 2009 . On the price of stability for undirected network design. In Approximation and Online Algorithms , 7th International Workshop, WAOA 2009 , Copenhagen, Denmark , September 10-11, 2009. Revised Papers. Springer, 86--97. George Christodoulou, Christine Chung, Katrina Ligett, Evangelia Pyrga, and Rob van Stee. 2009. On the price of stability for undirected network design. In Approximation and Online Algorithms, 7th International Workshop, WAOA 2009, Copenhagen, Denmark, September 10-11, 2009. Revised Papers. Springer, 86--97."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.40"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007445"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.09.035"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_53"},{"key":"e_1_2_1_19_1","volume-title":"WINE 2016, Montreal, Canada, December 11-14, 2016, Proceedings. Springer, 354--368","author":"Freeman Rupert","year":"2016","unstructured":"Rupert Freeman , Samuel Haney , and Debmalya Panigrahi . 2016 . On the price of stability of undirected multicast games. In Web and Internet Economics - 12th International Conference , WINE 2016, Montreal, Canada, December 11-14, 2016, Proceedings. Springer, 354--368 . Rupert Freeman, Samuel Haney, and Debmalya Panigrahi. 2016. On the price of stability of undirected multicast games. In Web and Internet Economics - 12th International Conference, WINE 2016, Montreal, Canada, December 11-14, 2016, Proceedings. Springer, 354--368."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.38"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.66"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_48"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0543"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404033"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.02.031"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the ACM Conference on Economics and Computation (EC\u201913)","author":"Lee Euiwoong","year":"2013","unstructured":"Euiwoong Lee and Katrina Ligett . 2013 . Improved bounds on the price of stability in network cost sharing games . In Proceedings of the ACM Conference on Economics and Computation (EC\u201913) . 607--620. Euiwoong Lee and Katrina Ligett. 2013. Improved bounds on the price of stability in network cost sharing games. In Proceedings of the ACM Conference on Economics and Computation (EC\u201913). 607--620."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.04.015"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0027"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.65"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0391-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0592"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"volume-title":"Internet and Network Economics","author":"Syrgkanis Vasili","key":"e_1_2_1_34_1","unstructured":"Vasili Syrgkanis . 2010. The complexity of equilibria in cost sharing games . In Internet and Network Economics . Springer Berlin , 366--377. Vasili Syrgkanis. 2010. The complexity of equilibria in cost sharing games. In Internet and Network Economics. Springer Berlin, 366--377."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0729"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.91"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434425","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434425","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434425","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:48Z","timestamp":1750195908000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434425"}},"subtitle":["Online Dynamics in Broadcast Games"],"short-title":[],"issued":{"date-parts":[[2021,5,10]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3434425"],"URL":"https:\/\/doi.org\/10.1145\/3434425","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2021,5,10]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}