Optimal Multi-stage Configuration Allocation with Applications to Video Advertising

In modern applications of real-time resource allocation, for example allocating ad opportunities created by users to relevant advertisers during video streaming, a prevalent scenario is when an arriving user can be served under different "configurations''. For example, in video advertising, a configuration can be an arrangement of video-ads of various lengths and formats for a subset of advertisers, showing up at different time-stamps of the video. Each selected configuration assigns a certain number of impressions to each advertiser. Depending on their long-term contracts, each advertiser is willing to pay for a certain number of impressions during the decision making horizon at a per-impression price depending on the assigned configuration. While this application is real-time, there is an inherent allowance for latency in showing ads to users, as several of these ads show up in the middle (or at the end) of the video. This provides an opportunity for ad allocator to batch the users and to make more profitable allocation decisions. While designing algorithms for the fully online variant of this setting has been studied in the literature [Devanur et al., 2016], the multi-stage variant where the allocation decisions are made batch-by-batch is not studied.Motivated by the above application, we study designing optimal competitive multi-stage configuration allocation algorithms (with preemption) in an adversarial setting, where users arrive in batches in a stage-wise fashion. The allocator then decides on an irrevocable configuration for each of the users in an arriving batch at each stage so as to maximize the total revenue. We propose a novel convex-programming based multi-stage configuration allocation algorithm that is 1-(1-1/K)^K competitive, where K is the number of stages. We further show an intimate connection between the convex programs used in each stage and a recursive functional equation (with a sequence of polynomials of decreasing degrees as its solution). Using this connection, we develop a recursive primal-dual analysis for our algorithm and extend the previous analysis framework of multi-stage fractional matching [Feng and Niazadeh, 2021] to this more general setting. Interestingly, we show there is an intimate connection between convex Lagrangian dual of each stage of our algorithm and how the primal-dual analysis needs to be set up, which might be of independent interest