---
_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'
...