[{"citation":{"mla":"Hirvonen, Juho, et al. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” <i>27th International Conference on Principles of Distributed Systems</i>, vol. 286, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">10.4230/LIPIcs.OPODIS.2023.11</a>.","ieee":"J. Hirvonen, L. Schmid, K. Chatterjee, and S. Schmid, “On the convergence time in graphical games: A locality-sensitive approach,” in <i>27th International Conference on Principles of Distributed Systems</i>, Tokyo, Japan, 2024, vol. 286.","ista":"Hirvonen J, Schmid L, Chatterjee K, Schmid S. 2024. On the convergence time in graphical games: A locality-sensitive approach. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 11.","chicago":"Hirvonen, Juho, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” In <i>27th International Conference on Principles of Distributed Systems</i>, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.11</a>.","apa":"Hirvonen, J., Schmid, L., Chatterjee, K., &#38; Schmid, S. (2024). On the convergence time in graphical games: A locality-sensitive approach. In <i>27th International Conference on Principles of Distributed Systems</i> (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.11</a>","ama":"Hirvonen J, Schmid L, Chatterjee K, Schmid S. On the convergence time in graphical games: A locality-sensitive approach. In: <i>27th International Conference on Principles of Distributed Systems</i>. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">10.4230/LIPIcs.OPODIS.2023.11</a>","short":"J. Hirvonen, L. Schmid, K. Chatterjee, S. Schmid, in:, 27th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"ec_funded":1,"title":"On the convergence time in graphical games: A locality-sensitive approach","conference":{"end_date":"2023-12-08","start_date":"2023-12-06","name":"OPODIS: Conference on Principles of Distributed Systems","location":"Tokyo, Japan"},"day":"18","type":"conference","author":[{"last_name":"Hirvonen","first_name":"Juho","full_name":"Hirvonen, Juho"},{"first_name":"Laura","full_name":"Schmid, Laura","last_name":"Schmid","orcid":"0000-0002-6978-7329","id":"38B437DE-F248-11E8-B48F-1D18A9856A87"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"}],"alternative_title":["LIPIcs"],"project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"}],"acknowledgement":"This work was partially funded by the Academy of Finland, grant 314888, the European Research Council CoG 863818 (ForM-SMArt), and the Austrian Science Fund (FWF) project I 4800-N (ADVISE). LS was supported by the Stochastic Analysis and Application Research Center (SAARC) under National Research Foundation of Korea grant NRF-2019R1A5A1028324.","language":[{"iso":"eng"}],"ddc":["000"],"doi":"10.4230/LIPIcs.OPODIS.2023.11","month":"01","date_created":"2024-02-18T23:01:01Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication":"27th International Conference on Principles of Distributed Systems","quality_controlled":"1","department":[{"_id":"KrCh"}],"intvolume":"       286","status":"public","has_accepted_license":"1","oa_version":"Published Version","year":"2024","external_id":{"arxiv":["2102.13457"]},"scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-07-14T09:10:03Z","publication_identifier":{"isbn":["9783959773089"],"issn":["18688969"]},"arxiv":1,"article_processing_charge":"No","article_number":"11","file":[{"file_name":"2024_LIPICs_Hirvonen.pdf","creator":"dernst","file_size":867363,"checksum":"4fc7eea6e4ba140b904781fc7df868ec","date_updated":"2024-02-26T09:04:58Z","access_level":"open_access","content_type":"application/pdf","file_id":"15028","relation":"main_file","date_created":"2024-02-26T09:04:58Z","success":1}],"abstract":[{"text":"Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though an agent’s payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of \"natural\" local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with constant-round local algorithms. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intuitive notion of \"time-constrained\" inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood.","lang":"eng"}],"_id":"15006","date_published":"2024-01-18T00:00:00Z","publication_status":"published","oa":1,"file_date_updated":"2024-02-26T09:04:58Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"volume":286},{"day":"18","alternative_title":["LIPIcs"],"author":[{"last_name":"Alpos","first_name":"Orestis","full_name":"Alpos, Orestis"},{"first_name":"Ignacio","full_name":"Amores-Sesar, Ignacio","last_name":"Amores-Sesar"},{"full_name":"Cachin, Christian","first_name":"Christian","last_name":"Cachin"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X"}],"type":"conference","citation":{"ieee":"O. Alpos, I. Amores-Sesar, C. Cachin, and M. X. Yeo, “Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks,” in <i>27th International Conference on Principles of Distributed Systems</i>, Tokyo, Japan, 2024, vol. 286.","ista":"Alpos O, Amores-Sesar I, Cachin C, Yeo MX. 2024. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 12.","chicago":"Alpos, Orestis, Ignacio Amores-Sesar, Christian Cachin, and Michelle X Yeo. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks.” In <i>27th International Conference on Principles of Distributed Systems</i>, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.12</a>.","mla":"Alpos, Orestis, et al. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks.” <i>27th International Conference on Principles of Distributed Systems</i>, vol. 286, 12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">10.4230/LIPIcs.OPODIS.2023.12</a>.","short":"O. Alpos, I. Amores-Sesar, C. Cachin, M.X. Yeo, in:, 27th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","apa":"Alpos, O., Amores-Sesar, I., Cachin, C., &#38; Yeo, M. X. (2024). Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. In <i>27th International Conference on Principles of Distributed Systems</i> (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.12</a>","ama":"Alpos O, Amores-Sesar I, Cachin C, Yeo MX. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. In: <i>27th International Conference on Principles of Distributed Systems</i>. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">10.4230/LIPIcs.OPODIS.2023.12</a>"},"conference":{"name":"OPODIS: Conference on Principles of Distributed Systems","end_date":"2023-12-08","start_date":"2023-12-06","location":"Tokyo, Japan"},"title":"Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks","language":[{"iso":"eng"}],"ddc":["000"],"doi":"10.4230/LIPIcs.OPODIS.2023.12","acknowledgement":"We would like to thank Krzysztof Pietrzak and Jovana Mićić for useful discussions. This work has been funded by the Swiss National Science Foundation (SNSF) under grant agreement Nr. 200021_188443 (Advanced Consensus Protocols).\r\n","month":"01","date_created":"2024-02-18T23:01:02Z","department":[{"_id":"KrPi"}],"quality_controlled":"1","publication":"27th International Conference on Principles of Distributed Systems","intvolume":"       286","status":"public","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2024","oa_version":"Published Version","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2024-02-26T10:18:18Z","external_id":{"arxiv":["2307.02954"]},"scopus_import":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773089"]},"article_number":"12","file":[{"date_updated":"2024-02-26T10:16:57Z","access_level":"open_access","checksum":"2993e810a45e8c8056106834b07aea92","file_name":"2024_LIPICs_Alpos.pdf","file_size":1505994,"creator":"dernst","success":1,"date_created":"2024-02-26T10:16:57Z","content_type":"application/pdf","relation":"main_file","file_id":"15031"}],"_id":"15007","date_published":"2024-01-18T00:00:00Z","abstract":[{"lang":"eng","text":"Traditional blockchains grant the miner of a block full control not only over which transactions but also their order. This constitutes a major flaw discovered with the introduction of decentralized finance and allows miners to perform MEV attacks. In this paper, we address the issue of sandwich attacks by providing a construction that takes as input a blockchain protocol and outputs a new blockchain protocol with the same security but in which sandwich attacks are not profitable. Furthermore, our protocol is fully decentralized with no trusted third parties or heavy cryptography primitives and carries a linear increase in latency and minimum computation overhead."}],"arxiv":1,"article_processing_charge":"No","file_date_updated":"2024-02-26T10:16:57Z","volume":286,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"publication_status":"published","oa":1}]