Consensus Over Martingale Graph Processes

In this paper, we consider a consensus seeking process based on repeated averaging in a randomly changing network. The underlying graph of such a network at each time is generated by a martingale random process. We prove that consensus is reached almost surely if and only if the expected graph of the network contains a directed spanning tree. We then provide an example of a consensus seeking process based on local averaging of opinions in a dynamic model of social network formation which is a martingale. At each time step, individual agents randomly choose some other agents to interact with according to some arbitrary probabilities. The interaction is one-sided and results in the agent averaging her opinion with those of her randomly chosen neighbors based on the weights she assigns to them. Once an agent chooses a neighbor, the weights are updated in such a way that the expected values of the weights are preserved. We show that agents reach consensus in this random dynamical network almost surely. Finally, we demonstrate that a Polya Urn process is a martingale process, and our prior results in [1] is a special case of the model proposed in this paper.