acceptodds
Under review as a conference paper at ICLR 2027

Price of Anarchy of First-Price Auctions in Agentic Markets

Abstract

An agentic marketplace is a decentralized, serving-time market where AI agents bid to claim each user query. An agent's bid is based on its expected value for the query, which is the expected reward for producing a high-quality response, less the agent's expected inference costs. First-price auctions (FPAs), in which the highest bidder wins and pays its bid, are a natural mechanism for this, since they are simple and transparent to run and require no central knowledge of private capabilities and costs. But a potential weakness is that FPAs are not truthful. Participants may bid less than their true value in the hope of a larger profit, so the query can be allocated to someone other than the bidder who values it most highly. This welfare loss is quantified by the _price-of-anarchy_. In this paper, however, we argue that agentic markets are likely to possess special structural features that reduce it. The first is _value concentration_. If the gap between the top two values is usually small (e.g., because the best models are often distilled into cheaper alternatives which perform similarly), then the welfare gap can go to zero. The second is _weak dependence_ between values after conditioning on the prompt, in which case the efficiency guarantee approaches . In both cases, we derive bounds on the price of anarchy that are significantly better than the well-known factor from the general case, and validate them empirically on prompt routing in the EmbedLLM dataset.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Multi-Agent Markets, Agentic Market, Auctions, LLM

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_WjXUOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies how much welfare is lost when strategic bid shading affects task allocation among AI agents in first-price auctions. It gives efficiency guarantees when the highest values are concentrated or values are nearly independent, and tests these ideas through auction simulations using EmbedLLM data.

Critical strengths
  1. The value-concentration result allows arbitrary dependence between values and does not require every agent to be strong. It captures the key question of whether there is enough competition at the top. (pp. 4–5, Theorem 4)
  2. The weak-dependence proof addresses the fact that changing the distribution can make the original strategies cease to be an equilibrium. This is a substantive technical contribution. (Appendix E)
Critical weaknesses
  1. The simulations do not adequately establish approximate equilibrium. Strategies use shading ratios within five value bins, convergence is judged by bid changes, and deviation gains outside this restricted class are not reported. Samples are also removed when adversarial welfare exceeds ordinary welfare, deleting up to 9%; that ordering has no theoretical guarantee. (p. 17)
  2. The weak-dependence theory is not yet connected to the experiments. Theorem 5 gives no computable error rate, and the predictive metrics in Appendix B.1 do not imply that the required total variation distance is small. They therefore do not yet provide a practical efficiency guarantee. (pp. 5, 15)
Questions for authors
  1. How large is the maximum unilateral deviation gain after lifting the bin-based shading restriction? Do the main lower-tail findings survive when samples with higher adversarial welfare are retained?
  2. How do the predictive metrics relate to the distance required by Theorem 5? If they cannot yield a numerical guarantee, should the empirical claim be explicitly limited to qualitative support?
1 comment

Thank you for your positive evaluation and thoughtful review. Below we address two of the methodological critiques that you have raised.

W1 & Q1: Approximate Equilibrium, Unrestricted Deviation Gains

Unlike small synthetic auctions where equilibria can be brute-forced on fine grids, our experiments solve over 100k100\text{k} empirical auctions with up to n=110n = 110 asymmetric models and ∼1,500\sim 1{,}500 prompts per cluster. Grouping values into 5 equal-mass bins preserves Bayesian uncertainty over the prompt distribution (whereas bidding freely per prompt would effectively let models condition on exact prompt realizations) while keeping equilibrium search tractable; within each bin, bidders still optimize over a fine grid including exact rival-outbidding thresholds. We will explicitly report the maximum unilateral regret after lifting the 5-bin linear shading restriction, along with a bin-count sensitivity check (K∈{5,10,20}K \in \{5, 10, 20\}) in Appendix C.

Do lower-tail findings survive without filtering?

