Online Allocation Strategies for Guaranteed Display Advertising: Modeling, Distributed Solving, and Adaptive Pacing

Preface

Brand advertising is a core component of Alibaba’s e‑commerce advertising ecosystem. It is used by most brand advertisers to build product image, strengthen user perception, and increase market share. The Alibaba display advertising platform must provide fast, efficient online decision mechanisms for a large variety of media resources both inside and outside the Taobao ecosystem. This article introduces the business challenges, thoughts, and solutions encountered in the online placement strategy for off‑site brand contract ads.

Background

Brand contract ads follow a Guaranteed Delivery (GD) model, where the platform must deliver a pre‑agreed number of impressions to a targeted audience within a specified time window. While performance ads focus on short‑term metrics such as clicks and conversions, brand ads are billed by exposure, yet advertisers increasingly demand measurable effectiveness. Consequently, the optimization of online decision algorithms for brand contract ads has two goals:

Guarantee volume : fulfill the contract’s exposure quota and maximize current platform revenue while avoiding penalties for under‑delivery.

Improve efficiency : on top of meeting the quota, maximize the marketing value for advertisers.

Problem Definition

The task can be modeled as a bipartite matching problem between supply (traffic nodes) and demand (contract orders). Two mainstream allocation frameworks exist:

Bid‑based : near‑real‑time heuristic adjustments and online ranking/filtering without offline model solving. Classic example: KDD'11 Real‑Time Bidding Algorithms for Performance‑Based Display Ad Allocation.

Guarantee‑based : offline allocation model training + online real‑time ranking (+ near‑real‑time pacing). Classic example: KDD'12 SHALE: An Efficient Algorithm for Allocation of Guaranteed Display Advertising.

Even when supply is abundant, a bid‑based framework can be used to boost performance, but for off‑site brand contract ads we adopt the guarantee‑based framework for two reasons:

Decoupling of volume‑guarantee dual variables and pacing thresholds simplifies management, especially during high‑pressure promotion periods.

Long‑tail orders with tiny quotas benefit from offline models that leverage extensive logs for stable allocation.

Algorithm Modeling

Basic Offline Model

We built a distributed training platform supporting up to 1 billion supply nodes based on the SHALE algorithm. The objective incorporates both volume guarantees and delivery effectiveness (e.g., CTR) to achieve a unified allocation that satisfies contracts while improving performance. Reference: ICDM'19 "Large‑scale personalized delivery for guaranteed display advertising with real‑time pacing".

The model variables include supply amount, order priority, contract quota, initial uniform allocation ratio, allocation probability, estimated effect (e.g., CTR), shortage penalty hyper‑parameter, and effect‑gain hyper‑parameter. Analysis shows that without an explicit over‑allocation constraint, the model may allocate more traffic than the contract quota, which yields no additional revenue in practice.

Anti‑Over‑Allocation Model

To address the over‑allocation issue, we modify the objective and constraints, introducing an explicit over‑allocation constraint. The objective consists of a regularization term, total release amount, and effect‑gain term. Using KKT conditions, the allocation probability can be expressed as a function of dual variables α and β (both ≥ 0).

Distributed Offline Solving

The dual parameters are solved via coordinate descent, alternating between fixing α to solve β and fixing β to solve α.

Fix α, solve β : Because each request retrieves a limited number of ads, the constraint Σ (allocation probability) = 1 allows direct computation of β.

Fix β, solve α : With millions of supply nodes per order, the constraint Σ (allocation amount) = quota is hard to solve directly; we approximate α using gradient descent within a distributed framework for acceleration.

Online Real‑Time Allocation

During online serving, the dual parameters retrieved for each candidate ad allow solving the equation Σ x = 1 to obtain β and the allocation probability x. Ads are then ordered by roulette‑wheel or inverted‑index ranking for display.

Adaptive Pacing

Traditional pacing modules use reinforcement learning or PID controllers to maintain a threshold per order. If the estimated effect score of a request falls below the threshold, the ad is not served, preserving budget for higher‑value traffic. Our framework adopts a probability‑based threshold: when competition is high, β > 0 and the allocation probability is reduced; when competition is low, β = 0 and the probability increases, thereby enhancing volume guarantee under traffic fluctuations.

Experimental Results

We compare our method (AUAF) with SHALE (KDD'12), RAP (KDD'20), and ALI (ICDM'19). Metrics include total allocation, fulfillment rate, over‑allocation rate, clicks after removing over‑allocation, and average CTR. AUAF matches SHALE in fulfillment while achieving the highest average CTR.

Conclusion

By extending the SHALE guaranteed‑delivery algorithm with effect‑based objectives and explicit over‑allocation constraints, we significantly improve the efficiency of contract‑guaranteed advertising. Online bucket tests demonstrate that our algorithm enhances brand marketing outcomes while preserving volume guarantees. Detailed methodology is available in our WSDM'22 paper "An Adaptive Unified Allocation Framework for Guaranteed Display Advertising".