Sustaining a Good Impression : Mechanisms for Selling 'Partitioned' Impressions at Ad-Exchanges

In the mobile advertising ecosystem, the role of ad-exchanges to match advertisers and publishers has grown significantly over the past few years. At a mobile ad-exchange, impressions (i.e., opportunities to display ads) are sold to advertisers in real time through an auction mechanism. The traditional mechanism selects a single advertiser whose ad is displayed over the entire duration of an impression, i.e., throughout the user's visit. We argue that such a mechanism leads to an allocative inefficiency, as displaying only the winning ad throughout the lifetime of an impression precludes the exchange from exploiting the opportunity to obtain additional revenue from advertisers whose willingness-to-pay becomes higher during the lifetime of that impression. Our goal in this paper is to address this efficiency loss by offering mechanisms in which multiple ads can be displayed sequentially over the lifetime of the impression. We consider two plausible settings – one, where each auction is individually rational for the advertisers and the other, where advertisers are better off relative to the traditional mechanism over the long run – and derive an optimal (i.e., revenue-maximizing for the ad-exchange) mechanism for each setting. To efficiently compute the payment rule, the optimal mechanism for the former setting uses randomized payments. Under this mechanism, while the ad-exchange always benefits relative to the traditional mechanism, the advertisers could either gain or lose – we demonstrate both these possibilities. The optimal mechanism for the latter setting is a "mutually-beneficial" mechanism in that it guarantees a win-win for both the parties relative to the traditional mechanism, over the long run. Happily, for both the mechanisms, the allocation of ads and the payments from the advertisers are efficiently computable, thereby making them amenable to real-time bidding