Source-linked AI summary
Online Stochastic Packing Applied to Display Ad Allocation
Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, Cliff Stein
TL;DR
The paper asks how online resource allocation can achieve near-optimal value when arrivals are stochastic rather than adversarial. It proposes a training-based primal-dual pricing algorithm for packing linear programs and evaluates it on display-ad data, finding near-optimal theoretical performance and an efficiency–fairness trade-off in practice.
Problem
Online packing must allocate sequentially arriving demands under capacity constraints, while adversarial arrivals make strong approximation guarantees impossible.
Method
The algorithm solves an LP on the first ε fraction of arrivals, uses its dual variables as posted resource prices, and allocates later agents by maximum utility.
Results
The algorithm is (1−O(ε))-competitive with high probability under bounded-option assumptions, while real display-ad experiments validate training-based primal-dual methods and reveal an efficiency–fairness trade-off.
Takeaways & Limitations
The framework provides near-optimal stochastic allocation guarantees across several packing applications and supports practical display-ad allocation analysis involving both efficiency and fairness.
Takeaways & Limitations
The theoretical algorithm requires advance knowledge of the number of arriving agents, and equal-sharing fairness can be arbitrarily inefficient in the worst case.
Abstract
from arXiv · showhide
Inspired by online ad allocation, we study online stochastic packing linear programs from theoretical and practical standpoints. We first present a near-optimal online algorithm for a general class of packing linear programs which model various online resource allocation problems including online variants of routing, ad allocations, generalized assignment, and combinatorial auctions. As our main theoretical result, we prove that a simple primal-dual training-based algorithm achieves a (1 - o(1))-approximation guarantee in the random order stochastic model. This is a significant improvement over logarithmic or constant-factor approximations for the adversarial variants of the same problems (e.g. factor 1 - 1/e for online ad allocation, and \log m for online routing). We then focus on the online display ad allocation problem and study the efficiency and fairness of various training-based and online allocation algorithms on data sets collected from real-life display ad allocation system. Our experimental evaluation confirms the effectiveness of training-based primal-dual algorithms on real data sets, and also indicate an intrinsic trade-off between fairness and efficiency.
1 Introduction
The paper studies online stochastic packing problems, where resource-constrained demands arrive sequentially and must be allocated for maximum total value. It develops a training-based primal-dual algorithm with near-optimal guarantees in stochastic settings and applies the framework to display advertising and related allocation problems.
- Problem setting: Online packing assigns arriving agents one option each while respecting resource capacities and maximizing total value.The framework models routing, combinatorial auctions, display advertising, and other dynamic allocation problems.
- Motivation: Adversarial arrivals can make every online algorithm achieve less than 1/10 of the offline optimum.The example uses one unit-capacity resource and two agents whose values depend on the first allocation decision.
- Main theoretical result: In the random-order stochastic model, the training-based algorithm achieves a 1−ε approximation under mild assumptions, also implying the same result in the i.i.d. model.The model randomizes arrival order without requiring additional prior information about demand types.
- Algorithm: The learned dual variables become posted resource prices, and each later agent selects the option maximizing value minus required resource payments.The algorithm estimates prices by solving an LP on the first ε fraction of arrivals.
- Main theoretical result: (1−O(ε))-competitive performance makes the Training-Based Primal-Dual algorithm a PTAS with high probability.The guarantee applies when individual options do not consume too much resource capacity or contribute too much total value.
- Applications: The framework extends to routing, combinatorial auctions, display advertising, and AdWords, improving known online results for these applications.The display-ad setting is also evaluated empirically using real traffic and allocation data.
2 A Training-based PTAS
The training-based PTAS learns dual prices from an initial sample, then uses those prices to allocate subsequent agents by maximum nonnegative gain. Concentration arguments show that, under bounded-option assumptions, this produces a feasible solution with value (1−O(ε))OPT with high probability.
- Algorithm: The algorithm uses the first εn agents as a training sample and solves a reduced Dual-LP to obtain resource prices.For analysis, the sample agents are not selected; implementations may allocate them separately.
- Algorithm: Each subsequent agent receives the option with maximum nonnegative gain, where gain equals value minus the prices of consumed resources.Agents with no nonnegative-gain option are not selected.
- Assumptions and scope: The framework assumes no individual option consumes too much resource or contributes too large a share of total value, and tie handling may require random perturbations.The paper also establishes that advance knowledge of the number of arriving agents is unavoidable for sub-logarithmic approximation.
- Proof strategy: The analysis compares sample resource usage and value with their expected ε fractions of the full selected set.For a fixed price vector, the sample quantities have expectations εC(j) and εW.
- Proof strategy: The sample is unlikely to be bad: each resource-balance failure has probability at most 1/[m·(nq)^(m+1)], while the value failure has probability at most 1/(nq)^(m+1).These bounds are obtained using concentration inequalities for random samples.
- Guarantee: If the sample is not bad, the selected options have value (1−O(ε))OPT.The proof constructs a feasible dual upper bound and shows the algorithm’s value is close to it.
- Guarantee: A small capacity violation can be repaired by reducing all capacities by a factor of 1+O(ε), sacrificing at most the same factor in optimum value.The number of possible learned price vectors is bounded, enabling a high-probability guarantee simultaneously over price outcomes.
3 Display Ad Allocation and Fairness
The paper defines display-ad fairness relative to advertiser competition, using an ideal offline allocation and distance-based comparison. It develops fair-allocation procedures and shows that fairness can conflict with efficiency.
- Fairness definition: Fairness is evaluated relative to advertisers competing for the same impressions, rather than by additive efficiency alone.The ideal fair allocation is defined algorithmically from the instance and competing advertisers.
- Fairness definition: The fairness metric compares an allocation with an ideal fair allocation after scaling it to the ideal allocation’s efficiency.This normalization evaluates relative advertiser efficiency rather than absolute efficiency.
- Sharing policies: Equal sharing assigns each impression equally among interested advertisers, while proportional sharing divides it according to advertiser weights.Stable-matching sharing instead assigns each impression to the highest-priority interested advertiser under a weight-based order.
- Fair allocation algorithm: The Fair Allocation algorithm runs in polynomial time and computes the most efficient fair allocation under supported sharing policies.Theorem 11 assumes that adding an interested advertiser does not increase another advertiser’s share.
- Efficiency trade-offs: Stable-matching sharing achieves at least 1/2 of maximum efficiency, whereas equal-sharing and proportional-sharing efficiency can be arbitrarily far from optimum.The stable-matching guarantee applies to the allocation produced under that sharing rule.
- Efficiency trade-offs: In practice, equal-sharing allocations can have efficiency on the same order of magnitude as the optimum despite their worst-case inefficiency.The paper states that this practical behavior is evaluated experimentally.
4 Online Heuristic Algorithms
The paper describes online display-ad heuristics through primal-dual updates, advertiser-specific dual variables, and training-based or hybrid variants. Its experiments compare these methods across six publishers using normalized efficiency.
- Primal-dual framework: Each arriving impression is assigned to the advertiser maximizing weight minus dual price, with low-value prior assignments removed when capacity is reached.The dual solution records the resulting surplus, while update rules determine the algorithm variant.
- Online algorithms: GREEDY sets each advertiser’s dual variable to the lightest impression among its n(j) heaviest assignments.This equals assigning each impression by maximum marginal increase in matching weight.
- Online algorithms: PD AVG uses the average weight of an advertiser’s n(j) most valuable assigned impressions, while PD EXP uses an exponentially weighted average.Both update advertiser-specific dual variables from currently assigned impressions.
- Comparative guarantees: The previous worst-case competitive ratios are 1/2 for GREEDY, 1/2 for PD AVG, and 1−1/e for PD EXP.These algorithms are compared with a training-based method in the paper’s stochastic setting.
- Training-based methods: The training-based algorithm learns fixed dual variables from sample data and applies them to the remaining impressions.HYBRID gradually combines these fixed variables with PD AVG’s changing variables.
- Experimental comparison: Table 2 normalizes every algorithm’s efficiency so that OPT = LP WEIGHT equals 100 across publishers and in the average.The experiments use six publishers with varying advertiser and impression counts.
5 Experimental Evaluation
Experiments on six publishers compare pure online, training-based, and offline allocation algorithms using efficiency and normalized fairness. Training-based methods generally improve efficiency, while fairness and efficiency can diverge across publisher settings.
- Fairness: GREEDY is the least fair algorithm, whereas the remaining algorithms, including LP WEIGHT, have roughly similar normalized fairness across publishers.Fairness scores are normalized per publisher so the least fair algorithm scores 100 and FAIR scores 0.
- Publisher-specific results: Publisher B is undersold: the top advertisers’ maximum possible efficiency is nearly the same as the efficiency achieved by all algorithms.The figures compare overall efficiency and fairness on the left with advertiser-level efficiency on the right, ordering advertisers by maximum possible efficiency.
- Publisher-specific results: Publisher D is highly competitive: top advertisers’ maximum possible efficiency greatly exceeds every algorithm’s achieved efficiency, including LP WEIGHT.In this setting, algorithm choice strongly affects efficiency; PD EXP outperforms the non-optimal algorithms.
- Publisher-specific results: For in-between publishers C and E, training-based algorithms clearly outperform pure online algorithms because their efficiency gap from top advertisers is not extreme.Publisher C is represented in Figure 3, while publisher E is not shown.
- Overall conclusions: PD AVG generally achieves better efficiency and fairness than GREEDY, while also producing the best fair solution overall.Both algorithms are 1/2-competitive in the worst case.
- Overall conclusions: Training-based algorithms clearly outperform pure online algorithms in efficiency, with DualBase improving 12% over PD AVG and 5% over PD EXP on average.HYBRID adds a 2% average improvement over DualBase, reaching up to 10% in one publisher.
6 Concluding Remarks
The paper establishes a near-optimal training-based guarantee for stochastic packing and validates training-based allocation methods on real display-ad data. It also identifies robustness, fairness, and broader stochastic-model extensions as open directions.
- A (1 −ε) approximation is achieved by the training-based algorithm in the random-order stochastic model under mild assumptions.
- On real display-ad data, the training-based algorithm outperforms PD AVG and PD EXP by a large factor.
- Combining pure online and training-based methods in a hybrid algorithm improves efficiency further.
- The paper asks whether one algorithm can perform well in both worst-case and stochastic settings, including when traffic differs from learned predictions.The cited examples include sudden website traffic spikes caused by breaking news or links from extremely high-traffic sources.
- Further open problems include achieving approximate efficiency and fairness simultaneously and extending the stochastic algorithm to Markov-based models.