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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

2 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)244-249
Journal / PublicationIFAC-PapersOnLine
Volume49
Issue number22
Online published1 Nov 2016
Publication statusPublished - 2016
Externally publishedYes

Workshop

Title6th IFAC Workshop on Distributed Estimation and Control in Networked Systems NECSYS 2016
LocationTokyo International Exchange Center
PlaceJapan
CityTokyo
Period8 - 9 September 2016

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.

Citation Format(s)

Lower Bounds on the Best-Case Complexity of Solving a Class of Non-cooperative Games. / Nekouei, Ehsan; Alpcan, Tansu; Nair, Girish N.; Evans, Robin J.

In: IFAC-PapersOnLine, Vol. 49, No. 22, 2016, p. 244-249.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review