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

Introduction

The rise of permissionless blockchains like Ethereum has introduced a revolutionary capability: smart contracts. These self-executing pieces of code, capable of maintaining state and interacting with other contracts, enable players in a game to deploy autonomous agents that act on their behalf. This fundamentally alters traditional game-theoretic assumptions about rationality. A player can now rationally choose to deploy a contract that commits them to act irrationally in specific situations, thereby making credible threats that were previously non-credible.

This paper introduces a formal model for analyzing these new types of games. We explore how the ability to deploy smart contracts changes the strategic landscape, generalizing established concepts like Stackelberg equilibria and providing new insights into the computational complexity of finding optimal strategies in these environments.

How Smart Contracts Change Game Theory

In conventional game theory, players are assumed to be rational actors who always choose actions to maximize their utility. The concept of a Subgame Perfect Equilibrium (SPE) is found through backward induction, where players reason backwards from the end of the game to determine optimal moves at each step.

Smart contracts disrupt this model. When a player deploys a smart contract:

• They commit to a strategy for the remainder of the game, which is publicly visible and immutable.
• They can make credible threats by programming the contract to take actions that would be irrational in a specific subgame but beneficial for the overall outcome.
• The contract acts autonomously, removing the player's ability to deviate from the pre-committed strategy based on short-term incentives.

This capability to commit transforms the game. Choosing which contract to deploy becomes a strategic move in itself, often taken before the conventional game begins. The interaction between multiple contracts, each reasoning about the others' potential actions, creates a complex, layered game of commitments and counter-commitments.

👉 Explore advanced strategic models

The Formal Model: Games with Smart Contract Moves

Our model builds upon extensive-form games, which represent sequential decision-making as a finite tree. We introduce a new type of node: a smart contract move.

Key Components of the Model

• Extensive-Form Game Tree: A finite tree where non-leaf nodes represent decision points for players, and leaf nodes represent outcomes with associated utility vectors for each player.
• Smart Contract Move: A special node where a player can choose to deploy a contract. This action is equivalent to the player selecting a "cut" in the game tree.
• Cut: A union of subtrees that a contract commits to removing from the set of possible future moves. A cut must respect information sets and cannot destroy the game by removing all possible moves for a player.
• Expanded Tree: The result of transforming a game with smart contract nodes. Each contract move is replaced by a new node where the player chooses among all possible cuts, with each choice leading to a new subgame. The SPE is then computed in this vastly larger expanded tree.

This model elegantly captures the strategic power of smart contracts. Deploying a contract is not just an action within the game; it is a meta-action that redefines the game itself for all players involved.

Recovering Classic Equilibria

A significant strength of our model is its ability to generalize well-known game-theoretic concepts as special cases.

Single Contract as Stackelberg Equilibrium

A Stackelberg equilibrium describes a scenario with a leader and a follower. The leader commits to a strategy first, and the follower optimizes their response based on this commitment.

Proposition: In our model, a game where one player has a single smart contract move is equivalent to a Stackelberg game with that player as the leader. The contract they deploy corresponds to the strategy they commit to, and the resulting SPE in the expanded tree yields the Stackelberg equilibrium outcome.

Two Contracts as Reverse Stackelberg Equilibrium

A reverse Stackelberg equilibrium further empowers the leader. Instead of committing to a single strategy, the leader commits to a response function—a mapping from the follower's possible actions to the leader's best responses. This allows the leader to punish the follower for undesirable choices.

Proposition: A game with two smart contract moves—one for the leader and one for the follower, in that order—is equivalent to a reverse Stackelberg game. The first player's contract can be designed to condition its actions on the contract subsequently deployed by the follower.

These equivalences show that our model provides a unified framework for understanding commitment in games, from classical concepts to the new possibilities enabled by blockchains.

Computational Complexity: The Challenge of Finding equilibria

While modeling these games is powerful, computing optimal strategies is computationally difficult. The expanded game tree, which includes all possible contract deployments, is exponentially larger than the original game.

