Sample Complexity of Solving Non-Cooperative Games

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

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number8930597
Pages (from-to)1261-1280
Journal / PublicationIEEE Transactions on Information Theory
Volume66
Issue number2
Online published10 Dec 2019
Publication statusPublished - Feb 2020

Abstract

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 communication channels. Our results indicate that the game class G can be solved at most exponentially fast. We next consider the class of all N -player non-cooperative games with at least one NE such that the players' utility functions satisfy a certain (differential) constraint. We derive lower bounds on the complexity of solving this game class under both Gaussian and non-Gaussian noise models. Finally, we derive upper and lower bounds on the sample complexity of a class of quadratic games. It is shown that the complexity of solving this game class scales according to Θ ( 1/ε2) where ε is the accuracy parameter.

Research Area(s)

  • Fano's inequality, information-based complexity, minimax analysis, Nash seeking algorithms, Non-cooperative games

Citation Format(s)

Sample Complexity of Solving Non-Cooperative Games. / Nekouei, Ehsan; Nair, Girish N.; Alpcan, Tansu; Evans, Robin J.

In: IEEE Transactions on Information Theory, Vol. 66, No. 2, 8930597, 02.2020, p. 1261-1280.

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