Multiplicative bidding in online advertising

MohammadHossein Bateni, Jon Feldman, Vahab S. Mirrokni, Sam Chiu-wai Wong

Abstract

In modern search advertising, advertisers often set bids using a base value adjusted by multipliers for specific features like location or device. This paper formalizes the optimization problem of setting these multipliers under a budget constraint. We prove that while the general problem is $\Omega(\sqrt{n})$-hard to approximate, leveraging real-world properties such as multiplicative prices and monotone values allows for an $O(\log n)$-approximation algorithm that significantly outperforms standard bidding strategies.

Introduction

Real-time ad auctions (e.g., Google AdWords) require advertisers to value ad placements across diverse contexts. To simplify this, search engines introduced bid adjustments. An advertiser sets a base bid and applies multipliers for different dimensions. For instance, a $1.00 base bid with a 1.1x multiplier for California and a 1.2x multiplier for mobile devices results in a final bid of $1.32.

While convenient, this bidding language is mathematically restrictive. It cannot easily express complex, non-linear cross-feature valuations. This paper investigates how an advertiser can optimally set these row and column multipliers in a 2D feature space to maximize total value within a budget, treating it as a highly constrained version of the classic knapsack problem.

Problem Formulation

The authors model the problem as a 2D grid of $m \times n$ possible feature combinations. Each cell $(i, j)$ has a price $p_{ij}$ and a value $v_{ij}$. The advertiser must choose row multipliers $r_i$ and column multipliers $c_j$ such that the effective bid $r_i \cdot c_j \ge p_{ij}$ to "capture" the cell and gain its value.

A core difficulty is cross-contamination: if multipliers are high enough to capture cell (A, A) and cell (B, B), the multiplicative structure forces the advertiser to also capture either (A, B) or (B, A). One cannot isolate diagonal targets without buying off-diagonal collateral.

Theoretical Bounds

The paper establishes a hierarchy of complexity based on the properties of the price and value distributions. In the general case, the problem is proven to be $\Omega(\sqrt{n})$-hard to approximate. However, by identifying specific structures common in real-world data—specifically multiplicative prices and monotone values—the authors derive much tighter approximation bounds.

Summary of hardness results and algorithmic approximation ratios for various bidding scenarios.

As shown in the table above, the introduction of multiplicative prices and monotone values reduces the approximation ratio from $O(\sqrt{n})$ to $O(\log n)$. The "staircase" structure is key here: if prices are multiplicative, the optimal set of captured cells forms a staircase shape where the set of captured cells in one column is a strict subset or superset of those in another.

Empirical Evaluation

The authors evaluated their algorithms using a dataset of 1,000 anonymized advertisers from Google AdWords, focusing on "geo" (location) and "keyword" dimensions. Historical conversion data served as a proxy for value, while cost-per-click (CPC) data represented price.

Key findings include:

  • Data Consistency: Market prices are highly multiplicative (linear regression fit $R^2 = 0.94$), and values exhibit strong monotonicity, validating the theoretical assumptions.
  • Performance: A ratio-based "staircase" optimization algorithm achieved 85% of the theoretical optimum on average (median 92%), compared to only 64% for a baseline uniform bidding strategy.

Conclusion

This work provides the first formal treatment of multiplicative bidding optimization. While the general problem is theoretically difficult, the structure of real-world auction data allows for efficient approximation algorithms. Future work includes extending these models to higher dimensions and incorporating non-uniform supply constraints and generalized second-price (GSP) auction mechanics.

Summary updated

BibTeX
@inproceedings{bateni2014multiplicative,
  author = {MohammadHossein Bateni and Jon Feldman and Vahab S. Mirrokni and Sam Chiu-wai Wong},
  title = {{Multiplicative bidding in online advertising}},
  booktitle = {EC},
  year = {2014},
  doi = {10.1145/2600057.2602874},
}
Figure