📈 economics

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

This paper characterizes truthful auctions for ROI-constrained bidders by proving that allocation rules uniquely determine payments and introducing $\sigma$ -increment mechanisms that asymptotically achieve revenue optimality comparable to Myerson's framework, while also deriving optimal pricing functions for single-bidder scenarios with public constraints.

Original authors: Zhiqiang Zhuang, Quan Yu, Yisong Wang, Kewen Wang, Zhe Wang

Published 2026-09-16✓ Author reviewed ⓘ

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhiqiang Zhuang, Quan Yu, Yisong Wang, Kewen Wang, Zhe Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the bustling digital marketplace of online advertising, platforms like Google act as vast auction houses where companies bid for the fleeting attention of a user scrolling through a webpage. For decades, the rules of these auctions were built on a simple assumption: a bidder knows exactly how much an item is worth to them, and they are willing to pay up to that amount to secure it. This straightforward logic allowed economists to design systems that were both fair to the participants and highly profitable for the seller. However, the real world of advertising is far more complex. Advertisers do not just care about the value of a single click; they operate under strict return-on-investment constraints. This means an advertiser is only willing to pay a certain fraction of the value they expect to receive. If a click is worth one dollar to them, they might refuse to pay more than twenty cents, ensuring their investment yields a specific profit margin. This constraint turns the auction into a multidimensional puzzle, where a bidder's strategy depends on two private numbers—their true valuation and their strict spending limit—rather than just one.

This new reality creates a significant challenge for the architects of these digital marketplaces. When bidders have these dual constraints, the standard tools used to design fair and profitable auctions often break down. The relationship between how much a bidder gets and how much they pay becomes tangled, making it difficult to ensure that everyone tells the truth about their limits while still maximizing the seller's earnings. Researchers Zhiqiang Zhuang, Quan Yu, Yisong Wang, Kewen Wang, and Zhe Wang have stepped into this complexity to untangle the mechanics of these constrained auctions. Their work provides a clear map of how truthful auctions can function when bidders are bound by return-on-investment rules, revealing that the rules for allocating items can uniquely determine the rules for charging money, even in this complicated two-dimensional setting.

The researchers began by translating the problem into a more manageable form. Instead of thinking about the raw value an advertiser places on an item and their separate spending limit, they focused on a single derived concept: the maximum price per unit of success that a bidder can afford. If an advertiser values a click at one dollar but will only pay twenty cents to ensure a five-to-one return, their "affordability cap" is twenty cents. By viewing the auction through the lens of this cap, the team discovered a powerful structural truth. They proved that in any fair auction where bidders have no incentive to lie, the way items are distributed to winners completely dictates the payments they must make. There is no wiggle room; once the allocation rule is set, the payment rule is mathematically locked in. This finding simplifies the design process significantly, as it removes the need to guess at payment schemes separately from allocation strategies.

With this foundation laid, the team turned their attention to the practical goal of making the most money for the seller. They explored the use of deterministic mechanisms, where the outcome is a fixed decision rather than a gamble. They found that the optimal strategy for these auctions closely resembles a classic method developed by economist Roger Myerson, but with a crucial twist. Instead of applying the rules to the bidders' valuations, the auctioneer applies them to the bidders' affordability caps. To ensure the system remains perfectly truthful and prevents bidders from gaming the edge cases, the researchers introduced a mechanism that adds a tiny, deliberate increment to the winning threshold. As this increment becomes infinitesimally small, the auction's revenue approaches the theoretical maximum possible for any truthful, deterministic system. Furthermore, they demonstrated that even in the worst-case scenarios, these deterministic auctions can capture at least a fraction of the revenue that would be possible if the seller were allowed to use randomized, probabilistic methods. This provides a strong guarantee that simple, fixed rules can perform nearly as well as complex, randomized ones.

