Reaching agreement despite noise in communication is a fundamental problem in multi-agent systems. Here we study this problem under an idealized model, where it is assumed that agents can sense the general tendency in the system. More specifically, we consider $n$ agents, each being associated with a real-valued number. In each round, each agent receives a noisy measurement of the average value, and then updates its value, which is in turn perturbed by random drift. We assume that both noises in measurements and drift follow Gaussian distributions. What should be the updating policy of agents if their goal is to minimize the expected deviation of the agents' values from the average value? We prove that a distributed weighted-average algorithm optimally minimizes this deviation for each agent, and for any round. Interestingly, this optimality holds even in the centralized setting, where a master agent can gather all the agents' measurements and instruct a move to each agent.We find this result surprising since it can be shown that the total measurements obtained by all agents contain strictly more information about the deviation of Agent $i$ from the average value, than the information contained in the measurements obtained by Agent $i$ alone. Although this information is relevant for Agent $i$, it is not processed by it when running a weighted-average algorithm. Nevertheless, the weighted-average algorithm is optimal, since by running it, other agents manage to fully process this information in a way that perfectly benefits Agent $i$.Finally, we also analyze the drift of the center of mass and show that no distributed algorithm can achieve drift that is as small as the one that can be achieved by the best centralized algorithm. In light of this, we also show that the drift associated with our weighted-average algorithm incurs a relatively small overhead over the best possible drift in the centralized setting.
翻译:在多试剂系统中,尽管通信中出现噪音,但仍要达成协议,这是多试剂系统的一个根本问题。 我们在这里根据一种理想化的模式研究这一问题, 假设代理人能够感觉到系统中的一般趋势。 更具体地说, 我们考虑的是, 美元代理, 每一个代理都与实际价值挂钩。 有趣的是, 在每轮中, 每一个代理都得到平均价值的噪音测量, 然后更新其价值, 而这反过来又会受到随机漂移的干扰。 我们认为, 测量和漂移中的噪音是多试剂分布的一个根本问题。 如果代理人的更新政策的目标是最大限度地减少代理人价值与平均价值的预期偏差? 我们证明, 一个分布的加权平均算法, 最大限度地减少每个代理商的这种偏差, 有趣的是, 这个最佳代理商可以收集所有代理商的测量结果, 并且我们通过一个正常的高度的计算法, 最精确的算法可以显示, 最精确的 美元 。