Fairness-Aware Algorithms for Seed Allocation in Social Advertising

Abstract

As a crucial and widely researched application in social networks, social advertising refers to selecting seed users for several advertisers to propagate their advertisements in the network via a information cascade effect. Prior studies on this topic have presented approximation algorithms merely for maximizing the expected revenue. However, regarding to the fairness issue, no existing works have provided effective solution. Such a issue would cause polarized revenues among different advertisers and the draining of them. In this paper, we investigate the fairness issue in social advertising. That is, how the social network platform owner distributes seeds users fairly to different advertisers. We define the fairness metric according to the maximin share, a concept about fair distribution in computation economics, and develop a novel approximation algorithm. Our approach achieves an approximation factor of $\frac{(1=1/e)^2}{3}\frac{1}{h^2}$ , where h is the number of different advertisers. Our result recovers the best-known proposed $\frac{(1-1/e)^2}{2}$ . -approximation ratio when h=1 and extends settings to a more general case. The evaluation on real datasets indicates that our solution is effective and outperforms the existing algorithms in terms of fairness.