Blockchains, MEV and the knapsack problem: a primer
In this paper, we take a close look at a problem labeled maximal extractable value (MEV), which arises in a blockchain due to the ability of a block producer to manipulate the order of transactions within a block. Indeed, blockchains such as Ethereum have spent considerable resources addressing this issue and have redesigned the block production process to account for MEV. This paper provides an overview of the MEV problem and tracks how Ethereum has adapted to its presence. A vital aspect of the block building exercise is that it is a variant of the knapsack problem. Consequently, this paper highlights the role of designing auctions to fill a knapsack--or knapsack auctions--in alleviating the MEV problem. Overall, this paper presents a survey of the main issues and an accessible primer for researchers and students wishing to explore the economics of block building and MEV further.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Knapsack: Connectedness, Path, and Shortest-Path
We study the knapsack problem with graph theoretic constraints. That is, we assume that there exists a graph structure on the set of items of knapsack and the solution also needs to satisfy certain graph theoretic proper…
The Blockchain Game: Synthesis of Byzantine Systems and Nash Equilibria
This position paper presents a synthesis viewpoint of blockchains from two orthogonal perspectives: fault-tolerant distributed systems and game theory. Specifically, we formulate a new game-theoretical problem in the con…
FormPositionA Theoretical Assessment of Solution Quality in Evolutionary Algorithms for the Knapsack Problem
Evolutionary algorithms are well suited for solving the knapsack problem. Some empirical studies claim that evolutionary algorithms can produce good solutions to the 0-1 knapsack problem. Nonetheless, few rigorous invest…
Evolutionary AlgorithmsThe Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks
In this paper, we study the bandits with knapsacks (BwK) problem and develop a primal-dual based algorithm that achieves a problem-dependent logarithmic regret bound. The BwK problem extends the multi-arm bandit (MAB) pr…
Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
The development of a satisfying and rigorous mathematical understanding of the performance of neural networks is a major challenge in artificial intelligence. Against this background, we study the expressive power of neu…
Combinatorial Optimization