TL;DR
This paper introduces two novel protocols that enable smart contracts to implement "correlated equilibria" for two-player games on blockchains. This is a significant advancement because it allows for more sophisticated and potentially more beneficial game outcomes than previously possible with blockchain-based mechanisms, without relying on trusted third parties.
What Problem Does This Paper Address?
In game theory, a "correlated equilibrium" is a solution concept that generalizes Nash equilibria. It allows players to achieve better outcomes by following recommendations from a central "correlation device" (like a traffic light). This device suggests a strategy profile (a combination of actions for all players) sampled from a specific probability distribution, but crucially, each player only sees their own suggested action, not the others'. This privacy is key to the equilibrium's self-enforcing nature.
The challenge on blockchains is that this correlation device is typically a trusted third party. Implementing such a device in a trustless, decentralized manner using smart contracts has been an open problem. Existing blockchain mechanisms can handle Nash equilibria, but correlated equilibria, which offer more expressive power for mechanism design, have been out of reach due to the need for a private, yet coordinated, signal. This paper tackles this gap by proposing ways to implement this "external signal" as a smart contract.
Methods
The paper proposes two distinct protocols to achieve trustless sampling of correlated equilibria:
- Protocol 1: Oblivious Transfer (OT)-based: This protocol leverages Oblivious Transfer, a cryptographic primitive where a receiver can obtain one of several data items from a sender without the sender knowing which item was chosen, and the receiver learns nothing about the other items.
- Alice (Player 1) first obtains a secret random number from a secure random beacon (a smart contract). This number determines her strategy.
- Alice then computes a conditional distribution for Bob's (Player 2) strategy, given her own.
- Using a 1-out-of-N Oblivious Transfer protocol, Alice acts as the sender and Bob as the receiver. Bob privately samples his strategy from the conditional distribution Alice provided.
- To ensure privacy and prevent Alice from knowing Bob's choice, Bob uses a secret choice number. To ensure Bob samples randomly, Alice permutes the data she sends.
- The protocol includes mechanisms for dispute resolution and on-chain commitments to ensure integrity.
- Protocol 2: zk-SNARKs-based: This protocol builds upon the first but incorporates Zero-Knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs) to improve efficiency, particularly for larger strategy spaces.
- Instead of publishing large data arrays directly on-chain, Alice publishes succinct commitments to these arrays and a zk-SNARK proof that verifies the correctness of the data and its relationship to the game's correlated equilibrium.
- This significantly reduces on-chain transaction costs, especially in cases where disputes might arise. The zk-SNARK allows Bob to verify the integrity of Alice's actions without requiring expensive on-chain computations of large datasets.
Datasets
Not discussed in the paper. The paper focuses on theoretical protocols and their implementation on a blockchain platform (Ethereum), rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Correlated Equilibria on Blockchain: The core insight is that the "external signal" or "correlation device" required for correlated equilibria can be implemented as a smart contract, unlocking more sophisticated game-theoretic designs for decentralized applications.
- Bridging Game Theory and Blockchain: The paper demonstrates how advanced cryptographic primitives like Oblivious Transfer and zk-SNARKs can be combined with smart contracts to solve complex game-theoretic problems in a trustless environment.
- Privacy-Preserving Coordination: The protocols achieve a delicate balance: players coordinate their strategies based on a shared distribution but maintain privacy regarding each other's specific choices until after the sampling phase.
- Efficiency Trade-offs: The two protocols highlight a trade-off between the complexity of the cryptographic tools and the resulting on-chain costs. The OT-based protocol is conceptually simpler but can be more expensive for large strategy spaces, while the zk-SNARKs approach offers better scalability at the cost of more complex cryptography.
Key Results
The paper presents two protocols that are proven to be:
- Trustless: They do not rely on any third-party intermediaries.
- Private: They provide the desired privacy properties of correlated equilibria, ensuring players only see their own suggested strategies.
- Gas-Efficient: The protocols are designed to be affordable in practice on Ethereum, with the zk-SNARKs version offering significant cost reductions for larger games. For example, the paper states the second protocol uses "merely $12.14 of gas for each sampling of the correlated equilibrium" in a specific scenario.
Limitations and Future Work
- Two-Player Focus: The current protocols are designed for two-player games. The authors acknowledge that extending these to games with more than two players is an important direction for future research.
- Rationality Assumption: The efficiency analysis often assumes players are rational and act in their own best interest. While mechanisms are in place to incentivize honesty, the behavior of irrational or malicious players is discussed as a potential challenge, particularly for the OT-based protocol where dispute resolution can be costly.
- SRNG Dependency: The first protocol relies on a secret random beacon (SRNG). While this is a standard component in such research, its security and availability are crucial.
- Future Work: The authors explicitly mention extending the work to non-cooperative one-shot games with more than two players as a key area for future research.
Summary updated