TLDR
- Simple Schelling games only pay a fixed amount p to voters that coordinate. More complex mechanisms can be added to the Schelling game which makes it more robust:
- Modifications to the payoff matrix: redistributive games + symbioitic games, deposits.
- External mechanisms: appeals, cognitive and moral costs associated with accepting a bribe.
- The external mechanisms defacto make collusion more expensive and harder to coordinate:
- With appeals, attackers either must pay bribes every appeal round or only pay for the last round (which itself is hard because it requires the bribe to be successful that round).
- Accounting for cognitive and moral costs increases the amount of bribe (i.e. ε) that attackers have to pay.
- Redistributive games (one of the modifications to the payoff matrix) prove to have nice theoretical properties that make attacking much more expensive.
- Together with appeals, it is shown that an attack cost grows quadratically with the number of voters.
- The Kleros on chain dispute resolution mechanism (which uses a redistributive payoff with appeals) is used as a test bed for coordinated p + ε attacks. In one low stakes experiment, voters were unwilling to consistently accept the bribe. This tentatively validates the theoretical results that collusion is hard with these new mechanisms.
Sources
George, W., & Lesaege, C. (2020). An Analysis of p+ε Attacks on Various Models of Schelling Game Based Systems. CryptoEconomicSystems. https://assets.pubpub.org/33am50c6/51581340370715.pdf
Buterin, V. (2015). The P + epsilon attack. Ethereum Blog. The P + epsilon Attack | Ethereum Foundation Blog
Background
- Coordination games are games where voters are rewarded for all taking the same action.
- Example: In proof of work, miners play a coordination game when choosing which fork of the chain to mine. Miners are rewarded when they mine on the consensus fork.
- Formally, this means the payoff matrix for the game is diagonal.
- Schelling games are a subset of coordination games where there is a single action that rational voters are expected to take.
- Example: In proof of work, miners running standard node software will not take forks where there are invalid transactions.
- When voting over options where only a single one is true (e.g. proof of work when there is only one valid branch), the truth is the Schelling point for the game.
- Schelling games have important applications in crypto:
- Consensus mechanisms (as illustrated in the example above).
- Oracle systems: when a network of voters is incentivized to report the truth (e.g. TruthCoin).
- On chain dispute resolution mechanisms (e.g. Kleros).
- The p + ε attack against Schelling games (where p is the payoff for voters when they coordinate successfully) is a collusion strategy where an attacker essentially bribes voters with incrementally more payoff to choose a specific option. It is an open question whether this attack can be defined against viably.
Core Research Question
- In the context of cryptosystems, what are generalizations of both Schelling games and p + ε attacks? Is an attack viable against advanced Schelling games?
Paper Summary
Method
- The paper considers 3 variants of a Schelling game, all specified by a payoff matrix.
- Notation:
- p: payoff for correct reporting.
- d: deposit made by agents prior to reporting. Receive deposit back only when correct reporting.
- M: total number of agents.
- x: total number of agents (not including USR) which voted for X
- Simple Schelling game:
- Redistributive Schelling game:
- Intuition for the diagonals:
- Numerator is the total pool of winnings: lost deposits + payoff pool.
- Denominator is the amount of players receiving the reward.
- Symbiotic Schelling game:
- Notation:
- There are several other modifications to the simple game model that the paper considers:
- Appeals and counter coordination to combat attacks.
- Moral and cognitive costs associated to accepting bribes from attackers.
- The primary sections of the paper consider:
- Equilibrium when there are moral and cognitive costs for the voters.
- Redistributive schelling games vs. standard p + ε attack.
- Redistributive schelling games vs. modified p + ε attack.
Results
- Equilibrium when there are moral and cognitive costs for the voters.
- Motivation: while the abstract game theory makes the incentives obvious, there are cognitive costs associated with understanding the attack and verifying the smart contract mechanism that coordinates the attacks.
- Formally: we include a moral cost m into the original payoff matrix to account for the cognitive and moral costs associated with accepting a bribe:
- Result: if p + d - m and /epsilon - m have the same sign, there is a dominant strategy. If positive, accept the bribe; if negative, reject the bribe.
- The dominant strategy case can be verified easily (just evaluate each column of the payoff matrix).
- The mixed strategy case is more complicated, and a formal proof is offered in the paper.
- Intuition: if the moral cost of accepting a bribe exceeds the rewards, the bribe will always be rejected. Likewise when the rewards exceed the moral cost.
- “Hence we see that the amount of the ε, namely the bribe that a corrupt voter can receive beyond the normal payout, needs to be large relative to cognitive and moral costs in order for the p + ε attack to be effective. In this way, this attack begins to resemble more traditional bribes”
- Redistributive schelling games vs. standard p + ε attack.
- Note: Many formal arguments are made in this section. We skip them for the sake of brevity and offer the main takeaways.
- Resilience of redistributive schelling games: absent a deposit or appeals rounds, the redistributive game roughly doubles the budget of the attacker.
- With appeals, the redistributive game is much stronger, where the cost of the attacker grows quadratically in the number of participants (vs. linearly for the simple Schelling game).
- Possible modifications to the attack:
- Only offer the bribe in the last round of appeals. This ends up being unlikely to succeed as voters must believe the bribe will work in order for this to be the last round.
- Offer a capped bribe: now, accepting the bribe is not a dominant strategy, and the mechanics become probabilistic. While this theoretically could lower attacker costs, it drastically increases cognitive costs for voters which make it unlikely to work.
- Stress tests on Kleros:
- Setting: simple game where voters distinguished between cats and dogs. Payoffs were a redistributive Schelling game, and a smart contract attack was made available to the voters before hand.
- p = 4 USD and d = 3.5 USD
-
- Shows that the bribe was unable to convince most people, though this is a small sample size of Kleros token holders.
- Surveys indicated that participants were not incentivized to act because the bribe was small, which supports the moral cost associated with accepting a bribe.
- Setting: simple game where voters distinguished between cats and dogs. Payoffs were a redistributive Schelling game, and a smart contract attack was made available to the voters before hand.
Key Takeaways + Applicability
- Schelling games are a paradigm for building consensus around truth on a network, but have some theoretical issues wrt collusion when naively applied. Specifically, they are vulnerable to p + epsilon attacks.
- Unaccounted for cognitive and moral costs associated with accepting bribes makes the attack more expensive in practice, and when experimentally tried in a Kleros court, bribes on the order of $1-$10 were not enough to flip the majority of voters.
- Redistributive Schelling games with an appeals system seem formally and experimentally (though not at scale) resilient to p + epsilon attacks. This validates the mechanism behind dispute resolution systems like Kleros and p2p oracle systems like TruthCoin.
Discussion Questions
- Are the arguments offered in this paper (i.e. cognitive costs, stress tests, formal proofs) convincing that p + eps attacks are unlikely to happen at scale? What are counterpoints that leave Schelling games vulnerable?
- What are the best applications of Schelling games in cryptosystems? Applications we’ve seen so far include:
- Base layer consensus mechanisms
- Oracle systems.
- Dispute resolution systems.