Targeting algorithms for online social advertising markets

Advertisers in online social networks (OSNs) like Facebook and LinkedIn have some preferred set of users they wish to reach by showing their ads. OSNs offer fine-grained sets of user characteristics - including their career, wealth, education information, etc - that advertisers can specify for targeting their audience, and each of these characteristics requires different amounts of money for targeting. The problem we address is what we call the targeting problem, that is, given a set S_T characteristics of interest to an advertiser (that is, the advertiser wishes to reach users who have these characteristics, i.e. U(S_T)) and a budget b₀ he wishes to spend, how to split the budget among the user characteristics so that they can reach the most number of users in U(S_T)? • OSN-perspective. OSNs have complete knowledge of each user and their characteristics. In this case, we propose a polynomial time algorithm for the targeting problem and prove that it is an 1-1/e approximation to the targeting that gets the optimal number of users. We define the marginal increment and iteratively maximize it. • Advertiser-perspective. No single advertiser has the mapping of users to their characteristics or the distribution of users over the characteristics, and hence they cannot use the algorithm from above. We show through empirical data analysis that the strategy of targeting subsets U(S) U(S_T) is their only feasible approach (in other words, targeting U(S) U(S_T) will be arbitrarily worse than the direct solution). For evaluation, we crawl and analyze more than one million suggested bids from Facebook and LinkedIn. Further, we propose a fast greedy algorithm for the targeting problem based on targeting subsets, that in empirical analysis, increases the number of reached preferred users by nearly 40% over directly targeting the characteristics of interest, and for a moderate budget, it increases the number of reached preferred users by nearly 20%.