Stanford InfoLab Publication Server

Sponsored Search Auctions with Conflict Constraints

Papadimitriou, Panagiotis and Garcia-Molina, Hector (2011) Sponsored Search Auctions with Conflict Constraints. Technical Report. Stanford InfoLab.




In sponsored search auctions (SSA) advertisers compete for ad slots in the search engine results page, by bidding on keywords of interest. To improve advertiser expressiveness, we augment the bidding process with \emph{conflict} constraints. With such constraints, advertisers can condition their bids on the non-appearance of certain undesired ads on the results page. We study the complexity of the \emph{allocation} problem in these augmented SSA and we introduce an algorithm that can efficiently allocate the ad slots to advertisers. We evaluate the algorithm run time in simulated conflict scenarios and we study the implications of the conflict constraints on search engine revenue. Our results show that the allocation problem can be solved within few tens of milliseconds and that the adoption of conflict constraints can potentially increase search engine revenue.

Item Type:Techreport (Technical Report)
Related URLs:Author Homepage
ID Code:1010
Deposited By:Panagiotis Papadimitriou
Deposited On:12 Aug 2011 10:26
Last Modified:20 Aug 2011 07:26

Download statistics

Repository Staff Only: item control page