Yes, completely. You are right that Wadv≤WtypicalW_{\text{adv}} \le W_{\text{typical}} has no theoretical guarantee, since the two solvers can converge to different equilibria. However, because typical welfare is already ∼98–99\sim 98\text{--}99%, every filtered sample with Wadv>WtypicalW_{\text{adv}} > W_{\text{typical}} sits in the upper tail of welfare—never near the 0.10.1-percentile. Dropping those runs only shifted the adversarial distribution slightly downward, making our reported lower-tail numbers slightly more conservative. We have updated the text to make this more explicit. We will also report the full unfiltered results in Section 6 and Appendix C.

W2 & Q2: Connecting Weak-Dependence Theory to Empirical Metrics

Yes; we agree that the empirical claim for Section 4 should be explicitly scoped to qualitative support, and we have clarified this in Sections 1, 4, 6, and Appendix B.1.

Theorem 5 is a qualitative stability guarantee without a closed-form error rate. Estimating the joint total variation distance across up to n=110n = 110 models from ∼1,500\sim 1{,}500 prompts per cluster is infeasible due to the curse of dimensionality. Held-out pairwise R2R^2 (Appendix B.1) was the cleanest tractable proxy we found to verify that prompt embeddings absorb most inter-model co-movement (∼90\sim 90% of rival-explained variance), and we welcome suggestions for better empirical measures. Accordingly, we do not claim a numerical guarantee from Theorem 5 (nor do we attempt to empirically disentangle near-independence from value concentration, which naturally co-occur); all quantitative bound comparisons in Section 6 rely solely on Theorem 4. We have updated the draft to reflect this more clearly.

Please do let us know if you would have any further questions.

Reviewer_pryqOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

There are users (human (?)), and there are agents. I think the agents are artificial. Users submit queries. Agents get utility from answering queries, I think the util depends on agent/query combination. Agents make bids for queries, presumably higher bids for queries they value higher. If queries are sold be first-price auction, agents would be expected to shade their bids. This might sometimes result in an agent winning a query, who doesn't value it highest. The abstract mentions something called "the prompt", which somehow affects the values agents have for queries. There's a general setting of auctions where the PoA is 1-1/e (Bayes NE, IIRC), and the paper identifies properties of these agentic marketplaces, that lead to an improved PoA. With "value concentration" it is, as the paper says, intuitive that the PoA is not so bad. The near-independence result is more interesting, interpolating with the Jin/Lu 1-1/2^2 result.

Critical strengths

Gets some positive results (as in, low Price of Anarchy) for a well-motivated kind of online marketplace.

Critical weaknesses

Not ideal for a Machine Learning conference, it's not a strongly ML scenario.

In experiments, a version of fictitious play is used to seek a bad equilibrium, but technically, the worst equilibrium might not be discoverable that way.

All proofs are relegated to the appendix. I would prefer more insight in the paper, especially in light of the unreliable computation of bad equilibria, noted above.

Questions for authors

Questions: The 1-1/e and 1-1/e^2 PoA results are for one seller, one buyer, one item, as I recall. So, the scenario studied in this paper, of multiple items, bidders, etc, is more general is that right? And I suppose from that, PoA bounds like 1-1/e should be harder to obtain, but maybe the multiple-agent aspect is exploitable (?)

Are any of the bounds in section 2 tight?

When computing approximate equilibria in the experiments section, what is the approximation guarantee?

Suggestions: In the abstract, I'd say that the fact that FPAs are not truthful, is not highly relevant to the issue of price of anarchy. Note that second price single-item VCG auctions are "truthful" but still have bad equilibria (in which an arbitrary bidder bids high and the others bid zero), so the PoA of truthful mechanisms can in fact be bad.

Weakly-dependent seems to mean different things in different parts of the probability literature. In Wikipedia, it is used to describe time-series. I think what is a better name for the values considered in section 4 is approximate conditional independence.

In line 267 vˉ\bar{v} can be introduced with a bit more clarity. Currently it reads like it has already been introduced.

Is ηncont\eta_n^\mathrm{cont} continuous? If not, the superscript cont is confusing.

