Optimal Auction Design for Mixed Bidders

Xiaohui Bei, Pinyan Lu, Zhiqi Wang, Tao Xiao, Xiang Yan

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Optimal allocation rules for mixed bidders showing distinct phases for Utility Maximizers (UM) and Value Maximizers (VM).

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

Abstract

The predominant setting in classic auction theory considers bidders as utility maximizers (UMs), who aim to maximize quasi-linear utility functions. Recent autobidding strategies in online advertising have sparked interest in auction design with value maximizers (VMs), who aim to maximize the total value obtained. In this work, we investigate revenue-maximizing auction design for selling a single item to a mix of UMs and VMs. Crucially, we assume the UM/VM type is private information of a bidder. This shift to a multi-parameter domain complicates the design of incentive compatible mechanisms. Under this setting, we first characterize the optimal auction structure for auctions with a single bidder. We observe that the optimal auction moves gradually from a first-price auction to a Myerson auction as the probability of the bidder being a UM increases from 0 to 1. We also extend our study to multi-bidder setting and present an algorithm for deriving the optimal lookahead auction with multiple mixed types of bidders.
BibTeX
@inproceedings{bei2025optimal,
  author = {Xiaohui Bei and Pinyan Lu and Zhiqi Wang and Tao Xiao and Xiang Yan},
  title = {{Optimal Auction Design for Mixed Bidders}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i13.33487},
}
Figure