Aarhus University Seal

Game Theory on the Blockchain: A Model for Games with Smart Contracts

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

We propose a model for games in which the players have shared access to a blockchain that allows them to deploy smart contracts to act on their behalf. This changes fundamental game-theoretic assumptions about rationality since a contract can commit a player to act irrationally in specific subgames, making credible otherwise non-credible threats. This is further complicated by considering the interaction between multiple contracts which can reason about each other. This changes the nature of the game in a nontrivial way as choosing which contract to play can itself be considered a move in the game. Our model generalizes known notions of equilibria, with a single contract being equivalent to a Stackelberg equilibrium, and two contracts being equivalent to a reverse Stackelberg equilibrium. We prove a number of bounds on the complexity of computing SPE in such games with smart contracts. We show that computing an SPE is PSPACE -hard in the general case. Specifically, in games with k contracts, we show that computing an SPE is ΣkP -hard for games of imperfect information. We show that computing an SPE remains PSPACE -hard in games of perfect information if we allow for an unbounded number of contracts. We give an algorithm for computing an SPE in two-contract games of perfect information that runs in time O(mℓ) where m is the size of the game tree and ℓ is the number of terminal nodes. Finally, we conjecture the problem to be NP -complete for three contracts.

Original languageEnglish
Title of host publicationAlgorithmic Game Theory - 14th International Symposium, SAGT 2021, Proceedings : 14th International Symposium, SAGT 2021, Aarhus, Denmark, September 21–24, 2021Proceedings
EditorsIoannis Caragiannis, Kristoffer Arnsfelt Hansen
Number of pages15
Place of publicationCham
Publication year2021
ISBN (print)978-3-030-85946-6
ISBN (Electronic)978-3-030-85947-3
Publication statusPublished - 2021
Event14th International Symposium on Algorithmic Game Theory - Aarhus Institute of Advanced Studies, Aarhus, Denmark
Duration: 21 Sept 202124 Sept 2021
Conference number: 14


Conference14th International Symposium on Algorithmic Game Theory
LocationAarhus Institute of Advanced Studies
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 223699496