PaperlayerView exact revision on arXiv

Source-linked AI summary

Price of Anarchy of First-Price Auctions in Agentic Markets

Shubhendu Trivedi, Jacob Eisenstein, Alekh Agarwal, Ian Gemp, Michael Kaisers, Adam Fisch

arXiv:2610.20587v1cs.GTcs.AIcs.LG

TL;DR

First-price auctions offer a simple way to allocate prompts in agentic markets, but strategic bid shading can lower welfare. This paper derives improved guarantees under competitive floors and near-independence, studies platform interventions, and evaluates the results on EmbedLLM. It finds that these structural features can support high efficiency, including in adversarial equilibria.

  • Problem

    First-price auctions can allocate prompts to lower-valued agents when bidders shade their bids, creating welfare loss that worst-case bounds quantify.

    Source: §1 · p. 2, §2.1 · p. 3

  • Method

    The paper derives price-of-anarchy bounds for competitive floors and values that are nearly independent after conditioning on the query, and examines filtering bidders or entering an in-house model.

    Source: §1 · p. 2, §8 · p. 11

  • Results

    Under near-independence, the 1 − 1/e^2 guarantee for independent values degrades smoothly with weak dependence, while competitive floors improve welfare guarantees toward full efficiency.

    Source: §1 · p. 2, §8 · p. 11

  • Takeaways & Limitations

    The paper concludes that first-price auctions can preserve substantially more welfare under agentic-market structure, and platforms can take simple steps to protect market efficiency.

    Source: §8 · p. 11

    A deterministic competitive floor requiring at least two bidders on every query is unrealistic because unusual queries may have only one capable model.

    Source: §3.2 · p. 5

Abstract

from arXiv · show

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.

1. Introduction

Agentic markets let agents bid directly for prompts, avoiding the need for a central platform to track every provider’s capabilities and costs. The paper analyzes whether first-price auctions can preserve welfare despite strategic bid shading, focusing on structural conditions and platform choices that improve efficiency.

1. Introduction

  • In an agentic market, responding agents bid to claim prompts and are rewarded according to response quality, while privately estimating their expected quality and cost.Unlike a centralized router, this decentralized approach scales with the number of participants rather than the platform’s ability to track them.Source: §1 · p. 1
  • First-price auctions are simple and transparent, but bid shading can cause a lower-valued agent to win and reduce welfare.The worst-case price-of-anarchy bound can be as low as 1 − 1/e ≈ 63%.Source: §1 · p. 2
  • Competitive floors improve welfare guarantees when several bidders usually value a query above a baseline, with losses tending to zero as the floor rises.Comparable substitutes, including models with similar capabilities, can support such competition.Source: §1 · p. 2
  • Near-independence after conditioning on the query preserves approximately the 1 − 1/e^2 guarantee for independent values.Shared prompt features such as difficulty may account for much of the co-movement in model values.Source: §1 · p. 2
  • Platforms can help create favorable market conditions by filtering weak responders or entering in-house models to increase competition.The paper’s EmbedLLM analysis finds competitive floors and conditional independence emerging with high efficiency, including in adversarial equilibria.Source: §1 · pp. 2–3

2. Preliminaries

The preliminaries model each agent’s value as expected reward minus service cost, with strategic bids represented in a Bayesian game. They define welfare and price of anarchy, then distinguish worst-case efficiency guarantees for general and independent value distributions.

2. Preliminaries

  • Each bidder’s value is its expected reward minus service cost, and a winning bidder’s expected surplus is value minus price.A strategy maps a bidder’s value to a possibly randomized bid; a Bayes-Nash equilibrium is one in which each bid maximizes expected surplus given others’ strategies and the value prior.Source: §2 · p. 3

2.1. Social welfare and the price of anarchy

  • In the single-item setting, welfare is the winning bidder’s value, while optimal welfare is the highest bidder value.The price of anarchy measures the worst-case ratio of expected equilibrium welfare to optimal welfare.Source: §2.1 · pp. 3–4
  • First-price auctions guarantee at least 63.2% of optimal welfare in general and 86.5% when bidder values are independent.These are worst-case bounds; the paper notes that agentic-market structure can push realized welfare higher.Source: §2.1 · p. 4

3. First-price auctions with competitive floors

A competitive floor exists when several bidders usually value a query above a share of the expected top value. The section derives welfare bounds that improve as the floor rises and competition becomes more reliable.

