Bid Optimization in Broad-Match Ad auctions - Computer Science > Computer Science and Game TheoryReportar como inadecuado

Bid Optimization in Broad-Match Ad auctions - Computer Science > Computer Science and Game Theory - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Ad auctions in sponsored search support ``broad match- that allows anadvertiser to target a large number of queries while bidding only on a limitednumber. While giving more expressiveness to advertisers, this feature makes itchallenging to optimize bids to maximize their returns: choosing to bid on aquery as a broad match because it provides high profit results in one biddingfor related queries which may yield low or even negative profits.We abstract and study the complexity of the {\em bid optimization problem}which is to determine an advertiser-s bids on a subset of keywords possiblyusing broad match so that her profit is maximized. In the query language modelwhen the advertiser is allowed to bid on all queries as broad match, we presentan linear programming LP-based polynomial-time algorithm that gets theoptimal profit. In the model in which an advertiser can only bid on keywords,ie., a subset of keywords as an exact or broad match, we show that this problemis not approximable within any reasonable approximation factor unless P=NP. Todeal with this hardness result, we present a constant-factor approximation whenthe optimal profit significantly exceeds the cost. This algorithm is based onrounding a natural LP formulation of the problem. Finally, we study a budgetedvariant of the problem, and show that in the query language model, one can findtwo budget constrained ad campaigns in polynomial time that implement theoptimal bidding strategy. Our results are the first to address bid optimizationunder the broad match feature which is common in ad auctions.

Autor: Eyal Even-dar, Yishay Mansour, Vahab Mirrokni, S. Muthukrishnan, Uri Nadav


Documentos relacionados