{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:19Z","timestamp":1750220059609,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,3,25]],"date-time":"2023-03-25T00:00:00Z","timestamp":1679702400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["IIS-1703846, IIS-0911036"],"award-info":[{"award-number":["IIS-1703846, IIS-0911036"]}]},{"name":"ARO","award":["W911NF-17-1-0592"],"award-info":[{"award-number":["W911NF-17-1-0592"]}]},{"DOI":"10.13039\/100014036","name":"MURI","doi-asserted-by":"crossref","award":["W911NF-19-1-0217"],"award-info":[{"award-number":["W911NF-19-1-0217"]}],"id":[{"id":"10.13039\/100014036","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Open Philanthropy"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>\n            Abraham, Dolev, Geffner, and Halpern [\n            <jats:xref ref-type=\"bibr\">1<\/jats:xref>\n            ] proved that, in asynchronous systems, a\n            <jats:italic>(k, t)-robust equilibrium<\/jats:italic>\n            for\n            <jats:italic>n<\/jats:italic>\n            players and a trusted mediator can be implemented without the mediator as long as\n            <jats:italic>n<\/jats:italic>\n            &gt; 4(\n            <jats:italic>k+t<\/jats:italic>\n            ), where an equilibrium is (\n            <jats:italic>k, t<\/jats:italic>\n            )-robust if, roughly speaking, no coalition of\n            <jats:italic>t<\/jats:italic>\n            players can decrease the payoff of any of the other players, and no coalition of\n            <jats:italic>k<\/jats:italic>\n            players can increase their payoff by deviating. We prove that this bound is tight, in the sense that if\n            <jats:italic>n<\/jats:italic>\n            \u2264 4(\n            <jats:italic>k+t<\/jats:italic>\n            ) there exist (\n            <jats:italic>k, t<\/jats:italic>\n            )-robust equilibria with a mediator that cannot be implemented by the players alone. Even though implementing (\n            <jats:italic>k, t<\/jats:italic>\n            )-robust mediators seems closely related to implementing asynchronous multiparty (\n            <jats:italic>k+t<\/jats:italic>\n            )-secure computation [\n            <jats:xref ref-type=\"bibr\">6<\/jats:xref>\n            ], to the best of our knowledge there is no known straightforward reduction from one problem to another. Nevertheless, we show that there is a non-trivial reduction from a slightly weaker notion of (\n            <jats:italic>k+t<\/jats:italic>\n            )-secure computation, which we call\n            <jats:italic>\n              (\n              <jats:italic>k+t<\/jats:italic>\n              )-strict secure computation\n            <\/jats:italic>\n            , to implementing (\n            <jats:italic>k, t<\/jats:italic>\n            )-robust mediators. We prove the desired lower bound by showing that there are functions on\n            <jats:italic>n<\/jats:italic>\n            variables that cannot be (\n            <jats:italic>k+t<\/jats:italic>\n            )-strictly securely computed if\n            <jats:italic>n<\/jats:italic>\n            \u2264 4(\n            <jats:italic>k+t<\/jats:italic>\n            ). This also provides a simple alternative proof for the well-known lower bound of 4\n            <jats:italic>t<\/jats:italic>\n            +1 on asynchronous secure computation in the presence of up to\n            <jats:italic>t<\/jats:italic>\n            malicious agents [\n            <jats:xref ref-type=\"bibr\">4<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">8<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">10<\/jats:xref>\n            ].\n          <\/jats:p>","DOI":"10.1145\/3578579","type":"journal-article","created":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T12:42:17Z","timestamp":1672663337000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Lower Bounds on Implementing Mediators in Asynchronous Systems with Rational and Malicious Agents"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6900-2109","authenticated-orcid":false,"given":"Ivan","family":"Geffner","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, NY"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9229-1663","authenticated-orcid":false,"given":"Joseph Y.","family":"Halpern","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}]}],"member":"320","published-online":{"date-parts":[[2023,3,25]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331623"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146393"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/1802614.1802638"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405722"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/2774187.2774193"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167109"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198088"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/800222.806743"},{"key":"e_1_3_2_11_2","volume-title":"Studies in Secure Multiparty Computation and Applications","author":"Canetti R.","year":"1996","unstructured":"R. Canetti. 1996. Studies in Secure Multiparty Computation and Applications. Ph.D. Dissertation. Technion. citeseer.nj.nec.com\/canetti95studies.html."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.2307\/2938319"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322398"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3578579","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3578579","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:38Z","timestamp":1750183718000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3578579"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,25]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3578579"],"URL":"https:\/\/doi.org\/10.1145\/3578579","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2023,3,25]]},"assertion":[{"value":"2021-07-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}