Title: Lower Bounds on the Complexity of Solving Two Classes of Non-cooperative Games,
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 $\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.