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, that is, 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 one 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, whereas 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.