Auction methods maximize revenue with bidders who limit investment returns
Auction Design with ROI-Constrained Bidders: Truthfulness and Revenue Maximization
Computer Science and Game Theory
Summary
Many auctions, like those for online ads, involve bidders who only want to pay a part of the value they expect to get. The authors study how to run auctions where both how much bidders value an item and their spending limits are private. They describe auctions that are truthful, meaning bidders are honest about their information, and show how to design them to earn high revenue. For one bidder, they also find simple pricing methods that work best when certain bidder details are public.
What this means in practice
- •For online advertising platforms: Create ad auctions that ensure bidders reveal true budgets and value constraints while maximizing platform revenue with ROI-based spending limits.$Commercial implications: Enables auction design tools improving ad platform revenue by handling private bidder ROI constraints accurately.
- •For digital marketplace operators: Design sales mechanisms for markets where buyers limit spending relative to perceived value, ensuring honest participation and better revenue.
Authors
Zhiqiang Zhuang, Quan Yu, Yisong Wang, Kewen Wang, Zhe Wang
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.