首页    期刊浏览 2025年01月22日 星期三
登录注册

文章基本信息

  • 标题: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).
  • 本地全文:下载
  • 作者:Ehsan Nekouei ; Ehsan Nekouei ; Tansu Alpcan
  • 期刊名称:IFAC PapersOnLine
  • 印刷版ISSN:2405-8963
  • 出版年度:2016
  • 卷号:49
  • 期号:22
  • 页码:244-249
  • DOI:10.1016/j.ifacol.2016.10.404
  • 语种:English
  • 出版社:Elsevier
  • 摘要: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.
国家哲学社会科学文献中心版权所有