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

## 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}*{i=1}^{n} x

\text { s.t. } & \sum*{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

#### Every game has a Nash equilibrium.

#### 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.

#### 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.