• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Proceedings of the 12th ACM conference on electronic commerce. >On the Efficiency of Equilibria in Generalized Second Price Auctions
【24h】

On the Efficiency of Equilibria in Generalized Second Price Auctions

机译：广义第二价格拍卖中的均衡效率

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In sponsored search auctions, advertisers compete for a number of available advertisement slots of different quality. The auctioneer decides the allocation of advertisers to slots using bids provided by them. Since the advertisers may act strategically and submit their bids in order to maximize their individual objectives, such an auction naturally defines a strategic game among the advertisers. In order to quantify the efficiency of outcomes in generalized second price auctions, we study the corresponding games and present new bounds on their price of anarchy, improving the recent results of Paes Leme and Tardos [16] and Lucier and Paes Leme [13]. For the full information setting, we prove a surprisingly low upper bound of 1.282 on the price of anarchy over pure Nash equilibria. Given the existing lower bounds, this bound denotes that the number of advertisers has almost no impact on the price of anarchy. The proof exploits the equilibrium conditions developed in [16] and follows by a detailed reasoning about the structure of equilibria and a novel relation of the price of anarchy to the objective value of a compact mathematical program. For more general equilibrium classes (i.e.. mixed Nash, correlated, and coarse correlated equilibria), we present an upper bound of 2.310 on the price of anarchy. We also consider the setting where advertisers have incomplete information about their competitors and prove a price of anarchy upper bound of 3.037 over Bayes-Nash equilibria. In order to obtain the last two bounds, we adapt techniques of Lucier and Paes Leme [13] and significantly extend them with new arguments.
机译：在赞助的搜索拍卖中，广告商争夺许多不同质量的可用广告位。拍卖师使用广告客户提供的出价来决定广告客户对广告位的分配。由于广告商可以策略性地行动并提交其出价以最大化其各自的目标，因此这样的拍卖自然会在广告商之间定义战略游戏。为了量化广义第二次拍卖中结果的效率，我们研究了相应的游戏并提出了其无政府状态价格的新界限，从而改善了Paes Leme和Tardos [16]和Lucier和Paes Leme [13]的最新结果。对于完整的信息设置，我们证明了无政府定价相对于纯纳什均衡的惊人低上限1.282。给定现有的下限，此界限表示广告商数量几乎对无政府状态的价格没有影响。该证明利用了[16]中提出的均衡条件，随后对均衡的结构进行了详细的推理，并把无政府状态的价格与紧凑型数学程序的目标值之间建立了新颖的联系。对于更一般的均衡类（即混合Nash，相关和粗相关均衡），我们给出无政府状态价格的上限2.310。我们还考虑了以下情况：广告商不完整地了解其竞争对手的信息，并证明无价上限的价格超过贝叶斯-纳什均衡的3.037。为了获得最后两个界限，我们采用了Lucier和Paes Leme [13]的技术，并用新的论据对其进行了显着扩展。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号