Distributed convergence to Nash equilibria with local utility measurements

We consider multiplayer repeated matrix games in which several players seek to increase their individual rewards by updating their strategies based on limited information. One body of work assumes that players can measure the actions of other players, but do not have access to the utility functions of other players. In this case, well known strategy update mechanisms such as Fictitious Play (FP) and Gradient Play (GP) provide convergence to Nash equilibria in certain special classes of games. Recent work by the authors introduced "dynamic" versions of FP and GP, where players use derivative action to process and respond to the information available to them. These mechanisms, called derivative action FP and derivative Action GP, lead to behaviour converging to Nash equilibria in a significantly larger set of games than standard FP and GP provide. In this paper, we consider the case where players do not have access to opposing actions. As before, players do not have access to opposing player utility functions. Furthermore, a player's access to its own utility function is restricted to the measured utility at each round of the repeated game-structural parameters of its own utility remain unknown. Our main result is to show that derivative action FP and GP can be adapted to the utility measurement case to yield the same dynamics (in continuous-time and up to a coordinate transformation) as though players could measure other player actions. The transformation holds for both two-player games as well as in multiplayer games with a specific utility structure. The implication is that many of the stability and convergence properties obtained under derivative action FP and GP can be extended to the utility measurement case.