# Is Folk's theorem the Blockchain's nightmare

Posted by Bruno Mazorra on May 20, 2022

# Is Folk’s theorem the Blockchain’s nightmare?

source, https://youtu.be/WsrzWuA0xdo

## Editors Note:

Could not find these slides, so these are my own notes. There is more content than this in the presentation.

## Economic rationality

### Individual rationality

An agent is individually rational if they try to maximize its own revenue. Example: Construct block with max fees

A miner receives a set of transactions $$xx _{1}, \ldots, tx x _{n}$$ with gas price $$b_{1}, \ldots, b_{n} and g_{1}, \ldots, g_{n}$$ units of gas. The miner can choose any subset of transactions $T X$ such that $$\sum_{t x \in T X } g_{ tx } \leq \max$$ Gas.

script[type=’math/tex’; mode=display] \begin{equation} T X \text { such that } \sum{ tx \in T X } g{ tx } \leq \max \text { Gas. } \end{equation}

### Example: Transaction inclusion

• A “dummy” node orders transaction by timestamp, by transaction hash or randomly.
• A rational node tries to solve the following optimization problem: \begin{equation} \begin{array}{ll} \max & \sum{i=1}^{n} x{i} b{i} g{i}
\text { s.t. } & \sum
{i=1}^{n} x{i} g{i} \leq \max G a s, \ & x{i} \in{0,1} \text { for } i=1, \ldots, n \end{array} \end{equation}

This is known as the Knapsack problem and is a NP-problem. In general, Ethereum nodes use a greedy approximation algorithm to obtain an approximation of the optimal solution. source, https://youtu.be/WsrzWuA0xdo?t=157

## Game Theory

### The Stage Game

A game is a tuple $$G =(N, A, u)$$ where:

• $N={1, \ldots, n}$ is the set of players.
• $A=\prod_{i=1}^{n} A_{i}$, where $A_{i}$ denotes the set of actions for a player $i$.
• $u_{i}: A \rightarrow R$ is the utility function of a player $i$.
• Players want to maximize $u_{i}$ and take actions simultaneously.

### Strategy

A pure strategy can be thought as a plan subject to the observations they make during the course of the game of play. A mixed strategy is an assignment of a probability to each pure strategy.

### Nash equilibrium

A mixed strategy $s=\left(s_{1}, \ldots, s_{n}\right)$ is a Nash equilibrium if for every player $$i$$, and any strategy $$\tilde{s}_{i}$$, we have that

script[type=’math/tex’; mode=display] \begin{equation} u{i}\left(s{i}, s{-i}\right) \geq u{i}\left(\tilde{s}{i}, s{-i}\right) \end{equation}

### Theorem

#### Example 2: L2 game

Game

Assume $$N=\{1,2\}$$ and $$t=2$$.

• $EV =$ The value that can be extracted if players know the content of txs per block.
• $CR =$ Commit and Reveal. If possible, slash the other player.
• RC $=$ Reveal and Commit. If possible, extract EV.
• $R =$ Reward per Block.
• $S =$ Slashing value s.t. $S » EV$.

Problems and difficulties to cooperate

• Anonymous players.
• Unable to commit to future strategies.
• Economic incentives to deviate from commitment. Conclusion on stage game cooperation Hard to achieve consensus to cooperate.

#### What if games are played indefinitely?

##### Non-Myopic

Players are non-myopic if they are concerned for presents and future payoffs. Given an infinite sequence of payoffs $$r_{0}, r_{1}, r_{2}, \ldots$$ for a player $i$ and a discount factor $$\delta$$ with $$0 \leq \delta<1, i^{\prime}$$ s future discounted reward is \begin{equation} \sum{i=0}^{\infty} \delta^{i} r{i} \end{equation} Intuition on discount factor:

• The agent values about near term profits than future profits.
• The discount factor models the players’ patience.

\begin{equation} \sum{i=0}^{\infty} \delta^{i} r{i} \end{equation}

### Repeated game

#### Repeated games

The stage game is played indefinitely many times. Players can observe past actions. All player: share the same discount factor $\delta$. Player’s utility Let $x_{t}$ be the tuple of actions played at round $t$, then the utility of a player $i$ with discount factor $\delta$ is: \begin{equation} U{i}=\sum{t=0}^{\infty} \delta^{t} u{i}\left(x{t}\right) \end{equation}

### Folk theorem with perfect monitoring

#### Folk Theorem

Let $G$ be any $n$-player game.

• For all strictly pure-action individually rational action profiles ã, that is, $u_{i}(\tilde{a})>\operatorname{minmax}_{i}$ for all $i$, there is a $\bar{\delta} \in(0,1)$ such that for every $\delta \in(\bar{\delta}, 1)$, there exists a subgame-perfect equilibrium of the infinitely repeated game with discount factor $\delta$ in which $\tilde{a}$ is played in every period.
• For all feasible tuple $v$, there is a $\bar{\delta} \in(0,1)$ such that for every $\delta \in(\bar{\delta}, 1)$, there exists a subgame-perfect equilibrium, with payoff $v$, of the infinitely repeated game with public correlation and discount factor $\delta$.

#### Example 1: Arbitrage competition and the Folk theorem

Since $(50 \,/\ 50 )$ is a feasible payoff, we have by Folk theorem that, if both players are enough patient (for $\delta \geq 2 / 3$ holds), there exists a Nash equilibrium $$\left(s_{1}, s_{2}\right) such that u_{i}\left(s_{1}, s_{2}\right)=50 \$$. In these setting, we have that collision among searchers induce:

• $+$ profits for searchers,
• profits for miners. compared to the stage game.

#### System performance

There exists Nash equilibrium that do not lead to egalitarian distribution of rewards.

source, https://youtu.be/WsrzWuA0xdo?t=924

#### Example 2: L2 with Threshold decryption scheme

##### Repeated game: All for nothing

If players are enough patient $(\delta \approx 1)$, then there exists a Nash Equilibrium where both players, play the Reveal-Commit strategy and extract the MEV. System performance Since miners extract MEV from users, the users’ revenue decreases compared to the myopic model.

source, https://youtu.be/WsrzWuA0xdo?t=966