arXiv CSopen access

Dynamic Transaction Scheduling and Pricing in the Ethereum Mempool

Dynamic Transaction Scheduling and Pricing in the Ethereum Mempool

arXiv:2605.12794v1 [cs.GT] 12 May 2026

FATEMEH FARDNO, University of Illinois Urbana-Champaign, USA S. RASOUL ETESAMI, University of Illinois Urbana-Champaign, USA The Ethereum blockchain utilizes the EIP-1559 algorithm to manage transaction inclusion and block assembly. However, the EIP-1559 algorithm and much of the existing literature address this problem from a static perspective, emphasizing how prices evolve over time without considering the dynamic evolution of transactions within the mempool. Motivated by this framework, we study a dynamic transaction scheduling problem in which transactions have heterogeneous sizes and per-unit values and arrive in the mempool over time. While prior work typically assumes that transactions are impatient, we instead model them as patient, reflecting the fact that unscheduled transactions remain in the mempool and may be scheduled in future blocks. To explicitly account for the stochastic dynamics of transactions waiting in the mempool, we model the problem as a discounted Markov Decision Process (MDP) that captures both arrival dynamics and the evolving state of the transaction pool. To this end, we first provide a novel primal–dual interpretation of the static EIP-1559 algorithm, which allows us to view the pricing scheme as the dual variables of an appropriate social welfare maximization program. This perspective enables us to characterize the interaction among pricing, block capacity constraints, and transaction selection. Building on this interpretation, we extend the framework by presenting a dual-based formulation of the transaction scheduling problem in the dynamic setting, interpreting block prices as decision variables linked to the dual occupancy measures of the underlying MDP. Moreover, we formulate the objective as maximizing the long-run discounted reward while accounting for holding costs and capacity overshoot penalties. We employ the Natural Policy Gradient (NPG) algorithm to determine the optimal scheduling policy. Our results show that dynamic pricing stabilizes the transaction pool while maximizing long-run discounted reward. In particular, as the overshoot penalty increases, the average scheduled transaction volume converges to the target block capacity, and the resulting NPG policy updates closely resemble the EIP-1559 price update rule [Babaioff and Nisan, 2024] in the static setting. We also validate our theoretical findings through extensive numerical experiments. Finally, we study two special cases of the MDP formulation: one with homogeneous transactions and one with uniform arrivals. In the homogeneous case, where the protocol directly controls the scheduled transaction volume, we show that the optimal policy has a threshold structure. Motivated by this characterization, we then propose a bang–bang pricing mechanism for uniform arrivals to address the challenge of block overflow and derive a theoretical lower bound on the block capacity required to ensure system stability.

Contents Abstract Contents 1 Introduction 2 Static Online Scheduling Problem 3 An MDP Formulation for the Dynamic Scheduling Problem 4 An Online Revenue Maximizing Algorithm for the Dynamic Scheduling Problem 5 Optimality of Threshold Policies for Homogeneous Dynamic Scheduling Problem 6 Block Capacity Lower Bounds under Bang–Bang Pricing with Uniform Arrivals 7 Conclusions References A An Alternative Primal-Dual Formulation for EIP-1559 B Auxiliary Lemmas and Omitted Proofs

0 0 1 4 8 9 14 17 22 22 24 26

Fatemeh Fardno and S. Rasoul Etesami

1

1

Introduction

Blockchains are distributed, tamper-resistant digital ledgers that record transactions across a network of computers in a way that ensures transparency, security, and decentralization [Nakamoto, 2008]. Blockchains, such as Ethereum [Buterin, 2014], operate by repeatedly scheduling transactions into blocks. For simplicity, one may assume that each transaction has a size and a value per size for its user, and that each block has a capacity limit. Blocks are assembled by validators, whom the protocol designer seeks to incentivize to maximize the total value of included transactions subject to this capacity constraint. A key challenge is that both users and validators are selfish and strategic, so the transaction selection mechanism must account for such behavior. Ethereum addresses this challenge through the EIP-1559 mechanism [Buterin et al., 2019], which relaxes the strict maximum block size from 𝐵 to 𝑐 · 𝐵 for some 𝑐 > 1, and instead effectively constrains the average block size to the target value 𝐵. As a result, EIP-1559 produces a sequence of blocks whose sizes may vary over time, but whose average is regulated to remain close to 𝐵. The EIP-1559 mechanism operates as follows. For each block 𝑡, the mechanism sets a price 𝑝𝑡 and accepts only transactions whose value per unit size exceeds 𝑝𝑡 . Transactions that do not meet this threshold remain in the mempool until they are scheduled at a later time. We assume that transactions are patient, meaning they can be scheduled at any future time without losing value. If the total size of eligible transactions exceeds the maximum block size 𝑐 · 𝐵, then transactions are prioritized according to the tips they are willing to pay. In this paper, we do not consider tips in our analysis and instead assume that, whenever the capacity constraint 𝑐 · 𝐵 is violated, an adversary selects which transactions are included in the block until the capacity 𝑐 · 𝐵 is reached. The price is updated according to a simple rule [Babaioff and Nisan, 2024]: if the total size of scheduled transactions exceeds the target block capacity 𝐵, the price for the next block is increased; otherwise, it is decreased. More formally, the price evolves according to o n 𝑄𝑡 −𝐵 𝑝𝑡 +1 = max 𝑝 min, 𝑝𝑡 · 𝑒 𝜂 𝐵 , where 𝑄𝑡 denotes the total size of block 𝑡, and 𝜂 is a small constant, set in Ethereum to 𝜂 = 18 . The protocol designer also specifies a minimum price 𝑝 min to ensure that the block price never falls below this level. This pricing mechanism, while simple and effective as shown in [Babaioff and Nisan, 2024], does not incorporate information about transactions waiting in the mempool or about newly arriving transactions. Such information can be important in settings where the cost of holding transactions in the mempool is high, in which case it may be desirable to schedule more than the target block size in order to prevent the mempool from becoming congested. We first formulate the transaction scheduling problem as a linear program with the objective of maximizing social welfare. We then show that the block price arises naturally as a dual variable of this linear program. This observation allows us to extend EIP-1559 to a dynamic setting with patient users using a Markov Decision Process (MDP), in which the action taken by the mechanism at each time 𝑡 is the price set for block 𝑡. More specifically, to explicitly capture the stochastic dynamics of transactions waiting in the mempool, we model the protocol as the decision-making agent in this MDP. The state corresponds to the mempool configuration, that is, the number of transactions of each value and size currently present, and the action is the price chosen by the protocol. The reward is defined to include penalties for mempool congestion as well as for scheduling transactions in excess of the target block capacity. Unlike the original EIP-1559 framework, our objective is not to maximize social welfare, but rather to reduce mempool congestion while still aiming to meet the target block capacity. We nevertheless show that, under an appropriate choice of parameters, the average volume of scheduled transactions converges to the same level as that achieved by the EIP-1559 algorithm.

Fatemeh Fardno and S. Rasoul Etesami

2

We then formulate the objective of maximizing the long-run discounted reward and apply the Natural Policy Gradient (NPG) algorithm to compute an optimal policy. Our results show that, as the penalty for exceeding the target block capacity increases, the average volume of scheduled transactions converges to that of the EIP-1559 algorithm, while the resulting policy updates closely resemble the EIP-1559 price update rule. We finally study two special cases of the MDP formulation. First, we consider a homogeneous setting in which all transaction sizes and values are identical. In this case, pricing becomes irrelevant because all transactions have the same value, and the problem reduces to one in which the protocol directly controls the scheduled transaction volume. In this case, we show that the optimal policy has a threshold structure. In particular, as long as mempool congestion remains below a certain threshold, the protocol schedules the minimum possible volume. Once congestion reaches the threshold, the protocol schedules more than 𝐵 units to reduce congestion, continuing until congestion falls below the threshold, at which point the cycle repeats. Subsequently, we study another special case of the MDP in which arrivals are uniform, meaning that at each time step exactly one transaction of each type arrives in the system. Motivated by the simple threshold structure of the optimal scheduling policy in the homogeneous transaction setting, we propose and analyze a bang–bang pricing mechanism for the uniform arrival setting; that is, a mechanism in which the price is restricted to either its minimum or maximum value. In particular, we derive a theoretical lower bound on the block capacity 𝐵 required to ensure system stability under the bang–bang pricing mechanism with uniform arrivals. 1.1

Related Works

In the Ethereum blockchain, the transaction fee mechanism determines the price that users pay to have their transactions included in the blockchain. In recent years, there has been significant progress in the design and analysis of blockchain transaction fee mechanisms, particularly within Ethereum. A foundational line of work was initiated by Vitalik Buterin [Buterin, 2014, 2018], who proposed a set of ideas aimed at controlling block size through protocol-controlled pricing. Central among these ideas is EIP-1559, a transaction fee mechanism originally proposed by Buterin [Buterin et al., 2019] and later implemented in Ethereum. The EIP-1559 mechanism has since been analyzed in academic works, including the paper by Tim Roughgarden [Roughgarden, 2020], which provides the first game-theoretic analysis of EIP-1559, examining its incentive properties and the economic rationale behind the price update rule. More recently, Babaioff et al. [Babaioff and Nisan, 2024] studied the optimality properties of the EIP-1559 mechanism. While their analysis provides strong theoretical support for EIP-1559 in static settings, it does not explicitly model the dynamic evolution of transactions in the mempool over time. Several other works study different aspects of the EIP-1559 mechanism. For example, Reijsbergen et al. [Reijsbergen et al., 2021] show that, while EIP-1559 achieves its goal on average, its short-term dynamics can be chaotic. In a different direction, Hougaard et al. [Hougaard and Pourpouneh, 2023] analyze EIP-1559 in settings where miners behave strategically rather than passively following the protocol. Another related work, [Angeris et al., 2024], also formulates blockchain resource allocation as an optimization problem and interprets prices through dual variables. However, their analysis focuses on regret with respect to the single best fixed price in hindsight, whereas we provide a competitive ratio bound against the optimal social welfare, which is a stronger and more challenging benchmark to achieve. Our work differs more fundamentally in that, by interpreting prices as dual variables, we extend the framework to a dynamic setting with full mempool information. In this setting, we show that, in the absence of congestion penalties, the resulting update rule coincides with EIP-1559.

Fatemeh Fardno and S. Rasoul Etesami

3

This body of work primarily adopts a static perspective, focusing on how prices evolve in response to previous block utilization and strategic user behavior, rather than on the stochastic evolution of transactions in the mempool. In contrast to this literature, our work explicitly models the dynamics of the mempool, treating unscheduled transactions as state variables that directly influence long-term scheduling decisions. There is also a large body of literature studying dynamic pricing in EIP-1559 [Ferreira et al., 2021, Leonardos et al., 2023]. Crapis et al. [Crapis et al., 2024] formulate blockchain fee design as a sequential decision-making problem and derive optimal fee update rules, which are empirically compared to EIP-1559 using Ethereum data. In this framework, the protocol that sets transaction fees acts as the learning agent; however, the model does not satisfy the Markov property. Interestingly, they show that the resulting optimal policy resembles the EIP-1559 update rule, with some key differences. In particular, EIP-1559 uses the current block size as a naive estimate for future demand, whereas their optimal policy relies on an explicit predictive estimate. Leonardos et al. [Leonardos et al., 2021] model transaction arrivals to the mempool as a Poisson process with impatient transactions, meaning that they leave the pool if they are not included in the next block. They analyze the price update rule as a discrete-time, discrete-space stochastic process {𝑝𝑡 }𝑡 ≥0 , where the source of randomness is the number of transactions included in block 𝑡 given the price 𝑝𝑡 . They study the convergence and stability of the resulting dynamics and derive bounds on the step size of the price update rule that guarantee global convergence to equilibrium. From a different perspective, [Inami and Phung-Duc, 2025] studies the EIP-1559 mechanism using tools from queuing theory. Similar to our approach, the mempool is modeled as a collection of queues, with the system state defined by the lengths of these queues. However, rather than maintaining separate queues for each transaction type as in our approach, transactions are classified into high-priority and low-priority classes, each with its own queue. Within this framework, the authors derive key performance metrics, including stability conditions, the stationary distribution, and the average queue length and waiting time for each transaction class. Similar to our approach, [Madrigal-Cianci et al., 2025] analyzes the EIP-1559 mechanism using a Markovian framework. Under suitable assumptions, the authors show that the price process {𝑝𝑡 }𝑡 ≥0 satisfies the Markov property and can be modeled as a discrete-time Markov chain. This characterization allows them to study the long-run behavior of the price. 1.2

Contributions

The key contributions of this work are as follows: • We present a novel primal–dual interpretation of the EIP-1559 algorithm, which enables us to view its pricing scheme as the dual variables of an appropriate social welfare maximization program. Using this principled primal–dual framework, we analyze the competitive ratio of the EIP-1559 algorithm. • Building upon the primal–dual analysis, we extend the framework to a dynamic setting by modeling the state evolution as a Markov decision process (MDP). • We employ an episodic Natural Policy Gradient (NPG) method to determine the optimal scheduling policy in the MDP. In particular, we show that the exponential price update rule used in EIP-1559 emerges naturally as a special case of the NPG algorithm, thereby providing a formal justification for the mechanism’s design. We also validate our results numerically. • We analytically study two special cases of the MDP formulation: one with homogeneous transactions and one with uniform arrivals. In the homogeneous transaction setting, we show that the optimal policy has a threshold structure. Motivated by this result, we propose a simple bang–bang pricing mechanism for the uniform arrival setting and use it to derive a lower bound on the target block capacity 𝐵 required to ensure stability under such policies.

Fatemeh Fardno and S. Rasoul Etesami

2

4

Static Online Scheduling Problem