3.1. Deterministic competitive floors

  • A 50% deterministic floor raises the welfare bound from approximately 63% to approximately 82%.The argument uses a runner-up who always values the query at least half the expected top value.Source: §3.1 · pp. 4–5

3.2. Probabilistic competitive floors

  • The probabilistic-floor bound subtracts a penalty that vanishes when the floor never fails and shrinks as more bidders meet it at the same rate.Theorem 3’s penalty reflects how reliably the competition holds.Source: §3.2 · p. 5
  • With a 90% floor met 90% of the time, the bound is approximately 63% for m=2, 74% for m=4, and 84% for m=16.Figure 1 illustrates that more floor-clearing competitors preserve efficiency even when the floor sometimes fails.Source: §3.2 · p. 5, Figure 1 · p. 5
  • The floor can adapt to public query information, and positively dependent values raise the non-strategic bound relative to independent values with the same marginals.Conditioning on public information makes the floor depend on query difficulty; the related dependence result is in Section B.2.Source: §3.2 · p. 6

4. First-price auctions with near-independent values

The section studies whether the independent-values efficiency guarantee persists when values are only approximately independent after conditioning on public query information. It shows that the guarantee is recovered at conditional independence, with a penalty for departures from it.

4. First-price auctions with near-independent values

  • The paper measures conditional dependence by the total variation distance between the values’ conditional joint distribution and the product of their conditional marginals.A distance of zero means values are conditionally independent given the public state.Source: §4 · p. 6
  • When values are conditionally independent given public information, the 1 − 1/e^2 welfare bound holds exactly, even if values are arbitrarily correlated across queries.Small departures incur an additive penalty scaled by the conditional value bound; a ratio guarantee also requires that bound not be too large relative to the conditional expected top value.Source: §4 · p. 6
  • Competitive floors and near-independence can coexist when values share a large query-dependent component and have small independent fluctuations.The example sets V_i = a(X) + θZ_i, with a(X) ≥ θ and conditionally independent zero-mean Z_i in [−1, 1].Source: §4 · p. 6

5. On implications for agentic market platform design

The section considers two platform choices that can shape market conditions: filtering which models bid and entering an in-house model. Both can support stronger welfare bounds, with a filtering trade-off and a reserve-price interpretation for platform participation.

5. On implications for agentic market platform design

  • Filtering out weak models can strengthen the welfare lower bound, but excluding the best model lowers the upper bound and creates risk.The risk can be mitigated by conservative filtering that retains the strongest models.Source: §5 · p. 7
  • An in-house model that publicly announces its value and bids that amount acts as a query-specific reserve price and keeps welfare at least at its value.Equilibria also recover at least a (1 − 1/e)-fraction of optimal welfare above that value; its value need only exceed a fraction of expected top value on average to match the deterministic-floor bound.Source: §5 · p. 7

6. Experiments

Experiments simulate strategic auctions on EmbedLLM, comparing realized welfare with allocation-rule baselines and the competitive-floor bound. Across full, sampled, and illustrative markets, auctions retain high welfare, while cohort results vary with competition and value structure.

6.1. Setting

  • The study estimates values from EmbedLLM response accuracy minus model costs, then solves cluster-conditioned approximate Bayes–Nash equilibria using fictitious play.The dataset contains over 30k prompts and 110 models; both typical and adversarial approximate equilibria are evaluated.Source: §6.1 · pp. 7–8

6.2. Results

  • 99.2% of oracle welfare at typical equilibrium and 98.8% at adversarial equilibrium, exceeding per-cluster routing (89.4%) and single-model routing (78.1%).On the worst cluster, the corresponding auction figures are 96.0% and 93.0%, versus 64.0% for per-cluster routing and 6.0% for the best single model.Source: §6.2 · p. 8, Table 1 · p. 8
  • Across 100k sampled sub-markets, most typical-equilibrium welfare ratios exceed 95%, and the bottom 0.1% rises with the competitive-floor bound for both equilibrium solvers.In the highest bound bin, bottom-tail welfare is 0.96 for adversarial and 0.96 for typical equilibria; the caption describes tightening distributions as market size grows.Source: §6.2 · p. 9, Figure 2 · p. 9
  • With similar versus diverse four-model cohorts, welfare losses are 0.4% versus 1.2%; a generalist with three niche models loses 5.1%, falling to 0.8% when one niche model is replaced by a second generalist.The cohorts have comparable first-best welfare, while runner-up gaps and shading differ across their value structures.Source: §6.2 · pp. 9–10, Table 2 · p. 10

