HEURISTIC RATIONAL MODELS IN SOCIAL NETWORKS

A network of social agents wants to minimize a global cost given by a sum of local terms involving convex nonlinear functions of self and neighboring variables. Agents update their variables at random times according to a random heuristic rule that is on average optimal with respect to the local cost given values of neighboring agents. When all agents apply heuristic rational optimization, convergence result shows that global cost visits a neighborhood of optimal cost infinitely often with probability 1. An exponential probability bound on the worst deviation from optimality between visits to near optimal operating points is also presented. Models of opinion propagation and voting are cast in the language of heuristic rational optimization. Numerical results are presented for the opinion propagation model on both geometric and small-world network structures.