...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Performance evaluation review >Efficiency of Best Response Dynamics with High Playing Rates in Potential Games
【24h】

Efficiency of Best Response Dynamics with High Playing Rates in Potential Games

机译：潜在游戏中具有较高游戏率的最佳响应动力学的效率

获取原文
获取原文并翻译 | 示例
   

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper we design and analyze distributed best response dynamics to compute Nash equilibria in potential games. This algorithm uses local Poisson clocks for each player and does not rely on the usual but unrealistic assumption that players take no time to compute their best response. If this time (denoted d) is taken into account, distributed best response dynamics (BRD) may suffer from overlaps: one player starts to play while another player has not changed its strategy yet. An overlap may lead to a decrease of the potential but we can show that they do not jeopardize eventual convergence to a Nash equilibrium. Our main result is to use a Markovian approach to show that the average execution time of the algorithm E[T_(BRD)] can be bounded: 2δn log n/log log n + O(n) ≤ E[T_(BRD)] ≤ 4e~γδn log n/ log log n+O(n), where 7 is the Euler constant, n is the number of players and S is the time taken by one player to compute its best response. These bounds are obtained by using an asymptotically optimal playing rate λ. Our analytic bound shows that 2δλ = log log n - log C, where C is a constant. This induces a large probability of overlap (p = 1 - C/log~(1/2)n). In practice, numerical simulations also show that using high playing rates is efficient, with an optimal probability of overlap p_(opt) ≈ 0.78, for n up to 250. This shows that best response dynamics are unexpectedly efficient to compute Nash equilibria, even in a distributed setting.
机译：在本文中，我们设计和分析了分布式最佳响应动力学，以计算潜在博弈中的纳什均衡。该算法为每个玩家使用本地Poisson时钟，并且不依赖通常但不切实际的假设，即玩家没有时间来计算其最佳响应。如果考虑到此时间（表示为d），则分布式最佳响应动力学（BRD）可能会出现重叠：一个玩家开始玩游戏，而另一个玩家尚未改变其策略。重叠可能导致电位降低，但我们可以证明它们不会危害最终收敛到Nash平衡。我们的主要结果是使用马尔可夫方法证明算法E [T_（BRD）]的平均执行时间是有界的：2δnlog n / log log n + O（n）≤E [T_（BRD）] ≤4e〜γδnlog n / log log n + O（n），其中7是欧拉常数，n是游戏者数量，S是一个游戏者计算其最佳响应所花费的时间。这些边界是通过使用渐近最佳播放率λ获得的。我们的解析界表明2δλ= log log n-log C，其中C是常数。这引起了很大的重叠可能性（p ＝ 1-C / log〜（1/2）n）。在实践中，数值模拟还表明，对于n最多为250的情况，使用高播放率是有效的，具有最优的重叠概率p_（opt）≈0.78。这表明，最佳响应动力学意外地有效地计算了纳什均衡，即使在分布式设置。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号