Complexity and stochastic evolution of dyadic networks

A strategic model of network formation is developed which permits unreliable links and organizational costs. Finding a connected Nash network which guarantees a given payoff to each player proves to be an NP-hard problem. For the associated evolutionary game with asynchronous updating and logit updating rules, the stochastically stable networks are characterized. The organization of agents into networks has an important role in the communication of information within a spatial structure. One goal is to understand how such networks form and evolve over time. Our agents are endowed with some information which can be accessed by other agents forming links with them. Link formation is costly and communication not fully reliable. We model the process of network formation as a non-cooperative game, and we then focus on Nash networks. But, showing existence of a Nash network with particular properties and computing one are two different tasks. The aim of this paper is to show that computing a connected Nash network is a computationally demanding optimization problem. The question then arises what outcomes might be chosen by agents who would like to form a connected Nash network but fail to achieve their goal because of computational limitations. We propose a stochastic evolutionary model. By solving a companion global optimization problem, this model selects a subset of Nash networks referred to as the set of stochastically stable networks. (c) 2004 Elsevier Ltd. All rights reserved.