Abstract
Modern online advertising relies heavily on automated bidding tools designed to satisfy specific marketing objectives, most notably Return on Investment (ROI). While existing literature primarily addresses ex ante ROI constraints—where targets are met on average—this paper investigates the more stringent ex post (or "hard") ROI constraint. Such constraints are vital for "long-tail" advertisers who participate in fewer auctions and require guaranteed returns on every transaction. We characterize the structure of dominant-strategy incentive compatible (DSIC) auctions in this setting and demonstrate that the revenue-optimal auction for ROI-constrained bidders necessitates a randomized allocation scheme and a unique "rebate" payment rule, departing significantly from classic Myersonian auction theory.
Introduction
In the landscape of digital advertising, the transition from manual bidding to algorithmic auto-bidding has shifted the focus of auction design. Advertisers no longer bid solely based on a fixed valuation; instead, they optimize for high-level goals like ROI, defined as the ratio of value gained to the price paid.
Standard auction theory typically assumes quasilinear utility and ex ante constraints. However, for many advertisers, an average ROI is insufficient. They require an ex post ROI constraint, ensuring that for every single realized value profile, the ROI target is met. This "hard" constraint fundamentally alters the bidder's utility function, making standard tools like Myerson’s Lemma difficult to apply directly. This paper addresses this gap by characterizing truthful mechanisms and deriving the optimal auction for bidders with these hard constraints.
Characterizing Truthfulness: The Rebate Rule
The authors first extend the foundational principles of mechanism design to accommodate ROI constraints. In a standard single-parameter environment, a mechanism is truthful if its allocation rule is monotone and its payment rule follows a specific integral form.
Under ex post ROI constraints (where $Value / Price \geq M_i$ for a target $M_i$), the authors prove Theorem 2, which provides a full characterization of DSIC and individually rational (IR) auctions. The most striking discovery is the unique payment rule required for truthfulness. It resembles the classic Myerson payment but incorporates a "rebate" term. This rebate is calculated as the maximum violation of the ROI constraint across all lower possible valuations, effectively lowering the price to ensure the hard ROI floor is never breached. This ensures that even when a bidder's value is low, their payment is adjusted to maintain the required ROI.
The Optimal Single-Bidder Auction
While truthfulness can be characterized for multiple bidders, finding the revenue-maximizing auction is more complex. The authors focus on the single-bidder case to derive the optimal structure.
The Necessity of Randomization
In classic auctions, optimal mechanisms are usually deterministic—the bidder either wins the item or they do not. However, the authors show that under hard ROI constraints, randomization is necessary to maximize revenue. To find the optimal allocation, they utilize the Decreasing Marginal Revenue (DMR) condition. This regularity assumption implies that expected revenue is concave in the value space, which is more natural for ROI-constrained settings than the standard regularity used in Myerson’s work.
The First-Price Interval
According to Theorem 5, the optimal auction for a single bidder consists of two distinct phases:
- The Randomized Interval: For lower valuations, the auction follows a "first-price" logic. The allocation probability $x(v)$ increases according to a power-law-like curve ($x(v) \propto v^{1/(M-1)}$). In this range, the payment exactly matches the bidder's maximum willingness to pay allowed by the ROI constraint, extracting as much surplus as possible while remaining compliant.
- The Flat Interval: Once the allocation probability reaches 1, the auction becomes deterministic for all higher valuations, maintaining a constant payment.
Performance and Revenue Gains
To illustrate the efficacy of this design, the authors provide a numerical example using a uniform distribution $U[0,1]$ and an ROI target of $M=2$.
- Standard Myerson Auction: Yields an expected revenue of $0.25$.
- Optimal ROI-Constrained Auction: Yields an expected revenue of $0.375$.
This $50\%$ increase in revenue demonstrates that by specifically accounting for the ROI constraint through randomization and the rebate rule, the seller can significantly outperform traditional mechanisms that were not designed for these modern bidder objectives.
Limitations and Future Directions
The current characterization of the optimal revenue-maximizing auction is limited to the single-bidder scenario. While the conditions for truthfulness (Theorem 2) apply to multiple bidders, determining the optimal allocation when multiple ROI-constrained bidders compete remains a significant challenge.
Future research may explore:
- Multi-bidder Optimality: Solving the "very challenging" problem of revenue maximization in competitive environments.
- Private ROI Targets: Investigating scenarios where the ROI target ($M_i$) is private information, leading to a multi-dimensional mechanism design problem.
- Empirical Validation: Testing how well these ex post constraints align with the actual behavior of long-tail advertisers in real-world ad exchanges.
Summary updated