# Dynamic Transaction Scheduling and Pricing in the Ethereum Mempool

Crypto.world

> Ethereum's EIP-1559 sets a per-block base fee and adjusts it up or down depending on whether the previous block was fuller or emptier than a target capacity, but it ignores what is actually waiting…

**arXiv**: 2605.12794

**Published**: 2026-05-12

**Authors**: Fatemeh Fardno, S. Rasoul Etesami

## AI summary

## Overview

**Research area:** Blockchain protocol design and mechanism design — specifically transaction fee mechanisms, mempool dynamics, Markov decision processes, and online scheduling theory (arXiv category: Computer Science and Game Theory).

**Technical level:** Advanced. The paper assumes familiarity with linear programming duality, Markov decision processes, policy gradient methods, and the EIP-1559 fee mechanism.

**Scope:** The paper recasts Ethereum's EIP-1559 fee mechanism as the dual of a value-maximizing linear program, then extends it to a dynamic, patient-transaction MDP setting solved with Natural Policy Gradient, with analytical treatment of two special cases.

## What This Paper Is About

Ethereum's EIP-1559 sets a per-block base fee and adjusts it up or down depending on whether the previous block was fuller or emptier than a target capacity, but it ignores what is actually waiting in the mempool. The authors ask what a price-setting protocol should do if it can see the queue of pending transactions, where transactions are *patient* (unscheduled ones simply wait and can be included in a later block without losing value). The goal is to choose block prices that trade off clearing mempool congestion against the cost of scheduling above the target block size, and to show how such a policy relates to the existing EIP-1559 update rule.

## Key Contributions

1. **A primal–dual interpretation of static EIP-1559.** The block price is shown to arise naturally as a dual variable of a linear program that maximizes the total value of scheduled transactions subject to the hard block cap, giving an interpretable link between prices, capacity constraints, and transaction selection.
2. **A competitive ratio analysis via the primal–dual method.** The paper proves EIP-1559 is γ-competitive against the optimal offline schedule, with γ stated explicitly in terms of block capacity, maximum transaction value, minimum transaction size, minimum price, and the update parameter η.
3. **An MDP extension to the dynamic, patient-transaction setting.** The mempool is modeled as a state matrix counting transactions of each (size, value) type, the action is a value threshold (equivalently a price), and the reward penalizes both holding costs and overshoot above the target capacity. An episodic Natural Policy Gradient method is used to compute the policy, and the authors report that EIP-1559's exponential price update emerges as a special case.
4. **Two analytically tractable special cases.** With homogeneous transactions (identical sizes and values, so pricing becomes irrelevant and the protocol directly controls volume), the optimal policy has a threshold structure. Motivated by this, the authors propose a bang–bang pricing mechanism (price restricted to its minimum or maximum) for uniform arrivals and derive a theoretical lower bound on the block capacity required for stability.

## Main Findings

- **Prices are dual variables.** In the static linear program, the dual variable β_t is interpreted as the price of using the full capacity 2B of block t, so scheduling q_j units in block t costs (β_t / 2B)·q_j. A transaction is scheduled only on blocks whose price does not exceed its per-unit value.
- **EIP-1559 admits an explicit competitive ratio.** Theorem 1 gives γ = 2B·v_max / (q_min·p_min·(1 + η(q_min − B)/B)) + (v_max − p_min)/v_max in the limit as the horizon T grows, where v_max is the maximum transaction value, q_min the minimum transaction size, and p_min the minimum allowable base fee. The finite-horizon version carries an additional factor (T − 1 + v_max/p_min)/(T − 1).
- **The proof uses weak duality.** Setting β_t = 2B·p_t·(v_max/p_min) and choosing per-transaction α_j values yields a feasible dual solution, and combining two independent lower bounds on the online algorithm's value produces the ratio.
- **The Ethereum parameters appear explicitly.** The price rule studied is p_{t+1} = max{p_min, p_t·exp(η(Q_t − B)/B)}, with η set to 1/8 in Ethereum, and the hard cap is 2B (the EIP-1559 relaxation of the target B).
- **The reward function encodes the congestion/overshoot tradeoff.** The per-step reward is r(S_t, a_t) = −c_hold·Q_pool^t − c_over·(Q_sched(S_t, a_t) − B)^+. When c_hold is much larger than c_over, the optimal policy schedules aggressively and keeps the pool nearly empty; when c_hold is much smaller than c_over, it protects the target capacity and tolerates a crowded mempool.
- **Natural Policy Gradient recovers EIP-1559-like updates.** The authors report that 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 in the static setting.
- **Homogeneous transactions yield a threshold policy.** Because all transactions have the same value, pricing is irrelevant and the protocol controls volume directly: below a congestion threshold the protocol schedules the minimum possible volume; once congestion reaches the threshold it schedules more than B units until congestion falls back below it, and the cycle repeats.
- **A bang–bang mechanism is proposed for uniform arrivals.** In the uniform-arrival case (exactly one transaction of each type arrives per time step), restricting the price to its minimum or maximum is analyzed, and a theoretical lower bound on B for system stability under that mechanism is derived. The explicit expression of that bound does not appear in the available text.
- **Assumptions and scope limits are stated openly.** Tips are not modeled (an adversary selects among eligible transactions when the 2B cap binds), transactions are non-strategic and buy the first block with a low enough price and sufficient capacity, and the protocol is assumed to observe the full mempool.

