Minimizing Regret in Social Media Advertisement^*

Social media advertisement has emerged as an effective approach to promoting commercial house brands. Hence, many of them have started using this medium to maximize the influence among the users and create a customer base. In recent times, several companies have emerged as influence providers, providing a certain number of views based on the budget provided by a commercial house. In this process, the influence provider tries to exploit the information diffusion phenomenon of a social network. In this problem, the challenge is how to allocate the seed nodes among the advertisers so that the regret of the allocation is minimized. The input to the problem is a set of advertisers with their respective influence, demand, and budget, a social network along with the selection cost of the users, and the goal here is to allocate the seed nodes among the advertisers that minimize the regret. In this context, we introduce a noble regret model for social media advertisement. Two efficient heuristic solution approaches have been proposed. Both methodologies have been analyzed to understand their time and space requirements. The proposed solution approaches have been implemented with real-world social network datasets, and a number of experiments have been conducted. From the experiments, we have observed that the proposed solution approaches lead to the allocation of seed nodes, resulting in much less regret than the baseline methods.