Minimizing the Probability of Error for Decision Making over Graphs

Distributed decision-making over graphs involves a group of agents that collaboratively work toward a common objective. In the social learning framework, the agents are tasked to infer an unknown state from a finite set by using a stream of local observations. The probability of decision errors for each agent asymptotically converges to zero at an exponential rate, characterized by the error exponent, which depends on the combination policy employed by the network. This work addresses the challenge of identifying optimal combination policies to maximize the error exponent for the true state while ensuring the errors for all other states converge to zero as well. We derive an upper bound on the achievable error exponent under the social learning rule, and then establish conditions for the combination policy to reach this upper bound. Moreover, we examine the performance loss scenarios when the combination policy is chosen inappropriately. From a geometric perspective, each combination policy induces a weighted nearest neighbor classifier where the weights correspond to the agents' Perron centralities. By implementing an optimized combination policy, we enhance the error exponent, leading to improved accuracy and efficiency in the distributed decision-making process. INDEX TERMS Social learning, combination policy, probability of error, large deviations, error exponent.