Lower Bounds on the Best-Case Complexity of Solving a Class of Non-cooperative Games^*

详细信息    查看全文

• 作者：Ehsan Nekouei^* ; ^{ehsan.nekouei@unimelb.edu.au" class="auth_mail" title="E-mail the corresponding author} ; Tansu Alpcan^* ; ^{tansu.alpcan@unimelb.edu.au" class="auth_mail" title="E-mail the corresponding author} ; Girish N. Nair^* ; ^{gnair@unimelb.edu.au" class="auth_mail" title="E-mail the corresponding author} ; Robin J. Evans^* ; ^{robinje@unimelb.edu.au" class="auth_mail" title="E-mail the corresponding author}
• 刊名：IFAC-PapersOnLine
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：49
• 期：22
• 页码：244-249
• 全文大小：439 K

文摘

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.