Truthful Univariate Estimators

Ioannis Caragiannis, Ariel Procaccia, Nisarg Shah
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:127-135, 2016.

Abstract

We revisit the classic problem of estimating the population mean of an unknown single-dimensional distribution from samples, taking a game-theoretic viewpoint. In our setting, samples are supplied by strategic agents, who wish to pull the estimate as close as possible to their own value. In this setting, the sample mean gives rise to manipulation opportunities, whereas the sample median does not. Our key question is whether the sample median is the best (in terms of mean squared error) truthful estimator of the population mean. We show that when the underlying distribution is symmetric, there are truthful estimators that dominate the median. Our main result is a characterization of worst-case optimal truthful estimators, which provably outperform the median, for possibly asymmetric distributions with bounded support.

Cite this Paper


BibTeX
@InProceedings{pmlr-v48-caragiannis16, title = {Truthful Univariate Estimators}, author = {Caragiannis, Ioannis and Procaccia, Ariel and Shah, Nisarg}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {127--135}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/caragiannis16.pdf}, url = {https://proceedings.mlr.press/v48/caragiannis16.html}, abstract = {We revisit the classic problem of estimating the population mean of an unknown single-dimensional distribution from samples, taking a game-theoretic viewpoint. In our setting, samples are supplied by strategic agents, who wish to pull the estimate as close as possible to their own value. In this setting, the sample mean gives rise to manipulation opportunities, whereas the sample median does not. Our key question is whether the sample median is the best (in terms of mean squared error) truthful estimator of the population mean. We show that when the underlying distribution is symmetric, there are truthful estimators that dominate the median. Our main result is a characterization of worst-case optimal truthful estimators, which provably outperform the median, for possibly asymmetric distributions with bounded support.} }
Endnote
%0 Conference Paper %T Truthful Univariate Estimators %A Ioannis Caragiannis %A Ariel Procaccia %A Nisarg Shah %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-caragiannis16 %I PMLR %P 127--135 %U https://proceedings.mlr.press/v48/caragiannis16.html %V 48 %X We revisit the classic problem of estimating the population mean of an unknown single-dimensional distribution from samples, taking a game-theoretic viewpoint. In our setting, samples are supplied by strategic agents, who wish to pull the estimate as close as possible to their own value. In this setting, the sample mean gives rise to manipulation opportunities, whereas the sample median does not. Our key question is whether the sample median is the best (in terms of mean squared error) truthful estimator of the population mean. We show that when the underlying distribution is symmetric, there are truthful estimators that dominate the median. Our main result is a characterization of worst-case optimal truthful estimators, which provably outperform the median, for possibly asymmetric distributions with bounded support.
RIS
TY - CPAPER TI - Truthful Univariate Estimators AU - Ioannis Caragiannis AU - Ariel Procaccia AU - Nisarg Shah BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-caragiannis16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 127 EP - 135 L1 - http://proceedings.mlr.press/v48/caragiannis16.pdf UR - https://proceedings.mlr.press/v48/caragiannis16.html AB - We revisit the classic problem of estimating the population mean of an unknown single-dimensional distribution from samples, taking a game-theoretic viewpoint. In our setting, samples are supplied by strategic agents, who wish to pull the estimate as close as possible to their own value. In this setting, the sample mean gives rise to manipulation opportunities, whereas the sample median does not. Our key question is whether the sample median is the best (in terms of mean squared error) truthful estimator of the population mean. We show that when the underlying distribution is symmetric, there are truthful estimators that dominate the median. Our main result is a characterization of worst-case optimal truthful estimators, which provably outperform the median, for possibly asymmetric distributions with bounded support. ER -
APA
Caragiannis, I., Procaccia, A. & Shah, N.. (2016). Truthful Univariate Estimators. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:127-135 Available from https://proceedings.mlr.press/v48/caragiannis16.html.

Related Material