LTH-image


Abstract

Lower Bounds on the Complexity of Solving Two Classes of Non-cooperative Games

Ehsan Nekouei, KTH

Abstract:  

In this talk, I will discuss 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  $\epsilon$ accuracy. First, we consider the class $\mathcal{G}$ of all $N$-player non-cooperative games with a continuous action space that admit at least one NE. Using information-theoretic inequalities, we derive a lower bound on the complexity of solving $\mathcal{G}$ that depends on the Kolmogorov $2\epsilon$-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 $\mathcal{G}$ which depends on the volume and surface area of the constraint set.  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. Our result in the non-Gaussian  case is derived by establishing a connection between the Kullback-Leibler distance and Fisher information.