---
_id: '17329'
abstract:
- lang: eng
text: 'We initiate the study of game dynamics in the population protocol model:
n agents each maintain a current local strategy and interact in pairs uniformly
at random. Upon each interaction, the agents play a two-person game and receive
a payoff from an underlying utility function, and they can subsequently update
their strategies according to a fixed local algorithm. In this setting, we ask
how the distribution over agent strategies evolves over a sequence of interactions,
and we introduce a new distributional equilibrium concept to quantify the quality
of such distributions. As an initial example, we study a class of repeated prisoner''s
dilemma games, and we consider a family of simple local update algorithms that
yield non-trivial dynamics over the distribution of agent strategies. We show
that these dynamics are related to a new class of high-dimensional Ehrenfest random
walks, and we derive exact characterizations of their stationary distributions,
bounds on their mixing times, and prove their convergence to approximate distributional
equilibria. Our results highlight trade-offs between the local state space of
each agent, and the convergence rate and approximation factor of the underlying
dynamics. Our approach opens the door towards the further characterization of
equilibrium computation for other classes of games and dynamics in the population
setting.'
acknowledgement: This work was supported in part by the ERC-2020-CoG 863818 (FoRM-SMArt)
grant. We thank James Aspnes and Thomas Sauerwald for several helpful discussions
on Ehrenfest random walks.
article_processing_charge: Yes (via OA deal)
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Mehrdad
full_name: Karrabi, Mehrdad
id: 67638922-f394-11eb-9cf6-f20423e08757
last_name: Karrabi
- first_name: John M
full_name: Lazarsfeld, John M
id: 17ce3656-183e-11ef-84c3-8932383e1b23
last_name: Lazarsfeld
citation:
ama: 'Alistarh D-A, Chatterjee K, Karrabi M, Lazarsfeld JM. Game dynamics and equilibrium
computation in the population protocol model. In: Proceedings of the 43rd Annual
ACM Symposium on Principles of Distributed Computing. Association for Computing
Machinery; 2024:40-49. doi:10.1145/3662158.3662768'
apa: 'Alistarh, D.-A., Chatterjee, K., Karrabi, M., & Lazarsfeld, J. M. (2024).
Game dynamics and equilibrium computation in the population protocol model. In
Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing
(pp. 40–49). Nantes, France: Association for Computing Machinery. https://doi.org/10.1145/3662158.3662768'
chicago: Alistarh, Dan-Adrian, Krishnendu Chatterjee, Mehrdad Karrabi, and John
M Lazarsfeld. “Game Dynamics and Equilibrium Computation in the Population Protocol
Model.” In Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed
Computing, 40–49. Association for Computing Machinery, 2024. https://doi.org/10.1145/3662158.3662768.
ieee: D.-A. Alistarh, K. Chatterjee, M. Karrabi, and J. M. Lazarsfeld, “Game dynamics
and equilibrium computation in the population protocol model,” in Proceedings
of the 43rd Annual ACM Symposium on Principles of Distributed Computing, Nantes,
France, 2024, pp. 40–49.
ista: 'Alistarh D-A, Chatterjee K, Karrabi M, Lazarsfeld JM. 2024. Game dynamics
and equilibrium computation in the population protocol model. Proceedings of the
43rd Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium
on Principles of Distributed Computing, 40–49.'
mla: Alistarh, Dan-Adrian, et al. “Game Dynamics and Equilibrium Computation in
the Population Protocol Model.” Proceedings of the 43rd Annual ACM Symposium
on Principles of Distributed Computing, Association for Computing Machinery,
2024, pp. 40–49, doi:10.1145/3662158.3662768.
short: D.-A. Alistarh, K. Chatterjee, M. Karrabi, J.M. Lazarsfeld, in:, Proceedings
of the 43rd Annual ACM Symposium on Principles of Distributed Computing, Association
for Computing Machinery, 2024, pp. 40–49.
conference:
end_date: 2024-06-21
location: Nantes, France
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2024-06-17
corr_author: '1'
date_created: 2024-07-28T22:01:10Z
date_published: 2024-06-17T00:00:00Z
date_updated: 2025-04-14T07:52:47Z
day: '17'
ddc:
- '000'
department:
- _id: DaAl
- _id: KrCh
doi: 10.1145/3662158.3662768
ec_funded: 1
file:
- access_level: open_access
checksum: 65a40437f83373fa79dd999d5287509e
content_type: application/pdf
creator: dernst
date_created: 2024-07-29T07:37:31Z
date_updated: 2024-07-29T07:37:31Z
file_id: '17335'
file_name: 2024_ACMPODC_Alistarh.pdf
file_size: 750908
relation: main_file
success: 1
file_date_updated: 2024-07-29T07:37:31Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: 40-49
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed
Computing
publication_identifier:
isbn:
- '9798400706684'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Game dynamics and equilibrium computation in the population protocol model
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
year: '2024'
...
---
_id: '17328'
abstract:
- lang: eng
text: "We study selfish mining attacks in longest-chain blockchains like Bitcoin,
but where the proof of work is replaced with efficient proof systems - like proofs
of stake or proofs of space - and consider the problem of computing an optimal
selfish mining attack which maximizes expected relative revenue of the adversary,
thus minimizing the chain quality. To this end, we propose a novel selfish mining
attack that aims to maximize this objective and formally model the attack as a
Markov decision process (MDP). We then present a formal analysis procedure which
computes an ϵ-tight lower bound on the optimal expected relative revenue in the
MDP and a strategy that achieves this ϵ-tight lower bound, where ϵ > 0 may be
any specified precision. Our analysis is fully automated and provides formal guarantees
on the correctness. We evaluate our selfish mining attack and observe that it
achieves superior expected relative revenue compared to two considered baselines.\r\nIn
concurrent work [Sarenche FC'24] does an automated analysis on selfish mining
in predictable longest-chain blockchains based on efficient proof systems. Predictable
means the randomness for the challenges is fixed for many blocks (as used e.g.,
in Ouroboros), while we consider unpredictable (Bitcoin-like) chains where the
challenge is derived from the previous block."
acknowledgement: "This work was supported in part by the ERC-2020-CoG 863818 (FoRM-SMArt)
grant and the MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms) grant.\r\n"
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Amirali
full_name: Ebrahimzadeh, Amirali
last_name: Ebrahimzadeh
- first_name: Mehrdad
full_name: Karrabi, Mehrdad
id: 67638922-f394-11eb-9cf6-f20423e08757
last_name: Karrabi
orcid: 0009-0007-5253-9170
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
- first_name: Dorde
full_name: Zikelic, Dorde
id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
last_name: Zikelic
orcid: 0000-0002-4681-1699
citation:
ama: 'Chatterjee K, Ebrahimzadeh A, Karrabi M, Pietrzak KZ, Yeo MX, Zikelic D. Fully
automated selfish mining analysis in efficient proof systems blockchains. In:
Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing.
Association for Computing Machinery; 2024:268-278. doi:10.1145/3662158.3662769'
apa: 'Chatterjee, K., Ebrahimzadeh, A., Karrabi, M., Pietrzak, K. Z., Yeo, M. X.,
& Zikelic, D. (2024). Fully automated selfish mining analysis in efficient
proof systems blockchains. In Proceedings of the 43rd Annual ACM Symposium
on Principles of Distributed Computing (pp. 268–278). Nantes, France: Association
for Computing Machinery. https://doi.org/10.1145/3662158.3662769'
chicago: Chatterjee, Krishnendu, Amirali Ebrahimzadeh, Mehrdad Karrabi, Krzysztof
Z Pietrzak, Michelle X Yeo, and Dorde Zikelic. “Fully Automated Selfish Mining
Analysis in Efficient Proof Systems Blockchains.” In Proceedings of the 43rd
Annual ACM Symposium on Principles of Distributed Computing, 268–78. Association
for Computing Machinery, 2024. https://doi.org/10.1145/3662158.3662769.
ieee: K. Chatterjee, A. Ebrahimzadeh, M. Karrabi, K. Z. Pietrzak, M. X. Yeo, and
D. Zikelic, “Fully automated selfish mining analysis in efficient proof systems
blockchains,” in Proceedings of the 43rd Annual ACM Symposium on Principles
of Distributed Computing, Nantes, France, 2024, pp. 268–278.
ista: 'Chatterjee K, Ebrahimzadeh A, Karrabi M, Pietrzak KZ, Yeo MX, Zikelic D.
2024. Fully automated selfish mining analysis in efficient proof systems blockchains.
Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing.
PODC: Symposium on Principles of Distributed Computing, 268–278.'
mla: Chatterjee, Krishnendu, et al. “Fully Automated Selfish Mining Analysis in
Efficient Proof Systems Blockchains.” Proceedings of the 43rd Annual ACM Symposium
on Principles of Distributed Computing, Association for Computing Machinery,
2024, pp. 268–78, doi:10.1145/3662158.3662769.
short: K. Chatterjee, A. Ebrahimzadeh, M. Karrabi, K.Z. Pietrzak, M.X. Yeo, D. Zikelic,
in:, Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed
Computing, Association for Computing Machinery, 2024, pp. 268–278.
conference:
end_date: 2024-06-21
location: Nantes, France
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2024-06-17
corr_author: '1'
das_tickbox: '1'
date_created: 2024-07-28T22:01:10Z
date_published: 2024-06-17T00:00:00Z
date_updated: 2026-07-07T13:30:07Z
day: '17'
ddc:
- '000'
department:
- _id: KrCh
- _id: KrPi
doi: 10.1145/3662158.3662769
ec_funded: 1
external_id:
arxiv:
- '2405.04420'
file:
- access_level: open_access
checksum: 6122bd97b42751ff81c452a19970f67d
content_type: application/pdf
creator: dernst
date_created: 2024-07-29T07:18:12Z
date_updated: 2024-07-29T07:18:12Z
file_id: '17334'
file_name: 2024_ACM_Chatterjee.pdf
file_size: 832034
relation: main_file
success: 1
file_date_updated: 2024-07-29T07:18:12Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 268-278
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed
Computing
publication_identifier:
isbn:
- '9798400706684'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully automated selfish mining analysis in efficient proof systems blockchains
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
year: '2024'
...