  In many real world networks agents are initially unsure of each other's
qualities and must learn about each other over time via repeated interactions.
This paper is the first to provide a methodology for studying the dynamics of
such networks, taking into account that agents differ from each other, that
they begin with incomplete information, and that they must learn through past
experiences which connections/links to form and which to break. The network
dynamics in our model vary drastically from the dynamics in models of complete
information. With incomplete information and learning, agents who provide high
benefits will develop high reputations and remain in the network, while agents
who provide low benefits will drop in reputation and become ostracized. We
show, among many other things, that the information to which agents have access
and the speed at which they learn and act can have a tremendous impact on the
resulting network dynamics. Using our model, we can also compute the ex ante
social welfare given an arbitrary initial network, which allows us to
characterize the socially optimal network structures for different sets of
agents. Importantly, we show through examples that the optimal network
structure depends sharply on both the initial beliefs of the agents, as well as
the rate of learning by the agents. Due to the potential negative consequences
of ostracism, it may be necessary to place agents with lower initial
reputations at less central positions within the network.
