Minimizing the regret of an influence provider

• Main Authors: ZHANG, Yipeng, LI, Yuchen, BAO, Zhifeng, ZHENG, Baihua
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2021
• Subjects: Outdoor advertising; Regret minimization; Influence provider; Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/6541; https://ink.library.smu.edu.sg/context/sis_research/article/7544/viewcontent/Sigmod_21.pdf
• Institution: Singapore Management University

Influence maximization has been studied extensively from the perspective of the influencer. However, the influencer typically purchases influence from a provider, for example in the form of purchased advertising. In this paper, we study the problem from the perspective of the influence provider. Specifically, we focus on influence providers who sell Out-of-Home (OOH) advertising on billboards. Given a set of requests from influencers, how should an influence provider allocate resources to minimize regret, whether due to forgone revenue from influencers whose needs were not met or due to over-provisioning of resources to meet the needs of influencers? We formalize this as the Minimizing Regret for the OOH Advertising Market problem (MROAM). We show that MROAM is both NP-hard and NP-hard to approximate within any constant factor. The regret function is neither monotone nor submodular, which renders any straightforward greedy approach ineffective. Therefore, we propose a randomized local search framework with two neighborhood search strategies, and prove that one of them ensures an approximation factor to a dual problem of MROAM. Experiments on real-world user movement and billboard datasets in New York City and Singapore show that on average our methods outperform the baselines in effectiveness by five times.