Preferred Deals in General Environments

Yuan Deng, Sébastien Lahaie, Vahab S. Mirrokni

Abstract

Preferred deals allow publishers to offer advertisers priority access to ad space at pre-negotiated prices. However, designing these deals is complicated by real-world constraints such as advertiser budget limits and inventory diversity requirements. This paper introduces a robust framework based on the Auction-Adjusted Greedy (AAG) algorithm, enhanced with a Constraint-aware Social Welfare (CAW) oracle. Evaluated on real-world Google Ad Exchange data, the proposed AAGBudget algorithm consistently achieves 94% to 99% of the liquid welfare benchmark, maintaining high performance across varying budget levels where traditional methods fail.

Introduction

In online advertising, "preferred deals" serve as a hybrid between traditional fixed-price reservations and real-time auctions. They grant advertisers "first dibs" on specific impressions at a fixed price; if declined, the inventory proceeds to the open auction. While lucrative, optimizing these deals is mathematically complex. Advertisers often operate under strict budget limits and volume constraints (e.g., demographic targeting limits). Previous research frequently overlooked these constraints, resulting in deals that were either unaffordable or unacceptable to buyers. This paper addresses this gap by developing a model that respects general convex constraints while maximizing publisher revenue.

Methodology

The authors extend the Auction-Adjusted Greedy (AAG) framework to handle complex constraints through a "Constraint-aware Social Welfare" (CAW) oracle. Instead of merely targeting the highest valuation, the CAW benchmark accounts for what buyers can actually afford (budgets) and what they are permitted to purchase (personalized constraints).

To ensure computational feasibility for millions of impressions, the authors utilize an Interim Allocation Reduction technique. This method shifts the focus from tracking individual ad impressions to tracking the probability of a buyer receiving specific types of inventory. This reduction transforms a massive discrete problem into a manageable convex program.

Experimental Setup

The researchers evaluated the algorithm using real-world auction data from the Google Ad Exchange (AdX). The study focused on five high-volume inventory units, analyzing the first 100,000 auctions for each where at least two of the top 50 frequent buyer-bid pairs were present. Given that second-price auctions are truthful, the bids in the dataset were treated as the advertisers' true valuations.

Results and Discussion

Revenue and welfare performance of AAGBudget compared to baselines across varying budget levels.

A key insight from the study is the "cherry-picking" factor: in preferred deals, buyers strategically select impressions that best fit their budgets and constraints. The AAGBudget algorithm accounts for this behavior to set optimal prices. The evaluation shows that while standard Second-Price Auctions (SPA) perform well at low budget levels and the original AAG performs well at high budget levels, only AAGBudget maintains high performance across the entire spectrum of budget ratios.

Performance metrics for AAGBudget and baselines across five distinct inventory units.

As shown in the data, AAGBudget consistently reached 94% to 99% of the liquid welfare benchmark across different inventory types. It significantly outperformed both the original budget-agnostic AAG and standard SPA baselines.

However, the authors noted a theoretical "hard limit": for environments with "general correlation" (where valuations are arbitrarily linked), no algorithm can guarantee a constant-factor approximation. Revenue in such cases might drop to $1/n$ of the maximum possible welfare. Conversely, if valuations are independent or additively correlated, constant-factor approximations (1/2 or 1/3) are achievable.

Conclusion

This research demonstrates that incorporating budget and diversity constraints into preferred deal design is both necessary and effective. The AAGBudget algorithm provides a stable, high-performing solution for publishers. Future work will focus on improving theoretical approximation ratios and exploring the integration of preferred deals with other selling methods, such as open auctions and traditional reservation contracts, into a single unified system.

Summary updated

Abstract

A preferred deal is a special contract for selling impressions of display ad inventory. By accepting a deal, a buyer agrees to buy a minimum amount of impressions at a fixed price per impression, and is granted priority access to the impressions before they are sent to an open auction on an ad exchange. We consider the problem of designing preferred deals (inventory, price, quantity) in the presence of general convex constraints, including budget constraints, and propose an approximation algorithm to maximize the revenue obtained from the deals. We then evaluate our algorithm using auction data from a major advertising exchange and our empirical results show that the algorithm achieves around 95% of the optimal revenue.
BibTeX
@inproceedings{deng2019preferred,
  author = {Yuan Deng and Sébastien Lahaie and Vahab S. Mirrokni},
  title = {{Preferred Deals in General Environments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/33},
}
Figure