Abstract
This paper addresses the challenge of designing revenue-maximizing auctions for a "mixed" pool of bidders consisting of Utility Maximizers (UMs) and Value Maximizers (VMs). While UMs seek to maximize profit (value minus price), VMs aim to maximize total value obtained, often due to fixed budget constraints. We characterize the optimal auction structure when a bidder's type is private information, demonstrating that the optimal mechanism smoothly transitions from a first-price auction to a Myerson-style posted price as the likelihood of facing a UM increases.
Introduction
In classical auction theory, bidders are typically modeled as UMs. However, the prevalence of internet advertising and automated bidding has introduced VMs—algorithmic bidders that prioritize obtaining items over price efficiency. Real-world markets often involve a mixture of both types, but the auctioneer rarely knows a bidder's specific strategic type. This creates a multi-parameter incentive compatibility (IC) problem where bidders might misreport both their private value and their type. This paper provides a mathematical framework to design optimal auctions that prevent such manipulation while maximizing revenue.
Methodology
The authors employ several mathematical tools to solve the mixed-bidder optimization problem:
- IC Characterization: A characterization theorem establishes the necessary and sufficient conditions for an auction to be Incentive Compatible and Individually Rational. This allows revenue to be expressed solely as a function of the UM allocation rule.
- Variational Calculus: The revenue-maximizing allocation is treated as a functional optimization problem. The authors apply the Euler-Lagrange equation to derive a second-order Ordinary Differential Equation (ODE) that the optimal allocation must satisfy.
- Numerical Algorithms: To handle arbitrary distributions where analytical solutions are elusive, the authors propose numerical methods (e.g., Runge-Kutta) to compute optimal allocation and payment rules.
- Lookahead Auctions: For multi-bidder scenarios, a "lookahead auction" framework is introduced, utilizing a version of Border’s Theorem to simplify feasibility constraints and make optimization tractable.
Key Insights
- The Hybrid Spectrum: The optimal auction is not a static format but a spectrum. It ranges from a first-price auction (100% VM probability) to a Myerson auction (100% UM probability). Intermediate probabilities result in randomized hybrid mechanisms.
- Scoring Rules: In multi-bidder settings, the auctioneer assigns a "score" based on reported value and type. The item is allocated to the highest score, effectively handicapping different types to maximize expected revenue.
- Exploiting VM Behavior: VMs are generally less price-sensitive. The mechanism exploits this by pushing VMs toward first-price-style payments while maintaining IC constraints to prevent UMs from mimicking VMs.
Key Results and Phase Transitions
The paper provides a complete solution for the single-bidder case, showing how the optimal reserve price and allocation probability shift with the probability of a bidder being a UM. For uniform distributions, the authors identified three distinct "phases" in the optimal allocation rule.
As seen in the figure, the allocation rules for UMs and VMs follow different trajectories across these phases, constrained by interim feasibility. The lookahead auction framework successfully extends this logic to multiple bidders, allowing for numerical optimization of complex mixed-type distributions.
Limitations and Future Work
While the lookahead auction is the best within its class, its global optimality for all possible mixed-bidder auctions remains a conjecture. Additionally, the resulting mechanisms are complex and involve randomized allocations, which may be difficult to implement in practice compared to simpler second-price auctions. Future research should explore "simple" auction approximations and relax the assumption that the auctioneer has perfect knowledge of prior distributions.
Summary updated