In this section, we present an online transaction scheduling problem in the static setting, i.e., without any state evolution, and extend this model to a dynamic setting in Section 3. Consider an online transaction scheduling problem in which time is divided into periods 𝑡 = 1, . . . ,𝑇 , each corresponding to a block with fixed capacity 𝐵. At each time 𝑡, a set of transactions arrives. Each transaction 𝑗 is characterized by a size 𝑞 𝑗 and a per-unit value 𝑣 𝑗 , resulting in a total value of 𝑞 𝑗 𝑣 𝑗 if it is scheduled in a block. Transaction 𝑗 arrives at time 𝑟 𝑗 and is patient, meaning that it can be scheduled in any block 𝑡 ≥ 𝑟 𝑗 without loss of value. The objective is to schedule transactions across blocks so as to maximize social welfare, defined as the total value of scheduled transactions over all blocks. Remark 1. In the EIP-1559 mechanism, the strict maximum block size is relaxed to 2𝐵, while the price update rule effectively constrains the average block size to the target value 𝐵. A difficulty arises when there are too many transactions with high per-unit values. Under EIP-1559, the total size of any block is constrained to be at most twice the target block size. In this case, we assume that an adversary selects a maximal (by inclusion) set of transactions that fit within the allowed maximum block size, i.e., 2𝐵. In the offline setting, when all transaction arrival times and values/sizes are given a priori, we can write a linear program relaxation that maximizes social welfare subject to block capacity constraints and feasibility constraints on transaction assignments. To this end, let 𝑥 𝑗𝑡 ∈ [0, 1] denote the fraction of transaction 𝑗 scheduled in block 𝑡. The resulting (primal) linear program relaxation is as follows 𝑇 ∑︁ ∑︁ max SW := 𝑞 𝑗 𝑣 𝑗 𝑥 𝑗𝑡 (1) 𝑗 ∈ C 𝑡 =1 𝑇 ∑︁

s.t.

𝑥 𝑗𝑡 ≤ 1 ∀𝑗

𝑡 =𝑟 𝑗

∑︁

𝑥 𝑗𝑡 𝑞 𝑗 ≤ 2𝐵

∀𝑡

𝑗∈C

𝑥 𝑗𝑡 ≥ 0 ∀𝑗 ∈ C, 𝑡 ≥ 𝑟 𝑗 , where C is the set of all transactions. Subsequently, the dual program can be written as min

𝑇 ∑︁

𝛽𝑡 +

𝑡 =1

𝑛 ∑︁

𝛼𝑗

(2)

𝑗=1

𝛽𝑡 𝑞 𝑗 + 𝛼 𝑗 ∀𝑗, ∀𝑡 ≥ 𝑟 𝑗 2𝐵 𝛽𝑡 ≥ 0, 𝛼 𝑗 ≥ 0 ∀𝑗, 𝑡 .

s.t. 𝑞 𝑗 𝑣 𝑗 ≤

We now provide an interpretation of the dual variables. Let 𝛽𝑡 denote the price of using the full capacity 2𝐵 of block 𝑡. Scheduling 𝑞 𝑗 units of transaction 𝑗 on block 𝑡 therefore incurs a cost of 𝛽𝑡 2𝐵 𝑞 𝑗 . Transaction 𝑗 has total value 𝑣 𝑗 𝑞 𝑗 . Thus, if it is scheduled on block 𝑡, its utility is 𝑞𝑗𝑣𝑗 − Define

𝛽𝑡 𝑞𝑗 . 2𝐵

  𝛽𝑡 𝛼 𝑗 := max 𝑞 𝑗 𝑣 𝑗 − 𝑞 𝑗 , 𝑡 ≥𝑟 𝑗 2𝐵

Fatemeh Fardno and S. Rasoul Etesami

5

which represents the maximum utility that transaction 𝑗 can achieve. Since transactions never accept negative utility, transaction 𝑗 is scheduled only on blocks whose price does not exceed its value, i.e., 𝛽𝑡 ≤ 𝑣𝑗. 2𝐵 Therefore, the problem of choosing the allocation variables 𝑥 𝑗𝑡 reduces to the problem of setting a 𝛽 price for each block 𝑡. As a result, transactions with 𝑣 𝑗 ≥ 2𝐵𝑡 are scheduled in block 𝑡. Another way to view this problem is through the objective of maximizing social welfare, which naturally leads us to schedule as many transactions as possible. To achieve this, transactions with high values should be scheduled on blocks with high prices; otherwise, low-value transactions may be left without any blocks on which they can be scheduled. Consequently, we prefer the surplus 𝛼 𝑗 of each transaction to be as small as possible (ideally zero). At the same time, prices should be kept as low as possible so as to encourage transactions to submit their jobs. This reasoning provides intuition for the dual objective function. Remark 2. If transactions act strategically, they could obtain a reward of at most 𝛼 𝑗 . In this formulation, however, we assume that transactions do not behave strategically. Instead, they purchase the first block whose price is below their value and that has sufficient remaining capacity. Í Remark 3. The capacity constraint 𝑗 ∈ C 𝑞 𝑗 𝑥 𝑗𝑡 ≤ 2𝐵 in the primal formulation (1) captures the hard cap on block size imposed by the EIP-1559 mechanism. Note that the target block size 𝐵 is not enforced as a feasibility constraint; instead, it emerges endogenously through the price update rule, which adjusts prices in response to block congestion. Our primal–dual formulation therefore enforces feasibility via the hard cap constraint, while regulating the realized block size through price updates. We refer the reader to the supplementary material in Appendix A for a more detailed primal–dual program that directly incorporates the target block size constraint into the objective function of the primal. 2.1

Competitive Ratio Analysis of EIP-1559 Using the Primal–Dual Method

Building on the linear program relaxation of the static online scheduling problem, in this section, we analyze the competitive ratio of the EIP-1559 algorithm using a principled primal–dual approach.1 To that end, we first formally describe the EIP-1559 mechanism in Algorithm 1. Algorithm 1 EIP-1559 Pricing Mechanism Require: Target block capacity 𝐵, hard cap 2𝐵, update parameter 𝜂 > 0, minimum price 𝑝 min , horizon 𝑇 1: Initialize base fee 𝑝 1 ≥ 𝑝 min 2: for 𝑡 = 1, 2, . . . ,𝑇 do 3: Announce base fee 𝑝𝑡 4: Include transactions with value 𝑣 𝑗 ≥ 𝑝𝑡 until total size2𝑄𝑡 ≤ 2𝐵. 5: Update price:    𝑄𝑡 − 𝐵 𝑝𝑡 +1 = max 𝑝 min, 𝑝𝑡 exp 𝜂 (3) 𝐵 6: end for 1 The competitive ratio of an online algorithm is the worst-case ratio between the objective value achieved by the online

algorithm and that of an optimal offline algorithm with full knowledge of the input.

6

Fatemeh Fardno and S. Rasoul Etesami

Theorem 1. The EIP-1559 algorithm is 𝛾-competitive for the static online scheduling problem where   2(𝑣 max − 𝑝 min ) 4𝐵 𝛾 = max . , 𝑣 max 𝑞 min𝑒 𝜂 (𝑞min −𝐵)/𝐵 Proof. Let SWOA denote the total social welfare achieved by the EIP-1559 online algorithm (OA) over the first 𝑇 blocks, and let SWOPT denote the optimal offline welfare. Moreover, let 𝑝𝑡 be the EIP-1559 price per unit size in block 𝑡, and define 𝛽𝑡 := 2𝐵 · 𝑝𝑡

𝑡 = 1, . . . ,𝑇 .

For each transaction 𝑗 with arrival time 𝑟 𝑗 , define n o 𝛼 𝑗 := max 0, max 𝑞 𝑗 (𝑣 𝑗 − 𝑝𝑡 ) . 𝑡 ≥𝑟 𝑗

Then, for every 𝑡 ≥ 𝑟 𝑗 , we have 𝛽𝑡 𝑞𝑗 + 𝛼𝑗, 2𝐵 so that (𝛼, 𝛽) is feasible for the dual program in Eq. (2). Using weak duality for the primal maximization program in Eq. (1), we have 𝑞 𝑗 𝑣 𝑗 ≤ 𝑝𝑡 𝑞 𝑗 + 𝛼 𝑗 =

SWOPT ≤

𝑇 ∑︁ 𝑡 =1

𝛽𝑡 +

∑︁

𝛼𝑗 .

(4)

𝑗

Next, we establish two (independent) lower bounds. • We first lower-bound SWOA . The worst case occurs when each transaction 𝑗 is scheduled in 𝛽 𝑞 a block 𝑡 such that 𝑞 𝑗 𝑣 𝑗 − 𝑡𝐵 𝑗 = 𝛼 𝑗 . Let 𝑡 𝑗 denote this block for transaction 𝑗. Note that for unscheduled transactions we set 𝛼 𝑗 = 0. It then follows that ∑︁ SWOA = 𝑣 𝑗𝑞𝑗 𝑗: scheduled

  𝛽𝑡 𝑗 𝑞 𝑗 𝛽𝑡 𝑗 𝑞 𝑗 = 𝑣 𝑗𝑞𝑗 − + 2𝐵 2𝐵 𝑗: scheduled  ∑︁  𝛽𝑡 𝑗 𝑞 𝑗 = 𝛼𝑗 + 2𝐵 ∑︁

𝑗: scheduled

≥

𝑛 ∑︁

𝛼 𝑗 + 𝑝 min

∑︁

𝑞𝑗 𝑗: scheduled 𝑛 𝑛 ∑︁ ∑︁ 𝛼𝑗 ≥ 𝛼 𝑗 + 𝑝 min 𝛽𝑡 𝑗 𝑗=1 𝑗=1 𝑣 𝑗 − 2𝐵   ∑︁ 𝑛 𝑝 min ≥ 1+ 𝛼𝑗 𝑣 max − 𝑝 min 𝑗=1 𝑛 ∑︁ 𝑣 max = 𝛼𝑗 𝑣 max − 𝑝 min 𝑗=1 𝑗=1

(5)

2 If the total size of eligible transactions exceeds 2𝐵, the miner selects a maximal (by inclusion) subset of eligible transactions

whose total size does not exceed the maximum block capacity, prioritizing transactions according to the tips they offer.

7

Fatemeh Fardno and S. Rasoul Etesami

where 𝑝 min is the minimum price set by the EIP-1559 protocol and 𝑣 max is the maximum value of the transactions. Í • We now derive a lower bound for SWOA based on 𝑇𝑡=1 𝛽𝑡 . For this bound, we assume that no block is empty. Let Alg𝑡 denote the social welfare of the online algorithm up to time 𝑡, so that Alg𝑡 +1 − Alg𝑡 represents the value scheduled in block 𝑡 + 1 by the online algorithm. Also, Í let 𝑄𝑡 = 𝑗 ∈ C 𝑞 𝑗 𝑥 𝑗𝑡 be the total amount of transactions scheduled in block 𝑡. We then have ∑︁ Alg𝑡 +1 − Alg𝑡 = 𝑞𝑗𝑣𝑗 𝑗:scheduled on block 𝑡 +1

∑︁

≥ 𝑝𝑡 +1

𝑞𝑗

𝑗:scheduled on block 𝑡 +1

= 𝑝𝑡 +1𝑄𝑡 +1 ≥ 𝑝𝑡 +1𝑞 min, where 𝑝𝑡 +1 is the price of block 𝑡 + 1 and is given by 𝑝𝑡 +1 = max{𝑝 min, 𝑝𝑡 𝑒 𝜂 (𝑄𝑡 −𝐵)/𝐵 }. Using 𝛽 the fact that 𝑝𝑡 = 2𝐵𝑡 , we have ∑︁ Alg𝑡 +1 − Alg𝑡 = 𝑞𝑗𝑣𝑗 𝑗:scheduled on block 𝑡 +1

≥ 𝑝𝑡 +1𝑞 min ≥ 𝑞 min𝑝𝑡 𝑒 𝜂 (𝑄𝑡 −𝐵)/𝐵 𝛽𝑡 𝜂 (𝑞min −𝐵)/𝐵 𝑒 . 𝐵 Given that the online algorithm can run up to time 𝑇 , we have ≥ 𝑞 min

𝑞 min𝑒 𝜂 (𝑞min −𝐵)/𝐵 ∑︁ 𝛽𝑡 . 2𝐵 𝑡 =1 𝑇

SWOA ≥

(6)

To complete the proof, by combining the lower bounds in Eq. (5) and Eq. (6), we get ∑︁ 𝑞 min𝑒 𝜂 (𝑞min −𝐵)/𝐵 ∑︁ 𝑣 max 𝛽𝑡 + 𝛼𝑗 . 4𝐵 2(𝑣 max − 𝑝 min ) 𝑗 𝑡 =1 𝑇

SWOA ≥ Hence 𝑇 ∑︁ 𝑡 =1

𝛽𝑡 +

∑︁ 𝑗

 𝛼 𝑗 ≤ max

4𝐵 𝑞 min𝑒 𝜂 (𝑞min

, −𝐵)/𝐵

2(𝑣 max − 𝑝 min ) 𝑣 max



SWOA .

This in view of (4) shows that the EIP-1559 algorithm is 𝛾-competitive with   2(𝑣 max − 𝑝 min ) 4𝐵 𝛾 = max , . 𝑣 max 𝑞 min𝑒 𝜂 (𝑞min −𝐵)/𝐵

(7) □

Remark 4. While the competitive ratio of EIP-1559 was analyzed in [Babaioff and Nisan, 2024], our analysis has several key advantages: (i) it provides a simple and principled analysis based on the primal–dual method; (ii) unlike the competitive-ratio analysis in [Babaioff and Nisan, 2024], we do not consider additional Γ time steps for the online algorithm; and (iii) it offers an interpretable way of choosing prices in terms of the dual variables of the underlying linear program, which in turn allows us to extend this method to a dynamic setting.

