Team for Research in
Ubiquitous Secure Technology

Citation
Panagiotis Papadimitriou, Hector Garcia-Molina. "Sponsored search auctions with conflict constraints". Proceedings of the fifth ACM international conference on Web search and data mining, 2012.

Abstract
In sponsored search auctions 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 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 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. top of pageAUTHORS

Electronic downloads

• http://dl.acm.org/citation.cfm?doid=2124295.2124332

• HTML

  Panagiotis Papadimitriou, Hector Garcia-Molina. <a
  href="http://www.truststc.org/pubs/897.html"
  >Sponsored search auctions with conflict
  constraints</a>, Proceedings of the fifth ACM
  international conference on Web search and data mining, 2012.

• Plain text

  Panagiotis Papadimitriou, Hector Garcia-Molina.
  "Sponsored search auctions with conflict
  constraints". Proceedings of the fifth ACM
  international conference on Web search and data mining, 2012.

• BibTeX

  @inproceedings{PapadimitriouGarciaMolina12_SponsoredSearchAuctionsWithConflictConstraints,
      author = {Panagiotis Papadimitriou and Hector Garcia-Molina},
      title = {Sponsored search auctions with conflict constraints},
      booktitle = {Proceedings of the fifth ACM international
                conference on Web search and data mining},
      year = {2012},
      abstract = {In sponsored search auctions 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 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
                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. top of
                pageAUTHORS},
      URL = {http://www.truststc.org/pubs/897.html}
  }
  

Posted by Mary Stewart on 4 Apr 2012.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.