Dynamic Transaction Scheduling and Pricing in the Ethereum Mempool

Dynamic transaction scheduling and pricing in Ethereum addresses how to manage block utilization by modeling transactions as patient entities arriving stochastically over time. This study introduces a dynamic transaction scheduling problem framed as a discounted Markov Decision Process (MDP) to extend the static EIP-1559 mechanism, showing that dynamic pricing stabilizes the mempool while maximizing long-run discounted reward.

Modeling the Dynamic Problem

The paper models transactions with heterogeneous sizes and per-unit values arriving over time, treating them as patient rather than impatient. The state of the system is represented by a matrix where each entry records the number of transactions of a specific size and value waiting in the pool at time t. The action taken by the mechanism at each time step is setting a price threshold, which corresponds to an index in a set of possible values. This formulation explicitly captures arrival dynamics and the evolving state of the transaction pool.

Primal-Dual Interpretation and Competitive Analysis

A novel primal–dual interpretation is provided for the static EIP-1559 algorithm, viewing its pricing scheme as the dual variables of a social welfare maximization program. This perspective allows for characterizing the interaction among pricing, block capacity constraints, and transaction selection. By building on this, the framework is extended to a dynamic setting where block prices are interpreted as decision variables linked to the dual occupancy measures of the underlying MDP. The competitive ratio analysis shows that EIP-1559 is γ-competitive for the static online scheduling problem with a specific constant γ derived from transaction parameters.

Optimal Policy Determination via NPG Algorithm

The objective is formulated as maximizing the long-run discounted reward while accounting for holding costs and capacity overshoot penalties. The optimal scheduling policy is determined using the Natural Policy Gradient (NPG) algorithm applied to this MDP. The results demonstrate 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, and the resulting policy updates closely resemble [the] EIP-1559 price update rule.

Special Case Analysis: Homogeneous Transactions

The study examines two special cases. In the homogeneous setting, where all transaction sizes and values are identical, pricing becomes irrelevant because all transactions have the same value, reducing the problem to one where the protocol directly controls the scheduled transaction volume. This characterization reveals that the optimal policy has a threshold structure, meaning it schedules a minimum volume until congestion reaches a threshold, after which it schedules more to reduce congestion.

Special Case Analysis: Uniform Arrivals and Lower Bounds

For the case of uniform arrivals—where exactly one transaction of each type arrives at every time step—the authors propose and analyze a bang–bang pricing mechanism. This analysis is used to derive a theoretical lower bound on the block capacity B required to ensure system stability under this bang–bang pricing mechanism, leading to a final constraint that simplifies to:

"nQ2 < Q4 / (3 + √8n2 − 16n + 9) ≤ B."

Numerical Validation and Findings

Numerical experiments validate the theoretical findings across different settings. In Setting 1, varying the overshoot penalty shows that the average volume of scheduled transactions converges toward the target block capacity, consistent with the behavior observed under EIP-1559. Furthermore, in Setting 3 (stochastic arrivals), for small overshoot costs, the average scheduled transaction volume closely matches the average incoming transaction volume, while increasing overshoot costs causes this volume to decrease and converge to a level below B.

Optimal Policy Structure

The analysis of the homogeneous setting leads to a closed-form characterization of the optimal scheduling policy, defined by a threshold state s∗ ≥ B. The resulting optimal policy f∗(s) is:

"f1(s) = min[s − B, 0], 0 ≤ s ≤ s∗, min[s − s∗, B], s > s∗." This structure implies that the protocol schedules as little as possible when congestion is below the threshold and schedules more than B units when congestion exceeds it.

Conclusion

The research confirms that dynamic pricing can stabilize the transaction pool while maximizing discounted reward, and it provides a principled framework for understanding how to design block prices to control mempool congestion in a dynamic environment. The work establishes necessary conditions for system stability under simple pricing rules by deriving lower bounds on target block capacity B.

The gist

