CS Paper Radar

Efficiency of Generalized Proportional First-Price Auctions Under Auto-bidding

Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Di Wang

cs.GT ·submitted 2026-09-30 00:27 UTC · v1
theory

Abstract

Auto-bidding is now widely adopted in online advertising platforms, allowing advertisers to specify high-level campaign objectives--such as maximizing total value subject to a return-on-spend (ROS) constraint--rather than manual per-query bids. A central question in algorithmic mechanism design is characterizing the worst-case efficiency loss, or Price of Anarchy (PoA), across auction formats in this prior-free setting. While randomized auctions are known to strictly improve efficiency over deterministic mechanisms for two bidders, two fundamental questions have remained open: (1) what is the optimal PoA for two bidders, and (2) can any mechanism beat the barrier of 2 for general $n \ge 3$ bidders? We resolve both questions using the family of $r$-proportional first-price auctions ($\text{pFPA}_r$), in which each bidder wins with probability proportional to their bid raised to an exponent $r > 0$ and pays their bid upon winning. First, for two bidders, we prove that the standard proportional first-price auction ($r = 1$) achieves a tight $\text{PoA} \le 1.5$, complemented by a matching lower bound showing that no anonymous, monotone mechanism can do better. Second, for general $n \ge 2$ bidders, setting $r = 2n$ achieves $\text{PoA} \le 2 - \frac{1}{4n+1} = 2 - Ω(1/n)$ across all undominated bid profiles, breaking the deterministic barrier of 2 for every finite $n$ and asymptotically matching the known $2 - Θ(1/n)$ lower bound.

Closest papers

Nearest neighbours by meaning across the whole index.

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.74
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

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.72
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

Two-sided Market Design Meets Autobidding

cs.GT ·2026-09-30 ·Yang Cai, Christopher Liaw, Aranyak Mehta, Xizhi Tan, Mingfei Zhao
publishedtheory similarity 0.71
Abstract · To appear in the 22nd Conference on Web and Internet Economics (WINE2026)

Autobidding has become a dominant paradigm in online advertising by enabling advertisers to set high-level goals while algorithms handle real-time bid optimization. A prominent example is the Return-on-Spend (RoS) value maximizer, which maximizes total value subject to an aggregate value-per-spend constraint. While most work on mechanism design for autobidders focuses on one-sided markets, many real-world platforms involve strategic behavior on both sides. We initiate the study of two-sided markets with autobidders. We first establish a stark negative result: for the challenging objective of liquid gains from trade (LGFT) in the prior-free setting, broad classes of utility-truthful, budget-balanced mechanisms have unbounded Price of Anarchy (PoA) once value-maximizing agents are present, even in double-auction environments. We then give two positive results. In the prior-free repeated double-auction setting, McAfee's Trade Reduction mechanism has unbounded PoA for LGFT but achieves constant PoA for liquid welfare under RoS bidding, showing that off-the-shelf mechanisms retain meaningful welfare guarantees. With distributional information regarding the private costs and values, we design a two-sided mechanism that is incentive compatible for each agent under its corresponding objective, individually rational, ex-ante weakly budget balanced, and achieves first-best liquid welfare, equivalently optimal LGFT, whenever at least one side of the market consists of RoS value maximizers. This result applies to matching markets with general downward-closed feasibility constraints. It contrasts sharply with the Myerson--Satterthwaite impossibility theorem~\citep{MS83}, which rules out first-best efficiency with incentive compatibility, individual rationality, and budget balance even in bilateral trade when both the buyer and the seller are quasi-linear utility maximizers.

0.32

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

cs.GT ·2026-11-02 ·Simone Palazzotto, Andrés Cristi
similarity 0.69
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

A Primal-Dual Approach to Randomized Online Bidding with Tail Constraints

cs.DM ·2026-10-04 ·Royce Kraakman, Bob Krekelberg, Alison Hsiang-Hsuan Liu, Fu-Hong Liu
theory similarity 0.68
Abstract

