Research map / Learning theory and algorithms / Submodular and game algorithms

Optimal Auction Design for Mixed Bidders

AAAI 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Learned auction design · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Characterizes revenue-optimal single-item auctions for a mix of utility maximizers and value maximizers with private types, deriving an ODE-based optimal mechanism for one bidder and an optimal lookahead auction for multiple bidders.

Problem

Revenue-maximizing auction design for selling one item to bidders who may be utility maximizers (UMs) or value maximizers (VMs), where the UM/VM type is private and the auctioneer cannot distinguish them.

Approach

Characterizes IC/IR interim allocations and payments for mixed UM/VM bidders (UMs pay Myerson payments, VMs pay first-price), reduces revenue to a function of the UM allocation, and uses variational methods plus a lookahead-auction restriction to find the optimal mechanism, which interpolates from first-price to Myerson as the UM probability goes from 0 to 1.

Key results

• For a single bidder, the optimal auction moves gradually from first-price auction (q=0) to Myerson auction (q=1) as the UM probability q increases from 0 to 1.
• Provides a numerical algorithm (Algorithm 2) for the revenue-optimal lookahead auction with multiple mixed bidders, illustrated for n=2, q=0.4, uniform values on [0,1].
• Derives a closed-form optimal mechanism for uniform value distributions (detailed in the full version).

Surprising findings

• A single-parameter IR and IC mechanism that only elicits values, without eliciting types, cannot achieve reasonable revenue for mixed bidders, especially when bidders are likely VMs.

Limitations

• Optimality among all mechanisms is established only for the single-bidder case; for multiple bidders the optimal auction is restricted to lookahead auctions and it is unknown whether this is optimal.
• Optimal mechanism is complex and randomized, which may be impractical compared to simple auctions.

Experimental setup

Metrics: revenue

Baselines: Myerson auction first-price auction

Builds on: Myerson auction Border's theorem

Closest papers by meaning

• Utility Maximizer or Value Maximizer: Mechanism Design for Mixed Bidders in Online Advertising (AAAI 2023 · similarity 0.92)
• Sample Complexity of Posted Pricing for a Single Item (NeurIPS 2024 · similarity 0.87)
• Simultaneous Optimization of Bid Shading and Internal Auction for Demand-Side Platforms (AAAI 2024 · similarity 0.87)
• No-Regret Online Autobidding Algorithms in First-price Auctions (NeurIPS 2025 · similarity 0.86)
• Increasing Revenue in Efficient Combinatorial Auctions by Learning to Generate Artificial Competition (AAAI 2025 · similarity 0.86)
• Maximizing the Success Probability of Policy Allocations in Online Systems (AAAI 2024 · similarity 0.85)