Asymptotically Optimal Safety Stuffing for Inventory Allocation in Display Advertising

Friday, December 10, 2010 - 1:25pm - 2:25pm
Vincent 16

Ana Radovanovic (Google)

A widely used model in online advertising industry is the one in which advertisers pre-purchase a reservation package of online inventory on content sites owned by the publishers (e.g., CNN, amazon, etc.). This package consists of specified inventory bundles of various types that are priced differently and differ in various properties including their expected effectiveness (e.g., Click Through Rate). When online advertisers arrive to a publisher, they have a daily budget, desirable duration of the advertising campaign and a performance goal, which is expressed through some target 'effectiveness' of the purchased package. We design a simple and easy to implement online inventory allocation policy and rigorously prove its asymptotically optimal long run performance.

The underlying dynamics of the described application has some similarities with bandwidth sharing in communication networks. However, there are intrinsic characteristics that make the problem of impression allocations in online advertising novel from the modeling and analysis perspective. The key difference is a random budget, which translates into random inventory demand. The other important property is that online advertisers do not ask for specific inventory type, but expect some overall effectiveness from the package of purchased inventory. In view of the existing capacity constraints, we propose a simple online inventory allocation rule, which uses 'careful' sizing of safety stocks to deal with the finite inventory capacities. We rigorously prove the long run revenue optimality of our policy in the regime where demand and inventory capacities grow proportionally.

Joint work with Assaf Zeevi (Columbia University).

MSC Code: