CS Events

Online advertising is one of vital markets on the Internet. In an online social network (OSN), its owner charges advertisers when they show ads to their target users. Consequently, the price to shown an ad largely depends on its audience, i.e. the OSN users.

We crawl a large dataset of user attention prices from LinkedIn and Facebook. Through empirical study, we reveal the underlying characteristics of user prices of LinkedIn. Going beyond, we study how advertisers can use these prices strategically. We formulate the fractional cheap targeting problem and devise approximate algorithms.

We are also addressing the problem to compute an arbitrage-free pricing with revenue guarantee. So far, we show that any uniform pricing is arbitrage-free, and the optimal uniform pricing can be computed in polynomial time. We prove that the revenue generated by the optimal uniform pricing has logarithmic approximation to the optimal one. Based on these, we devise a polynomial algorithm to compute an arbitrage-free non-uniform pricing which generates no less revenue than the optimal uniform pricing.