7. Related work

Prior work studies truthful auction mechanisms and worst-case efficiency guarantees for first-price auctions. This paper instead examines how value structure can improve those guarantees and relates its analysis to beyond-worst-case auction results.

7. Related work

  • Recent agentic-market work favors DSIC second-price and VCG mechanisms, while this paper studies first-price auctions under competitive floors and weakly dependent values.The related-work discussion notes that DSIC mechanisms may be susceptible to collusion and require trust in the auctioneer.Source: §7 · p. 10
  • For arbitrary correlation, prior first-price-auction bounds give 1 − 1/e ≈ 0.632; independent private values raise the guarantee to 1 − 1/e^2 ≈ 0.865 [Christodoulou et al., 2016; Syrgkanis and Tardos, 2013; Jin and Lu, 2023a].The cited independent-values bound is tight, and worst-case bounds remain tight even for the best equilibrium [Jin and Lu, 2023b].Source: §7 · p. 10
  • The paper extends beyond-worst-case analysis to structural value conditions, relating weak dependence to prior results where evenly spread information improves simple-auction guarantees.It also connects its experiments to empirical price-of-anarchy approaches and analyses weighting equilibria by learning-dynamics reachability.Source: §7 · p. 10

8. Conclusion

The paper concludes that first-price auctions among AI agents can preserve welfare despite bid shading. Its theoretical guarantees improve under competitive floors and near-independent values, and platforms can use filtering or reserve bids to protect efficiency.

8. Conclusion

  • Under similar values among the strongest bidders, the welfare guarantee rises toward full efficiency; with weakly dependent values, the independent-values bound degrades smoothly.Platforms can also filter weak bidders through routing rules or enter their own models to set competitive reserve prices.Source: §8 · p. 11

A. Limitations and future work

The appendix extends the welfare bounds to families of priors and query-conditional floors, and examines how positive dependence affects competitive floors. It also identifies limits involving equilibrium behavior, value dependence, and the paper’s focus on welfare.

A. Limitations and future work

  • The analysis assumes user and model utility are aligned and bounds describe equilibrium bidders; learning dynamics and combining competitive-floor and near-independence guarantees remain for future work.External utility, such as advertising, requires additional analysis.Source: A. Limitations and future work · p. 16

B.1. Bounds that hold over a family of priors

  • For a family of priors, the guaranteed PoA is at least the smallest bound L(μ) among priors in that family.The bounds may use prior-specific parameters, such as α, m, and ε.Source: §B.1 · p. 16

B.2. Positively dependent values

  • For associated values, expected maximum value is at least as high as under independent values with the same marginals, but positive dependence can worsen Theorem 3’s floor bound.Shared low-value queries can increase ε.Source: §B.2 · pp. 16–17

B.3. Query-conditional competitive floors

  • Applying Theorem 3 separately to each query’s conditional prior yields a floor adapted to that query and can improve on using one floor for the unconditional prior.A single floor can be too high for hard queries and too low for easy ones.Source: §B.3 · p. 17

B.4. Example: Competitive floors from specialist models

A capability-based example shows how specialist models can create a competitive floor when enough models can handle most queries. The accompanying experiments find that prompt information explains much of the predictive signal in rival values, while residual dependence remains and the evidence does not establish conditional independence.

B.4. Example: Competitive floors from specialist models

  • A specialist-model market has an (α, m, ε)-competitive floor when at least m models can handle a query with probability 1−ε; queries requiring rare or many capabilities are where the floor may fail.For heterogeneous capability probabilities, the floor holds when several models have high probabilities for the required capabilities.Source: §B.4 · pp. 17–18
  • With 100 models, m=8, and p=0.8, the bound guarantees about 0.89 of optimal welfare when no more than 3% of queries require over 9 capabilities, versus about 0.63 from the general bound.The example has ε_9=0.03; values may be dependent through the shared query.Source: §B.4 · p. 18

C.1. Near-independence given the prompt

  • Across ordered model pairs, the prompt predicts value with R2=0.67 on average, while adding a rival after the prompt raises R2 by 0.05 on average and 0.09 at the 90th percentile.The prompt alone is the better predictor in 84% of pairs; residual dependence is greatest for near-duplicate models.Source: Figure 3 · p. 18, §C.1 · p. 19
  • The R2 results support but do not establish conditional independence, and small R2 gains do not bound the total variation distance τ(x).The paper does not directly estimate τ(x).Source: §C.1 · p. 19