Our research establishes several important complexity bounds:

• General Case (Imperfect Information): Computing an SPE in games with smart contracts is PSPACE-hard. This is proven by a reduction from the True Quantified Boolean Formula (TQBF) problem, a canonical PSPACE-complete problem.
• Single Contract (Imperfect Information): The problem is NP-complete. We show this via a reduction from the CircuitSAT problem, where a player's contract assigns values to variables in a logical circuit.
• Unbounded Contracts (Perfect Information): Allowing an unlimited number of contracts keeps the problem PSPACE-hard, which we prove by a reduction from a generalized graph 3-coloring problem.
• Two Contracts (Perfect Information): We provide an algorithm that can compute an SPE in time O(|T| * |L|^2), where |T| is the size of the game tree and |L| is the number of terminal nodes. This is a positive result, showing that for a small, fixed number of contracts, computation can be tractable for reasonable game sizes.

We conjecture that the problem for three contracts is NP-complete, lying between the efficiency of the two-contract algorithm and the hardness of the unbounded case.

Table: Overview of Complexity Results for Computing SPE

Applications and Implications

This model is not merely theoretical; it has practical implications for the design and analysis of decentralized systems.

• Blockchain Security: Proof-of-Stake (PoS) blockchains and other consensus mechanisms can be analyzed as games where validators can deploy contracts. Understanding the equilibria helps assess the system's resilience to strategic manipulation.
• DeFi and Financial Applications: Decentralized finance (DeFi) protocols often involve complex interactions between users and automated market makers (AMMs). Our model can help predict user behavior and identify potential exploit vectors based on strategic contract deployment.
• Mechanism Design: When designing auctions, voting systems, or other mechanisms on a blockchain, architects must account for the fact that participants can use smart contracts. Our model provides tools to ensure mechanisms are robust to these strategic commitments.

The ability to pre-commit via smart contracts is a double-edged sword. It can be used to create more stable and efficient equilibria, but it can also be used to coordinate attacks or exploit systems in unforeseen ways.

👉 Learn more about strategic commitment

Frequently Asked Questions

What is a smart contract in game theory?

In game theory, a smart contract is a formalization of a player's ability to irreversibly commit to a strategy or a set of rules before a game is played. It is a programmable agent that acts on the player's behalf, making their threats or promises credible because deviation is impossible.

How does a smart contract create a credible threat?

A threat is credible if it is rational to carry out. A smart contract makes a threat credible by removing the player's autonomy. The contract is programmed to execute the threatening action regardless of whether it seems irrational in the moment, which forces other players to take the threat seriously when forming their strategies.

What is the difference between a Stackelberg equilibrium and a Nash equilibrium?

A Nash equilibrium is a set of strategies where no player can benefit by unilaterally changing their strategy. A Stackelberg equilibrium is a sequential concept where a leader commits to a strategy first, and a follower then responds optimally. The Stackelberg outcome is often better for the leader than any Nash equilibrium because the commitment power allows them to influence the follower's choice.

Why is computing equilibria with smart contracts so complex?

The complexity arises because deploying a contract is a meta-action that creates a new, larger game. Each possible contract a player could deploy leads to a different subgame. Reasoning about all possible contracts and their interactions causes an exponential explosion in the number of scenarios that must be analyzed, pushing the problem into higher complexity classes.

Are these results only relevant for blockchain-based games?

While motivated by blockchain technology, the model is abstract and general. It applies to any strategic setting where players have the ability to make binding, automated commitments before engaging in an interaction. This could include certain automated trading scenarios or long-term business contracts.

What is the significance of the reverse Stackelberg equilibrium?

The reverse Stackelberg equilibrium represents a significant increase in strategic power for the leader. Instead of just committing to a single action, the leader commits to a full strategy that punishes the follower for making undesirable choices. This allows the leader to extract more value from the interaction and achieve a more favorable outcome.