Heuristic Rational Models In Social Networks
Abstract
A network of distributed agents wants to minimize a global cost given by a sum of local terms involving nonlinear functions of self and neighboring variables. Agents update their variables at random times by observing the values of neighboring agents and applying a random heuristic rule intent on minimizing the local cost with respect to their own variables. The heuristic rules are rational in that their average result is the actual optimal action with respect to the given values of neighboring variables. By identifying heuristic rational optimization with stochastic coordinate descent it is shown that all agents visit a neighborhood of the 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 derived. Commonly used models of consensus and opinion propagation in social networks are cast in the language of heuristic rational optimization. Numerical results for opinion propagation in social networks are presented to corroborate the analytical results.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 2011
- Accession Number
- ADA557938
Entities
People
- Alejandro Ribeiro
- Ceyhun Eksin
Organizations
- University of Pennsylvania