CS Paper Radar

Priority Gas Auction Cadence and Searcher Competition: Evidence from Flashblocks on Base

Pranay Anchuri, Edward W. Felten, Akaki Mamageishvili

cs.CE cs.GTq-fin.TR ·submitted 2026-10-02 18:30 UTC · v1
theory

Abstract

Flashblocks divide a block's priority gas auction into shorter sequential auctions that commit transaction order before the block is complete. We ask how this auction cadence affects bidding and competition among automated arbitrageurs, or searchers. In July 2025 Base replaced a single 2 s auction with ten 200 ms auctions. We use this change to estimate the searcher response from on-chain data alone. On an address-day panel of 3,032 searchers and 8,053 activity-matched controls, a difference-in-differences design estimates a 0.187 gwei fall in the effective priority fee (59% of the searcher pre-period mean). The share of searcher priority-fee value paid in the first tenth of block gas falls from 0.98 to 0.28. This fee compression is the identified effect. The revert-rate response is not (causally) identified and is reported descriptively. At the level of a single opportunity, the winning fee splits into an approximately invariant floor and a competitive premium. The premium scales about linearly with auction duration at high contention and less steeply at low contention. A first-price auction model with uncertain arrival and partial payments by losing searchers accounts for this pattern. We match attempts to the pool they contest. A higher-fee transaction reverts behind a lower-fee winner that landed earlier in 1.9 to 2.7% of contested opportunities by value, an upper bound. Latency therefore decides part of the ordering. A micro-auction model projects diminishing returns from shortening the window below 200 ms, as bids approach a nonzero floor. Rollups such as Arbitrum One now make auction cadence a governance tunable parameter, so these estimates inform how it is set.

Comment
32 pages, 5 figures, includes appendices

Closest papers

Nearest neighbours by meaning across the whole index.

Efficiency of Generalized Proportional First-Price Auctions Under Auto-bidding

cs.GT ·2026-09-30 ·Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta +2 more
theory similarity 0.60
Abstract

Auto-bidding is now widely adopted in online advertising platforms, allowing advertisers to specify high-level campaign objectives--such as maximizing total value subject to a return-on-spend (ROS) constraint--rather than manual per-query bids. A central question in algorithmic mechanism design is characterizing the worst-case efficiency loss, or Price of Anarchy (PoA), across auction formats in this prior-free setting. While randomized auctions are known to strictly improve efficiency over deterministic mechanisms for two bidders, two fundamental questions have remained open: (1) what is the optimal PoA for two bidders, and (2) can any mechanism beat the barrier of 2 for general $n \ge 3$ bidders? We resolve both questions using the family of $r$-proportional first-price auctions ($\text{pFPA}_r$), in which each bidder wins with probability proportional to their bid raised to an exponent $r > 0$ and pays their bid upon winning. First, for two bidders, we prove that the standard proportional first-price auction ($r = 1$) achieves a tight $\text{PoA} \le 1.5$, complemented by a matching lower bound showing that no anonymous, monotone mechanism can do better. Second, for general $n \ge 2$ bidders, setting $r = 2n$ achieves $\text{PoA} \le 2 - \frac{1}{4n+1} = 2 - Ω(1/n)$ across all undominated bid profiles, breaking the deterministic barrier of 2 for every finite $n$ and asymptotically matching the known $2 - Θ(1/n)$ lower bound.

0.46

Impossibility of No-Regret in Multi-Agent Bidding

cs.GT cs.CCcs.LG ·2026-10-27 ·Zongjun Yang, Rachitesh Kumar, Christian Kroer
theory similarity 0.59
Abstract

We consider $T$ repeated second-price auctions across $n$ pacing bidders with i.i.d. item arrivals, and show that it is computationally impossible for all bidders to achieve no-regret simultaneously while satisfying their respective budget or return-on-investment constraints. Therefore, in the prominent internet auction systems where buyers simultaneously deploy pacing algorithms or automated bidding agents, we cannot hope to achieve joint no-regret guarantees in general. We establish a deterministic relationship that high variance in online bidding systems implies high regret. By showing that one can extract a pacing equilibrium from a low-variance system, we prove PPAD-hardness of attaining joint no-regret. For several widely used bidding algorithms, we also show evidence from dynamical systems and numerical simulations that they can indeed display high-variance behavior through cycling, even on simple market instances.