2 comments

We appreciate the constructive feedback. Below we address your various questions and concerns directly.

W1 and Summary: Connection to Machine Learning

Thanks for this comment. We have made the ML setup and context self-contained in Section 1. Perhaps our introduction assumed too much familiarity with the ML routing literature. However, LLM routing -- which involves selecting which model among many candidates should answer a user query, while trading off between accuracy and inference cost -- is now an active and core ML area ([1, 2, 3]). Very recent work has proposed decentralizing routing via serving-time agentic marketplaces ([4, 5, 6]). Here ML directly shapes the auction structure. Each LLM estimates its accuracy on a prompt from learning representations (Gemini embeddings in Section 6.1). Conditioning on prompt features XX removes shared task-difficulty variance. Both of these enable ML-aware bidding and induce the approximate conditional independence analyzed in Section 4 and Appendix B.1.

W2 & Q3: On equilibrium computation.

Yes, you are correct that damped fictitious play may not discover the worst equilibrium (or even an equilibrium at all for that matter). We explicitly acknowledge, and discuss, this limitation in Appendix C. Nevertheless, fictitious play is a popular approach to computing approximate equilibria, especially in settings like ours where, e.g., a brute-force search is infeasible. In general, our empirical results should be read as a best-attempt (especially with our "adversarial" solver) to measure FPA PoA in practice. We see that it is nearly always high; and we think this is a practically useful observation. Our theoretical results then do provably hold across all exact BNEs, regardless of whether the solver we choose can find them -- and these higher bounds help justify the high empirical welfare we see.

Q1 & Q2: Multi item extensions and tightness:

We analyze the one item and nn asymmetric bidders setting, as in the classical 1−1/e1 - 1/e [7] and 1−1/e21 - 1/e^2 [8] bounds. We don’t study simultaneous or sequential multi-item effects. We agree that extending our analysis to multiple items is a very interesting direction for future work, which we have highlighted in Section 8.

Are the bounds tight (Question 2): No, they are not. Our new bounds (e.g. sections 3–4, Proposition 1, Theorems 4–5) match known tight values only at the boundary regimes. We have added a line about this in the updated draft.

More proof intuition in the main paper.

Thanks for the suggestion. If the paper is accepted, we will use the extra space to expand Sections 3.2 and 4 with clear proof sketches. We have included some comments in the updated draft.

Truthfulness vs PoA:

Great catch, thanks! We have revised the abstract and introduction to make this explicit.

Terminology and notation:

Fixed and updated the draft, thanks!

References used in this response:

[1] L. Chen, M. Zaharia, and J. Zou. FrugalGPT: How to use large language models while reducing cost and improving performance. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https://openreview.net/forum?id=cSimKw5p6R.

[2] I. Ong, A. Almahairi, V. Wu, W.-L. Chiang, T. Wu, J. E. Gonzalez, M. W. Kadous, and I. Stoica. RouteLLM: Learning to route LLMs from preference data. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=8sSqNntaMr.

[3] R. Zhuang, T. Wu, Z. Wen, A. Li, J. Jiao, and K. Ramchandran. Embedllm: Learning compact representations of large language models. In International Conference on Learning Representations, volume 2025, pages 76913–76926, 2025.

[4] M. Chang, S. Kaushik, S. M. Weinberg, T. Griffiths, and S. Levine. Decentralized reinforcement learning: Global decision-making via local economic transactions. In International Conference on Machine Learning, pages 1437–1447. PMLR, 2020.

[5] Z. Qi, H. Su, A. Qu, C. Wang, Y. Yao, H. Zheng, K. Chattopadhyay, G. Xu, Z. Wang, W. Ye, V. J. Reddi, J. Li, P. P. Liang, H. Lakkaraju, S. Kakade, and Y. Du. Economy of minds: Emerging multi-agent intelligence with economic interactions. ArXiv preprint: 2606.02859, 2026. URL https://arxiv.org/abs/2606.02859.

