Due to recent events that have demonstrated the vulnerabilities of global navigation satellite systems (GNSS) there has been an increased interest in alternative methods for localization. One traditional alternative method is terrain-aided navigation (TAN), where a platform localizes itself by measuring the terrain elevation and comparing it to a digital elevation map (DEM). While single-agent TAN has been extensively studied, multi-agent TAN remains less explored. This paper addresses the multi-agent TAN problem with a focus on its properties. We formulate a weighted least squares (WLS) estimator for computing a snapshot solution to the problem and formulate a CramérRao Lower Bound (CRLB) to evaluate it. Using the expressions for the estimator and the CRLB we are able to highlight some insightful properties of the problem. The findings are verified in a simulation study where we evaluate the performance with respect to the altitude sensor accuracy, the group formation accuracy, the number of agents and their formation. Notably, we observe that the solution is relatively insensitive to errors in agent position, suggesting that low-accuracy inertial navigation systems and distance sensors are sufficient for determining their positions. Increasing the number of agents beyond a few seems to have a large effect on both the efficiency and robustness of the estimator, which lessens as the number of agents increases. However, increasing the number of agents does not compensate for poor altitude sensor quality. Additionally, while spatial separation between agents is important for effective map utilization, further separation beyond a certain point does not enhance performance. These findings provide design guidelines for multi-agent TAN systems and identify areas for further research.