Learning the Allowance: Truthful-Approximate Sponsored Search with Unknown Auto-Bidder Constraints

Xu et al. (2024) introduce an allowance utility model that unifies quasi-linear and value-max bidders, showing strong guarantees when allowances are known and more modest ones when private. Balseiro et al. (2021) show robust benefits of reserves across bidder types with auto-bidding. We propose a mechanism that internally learns each bidder’s effective allowance from bidding trajectories—detecting the shift from value-max to utility-max behavior—using hybrid predictors inspired by Wang & Yu (2024)’s integration of game-theoretic priors with ML. The mechanism sets dynamic reserve prices and additive boosts tailored to inferred allowances, while committing to a payment rule that is approximately truthful in the learned-allowance model and robust when misclassification occurs. Unlike Xu et al., who analyze known versus private allowances, we address the realistic case where the platform never observes true allowances but can statistically recover “shadow allowances” with confidence bounds, designing payments to be insensitive within those bounds. The novelty is to turn type heterogeneity from a modeling headache into a design feature: a single mechanism that adapts to mixed bidder populations, maintaining welfare guarantees akin to Balseiro’s robustness and shrinking the gap between the public-allowance and private-allowance worlds.

References:

1. Robust Auction Design in the Auto-bidding World. S. Balseiro, Yuan Deng, Jieming Mao, V. Mirrokni, Song Zuo (2021). Neural Information Processing Systems.
2. Sponsored Search Auction Design Beyond Single Utility Maximization. Changfeng Xu, Chao Peng, Chenyang Xu, Zhengfeng Yang (2024). International Computing and Combinatorics Conference.
3. Predicting Real-World Penny Auction Durations by Integrating Game Theory and Machine Learning. Yujia Wang, Haoran Yu (2024). AAAI Conference on Artificial Intelligence.