{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:09Z","timestamp":1750306089699,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,8,9]],"date-time":"2017-08-09T00:00:00Z","timestamp":1502236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1101690"],"award-info":[{"award-number":["CCF-1101690"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["420\/12"],"award-info":[{"award-number":["420\/12"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Israeli Center for Research Excellence in Algorithms"},{"DOI":"10.13039\/100007297","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007297","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":[[2017,8,31]]},"abstract":"<jats:p>We use ideas from distributed computing and game theory to study dynamic and decentralized environments in which computational nodes, or decision makers, interact strategically and with limited information. In such environments, which arise in many real-world settings, the participants act as both economic and computational entities. We exhibit a general non-convergence result for a broad class of dynamics in asynchronous settings. We consider implications of our result across a wide variety of interesting and timely applications: game dynamics, circuit design, social networks, Internet routing, and congestion control. We also study the computational and communication complexity of testing the convergence of asynchronous dynamics. Our work opens a new avenue for research at the intersection of distributed computing and game theory.<\/jats:p>","DOI":"10.1145\/3107182","type":"journal-article","created":{"date-parts":[[2017,8,10]],"date-time":"2017-08-10T12:12:29Z","timestamp":1502367149000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Dynamics at the Boundary of Game Theory and Distributed Computing"],"prefix":"10.1145","volume":"5","author":[{"given":"Aaron D.","family":"Jaggard","sequence":"first","affiliation":[{"name":"U.S. Naval Research Laboratory, DC, USA"}]},{"given":"Neil","family":"Lutz","sequence":"additional","affiliation":[{"name":"Rutgers University"}]},{"given":"Michael","family":"Schapira","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Israel"}]},{"given":"Rebecca N.","family":"Wright","sequence":"additional","affiliation":[{"name":"Rutgers University, NJ, USA"}]}],"member":"320","published-online":{"date-parts":[[2017,8,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146393"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the ICML Workshop on Markets, Mechanisms and Multi-Agent Models.","author":"Balcan Maria-Florina","year":"2012","unstructured":"Maria-Florina Balcan , Florin Constantin , and Ruta Mehta . 2012 . The weighted majority algorithm does not converge in nearly zero-sum games . In Proceedings of the ICML Workshop on Markets, Mechanisms and Multi-Agent Models. Maria-Florina Balcan, Florin Constantin, and Ruta Mehta. 2012. The weighted majority algorithm does not converge in nearly zero-sum games. In Proceedings of the ICML Workshop on Markets, Mechanisms and Multi-Agent Models."},{"volume-title":"Randomized agreement protocols","author":"Ben-Or Michael","key":"e_1_2_1_3_1","unstructured":"Michael Ben-Or . 1986. Randomized agreement protocols . In Fault-Tolerant Distributed Computing, Barbara Simons and Alfred Spector (Eds.). Springer , New York, NY , 72--83. DOI:https:\/\/dx.doi.org\/10.1007\/bfb0042326 10.1007\/bfb0042326 Michael Ben-Or. 1986. Randomized agreement protocols. In Fault-Tolerant Distributed Computing, Barbara Simons and Alfred Spector (Eds.). Springer, New York, NY, 72--83. DOI:https:\/\/dx.doi.org\/10.1007\/bfb0042326"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167119"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16170-4_11"},{"key":"e_1_2_1_7_1","volume-title":"Nowick","author":"Davis Al","year":"1997","unstructured":"Al Davis and Steven M . Nowick . 1997 . An Introduction to Asynchronous Circuit Design. Technical Report. The Encyclopedia of Computer Science and Technology . Al Davis and Steven M. Nowick. 1997. An Introduction to Asynchronous Circuit Design. Technical Report. The Encyclopedia of Computer Science and Technology."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7533"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Shlomi Dolev. 2000. Self-Stabilization. MIT Press Cambridge MA.  Shlomi Dolev. 2000. Self-Stabilization. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/6156.001.0001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482609"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01119684"},{"volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Fabrikant Alex","key":"e_1_2_1_13_1","unstructured":"Alex Fabrikant and Christos H. Papadimitriou . 2008. The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908) . SIAM, Philadelphia, PA, 844--853. Alex Fabrikant and Christos H. Papadimitriou. 2008. The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). SIAM, Philadelphia, PA, 844--853."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-003-0091-y"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811039.1811051"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.993304"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0899-8256(02)00529-8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79161"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2005.00625.x"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1257\/000282803322655581"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.09.007"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250923"},{"volume-title":"Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS\u201911)","author":"Jaggard Aaron D.","key":"e_1_2_1_25_1","unstructured":"Aaron D. Jaggard , Michael Schapira , and Rebecca N. Wright . 2011. Distributed computing with adaptive heuristics . In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS\u201911) . Tsinghua University Press, Beijing, 417--443. Aaron D. Jaggard, Michael Schapira, and Rebecca N. Wright. 2011. Distributed computing with adaptive heuristics. In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS\u201911). Tsinghua University Press, Beijing, 417--443."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS\u201911)","author":"Kleinberg Robert D.","year":"2011","unstructured":"Robert D. Kleinberg , Katrina Ligett , Georgios Piliouras , and \u00c9va Tardos . 2011 . Beyond the Nash equilibrium barrier . In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS\u201911) . Tsinghua University Press, Beijing, 125--140. Robert D. Kleinberg, Katrina Ligett, Georgios Piliouras, and \u00c9va Tardos. 2011. Beyond the Nash equilibrium barrier. In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS\u201911). Tsinghua University Press, Beijing, 125--140."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2009.04.003"},{"volume-title":"Proceedings of the 4th USENIX Conference on Networked Systems Design & Implementation (NSDI\u201907)","author":"Kushman Nate","key":"e_1_2_1_28_1","unstructured":"Nate Kushman , Srikanth Kandula , Dina Katabi , and Bruce M. Maggs . 2007. R-BGP: Staying connected in a connected world . In Proceedings of the 4th USENIX Conference on Networked Systems Design & Implementation (NSDI\u201907) . USENIX, Berkeley, CA. Nate Kushman, Srikanth Kandula, Dina Katabi, and Bruce M. Maggs. 2007. R-BGP: Staying connected in a connected world. In Proceedings of the 4th USENIX Conference on Networked Systems Design & Implementation (NSDI\u201907). USENIX, Berkeley, CA."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2307\/2171745"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/72981.72982"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2012.03.006"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-937X.00121"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"volume-title":"Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. ACM","author":"Christos","key":"e_1_2_1_37_1","unstructured":"Christos H. Papadimitriou and Georgios Piliouras. 2016. From Nash equilibria to chain recurrent sets: Solution concepts and topology . In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. ACM , New York, NY, 227--235. DOI:https:\/\/dx.doi.org\/10.1145\/2840728.2840757 10.1145\/2840728.2840757 Christos H. Papadimitriou and Georgios Piliouras. 2016. From Nash equilibria to chain recurrent sets: Solution concepts and topology. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. ACM, New York, NY, 227--235. DOI:https:\/\/dx.doi.org\/10.1145\/2840728.2840757"},{"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.1137\/S0097539796307698"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2009.5061961"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555349.1555375"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001820300161"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0323"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3107182","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3107182","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3107182","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:21Z","timestamp":1750217421000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3107182"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,9]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3107182"],"URL":"https:\/\/doi.org\/10.1145\/3107182","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2017,8,9]]},"assertion":[{"value":"2016-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}