{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:57:01Z","timestamp":1780073821326,"version":"3.54.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,2,14]],"date-time":"2019-02-14T00:00:00Z","timestamp":1550102400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"HUJI Cyber Security Research Center"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["IIS-0911036"],"award-info":[{"award-number":["IIS-0911036"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Open Philanthropy Foundation"},{"name":"ARO","award":["W911NF-09-1-0281"],"award-info":[{"award-number":["W911NF-09-1-0281"]}]},{"DOI":"10.13039\/100000181","name":"AFOSR","doi-asserted-by":"crossref","award":["FA9550-09-1-0266"],"award-info":[{"award-number":["FA9550-09-1-0266"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2019,2,28]]},"abstract":"<jats:p>\n            We do a game-theoretic analysis of leader election, under the assumption that each agent prefers to have some leader than no leader at all. We show that it is possible to obtain a\n            <jats:italic>fair<\/jats:italic>\n            Nash equilibrium, where each agent has an equal probability of being elected leader, in a completely connected network, in a bidirectional ring, and a unidirectional ring, in the synchronous setting. In the asynchronous setting, Nash equilibrium is not quite the right solution concept. Rather, we must consider\n            <jats:italic>ex post<\/jats:italic>\n            Nash equilibrium; this means that we have a Nash equilibrium no matter what a scheduling adversary does. We show that ex post Nash equilibrium is attainable in the asynchronous setting in all the networks we consider, using a protocol with bounded running time. However, in the asynchronous setting, we require that\n            <jats:italic>n<\/jats:italic>\n            &gt; 2. We show that we can get a fair ex post\n            <jats:italic>\u03f5-Nash<\/jats:italic>\n            equilibrium if\n            <jats:italic>n<\/jats:italic>\n            =2 in the asynchronous setting under some cryptographic assumptions (specifically, the existence of a one-way functions), using a\n            <jats:italic>commitment protocol<\/jats:italic>\n            . We then generalize these results to a setting where we can have deviations by a coalition of size\n            <jats:italic>k<\/jats:italic>\n            . In this case, we can get what we call a fair\n            <jats:italic>k<\/jats:italic>\n            -resilient equilibrium in a completely connected network if\n            <jats:italic>n<\/jats:italic>\n            &gt; 2\n            <jats:italic>k<\/jats:italic>\n            ; under the same cryptographic assumptions, we can a get a\n            <jats:italic>k<\/jats:italic>\n            -resilient equilibrium in a completely connected network, unidirectional ring, or bidirectional ring if\n            <jats:italic>n<\/jats:italic>\n            &gt;\n            <jats:italic>k<\/jats:italic>\n            . Finally, we show that under minimal assumptions, not only do our protocols give a Nash equilibrium, they also give a\n            <jats:italic>sequential<\/jats:italic>\n            equilibrium, so players even play optimally off the equilibrium path.\n          <\/jats:p>","DOI":"10.1145\/3303712","type":"journal-article","created":{"date-parts":[[2019,2,19]],"date-time":"2019-02-19T20:54:15Z","timestamp":1550609655000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Distributed Protocols for Leader Election"],"prefix":"10.1145","volume":"7","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[{"name":"VMWARE Research, Herliya, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Danny","family":"Dolev","sequence":"additional","affiliation":[{"name":"The Hebrew University of Jerusalem, Jerusalem, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph Y.","family":"Halpern","sequence":"additional","affiliation":[{"name":"Cornell University, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,2,14]]},"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 5th Theory of Cryptography Conference. 302--319","author":"Abraham I."},{"key":"e_1_2_1_3_1","unstructured":"I. Abraham D. Dolev and J. Y. Halpern. 2011. On the Power of Cheap Talk. Unpublished manuscript.  I. Abraham D. Dolev and J. Y. Halpern. 2011. On the Power of Cheap Talk. Unpublished manuscript."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611481"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095810.1095816"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems. 1549--1552","author":"Altman A."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132544"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2774187.2774193"},{"key":"e_1_2_1_10_1","unstructured":"X. Bei W. Chen and J. Zhang. 2012. Distributed consensus resilient to both crash failures and strategic manipulations. Version 3. Available at http:\/\/arxiv.org\/abs\/1203.4324  X. Bei W. Chen and J. Zhang. 2012. Distributed consensus resilient to both crash failures and strategic manipulations. Version 3. Available at http:\/\/arxiv.org\/abs\/1203.4324"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.15"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"E. Ben-Porath. 2003. Cheap talk in games with incomplete information.Journal of Economic Theory 108 1 (2003) 45--71.  E. Ben-Porath. 2003. Cheap talk in games with incomplete information.Journal of Economic Theory 108 1 (2003) 45--71.","DOI":"10.1016\/S0022-0531(02)00011-X"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the IEEE Workshop on Communications Security (CRYPTO\u201981)","author":"Blum M.","year":"1981"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796307182"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/359104.359108"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993833"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 20th International Cryptology Conference (CRYPTO\u201900)","author":"Dodis Y."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90004-9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795291562"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90023-2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790187084"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2307\/2938319"},{"key":"e_1_2_1_24_1","unstructured":"E. Friedman and S. Shenker. 1998. Learning and implementation on the Internet. Working paper.  E. Friedman and S. Shenker. 1998. Learning and implementation on the Internet. Working paper."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11799-2_25"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"O. Goldreich. 2001. Foundations of Cryptography Vol. 1. Cambridge University Press Cambridge UK.   O. Goldreich. 2001. Foundations of Cryptography Vol. 1. Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9780511546891"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"O. Goldreich. 2005. Foundations of Cryptography: A Primer. Now Publishers Inc.   O. Goldreich. 2005. Foundations of Cryptography: A Primer. Now Publishers Inc.","DOI":"10.1561\/9781933019529"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11832072_16"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11799-2_24"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940733"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007447"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933088"},{"key":"e_1_2_1_33_1","unstructured":"Y. Heller. 2005. A minority-proof cheap-talk protocol. Unpublished manuscript.  Y. Heller. 2005. A minority-proof cheap-talk protocol. Unpublished manuscript."},{"key":"e_1_2_1_34_1","volume-title":"Games and Economic Behavior 71","author":"Izmalkov S.","year":"2011"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_27"},{"key":"e_1_2_1_36_1","volume-title":"Econometrica 50","author":"Kreps D. M.","year":"1982"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the IFIP Congress","volume":"7","author":"Le Lann G.","year":"1977"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011769"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699446"},{"key":"e_1_2_1_40_1","volume-title":"TCC 2008: Theory of Cryptography. Lecture Notes in Computer Science","volume":"4948","author":"Lin H."},{"key":"e_1_2_1_41_1","unstructured":"N. A. Lynch. 1997. Distributed Algorithms. Morgan Kaufmann San Francisco CA.  N. A. Lynch. 1997. Distributed Algorithms. Morgan Kaufmann San Francisco CA."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_11"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/846241.846249"},{"key":"e_1_2_1_44_1","volume-title":"Games and Economic Behavior 28","author":"Monderer D.","year":"1999"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146391"},{"key":"e_1_2_1_46_1","unstructured":"M. J. Osborne and A. Rubinstein. 1994. A Course in Game Theory. MIT Press Cambridge MA.  M. J. Osborne and A. Rubinstein. 1994. A Course in Game Theory. MIT Press Cambridge MA."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/060661880"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/69622.357194"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402020"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.009"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00357"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-003-0378-z"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25873-2_7"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212767"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3303712","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3303712","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3303712","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:39Z","timestamp":1750204419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3303712"}},"subtitle":["A Game-Theoretic Perspective"],"short-title":[],"issued":{"date-parts":[[2019,2,14]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2,28]]}},"alternative-id":["10.1145\/3303712"],"URL":"https:\/\/doi.org\/10.1145\/3303712","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,14]]},"assertion":[{"value":"2017-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}