Online Block Packing and Multidimensional EIP-1559
read the original abstract
We consider the online algorithmic challenge that is faced by blockchains that have multidimensional block constraints and serve quasi-patient bidders. We first provide online approximation algorithms for the important special cases of small transactions or a small number of dimensions; this solves open problems left by [Babaioff and Nisan, EC 2025]. Second, we study multidimensional variants of Ethereum's EIP-1559 protocol. We show that if the block builders manage to approximately optimize each block's welfare myopically, then an approximation to the global offline optimal welfare is obtained. On the other hand, we show that, unlike in the single-dimensional case, EIP-1559 by itself does not guarantee any good approximation.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
SoK: Preconfirmations
The paper systematizes preconfirmation protocols by defining core terms, proposing a general framework, analyzing economics and risks, and surveying implementations in blockchain systems.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.