Abstract
Search ads have evolved in recent years from simple text formats to rich ads that allow deep site
links, ratings, images and videos. In this paper, we
consider a model where several slots are available
on the search results page, as in the classic generalized second-price auction (GSP), but now a bidder
can be allocated several consecutive slots, which
are interpreted as a rich ad. As in the GSP, each bidder submits a bid-per-click, but the click-through
rate (CTR) function is generalized from a simple
CTR for each slot to a general CTR function over
sets of consecutive slots. We study allocation and
pricing in this model under subadditive and fractionally subadditive CTRs. We design and analyze
a constant-factor approximation algorithm for the
efficient allocation problem under fractionally subadditive CTRs, and a log-approximation algorithm
for the subadditive case. Building on these results,
we show that approximate competitive equilibrium
prices exist and can be computed for subadditive
and fractionally subadditive CTRs, with the same
guarantees as for allocation