Controlling tail risk in randomized algorithms has received increasing attention. Randomized online algorithms can achieve a lower expected competitive ratio than the competitive ratio of the best deterministic online algorithm. However, individual executions may still incur poor outcomes. Tail constraints address this risk by limiting the probability that the incurred ratio exceeds a prescribed threshold. We investigate how such constraints affect the structure and performance of randomized online bidding algorithms. By revisiting the classical primal-dual lower-bound framework for online bidding, we find that restricting the growth between consecutive bids can yield a stronger lower bound on the expected competitive ratio. We then show that tail constraints with zero exceedance probability impose an asymptotic upper bound on the ratios between consecutive bids. Incorporating this structural property into the primal-dual framework allows us to derive a stronger lower bound. Moreover, the dual analysis suggests a randomized geometric bidding algorithm whose performance matches this bound. The insight from our primal-dual analysis also guides the design of algorithms for general tail constraints allowing positive exceedance probabilities. Motivated by the geometric growth suggested by the dual solution, we study randomized periodic bidding algorithms. We show that, for any fixed geometric base, the uniform offset distribution is optimal in terms of both the expected competitive ratio and tail-constraint feasibility. We then characterize the exceedance probability of these algorithms and use this characterization to choose a geometric growth factor that satisfies the prescribed tail constraints, establishing parameter-dependent upper bounds on the optimal expected competitive ratio.

0.20

Auction Design with ROI-Constrained Bidders: Truthfulness and Revenue Maximization

cs.GT econ.TH ·2026-09-15 ·Zhiqiang Zhuang, Quan Yu, Yisong Wang, Kewen Wang, Zhe Wang
theory similarity 0.68
Abstract

The return-on-investment (ROI) constraint is central to many auctions, particularly in online advertising, where a bidder is unwilling to pay more than a fixed fraction of the value obtained. We study truthful and revenue-maximizing auctions for ROI-constrained bidders. We first characterize truthful auctions when both valuations and ROI constraints are private, showing that the allocation rule uniquely determines the payment rule. Building on this characterization, for multiple bidders we introduce $σ$-increment mechanisms that resemble Myerson's optimal mechanism~\cite{journals/mor/Myerson81}; as $σ$ vanishes, these mechanisms become asymptotically optimal among deterministic truthful mechanisms, and their revenue approaches at least a $1/\bar r$ fraction of the optimal expected revenue over all truthful mechanisms, where $\bar r$ is the largest possible ROI constraint. In the single-bidder setting, we prove that every truthful auction can be replaced by a convex pricing function with weakly higher payments for every type, and we derive the optimal pricing functions when either the valuation or the ROI constraint is public.

0.21

Tight Inapproximability of Pacing and Throttling Equilibria in Second-Price Auctions

cs.GT cs.CC ·2026-08-17 ·Zhengyang Liu
theory similarity 0.66
Abstract

Budget-constrained advertisers commonly rely on two control mechanisms: pacing scales bids, whereas throttling randomizes participation. We prove that, in second-price auctions, these two different mechanisms share the same sharp approximation-hardness threshold. For pacing, computing a $γ$-approximate equilibrium is $\mathsf{PPAD}$-hard for every constant $γ\in[0,1)$. For throttling, computing a $δ$-approximate equilibrium is $\mathsf{PPAD}$-hard for every constant $δ\in(0,1)$. At parameter $1$, the complementarity requirement becomes vacuous and the all-zero solution is feasible. That is, approximation does not eliminate the fixed-point barrier at any nontrivial parameter value.

0.46

A Truthful-in-Expectation 2-Approximation for Pair-Specific Cascade Auctions in AI-Generated Content

cs.GT ·2026-10-25 ·Tao Jiang, Minbo Gao, Shaowei Cai
similarity 0.66
Abstract · 9 pages, 4 figures, 5 tables

Generative AI interfaces can insert sponsored content at multiple points in an answer, where click-through rates (CTRs) depend on the advertiser-position pair. Under the cascade model, users read ads sequentially and stop after their first click, so both ad assignment and display order affect welfare. For arbitrary pair-specific CTRs, Balseiro et al. (WWW 2026) gave a $4/(1-\varepsilon)$-approximation whose monotonicity has not been established, and a monotone $O(\log m)$-approximation for $m$ candidate positions. Earlier truthful constant-factor mechanisms require factorized CTR models and do not apply. Whether monotonicity is compatible with a constant-factor approximation in this general setting was left open by that work. We give a polynomial-time mechanism for arbitrary pair-specific CTRs and any limit on displayed ads that is truthful and individually rational in expectation and achieves a 2-approximation to optimal cascade welfare. Our mechanism selects an advertiser-position matching and a designated last ad, then randomly thins earlier ads so that each selected ad's expected cascade CTR is the same fraction of its standalone CTR. This yields an exact closed-form expression for expected welfare, which we maximize over a bid-independent lottery range using linear programming. Exact optimization ensures monotonicity, while a random-prefix decomposition proves the factor-two guarantee, which is tight for this range. We also show that exactly optimizing the previous welfare surrogate can violate monotonicity, and evaluate welfare and running time on synthetic instances.

0.22