0.08

A Primal-Dual Approach to Randomized Online Bidding with Tail Constraints

cs.DM ·2026-10-04 ·Royce Kraakman, Bob Krekelberg, Alison Hsiang-Hsuan Liu, Fu-Hong Liu
theory similarity 0.58
Abstract

Controlling tail risk in randomized algorithms has received increasing attention. Randomized online algorithms can achieve a lower expected competitive ratio than the competitive ratio of the best deterministic online algorithm. However, individual executions may still incur poor outcomes. Tail constraints address this risk by limiting the probability that the incurred ratio exceeds a prescribed threshold. We investigate how such constraints affect the structure and performance of randomized online bidding algorithms. By revisiting the classical primal-dual lower-bound framework for online bidding, we find that restricting the growth between consecutive bids can yield a stronger lower bound on the expected competitive ratio. We then show that tail constraints with zero exceedance probability impose an asymptotic upper bound on the ratios between consecutive bids. Incorporating this structural property into the primal-dual framework allows us to derive a stronger lower bound. Moreover, the dual analysis suggests a randomized geometric bidding algorithm whose performance matches this bound. The insight from our primal-dual analysis also guides the design of algorithms for general tail constraints allowing positive exceedance probabilities. Motivated by the geometric growth suggested by the dual solution, we study randomized periodic bidding algorithms. We show that, for any fixed geometric base, the uniform offset distribution is optimal in terms of both the expected competitive ratio and tail-constraint feasibility. We then characterize the exceedance probability of these algorithms and use this characterization to choose a geometric growth factor that satisfies the prescribed tail constraints, establishing parameter-dependent upper bounds on the optimal expected competitive ratio.

0.20

Price of Anarchy of First-Price Auctions in Agentic Markets

cs.GT cs.AIcs.LG ·2026-10-14 ·Shubhendu Trivedi, Jacob Eisenstein, Alekh Agarwal, Ian Gemp, Michael Kaisers +1 more
position similarity 0.57
Abstract · 40 pages

An agentic market is a decentralized serving-time market where AI agents bid to claim each user prompt. An agent's bid is based on its expected value for the prompt, which is the expectation of the reward for its response minus its inference costs. First-price auctions (FPAs), in which the highest bidder pays its bid and receives the prompt, are a natural way to allocate prompts in such a market, since they are simple and transparent to run, and do not require central knowledge of private capabilities and costs. However, FPAs are not truthful: participants may bid less than their true value in the hope of a larger profit, and the prompt may then be allocated to someone other than the bidder who values it the most. This welfare loss is quantified by the $\textit{price-of-anarchy}$ (PoA). In this paper, we argue that agentic markets are likely to possess features that reduce the price-of-anarchy. The first is a $\textit{competitive floor}$, which occurs when multiple bidders usually value the prompt above some baseline share of the optimal welfare (e.g., because the best models are often distilled into cheaper alternatives, which perform similarly). We show that competition among them then limits the welfare loss, which can be driven to zero as the floor rises. The second feature is $\textit{near-independence}$ of values after conditioning on the prompt, which occurs when most of the predictable variation in the expected value is determined by the difficulty of the prompt. As the value distribution approaches conditional independence, we can derive an efficiency guarantee that approaches a factor of $1 - 1/e^2$ of the optimal welfare. Thus, both features give rise to welfare lower bounds that are significantly better than the well-known general case of $1 - 1/e$. We validate these results empirically using auctions with strategic bidders simulated on the EmbedLLM prompt routing dataset.

0.34

Regret Bounds for Market Making with Persistent Orders

cs.GT cs.LG ·2026-11-04 ·Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Luigi Foscari, Vinayak Pathak
similarity 0.57
Abstract

