Paper Overview
Field: Machine Learning Authors: Shubhendu Trivedi, Jacob Eisenstein, Alekh Agarwal, Ian Gemp, Michael Kaisers Published: 2026-10-14 arXiv: 2610.20587
Summary
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: 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 allocation mechanism for such markets — they are simple and transparent, 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 most. This welfare loss is quantified by the price of anarchy (PoA).
This paper argues that agentic markets may exhibit features that reduce the PoA:
1. Competitive floor: When multiple bidders typically value a prompt above some baseline share of optimal welfare (e.g., because the best models are often distilled into cheaper substitutes with similar performance), competition among them limits welfare loss, which can approach zero as the floor increases.
2. Approximate conditional independence of value given the prompt: This occurs when most of the predictable variation in expected value is determined by prompt difficulty. As the value distribution approaches conditional independence, the authors derive efficiency guarantees approaching a 1-1/e^2 factor of optimal welfare.
Both features yield welfare lower bounds that significantly improve on the well-known general 1-1/e bound. The authors validate these results by simulating auctions with strategic bidders on the EmbedLLM prompt-routing dataset.
Original Abstract (excerpt)
> 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 price-of-anarchy (PoA). In this paper...
*Automatically collected on 2026-10-16*