Optimizing ad allocation in mobile advertising

As Internet advertisements (also called "ads") revenue growth is being driven further than ever before, one challenge facing publishers, such as Google and Amazon, is to quickly select and place a group of ads in an ad space for each online user with the objective of maximizing the expected revenue. This is especially challenging in the context of mobile advertising due to the smaller screen size of mobile devices and longer user session. We notice that most existing models do not allow the publisher to place the same ad in multiple positions. However, it has been reported that people must see an advertisement at least several times before they will acquire enough interest to consider buying the product or service advertised. To capture this repetition effect we largely generalize the previous model by allowing the publisher to repeat the same ads multiple times. We also notice that many existing models assume that a user will leave the ad session permanently after clicking an ad. Our framework allows a more realistic but complicated user behavior by allowing a user to return to the previous ad session. Our model is able to capture many factors that may affect the click probability of an ad such as the intrinsic quality of the ad, the position of the ad, and all ads that have been previously displayed. We also extend our work to adaptive setting where publishers can dynamically adjust their ad display according to user's feedback. We develop effective algorithms with guarantees of finding either optimal or approximate solutions.