Computing Optimal Bundles for Sponsored Search
Computing Optimal Bundles for Sponsored Search
复制标题
DOI：
10.1007/978-3-540-77105-0_63
复制
发表时间：
2007-12
期刊：
影响因子：
--
通讯作者：
Arpita Ghosh;Hamid Nazerzadeh;Mukund Sundararajan
中科院分区：
文献类型：
--
作者：
Arpita Ghosh;Hamid Nazerzadeh;Mukund Sundararajan
上下文赞助搜索是关于查询的附加信息，例如用户的年龄、性别或位置，这些信息可以改变广告的相关性或广告商对该查询的价值。给定一组上下文，如果搜索引擎为每个上下文运行单独的拍卖，广告商的福利将最大化；然而，由于在上下文中缺乏竞争，这可能导致收入的重大损失。一般来说，无论是单独拍卖还是纯捆绑销售都不需要实现收益最大化。在此动机下，我们研究了在第二价格机制下计算一组商品的收益最大化分配的算法问题和对捆绑的附加估价问题。我们证明了这个问题是强np困难的，并提出了一种算法，该算法可以从最优划分中获得收益的近似。该算法同时产生最优福利的近似值，从而确保收入的增加不以福利为代价。最后，我们证明了我们的算法可以应用于具有多个槽位的赞助搜索设置，以获得最优分区的常因子近似收益。
contextin sponsored search is additional information about a query, such as the user’s age, gender or location, that can change an advertisement’s relevance or an advertiser’s value for that query. Given a set of contexts, advertiser welfare is maximized if the search engine runs a separate auction for each context; however, due to lack of competition within contexts, this can lead to a significant loss in revenue. In general, neither separate auctions nor pure bundling need maximize revenue.With this motivation, we study the algorithmic question of computing the revenue-maximizing partition of a set of items under a second-price mechanism and additive valuations for bundles. We show that the problem is strongly NP-hard, and present an algorithm that yields a-approximation of the revenue from the optimal partition. The algorithm simultaneously yields a-approximation of the optimal welfare, thus ensuring that the gain in revenue is not at the cost of welfare. Finally we show that our algorithm can be applied to the sponsored search setting with multiple slots, to obtain a constant factor approximation of the revenue from the optimal partition.