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
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.
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