On the Welfare of EIP-1559 with Patient Bidders

Moshe Babaioff, Noam Nisan · 2025

Read On the Welfare of EIP-1559 with Patient Bidders by Moshe Babaioff, Noam Nisan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-20031.txt.

Introduction

Moshe Babaioff and Noam Nisan study the fee rule used to pack Ethereum transactions into blocks, in a 2025 paper. Earlier work assumed bidders grow impatient and vanish if not picked at once. In truth, unsent transactions wait in a public pool and can be picked later, so the authors redo the math for patient bidders.

They show that with patient bidders the rule builds blocks of near-best total value, as long as it gets a mild extra allowance that does not grow with time. The paper also proves side results that rule out some tempting upgrades to the rule. For a system that clears billions in trades, the finding says the current rule wastes little when users can wait.

Catalog record

CREATORMoshe Babaioff, Noam Nisan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE92 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-20031

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Welfare of EIP-1559 with Patient Bidders Moshe Babaioff, Noam Nisan Abstract The “EIP-1599 algorithm” is used by the Ethereum blockchain to assemble transactions into blocks. While prior work has studied it under the assumption that bidders are “impatient”, we analyze it under the assumption that bidders are “patient”, which better corresponds to the fact that unscheduled transactions remain in the mempool and can be scheduled at a later time. We show that with “patient” bidders, this algorithm produces schedules of near-optimal welfare, provided it is given a mild resource augmentation (that does not increase with the time horizon). We prove some generalizations of the basic theorem, establish lower bounds that rule out several candidate improvements and extensions, and propose several questions for future work. 1 Introduction 1.1 Background on Blockchains Blockchains like Bitcoin [ Nak09 ] or Ethereum [ But14 ] operate by repeatedly aggregating transactions into blocks. As a first approximation, each transaction requires some ‘‘size’’ and has some value for its user, and each block has some size limit, where the notion of ‘‘size’’ is defined by the blockchain. 1 1 1 E.g. “gas” for Ethereum or (virtual-)bytes for Bitcoin. Each block is assembled by a different ‘‘operator’’ 2 2 2 In Bitcoin these are the “miners” and in Ethereum these are the “validators”. which the blockchain protocol designer tries to motivate to maximize the total value subject to the block’s capacity constraints. A key difficulty here is that both users and operators are selfish and strategic, so the mechanism that specifies which transactions are accepted to the block and how much do their users pay and to whom must take such strategic behavior into account. A large literature has studied such mechanisms. While Bitcoin’s “pay your bid” mechanisms is relatively simple (but not incentive compatible for the users), Ethereum’s mechanism [ BCD+19 ] , known as EIP-1559, is more sophisticated and, following [ Rou21 ] , a large literature (e.g. [ LMR+21 , CS23 , GTW24 , AGHH23 ] ) studies its strategic properties. In this paper we undertake an algorithmic analysis of this protocol and the family of protocols that vary its various parameters. Specifically, we ask to what extent does it indeed succeed in maximizing the social welfare given the size constraints. Our main result is essentially positive: for “patient bidders”, the social welfare achieved by EIP-1559, with a slight tweak of parameters, is close to optimal. Before specifying more precisely what “close to optimal” means, we need to be more specific about our time-model of transactions. Blocks are created one at a time 3 3 3 For Ethereum a block every 12 seconds and for Bitcoin a block every 10 minutes on the average. and transactions arrive continuously through time. Much analysis of blockchains assumes that a transaction that arrives at a certain point in time must be scheduled in the immediately next block or loses all value for its user. This is called the model of “impatient users”. In reality, however, blockchains operate under an opposite assumption and submitted transactions remain in the “mempool” until accepted, and thus may be scheduled at any future block. The model that assumes that transactions can be scheduled at any future time without losing their value, which is closer to how blockchains actually operate, is termed a model with “patient users”, and has only received modest attention [ Nis23 , HLM21 , PS24 , GY24 ] . A more general model may consider a mix of patient, impatient, and also “partially patient” users, who may have some time-sensitivity, e.g., model the value of a transaction as decreasing with its execution time [ HLM21 , PS24 , GY24 ] . Unfortunately, current mainstream blockchain transaction fees mechanisms do not allow the user to express any time preferences. We show the near-optimally of EIP-1559 for fully patient users in the worst case, i.e. without any stochastic or distributional assumptions on the demand. 4 4 4 It is not difficult to observe that if one looks, instead, at impatient users , then any algorithm that relies on historical prices to set inclusion criteria for the current block (as does EIP-1559) may catastrophically fail to achieve any decent social welfare under adversarial conditions. We will also show that no online algorithm can achieve near-optimally for a mix of patient and either impatient or partially patient users (even if they are “very patient”); see Section 1.5.1 . 1.2 The EIP-1559 algorithm and its parameters The EIP-1559 algorithm assembles a sequence of blocks whose average size is at a target of a quantity B per block. 5 5 5 Ethereum’s choice is B=15M gas. I.e. the original constraint of maximum block size is relaxed, and is replaced by effectively limiting the average block size to be B , while relaxing the constraint of maximum block size to being only slightly larger than B . 6 6 6 Maximum size of only 2B , a factor 2 increase that is independent of the parameters of the input (such as the range of per-unit values and the time horizon). This relaxation is justified by the specific constraints of the Ethereum blockchain 7 7 7 I.e. it was deemed that the “syncing time” of “full nodes” (i.e., reading the entire history of the block chain) is more significant than the maximum block size limitation, and for it, only the average block size is important. and may be viewed as a type of resource augmentation which was not technically studied in the literature of bin-packing and knapsack algorithms, and may be of independent interest. 8 8 8 This relaxation may be related in motivation to open-ended bin packing (e.g. [ Eps22 ] ), but not technically so. Here is how it operates: for every block t it choose a price p_{t} (according to an algorithm that we will explain shortly) and accepts only transactions whose value per unit is at least the price p_{t} . A difficulty arises if there are too many transactions with such high value per unit, as the EIP-1559 algorithm does not allow any block to be of total size that is larger than c times the target block size, with the parameter choice c=2 . 9 9 9 I.e. the maximum allowed block size in Ethereum is 30M gas. In this case only a subset of the transactions that fit into the maximum block size is chosen, with the subset determined by an additional “tip” bid that is strategically chosen by each user. In this paper we will not undertake a strategic analysis, and we will analyze the protocol under the assumption that the subset of transactions is being chosen by an adversary 10 10 10 This naturally only strengthens our main result. , making only the following mild assumption: the adversary must pick a maximal (by inclusion) set of transactions that fit into the allowed maximum block size. 11 11 11 This is a mild assumption as any rational operator that is myopic (cares only about the current block and disregards the future) is never better off by excluding transactions that can simply be added to the block. In particular, the presence of (non-negative) tips only encourages the inclusion

Read the complete text