Reinforcement Mechanism Design: With Applications to Dynamic Pricing in Sponsored Search Auctions

Weiran Shen, Binghui Peng, Hanpeng Liu, Michael Zhang, Ruohan Qian, Yan Hong, Zhi Guo, Zongyao Ding, Pengjun Lu, Pingzhong Tang

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.

Interaction between the bidder model and the search engine mechanism over time.
  1. 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.
  2. 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.

Comparison of daily revenue across different pricing strategies over a 120-day simulation.
  • 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

Abstract

In many social systems in which individuals and organizations interact with each other, there can be no easy laws to govern the rules of the environment, and agents' payoffs are often influenced by other agents' actions. We examine such a social system in the setting of sponsored search auctions and tackle the search engine's dynamic pricing problem by combining the tools from both mechanism design and the AI domain. In this setting, the environment not only changes over time, but also behaves strategically. Over repeated interactions with bidders, the search engine can dynamically change the reserve prices and determine the optimal strategy that maximizes the profit. We first train a buyer behavior model, with a real bidding data set from a major search engine, that predicts bids given information disclosed by the search engine and the bidders' performance data from previous rounds. We then formulate the dynamic pricing problem as an MDP and apply a reinforcement-based algorithm that optimizes reserve prices over time. Experiments demonstrate that our model outperforms static optimization strategies including the ones that are currently in use as well as several other dynamic ones.
BibTeX
@inproceedings{shen2020reinforcement,
  author = {Weiran Shen and Binghui Peng and Hanpeng Liu and Michael Zhang and Ruohan Qian and Yan Hong and Zhi Guo and Zongyao Ding and Pengjun Lu and Pingzhong Tang},
  title = {{Reinforcement Mechanism Design: With Applications to Dynamic Pricing in Sponsored Search Auctions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=K5HzyugpELE},
}
Figure