ROI constrained optimal online allocation in sponsored search

Wenjian Xu, Shui Liu, Zulong Chen, Ying Zhou, Liangyue Li, Yangyang Wang, Quan Lü, Yuxin Ji, Jian WanScientific 2024 · DOI

TL;DR

This paper introduces ROAM, a novel framework for optimizing ad allocation in sponsored search. ROAM simultaneously maximizes platform revenue and user experience while respecting advertiser ROI constraints, a critical but often overlooked aspect in prior work. Through a parameter-server based offline optimization and a clever online strategy, ROAM significantly boosts platform revenue and advertiser ROI, as validated by extensive offline and online A/B testing.

What Problem Does This Paper Address?

Sponsored search is a cornerstone of e-commerce revenue, where search engines display ads alongside organic results. The core challenge lies in "online allocation": deciding in real-time which ads to show for a given user query. Existing systems aim to maximize platform revenue, but this often comes at the expense of user experience, advertiser utility, or long-term platform health. A key gap is addressing advertiser Return on Investment (ROI) constraints, which are crucial for advertiser satisfaction and retention. Furthermore, the inherent conflict between offline allocation models (which might rank ads based on various factors) and the online auction mechanism (which typically uses eCPM) needs to be reconciled to ensure the allocation strategy effectively influences the final ad display. This paper tackles these issues by proposing a unified framework that balances platform revenue, user experience, and advertiser ROI, while also bridging the gap between offline optimization and online auction dynamics.

Methods

The proposed framework, ROAM (ROI constrained Optimal Allocation Model), has two main components:

  1. Offline Optimization:
    • Constrained Optimization Formulation: The problem is framed as a constrained optimization problem on a bipartite graph, where supply nodes represent user search requests and demand nodes represent ad campaigns. The objective is to maximize platform revenue while minimizing impressions (to preserve user experience) and satisfying budget and ROI constraints for advertisers.
  2. Parameter-Server Architecture: To handle the large scale of sponsored search, a parallel optimization algorithm is developed using a parameter-server architecture. This allows for efficient computation of dual variables and allocation probabilities.
  3. Lagrangian Relaxation and KKT Conditions: The optimization problem is solved by deriving its dual problem using KKT conditions, leading to an iterative update of dual variables.
  4. Online Strategy:
    • Conflict Resolution: A key innovation is the online strategy designed to bridge the gap between the offline allocation model's output and the online Generalized Second Price (GSP) auction. The allocation model determines an "optimal" ad, but this ad might not win the auction if it doesn't have the highest eCPM. To address this, ROAM reserves ads whose eCPM is lower than the predicted winning ad's eCPM to participate in the auction. This ensures that the allocation model's preference has a strong influence on the final ad selection, thereby maximizing platform revenue.

Datasets

The paper utilizes a real-world production dataset comprising:

  • 1.2 million requests (supply nodes)
  • 622 ad campaigns (demand nodes)
  • Over 4.8 million edges in the allocation bipartite graph.

For offline evaluation, model-estimated CTR and CVR were used to represent true values, as actual click and conversion probabilities are unknown. The paper also mentions generating a synthetic dataset for hyper-parameter sensitivity analysis, based on a dataset from a previous study (Ref. [31]).

Key Insights and Ideas

  • ROI as a First-Class Constraint: Explicitly incorporating advertiser ROI constraints into the allocation model is crucial for long-term platform health and advertiser satisfaction. Simply maximizing platform revenue can lead to advertiser churn if their ROI suffers.
  • Balancing Revenue and User Experience: The model's objective function explicitly balances platform revenue with user experience (by minimizing impressions), acknowledging that a good user experience is vital for sustained engagement and future revenue.
  • Bridging Offline Allocation and Online Auction: The proposed online strategy to reconcile the allocation model's output with the GSP auction mechanism is a significant practical contribution. It ensures that the offline optimization efforts translate into tangible improvements in the online serving environment.
  • Parameter-Server for Scalability: The adoption of a parameter-server architecture is essential for tackling the massive scale of real-world sponsored search systems, enabling efficient distributed computation.

Key Results

  • Offline Evaluation:
    • ROAM achieved the highest ROI among all tested methods, significantly outperforming OAM (ROAM without ROI constraint).
  • It maintained competitive performance in other metrics like Revenue, RPM, BCR, and GMV.
  • The model converged within 1000 iterations for ROI and BCR metrics.
  • Online A/B Testing:
    • ROAM demonstrated stable and significant improvements in both platform RPM and advertiser ROI over a 7-day period.
  • Crucially, ROAM was the only method that achieved a positive lift in RPM without sacrificing ROI.
  • ODBC showed the highest RPM lift but at the cost of a significant drop in ROI.
  • AUAF showed no significant lift in either RPM or ROI.
  • Production Stability: The ROAM model has been running stably in production for over three months since its launch.

Limitations and Future Work

  • Limitations:
    • The paper notes that for offline evaluation, model-estimated CTR and CVR were used as proxies for true values, as these are inherently unknown.
  • The paper doesn't explicitly detail limitations of the parameter-server architecture itself, but large-scale distributed systems inherently face challenges like network latency and synchronization.
  • Future Work:
    • The paper's conclusion suggests that the proposed model has made significant improvements, implying that further refinements and extensions are possible. However, specific future research directions are not explicitly detailed in the provided text. The focus is on the successful implementation and validation of the current ROAM framework.

Summary updated

Abstract

Sponsored search plays a major role in the revenue contribution of e-commerce platforms. Advertising systems are designed to maximize platform revenue, but other goals also need to be considered, such as user experience, advertiser utility, and how to achieve the long-term revenue goal. A key component of a sponsored search system is online allocation, which makes real-time decisions to match users' search requests with relevant ad campaigns to maximize platform revenue within constraints such as campaign budgets. Although much progress has been made, most of the research work on allocation problem has focused on satisfying guaranteed deals for display ads, and those challenges for allocation problems in sponsored search are not properly addressed. In this paper, we develop a framework to solve the large-scale sponsored search ad allocation problem, consisting of two main parts. One is an optimization problem solved offline by a parameter-server based architecture, and the other is an online strategy to alleviate the conflict with the auction mechanism during online service. Comprehensive offline evaluation on real production data and online A/B testing on real production system have been made. The experimental results demonstrate that through better allocating user queries to appropriate ads, the proposed model can significantly increase the platform's revenue without sacrificing advertisers' ROI.
BibTeX
@inproceedings{xu2024roi,
  author = {Wenjian Xu and Shui Liu and Zulong Chen and Ying Zhou and Liangyue Li and Yangyang Wang and Quan Lü and Yuxin Ji and Jian Wan},
  title = {{ROI constrained optimal online allocation in sponsored search}},
  booktitle = {Scientific},
  year = {2024},
  doi = {10.1038/s41598-024-77506-3},
}

Loading related content...

Figure