We thank the reviewers for their feedback. $
We believe that we can convincingly address the main concerns of Assigned_Reviewer_4. 

1) Distributions are hardly ever symmetric.

Response: The reviewer is surely aware of this, but just to make it clear to other readers: Most of the paper (including the main result, Theorem 4.5) is devoted to (possibly) asymmetric distributions. 

2) If distributions are not symmetric then clearly any generalized median will remain a bad estimator. 

Response: Moulin’s characterization (Lemma 2.2) implies that generalized medians are the only truthful estimators. By the revelation principle, when the data sources are strategic, no estimator is better than the best truthful estimator (refer to lines 223-236 of the paper). The reviewer is correct that for specific distributions the guarantees provided by generalized medians (i.e., by any truthful estimator) may not be very compelling. But it is impossible (in a formal sense) to give better guarantees in the face of strategic behavior.

Put another way, one should not directly compare the guarantees provided by truthful estimators with those of untruthful estimators, as the latter guarantees rely on access to true values sampled from the distribution. Without truthfulness, the data may be severely contaminated, in which case estimators like the sample mean may not provide any guarantees.

That said, in practice the choice between truthful and untruthful estimators would crucially depend on what the distribution might look like, and on how likely strategic behavior is. In order to make an informed choice, we must first understand the power and limitations of truthful estimators, which is our goal in the paper. 

3) This paper would have been more interesting if we were considering a regression problem instead of simply estimating the mean. 

Response: This is more subjective, but we wanted to introduce a novel type of question, along with new conceptual connections between statistical ML and mechanism design. We started our investigation with the simpler setting of univariate estimation, which turned out to be quite rich (even though we were able to leverage the strong result by Moulin). We certainly see our paper as laying the foundations for a more extensive investigation -- by us and, hopefully, others in the ICML community -- which will include multi-dimensional estimation, regression, classification, etc.