@inproceedings{17329,
  abstract     = {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.},
  author       = {Alistarh, Dan-Adrian and Chatterjee, Krishnendu and Karrabi, Mehrdad and Lazarsfeld, John M},
  booktitle    = {Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing},
  isbn         = {9798400706684},
  location     = {Nantes, France},
  pages        = {40--49},
  publisher    = {Association for Computing Machinery},
  title        = {{Game dynamics and equilibrium computation in the population protocol model}},
  doi          = {10.1145/3662158.3662768},
  year         = {2024},
}

@inproceedings{17328,
  abstract     = {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.
In 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.},
  author       = {Chatterjee, Krishnendu and Ebrahimzadeh, Amirali and Karrabi, Mehrdad and Pietrzak, Krzysztof Z and Yeo, Michelle X and Zikelic, Dorde},
  booktitle    = {Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing},
  isbn         = {9798400706684},
  location     = {Nantes, France},
  pages        = {268--278},
  publisher    = {Association for Computing Machinery},
  title        = {{Fully automated selfish mining analysis in efficient proof systems blockchains}},
  doi          = {10.1145/3662158.3662769},
  year         = {2024},
}