TY - GEN
T1 - Strategyproof Mean Estimation from Multiple-Choice Questions
AU - Kahng, Anson
AU - Kehne, Gregory
AU - Procaccia, Ariel D.
N1 - Publisher Copyright:
© 2020 by the Authors.
PY - 2020
Y1 - 2020
N2 - Given n values possessed by n agents, we study the problem of estimating the mean by truthfully eliciting agents' answers to multiple-choice questions about their values. We consider two natural candidates for estimation error: mean squared error (MSE) and mean absolute error (MAE). We design a randomized estimator which is asymptotically optimal for both measures in the worst case. In the case where prior distributions over the agents' values are known, we give an optimal, polynomial-Time algorithm for MSE, and show that the task of computing an optimal estimate for MAE is P-hard. Finally, we demonstrate empirically that knowledge of prior distributions gives a significant edge.
AB - Given n values possessed by n agents, we study the problem of estimating the mean by truthfully eliciting agents' answers to multiple-choice questions about their values. We consider two natural candidates for estimation error: mean squared error (MSE) and mean absolute error (MAE). We design a randomized estimator which is asymptotically optimal for both measures in the worst case. In the case where prior distributions over the agents' values are known, we give an optimal, polynomial-Time algorithm for MSE, and show that the task of computing an optimal estimate for MAE is P-hard. Finally, we demonstrate empirically that knowledge of prior distributions gives a significant edge.
UR - https://www.scopus.com/pages/publications/85105211946
M3 - Conference contribution
AN - SCOPUS:85105211946
T3 - 37th International Conference on Machine Learning, ICML 2020
SP - 5009
EP - 5019
BT - 37th International Conference on Machine Learning, ICML 2020
A2 - Daume, Hal
A2 - Singh, Aarti
PB - International Machine Learning Society (IMLS)
T2 - 37th International Conference on Machine Learning, ICML 2020
Y2 - 13 July 2020 through 18 July 2020
ER -