CS Paper Radar

Robust Analysis of First-Price Auctions with Large Supply

Jason Hartline, Anant Shah, Matthew vonAllmen

cs.GT ·submitted 2026-11-06 22:44 UTC · v1
theory

Abstract

This paper performs a robust analysis of welfare (i.e., the price of anarchy) in multi-unit first-price auctions with independent private values and unit-demand bidders. We employ a smoothness framework (see \citealp{ST-13}) to analyze the price of anarchy when supply is large. The main barrier to analysis in this framework is a worst-case bid distribution that establishes a lower bound on the price of anarchy of $1- \frac{1}{e}$. We show that such worst-case distributions cannot arise in equilibrium when agents' values satisfy a mild density lower bound condition. This characterization leads to novel asymptotic lower bounds. In particular, the price of anarchy for $ε$-approximate equilibrium as the number of units goes to infinity is at least $1-Θ\left(ε\log \left(\frac{1}ε\right)\right)$. Our analysis relies on a key structural property of equilibrium bid distributions: for a welfare analysis in any multi-unit first-price auction, it is without loss to analyze (approximate) equilibria with no atoms. In addition to this, we establish continuity and monotonicity properties of Bayes-Nash equilibria. We believe these results are of independent interest.

Closest papers

Nearest neighbours by meaning across the whole index.

At What Cost? (In)efficiency in First-Price Procurement Auctions

cs.GT ·2026-11-02 ·Simone Palazzotto, Andrés Cristi
similarity 0.74
Abstract · 19 pages

We study the efficiency of Bayes-Nash equilibria in first-price procurement auctions. We measure efficiency by the Price of Anarchy (PoA): the ratio between the expected social cost in equilibrium and the minimum expected social cost resulting from a socially optimal allocation. We first show that the standard first-price procurement auction has no bounded PoA guarantee. We construct equilibria in which every bidder is indifferent between all bids in a common interval, so that bids can be arbitrarily large, and the PoA is unbounded. If costs lie in an interval $[\underline c,\bar c]$ but bids are not restricted, the PoA equals the trivial ratio $\bar c/\underline c$. We hence study ways to restore a finite guarantee, first by characterizing the PoA when bids lie in $[\underline c,\bar c]$, which leads to the tight bound $1 + \frac1{e^2}(\frac{\bar c}{\underline c}-1)$. Alternatively, we introduce the notion of a phantom bidder: the auctioneer accepts the lowest bid only if it does not exceed a phantom bid, drawn independently of the costs, and otherwise buys from an outside option at cost $\bar c$. We show that a simple fixed phantom bid, i.e., a deterministic cap, gives PoA $=\frac1e\sqrt {\frac{\bar c}{\underline c}}+O(1)$. We further show that no phantom mechanism whose construction depends only on the cost interval, under a mild regularity condition, whatever distribution it uses and whatever it reveals about the phantom bid before bidding, can improve on the $\sqrt{\frac{\bar c}{\underline c}}$ dependence.

0.22

Tight Liquid Welfare Guarantees for Auctions with Budgets via LP Duality

cs.GT ·2026-09-30 ·Twan Kroll, Guido Schäfer, Artem Tsikiridis
theory similarity 0.70
Abstract

We study the efficiency of auctions with budget-constrained bidders and derive tight price of anarchy (PoA) bounds for coarse correlated equilibria (CCE). To this end, we develop a general framework that reduces proving PoA guarantees to finding feasible solutions to the dual of a linear program. The LP is formulated over a small number of per-bidder equilibrium statistics, incorporates constraints implied by the auction setting and equilibrium behavior, and captures a novel smoothness notion tailored to budget-constrained environments; we provide a reduction from classical smoothness to this new notion. Our approach enables simple and tight PoA analyses across a broad range of auction formats. Using our framework, we obtain tight liquid welfare guarantees for simultaneous first-price, second-price, and all-pay auctions, simultaneous auctions with restricted uniform bidding interfaces, discriminatory and uniform price multi-unit auctions, and generalized first-price position auctions. Beyond budget-constrained settings, we derive new lower bounds for the budget-free uniform price auction and generalized second-price auction; in particular, our lower bound for the uniform price auction matches the upper bound of $3.146$ by de Keijzer et al. (2013).

0.16

The Exact Approximation Ratio of the Optimal Fixed-Price Mechanism in Bilateral Trade

cs.DS ·2026-08-20 ·Tao Jiang, Minbo Gao, Shaowei Cai
similarity 0.67
Abstract

In bilateral trade, a seller owns an item that a buyer may value more, and their values are drawn independently from known distributions. A fixed-price mechanism posts a single price and trades exactly when both agents accept it. How much of the first-best expected welfare can the optimal fixed price guarantee? A sequence of analytic and computer-assisted results narrowed the worst-case ratio to the interval $[0.7292,0.73805]$, but its exact value remained open. We determine this ratio exactly: it equals $0.7380243357\ldots$, given in closed form through the unique root of an explicit one-dimensional equation. The guarantee holds for every pair of independent nonnegative distributions with finite means, including atomic and unbounded ones, and an explicit family of instances shows that no larger constant is possible. The proof reduces the problem, through put and call transforms of the two distributions and a worst-case choice of seller, to a one-dimensional control problem for the buyer. A logarithmic change of variables makes this problem strictly convex, so its first-order conditions certify a global optimum. The optimizer switches exactly once from an interior arc to the boundary and can be integrated in closed form. Realizing it yields a bounded seller and a bounded buyer together with a vanishing buyer atom at a diverging value. The worst case is approached by this family but attained by no instance.

0.32

