Conference Proceedings

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

Ehsan Nekouei, Tansu Alpcan, Girish N Nair, Robin J Evans

Proceedings of the 6th IFAC Workshop on Distributed Estimation and Control in Networked Systems | Elsevier | Published : 2016


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 s..

View full abstract


Awarded by Australian Research Council

Funding Acknowledgements

This work was supported by the Australian Research Council's Discovery Projects funding scheme (DP140100819).