[6] X. Liu, H. Li, S. Li, H. Fang, F. Xu, F. Shi, and J. Evans. Markets, not planners: Decentralized orchestration of llm agents with private information. arXiv preprint arXiv:2608.23867, 2026.

[7] V. Syrgkanis and E. Tardos. Composable and efficient mechanisms. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, page 211–220, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320290. doi: 10.1145/2488608.2488635. URL https://doi.org/10.1145/2488608.2488635.

[8] Y. Jin and P. Lu. First price auction is 1 − 1/𝑒2 efficient. J. ACM, 70(5), Oct. 2023a. ISSN 0004-5411. doi: 10.1145/3617902. URL https://doi.org/10.1145/3617902.

Please do let us know if we can provide any further clarification

Reviewer_msD7OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper provides bounds on the price of anarchy for single-item first price auctions on instances satisfying specific instances. Price of Anarchy is the ratio between the valuation of the winner selected by the auction in the worst possible equilibrium and the maximum valuation. For first-price auctions, that are not strategy-proof, is known that this ratio can be as large as 1-1/e (i.e., by running first price auction one can sell the item to a buyer whose valuation is about 37% smaller than the maximum valuation), and it decrease to 1-1/e^2 when valuations are independent.

The paper then shows that

  • the ratio 1-1/e scales down when the distance between the optimal valuation and the second largest one decreases;
  • the ratio 1-1/e^2 essentially holds even if distribution are non independent as long as dependence is weak (i.e., the difference between product of marginals and joint distribution is small)

The paper then shows that when buyers are LLMs the empirical price of anarchy is usually much smaller than given bounds.

Critical strengths

The results appears to be sound.

Critical weaknesses
  1. Theoretical results are incremental with respect to previous results. Moreover, they are not surprising: it is expected that by increasing competition the value of equilibrium also increases; and similarly, it is expected that what holds for independent valuation should approximatively holds even for near-independent valuations. Clearly, the paper includes formal bounds on how these bounds holds. Still I believe that the fact that the results are both incremental and unsurprising makes them not sufficient for justify acceptance for this conference.

  2. Experimental results are only scarcely tied with theoretical results. While the former results show better price of anarchy, it is not clear if this is due to high competition or near independence or something else. Actually, bounds are much better than the theoretical ones. However, this is expected, and this is not necessarily related to agentic bidding. There are a lot of experiments showing that bidding in fpa rarely matches PoA bounds.

  3. All the results assume no overbidding assumption. While this is a very common assumption in literature, it is also an highly criticized. Indeed, in many settings (and specifically for the advertising setting considered in this paper), buyers usually participate in many auctions. And overbidding in such cases can be useful to force high valuation guys to consume their budget, so to make future participation much less competitive

Minor: line 161: "user's value" -> "auctioneer's value" line 267: "following holds." What? line 267: "bar{v}(X)" -> undefined

Questions for authors
  1. How do experiments are related to theoretical results? Can you describe the difference between your LLM based experimental setting and other non-LLM experimental valuations of FPA performances?
3 comments

Thank you for verifying the soundness of our results and catching the minor issues, which we have corrected in the updated draft. Below, we address your specific questions and concerns.

W1: Significance of our results

Results incremental and unsurprising

We agree that intuition strongly suggests that the PoA of the FPA should not be that bad, but the theory required to rigorously prove this is surprisingly complex and nuanced, and prior theory offers only isolated point guarantees (1,1−1/e2, or 1−1/e)(1, 1-1/e^2, \text{ or } 1-1/e) [1,2] without characterizing the much wider spectrum of intermediate regimes seen in practice, of which the agentic market setting is one. Agentic markets are arguably a key feature of the future of AI agent coordination, and having a more complete characterization of the tradeoffs of different mechanisms should be of interest to the ICLR community -- both those who are practitioners that want to better understand the available market mechanisms, and theorists who will derive independent interest from our results.

