Introduction
This paper bridges the gap between traditional auction theory and the modern reality of "autobidding" in online advertising. The authors demonstrate that while ROI-constrained value maximizers are fundamentally harder to price for than traditional utility maximizers, simple anonymous posted-price mechanisms can still guarantee at least ~31.6% of the optimal welfare as revenue. Remarkably, these guarantees hold even in complex dynamic or combinatorial settings.
The Problem: Utility Maximizers vs. Value Maximizers
In classical auction theory, bidders are typically modeled as utility maximizers: agents who want to maximize the difference between their value for an item and the price they pay ($v - p$). However, the landscape of online advertising has shifted heavily toward autobidding. Modern advertisers specify high-level goals, such as a target Return on Investment (ROI), and allow algorithms to bid on their behalf.
These autobidding agents are value maximizers: they aim to accumulate as much total value as possible, provided they do not violate a minimum ROI constraint (e.g., "I want as many clicks as possible, as long as my average cost per click remains under $1").
While complex mechanisms like VCG can theoretically extract full welfare from these agents, they are notoriously "brittle." They require the seller to have perfect prior knowledge of bidder values; if the seller's beliefs are even slightly inaccurate, the mechanism's performance can collapse. This paper seeks simple, robust, and prior-independent solutions—specifically posted-price auctions—that function effectively even when the seller lacks knowledge of the bidders' underlying value distributions.
Methodology
The authors analyze Sequential Posted Price Mechanisms, where the seller approaches buyers sequentially and offers a take-it-or-leave-it price. They investigate three primary scenarios:
- Personalized Prices: The seller can offer a distinct price to each buyer.
- Anonymous Prices: The seller must offer the identical price to all buyers.
- Dynamic/Prior-Independent: The seller does not know the value distributions beforehand and must learn the optimal price over time.
For the anonymous case, the researchers analyze the performance of the "usual price": setting the price to exactly half of the expected maximum value across all buyers ($\frac{1}{2} \mathbb{E}[\max_i v_i]$). To establish the theoretical limits of what is possible (the "upper bound"), they utilized a computer-aided search over structured "binary" value distributions (where a buyer's value is either a fixed high number or zero) to identify worst-case scenarios where anonymous pricing performs poorly.
Key Insights and Results
The ROI Complexity Gap
For traditional utility maximizers, an anonymous price can achieve a $1/2$ (50%) approximation of optimal welfare. This paper proves that this benchmark is impossible for ROI-constrained value maximizers. Through their computer-aided search, the authors found a counter-example demonstrating that no anonymous price can achieve better than a ~0.479 approximation (Theorem 3).
The Power of Personalization
If a mechanism can charge different prices to different buyers, value maximizers become no harder to handle than utility maximizers. In fact, the ROI constraint becomes "binding," meaning the seller can extract the entire value as revenue. The authors show that personalized pricing achieves a 1/2 approximation of optimal welfare as revenue (Proposition 4).
The 0.316 Guarantee
Even though the 50% mark is unreachable with anonymous prices, the authors prove that the standard "half-the-expected-max" price still yields a $\frac{1}{2}(1 - 1/e) \approx 0.316$ approximation (Theorem 4). This is a "tight" result for this specific pricing strategy, meaning there are specific cases where this strategy cannot perform any better.
Learning on the Fly
By framing the search for the best anonymous price as a Multi-Armed Bandit problem, the authors created a mechanism that learns the optimal price over time with $O(T^{2/3})$ regret. To the best of their knowledge, this provides the first constant revenue guarantee for multiple value maximizers in a dynamic, prior-independent setting.
Combinatorial Auctions
Extending their findings to complex settings with multiple items and submodular/XOS agents, the authors achieved a 1/4 approximation of welfare (Proposition 7).
Limitations and Future Work
The paper opens several avenues for future research:
- The Approximation Gap: There remains a theoretical gap between the $0.316$ lower bound and the $0.479$ upper bound for anonymous pricing. Determining the "true" optimal ratio for anonymous pricing is an open question.
- Revenue in Combinatorial Settings: The current results for combinatorial auctions apply primarily to welfare (total value created), rather than revenue (money collected by the seller). Extending these guarantees to revenue is a critical next step.
- Regret Bounds: While achieving $O(T^{2/3})$ regret is a solid foundation for the dynamic setting, future work could investigate whether this can be tightened to $O(T^{1/2})$ or better.
Summary updated