The study also delved into the specific case of a single bidder, a scenario that serves as a building block for understanding larger markets. Here, the researchers showed that any complex auction mechanism could be replaced by a simple pricing menu. Imagine a seller offering a product where the price per unit changes depending on how much you buy. The team proved that the best way to structure this menu is through a convex pricing function, where the average price per unit rises as the quantity increases. When the seller knows the bidder's true value but not their spending limit, the optimal pricing strategy involves offering the first portion of the item for free, then charging a steep, linear rate for any additional amount. Conversely, when the seller knows the spending limit but not the true value, the optimal pricing follows a power law, where the price starts low and curves upward, becoming increasingly expensive as the buyer approaches the full quantity. These findings offer concrete blueprints for how to price goods when buyers are constrained by efficiency goals.

Ultimately, this research clarifies the landscape of modern auction design in the face of economic constraints. It confirms that while return-on-investment limits complicate the bidding process, they do not make fair and profitable auctions impossible. By shifting the focus to what bidders can actually afford per unit of success, the researchers have provided a rigorous framework for designing systems that are both truthful and revenue-maximizing. Their work suggests that even in a world where bidders are cautious and constrained, sellers can rely on well-structured, deterministic rules to achieve outcomes that are nearly as good as the best possible theoretical limits, offering a path forward for the efficient design of the digital economies that power our daily lives.

Technical Summary: Auction Design with ROI-Constrained Bidders

Problem Statement

This paper addresses the design of truthful and revenue-maximizing auctions for bidders subject to Return-on-Investment (ROI) constraints. Unlike classical quasilinear settings where bidders maximize utility $v \cdot x - p$ , bidders in online advertising and similar markets often operate under the constraint that their payment $p$ cannot exceed a fixed fraction $1/r$ of their value $v \cdot x$ obtained from the auction. Formally, a bidder with valuation $v$ and ROI constraint $r$ derives utility $v \cdot x - p$ only if $p \leq (v/r)x$ ; otherwise, utility is $-\infty$ .

The core challenge lies in the multidimensionality of the bidder's type space $(v, r)$ . Standard mechanism design tools, which rely on one-dimensional types and immediate monotonicity properties, do not directly apply. The interaction between the valuation and the ROI constraint complicates the incentive compatibility (IC) and individual rationality (IR) conditions, making the characterization of truthful mechanisms and the derivation of optimal revenue significantly more difficult.

Methodology and Framework

1. Type Space Transformation

The authors introduce a transformation of the bidder's type from $(v, r)$ to $(v, c)$ , where $c = v/r$ is defined as the unit-payment cap.

Rationale: The ROI constraint $p \leq (v/r)x$ becomes $p \leq c \cdot x$ . This separates the concept of "affordability" (determined by $c$ ) from "utility comparison" (determined by $v$ ).
Type Space: The type space is redefined as $T = \{(v, c) : 0 \leq v \leq \bar{v}, v/\bar{r} \leq c \leq v\}$ .

2. Characterization of Truthful Mechanisms

The paper characterizes truthful mechanisms (Dominant Strategy Incentive Compatible and Individually Rational) by analyzing the allocation rule $x(v, c)$ and the unit payment $q(v, c) = p(v, c)/x(v, c)$ .

Allocation Properties: The authors derive monotonicity conditions (A1–A5) showing that allocation ordering is constrained by the relationship between a bidder's cap and the unit payments assigned to other types.
Payment Identity: By restricting the mechanism to specific one-dimensional subsets of the type space (the diagonal $v=c$ and fixed-cap slices $c=$ constant), the authors derive a closed-form payment identity:
$p(v, c) = v x(v, c) - \int_0^c x(z, z) \, dz - \int_c^v x(z, c) \, dz$
This result demonstrates that the allocation rule uniquely determines the payment rule, even in this two-dimensional setting.

3. Deterministic Mechanisms and Revenue Maximization

For the multi-bidder setting, the paper focuses on deterministic mechanisms.

