Online Block Packing and Multidimensional EIP-1559
This work solves open problems from Babaioff and Nisan (EC 2025) and provides foundational insights for blockchain mechanism design with multidimensional constraints.
The paper addresses the online algorithmic challenge of block packing with multidimensional constraints in blockchains, providing approximation algorithms for small transactions or few dimensions, and analyzing multidimensional EIP-1559 variants. It shows that myopic optimization by block builders can achieve near-optimal welfare, but EIP-1559 alone fails to guarantee good approximation in multiple dimensions.
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.