Fatemeh Fardno and S. Rasoul Etesami

3

8

An MDP Formulation for the Dynamic Scheduling Problem

Building upon the primal–dual analysis of the static online scheduling problem, in this section we provide an extension to the dynamic version of the problem by modeling state evolution using a Markov decision process (MDP) formulation. We consider a pool of transactions with heterogeneous sizes and values.3 Transactions take per-unit values from the finite set V = {𝑣 1, . . . , 𝑣𝑛 } with 𝑛 ≥ 2, and sizes from the finite set Q = {𝑞 1, . . . , 𝑞𝑚 }. At each time 𝑡 = 1, 2, . . ., the system state is represented by a matrix S𝑡 ∈ Z𝑚×𝑛 ≥0 , where the (𝑖, 𝑗)th entry, denoted by S𝑡 [𝑖, 𝑗], records the number of transactions of size 𝑞𝑖 and value 𝑣 𝑗 waiting in the pool at time 𝑡. The action at time 𝑡 is an index 𝑎𝑡 ∈ {1, . . . , 𝑛}, corresponding to a value threshold 𝑣 𝑎𝑡 ∈ V. All transactions with value at least 𝑣 𝑎𝑡 are eligible to be scheduled on block 𝑡. Let F be a scheduling protocol that is determined at the beginning and fixed throughout the process, such that for any state S and action 𝑎, F (S, 𝑎) determines how the eligible transactions at that state (i.e., those whose value exceeds 𝑣 𝑎 ) are packed into a block of size at most 2𝐵. Accordingly, F (S, 𝑎) can be represented as an (𝑚, 𝑛)-dimensional matrix, where the (𝑖, 𝑗)th entry, denoted by F (S, 𝑎) [𝑖, 𝑗], specifies the number of transactions of size 𝑞𝑖 and value 𝑣 𝑗 scheduled into the block F under state S and action 𝑎. Given the scheduling protocol F , we let 𝑄 sched (S, 𝑎) denote the total size of transactions scheduled under state S and action 𝑎 when following protocol F , i.e., 𝑚 𝑛 ∑︁ ∑︁ F 𝑄 sched (S, 𝑎) = 𝑞𝑖 F (S, 𝑎) [𝑖, 𝑗]. 𝑖=1

𝑗=1

Remark 5. While F may take a general form, for concreteness we adopt in this work the following natural choice, which follows a bang-per-buck packing rule up to some threshold 𝜏.4 Specifically, given a state–action pair (S, 𝑎), the protocol first sorts all eligible transactions in state S in ascending order of the product of their value and size, i.e., 𝑣 · 𝑞, and then packs them into the block until a maximum capacity threshold 𝜏 ≤ 2𝐵 is reached. To ensure that the state space remains finite, whenever S[𝑖, 𝑗] > 𝐿 for some (𝑖, 𝑗), the protocol first schedules transactions from S[𝑖, 𝑗] until it is reduced to 𝐿. Any remaining block capacity is then allocated according to the original sorting rule. Let A𝑡 be a stationary stochastic arrival matrix, where A𝑡 [𝑖, 𝑗] is a random variable denoting the number of new transactions of size 𝑞𝑖 and value 𝑣 𝑗 that arrive in the system at time 𝑡. The state evolution of the system is then governed by the following dynamics: S𝑡 +1 = S𝑡 + A𝑡 − F (S𝑡 , 𝑎𝑡 ),

(8)

and the state transition probability function is defined accordingly as: 𝑃 (S𝑡 +1 |S𝑡 , 𝑎𝑡 , F ) = P(A𝑡 = S𝑡 +1 − S𝑡 + F (S𝑡 , 𝑎𝑡 )).

(9)

Since the scheduling protocol F is assumed to be fixed, we can suppress it in the notation and write the transition probability as 𝑃 (S𝑡 +1 | S𝑡 , 𝑎𝑡 ). After the transition occurs, the reward received is  + F (10) 𝑟 (S𝑡 , 𝑎𝑡 ) = −𝑐 hold𝑄 𝑡pool − 𝑐 over 𝑄 sched (S𝑡 , 𝑎𝑡 ) − 𝐵 , where (·) + = max{0, ·}, and 𝑄 𝑡pool is the total size of transactions in the pool at time 𝑡, defined as 𝑄 𝑡pool =

𝑚 ∑︁ 𝑖=1

𝑞𝑖

𝑛 ∑︁

S𝑡 [𝑖, 𝑗].

𝑗=1

3We refer to Section 5 for an equivalent simplified version of this model in the case of homogeneous transactions. 4 In fact, we will show in Section 5 that this class of scheduling protocols is optimal in the case of homogeneous transactions.

Fatemeh Fardno and S. Rasoul Etesami

9

The parameter 𝑐 hold denotes the holding cost incurred by transactions that remain in the pool, whereas 𝑐 over represents the penalty for scheduling transactions in excess of the target block size 𝐵. Finally, our goal is to maximize the total expected discounted revenue, defined as5 𝑉 𝜋 (S0 ) = E𝜋 [

∞ ∑︁

𝛾 𝑡 𝑟 (S𝑡 , 𝑎𝑡 )],

𝑡 =1

where 𝜋 is the stationary policy followed by the mechanism, mapping each state to a probability distribution over actions, and 𝛾 ∈ (0, 1) is the discount factor. We further assume that the initial state S0 is the all-zero matrix, indicating that the pool is initially empty. Remark 6. For stationary transaction arrivals, finding the optimal policy is equivalent to solving a finite-state, finite-action MDP, for which the existence of a deterministic stationary optimal policy is well established [Abbasi Yadkori et al., 2013]. Therefore, in the remainder of the paper, without loss of generality, we restrict our analysis to the class of stationary deterministic policies, i.e., mappings 𝜋 : S → A that assign a single action to each state independently of the time step 𝑡. Remark 7. The structure of the reward function (10) induces different scheduling priorities depending on the relative magnitudes of the holding cost 𝑐 hold and the overshoot penalty 𝑐 over . When 𝑐 hold ≫ 𝑐 over , maximizing the reward favors scheduling all incoming transactions as quickly as possible, keeping the mempool nearly empty even at the expense of exceeding the target block size. In contrast, when 𝑐 hold ≪ 𝑐 over , the optimal policy emphasizes adhering to the target block capacity 𝐵, potentially allowing the mempool to become crowded in order to avoid overshoot penalties. Remark 8. Let 𝑄 𝑡arrival denote the total size of transactions arriving at time 𝑡. If 𝑄 𝑡arrival > 2𝐵 for all 𝑡, it becomes impossible to schedule all arriving transactions, and the system will eventually become unstable. Accordingly, in the stochastic arrival setting, we assume that 𝑄 𝑡arrival is a random variable taking values in the range [0, 2𝐵]. In the deterministic setting, we assume 𝐵 < 𝑄 arrival ≤ 2𝐵, since if 𝑄 arrival ≤ 𝐵, all transactions can be scheduled within a single block, making the problem trivial. In our formulation, we assume that the protocol has complete information about the number of transactions of each type in the mempool. However, we note that our framework can be extended to settings in which the protocol has only partial observations of the mempool, thanks to the extension of MDPs to partially observable Markov decision processes (POMDPs). For instance, if the protocol can observe only the history of included transactions, rather than the entire mempool, it can use the history of scheduled transactions to form and update a belief distribution over the mempool (state), which becomes more accurate over time. In this case, the system can be modeled as a POMDP with belief states rather than an MDP with fully observable states, and existing results [Anjarlekar et al., 2026] can be used to reduce it to an MDP with a small error in the optimal policy evaluation. In our setting, however, as an initial model and to keep the derivations simple, we assume full information and that the distribution of transactions in the mempool is known. 4

An Online Revenue Maximizing Algorithm for the Dynamic Scheduling Problem

In this section, we provide an online algorithm for obtaining the optimal policy that maximizes the long-run discounted average reward under the given state dynamics while ensuring that all arriving transactions are eventually scheduled. 5We note that, unlike the original EIP-1559 formulation, we are not maximizing social welfare, but rather the total revenue.

Fatemeh Fardno and S. Rasoul Etesami

10

Recall that the long-run discounted average reward of a policy 𝜋, starting from the initial state S0 , is defined as # "∞ ∑︁ 𝑡 𝜋 𝛾 𝑟 (S𝑡 , 𝑎𝑡 ) | S0 . 𝑉 (S0 ) = E𝜋 𝑡 =1

To maximize the revenue in the dynamic scheduling problem in an online fashion, we employ the Natural Policy Gradient (NPG) algorithm [Even-Dar et al., 2009], adapted to our setting. The NPG algorithm defines a Fisher information matrix and performs gradient updates in the geometry induced by this matrix as follows: 
⊤ 𝐹 𝜌 (𝜃 ) = E𝑠∼𝜈𝜌𝜋𝜃 E𝑎∼𝜋𝜃 (· |𝑠 ) ∇𝜃 log 𝜋𝜃 (𝑎 | 𝑠) ∇𝜃 log 𝜋𝜃 (𝑎 | 𝑠) , (11) 𝜃 (𝑡 +1) = 𝜃 (𝑡 ) + 𝜂 𝐹 𝜌 (𝜃 (𝑡 ) ) † ∇𝜃 𝑉 (𝑡 ) (𝜌), where {𝜋𝜃 | 𝜃 ∈ Θ} is the class of stationary policies parametrized by 𝜃 , 𝜂 is the learning rate, 𝜌 is the initial state distribution, and 𝜈 𝜌𝜋𝜃 is the state visitation distribution under policy 𝜋𝜃 and 𝜌. We use softmax parametrization, where for unconstrained 𝜃 ∈ R | S | | A | , the policy is parametrized as
exp 𝜃 S,𝑎
. 𝜋𝜃 (𝑎 | S) = Í (12) 𝑎 ′ ∈ A exp 𝜃 S,𝑎 ′ Next, we state the following lemma from [Even-Dar et al., 2009, Lemma 15], which provides a performance guarantee for the convergence of the NPG algorithm to an approximately optimal stationary policy. Lemma 2. For the softmax parameterization (12), the NPG updates in (11) take the form 𝜂 𝜃 (𝑡 +1) = 𝜃 (𝑡 ) + 𝐴 (𝑡 ) , 1 −𝛾
exp 𝜂𝐴 (𝑡 ) (𝑠, 𝑎)/(1 − 𝛾) (𝑡 +1) (𝑡 ) 𝜋 (𝑎 | 𝑠) = 𝜋 (𝑎 | 𝑠) , 𝑍𝑡 (𝑠) (𝑡 )

(𝑡 )

where 𝐴 (𝑡 ) (𝑠, 𝑎) := 𝑄 𝜋 (𝑠, 𝑎) − 𝑉 𝜋 (𝑠) is the advantage function for policy 𝜋 (𝑡 ) , and   ∑︁ 𝑍𝑡 (𝑠) = 𝜋 (𝑡 ) (𝑎 | 𝑠) exp 𝜂𝐴 (𝑡 ) (𝑠, 𝑎)/(1 − 𝛾) . 𝑎∈ A

In particular, by setting 𝜂 ≥ (1 − 𝛾) 2 log |A|,

(13)

the NPG finds an 𝜖-optimal policy in at most 𝑇 ≤ (1−𝛾2 ) 2𝜖 iterations. In order to obtain more accurate estimates of the advantage function, we employ an episodic NPG, detailed in Algorithm 2. 4.1

EIP-1559 as a Special Case of a Natural Policy Gradient Algorithm

As discussed earlier, the EIP-1559 mechanism does not account for the dynamic evolution of the transaction mempool in its price update rule. We therefore examine whether the static version of Algorithm 2 has an update rule analogous to that of EIP-1559. Suppose the mempool is sufficiently congested that additions or removals of transactions do not affect the state; that is, the system reaches a stationary state S𝑡 = S for all 𝑡, thus resembling a stateless, static setting. Under this assumption, the 𝑄-function under policy 𝜋 can be written as 𝑄 𝜋 (S, 𝑎) = 𝑟 (S, 𝑎) + 𝛾𝑉 𝜋 (S).

Fatemeh Fardno and S. Rasoul Etesami

11

Algorithm 2 Episodic NPG for Dynamic Pricing of the Ethereum Mempool Input: transaction size set Q ={𝑞 1, . . . , 𝑞𝑚 }, value per size set V ={𝑣 1, . . . , 𝑣𝑛 }, target block size 𝐵, scheduling protocol F , learning rate 𝜂, discount factor 𝛾, horizon 𝐻 , number of iterations 𝑇 . Initialize: environment E, initial state S0 ← Reset(E), initial policy 𝜋 (0) (· | S0 ) over 𝑛 actions. for iteration 𝑘 = 0 to 𝑇 − 1 do Initialize episode buffer B𝑘 ← ∅. Set S0(𝑘 ) ← Reset(E). for 𝑡 = 0 to 𝐻 − 1 do Sample 𝑎𝑡(𝑘 ) ∼ 𝜋 (𝑘 ) (· | S𝑡(𝑘 ) ). Apply the scheduling protocol F to obtain F (S𝑡 , 𝑎𝑡 ) ∈ Z𝑚×𝑛 , where the (𝑖, 𝑗)-th element + denotes the number of transactions scheduled with size 𝑞𝑖 and value per size 𝑣 𝑗 . Calculate the reward 𝑟𝑡𝑘 using Eq. (10). Calculate the next state S𝑡(𝑘+1) using Eq. (8). Step environment: (𝑟𝑡(𝑘 ) , S𝑡(𝑘+1) ) ← Step(E, 𝑎𝑡(𝑘 ) ). Store transition: B𝑘 ← B𝑘 ∪ {(S𝑡(𝑘 ) , 𝑎𝑡(𝑘 ) , 𝑟𝑡(𝑘 ) , S𝑡(𝑘+1) )}. end for b𝑘 (S, 𝑎) using the collected trajectory. Compute advantage estimates 𝐴 for each state S for which (S, ·) appears in B𝑘 do Compute the normalization constant:   b Í 𝜂𝐴𝑘 (S,𝑎 ′ ) 𝑍 S,𝑘 ← 𝑎′ 𝜋 (𝑘 ) (𝑎 ′ | S) exp . 1−𝛾 for each action 𝑎 ∈ {1, . . . , 𝑛} do Update:   𝜋 (𝑘+1) (𝑎 | S) =