Dynamic pricing stabilizes the transaction pool while maximizing long-run discounted reward by modeling transactions as patient entities arriving stochastically over time, and showing that dynamic pricing can stabilize the mempool while maximizing discounted reward.

References

[Babaioff and Nisan, 2024]

[Buterin et al.

As a fastidious researcher, I have analyzed this paper, Dynamic Transaction Scheduling and Pricing in the Ethereum Mempool. The core contribution is extending static EIP-1559 analysis to a dynamic setting using a Discounted Markov Decision Process (MDP) framework, optimized by Natural Policy Gradient (NPG).

Here are specific improvements you can make to AI systems based on this research:

),

• Use the derived NPG policy updates (Eq. 15) as an update rule for reinforcement learning agents in dynamic resource allocation or scheduling problems where a cost function involves a fixed capacity constraint and a penalty for exceeding it.

• Implement the primal-dual interpretation (Section A) to design novel, interpretable pricing mechanisms for decentralized systems. Instead of relying on opaque heuristics, AI agents can learn pricing strategies that are mathematically guaranteed to be optimal relative to an underlying social welfare maximization program.

• Develop Capacity-Aware scheduling algorithms for distributed ledger technologies (DLT). These algorithms would dynamically adjust transaction fees/prices based on real-time mempool congestion and transaction heterogeneity, ensuring the system stabilizes towards a target utilization rate without incurring excessive holding costs or overflow penalties.

• Create specialized RL agents for Mempool Management. These agents would learn to balance two competing objectives: minimizing the cost of holding unscheduled transactions (holding cost, Eq. 10) versus minimizing block size overshoot penalties (overrun penalty, Eq. 10), leading to optimal scheduling policies that are sensitive to the relative magnitudes of these costs.

• Design robust stability analysis tools for blockchain protocols using the derived lower bounds on target block capacity (Section 6). These tools can be used by protocol designers to prove mathematically the minimum required block size necessary for a given set of transaction types and arrival patterns to prevent system instability under simple pricing rules (like bang-bang pricing).

• Apply the threshold policy structure (Theorem 5) to simplify complex scheduling policies. AI systems could learn to identify congestion thresholds and switch between two distinct operational modes—one prioritizing low volume when congestion is low, and another prioritizing high volume when congestion is high—leading to simpler, more robust decision-making logic.

• Extend the MDP framework (Section 3) to model Partially Observable Markov Decision Processes (POMDPs). This would allow AI agents to make optimal scheduling decisions even when they do not have perfect knowledge of the entire mempool state, by using history of scheduled transactions to maintain a belief distribution over the true state.

The Ethereum blockchain utilizes the EIP-1559 algorithm to manage transaction inclusion and block assembly. However, EIP-1559 and much of the existing literature study this problem from a static perspective, focusing on price evolution without modelling transaction dynamics within the mempool. Motivated by this limitation, we study a dynamic transaction scheduling problem in which transactions with heterogeneous sizes and per-unit values arrive over time and remain in the mempool until scheduled. To capture the stochastic mempool evolution, we formulate the problem as a Markov Decision Process (MDP) whose state represents the mempool configuration and whose actions correspond to block prices. We first provide a primal-dual interpretation of the static EIP-1559 mechanism, showing that block prices arise naturally as dual variables of a social-welfare maximization problem. Building on this perspective, we extend the framework to the dynamic setting and formulate an objective that maximizes long-run discounted reward while incorporating holding costs and overshoot penalties. We then employ a Natural Policy Gradient (NPG) algorithm to compute the optimal policy. Our results show that dynamic pricing stabilizes the mempool 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 updates closely resemble the EIP-1559 price update rule. Finally, we study two special cases of the MDP formulation: homogeneous transactions and uniform arrivals. In the homogeneous setting, where the protocol directly controls scheduled volume, we show that the optimal policy has a threshold structure. We then propose a bang-bang pricing mechanism for uniform arrivals and derive a lower bound on the block capacity needed to ensure system stability.