document: Real-time bidding algorithms for performance-based display ad allocation 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 adjusts 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 .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O