Deals or No Deals: Contract Design for Online Advertising

Billions of dollars worth of display advertising are sold via contracts and deals. This paper presents a formal study of preferred deals, a new generation of contracts for selling online advertisement, that generalize the traditional reservation contracts; these contracts are suitable for advertisers with advanced targeting capabilities. We propose a constant-factor approximation algorithm for maximizing the revenue that can be obtained from these deals. We show, both theoretically and via data analysis, that deals, with appropriately chosen minimum-purchase guarantees, can yield significantly higher revenue than auctions. We evaluate our algorithm using data from Google's ad exchange platform. Our algorithm obtains about 90% of the optimal revenue where the second-price auction, even with personalized reserve, obtains at most 52% of the benchmark.

• Algorithms and Theory