A 1.283 Price-of-Anarchy Bound for the Repeated Virtual First-Price Auction

cs.GT econ.TH ·2026-08-28 ·Endre Csóka
similarity 0.66
Abstract

We study the repeated allocation of a single indivisible resource among $n$ strategic players. Each player $i$ has a privately known value distribution $D_i$, and values are drawn independently across players and periods. The goal is to find fair and efficient mechanisms. We apply the repeated first-price auction with equal initial endowments of virtual money. We show that each player can asymptotically secure the same fair-floor guarantee $f(D_i)$ as in Csóka 2026; consequently, the mechanism is $1.283$-optimal. This provides a simpler and more robust alternative mechanism for this special case and may also help derive sharper upper bounds on the price of anarchy.

0.38

Price of Anarchy of First-Price Auctions in Agentic Markets

cs.GT cs.AIcs.LG ·2026-10-14 ·Shubhendu Trivedi, Jacob Eisenstein, Alekh Agarwal, Ian Gemp, Michael Kaisers +1 more
position similarity 0.65
Abstract · 40 pages

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.

0.34

On the Power of Determinism in Multi-Item Auctions

cs.GT cs.DM ·2026-09-28 ·Yiannis Giannakopoulos, Johannes Hahn
theory similarity 0.64
Abstract · Improved the upper bound on REV/max{SREV,BREV} from 3 to 2.5 for independent items, and added a lower bound of 2.19. For iid items, improved…

We study the classical multi-item monopoly setting with a single additive buyer and $m$ heterogeneous items whose values are independent but not necessarily identically distributed. We compare the revenue (REV) of the optimal truthful auction, which in general may be randomized or complicated, with the revenues of three simple deterministic auctions: selling all items separately (SREV), selling them as a single grand bundle (BREV), and choosing the better of the two. Our technical cornerstone is a general upper bound on the optimal multidimensional revenue, parameterized by freely chosen item-wise caps, and expressed in terms of optimal single-item, Myersonian revenues and basic statistics of the value distributions. We derive this inequality through Lagrangian duality for a nonlinear programming formulation of the worst-case approximation ratio of separate-selling. Combining this inequality with carefully chosen caps and a probabilistic analysis of the resulting terms, we obtain improved approximation guarantees for all three deterministic auctions, both for general independent values and for iid values. Notably, we prove that $REV\le 2.5\max\{SREV,BREV\}$, improving the long-standing $5.2$ factor of Ma and Simchi-Levi and the $6$ factor of Babaioff, Immorlica, Lucier, and Weinberg. We complement this upper bound with a construction establishing a lower bound of $2.19$, improving the bound of $2$ by Rubinstein. For two iid items, we determine the exact approximation ratio of selling separately. Our proof constructs tight Lagrangian dual certificates for the aforementioned programming formulation, when item values lie in the grid $\{0,1/K,2/K,\dots,1\}$, for any discretization parameter $K$. Taking $K\to\infty$ yields the tight ratio $1+W(1/e)\approx1.2785$ in the continuous-valued setting, where $W$ is the Lambert-W function, closing the $[1.278,1.368]$ gap left by Hart and Nisan.

0.41

The Price of Anarchy in Markets for Lemons

cs.GT cs.DSecon.TH ·2026-11-11 ·Naveen Durvasula, Tim Roughgarden
similarity 0.63
Abstract

We study the worst-case equilibrium gains from trade in simple bilateral trade mechanisms with interdependent valuations. Equilibria in such settings are typically complex, as proposed prices can convey private information held by the proposer. Such equilibria suffer lost gains from trade both due to the inefficiency introduced by screening (as in independent private value settings) and due to adverse selection. We identify broad conditions under which, nevertheless, sequential equilibria are guaranteed to achieve a constant fraction of the first-best gains from trade. Our bounds quantify the central role of rare pessimistic seller signals and rare optimistic buyer signals. The results apply to seller-proposer, buyer-proposer, and random-proposer mechanisms. The key idea in our analysis is to relate equilibrium gains from trade to proposer profits in an auxiliary market with independent private values.

0.21

Improved Combinatorial Auctions with and without Samples

cs.GT cs.DS ·2026-10-13 ·Aviad Rubinstein, Sahil Singla
similarity 0.63
Abstract · Abstract shortened to fit arXiv constraints

We give new mechanisms for combinatorial auctions in the offline, secretary, and prophet-with-samples models. Specifically, we obtain the following guarantees for social welfare maximization with $m$ items and $n$ XOS buyers: * In the prophet-with-samples version, buyers arrive in adversarial order and draw their values from independent distributions. We give a universally truthful, polynomial-time $(2+\eps)$-approximation mechanism using $O(\log\!\log m)$ samples from each distribution. The approximation factor is tight even for a single item and without the incentive constraints, due to the classic prophet inequality. Compared to the previous state-of-the-art with the same guarantees [Dütting--Kesselheim--Lucier--Reiffenhäuser--Singla (FOCS 2024)], our running time is exponentially faster, and our sample complexity is doubly-exponentially lower, resolving two explicit open problems by Dütting et al. * Using the same techniques, we also obtain improved mechanisms in the secretary and offline versions, where the values are worst-case, and buyers are processed in either random order (secretary) or without any timing restrictions (offline). After a long line of works, the state of the art in both models is an $O((\log\!\log m)^2)$-approximation due to [Assadi--Kesselheim--Singla (SODA 2021)], who explicitly ask whether it can be improved to $O(\log\!\log m)$. We indeed obtain an $O(\log\!\log m)$-approximate universally truthful mechanism for the secretary and offline models.

0.08