---
_id: '15006'
abstract:
- lang: eng
  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.
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.
alternative_title:
- LIPIcs
article_number: '11'
article_processing_charge: No
arxiv: 1
author:
- first_name: Juho
  full_name: Hirvonen, Juho
  last_name: Hirvonen
- first_name: Laura
  full_name: Schmid, Laura
  id: 38B437DE-F248-11E8-B48F-1D18A9856A87
  last_name: Schmid
  orcid: 0000-0002-6978-7329
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
citation:
  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>'
  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>'
  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>.'
  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.'
  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>.'
  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.
conference:
  end_date: 2023-12-08
  location: Tokyo, Japan
  name: 'OPODIS: Conference on Principles of Distributed Systems'
  start_date: 2023-12-06
date_created: 2024-02-18T23:01:01Z
date_published: 2024-01-18T00:00:00Z
date_updated: 2025-07-14T09:10:03Z
day: '18'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.OPODIS.2023.11
ec_funded: 1
external_id:
  arxiv:
  - '2102.13457'
file:
- access_level: open_access
  checksum: 4fc7eea6e4ba140b904781fc7df868ec
  content_type: application/pdf
  creator: dernst
  date_created: 2024-02-26T09:04:58Z
  date_updated: 2024-02-26T09:04:58Z
  file_id: '15028'
  file_name: 2024_LIPICs_Hirvonen.pdf
  file_size: 867363
  relation: main_file
  success: 1
file_date_updated: 2024-02-26T09:04:58Z
has_accepted_license: '1'
intvolume: '       286'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 27th International Conference on Principles of Distributed Systems
publication_identifier:
  isbn:
  - '9783959773089'
  issn:
  - '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'On the convergence time in graphical games: A locality-sensitive approach'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 286
year: '2024'
...
---
_id: '15007'
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.
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"
alternative_title:
- LIPIcs
article_number: '12'
article_processing_charge: No
arxiv: 1
author:
- first_name: Orestis
  full_name: Alpos, Orestis
  last_name: Alpos
- first_name: Ignacio
  full_name: Amores-Sesar, Ignacio
  last_name: Amores-Sesar
- first_name: Christian
  full_name: Cachin, Christian
  last_name: Cachin
- first_name: Michelle X
  full_name: Yeo, Michelle X
  id: 2D82B818-F248-11E8-B48F-1D18A9856A87
  last_name: Yeo
citation:
  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>'
  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>'
  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>.'
  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.'
  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.
conference:
  end_date: 2023-12-08
  location: Tokyo, Japan
  name: 'OPODIS: Conference on Principles of Distributed Systems'
  start_date: 2023-12-06
date_created: 2024-02-18T23:01:02Z
date_published: 2024-01-18T00:00:00Z
date_updated: 2024-02-26T10:18:18Z
day: '18'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.OPODIS.2023.12
external_id:
  arxiv:
  - '2307.02954'
file:
- access_level: open_access
  checksum: 2993e810a45e8c8056106834b07aea92
  content_type: application/pdf
  creator: dernst
  date_created: 2024-02-26T10:16:57Z
  date_updated: 2024-02-26T10:16:57Z
  file_id: '15031'
  file_name: 2024_LIPICs_Alpos.pdf
  file_size: 1505994
  relation: main_file
  success: 1
file_date_updated: 2024-02-26T10:16:57Z
has_accepted_license: '1'
intvolume: '       286'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
publication: 27th International Conference on Principles of Distributed Systems
publication_identifier:
  isbn:
  - '9783959773089'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Eating sandwiches: Modular and lightweight elimination of transaction reordering
  attacks'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 286
year: '2024'
...