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.