𝜋 (𝑘 ) (𝑎 |S) exp

b (S,𝑎) 𝜂𝐴 𝑘 1−𝛾

𝑍 S,𝑘

.

end for end for end for

We can write the value functions as 𝑉 𝜋 (S) = E𝑎∼𝜋 (· |S) [𝑄 𝜋 (S, 𝑎)] = E𝑎∼𝜋 (· |S) [𝑟 (S, 𝑎) + 𝛾𝑉 𝜋 (S)] , which implies (1 − 𝛾) 𝑉 𝜋 (S) = E𝑎∼𝜋 (· |S) [𝑟 (S, 𝑎)] . The advantage function is defined as 𝐴𝜋 (S, 𝑎) = 𝑄 𝜋 (S, 𝑎) − 𝑉 𝜋 (S). Substituting the expressions above yields, 𝐴𝜋 (S, 𝑎) = 𝑟 (S, 𝑎) + 𝛾𝑉 𝜋 (S) − 𝑉 𝜋 (S) = 𝑟 (S, 𝑎) − (1 − 𝛾)𝑉 𝜋 (S) = 𝑟 (S, 𝑎) − E𝑎′ ∼𝜋 (· |S) [𝑟 (S, 𝑎 ′ )] .

(14)

By setting the holding cost 𝑐 hold = 0 in the reward function (10), and by substituting the advantage

Fatemeh Fardno and S. Rasoul Etesami

