Abstract
We consider $n$ agents located on the vertices of a connected graph. Each agent $v$ receives a signal $X_v(0) \sim N(s, 1)$ where $s$ is an unknown quantity. A natural iterative way of estimating $s$ is to perform the following procedure: at iteration $t + 1$, let $X_v(t + 1)$ be the average of $X_v(t)$ and of $X_w(t)$ among all the neighbors $w$ of $v$. In this paper, we consider a variant of simple iterative averaging which models "greedy" behavior of the agents. At iteration $t$, each agent $v$ declares its estimator $X_v(t)$ to all neighbors. Then, it updates $X_v(t + 1)$ by taking the maximum likelihood (or minimum variance) estimator of $s$, given $X_v(t)$ and $X_w(t)$ for all neighbors $w$, and the structure of the graph. We provide an efficient procedure for calculating $X_v(t)$, study the convergence of the process, and show that if a limit exists, it is the same for all agents. For graphs symmetric under transitive groups, the process is efficient. However, we demonstrate that this greedy process can be more or less efficient than simple averaging depending on the graph topology, suggesting that individual "greed" may adversely affect the collective outcome.
Introduction
In distributed systems—ranging from sensor networks to social groups—a fundamental challenge is the collective estimation of an unknown parameter $\mu$ based on noisy individual observations. The most common heuristic for reaching consensus is simple iterative averaging, where agents repeatedly update their beliefs by averaging their neighbors' current estimates. While this method eventually leads to consensus, it does not necessarily yield the most statistically efficient estimate (the one with the minimum variance).
This research explores a more sophisticated "greedy" model. Instead of simple averaging, agents act as rational statistical processors. At each step, an agent calculates the Maximum Likelihood Estimator (MLE) of the target parameter by accounting for the correlations inherent in their neighbors' estimates and the known structure of the network. This paper investigates whether such local optimization leads to global optimality.
The Greedy Update Model
The model consists of $n$ agents on a connected graph $G$. The process follows three primary phases:
- Initialization: Each agent $v$ starts with an initial signal $X_v(0) = s + \epsilon_v$, where $\epsilon_v \sim N(0, 1)$ are independent and identically distributed.
- The Greedy Update: At each discrete time step $t+1$, agent $v$ observes the estimates $X_w(t)$ of all its neighbors $w \in N(v)$. The agent then computes the Minimum Variance Unbiased Estimator (MVUE) of $s$ based on these observations.
- Correlation Awareness: Crucially, these agents are not naive. They recognize that their neighbors' estimates are derived from previous steps and are therefore correlated. By understanding the graph structure, agents attempt to "de-bias" the shared information, distinguishing between novel data and information that has merely echoed through the network.
The authors demonstrate that this update rule can be framed as a geometric problem: finding a point in an $n$-dimensional affine space with the minimal $L_2$ norm. This allows the update to be computed efficiently via convex optimization.
Convergence and Consensus
A primary theoretical concern is whether this iterative process reaches a stable state. The authors prove several key properties of the system:
- Well-Definedness: A unique minimum variance estimator always exists for each agent at every step.
- Consensus: If the process converges as $t \to \infty$, all agents must necessarily reach the same estimate. This ensures that the network eventually speaks with one voice, even if that voice is not perfectly optimal.
- The Role of Memory: An important finding is that sub-optimality is a product of "memorylessness." If agents simply retain their original signal $X_v(0)$ and include it in their MLE calculation at every step, the network is guaranteed to converge to the global optimum. The "greedy" failures occur only when agents rely solely on the current state of their neighbors.
The Impact of Network Topology
The efficiency of the greedy process is highly sensitive to the symmetry of the graph.
Symmetric (Transitive) Graphs
In transitive graphs—where the network looks identical from the perspective of every node (e.g., complete graphs, rings, or hypercubes)—the greedy process is globally efficient. In these cases, local optimization perfectly aligns with global optimization, and the agents converge to the same variance they would achieve if a single central processor had access to all initial signals simultaneously.
The Star Graph Advantage
In a star graph (a central hub connected to multiple leaves), the greedy process is exceptionally effective. It reaches the global optimum (variance $1/n$) in just two steps. In contrast, simple averaging on a star graph is significantly slower and converges to a much higher asymptotic variance (approximately $1/9$).
The "Price of Greed" in Asymmetric Graphs
Surprisingly, in asymmetric structures like path graphs, local greed can be a liability. For a path of four nodes, the greedy process converges to a variance of $\approx 0.268$. Simple averaging, despite its relative simplicity, achieves a superior (lower) variance of $0.26$. By attempting to be "too smart" about local correlations, agents in a line can inadvertently underweight valuable information coming from distant parts of the chain.
Conclusion and Future Directions
This work highlights a nuanced "price of anarchy" in distributed estimation. While local Maximum Likelihood updates are computationally efficient and optimal for symmetric or hub-and-spoke networks, they can be outperformed by simple averaging in linear or asymmetric structures.
Several questions remain open. While the authors conjecture that the process always converges, a general proof for all graph types is still needed. Additionally, the model assumes agents possess global knowledge of the graph structure to calculate covariances—a requirement that may be impractical for massive, decentralized networks. Future research may explore the performance of these greedy agents under conditions of limited structural knowledge or in the presence of dynamic network changes.
Summary updated