Abstract
In sponsored search auctions, the environment is dynamic and agents behave strategically. This paper addresses the search engine's dynamic pricing problem by combining mechanism design with reinforcement learning. We first train an LSTM-based buyer behavior model using real-world data from Baidu to predict bid distributions. We then formulate the pricing problem as a Markov Decision Process (MDP) and employ Monte-Carlo Tree Search (MCTS) to optimize reserve prices over time. Our approach significantly outperforms traditional static optimization strategies and simpler dynamic models.
Introduction
The Generalized Second Price (GSP) auction is the standard for online advertising. While theoretical models like Myerson’s suggest optimal reserve prices, they often assume bidders are perfectly rational with static preferences. In practice, bidders have budget constraints and diverse goals. Crucially, they exhibit a "second-order effect": changing pricing rules causes bidders to adapt their strategies. This creates a "moving target" problem that static optimization cannot solve. We propose a "Reinforcement Mechanism Design" framework to dynamically adjust to these strategic human players.
Methods
The proposed framework consists of two primary components: an RNN-based bidder behavior model and an MCTS-based optimization algorithm.
- RNN-based Bidder Behavior Model: Instead of assuming rationality, we use a Long Short-Term Memory (LSTM) network to predict future bid distributions. The model processes "private" features (past bids, clicks, impressions, payments) and "public" features (temporal data). This allows the system to learn how bidders react to environmental changes without explicit utility functions.
- MDP and MCTS Optimization: The pricing problem is modeled as an MDP where the state is the current bid distribution and the action is setting the reserve price. To navigate the massive state space, we utilize Monte-Carlo Tree Search (MCTS) to maximize long-term discounted revenue by looking several steps ahead.
Datasets
The study uses a massive dataset from Baidu, consisting of 8 months of bidding data (70TB). We focused on 400 keywords in "thin markets" where the top three bidders generate over 80% of the revenue. The bidder model was trained on a 90/10 split, followed by 120-day simulations to evaluate the mechanism design.
Key Results
The MCTS-based dynamic strategy consistently outperformed all baselines, including Baidu’s legacy system and static optimal pricing.
- Long-term Stability: Aggressive static pricing often yields a short-term revenue spike followed by a crash as bidders lower their bids. The MCTS strategy maintains higher revenue by accounting for these long-term strategic shifts.
- Model Performance: The LSTM bidder model achieved high accuracy (cross-entropy loss ~1.67), capturing nuanced shifts in bid distributions.
- Real-world Impact: This framework was implemented in Baidu’s production system, contributing to a significant revenue increase reported in their 2018 Q1 financial results.
Discussion and Limitations
While successful in thin markets, scaling this approach to "thick markets" with hundreds of bidders presents computational challenges due to the complexity of MCTS. Future work will focus on improving computational efficiency and addressing fairness concerns related to personalized reserve prices, potentially incorporating constraints for advertiser welfare.
Summary updated