Planning Online Advertising Using Gini Indices

We study an online display advertising planning problem in which advertisers’ demands for ad exposures (impressions) of various types compete for slices of shared resources, and advertisers prefer to receive impressions that are evenly spread across the audience segments they target. We use the Gini coefficient measure and formulate an optimization problem that maximizes the spreading of impressions across targeted audience segments, while limiting demand shortfalls. First, we show how Gini-based metrics can be used to measure spreading that publishers of online advertising care about and how Lorenz curves can be used to visualize Gini-based spread so that managers can effectively monitor the performance of a publisher’s ad delivery system. Second, we adapt an existing ad planning model to measure Gini-based spread across audience segments and compare and contrast our model to this baseline with respect to key properties and the structure of the solutions they produce. Third, we introduce a novel optimization-based decomposition scheme that efficiently solves our instances of the Gini-based problem up to 60 times faster than the commercial solver CPLEX directly solves a basic formulation. Finally, we present a number of model and algorithmic extensions, including (1) an online algorithm that mirrors the structure of our decomposition method to serve well-spread ads in real time, (2) a model extension that allows an aggregator buying impressions in an external market to allocate them to advertisers in a well-spread manner, and (3) a multiperiod model and decomposition method that spreads impressions across both audience segments and time.