CS Paper Radar

Circumventing the Computational Hardness of Computational Arbitrage

Nastaran Okati, Ricardo Olmedo, Moritz Hardt

cs.AI ·submitted 2026-10-29 18:14 UTC · v1

Abstract

AI model marketplaces host providers with heterogeneous costs and capabilities. These differences create an opportunity for computational arbitrage (Olmedo et al., 2026), in which an intermediary purchases inference from a portfolio of models and resells it to users at a profit. Beyond creating profit opportunities for the arbitrageur, computational arbitrage offers financial value to both consumers and providers and could therefore significantly influence AI model markets. While prior work empirically demonstrates the feasibility of computational arbitrage for small model pools, scaling it to large marketplaces requires arbitrage strategies that are both computationally tractable and inexpensive to identify and deploy. In this work, we formalize computational arbitrage as an allocation problem and prove that it is generally NP-hard. However, we show that the optimal allocation can be computed efficiently under a natural diminishing-returns condition on how model performance scales with inference spending. We further develop a sample-efficient method for estimating model performance from limited data, reducing the upfront cost of identifying arbitrage strategies. Our analysis also yields several economic insights: at the optimum, every funded model delivers the same marginal utility per dollar; arbitrage directs revenue away from providers offering little utility relative to their prices; and it rewards complementary specialization.

Closest papers

Nearest neighbours by meaning across the whole index.

Spot Markets for AI Inference: Dynamic Capacity Allocation and Pricing on a Shared Accelerator Fleet

eess.SY ·2026-11-08 ·Quanyan Zhu
similarity 0.64
Abstract · 39 pages, 12 figures, 4 tables

Inference providers size their accelerator fleets for the interactive peak and sell spare capacity through fixed discounts, such as batch tiers at half price. However, inference differs from conventional cloud capacity in four respects: capacity depends on the latency tier through batching, moving weights between models is slow and costly, spot demand can wait until its deadline, and power can bind. In this paper, we develop a framework for dynamic capacity allocation and pricing of AI inference on a shared accelerator fleet. We consider a provider that serves several models under a power cap and sells each model in an interactive tier with a speed promise and in a spot tier for preemptible work with a deadline. In each period, the provider chooses how many replicas of each model to keep loaded and what spot price to quote. We show that one interactive token displaces a fixed number $ρ_m>1$ of spot tokens, and that the optimal spot price lies midway between the interactive price and the effective cost of capacity in the deadline window, which is close to the prevailing half price only when the fleet is slack. We further show that a spot tier raises the optimal reliability of the interactive tier, and that placement should follow persistent demand shifts while prices absorb transients. Building on these results, we design a model predictive controller based on a linear program with explicit approximation bounds, which solves each period in milliseconds. Numerical experiments on a simulated week with a measured daily demand profile, a flash crowd, and a grid curtailment show that the controller raises profit by 7.4% over fixed half-price practice, captures 93% of the gain available with perfect forecasts, keeps the interactive promise through both events, and leaves spot buyers better off.

0.28

Cost-Aware Mixture-of-Experts Coordination for Model Markets

cs.DB cs.LG ·2026-10-08 ·Yizhou Ma, Wenbo Wu, Xikun Jiang, Zhuoqin Yang, Luis-Daniel Ibáñez
similarity 0.62
Abstract

Existing model marketplaces typically trade and select individual models as indivisible units, limiting their ability to exploit complementarities among heterogeneous experts. This paper proposes an MoE-based model market framework that lifts Mixture-of-Experts from a model-level learning architecture to a market-level coordination mechanism. In this framework, brokers use gating networks to coordinate multiple heterogeneous experts and deliver a composite model service. We formalize the market participants, service workflow, expert cost structure, and a welfare objective that combines predictive utility with heterogeneous execution costs. We then derive a cost-aware gating mechanism and market-aware training objective, and introduce a cost-adjusted revenue allocation rule that distributes residual revenue according to realized expert participation and execution cost. We also establish basic theoretical properties of the allocation rule, including budget balance, participation monotonicity, and cost sensitivity. Experiments over five random seeds on fifteen tabular and image benchmarks use independently trained and frozen neural and tree-based experts together with latency-derived execution costs. MoE Market achieves the highest mean welfare on all fifteen datasets and a lower mean expected cost than Standard MoE in every case, while maintaining competitive predictive performance. The allocation experiments further demonstrate systematic sensitivity to expert participation and cost, together with substantially lower computational overhead than exact Shapley allocation. These results suggest that MoE can serve as a market-level coordination principle for collaborative, cost-aware, and economically grounded model marketplaces.