function in Eq. (14) in the policy update in Algorithm 2, we get   b 𝜂𝐴𝑘 (S,𝑎) 𝜋 (𝑡 ) (𝑎 | S) exp 1−𝛾 𝜋 (𝑡 +1) (𝑎 | S) = Í   b ˆ (𝑡 ) (𝑎ˆ | S) exp 𝜂𝐴𝑘 (S,𝑎) 𝑎ˆ 𝜋 1−𝛾   𝜂 (𝑟 (S,𝑎) −E𝑎 ′ ∼𝜋 [𝑟 (S,𝑎 ′ ) ] ) (𝑡 ) 𝜋 (𝑎 | S) exp 1−𝛾   ≃Í ˆ −E𝑎 ′ ∼𝜋 [𝑟 (S,𝑎 ′ ) ] ) (𝑡 ) (𝑎ˆ | S) exp 𝜂 (𝑟 (S,𝑎) 𝑎ˆ 𝜋 1−𝛾   𝜂𝑟 (S,𝑎) (𝑡 ) 𝜋 (𝑎 | S) exp 1−𝛾   =Í ˆ (𝑡 ) (𝑎ˆ | S) exp 𝜂𝑟 (S,𝑎) 𝑎ˆ 𝜋 1−𝛾   𝜂𝑟 (S, 𝑎) ∝ 𝜋 (𝑡 ) (𝑎 | S) exp 1 −𝛾  + ! F −𝜂𝑐 over 𝑄 sched (S, 𝑎) − 𝐵 = 𝜋 (𝑡 ) (𝑎 | S) exp , 1 −𝛾

12

(15)

which closely coincides with the EIP-1559 price update rule (3). In the next section, we show that when 𝑐 over ≫ 𝑐 hold , the average amount of scheduled transactions converges to the target block capacity 𝐵, consistent with the results shown for EIP-1559 [Babaioff and Nisan, 2024]. 4.2

Numerical Results

In this section, we present numerical results to evaluate the performance of Algorithm 2 under various settings of the dynamic transaction scheduling problem. In our simulations, we consider different choices of parameters for transaction sizes, values per size, target block capacity 𝐵, the overshoot penalty 𝑐 over , and the holding cost 𝑐 hold . Throughout this section, we run the algorithm for a total of 10,000 iterations, where each iteration corresponds to an episode of length 𝐻 = 400. The discount factor is set to 𝛾 = 0.95, and the learning rate is tuned for each setting while ensuring that the condition in Eq. (13) is satisfied. For the following experiments, we also assume uniform deterministic arrivals, i.e., exactly one transaction of each type arrives in the system at each timestep. For the first set of experiments (Setting 1), we fix the holding cost at 𝑐 hold = 1 and vary the overshoot penalty over the set 𝑐 over ∈ {0, 1, 10, 30, 50, 70, 100, 150}. As an example, Fig. 1 illustrates Setting 1, which considers transactions with sizes Q = {2, 4, 5, 7} and per-unit values V = {2, 4, 9}. The figure reports the average scheduled transaction volume as a function of the overshoot penalty for three different target block capacities 𝐵. A key observation is that as 𝑐 over increases, the average volume of scheduled transactions converges toward the target block capacity, consistent with the behavior observed under EIP-1559. We now conduct a set of experiments (Setting 2) in which 𝑐 hold and 𝑐 over are fixed, while the target block capacity is varied over the range 𝐵 ∈ {28, 30, 32, 33, 35, 38, 40, 42, 45}. For Setting 2, the total arrival size is 54, so we vary 𝐵 from 54/2 up to values close to the total arrival size. The corresponding results are shown in Fig. 2. When the gap between 𝑐 hold and 𝑐 over is small, the scheduling algorithm admits nearly all incoming transactions. This behavior is illustrated in Fig. 2a, which corresponds to the parameter setting

13

Fatemeh Fardno and S. Rasoul Etesami

(a) 𝐵 = 30

(b) 𝐵 = 35

(c) 𝐵 = 40

Fig. 1. Average scheduled transaction volume as a function of the overshoot penalty for Setting 1.

(a) 𝑐 hold = 1, 𝑐 over = 8

(b) 𝑐 hold = 1, 𝑐 over = 35

(c) 𝑐 hold = 1, 𝑐 over = 40

Fig. 2. Average scheduled transaction volume as a function of the target block capacity for Setting 1.

𝑐 hold = 1 and 𝑐 over = 8. In this case, only a slight decrease in the amount of scheduled transactions is observed when the block capacity 𝐵 drops below the threshold specified in Lemma 8. By contrast, as the gap between 𝑐 hold and 𝑐 over increases, the degradation in scheduling performance becomes more pronounced. This is illustrated in Fig. 2b, which corresponds to 𝑐 hold = 1 and 𝑐 over = 35. A similar trend is observed in Fig. 2c, where the overshoot penalty is further increased to 𝑐 over = 40. 4.2.1 Stochastic Arrival Process. Here, we extend our simulation results to stochastic arrivals, assuming that transactions enter the pool according to a stationary random process. Let 𝐴[𝑖, 𝑗] ∼ Poisson(𝜇𝑖 ) denote the number of arriving transactions of size 𝑞𝑖 and value 𝑣 𝑗 in a single time step. The total arrival size in one time step is then given by 𝑄 arr :=

𝑚 ∑︁ 𝑛 ∑︁

(16)

𝑞𝑖 𝐴[𝑖, 𝑗].

𝑖=1 𝑗=1 2𝐵 Letting 𝜇𝑖 = 𝑚𝑛𝑞 , the expected total arrival size is 𝑖

E [𝑄 arr ] =

𝑚 ∑︁ 𝑛 ∑︁ 𝑖=1 𝑗=1

𝑞𝑖 E [𝐴[𝑖, 𝑗]] =

𝑚 ∑︁ 𝑛 ∑︁ 𝑖=1 𝑗=1

𝑞 𝑖 𝜇𝑖 =

𝑚 ∑︁ 𝑖=1

 𝑛𝑞𝑖

 ∑︁ 𝑚 2𝐵 2𝐵 𝜆 = 𝜆 = 2𝐵𝜆. 𝑚𝑛𝑞𝑖 𝑚 𝑖=1

(17)

Therefore, to avoid the trivial case, we choose 𝜆 ∈ (0.5, 1), which ensures that the expected total arrival size exceeds the target block size 𝐵 while remaining below the hard block capacity 2𝐵. For stochastic arrivals, we consider a simple setting, referred to as Setting 3, with Q = {2, 4} and V = {4, 9}. We increase the episode length to 1000 time steps and set the arrival rate to 𝜆 = 0.6.

14

Fatemeh Fardno and S. Rasoul Etesami

(a) 𝐵 = 7

(b) 𝐵 = 10

(c) 𝐵 = 15

Fig. 3. Average scheduled transaction volume as a function of the overshoot penalty in Setting 3 under stochastic arrivals with 𝜆 = 0.6.

We plot the average amount of scheduled transactions by fixing 𝑐 hold = 1 and varying 𝑐 over ∈ {0, 1, 10, 30, 50, 70, 100, 150} for three different target block capacities, as shown in Fig. 3. Unlike the deterministic arrival case, here we can vary the target block size 𝐵 over a wide range without being constrained by a fixed number of arrivals. This is because the Poisson arrival rate is chosen such that the expected total arrival size at each time step is 2𝐵𝜆, which lies between 𝐵 and 2𝐵. As shown in Fig. 3, for small overshoot costs, the average scheduled transaction volume closely matches the average incoming transaction volume, which varies across different target block capacities 𝐵. As the overshoot cost increases, the average scheduled volume decreases and converges to a level below 𝐵, reflecting the policy’s attempt to avoid overshoot penalties. 5

Optimality of Threshold Policies for Homogeneous Dynamic Scheduling Problem

While the NPG Algorithm 2 provides an efficient method to obtain an optimal policy for the dynamic scheduling problem, the structure of the optimal policy can be quite complex and depend on many parameters involved in the problem. However, it turns out that by restricting the problem to certain special cases, one can obtain a closed-form characterization of the optimal scheduling policy, which provides useful insights into the behavior of the optimal policy in general. Therefore, in this section we consider a special case of the MDP introduced in Section 3, in which all transactions are homogeneous, i.e., they have the same value and size. In this setting, pricing becomes irrelevant, since no transaction is preferred over another. As a result, the homogeneous dynamic scheduling problem reduces to an equivalent formulation in which the protocol directly controls the total volume of scheduled transactions through the scheduling protocol F , as described in detail below. 5.1

Reformulation of the Dynamic Scheduling Problem under Homogeneous Arrivals

Let 𝑠𝑡 denote the state of the system at time 𝑡, represented by a scalar quantity corresponding to the total size of transactions in the mempool at time 𝑡. Let 𝐴𝑡 denote the total size of transactions arriving at time 𝑡, where {𝐴𝑡 } ∼ 𝐴 is an i.i.d. process with 𝐴 ∈ [0, 2𝐵]. Since setting a price action 𝑎𝑡 either makes all transactions eligible or ineligible (depending on whether 𝑣 𝑎𝑡 is smaller or larger than the common transaction value 𝑣, respectively), the scheduler should clearly set a low price to ensure that all transactions are eligible; otherwise, no transactions can be scheduled. In this case, the only remaining degree of freedom for the scheduler is the choice of scheduling protocol F .6 6 Note that in Section 3, we fixed the scheduling protocol F to the one described in Remark 5. Here, we show that this

structure is indeed optimal in the homogeneous setting.

Fatemeh Fardno and S. Rasoul Etesami

15

In order to characterize the optimal scheduling protocol in the homogeneous setting, let us define the action 𝑓𝑡 as the amount of overshoot above the target capacity 𝐵 scheduled at time 𝑡. By feasibility constraints, it must hold that7 −𝐵 ≤ 𝑓𝑡 ≤ min{𝑠𝑡 , 2𝐵} − 𝐵. The state then evolves as 𝑠𝑡 +1 = 𝑠𝑡 + 𝐴𝑡 − (𝑓𝑡 + 𝐵) . The instantaneous cost at time 𝑡 is given by 𝑐 (𝑠𝑡 , 𝑓𝑡 ) = 𝑐 hold𝑠𝑡 + 𝑐 over (𝑓𝑡 ) +, which is the negative of the instantaneous reward function defined in Eq. (10). Note that this cost is bounded since we have imposed a cap of 𝐿 on the state, i.e., there exists 𝐿 > 0 such that 𝑠𝑡 ≤ 𝐿 ∀𝑡. For the remainder of this section, we assume that 𝑐 over > 𝑐 hold , as the analysis for the other case is similar (see Remark 9 below). As before, we consider the infinite horizon discounted cost setting, i.e.,  𝐽 (𝑠) = 𝑐 hold𝑠 + min 𝑐 over (𝑓 ) + + 𝛾E[𝐽 (𝑠 ′ )] , (18) −𝐵 ≤ 𝑓 ≤min{𝑠,2𝐵 } −𝐵

where 𝑠 ′ = 𝑠 + 𝐴 − (𝑓 + 𝐵), and the expectation is taken over random arrivals 𝐴. Now, if we define 𝑄 (𝑠, 𝑓 ) = 𝑐 hold𝑠 + 𝑐 over (𝑓 ) + + 𝛾E[𝐽 (𝑠 ′ )], we can rewrite (18) equivalently as 𝐽 (𝑠) = 5.2

min

[𝑄 (𝑠, 𝑓 )] .

−𝐵 ≤ 𝑓 ≤min{𝑠,2𝐵 }−𝐵

(19)

Characterization of the Optimal Scheduling Policy

In order to characterize the structure of the optimal scheduling protocol for the homogeneous dynamic scheduling problem described above, we apply a value iteration method to compute the optimal cost function 𝐽 ∗ (·). To that end, let 𝐽0 (𝑠) = 𝑐 term𝑠 ∀𝑠. The value iteration update equals  𝐽𝑘+1 (𝑠) = 𝑐 hold𝑠 + min 𝑐 over (𝑓 ) + + 𝛾E [𝐽𝑘 (𝑠 ′ )] , (20) −𝐵 ≤ 𝑓 ≤min{𝑠,2𝐵 } −𝐵

which is iterated until convergence to the fixed point. Since the instantaneous cost is bounded and 𝛾 ∈ (0, 1), value iteration converges to the optimal cost function [Bertsekas, 2012], i.e., 𝐽 ∗ (𝑠) = lim 𝐽𝑘 (𝑠). 𝑘→∞

Next, we establish the following two properties of the optimal cost function. The proof of these lemmas are deferred to appendices B.3 and B.2, respectively. Lemma 3. 𝐽 ∗ (·) is a convex function. Moreover, if we let 𝐽 ∗ (𝑠) = min−𝐵 ≤ 𝑓 ≤min{𝑠,2𝐵 }−𝐵 [𝑄 ∗ (𝑠, 𝑓 )], then for any 𝑠 ≥ 0, the function 𝑄 ∗ (𝑠, ·) is convex in its second argument. Lemma 4. 𝐽 ∗ is non-decreasing. Finally, by combining Lemmas 3 and 4, we show that the optimal policy is a threshold policy. Theorem 5. There exists a threshold 𝑠 ∗ ≥ 𝐵 such that the optimal policy 𝑓 ∗ is given by    min{𝑠 − 𝐵, 0}, 0 ≤ 𝑠 ≤ 𝑠 ∗,  ∗ 𝑓 (𝑠) =   min{𝑠 − 𝑠 ∗, 𝐵}, 𝑠 > 𝑠 ∗ . 

7 For simplicity of the analysis, we assume that 𝑓 can take fractional values, which is realistic and becomes more accurate 𝑡

when transaction sizes are much smaller than the target block capacity 𝐵.

16

Fatemeh Fardno and S. Rasoul Etesami

Proof. Define 𝑦 := 𝑠 − (𝑓 + 𝐵) to be the pool size after the scheduling happens. We can therefore rewrite Eq. (18) for the optimal cost function 𝐽 ∗ as 𝐽 ∗ (𝑠) = 𝑐 hold𝑠 +

min

max{0,𝑠 −2𝐵 } ≤𝑦 ≤𝑠

{𝑐 over (𝑠 − 𝑦 − 𝐵) + + 𝛾E[𝐽 ∗ (𝑦 + 𝐴)]}.

Let 𝑔(𝑦) := 𝛾E[𝐽 ∗ (𝑦 + 𝐴)]. Since 𝐽 ∗ is convex and non-decreasing by Lemmas 3 and 4, it follows that 𝑔 is also convex and non-decreasing. Thus, we have 𝐽 ∗ (𝑠) = =

min

{𝑐 hold𝑠 + 𝑐 over (𝑠 − 𝑦 − 𝐵) + + 𝑔(𝑦)}

min

[𝑄 ∗ (𝑠, 𝑦)],

max{0,𝑠 −2𝐵 } ≤𝑦 ≤𝑠 max{0,𝑠 −2𝐵 } ≤𝑦 ≤𝑠

which, in view of Lemma 3, shows that 𝑄 ∗ (𝑠, 𝑦) is convex in 𝑦 for any 𝑠. Now we have three cases: • 𝑠 ≤ 𝐵: In this case, we have 𝐽 ∗ (𝑠) = 𝑐 hold𝑠 + min0≤𝑦 ≤𝑠 {𝑔(𝑦)}, and since 𝑔 is non-decreasing, the optimal solution is attained at 𝑦 ∗ (𝑠) = 0, and thus 𝑓 ∗ (𝑠) = 𝑠 − 𝐵. • 𝐵 < 𝑠 ≤ 𝑦 + 𝐵: In this case even though 𝑠 > 𝐵, but no overshoot happens. Therefore 𝑦 ∗ (𝑠) + 𝐵 = 𝑠 and 𝑓 ∗ (𝑠) = 0. • 𝑦 + 𝐵 ≤ 𝑠: In this case, we have 𝑄 ∗ (𝑠, 𝑦) = 𝑐 hold𝑠 + 𝑐 over (𝑠 − 𝐵) + (𝑔(𝑦) − 𝑐 over𝑦) and therefore 𝐽 ∗ (𝑠) = 𝑐 hold𝑠 + 𝑐 over (𝑠 − 𝐵) +

min

max{0,𝑠 −2𝐵 } ≤𝑦 ≤𝑠 −𝐵

[𝑔(𝑦) − 𝑐 over𝑦].

Since 𝑔 is convex, 𝑔(𝑦) − 𝑐 over𝑦 is also convex. Suppose 𝑥 ∗ = arg min𝑦 ∈ [0,∞) {𝑔(𝑦) − 𝑐 over𝑦}. If 𝑥 ∗ ∈ [max{0, 𝑠 − 2𝐵}, 𝑠 − 𝐵], then 𝑦 ∗ (𝑠) = 𝑥 ∗ . If 𝑥 ∗ > 𝑠 − 𝐵, then 𝑦 ∗ (𝑠) = 𝑠 − 𝐵, and if 𝑥 ∗ < max{0, 𝑠 − 2𝐵}, then 𝑦 ∗ (𝑠) = max{0, 𝑠 − 2𝐵}. In the case of 𝑔(𝑦) − 𝑐 over𝑦 not having a minimizer on [0, ∞), the minimum happens at one of the two ends points of the interval and we have 𝑥 ∗ = 𝑦 ∗ (𝑠) = arg min𝑦 ∈ {max{0,𝑠 −2𝐵 },𝑠 −𝐵 } {𝑔(𝑦) − 𝑐 over𝑦}. Thus, in any case, 𝑦 ∗ (𝑠) is the projection of 𝑥 ∗ to the interval [max{0, 𝑠 − 2𝐵}, 𝑠 − 𝐵], which can be written explicitly as 𝑦 ∗ (𝑠) = min{max{𝑥 ∗, max{0, 𝑠 − 2𝐵}}, 𝑠 − 𝐵}. Subsequently, 𝑓 ∗ (𝑠) = 𝑠 − 𝑦 ∗ (𝑠) − 𝐵, and we have 𝑓 ∗ (𝑠) = 𝑠 − min{max{𝑥 ∗, max{0, 𝑠 − 2𝐵}}, 𝑠 − 𝐵} − 𝐵 = max{𝑠 − 𝐵 − max{𝑥 ∗, max{0, 𝑠 − 2𝐵}}, 0} = max{min{𝑠 − 𝐵 − 𝑥 ∗, min{𝑠 − 𝐵, 𝐵}}, 0} = min{max{𝑠 − (𝐵 + 𝑥 ∗ ), 0}, 𝐵}.

(21)

Note that 𝑓 ∗ (𝑠) ≥ 0, which guarantees that 𝑦 ∗ (𝑠) + 𝐵 ≤ 𝑠. Thus, if we define 𝑠 ∗ = 𝐵 + 𝑥 ∗ ≥ 𝐵, then for 𝑠 > 𝑠 ∗ , using (21), we have 𝑓 ∗ (𝑠) = min{𝑠 − 𝑠 ∗, 𝐵}. Moreover, if 𝑠 ≤ 𝑠 ∗ , then 𝑓 ∗ (𝑠) = 0, which corresponds to the boundary case 𝑦 ∗ (𝑠) + 𝐵 = 𝑠. This boundary is shared by the second and third cases, with no overshoot. Finally, by summarizing all the above cases, we conclude that there exists an 𝑠 ∗ ≥ 𝐵 such that ∗    min{𝑠, 𝐵} − 𝐵 𝑠 ≤ 𝑠  𝑓 (𝑠) =   min{𝑠 − 𝑠 ∗, 𝐵} 𝑠 ∗ < 𝑠.  ∗

□ Remark 9. Using similar reasoning, one can show that when 𝑐 over ≤ 𝑐 hold , the optimal policy is to schedule as many transactions as possible up to the hard capacity 2𝐵. That is, 𝑓 ∗ (𝑠) = min{𝑠 − 𝐵, 𝐵}.

Fatemeh Fardno and S. Rasoul Etesami

17

The results in this section imply that, as long as the pool congestion remains below a certain threshold, the optimal policy schedules as little as possible. In our setting, this corresponds to scheduling 𝐵 units of transactions, or all available transactions if the pool contains fewer than 𝐵 units. Consequently, the pool congestion increases over time until it reaches a threshold 𝑠 ∗ ≥ 𝐵. Once the congestion exceeds 𝑠 ∗ , the policy schedules more than 𝐵 units, with the scheduled amount increasing linearly with the congestion level. This reduces the pool congestion, eventually bringing it back below 𝑠 ∗ , after which the process repeats. 6

Block Capacity Lower Bounds under Bang–Bang Pricing with Uniform Arrivals

In this section, we study another special case of the dynamic scheduling problem introduced in Section 3, where arrivals are uniform, meaning that at each time step 𝑡, exactly one transaction of each type arrives.8 Here, instead of characterizing the structure of the optimal policy, we are interested in obtaining a lower bound on the target block capacity that ensures stability of the system under a simple pricing rule, namely bang-bang pricing policies (Definition 6). The motivation for considering such bang-bang policies is inspired by our analysis in Section 5, which suggests that under reasonably homogeneous transaction dynamics, if the scheduler aims to use a simple threshold-based pricing mechanism to control the mempool, it should set a high price to schedule as few transactions as possible while the pool congestion remains below the threshold. As congestion increases and reaches the threshold, the scheduler must lower prices to their minimum value to schedule more transactions and bring congestion back toward the threshold. Moreover, our analysis in this section is particularly useful from a managerial perspective, where the scheduler seeks simple and interpretable pricing policies to control mempool congestion. In particular, it helps determine a minimum target block capacity that ensures even a simple bang–bang policy can schedule all incoming transactions while keeping the average overshoot cost bounded. Definition 6 (Bang–Bang Pricing Mechanism). A bang–bang pricing mechanism is a pricing rule under which the posted price at each time step is restricted to the extreme values of the price range. Specifically, the mechanism satisfies 𝑝𝑡 ∈ {𝑝 min, 𝑝 max } ∀𝑡 ≥ 1. Before presenting the main result of this section, we introduce the following preliminaries. For simplicity, we work with the long-run average reward rather than the long-run discounted reward. However, the analysis extends naturally to the discounted setting as well. The long-run average reward of a policy 𝜋, starting from the initial state S0 , is defined as follows: " # 𝑇 1 ∑︁ 𝜋 𝑉 (S0 ) = E𝜋 lim 𝑟 (S𝑡 , 𝑎𝑡 ) | S0 𝑇 →∞ 𝑇 𝑡 =1 ∑︁ ∑︁ = 𝜌 𝜋 (S, 𝑎)𝑟 (S, 𝑎), 𝑎∈ A S∈ S

where 𝑇

1 ∑︁ P{S𝑡 = S, 𝑎𝑡 = 𝑎} 𝑇 →∞ 𝑇 𝑡 =0

𝜌 𝜋 (S, 𝑎) = lim

denotes the occupancy measure induced by policy 𝜋, representing the proportion of time that policy 𝜋 spends at the state-action pair (S, 𝑎). Therefore, the expected revenue maximization problem can 8 Note that although we assume uniform arrivals in this section, most of our derivations extend to the more general case of

stationary stochastic arrivals, with the bounds depending on the underlying distributions.

Fatemeh Fardno and S. Rasoul Etesami

18

be formulated as max s.t.

∑︁ ∑︁

𝜌 𝜋 (S, 𝑎)𝑟 (S, 𝑎)

(22)

𝑎∈ A S∈ S 𝜋

𝜌 (S, 𝑎) ∈ Δ.

where the reward function 𝑟 (·, ·) is defined in Eq. (10), and Δ denotes the polytope of feasible occupancy measures defined as follows [Altman, 2021]: ( ) ∑︁ ∑︁ ∑︁ Δ = 𝜌 ∈ [0, 1] | S× A | : 𝜌 (S, 𝑎) = 1, 𝜌 (S, 𝑎) = 𝑃 (S | S′, 𝑎 ′ )𝜌 (S′, 𝑎 ′ ) ∀S ∈ S . (23) S,𝑎

𝑎

S′ ,𝑎 ′

It is worth noting that the hard capacity constraint of each block is implicitly incorporated into the feasible polytope Δ defined in Eq. (23). Specifically, for the prescribed scheduling protocol F , the transition probability in (9) automatically enforces the block capacity constraint, which in turn restricts the set of feasible occupancy measures in (23). Thus, no additional capacity constraints are needed in the maximization problem (22). Remark 10. The primal optimization problem for the dynamic scheduling problem can be interpreted as finding an optimal stationary policy (the primal variables) that maximizes the expected revenue, i.e., the value function (the primal objective). Reformulating this problem in terms of occupancy measures (the dual variables) yields the dual program given in (22). As shown earlier, the price update rule under the Natural Policy Gradient algorithm—which can be thought as an exponential update rule for the occupancy measures—closely mirrors the dual update rule in the primal-dual analysis of the EIP-1559 mechanism. This correspondence provides a primal-dual extension of the earlier static EIP-1559 analysis to the dynamic setting. Definition 7. We define the average overshoot cost associated with a pricing mechanism that schedules 𝑄𝑡 transactions on block 𝑡 as 𝑇  1 ∑︁  E 𝑐 over (𝑄𝑡 − 𝐵) + . 𝑇 →∞ 𝑇 𝑡 =1

𝐶 over := lim Theorem 8. Let 𝑄 = that

(24)

Í𝑚

𝑖=1 𝑞𝑖 and |V | = 𝑛. Suppose that the target block capacity 𝐵 is chosen such

 √ 𝑄  3 + 8𝑛 2 − 16𝑛 + 9 ≤ 𝐵, 4 and that there exists a positive integer 𝑘 such that 9 2𝐵 − 𝑄 𝑄 (𝑛 − 1) ≤𝑘 ≤ . 𝐵 −𝑄 𝑄 (𝑛 − 1) Then there exists a bang–bang pricing mechanism that can schedule all incoming transactions and the average overshoot cost would be upper bounded by 𝐶 over ≤

𝐵𝑄 (𝑛 − 1) . 2𝐵 − 𝑄

Proof. Let 𝜋 denote a stationary deterministic policy. For each state S ∈ S and iteration 𝑡 = 1, 2, . . . , let 𝑥 S𝑡 be an indicator variable that equals 1 if the system is in state S at time step 𝑡, and 9 As shown in Remark 11, it is always possible to satisfy both of these conditions simultaneously.

Fatemeh Fardno and S. Rasoul Etesami

19

0 otherwise. Assuming a stationary arrival process where A𝑡 = A for all 𝑡 = 1, 2, . . . , the average eligible arrival rate to the system is given by: 𝑚 𝑛 ∑︁ ©∑︁ ª 𝜈 (S) ­ 𝑞𝑖 A[𝑖, 𝑗] ® . S∈ S « 𝑖=1 𝑗∼𝜋 (· |S) ¬

∑︁

where 𝜈 (S) := lim𝑇 →∞ 𝑇1 therefore satisfy

Í𝑇

𝑡 𝑡 =1 𝑥 S denotes the state visitation frequency. The block capacity 𝐵 should

𝑚 𝑛 ∑︁ ª ©∑︁ 𝜈 (S) ­ 𝑞𝑖 A[𝑖, 𝑗] ® ≤ 𝐵, S∈ S « 𝑖=1 𝑗∼𝜋 (· |S) ¬

∑︁

while also making sure that the systems remains stable. For the system to remain stable, the average rate of scheduled transactions must equal 𝑄 𝑡arrival , i.e., 𝑚 𝑛 ∑︁ ©∑︁ ª 𝜈 (S) ­ 𝑞𝑖 S[𝑖, 𝑗] ® = 𝑄 𝑡arrival . 𝑠∈S « 𝑖=1 𝑗∼𝜋 (· |S) ¬

∑︁

Using the definition of the occupancy measure 𝜌 (S, 𝑎) as the average proportion of time the system encounters the state-action pair (S, 𝑎) under policy 𝜋 [Altman, 2021, Qin and Etesami, 2023], i.e., 𝑇

1 ∑︁ P(S𝑡 = S, 𝑎𝑡 = 𝑎) 𝑇 →∞ 𝑇 𝑡 =0

𝜌 (S, 𝑎) = lim

= 𝜈 (S)𝜋 (𝑎|S),

(25)

we can formulate an optimization problem to determine the minimum block capacity required to accommodate all incoming transactions as below: ! 𝑚 𝑛 ∑︁ ∑︁ ∑︁ ∑︁ min 𝜌 (S, 𝑎) 𝑞𝑖 A[𝑖, 𝑗] (26) 𝑎∈ A S∈ S

s.t.

𝑗=𝑎

𝑖=1

𝜌 (S, 𝑎) ∈ Δ, ∑︁ ∑︁

𝜌 (S, 𝑎)

𝑎∈ A S∈ S

(27) 𝑚 ∑︁

𝑞𝑖

𝑛 ∑︁

! S[𝑖, 𝑗] = 𝑄 𝑡arrival .

(28)

𝑗=𝑎

𝑖=1

To further simplify the analysis, we assume that exactly one transaction of each type (𝑞𝑖 , 𝑣 𝑗 ) arrives at every time step. Under this assumption, the above optimization problem reduces to: min

∑︁ ∑︁

𝜌 (S, 𝑎) · (𝑛 − 𝑎 + 1) ·

𝑎∈ A S∈ S

s.t.

𝑚 ∑︁

𝑞𝑖

𝑖=1

𝜌 (S, 𝑎) ∈ Δ, ∑︁ ∑︁ 𝑎∈ A S∈ S

𝜌 (S, 𝑎)

𝑚 ∑︁ 𝑖=1

𝑞𝑖

𝑛 ∑︁ 𝑗=𝑎

! S[𝑖, 𝑗] = 𝑄 𝑡arrival .

Fatemeh Fardno and S. Rasoul Etesami

20

This objective function can be further simplified to: ∑︁ ∑︁ max 𝑎 · 𝜌 (S, 𝑎) 𝑎∈ A S∈ S

s.t.

𝜌 (S, 𝑎) ∈ Δ, ∑︁ ∑︁

𝜌 (S, 𝑎)

𝑎∈ A S∈ S

𝑚 ∑︁ 𝑖=1

𝑞𝑖

𝑛 ∑︁

! S[𝑖, 𝑗] = 𝑄 𝑡arrival .

𝑗=𝑎

Next, to obtain a lower bound for 𝐵, it is enough to construct a feasible solution following bang– bang mechanism to this optimization problem, whose objective value will serve as a lower bound for 𝐵. We do so by constructing a stationary deterministic policy 𝜋 and then defining a corresponding occupancy measure 𝜌 ∈ Δ induced by 𝜋. Fix an integer 𝑘 ≥ 1 and define the following state 𝑘 © 𝑘 ­ S (𝑘 ) := ­­ . ­ .. «𝑘

𝑘 𝑘 .. .

··· ··· .. .

𝑘

···

1 ª 1® .. ®® , .® 1¬

where S (0) is the state of all zeros. We consider the stationary deterministic policy 𝜋 following the bang–bang mechanism given by ( 1, if S = S (𝑘 ) , 𝜋 (S) := (29) 𝑛, otherwise. That is, the policy chooses the highest price 𝑎 = 𝑛 in all states except when the pool reaches S (𝑘 ) , at which point it posts the lowest price 𝑎 = 1 to make the pool less congested. Í Under our deterministic arrival assumption, each step adds a total size 𝑄 := 𝑚 𝑖=1 𝑞𝑖 to each value column. When 𝜋 (S) = 𝑛, only the top-value column is eligible; consequently, the first 𝑛 − 1 columns increase by +1 in every entry at each time step. Starting from the all-zero state, after 𝑘 consecutive steps of playing 𝑎 = 𝑛, the state becomes exactly S (𝑘 ) . At that point, the policy plays 𝑎 = 1, making all columns eligible. The total pool size at S (𝑘 ) equals 𝑚 ∑︁

𝑞𝑖 (𝑛 − 1)𝑘 + 1 = (𝑛 − 1)𝑘 + 1 𝑄.

𝑖=1

Thus, if
(𝑛 − 1)𝑘 + 1 𝑄 ≤ 2𝐵,

(30)

on the flush step, the scheduler can clear the entire pool. Hence, the system returns to the S (1) state and the cycle repeats, implying that all arriving transactions are eventually scheduled. Now fix the above stationary policy 𝜋 and consider the induced MDP with transition kernel 𝑃 (S′ | S, 𝜋 (S)). Note that by choosing the target block capacity sufficiently large, as in Eq. (30), the state evolution becomes periodic over a finite set of states, with each cycle closing by returning to the S (1) state. This periodic behavior is illustrated in Fig. 4. A direct result of the periodic state evolution described above is that the induced Markov chain visits each state in the cycle exactly once per period. Hence for S ∈ {S (0) , S (1) , . . . , S (𝑘 ) }, the induced state distribution can be written as 1 𝜈 (S) = , 𝑘

21

Fatemeh Fardno and S. Rasoul Etesami

𝑎 =1

S (1)

𝑎 =𝑛

S (2)

···

𝑎 =𝑛

S (𝑘 )

Fig. 4. Periodic state evolution induced by the policy defined in Eq. (29): 𝑘 steps with 𝑎 = 𝑛 followed by one flush step with 𝑎 = 1.

and 𝜈 (S) = 0 for all other S ∈ S not belonging to this cycle. Therefore, the occupancy measure defined in (25) corresponding to this policy is given by
1
1 𝜌 S (ℓ ) , 𝑛 = for ℓ = 1, . . . , 𝑘 − 1, 𝜌 S (𝑘 ) , 1 = , 𝑘 𝑘 and 𝜌 (S, 𝑎) = 0 otherwise. We can then verify that 𝜌 (S, 𝑎) ∈ Δ. Substituting the policy defined in Eq. (29) into the initial objective in Eq. (26), we get 𝑛 +𝑘 −1 · 𝑄 ≤ 𝐵, 𝑘 which then combined with inequality Eq. (30) gives us 𝑄 (𝑛 − 1) 2𝐵 − 𝑄 ≤𝑘 ≤ , 𝐵 −𝑄 𝑄 (𝑛 − 1)

(31)

Í where 𝑄 = 𝑚 𝑖=1 𝑞𝑖 . Note that the above statement should hold while making sure that 𝑘 remains an integer. Therefore we need to find the smallest 𝐵 such that 𝑄 (𝑛 − 1) 2𝐵 − 𝑄 ≤ , 𝐵 −𝑄 𝑄 (𝑛 − 1) which further simplifies to 0 ≤ 2𝐵 2 − 3𝐵𝑄 + 2𝑛𝑄 2 − 𝑄 2𝑛 2, and finally  √ 𝑛𝑄 𝑄  < 3 + 8𝑛 2 − 16𝑛 + 9 ≤ 𝐵. (32) 2 4 Thus, for all 𝐵 satisfying the above inequality, it is sufficient to find the smallest value of 𝐵 for which the range shown in Eq. (31) includes a positive integer 𝑘. Now that we have established a lower bound on the target block capacity, we want to derive an upper bound on the average overshoot cost defined in Eq. (24). Over a cycle of 𝑘 steps, exactly 𝑘 − 1 blocks are scheduled without incurring any overshoot cost. Consequently, the average overshoot cost over the cycle satisfies ((𝑛 − 1)𝑘 + 1)𝑄 − 𝐵 𝐶 over = . 𝑘 Using the result of Remark 8, we know 𝑛𝑄 2 ≤ 𝐵 < 𝑛𝑄, and since 𝑛 ≥ 2, we can conclude that 𝑄 ≤ 𝐵. Therefore, we can conclude that 𝐶 over is an increasing function of 𝑘. By substituting the upper bound on 𝑘 in Eq. (31) we get 𝐵𝑄 (𝑛 − 1) 𝐶 over ≤ . 2𝐵 − 𝑄 □

Fatemeh Fardno and S. Rasoul Etesami

22

Remark 11. Note that a positive integer 𝑘 satisfying (31) can always be found by increasing the block capacity 𝐵. In particular, if 𝐵 is increased by an amount 𝑥, the upper bound in (31) increases 2𝑥 by 𝑄 (𝑛−1) , while the lower bound decreases by 𝑥𝑄 (𝑛 − 1) . (𝐵 − 𝑄) (𝐵 + 𝑥 − 𝑄) As a result, the feasible interval for 𝑘 expands as 𝐵 increases, making it always possible to find a positive integer 𝑘 within this range by choosing 𝐵 sufficiently large. 7

Conclusions

Ethereum’s EIP-1559 mechanism regulates block utilization through a simple price update rule. However, existing analyses treat this pricing problem in a static setting and do not explicitly model the evolving composition of the mempool. In this paper, we study a dynamic transaction scheduling problem with heterogeneous transaction sizes and per-unit values, where users are patient and unscheduled transactions remain in the mempool and can be scheduled in future blocks. We first provide a primal–dual interpretation of the static EIP-1559 mechanism, showing that the block price naturally arises as a dual variable of a social-welfare maximization program. We then leverage this view to analyze the mechanism via a primal–dual competitive-ratio argument. Next, we extend this framework to a dynamic setting by formulating the scheduling problem as a discounted MDP whose state captures the mempool configuration and whose actions correspond to prices. We further incorporate holding costs and overshoot penalties into a long-run discounted objective and apply an episodic Natural Policy Gradient (NPG) algorithm to learn an optimal dynamic pricing policy. Our experiments in both deterministic and stochastic arrival regimes confirm that dynamic pricing can stabilize the transaction pool while maximizing discounted reward. In particular, as the overshoot penalty increases, the average scheduled transaction volume converges to the target block capacity 𝐵, and the resulting NPG updates closely resemble the EIP1559 exponential price update rule observed in the static setting. Finally, we examine two special cases of the MDP formulation: one with homogeneous transactions and one with uniform arrivals. In the homogeneous setting, where the protocol directly controls the scheduled transaction volume, we show that the optimal policy has a threshold structure. Building on this insight and addressing block overflow, we then derive a theoretical lower bound on the block capacity 𝐵 required to ensure system stability under a bang–bang pricing mechanism with uniform arrivals. Our work opens an avenue to several intriguing research questions. One direction is to extend our results to a partially observable setting. Another is to characterize the structure of optimal scheduling policies for a broader class of arrival processes beyond homogeneous or uniform arrivals. Finally, extending our results to scenarios where the scheduler is further constrained by the environment is an important direction. For instance, one may ask how to design optimal policies when transactions are strategic and the scheduler must design a mechanism to elicit truthful information about users’ transaction sizes and values in a dynamic manner [Leon and Etesami, 2025]. Another extension is to consider heterogeneous blocks with varying features, which impose additional constraints on the types of transactions that can be scheduled. In such constrained dynamic environments, we believe that our primal–dual analysis based on occupancy measures sets the stage for incorporating additional constraints and future developments. References Yasin Abbasi Yadkori, Peter L Bartlett, Varun Kanade, Yevgeny Seldin, and Csaba Szepesvári. 2013. Online learning in markov decision processes with adversarially chosen transition probability distributions. Advances in neural information processing systems 26 (2013).

Fatemeh Fardno and S. Rasoul Etesami

23

Eitan Altman. 2021. Constrained Markov Decision Processes. Routledge. Guillermo Angeris, Theo Diamandis, and Ciamac Moallemi. 2024. Multidimensional blockchain fees are (essentially) optimal. arXiv preprint arXiv:2402.08661 (2024). Ameya Anjarlekar, S. Rasoul Etesami, and R. Srikant. 2026. Scalable policy-based RL algorithms for POMDPs. Advances in Neural Information Processing Systems 38 (2026), 96536–96571. Moshe Babaioff and Noam Nisan. 2024. On the Optimality of EIP-1559 for Patient Bidders (Draft–Comments Welcome). (2024). Dimitri Bertsekas. 2012. Dynamic programming and optimal control: Volume I. Vol. 4. Athena scientific. Vitalik Buterin. 2014. Ethereum: A Next-Generation Smart Contract and Decentralized Application Platform. https: //ethereum.org/en/whitepaper. Accessed: 2026-02-01. Vitalik Buterin. 2018. Blockchain resource pricing. URL: https://ethresear. ch/uploads/default/original X 2, 3 (2018), 6. Vitalik Buterin, Eric Conner, Rick Dudley, Matthew Slipper, Ian Norden, and Abdelhamid Bakhta. 2019. EIP-1559: Fee market change for ETH 1.0 chain. Ethereum Improvement Proposals, no. 1559. https://eips.ethereum.org/EIPS/eip-1559 Accessed: 2026-02-01. Davide Crapis, Ciamac C Moallemi, and Shouqiao Wang. 2024. Optimal dynamic fees for blockchain resources. In International Conference on Financial Cryptography and Data Security. Springer, 271–291. Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. 2009. Online Markov decision processes. Mathematics of Operations Research 34, 3 (2009), 726–736. Matheus VX Ferreira, Daniel J Moroz, David C Parkes, and Mitchell Stern. 2021. Dynamic posted-price mechanisms for the blockchain transaction-fee market. In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies. 86–99. Jens Leth Hougaard and Mohsen Pourpouneh. 2023. Farsighted miners under transaction fee mechanism eip1559. In 2023 IEEE International Conference on Blockchain and Cryptocurrency (ICBC). IEEE, 1–9. Koki Inami and Tuan Phung-Duc. 2025. Analysis of Dynamic Transaction Fee Blockchain Using Queueing Theory. Mathematics 13, 6 (2025). https://doi.org/10.3390/math13061010 Vincent Leon and S. Rasoul Etesami. 2025. Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Sequential Auctions under Unknown Environments. arXiv e-prints (2025), arXiv–2506. Stefanos Leonardos, Barnabé Monnot, Daniël Reijsbergen, Efstratios Skoulakis, and Georgios Piliouras. 2021. Dynamical analysis of the eip-1559 ethereum fee market. In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies. 114–126. Stefanos Leonardos, Daniël Reijsbergen, Barnabé Monnot, and Georgios Piliouras. 2023. Optimality despite chaos in fee markets. In International Conference on Financial Cryptography and Data Security. Springer, 346–362. Juan P. Madrigal-Cianci, Camilo Monsalve Maya, and Lachlan Breakey. 2025. A Methodology for Pricing Gas Options in Blockchain Protocols. Finance Research Letters 84 (2025), 107700. https://doi.org/10.1016/j.frl.2025.107700 Available at SSRN: https://ssrn.com/abstract=5180204. Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. (2008). Tiancheng Qin and S Rasoul Etesami. 2023. Scalable and Independent Learning of Nash Equilibrium Policies in 𝑛-Player Stochastic Games with Unknown Independent Chains. arXiv preprint arXiv:2312.01587 (2023). Daniël Reijsbergen, Shyam Sridhar, Barnabé Monnot, Stefanos Leonardos, Stratis Skoulakis, and Georgios Piliouras. 2021. Transaction fees on a honeymoon: Ethereum’s eip-1559 one month later. In 2021 IEEE International Conference on Blockchain (Blockchain). IEEE, 196–204. Tim Roughgarden. 2020. Transaction fee mechanism design for the Ethereum blockchain: An economic analysis of EIP-1559. arXiv preprint arXiv:2012.00854 (2020).

Fatemeh Fardno and S. Rasoul Etesami

24

Appendix Notations The main notations used in this paper are listed in Table 1.

Notation Definitions Q = {𝑞 1, · · · , 𝑞𝑚 } set of transaction sizes V = {𝑣 1, · · · , 𝑣𝑛 } set of transaction per unit values 𝑚 number of different transaction sizes 𝑛 number of different per unit values 𝐵 target block size 𝑐 ·𝐵 maximum block size 𝑟𝑗 arrival time of transaction 𝑗 𝑥 𝑗𝑡 fraction of transaction 𝑗 scheduled on block 𝑡 C set of all transactions 𝑎𝑡 action at time 𝑡 S𝑡 state at time 𝑡 S0 initial state A action space S state space F scheduling protocol 𝜌 𝜋 (·, ·) occupancy measure induced by policy 𝜋

Table 1. List of notations.

A

An Alternative Primal-Dual Formulation for EIP-1559

In this appendix, we provide a more detailed primal–dual formulation of EIP-1559, which yields an interpretable price update rule in terms of the corresponding dual variables. Í Let 𝑄𝑡 := 𝑗 ∈ C 𝑞 𝑗 𝑥 𝑗𝑡 denote the total scheduled size in block 𝑡. We aim to incorporate a one-sided penalty (𝑄𝑡 − 𝐵)+ into our main objective, which is the social welfare:

Social Welfare =

 ∑︁  ∑︁    𝑣 𝑥 − 𝑐 (𝑄 − 𝐵) 𝑗 𝑗𝑡 over 𝑡 + ,   𝑡 𝑗 ∈ C  

where 𝑐 over is the penalty coefficient for exceeding the target block size 𝐵.

SW :=

𝑇 ∑︁ ∑︁ 𝑗 ∈ C 𝑡 =1

𝑞 𝑗 𝑣 𝑗 𝑥 𝑗𝑡 .

25

Fatemeh Fardno and S. Rasoul Etesami

To model the one-sided penalty (𝑄𝑡 − 𝐵)Í+ , we introduce auxiliary variables 𝑦𝑡 ≥ 0 such that 𝑦𝑡 ≥ 𝑄𝑡 − 𝐵 and maximize welfare minus 𝑡 𝑦𝑡 : max

𝑇 ∑︁ ∑︁

𝑞 𝑗 𝑣 𝑗 𝑥 𝑗𝑡 −

𝑗 ∈ C 𝑡 =1

s.t.

𝑇 ∑︁

𝑇 ∑︁

(33)

𝑦𝑡

𝑡 =1

𝑥 𝑗𝑡 ≤ 1

∀𝑗 ∈ C,

𝑡 =𝑟 𝑗

∑︁

𝑞 𝑗 𝑥 𝑗𝑡 ≤ 2𝐵

∀𝑡 ∈ {1, . . . ,𝑇 },

𝑞 𝑗 𝑥 𝑗𝑡 − 𝑦𝑡 ≤ 𝐵

∀𝑡 ∈ {1, . . . ,𝑇 },

𝑗∈C

∑︁ 𝑗∈C

𝑦𝑡 ≥ 0

∀𝑡 ∈ {1, . . . ,𝑇 },

𝑥 𝑗𝑡 ≥ 0

∀𝑗 ∈ C, ∀𝑡 ≥ 𝑟 𝑗 .

Then the dual can be written as min

∑︁

𝛼𝑗 +

𝑗∈C

𝑇 ∑︁ 𝑡 =1

𝛽𝑡 +

𝑇 ∑︁

(34)

𝛾𝑡

𝑡 =1



 𝛽𝑡 𝛾𝑡 + ≥ 𝑞𝑗𝑣𝑗 2𝐵 𝐵 𝛼 𝑗 ≥ 0 ∀𝑗, 𝛽𝑡 ≥ 0 ∀𝑡,

s.t. 𝛼 𝑗 + 𝑞 𝑗

∀𝑗 ∈ C, ∀𝑡 ≥ 𝑟 𝑗 , 0 ≤ 𝛾𝑡 ≤ 𝐵

∀𝑡 .

We now provide an interpretation of the dual variables. Let 𝛽𝑡 denote the shadow price associated with the hard capacity constraint of block 𝑡, i.e., the marginal cost of utilizing the full block capacity 2𝐵. Accordingly, scheduling 𝑞 𝑗 units of transaction 𝑗 in block 𝑡 incurs a capacity cost of 𝛽𝑡 𝑞𝑗 . 2𝐵 The dual variable 𝛾𝑡 represents the penalty associated with exceeding the target block size 𝐵 in block 𝑡. Specifically, 𝛾𝑡 is activated when the total scheduled transaction size on block 𝑡, i.e., 𝑄𝑡 , exceeds 𝐵, and it captures the cost of allocating up to an additional block-sized amount of capacity beyond the target. Equivalently, when the block size exceeds 𝐵, scheduling 𝑞 𝑗 additional units of transaction 𝑗 incurs an extra charge of 𝛾𝑡 𝑞𝑗 . 𝐵 We can also interpret this as follows: if 𝑄𝑡 > 𝐵, then the share of the overshoot penalty allocated to 𝛾 transaction 𝑗 is proportional to its size, i.e., 𝑞 𝑗 multiplied by the marginal cost 𝐵𝑡 . Together, the effective per-unit price faced by a transaction scheduled on block 𝑡 is 𝛽𝑡 𝛾𝑡 + , 2𝐵 𝐵 which reflects both the scarcity of total block capacity and the congestion cost of exceeding the target block size. Transaction 𝑗 has total value 𝑣 𝑗 𝑞 𝑗 . Thus, if it is scheduled on block 𝑡, its utility is 𝑝𝑡 =

𝑢 𝑗,𝑡 = 𝑞 𝑗 𝑣 𝑗 −

𝛽𝑡 𝛾𝑡 𝑞𝑗 − 𝑞𝑗 . 2𝐵 𝐵

Fatemeh Fardno and S. Rasoul Etesami

26

Define   𝛽𝑡 𝛾𝑡 𝛼 𝑗 := max 𝑞 𝑗 𝑣 𝑗 − 𝑞 𝑗 − 𝑞 𝑗 , 𝑡 ≥𝑟 𝑗 2𝐵 𝐵 which represents the maximum utility that transaction 𝑗 can achieve. Since transactions never accept negative utility, transaction 𝑗 is scheduled only on blocks whose effective price does not exceed its value, i.e., 𝛽𝑡 𝛾𝑡 + ≤ 𝑣𝑗. 𝑝𝑡 = 2𝐵 𝐵 Therefore, the problem of choosing the allocation variables 𝑥 𝑗𝑡 reduces to the problem of setting an appropriate price for each block 𝑡. As a result, only transactions with 𝑣 𝑗 ≥ 𝑝𝑡 can be scheduled in block 𝑡. B B.1

Auxiliary Lemmas and Omitted Proofs Auxiliary Lemmas

Lemma 9. Let ℎ : R2 → R be a jointly convex function, and define 𝑔(𝑥) := inf 𝑓 ∈R ℎ(𝑥, 𝑓 ). Then, 𝑔 is a convex function on R. Proof. Let 𝑔(𝑥 1 ) = inf 𝑓 ∈R ℎ(𝑥 1, 𝑓 ) and 𝑔(𝑥 2 ) = inf 𝑓 ∈R ℎ(𝑥 2, 𝑓 ). For every 𝜖 > 0, there exists 𝑓1, 𝑓2 ∈ R such that 𝑔(𝑥 1 ) + 𝜖 ≥ ℎ(𝑥 1, 𝑓1 ) and 𝑔(𝑥 2 ) + 𝜖 ≥ ℎ(𝑥 2, 𝑓2 ). For 𝜆 ∈ [0, 1], we have 𝜆𝑔(𝑥 1 ) + (1 − 𝜆)𝑔(𝑥 2 ) = 𝜆(𝑔(𝑥 1 ) + 𝜖) + (1 − 𝜆) (𝑔(𝑥 2 ) + 𝜖) − 𝜖 ≥ 𝜆ℎ(𝑥 1, 𝑓1 ) + (1 − 𝜆)ℎ(𝑥 2, 𝑓2 ) − 𝜖 ≥ ℎ(𝜆𝑥 1 + (1 − 𝜆)𝑥 2, 𝜆𝑓1 + (1 − 𝜆) 𝑓2 ) − 𝜖 ≥ 𝑔(𝜆𝑥 1 + (1 − 𝜆)𝑥 2 ) − 𝜖. Since this relation holds for every 𝜖 > 0, we conclude that 𝜆𝑔(𝑥 1 ) + (1 − 𝜆)𝑔(𝑥 2 ) ≥ 𝑔(𝜆𝑥 1 + (1 − 𝜆)𝑥 2 ), and therefore 𝑔(·) is convex on R.

□

Lemma 10. Let 𝑄 : R2 → R be jointly convex and continuous, and let H ⊆ R2 be a nonempty convex set. For each 𝑥 ∈ R, define H𝑥 := {𝑓 ∈ R : (𝑥, 𝑓 ) ∈ H }, and suppose that H𝑥 is compact. Define 𝑔(𝑥) := min 𝑓 ∈ H𝑥 𝑄 (𝑥, 𝑓 ). Then 𝑔 is convex on the set {𝑥 ∈ R : ∃ 𝑓 ∈ R such that (𝑥, 𝑓 ) ∈ H }. Proof. Since 𝑄 is jointly convex, 𝑄 (𝑥, ·) must be convex for each fixed 𝑥. Also, since H𝑥 is assumed to be compact, min 𝑓 ∈ H𝑥 𝑄 (𝑥, 𝑓 ) is well-defined. Define ℎ : R2 → R as   0  ℎ(𝑥, 𝑓 ) =   ∞

(𝑥, 𝑓 ) ∈ H, else,

where we note that ℎ : R2 → R is jointly convex. This is because for 𝜆 ∈ [0, 1], we have 𝜆ℎ(𝑥 1, 𝑓1 ) + (1 − 𝜆)ℎ(𝑥 2, 𝑓2 ) ≥ ℎ(𝜆𝑥 1 + (1 − 𝜆)𝑥 2, 𝜆𝑓1 + (1 − 𝜆) 𝑓2 ), which holds if (𝑥 1, 𝑓1 ), (𝑥 2, 𝑓2 ) ∈ H because of convexity of H . On the other hand, if one of the points is not in H , for example (𝑥 1, 𝑓1 ) ∉ H or (𝑥 2, 𝑓2 ) ∉ H , then the left-hand side would be infinity and the inequality would hold trivially. We can therefore rewrite 𝑔(·) as 𝑔(𝑥) = min 𝑓 ∈R {𝑄 (𝑥, 𝑓 ) + ℎ(𝑥, 𝑓 )}, which is well defined since we assume that H is nonempty. Now since both ℎ and 𝑄 are jointly convex, their sum is also jointly convex and according to Lemma 9, 𝑔 is convex on its domain. □

27

Fatemeh Fardno and S. Rasoul Etesami

B.2

Proof of Lemma 3

We first use induction to show that 𝐽𝑘 is convex for all 𝑘. The base case holds since 𝐽0 (𝑥) = 𝑐 term𝑥, which is convex. Now suppose that 𝐽𝑘 (·) is convex. Let 𝐽𝑘+1 (𝑥) = min {𝑄𝑘 (𝑥, 𝑓 )},

(35)

𝑓 ∈ H𝑥

where 𝑄𝑘 (𝑥, 𝑓 ) := 𝑐 hold𝑥 + 𝑐 over (𝑓 ) + + 𝛾E[𝐽𝑘 (𝑥 + 𝐴 − 𝑓 − 𝐵)], and H𝑥 = {𝑓 ∈ R : (𝑥, 𝑓 ) ∈ H } with H = {(𝑥, 𝑓 ) ∈ [0, ∞] × [−𝐵, ∞) : 𝑓 ≤ min{𝑥, 2𝐵} −𝐵}. We have (0, −𝐵) ∈ H , hence H is nonempty. The feasible region H is clearly closed and convex, but not necessarily bounded. However, for each fixed 𝑥, the set H𝑥 is both closed and bounded (see Fig. 5 for 𝐵 = 5).

Fig. 5. Illustration of the feasible region H for 𝐵 = 5.

Next, we show that 𝑄𝑘 (·, ·) is jointly convex. For any 𝜆 ∈ [0, 1], it suffices to show that 𝜆𝑄𝑘 (𝑥 1, 𝑓1 ) + (1 − 𝜆)𝑄𝑘 (𝑥 2, 𝑓2 ) ≥ 𝑄𝑘 (𝜆𝑥 1 + (1 − 𝜆)𝑥 2, 𝜆𝑓1 + (1 − 𝜆) 𝑓2 ). We can write 𝜆𝑄𝑘 (𝑥 1, 𝑓1 ) + (1 − 𝜆)𝑄𝑘 (𝑥 2, 𝑓2 ) = 𝜆 𝑐 hold𝑥 1 + 𝑐 over (𝑓1 ) + + 𝛾E[𝐽𝑘 (𝑥 1 + 𝐴 − 𝑓1 − 𝐵)]

+ (1 − 𝜆) 𝑐 hold𝑥 2 + 𝑐 over (𝑓2 ) + + 𝛾E[𝐽𝑘 (𝑥 2 + 𝐴 − 𝑓2 − 𝐵)]
= 𝑐 hold (𝜆𝑥 1 + (1 − 𝜆)𝑥 2 ) + 𝑐 over 𝜆(𝑓1 ) + + (1 − 𝜆) (𝑓2 ) +

+ 𝛾E[𝜆𝐽𝑘 (𝑥 1 + 𝐴 − 𝑓1 − 𝐵) + (1 − 𝜆) 𝐽𝑘 (𝑥 2 + 𝐴 − 𝑓2 − 𝐵)] ≥ 𝑐 hold (𝜆𝑥 1 + (1 − 𝜆)𝑥 2 ) + 𝑐 over (𝜆𝑓1 + (1 − 𝜆) 𝑓2 ) + + 𝛾E[𝐽𝑘 (𝜆𝑥 1 + (1 − 𝜆)𝑥 2 − 𝜆𝑓1 − (1 − 𝜆) 𝑓2 + 𝐴 − 𝐵)]. In the above relations, we have used the fact that (·) + is convex, and that 𝐽𝑘 (𝑥 + 𝐴 − 𝑓 − 𝐵) is the composition of a convex function (by the induction hypothesis) with an affine function of (𝑥, 𝑓 ), and is therefore convex. Moreover, taking expectations preserves convexity. Therefore, we have shown that 𝑄𝑘 (·, ·) is jointly convex, which, in view of Lemma 10, implies that 𝐽𝑘+1 is convex, completing the induction. Now, since we have shown that 𝐽𝑘 (·) is convex for all 𝑘 = 1, 2, . . ., and the limit lim𝑘→∞ 𝐽𝑘 exists, the limit function 𝐽 ∗ := lim𝑘→∞ 𝐽𝑘 is also convex. Finally, using the convexity of 𝐽 ∗ and a similar argument as above, one can show that 𝑄 ∗ (𝑠, 𝑓 ) is jointly convex, where 𝐽 ∗ (𝑠) =

min

𝑄 ∗ (𝑠, 𝑓 ).

−𝐵 ≤ 𝑓 ≤min{𝑠,2𝐵 }−𝐵

Consequently, for any fixed 𝑠, the function 𝑄 ∗ (𝑠, ·) is convex in 𝑓 .

Fatemeh Fardno and S. Rasoul Etesami

B.3

28

Proof of Lemma 4

We first show that 𝐽𝑘 (·), as defined in Eq. (20), is non-decreasing for all 𝑘 using induction. The statement holds for 𝐽0 (𝑥) = 𝑐 term𝑥. Now suppose that 𝐽𝑘 (·) is non-decreasing. Let 𝑥 1 ≤ 𝑥 2 . We have   𝐽𝑘+1 (𝑥 1 ) − 𝐽𝑘+1 (𝑥 2 ) = min 𝑐 hold𝑥 1 + 𝑐 over (𝑓 ) + + 𝛾E[𝐽𝑘 (𝑥 1 + 𝐴 − 𝑓 − 𝐵)] 𝑓 ∈ H𝑥 1   − min 𝑐 hold𝑥 2 + 𝑐 over (𝑓 ) + + 𝛾E[𝐽𝑘 (𝑥 2 + 𝐴 − 𝑓 − 𝐵)] 𝑓 ∈ H𝑥 2

:= min [𝑄𝑘 (𝑥 1, 𝑓 )] − min [𝑄𝑘 (𝑥 2, 𝑓 )] . 𝑓 ∈ H𝑥 1

𝑓 ∈ H𝑥 2

Note that since we have already shown that 𝐽𝑘 is convex in Lemma 3, the quantity min 𝑓 ∈ H𝑥 𝑄𝑘 (𝑥, 𝑓 ) is well-defined. Also, by the definition of H𝑥 , we know that H𝑥 1 ⊆ H𝑥 2 . We consider two cases: • arg min 𝑓 ∈ H𝑥2 𝑄𝑘 (𝑥 2, 𝑓 ) ∈ H𝑥 1 : Then, for every realization of 𝐴, and any 𝑓 ∈ H𝑥 1 , we have 𝑥 1 + 𝐴 − 𝑓 − 𝐵 ≤ 𝑥 2 + 𝐴 − 𝑓 − 𝐵, and since 𝐽𝑘 (·) is non-decreasing, 𝐽𝑘 (𝑥 1 + 𝐴 − 𝑓 − 𝐵) ≤ 𝐽𝑘 (𝑥 2 + 𝐴 − 𝑓 − 𝐵). Taking expectation preserves the inequality, hence E[𝐽𝑘 (𝑥 1 + 𝐴 − 𝑓 − 𝐵)] ≤ E[𝐽𝑘 (𝑥 2 + 𝐴 − 𝑓 − 𝐵)]. And since 𝑥 1 ≤ 𝑥 2 , we have 𝑄𝑘 (𝑥 1, 𝑓 ) ≤ 𝑄𝑘 (𝑥 2, 𝑓 ). Taking minimum over 𝑓 ∈ H𝑥 1 we obtain 𝐽𝑘+1 (𝑥 1 ) = min 𝑄𝑘 (𝑥 1, 𝑓 ) ≤ min 𝑄𝑘 (𝑥 2, 𝑓 ) = min 𝑄𝑘 (𝑥 2, 𝑓 ) = 𝐽𝑘+1 (𝑥 2 ). 𝑓 ∈ H𝑥 1

𝑓 ∈ H𝑥 1

𝑓 ∈ H𝑥 2

• arg min 𝑓 ∈ H𝑥2 𝑄𝑘 (𝑥 2, 𝑓 ) ∈ H𝑥 2 − H𝑥 1 : In this case, let us define 𝑓2∗ = arg min 𝑓 ∈ H𝑥2 𝑄𝑘 (𝑥 2, 𝑓 ) and 𝑓1∗ = arg min 𝑓 ∈ H𝑥1 𝑄𝑘 (𝑥 1, 𝑓 ). According to the definition of H𝑥 , it is not hard to see that 𝑓1∗ ≤ min{𝑥 1, 2𝐵} − 𝐵 < 𝑓2∗ ≤ min{𝑥 2, 2𝐵} − 𝐵. Instead of directly showing 𝑄𝑘 (𝑥 1, 𝑓1∗ ) ≤ 𝑄𝑘 (𝑥 2, 𝑓2∗ ), we will show that 𝑄𝑘 (𝑥 1, 𝑓1∗ ) ≤ 𝑄𝑘 (𝑥 1, 𝑓ˆ), and 𝑄𝑘 (𝑥 1, 𝑓ˆ) ≤ 𝑄𝑘 (𝑥 2, 𝑓2∗ ), where 𝑓ˆ = min{𝑥 1, 2𝐵} − 𝐵 ∈ H𝑥 1 . Since 𝑓1∗ is a minimizer over H𝑥 1 and 𝑓ˆ ∈ H𝑥 1 , we have 𝑄𝑘 (𝑥 1, 𝑓1∗ ) ≤ 𝑄𝑘 (𝑥 1, 𝑓ˆ). Therefore, it remains to show that 𝑄𝑘 (𝑥 1, 𝑓ˆ) ≤ 𝑄𝑘 (𝑥 2, 𝑓2∗ ).

(36)

To show inequality (36), we can write 𝑄𝑘 (𝑥 1, 𝑓ˆ) = 𝑐 hold𝑥 1 + 𝑐 over ( 𝑓ˆ) + + 𝛾E[𝐽𝑘 (𝑥 1 + 𝑎 − 𝑓ˆ − 𝐵)]. Since 𝑥 1 ≤ 𝑥 2 , we have 𝑐 hold𝑥 1 ≤ 𝑐 hold𝑥 2 . Also, by construction: 𝑓ˆ = min{𝑥 1, 2𝐵} − 𝐵 < 𝑓2∗, and since (·) + is non-decreasing, 𝑐 over ( 𝑓ˆ) + < 𝑐 over (𝑓2∗ ) + . Finally, we compare the 𝐽𝑘 (·) terms that appear on both sides of (36). We have 𝑓2∗ ≤ min{𝑥 2, 2𝐵} − 𝐵 ≤ 𝑥 2 − 𝐵. Hence, for any realization of 𝐴, we have 𝐴 ≤ 𝑥 2 + 𝐴 − 𝑓2∗ − 𝐵. On the other hand, since 𝑓ˆ = min{𝑥 1, 2𝐵} − 𝐵, we can write the following relations 𝑥 1 + 𝐴 − 𝑓ˆ − 𝐵 = 𝐴 + 𝑥 1 − min{𝑥 1, 2𝐵} 𝑥 2 + 𝐴 − 𝑓2∗ − 𝐵 ≥ 𝐴 + 𝑥 2 − min{𝑥 2, 2𝐵}.

Fatemeh Fardno and S. Rasoul Etesami

29

Now note that the function 𝑥 − min{𝑥, 2𝐵} is non-decreasing in 𝑥. Since 𝑥 1 ≤ 𝑥 2 , we have 𝑥 1 − min{𝑥 1, 2𝐵} ≤ 𝑥 2 − min{𝑥 2, 2𝐵}. Hence, 𝑥 1 + 𝐴 − 𝑓ˆ − 𝐵 ≤ 𝑥 2 + 𝐴 − 𝑓2∗ − 𝐵. Finally since 𝐽𝑘 (·) is non-decreasing by the induction hypothesis, we have 𝐽𝑘 (𝑥 1 + 𝐴 − 𝑓ˆ − 𝐵) ≤ 𝐽𝑘 (𝑥 2 + 𝐴 − 𝑓 ∗ − 𝐵). 2

Since taking expectation preserves the inequality, we can conclude that Eq. (36) holds and 𝐽𝑘+1 (𝑥 1 ) − 𝐽𝑘+1 (𝑥 2 ) = 𝑄𝑘 (𝑥 1, 𝑓1∗ ) − 𝑄𝑘 (𝑥 2, 𝑓2∗ ) ≤ 0. Hence, in both cases, 𝐽𝑘+1 (𝑥 1 ) ≤ 𝐽𝑘+1 (𝑥 2 ), which completes the induction. Finally, since we have shown that 𝐽𝑘 (·) is non-decreasing for all 𝑘, taking the limit as 𝑘 → ∞, we conclude that 𝐽 ∗ (·) is also a non-decreasing function.