With regards to what we believe is of independent interest (and surprisingly non-trivial to prove):

  • Stability of the 1−1/e21 - 1/e^2 bound. You are justified in expecting that what holds for independent valuation should approximatively hold even for near-independent valuations! But the 1−1/e21 - 1/e^2 proof of Jin & Lu [2] is fundamentally different than the smoothness-based proofs for the 1−1/e1 - 1/e bound (for which such a result would indeed be trivial; see Appendix D.3). Proving uniform stability for the 1−1/e21 - 1/e^2 bound requires arguments that do not follow from existing techniques.

  • Increasing competition mitigates the PoA. Again, this is indeed what intuition tells us. But the behavior of equilibria under correlated priors are notoriously unintuitive. Proving this result requires a quite interesting (at least, in our opinion) argument based on deviation bids. It cannot be obtained via simple techniques, despite the simplicity of the result. Even as such, our bounds are still conservative -- and leave interesting theoretical questions to follow-up work

W2 & Q1: How experiments tie to theory & differ from standard FPA studies

Yes, ample prior work shows that bidding in FPAs rarely matches worst-case PoA bounds -- yet very little prior work tries to narrow that theoretical gap, as we do. Moreover, empirical FPA behavior varies across domains, and little if any prior work has studied and characterized this emerging agentic market setting, making these empirical results useful in their own right. While our bounds indeed remain conservative -- and we certainly cannot claim that the high welfare efficiency we observe is solely due to the two factors we formalize (which naturally co-occur in practice) -- it is still significant that our theoretical bounds track the empirical patterns we observe: realized worst-case PoA rises monotonically with our Theorem 4 bound across sub-markets (Figure 2 Right), shading drops sharply as runner-up competition tightens at fixed oracle welfare (Table 2), and prompt embeddings absorb the bulk of inter-model correlation (Appendix B.1).

Regarding how our LLM-based experimental setting differs from prior non-LLM FPA evaluations:

Organic prompt driven valuations vs. synthetic settings:

Existing experimental FPA studies will typically draw valuations from synthetic parametric priors. Here, valuations arise directly as a result of heterogeneous model capabilities and inference costs across 30k real prompts in EmbedLLM. This provides a realistic setting where we can see co-movement from shared prompt difficulty alongside fine-grained specialist advantages.

Adversarial equilibrium:

Rather than reporting only typical bidding trajectories, we explicitly search for welfare-minimizing approximate equilibria (Section 6.1) to test whether worst-case shading degrades routing quality.

Comparison against ML routing baselines:

Unlike generic auction studies that compare FPA only to the oracle, our setting benchmarks decentralized bidding against centralized ML cluster-routing (Table 1), showing that FPA (98.898.8% overall, 93.293.2% worst-cluster) substantially outperforms centralized routing (89.489.4% overall, 64.064.0% worst-cluster) because private self-evaluation lets specialists win prompts where a (cluster-level) generalist fails.

W3: No-Overbidding We want to clarify that our paper does not study display advertising or budget-constrained buyers; display ads are mentioned only once (line 056) as an example. Our setting is serving-time LLM query routing (Section 2, Eq 1). Here, winning with bid bib_i gives the surplus vi−biv_i - b_i (expected reward minus inference cost, less the bid). This means overbidding (bi−vib_i - v_i) guarantees an expected loss. Therefore, we believe the standard no-overbidding assumption [1, 2] is appropriate for this application. That said, analyzing the PoA without it would be an interesting direction for future work (along with others, for example, when over-bidding due to estimation error).

Please do let us know if we can clarify any other point.

References used in the above response:

[1] V. Syrgkanis and E. Tardos. Composable and efficient mechanisms. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, page 211–220, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320290. doi: 10.1145/2488608.2488635. URL https://doi.org/10.1145/2488608.2488635.

[2] Y. Jin and P. Lu. First price auction is 1 − 1/𝑒2 efficient. J. ACM, 70(5), Oct. 2023a. ISSN 0004-5411. doi: 10.1145/3617902. URL https://doi.org/10.1145/3617902.

Thanks for your response. No further clarification is needed.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.