Wednesday, 4:00–5:00 PM
Chairs: S. Muthu Muthukrishnan

Expressive Auctions for Externalities in Online Advertising

Arpita Ghosh, Amin Sayedi

When online ads are shown together, they compete for user attention and conversions, imposing negative externalities on each other. While the competition for user attention in sponsored search can be captured via models of clickthrough rates, the post-click {\em competition for conversions} cannot: since the value-per-click of an advertiser is proportional to the conversion probability conditional on a click, which depends on the other ads displayed, the private value of an advertiser is no longer one-dimensional, and the GSP mechanism is not adequately expressive. We study the design of expressive GSP-like mechanisms for the simplest form that an advertiser’s private value can have in the presence of such externalities—an advertiser’s value depends on {\em exclusivity}, \ ie, whether her ad is shown exclusively, or along with other ads. Our auctions take as input two-dimensional (per-click) bids for exclusive and nonexclusive display, and have two types of outcomes: either a single ad is displayed exclusively, or multiple ads are simultaneously shown. We design two expressive auctions that are both extensions of GSP—the first auction, \GGSP, is designed with the property that the allocation and pricing are identical to GSP when multiple ads are shown; the second auction, \NP, is designed to be a next price auction. We show that both auctions have high efficiency and revenue in all reasonable equilibria; further, the \NP\ auction is guaranteed to always have an equilibrium with revenue at least as much as the current GSP mechanism. However, we find that unlike with one-dimensional valuations, the GSP-like auctions for these richer valuations do not always preserve efficiency and revenue with respect to the VCG mechanism.

AdHeat: An Influence-based Diffusion Model for Propagating Hints to Match Ads

Hongji Bao, Ed Chang

In this paper, we present AdHeat, a social ads model considering {\em user influence} in addition to {\em relevance} for matching ads. Traditionally, ads placement employs the {\em relevance} model. Such a model matches ads with Web page content, user interests, or both. We have observed, however, on social networks that the relevance model suffers from two shortcomings. First, influential users (users who contribute opinions) seldom click ads that are highly relevant to their expertise. Second, because influential users’ contents and activities are attractive to other users, {\em hint words} summarizing their expertise and activities may be widely preferred. Therefore, we propose AdHeat, which diffuses hint words of influential users to others and then matches ads for each user with aggregated hints. We performed experiments on a large online Q\&A community with half a million users. The experimental results show that AdHeat outperforms the relevance model on CTR (click through rate) by significant margins.

Using Landing Pages for Sponsored Search Ad Selection

Yejin Choi, Marcus Fontoura, Evgeniy Gabrilovich, Vanja Josifovski, Bo Pang, Mauricio Mediano

We explore the use of the landing page content in sponsored search ad selection. Specifically, we compare the use of the ad’s intrinsic content to augmenting the ad with the whole, or parts, of the landing page. We explore two types of extractive summarization techniques to select useful regions from the landing pages: out-of-context and in-context methods. Out-of-context methods select salient regions from the landing page by analyzing the content alone, without taking into account the ad associated with the landing page. In-context methods use the ad context (including its title, creative, and bid phrases) to help identify regions of the landing page that should be used by the ad selection engine. In addition, we introduce a simple yet effective unsupervised algorithm to enrich the ad context to further improve the ad selection. Experimental evaluation confirms that the use of landing pages can significantly improve the quality of ad selection. We also find that our extractive summarization techniques reduce the size of landing pages substantially, while retaining or even improving the performance of ad retrieval over the method that utilize the entire landing page.


Back to full list of papers