III: Small: Inferring First Movers in Large-Scale Network Games

Title: III: Small: Inferring first movers in large-scale socio-technical networks (NSF IIS-1219071) Statement of Work: We plan to collaborate with the PI at Michigan to accomplish the following tasks in the themes outlines in the award: 1. Scalable Inference for Diffusions: The theme of this proposal is inference problems in social networks. We plan to study approaches for inferring first movers in network diffusions that have lower complexity than using maximum likelihood estimators. One natural approach is to trim certain low probability paths in phase space. Trimming such paths reduces the complexity of the underlying shortest path problem. We will study bounds on the performance of such a heuristics and related techniques. Another approach for reducing complexity might be to aggregate states, creating a smaller graph. In such cases, one may not be able to exactly identify the first movers, but could instead identify the most likely set of nodes containing a first mover. Various aggregation techniques can be considered as well. Such aggregation could in turn be based on properties of the underlying network, for example identifying groups of nodes that would likely have similar likelihoods of being first adopters. Alternatively it could be based on external factors such as the geographic location of users. 2. Generalization of the Game Structure: We plan to consider several variations of the simple coordination game described in the proposal. One variation is to consider models with heterogeneous agents, this can be modeled by allowing the per-link pay-off functions to be link dependent. In some settings it might be reasonable to consider a small number of possible pay-offs based on some other identifiable characteristic of a user. For example, consider a social network with two types of users: buyers and sellers. Another generalization is to enlarge the strategy spaces of the users. For example, following we can consider the case where in addition to adopting one of two technologies: A or B, users can use both technologies but at a higher cost. Additionally, we can relax the assumption of a coordination game and consider other network games. Finally, we can consider variations in the underlying dynamical process by which users are chosen to act and study not only sequential dynamics but multi-site/parallel/block dynamics. 3. Estimating The Social Network Structure. From the preliminary results described in the proposal, it is clear that knowledge of the social network is critical to our analysis. The social network determines the connectivity of in configuration space. Thus, an additional task that we will undertake is the determination of the network structure from time-traces of the adoption process. There are two ways to formulate the problem. The first one is to choose the most likely network graph given the data-traces. The second is to consider an underlying distribution on the network structure, i.e., on possible graphs, and then carrying out the estimation procedure, which would now be a maximum a posteriori probability estimate. 4. Additional Questions: Another generalization that we will consider is when the samples of user actions are not error-free, i.e., in some settings certain users may choose to not report their actions while others may choose to report an action different from what they are playing at the moment. We will study network game with such errors and seek to understand their impact on agent behavior as well as the resulting inference problems.