We study a novel resource-allocation problem faced by Alibaba Group. In this problem, mobile “push messages” must be sent over the course of a day to hundreds of millions of users. Each message can be sent to any number of users, and yields a reward when it generates a clickthrough, subject to a budget constraint on the total reward over all users for the message. This budget represents the maximum amount that an advertiser is willing to pay for clickthroughs for the message on a given day. Given users’ diverse preferences, the problem aims to deliver the “right messages” to the “right users” to maximize ad revenues without overwhelming each user with too many messages. Due to the large size of the real application, we analyze algorithms for the above problem in an asymptotic regime. We consider a novel scaling of the problem “size,” called big-data scaling. In this scaling, as the problem size grows, the number of users, as well as their diversity, grow. The scaling captures the fact that individual user information remains highly granular and distinctive even as the size of the user base increases. We prove that solving the problem as a static assignment problem results in a regret of O( √ t), where t is the parameter scaling the problem. Furthermore, adding a single recourse opportunity, by sending push messages in two cycles over the course of a day and making use of information observed in the first cycle to adapt decisions in the second cycle, can reduce the regret to O(t 1/4 log t). Finally, the difference in regret between the static and dynamic strategy can be Ω(√ t). Numerical experiments on three real data sets, each containing several hundred million users, show that the latter strategy improves the regret of the former by at least 10%-50%.
This is joint work with Xinshang Wang, Shenghuo Zhu, and Qiong Zhang.