0.22

Pandora's AI Model Routing Box: Efficient Allocation with Costly Value Estimation

cs.AI ·2026-08-20 ·Adam Fisch, Shubhendu Trivedi, Fantine Huot, William W. Cohen, Michael Kaisers +3 more
benchmarkhighly cited similarity 0.61
Abstract

Heterogeneous AI systems composed of multiple models, architectures, harnesses, or inference-time settings can improve quality and efficiency by routing queries to the specialist who can answer most effectively at the lowest cost. Routing requires estimating each specialist's expected return, but this value estimation has a cost. Cheap estimators (e.g., embedding-based predictors) are fast but noisy, while accurate estimators (e.g., fine-tuned models with access to retrieval results or partial reasoning traces) are expensive. We formalize this tradeoff as an instance of Pandora's Box, the classical problem of optimal search with costly inspection. Under a Gaussian signal model, the resulting policies have closed-form value-of-information expressions that determine, for each specialist and input, whether refining the value estimate is worth its cost. We call the centralized policy Pandora's Router. We extend this to a decentralized setting, Pandora's Bidder, where specialists independently decide whether to invest in self-assessment before accepting an offered price to claim a query. Experiments across three domains---a standard multi-LLM benchmark, retrieval-augmented specialists, and LLMs with variable inference-time reasoning---show that Pandora's Router matches the routing quality of exhaustive estimation, while querying the expensive estimator far less often. In the decentralized setting, value-of-information reasoning improves allocative efficiency when competing estimates are accurate; when competing estimates are noisy, however, it can increase the strategic specialist's utility at the expense of others.

0.34

Computing Multi-Slot First-Price Pacing Equilibria at Scale via Entropic Smoothing

cs.GT math.OC ·2026-10-16 ·Yuchen Xie, Shenyinying Tu, Yuan Gao, Yi Zhang, Deepak Kumar
similarity 0.60
Abstract · 40 pages, 6 figures, 5 tables

Pacing equilibria describe how budget-constrained advertisers clear an ad market, but computing one at production scale is hard when every request fills several slots: the allocation jumps whenever two campaigns' scores cross. We consider the first-price pacing equilibrium (FPPE) of auctions with $K$ homogeneous slots and unit-demand campaigns, whose Eisenberg-Gale dual reduces, via a TopK identity, to a convex program over bids. Regularizing each request's allocation with the binary (Fermi-Dirac) entropy gives a smooth, strictly convex dual whose gradient is exactly spend minus budget and whose evaluation splits into independent one-dimensional threshold solves, one per request. The smoothed equilibrium converges to the hard one at an explicit $O(\sqrt{T})$ rate, and a duality gap certifies how far any bids are from the hard equilibrium. We implement an efficient multi-GPU solver and test it on a production ad workload. We use it to compute an equilibrium price anchor: each campaign's hindsight equilibrium cost per key result.

0.12

When AI Agents Meet MEV: Cross-Chain Arbitrage in the Agentic Economy

cs.CR cs.CE ·2026-09-15 ·Wei Ye, Jingyan Xu, Yuanhong Wu
published similarity 0.59
Abstract · 17 pages, 4 figures, 4 tables; Accepted to the 7th International Conference on Mathematical Research for Blockchain Economy (MARBLE 2026)

We study cross-chain arbitrage when autonomous AI agents, rather than humans or bots, are the searchers. We model agents as both arbitrage extractors and Maximal Extractable Value targets, derive the optimal trade size for a risk-averse agent under mean-variance utility with stochastic bridge delays, and formalize multi-chain path selection as a belief-weighted online learning problem whose belief estimates converge under a Robbins-Monro schedule. Using 23,000 Uniswap V3 swap events across Ethereum, Arbitrum, and Base, we find that Ethereum-Arbitrum price gaps average 0.044% at 10-second resolution and Arbitrum--Base gaps average 0.013%, so $10,000 trades clear in 63% of L2-L2 windows via CCTP while L1-L2 routes require $50,000 or more for comparable viability. Our adaptive path-selection algorithm outperforms standard baselines by 11% on average, and moderate randomization cuts MEV exposure by over 50% with only modest profit loss.

