The detection of agents whose responses satisfy equilibrium play is useful for predicting the dynamics of information propagation in social networks. Using Afriat’s theorem of revealed preferences, we construct a non-parametric detection test to detect if the responses of a group of agents is consistent with play from the Nash equilibrium of a concave potential game. For agents that satisfy the detection test, it is useful to learn the associated concave potential function of the game. In this paper, a non-parametric learning algorithm is provided to estimate the concave potential function of agents with necessary and sufficient conditions on the response class for the algorithm to be a  probably approximately correct  learning algorithm. In the case of response signals measured in noise, a statistical test to detect agents playing a concave potential game that has a pre-specified Type-I error probability is provided. The detection tests and learning algorithm are applied to real-world data sets from the Twitter social network and the Ontario power grid.
['William Hoiles', 'Vikram Krishnamurthy', 'Anup Aprem']
PAC Algorithms for Detecting Nash Equilibrium Play in Social Networks: From Twitter to Energy Markets