A General Framework for Evaluating Callout Mechanisms in Repeated Auctions

Hossein Azari, William D. Heavlin, Hoda Heidari, Max Lin, Sonia TodorovaarXiv 2017 · arXiv · OpenReview

TL;DR

This paper introduces a novel framework for evaluating different strategies (callout mechanisms) that online ad exchanges use to decide which advertisers to invite to auctions. By simulating these strategies on historical data, the authors show that smarter mechanisms can significantly boost revenue and social welfare compared to simple random methods, while also being computationally more efficient.

What Problem Does This Paper Address?

Online ad exchanges operate by running numerous auctions for ad slots. A key challenge is that advertisers (bidders) have limitations on how many auctions they can participate in per second (their "quota"). To manage this, exchanges typically use "random quota throttling" (RQT), which randomly selects bidders. However, exchanges collect a lot of data about bidder behavior over time. This paper argues that this historical data can be leveraged to design much more effective "callout mechanisms" that strategically invite bidders, leading to higher long-term revenue for the exchange. The core problem is how to evaluate and compare these sophisticated callout mechanisms without costly real-world experiments, and to understand how strategic bidder behavior impacts these mechanisms.

Methods

The authors propose a general framework for evaluating callout mechanisms using only historical auction data. This framework involves:

  1. A Strategic Model: They develop a two-stage game-theoretic model to capture the repeated interaction between the exchange and strategic bidders. This model helps understand how bidders adapt their behavior based on the exchange's callout strategy and how this affects long-term revenue.
  2. Performance Metrics: Based on the model, they define two key metrics:
  3. Immediate Revenue Impact: How much revenue a callout mechanism generates in a single auction.
  4. Social Welfare: A measure of the overall value generated, approximated by bids.
  5. Empirical Framework: They devise methods to estimate these metrics from historical bidding data. This allows for simulating and comparing different callout mechanisms without live experiments.
  6. Callout Mechanisms: They propose several "myopic symmetric thresholding" heuristics (e.g., based on past bidding, winning, or spending) and compare them against baselines like RQT and a theoretically grounded Greedy Algorithm (GRA).

Datasets

The paper uses two types of datasets for evaluation:

  1. Synthetic Auction Data: Generated to allow for controlled experiments with varying parameters like reserve price, bidder variance, and the number of auctions.
  2. Real Auction Data: Collected from Google's DoubleClick Ad Exchange, consisting of bids from 100 buyers over three consecutive weekdays for similar auctions.

Key Insights and Ideas

  • Beyond Randomness: Simple random quota throttling (RQT) is a poor baseline. Even basic heuristics that leverage historical data can significantly outperform it.
  • Strategic Bidders Matter: Bidders aren't passive; they react to callout strategies. A mechanism that boosts short-term revenue might hurt long-term revenue if it drives bidders away by not providing sufficient utility.
  • Information is Power: Heuristics that incorporate more information about a bidder's past behavior and their potential revenue impact (like the proposed Shapley's Linear Heuristic, ShA) perform best.
  • Trade-off Between Revenue and Utility: Exchanges face a trade-off: increasing callouts can boost immediate revenue, but it must be balanced with maintaining bidder utility to ensure their continued participation and long-term revenue.

Key Results

  • Significant Revenue Gains: Sophisticated heuristics, particularly Shapley's Linear Heuristic (ShA), consistently outperform baselines like RQT and GRA. In some settings, ShA achieved up to 50% more revenue than RQT and 25% more than GRA.
  • Computational Efficiency: Many of the proposed heuristics are computationally faster than the baselines, making them practical for real-world deployment.
  • Robustness: The relative performance of heuristics remains consistent across different synthetic data settings (varying reserve price, variance, and number of items) and on real-world data.
  • Heuristic Performance Ranking: A general trend observed is ShA > BID > {RNK, RVC, GRA} > {SPD, WIN, RQT, BAR}.

Limitations and Future Work

  • Myopic Heuristics: The proposed heuristics are largely "myopic," meaning they don't explicitly consider the long-term consequences of today's callout decisions on future bidder behavior.
  • Simplified Bidder Model: The strategic model assumes bidders choose the exchange that offers the highest utility, which is a simplification of real-world complex decision-making.
  • Future Directions: The authors suggest exploring more complex callout mechanisms, including those with more sophisticated learning steps, those that combine multiple heuristics, and mechanisms that use non-myopic or dynamic targeting. They also mention extending the framework to different auction mechanisms and bidding distributions.

Summary updated

Abstract

Motivated by online display ad exchanges, we study a setting in which an exchange repeatedly interacts with bidders who have quota, making decisions about which subsets of bidders are called to participate in ad-slot-specific auctions. A bidder with quota cannot respond to more than a certain number of calls per second. In practice, random throttling is the principal solution by which these constraints are enforced. Given the repeated nature of the interaction with its bidders, the exchange has access to data containing information about each bidder's segments of interest. This information can be utilized to design smarter callout mechanisms --- with the potential of improving the exchange's long-term revenue. In this work, we present a general framework for evaluating and comparing the performance of various callout mechanisms using historical auction data only. To measure the impact of a callout mechanism on long-term revenue, we propose a strategic model that captures the repeated interaction between the exchange and bidders. Our model leads us to two metrics for performance: immediate revenue impact and social welfare. Next we present an empirical framework for estimating these two metrics from historical data. For the baseline to compare against, we consider random throttling, as well as a greedy algorithm with certain theoretical guarantees. We propose several natural callout mechanisms and investigate them through our framework on both synthetic and real auction data. We characterize the conditions under which each heuristic performs well and show that, in addition to being computationally faster, in practice our heuristics consistently and significantly outperform the baselines.
BibTeX
@misc{azari2017general,
  author = {Hossein Azari and William D. Heavlin and Hoda Heidari and Max Lin and Sonia Todorova},
  title = {{A General Framework for Evaluating Callout Mechanisms in Repeated Auctions}},
  year = {2017},
  eprint = {1702.01803},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1702.01803},
}
Figure