We study adversarial market making with orders that remain active until execution. The maker operates on two markets: a primary market where orders are made and a secondary market where the resulting positions are hedged. In each round, the maker posts a quote on the primary market before observing both primary and secondary market prices. An order executes when the primary price reaches its quote, and the resulting position is immediately offset at the secondary price. When both price sequences are chosen by an adversary over $T$ rounds, we give a simple deterministic policy with regret of order $\log T$ against the best fixed quote (static comparator) and $\sqrt T$ against the best quote for each submission date (dynamic comparator), plus two terms measuring exposure to future primary and secondary prices. These rates remain optimal even when both exposure terms vanish and lower bounds show that the exposure terms are necessary. Our policy naturally extends to simultaneous bids and asks, where we show that static and dynamic regret are both characterized (up to constant factors) by the exposures terms (where the primary price exposure $V_T^{\mathrm{two}}$ now accounts for both bids and asks) and a term of order $\sqrt{V_T^{\mathrm{two}}\log T}$. Our policy is simple, efficient and fully parameterless. We extend this setting by demonstrating how natural assumptions on the price processes lead to improved guarantees without changing the policy.

0.21

Tight Inapproximability of Pacing and Throttling Equilibria in Second-Price Auctions

cs.GT cs.CC ·2026-08-17 ·Zhengyang Liu
theory similarity 0.57
Abstract

Budget-constrained advertisers commonly rely on two control mechanisms: pacing scales bids, whereas throttling randomizes participation. We prove that, in second-price auctions, these two different mechanisms share the same sharp approximation-hardness threshold. For pacing, computing a $γ$-approximate equilibrium is $\mathsf{PPAD}$-hard for every constant $γ\in[0,1)$. For throttling, computing a $δ$-approximate equilibrium is $\mathsf{PPAD}$-hard for every constant $δ\in(0,1)$. At parameter $1$, the complementarity requirement becomes vacuous and the all-zero solution is feasible. That is, approximation does not eliminate the fixed-point barrier at any nontrivial parameter value.

0.46

Payment Design under Belief Disagreement: Rent Placement, Bid Resolution, and Auction Choice

cs.GT econ.THmath.OC ·2026-10-05 ·Lijian Lu, Ce Zhang
similarity 0.57
Abstract

When auction bidders misperceive their rivals, a seller can change not only the amount of information rent but also the states in which it is delivered. We ask when this payment-design opportunity survives a finite bidding interface, nonnegative-payment restrictions, and comparison with conventional auctions under the same beliefs. We formulate payment design as a linear program in nonnegative bidder rents. A single state can safely carry a report's rent when it is both cheapest for its intended type and least attractive to potential mimics. We characterize this alignment, bound the cost of a restricted payment architecture when alignment is imperfect, and use shadow prices when the rankings conflict. Own-type projection yields a unique optimal expected-payment rule for a fixed allocation. Contiguous bid bands implement truthful reporting at every value, but create pooling losses and within-band surplus. Under a separate smooth-belief model, feasible truthful rules and revenue upper bounds support comparisons with a first-price equilibrium under the same beliefs. A calibration using 1,000 eBay proof-set auction records illustrates a partition-dependent reversal: first price dominates all exactly truthful, no-subsidy rules on ten equal-probability bands in one scenario, while a richer contingent rule on ten equal-dollar bands outperforms it. An operator should choose interface resolution, payment dependence, and integrity tolerances jointly. Validate the probabilities that support incentives, compare formats under the same beliefs, and distinguish redesign from deployment. Any receipt advantage must cover implementation costs before it can imply a profit advantage.

0.20

Inference Auctions

cs.LG cs.AIcs.GT ·2026-09-30 ·Keegan Harris, Siddharth Prasad, Asher Trockman, Nika Haghtalab, Michael I. Jordan
similarity 0.56
Abstract

When inference demand exceeds available compute capacity, model providers must decide which requests should be served first. Users have different tolerances for delay from an LLM API, but current priority pricing schemes compress these differences into coarse fixed-price service tiers. We design an inference auction that allows users to bid for faster service. Our auction allocates priority in an economically efficient way without sacrificing latency, and we develop fast algorithms for implementing prices that incentivize truthful bidding. We also design an autobidding agent for our inference auction, where users specify an inference budget and the autobidder dynamically adjusts its bids over time to maximize user utility subject to the budget constraint. Experiments validate the practicality of our auction: it increases system welfare while maintaining the cache utilization and latency advantages of SGLang, a state-of-the-art inference serving framework.

0.27