2011 RealTimeBiddingAlgorithmsforPer

• (Chen et al., 2011) ⇒ Ye Chen, Pavel Berkhin, Bo Anderson, and Nikhil R. Devanur. (2011). “Real-time Bidding Algorithms for Performance-based Display Ad Allocation.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020604

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Real-time+Bidding+Algorithms+for+Performance-based+Display+Ad+Allocation
• http://dl.acm.org/citation.cfm?id=2020408.2020604&preflayout=flat#citedby

Quotes

Author Keywords

• Ad exchange; algorithms; combinatorial optimization; complexity of proof procedures; computations on discrete structures; experimentation; linear programming; performance; performance display; real-time bidding

Abstract

We describe a real-time bidding algorithm for performance-based display ad allocation. A central issue in performance display advertising is matching campaigns to ad impressions, which can be formulated as a constrained optimization problem that maximizes revenue subject to constraints such as budget limits and inventory availability. The current practice is to solve the optimization problem offline at a tractable level of impression granularity (e.g., the page level), and to serve ads online based on the precomputed static delivery scheme. Although this offline approach takes a global view to achieve optimality, it fails to scale to ad allocation at the individual impression level. Therefore, we propose a real-time bidding algorithm that enables fine-grained impression valuation (e.g., targeting users with real-time conversion data), and djusts value-based bids according to real-time constraint snapshots (e.g., budget consumption levels). Theoretically, we show that under a linear programming (LP) primal-dual formulation, the simple real-time bidding algorithm is indeed an online solver to the original primal problem by taking the optimal solution to the dual problem as input. In other words, the online algorithm guarantees the offline optimality given the same level of knowledge an offline optimization would have. Empirically, we develop and experiment with two real-time bid adjustment approaches to adapting to the non-stationary nature of the marketplace: one adjusts bids against real-time constraint satisfaction levels using control-theoretic methods, and the other adjusts bids also based on the statistically modeled historical bidding landscape. Finally, we show experimental results with real-world ad delivery data that support our theoretical conclusions.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 RealTimeBiddingAlgorithmsforPer	Ye Chen Pavel Berkhin Bo Anderson Nikhil R. Devanur			Real-time Bidding Algorithms for Performance-based Display Ad Allocation				10.1145/2020408.2020604		2011