• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IFAC PapersOnLine >Lower Bounds on the Best-Case Complexity of Solving a Class of Non-cooperative Games * * This work was supported by the Australian Research Council’s Discovery Projects funding scheme (DP140100819).
【24h】

Lower Bounds on the Best-Case Complexity of Solving a Class of Non-cooperative Games * * This work was supported by the Australian Research Council’s Discovery Projects funding scheme (DP140100819).

机译：解决一类非合作游戏的最佳情况复杂度的下界 * * 此作品由澳大利亚研究委员会的“探索项目”资助计划（DP140100819）支持。

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

摘要

Abstract: This paper studies the complexity of solving the class G of all N -player non-cooperative games with continuous action spaces that admit at least one Nash equilibrium (NE). We consider a distributed Nash seeking setting where agents communicate with a set of system nodes (SNs), over noisy communication channels, to obtain the required information for updating their actions. The complexity of solving games in the class G is defined as the minimum number of iterations required to find a NE of any game in G with ε accuracy. Using information-theoretic inequalities, we derive a lower bound on the complexity of solving the game class G that depends on the Kolmogorov 2ε-capacity of the constraint set and the total capacity of the communication channels. We also derive a lower bound on the complexity of solving games in G which depends on the volume and surface area of the constraint set.
机译：摘要：本文研究了解决具有连续动作空间且允许至少一个纳什均衡（NE）的所有N个非玩家游戏的类G的复杂性。我们考虑一种分布式Nash搜寻设置，在该设置中，代理通过嘈杂的通信通道与一组系统节点（SN）通信，以获得更新其操作所需的信息。解决类G中游戏的复杂性定义为以ε精度找到G中任何游戏的NE所需的最小迭代次数。使用信息论不等式，我们得出了求解游戏类G的复杂性的下界，该类G取决于约束集的Kolmogorov2ε能力和通信渠道的总容量。我们还得出了在G中求解游戏的复杂性的下限，这取决于约束集的体积和表面积。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号