Decentralized Decision Making over Random Graphs*

Decentralized decision making methods often require significant communication between agents. A two-stage approach is presented to ensure a convergent decision making methodology with limited lines of communication. First, a scheme is outlined for randomized, directed communication between agents. Guarantees on connectivity and communication times are illustrated. Additionally, communications of optimal action trajectories for another agent often lead to changes in locally optimal actions. With the assumption that such breakpoints occur as a power law in search time, asymptotic convergence toward a globally optimal consensus is demonstrated.