C.2. Platform-owned bidder

The experiments evaluate platform-owned bidding and pre-auction filtering on sampled EmbedLLM markets, alongside the equilibrium solver used to analyze them. Filtering can improve adversarial lower-tail welfare while retaining strong models, but aggressive filtering reduces welfare; a stronger platform model also improves the adversarial lower tail.

C.2. Platform-owned bidder

  • With a platform-owned bidder, moving the platform model into the top half raises adversarial lower-tail PoA from 0.94 to 0.96 at n=5; matching the best model lifts curves to about 0.98–0.99.Markets already have mean PoA about 0.98, so weak or average platform models change welfare little.Source: §C.2 · p. 20, Figure 4 · p. 20

C.3. Pre-auction filtering

  • For β≤0.6, filtering leaves mean welfare near 0.99 and improves the adversarial lower tail; beyond β=0.6 it can exclude prompt-best models, and welfare falls to about 0.91 when only cluster leaders bid.The cluster-router baseline is below the auction for every β<1 in both mean and 0.1 percentile.Source: §C.3 · p. 20, Figure 5 · p. 21

D. Equilibrium solver

  • The solver estimates typical and adversarial equilibria by iterating best responses over five value bins per bidder and cluster, using empirical rival bids and values.Typical responses maximize utility; adversarial responses choose among near-optimal-utility responses with the lowest welfare.Source: D. Equilibrium solver · pp. 21–22
  • The solver damps bid updates to help avoid cycling, but starting from truthful bids can miss equilibria not reachable by lowering bids.It stops after ten consecutive rounds with bid changes no larger than 10^-3, or after 100 rounds.Source: D. Equilibrium solver · p. 22

E. Proofs for competitive floors

The proofs turn competitive floors into welfare guarantees by controlling the winning bid and the welfare shortfall above a threshold. They also extend the analysis to committed platform bidding and to weak dependence, where small regret preserves the independent-values guarantee approximately.

E. Proofs for competitive floors

  • For any threshold c ≥ 0, equilibrium welfare is at least expected revenue capped at c plus (1−1/e) times the expected top-value excess above c.At c = 0, this recovers the standard 1−1/e guarantee.Source: E. Proofs for competitive floors · p. 22

E.1. Deterministic competitive floor

  • If the second-highest value is at least c almost surely, every Bayes–Nash equilibrium has a winning bid of at least c almost surely.The proof uses a unilateral bid increase by bidders whose values clear c to rule out a winning bid below the floor.Source: §E.1 · pp. 23–24

E.2. Probabilistic competitive floor

  • When at least m bidders clear c with probability at least 1−ε, the proof bounds expected shortfall of the winning bid below c using deviations at each bid level.The deviation may lose when fewer than m bidders clear c, so the argument accounts for that event rather than guaranteeing a deterministic floor.Source: §E.2 · p. 24

E.3. Welfare with a committed platform bidder

  • A platform that publicly announces its value and bids it creates a query-specific floor, and the threshold welfare argument applies conditional on the public state.The platform's bid ensures the winning bid is at least its announced value; its utility is zero.Source: §E.3 · p. 26

F. Proofs and additional results for weak dependence

  • At exact equilibrium, the 1−1/e welfare guarantee holds under every joint value distribution, while the sharper 1−1/e^2 guarantee requires independence.The robustness argument allows arbitrary correlation because its deviations depend only on each bidder's own value.Source: F. Proofs and additional results for… · p. 26

F.2. Proof overview

  • For weak dependence, the proof transfers an equilibrium to the product of conditional marginals, uses its small regret to invoke the independent-values guarantee, then transfers welfare back.The strategy profile has regret at most 2v̄(x)τ(x) under the product distribution.Source: §F.2 · p. 26

F.3. Welfare shortfall under small regret

  • For fixed bidder count, independent-values auctions with vanishing regret have vanishing welfare shortfall below the Jin–Lu guarantee.The proposition's bound is uniform over the auctions in its definition, but supplies no explicit rate.Source: §F.3 · p. 27

F.3.1. Proof of Proposition F.1