Myerson-Cap Mechanism: Under the assumption of regularity (monotone virtual caps), the authors show that applying Myerson's optimal auction logic to the unit-payment caps rather than valuations provides a tight upper bound on the expected revenue of deterministic truthful mechanisms.
$\sigma$ -Increment Mechanisms: The standard Myerson-cap mechanism may fail to be DSIC at specific measure-zero points (ties). To restore truthfulness without sacrificing asymptotic revenue, the authors introduce $\sigma$ $σ$ -increment mechanisms. These mechanisms raise the winning threshold by a small $\sigma > 0$ $σ > 0$ .
- As $\sigma \to 0$ , the revenue of these mechanisms converges to the optimal deterministic revenue.
- Crucially, these mechanisms are shown to achieve at least a $1/\bar{r}$ fraction of the optimal expected revenue among all truthful mechanisms (including randomized ones).

4. Single-Bidder Pricing Functions

In the single-bidder setting, the authors shift from mechanism design to pricing functions $\pi(x)$ , where the bidder chooses quantity $x$ to maximize $vx - \pi(x)$ subject to $\pi(x) \leq cx$ .

Convexity Result: The paper proves that any truthful mechanism can be replaced by a continuous, convex, nondecreasing pricing function that yields weakly higher payments for every type.
Public Valuation ( $v$ known): When $v$ is public, the optimal pricing function is "zero up to a cutoff, then linear." Specifically, $\pi^*(x) = [vx - (v - c^*)]^+$ , where $c^*$ is a threshold determined by the distribution of caps.
Public ROI ( $r$ known): When $r$ is public and the valuation distribution satisfies the Decreasing Marginal Revenue (DMR) condition, the optimal pricing function follows a power law: $\pi^*(x) = (v^*/r)x^r$ . This function is strictly convex for $r > 1$ .

Key Contributions and Results

Exact Characterization of Truthfulness: The paper provides the first exact characterization of truthful mechanisms for bidders with private valuations and private ROI constraints. It establishes that the allocation rule uniquely determines the payment rule via a generalized envelope theorem, despite the multidimensional type space.
Asymptotic Optimality of Deterministic Mechanisms: The authors construct a family of deterministic mechanisms ( $\sigma$ -increment) that are truthful and asymptotically optimal among all deterministic truthful mechanisms.
Revenue Approximation Bounds: A significant result is the bound on the revenue gap between deterministic and randomized mechanisms. The deterministic mechanisms achieve at least $1/\bar{r}$ of the optimal revenue achievable by any truthful mechanism (randomized or deterministic), where $\bar{r}$ is the maximum possible ROI constraint.
Optimal Pricing under Partial Information:
- For public valuations, the optimal pricing strategy involves a "free" initial quantity followed by a linear price increase.
- For public ROI constraints, the optimal strategy is a power-law pricing function, generalizing the linear pricing of standard posted-price auctions ( $r=1$ ).
Reduction to Convex Pricing: In the single-bidder case, the problem of revenue maximization is reduced to finding an optimal convex pricing function, simplifying the design space significantly.

Significance and Claims

The paper claims to generalize existing results on auction design with constraints (such as budget constraints) to the specific and economically relevant case of ROI constraints. Unlike budget constraints where the payment cap is fixed ( $p \leq B$ ), ROI constraints scale with the allocation ( $p \leq (v/r)x$ ), creating a more complex incentive structure.

The authors emphasize that their characterization of truthful mechanisms resolves the difficulty of multidimensionality by utilizing the unit-payment cap representation. They note that while applying Myerson's mechanism directly to caps yields a revenue bound, it is not necessarily DSIC pointwise; their $\sigma$ -increment construction is necessary to ensure truthfulness while preserving the revenue bound.

The work bridges the gap between theoretical mechanism design and practical online advertising constraints, providing a rigorous foundation for understanding how ROI constraints impact revenue and the design of truthful auctions. The paper concludes that finding the optimal pricing function for the fully private setting (both $v$ and $r$ private) remains an open problem, though the reduction to convex pricing functions offers a clear path for future research.