## Methodology in Plain English

The authors start with a stripped-down offline version of the problem: given every transaction's arrival time, size, and per-unit value, choose what fraction of each transaction goes into each block to maximize total scheduled value, subject to each block holding at most 2B of size. Writing down the dual of that linear program reveals that the dual variable attached to each block behaves exactly like a price — a transaction is only worth including if its value covers that price. This gives a recipe for reasoning about EIP-1559: the fee mechanism is implicitly solving (or approximating) that dual, and the standard exponential update of the base fee is how the dual prices get adjusted over time.

They then prove a worst-case guarantee for EIP-1559 by constructing a feasible dual solution from the algorithm's own prices and comparing the dual objective to the value the online algorithm actually captures.

For the dynamic version, they replace the static snapshot with a state machine: the state is a table of how many transactions of each size-and-value type sit in the mempool, the action is a value cutoff (equivalently a price), and each step the protocol schedules eligible transactions according to a fixed packing rule, new transactions arrive randomly, and a reward is paid that subtracts a holding cost for everything left in the pool plus a penalty for exceeding the target block size B. Because the state can grow unboundedly, the packing rule caps each cell at a level L and clears the excess first. They then optimize the policy with an episodic Natural Policy Gradient algorithm rather than by brute force, since the state space is large. Finally, they isolate two simplifications — all transactions identical, and deterministic one-of-each-type arrivals — where the optimal policy can be characterized analytically instead of numerically.

## Why This Matters

**Research impact.** The primal–dual framing turns a mechanism-design question into a linear-programming question, which makes the price interpretable and extensible. It also gives an alternative competitive-ratio proof for EIP-1559 that, per Remark 4, avoids the extra Γ time steps used in prior analysis (Babaioff and Nisan, 2025) and does not rely on regret against a single fixed price in hindsight as in Angeris et al. (2024). The MDP formulation puts mempool state — largely absent from the static literature — at the center of the analysis.

**Real-world applications:**

- Setting base-fee update aggressiveness and block-capacity parameters in production fee markets, using the competitive-ratio expression as a design guide.
- Designing congestion-aware fee mechanisms for rollups and other L2 sequencers that face the same "target capacity versus burst" tradeoff.
- Capacity planning: the stability lower bound on B indicates how much block space a chain needs before a bang–bang style price policy keeps the mempool from growing without bound.
- Operational dashboards and validator/protocol tooling that could condition fee policy on observed mempool composition rather than only on the previous block's fill level.

**Industry relevance.** Ethereum's fee mechanism is directly parameterized by values the paper names (η = 1/8, target B, hard cap 2B, minimum price p_min), so the results speak to protocol-level parameter choices. The finding that NPG updates resemble EIP-1559's rule provides a formal justification for the existing mechanism's design while identifying exactly which ingredient it omits: information about waiting transactions.

## Future Directions

- **Partial observability.** The authors note that full mempool knowledge is assumed for tractability, and sketch an extension to a POMDP where the protocol maintains a belief over the mempool from the history of included transactions, citing existing reduction results (Anjarlekar et al., 2026).
- **Strategic users.** The model assumes transactions are non-strategic and take the first affordable block with capacity; extending the analysis to users who misreport values or time their submissions is left open.
- **Tips.** Transaction tips are explicitly excluded, with an adversary selecting among eligible transactions when the 2B cap binds; incorporating tip-based priority is an obvious next step.
- **Tightening and applying the stability bound.** The explicit lower bound on B under bang–bang pricing with uniform arrivals, and whether the threshold structure of the homogeneous case survives under heterogeneous values and sizes, remain to be fully characterized in the available text.

## Target Audience

Protocol researchers and mechanism designers working on transaction fee markets; graduate students and academics in algorithmic game theory, online scheduling, and reinforcement learning applied to systems; and blockchain engineers at foundations, L2 teams, or infrastructure companies who need a rigorous basis for choosing base-fee update rules and block-capacity parameters. Readers should be comfortable with LP duality and MDP notation, since the central arguments are stated in those terms.

## Authors’ abstract

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…

[The full abstract on arXiv](https://arxiv.org/abs/2605.12794)

[Read the original paper](https://arxiv.org/abs/2605.12794)

---

Canonical: https://crypto.world/paper/dynamic-transaction-scheduling-and-pricing-in-the-ethereum-mempool-2605.12794
