Circumventing the Computational Hardness of Computational Arbitrage

AI model marketplaces host many providers with heterogeneous costs and capabilities. These differences create an opportunity for computational arbitrage~\cite{olmedo2026computational}, where an intermediary benefits from these asymmetries by allocating inference budget across model providers. Beyond creating profit opportunities for the arbitrageur, computational arbitrage offers financial value to both consumers and model providers and could therefore significantly influence AI model markets. While~\citet{olmedo2026computational} empirically demonstrate the feasibility of computational arbitrage for small model pools, scaling this strategy 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 show that it is generally NP-hard. We then identify a natural structural condition on how model performance scales with inference spending, under which an optimal strategy is efficiently computable. Moreover, we characterize deployment strategies that reduce realized arbitrage costs. Our analysis also yields several economic insights: at the optimum, every funded model delivers the same marginal utility per dollar; arbitrage rewards complementary specialization; and it withholds budget from providers that overprice their services.