The proof shows that vanishing regret in independent-values auctions cannot sustain a positive welfare shortfall below the Jin–Lu guarantee. It then transfers that guarantee to weakly dependent values, with a linear error bound under additional regularity assumptions.

F.3.1. Proof of Proposition F.1

  • A sequence of independent-values auctions with vanishing regret cannot retain a fixed positive welfare shortfall below the Jin–Lu guarantee.The proof takes a limit that is an exact equilibrium, contradicting the Jin–Lu bound if the shortfall persists.Source: §F.3.1 · p. 27, Proof of Proposition F.1 · p. 30
  • The limiting argument records value–bid distributions and winners so utilities and welfare survive convergence, including when distinct bids become tied.It constructs a bid-only tie rule that preserves welfare and makes the limiting profile an equilibrium.Source: §F.3.1 · pp. 28, 30

F.4. Proof of the main qualitative theorem (Theorem 5).

  • For bounded values, Theorem 5 gives qualitative stability of the Jin–Lu guarantee for weakly dependent values, without requiring equilibrium strategies to vary continuously with the distribution.The theorem compares the conditional joint distribution with the product of its marginals.Source: §F.4 · p. 31

F.5. A quantitative bound for weakly-dependent values

  • Under continuous marginal densities and the stated regularity assumptions, the welfare error is bounded linearly in total variation from independence.The result allows differing marginals and applies to every no-overbidding Bayes–Nash equilibrium, including mixed equilibria.Source: §F.5 · p. 31

F.5.1. Proof Overview

  • The quantitative proof constructs a nearby exact independent-values equilibrium, transfers its Jin–Lu guarantee back, and uses a derivative condition to bound the error.The construction adjusts bid distributions jointly and proves the resulting bids are globally optimal for their assigned values.Source: §F.5 · pp. 31–32, §F.5.1 · p. 32

F.5.2. Proof of Theorem F.4

The proof establishes equilibrium-bid bounds and constructs an exact independent-value comparison equilibrium, then uses a product-prior comparison to bound welfare shortfall while accounting for the prior change. It also gives a correlated-prior example satisfying the stated regularity assumptions.

F.5.2. Proof of Theorem F.4

  • Every equilibrium is outcome-equivalent, up to null sets, to pure nondecreasing strategies with atomless bid distributions; bid supports cover [0, β], and each interior bid belongs to at least two supports.At each support bid, the corresponding cutoff type has that bid as a best response, including endpoints by continuity.Source: §F.5.2 · pp. 32, 34
  • Lemma F.6 gives constants Q ≥ 4 and σ > 0, depending only on n, ℓ, and u, such that for 0 < b ≤ β, (1 + σ)b ≤ v_i(b) ≤ min{1, Qb}, with β ≤ 1/(1 + σ).It also gives H_i(b) ≤ uQb.Source: §F.5.2 · p. 34
  • Bid CDFs and value cutoffs are locally Lipschitz, and at least two bidders’ bid densities are positive almost everywhere; first-order conditions are used only on each bidder’s support.Individual supports may have gaps or end before β.Source: §F.5.2 · pp. 32, 35
  • For sufficiently small ε, atomless comparison bid distributions induce an exact no-overbidding Bayes–Nash equilibrium with independent values, whose marginals may differ from the original value marginals.The constructed strategies are global best responses for almost every assigned value.Source: §F.5.2 · pp. 36, 39

Proof of Theorem F.4

  • For ε≤ε0, the proof controls welfare shortfall using a product-bid comparison with total variation at most Bε and a prior-change error of at most τ.For ε>ε0, it says the same inequality is immediate because Bε exceeds cJL, while the signed shortfall is at most cJL; the prior change remains bounded by τ.Source: Proof of Theorem F.4 · p. 40
  • The universal 1−1/e guarantee leaves normalized shortfall at most e^-1−e^-2 on the prior class considered.The proof identifies this as the additive-error function for Theorem 5 on that class, without optimizing its constant.Source: Proof of Theorem F.4 · p. 40
  • A two-variable density perturbation preserves the marginals and satisfies the assumptions with ℓ=1/2, u=3/2, L=3, and τ=ε/8.The construction uses r(v)=1+ε(2F1(v1)−1)(2F2(v2)−1), for 0≤ε≤1, and has ∥r−1∥∞=ε, even when the marginals differ.Source: Proof of Theorem F.4 · p. 40

Related papers

Loading 2610.20587v1…