0.42

Non-Linear Pricing Restores Tractability for a Data Seller

cs.GT ·2026-09-29 ·Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma, Jiaxin Song
top venue similarity 0.59
Abstract · Accepted to NeurIPS 2026

We consider a data seller who designs pricing mechanisms over multiple datasets to maximize revenue from budget-constrained buyers. The seller offers multiple datasets and assigns each a pricing function that maps the quantity purchased to a total payment. The goal is to design these pricing functions to maximize revenue, anticipating that buyers---who trade off accuracy gains against cost---choose bundles optimally subject to their budget constraints. Prior work [Chaudhury et al., 2026] studies such optimal pricing under the restriction that each dataset is assigned a linear price, and shows that computing optimal linear prices is computationally intractable. In contrast, we allow each dataset to be priced via a general function and show that this additional flexibility can not only increase the revenue but also restore tractability, yielding a surprising simultaneous improvement in economic performance and computational efficiency. Even when pricing functions are only required to be monotone and lower-continuous, optimal pricing admits a highly structured and simple form: each pricing function is piecewise linear and convex (PLC), and the optimal solution can be computed in polynomial time. Moreover, the total number of kinks across all pricing functions is bounded by the number of buyers. Consequently, when datasets significantly outnumber buyers, most pricing functions are effectively linear. We further empirically study the structure of optimal pricing by analyzing the number of kinks and the revenue gap between optimal nonlinear pricing and optimal linear pricing on simulations generated from a real dataset.

0.32

Equilibrium Pricing in Oligopolistic Data Markets

cs.GT ·2026-08-14 ·Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma, Jiaxin Song
top venue similarity 0.59
Abstract · This work received an oral presentation at ICML 2026

We study equilibrium pricing in oligopolistic data markets with budget-constrained buyers (e.g., machine learning companies purchasing data to improve model accuracy) and strategic data sellers. Sellers compete by setting prices for their datasets, giving rise to a pricing game whose pure Nash equilibria correspond to equilibrium prices. While equilibrium prices are guaranteed for rivalrous goods via competitive equilibrium, we show that the non-rivalry of data fundamentally alters this picture: an exact Nash equilibrium (NE) need not exist, and in fact, 1.363-approximate NE may also not exist under uniform pricing. We therefore investigate relaxed equilibrium notions. Allowing sellers to use beyond-uniform pricing---specifically, piecewise-linear convex pricing functions---guarantees approximate stability within a constant factor: there exists a pricing profile in which no seller can improve revenue by a factor of two by deviating to any uniform price (a 2-approximate NE against uniform deviations). Finally, our simulations demonstrate fast convergence and empirical approximation guarantees that outperform the worst-case bound of 2.

0.59

Pacing Equilibria in Abstract Mechanisms

cs.GT ·2026-09-23 ·Salam Afiouni, Christian Kroer
benchmarktheory similarity 0.59
Abstract

Digital platforms increasingly rely on automated budget-management systems to regulate participation across allocation opportunities. A common tool is multiplicative pacing, which scales buyers' bids so that campaign-level budgets are spent gradually. Although pacing is operationally simple, its aggregate behavior depends on the underlying mechanism. In first-price single-item auction markets, pacing enjoys strong structural and computational properties that often fail in second-price auctions. It is unclear whether these properties extend to richer platform mechanisms. We develop a unified theory of pacing equilibria across a hierarchy of mechanisms. We first show that, even in first-price position auctions, the market-equilibrium interpretation of the single-item benchmark can fail. We then identify bid-maximizing pay-your-bid mechanisms as a broad class in which pacing equilibria exist, are unique, and admit an Eisenberg-Gale-type convex-program characterization. This implies efficient computation, Pareto-efficiency, and liquid-welfare guarantees, enabling pacing integration into large-scale optimization-based allocation routines. Finally, for abstract mechanisms satisfying a payment monotonicity condition, we prove equilibrium existence by smoothing discontinuities. With additional conditions and appropriate tie-breaking, we obtain uniqueness, revenue maximality among budget-feasible pacing vectors, and shill-proof implementability, and provide convergent budget-adjustment dynamics for approximate equilibria. Overall, many favorable properties of first-price pacing extend beyond single-item auctions under appropriate mechanism-level conditions.

0.29