Multi-objective optimization for sponsored search

Yilei Wang, Bingzheng Wei, Jun Yan, Zheng Chen, Qiao Du2012 · DOI

TL;DR

This paper introduces a Multi-Objective Optimization (MOO) framework to simultaneously optimize sponsored search ad ranking for users, advertisers, and publishers. By leveraging the Pareto optimal solution set, it offers a more flexible and comprehensive approach to balancing conflicting objectives, leading to better overall performance and enabling novel applications like intelligent parameter selection.

What Problem Does This Paper Address?

Sponsored search, a cornerstone of online advertising, aims to display relevant ads to users in response to their queries, generating revenue for publishers and advertisers. However, the core challenge lies in the inherent conflict between the objectives of the three main participants: users (seeking relevance), advertisers (seeking clicks and ROI), and publishers (seeking revenue). Previous research has largely focused on optimizing one or two of these objectives independently, leading to potential trade-offs where improving one objective might degrade others. This paper addresses the gap of optimizing for all three participants in a unified, systematic framework, acknowledging that a truly effective ad ranking system must balance these competing interests.

Methods

The paper proposes modeling the sponsored search ad ranking problem as a Multi-Objective Optimization (MOO) problem. This means finding a set of ad rankings that represent the best possible trade-offs across multiple, often conflicting, objectives. The authors define three key objectives:

  • User Relevance: Measured by Discounted Cumulative Gain (DCG), aiming to show ads that are highly relevant to the user's query.
  • Advertiser Utility: Measured by Click-Through Rate (CTR), aiming to maximize the number of clicks advertisers receive.
  • Publisher Revenue: Measured by the sum of CTR * Cost-Per-Click (CPC) for all displayed ads, aiming to maximize the publisher's earnings.

The MOO framework allows for the generation of a Pareto optimal solution set, which contains all non-dominated rankings. This set provides a comprehensive view of possible trade-offs, allowing for flexible adjustments. The paper discusses several MOO solution methods, including the Weighted Sum Method, Lexicographic Method, and Genetic Method, ultimately employing an evolutionary strategy (a type of genetic method) for their experiments.

A key novel application presented is using the MOO framework to predict optimal trade-off parameters. By analyzing the Pareto optimal set, they can train models to recommend parameter configurations that achieve desired balances between objectives, a task that is difficult with traditional single-objective optimization.

Datasets

The experiments were conducted using a dataset collected from a commercial search engine over three days, containing search queries, returned ads, and click history. This dataset comprised 3,601,305 queries. For evaluation, a 5-level grade for ad relevance was assigned based on editorial judgments. The paper does not introduce new benchmarks but uses a real-world dataset for empirical validation.

Key Insights and Ideas

  • Unified Framework: The MOO framework elegantly unifies the optimization problem for all three key participants (users, advertisers, publishers), which was previously underexplored.
  • Special Cases: Many existing sponsored search optimization methods are shown to be special cases of this MOO framework, highlighting the generality of their approach.
  • Pareto Optimality for Flexibility: The Pareto optimal solution set provides a rich landscape of trade-offs, allowing for more nuanced decisions than single-objective optimization. This enables finding solutions that might be slightly suboptimal in one area but significantly better overall.
  • CTR as an Independent Objective: Explicitly treating CTR as an individual objective, rather than just a feature, is crucial for advertiser satisfaction and can lead to more balanced outcomes.
  • Intelligent Parameter Selection: The MOO framework facilitates the development of predictive models for selecting optimal trade-off parameters, a significant practical advantage for tuning ad ranking systems.

Key Results

  • Completeness: The MOO framework's Pareto Set was shown to contain results from single-objective optimizations and RnR (Relevance and Revenue) optimizations, demonstrating its comprehensive nature. In experiments, the MOO framework covered approximately 80% of single-objective optimization results within 50 iterations.
  • Balanced Performance: While single-objective optimizations excelled in their specific metrics, MOO provided more balanced results across all three objectives (Relevance, CTR, Revenue). For instance, MOO achieved a good balance, outperforming some single-objective methods in certain metrics while maintaining competitive performance in others.
  • Parameter Prediction Efficiency: The proposed parameter prediction model, trained using MOO-generated data, significantly speeds up the process of finding optimal parameter configurations compared to naive enumeration. The paper claims a potential speedup of 20 times for training data generation.
  • Empirical Validation: Experimental results demonstrated the effectiveness of the MOO framework in generating a diverse set of optimized ad rankings and its utility in applications like parameter selection.

Limitations and Future Work

  • Real-time Integration: The authors acknowledge that a significant future direction is integrating the MOO framework with real-time search engines, which presents unique challenges.
  • Formalized Standards: They suggest the need for formalizing specific standards to objectively compare different ranking functions and their effectiveness.
  • Orthogonal Experimental Design: For online search engines, they propose exploring orthogonal experimental design to find optimized solutions more efficiently.

Summary updated

Abstract

Sponsored search has been recognized as one of the major internet monetization solutions for commercial search engines. There are generally three types of participants in this online advertising problem, who are search users, advertisers and publishers. Though previous studies have proposed to optimize for different participants independently, it is underexplored how to optimize for all participants in a unified framework and in a systematic way. In this paper, we propose to model the ad ranking problem in sponsored search as a Multi-Objective Optimization (MOO) problem for all participants. We show that many previous studies are special cases of the MOO framework. Taking advantage from the Pareto solution set of MOO, we can easily find more optimized solutions with significant improvement in one objective and minor sacrifice in others. This enables a more flexible way for us to tradeoff among different participants, i.e. objective functions, in sponsored search. Besides the empirical studies for comparing MOO with related previous sponsored search studies, we provide the insightful applications of MOO framework, which is a prediction model to help users determine the tradeoff parameters among different objective functions. Experimental results show the outstanding performance of the proposed prediction model for parameter selection in ad ranking optimization.
BibTeX
@misc{wang2012multi,
  author = {Yilei Wang and Bingzheng Wei and Jun Yan and Zheng Chen and Qiao Du},
  title = {{Multi-objective optimization for sponsored search}},
  year = {2012},
  doi = {10.1145/2351356.2351359},
}
Figure