Sample Complexity of Solving Non-Cooperative Games
Ehsan Nekouei, Girish N Nair, Tansu Alpcan, Robin J Evans
IEEE Transactions on Information Theory | Institute of Electrical and Electronics Engineers | Published : 2020
This paper studies the complexity of solving two classes of non-cooperative games in a distributed manner, in which the players communicate with a set of system nodes over noisy communication channels. The complexity of solving each game class is defined as the minimum number of iterations required to find a Nash equilibrium (NE) of any game in that class with ∈ accuracy. First, we consider the class G of all N-player non-cooperative games with a continuous action space that admit at least one NE. Using information-theoretic inequalities, a lower bound on the complexity of solving G is derived which depends on the Kolmogorov 2∈-capacity of the constraint set and the total capacity of the com..View full abstract
Related Projects (3)
Awarded by Australian Research Council
Awarded by ARC
This work was supported by the Australian Research Council's Discovery Projects funding scheme under Grant DP140100819. The work of G. N. Nair was supported by ARC under Grant FT140100527. This article was presented in part at the 6th IFAC NecSys Workshop.