Optimization Algorithms for Guaranteed Delivery Advertising in Double‑11 Interactive Campaign

The document introduces guaranteed‑delivery advertising contracts widely used in e‑commerce marketing, which provide advertisers with a contracted number of audience impressions. To meet contract volume requirements, a delivery allocation algorithm must assign and display ads for each request.

In the traditional APP splash‑screen guaranteed‑delivery scenario, the team previously designed the XSHALE and AUAF algorithms, achieving significant business results. For the Double‑11 Interactive City, a specialized allocation problem was formalized, leading to the development of a primal‑dual algorithm for guaranteed‑downline orders and a flow‑balancing re‑ranking algorithm for guaranteed‑non‑downline orders.

Background

During Double‑11, interactive games attract massive user traffic, which is sold to advertisers as multi‑level guaranteed‑delivery packages. The 2021 game featured "Earn Meow‑Candy, Capture Land, Grab Red Packets" and offered various commercial slots. These slots must be allocated according to contract commitments while maximizing advertisers' delivery effectiveness.

Technical Solution and Implementation

Motivation for Scheme Selection

Two mainstream traffic‑control frameworks exist: (1) offline‑trained allocation models combined with near‑line pacing, and (2) near‑line adjustment of dual parameters for real‑time bidding.

Based on extensive experience with APP splash‑screen contracts, the team adopted the offline‑model + near‑line pacing solution for the interactive scenario because:

APP splash orders have high sell‑through rates and many scarce orders; disabling pacing during high‑pressure periods preserves volume.

Long‑tail orders benefit from stable offline allocation using long‑term logs.

However, this approach has drawbacks: higher system complexity and weaker efficiency gains.

Given the abundant traffic in the promotional interactive scenario, the team chose the near‑line dual‑parameter adjustment method, which yields better delivery performance.

Optimized Algorithm for Guaranteed‑Downline Contracts

For precise guaranteed‑downline orders, after a pre‑locking step the shortage risk is low, allowing pacing‑based optimization to maximize post‑chain effects. The team applied a Primal‑Dual algorithm using a brandScore metric to enhance delivery.

Derivation of the Objective Function

The optimization goal is to maximize the estimated brand‑score effect under the guarantee constraint. The dual problem is formulated, and the online price calculation selects the ad with the highest shadow‑price premium, discarding traffic if no ad meets the threshold. The reserve price is set to zero.

Near‑Line Control of Dual Variables

Traditional near‑line dual control adjusts the dual variable α based on over‑delivery and shortage feedback. In the "Meow‑Candy" interactive city, traffic trends are volatile; the team collaborated with product and business teams to predict traffic patterns from game rules, greatly smoothing brand‑contract release.

Online Allocation Algorithm for Guaranteed‑Non‑Downline Contracts

Non‑downline contracts require real‑time, high‑precision allocation because orders are fully controlled by the algorithm without fallback mechanisms. Orders are tiered by price, with higher‑priced packages receiving more exposure and higher overflow rates. The algorithm optimizes under a "guarantee and balance" constraint, deriving a dual‑based allocation formula and adjusting dual variables in near‑line based on progress and target overflow ratios.

Derivation of the Consistency Dual Allocation Formula

The objective includes a quadratic regularization term to ensure strong convexity, uniqueness of the optimal solution, and robust, balanced traffic distribution. Using Lagrange multipliers and KKT conditions, the model stores dual variables instead of explicit probabilities, yielding a compact solution.

Near‑Line Strategy & Release‑Rate Computation

Minute‑level near‑line scheduling employs linear interpolation of real‑time settlement feedback to adjust each order’s dual variable α. The algorithm ensures similar overflow rates across orders while respecting tiered overflow hierarchies. It estimates total daily release, re‑weights by ideal overflow rates, and computes the remaining release volume to determine the target release speed for the next time slice.

Summary & Planning

For Double‑11, the team designed two specialized algorithms: a brandScore‑driven primal‑dual allocation for guaranteed‑downline contracts and a guarantee‑and‑balance optimization for guaranteed‑non‑downline contracts. Both achieved the expected volume and improved post‑chain metrics such as interaction depth, repeat store visits, and average browsing time.

Experiments on downline contracts showed improvements in interaction depth, repeat visits, and average browsing time compared with a baseline without control.

Experiments on non‑downline contracts reduced progress imbalance and significantly boosted the same metrics.

Future work will focus on:

Deepening the value extraction of precise contract audience segments and developing serialized delivery algorithms to promote audience flow.

Building customizable delivery interfaces for complex non‑downline contracts, automatically handling pricing and strategy configuration based on difficulty and complexity.

References

Fang Z, Li Y, Liu C, et al. Large‑Scale Personalized Delivery for Guaranteed Display Advertising with Real‑Time Pacing[C]//2019 IEEE International Conference on Data Mining (ICDM). IEEE, 2019: 190‑199.

An Adaptive Unified Allocation Framework for Guaranteed Display Advertising, accepted by WSDM2022.

Chen Y, Berkhin P, Anderson B, et al. Real‑time bidding algorithms for performance‑based display ad allocation[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011: 1307‑1315.