PAC Algorithms for Detecting Nash Equilibrium Play in Social Networks: From Twitter to Energy Markets

IEEE Access

Vikram Krishnamurthy¹  Anup Aprem²  William Hoiles² 

[1] Department of Electrical and Computer Engineering, Cornell University, Ithaca, NY, USA;Department of Electrical and Computer Engineering, The University of British Columbia, Vancouver, BC, Canada;

关键词: Social network;    Afriat’s theorem;    detecting equilibrium play;    intertemporal utility;    Twitter;    energy market;   

DOI  :  10.1109/ACCESS.2016.2629478

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown