TY - JOUR
T1 - Sample Complexity of Solving Non-Cooperative Games
AU - Nekouei, Ehsan
AU - Nair, Girish N.
AU - Alpcan, Tansu
AU - Evans, Robin J.
PY - 2020/2
Y1 - 2020/2
N2 - 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.
AB - 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.
KW - Fano's inequality
KW - information-based complexity
KW - minimax analysis
KW - Nash seeking algorithms
KW - Non-cooperative games
UR - http://www.scopus.com/inward/record.url?scp=85078538096&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85078538096&origin=recordpage
U2 - 10.1109/TIT.2019.2958904
DO - 10.1109/TIT.2019.2958904
M3 - 21_Publication in refereed journal
VL - 66
SP - 1261
EP - 1280
JO - IRE Transactions on Information Theory
JF - IRE Transactions on Information Theory
SN - 0018-9448
IS - 2
M1 - 8930597
ER -