Papakonstantinou, A. and Rogers, A and Gerding, E. H. and Jennings, N. R. (2010): Mechanism Design for the truthful elicitation of costly probabilistic estimates in Distributed Information Systems. Published in: Artificial Intelligence , Vol. 175, No. 2 (February 2011): pp. 648672.

PDF
MPRA_paper_43324.pdf Download (270kB)  Preview 
Abstract
This paper reports on the design of a novel twostage mechanism, based on strictly proper scoring rules, that allows a centre to acquire a costly forecast of a future event (such as a meteorological phenomenon) or a probabilistic estimate of a specific parameter (such as the quality of an expected service), with a specified minimum precision, from one or more agents. In the first stage, the centre elicits the agents' true costs and identifies the agent that can provide an estimate of the specified precision at the lowest cost. Then, in the second stage, the centre uses an appropriately scaled strictly proper scoring rule to incentivise this agent to generate the estimate with the required precision, and to truthfully report it. In particular, this is the first mechanism that can be applied to settings in which the centre has no knowledge about the actual costs involved in the generation an agents' estimates and also has no external means of evaluating the quality and accuracy of the estimates it receives. En route to this mechanism, we first consider a setting in which any single agent can provide an estimate of the required precision, and the centre can evaluate this estimate by comparing it with the outcome which is observed at a later stage. This mechanism is then extended, so that it can be applied in a setting where the agents' different capabilities are reflected in the maximum precision of the estimates that they can provide, potentially requiring the centre to select multiple agents and combine their individual results in order to obtain an estimate of the required precision. For all three mechanisms (the original and the two extensions), we prove their economic properties (i.e. incentive compatibility and individual rationality) and then perform a number of numerical simulations. For the single agent mechanism we compare the quadratic, spherical and logarithmic scoring rules with a parametric family of scoring rules. We show that although the logarithmic scoring rule minimises both the mean and variance of the centre's total payments, using this rule means that an agent may face an unbounded penalty if it provides an estimate of extremely poor quality. We show that this is not the case for the parametric family, and thus, we suggest that the parametric scoring rule is the best candidate in our setting. Furthermore, we show that the 'multiple agent' extension describes a family of possible approaches to select agents in the first stage of our mechanism, and we show empirically and prove analytically that there is one approach that dominates all others. Finally, we compare our mechanism to the peer prediction mechanism introduced by Miller et al. (2007) [29] and show that the centre's total expected payment is the same in both mechanisms (and is equal to total expected payment in the case that the estimates can be compared to the actual outcome), while the variance in these payments is significantly reduced within our mechanism.
Item Type:  MPRA Paper 

Original Title:  Mechanism Design for the truthful elicitation of costly probabilistic estimates in Distributed Information Systems 
Language:  English 
Keywords:  Multiagent systems; Scoring rules; Auction theory; Mechanism design 
Subjects:  D  Microeconomics > D8  Information, Knowledge, and Uncertainty > D81  Criteria for DecisionMaking under Risk and Uncertainty D  Microeconomics > D4  Market Structure, Pricing, and Design > D44  Auctions D  Microeconomics > D8  Information, Knowledge, and Uncertainty > D82  Asymmetric and Private Information ; Mechanism Design 
Item ID:  43324 
Depositing User:  Athanasios Papakonstantinou 
Date Deposited:  19 Dec 2012 02:19 
Last Modified:  28 Sep 2019 04:45 
References:  G. Adomavicius and A. Tuzhilin. Toward the next generation of recommender systems: A survey of the stateoftheart and possible extensions. IEEE Transactions on Knowledge and Data Engineering, 17(6):734–749, 2005. B. C. Arnold, N. Balakrishnan, and H. N. Nagaraja. A First Course in Order Statistics. SIAM, 2008. J. E. Berg and T. A. Rietz. Prediction markets as decision support systems. Information Systems Frontiers, 5(1):79–93, 2003. G. W. Brier. Veriﬁcation of forecasts expressed in terms of probability. Monthly Weather Review, 78:1–3, 1950. E. Clarke. Multipart pricing of public goods. Public Choice, 11(1):17–33, 1971. A. Czumaj and A. Ronen. On the expected payment of mechanisms for task allocation. In Proceedings of the TwentyThird Annual ACM Symposium on Principles of Distributed Computing, pages 98–106, 2004. R. Day and P. Milgrom. Coreselecting package auctions. International Journal of Game Theory, 36(3):393–407, 2008. M. H. DeGroot and M. J. Schervish. Probability and Statistics. Addison Wesley, 2002. S. Goel, D. M. Reeves, and D. M. Pennock. Collective revelation: A mechanism for selfveriﬁed, weighted, and truthful predictions. In Proceedings of the ACM Conference on Electronic Commerce, pages 265–274, Stanford, California, USA, 2009. P. C. Gregory. Bayesian logical data analysis for the physical sciences: A comparative approach with Mathematica support. Cambridge Univ Pr, 2005. S. J. Grossman and O. D. Hart. An analysis of the principalagent problem. Econometrica, 51 (1):7–45, 1983. T. Groves. Incentives in teams. Econometrica, 41(4):617–631, 1973. R. Hanson. Logarithmic market scoring rules for modular combinatorial information aggregation. The Journal of Prediction Markets, 1(1):3–15, 2007. R. Hanson. Combinatorial information market design. Information Systems Frontiers, 5(1): 107–119, 2003. J. K. Hart and K. Martinez. Environmental sensor networks: A revolution in the earth system science? EarthScience Reviews, 78:177–191, 2006. A. D. Hendrickson and R. J. Buehler. Proper scores for probability forecasters. The Annals of Mathematical Statistics, 42(6):1916–1921, 1971. P. Jehiel and B. Moldovanu. Efﬁcient design with interdependent valuations. Econometrica, 69 (5):1237–1259, 2001. A. Jøsang, R. Ismail, and A. Boydb. A survey of trust and reputation systems for online service provision. Decision Support Systems, 43(2):618–644, 2007. R. Jurca and B. Faltings. Reputationbased service level agreements for web services. In Service Oriented Computing, volume 3826 of Lecture Notes in Computer Science, pages 396–409. Springer Berlin / Heidelberg, 2005. R. Jurca and B. Faltings. Minimum payments that reward honest reputation feedback. In Proceedings of the ACM Conference on Electronic Commerce, pages 190–199, Ann Arbor, Michigan, USA, 2006. R. Jurca and B. Faltings. Collusion resistant, incentive compatible feedback payments. In Proceedings of the ACM Conference on Electronic Commerce, pages 200–209, San Diego, California, USA, 2007. M. Klein, G. A. Moreno, D. C. Parkes, D. Plakosh, S. Seuken, and K. Wallnau. Handling interdependent values in an auction mechanism for enhanced bandwidth allocation in tactical data networks. In Proceedings of the 3rd international workshop on Economics of networked systems, (NetEcon 2008), pages 73–78, New York, USA, 2008. V. Krishna. Auction Theory. Academic Press, 2002. A. MasColell, M. D. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, 1995. J. E. Matheson and R. L. Winkler. Scoring rules for continuous probability distributions. Management Science, 22(10):1087–1096, 1976. C. Mezzetti. Mechanism design with interdependent valuations: Efﬁciency. Econometrica, 72 (5):1617–1626, 2004. C. Mezzetti. Mechanism design with interdependent valuations: Surplus extraction. Economic Theory, 31(3):473–488, 2007. N. H. Miller, J. W. Pratt, R. J. Zeckhauser, and S. Johnson. Mechanism design with multidimensional, continuous types and interdependent valuations. Journal of Economic Theory, 136: 476–496, 2007a. N. H. Miller, P. Resnick, and R. J. Zeckhauser. Eliciting honest feedback: The peer prediction method. Management Science, 51(9):1359–1373, 2007b. A. Papakonstantinou, A. Rogers, E. H. Gerding, and N. R. Jennings. A truthful twostage mechanism for eliciting probabilistic estimates with unknown costs. In Proceedings of the Eighteenth European Conference on Artiﬁcial Intelligence, pages 448–452, Patras, Greece, 2008. A. Papakonstantinou, A. Rogers, E. H. Gerding, and N. R. Jennings. Mechanism design for eliciting probabilistic estimates from multiple suppliers with unknown costs and limited precision. In Proceedings of the Eleventh Worhshop in Agent Mediated Electronic Commerce, pages 111–124, Budapest, Hungary, 2009. R. Porter, A. Ronen, Y. Shoham, and M. Tennenholtz. Fault tolerant mechanism design. Artiﬁcial Intelligence, 172(15):1783–1799, 2008. D. Prelec. A Bayesian truth serum for subjective data. Science, 306(5695):462–466, 2004. S. D. Ramchurn, C. Mezzetti, A. Giovannucci, J. A. Rodriguez, R. K. Dash, and N. R. Jennings. Trustbased mechanisms for robust and efﬁcient task allocation in the presence of execution uncertainty. Journal of Artiﬁcial Intelligence Research, 35:119–159, 2009. W. P. Rogerson. The ﬁrstorder approach to principalagent problems. Econometrica, 53(6): 1357–1367, 1985. L. J. Savage. Elicitation of personal probabilities and expectations. Journal of the American Statistical Association, 66(336):783–801, 1971. R. Selten. Axiomatic characterization of the quadratic scoring rule. Experimental Economics, 1(1):43–61, 1998. W. Vickrey. Counterspeculation, auctions and competitive sealed tenders. The Journal of Finance, 16(1):8–37, 1961. G. WernerAllen, J. Johnson, M. Ruiz, J. Lees, and M. Welsh. Monitoring volcanic eruptions with a wireless sensor network. In Proceedings of the Second European Workshop on Wireless Sensor Networks, pages 108–120, Instanbul, Turkey, 2005. J. Wolfers and E. Zitzewitz. Prediction markets. Journal of Economic Perspectives, 18(2):107– 126, 2004. M. Xue, D. Wang, J. Gao, and K. Brewster. The advanced regional prediction system (ARPS): Stormscale numerical weather prediction and data assimilation. Meteorology and Atmospheric Physics, 82(14):139–170, 2004. M. Yokoo, Y. Sakurai, and S. Matsubara. The effect of falsename bids in combinatorial auctions: New fraud in internet auctions. Games and Economic Behavior, 46(1):174–188, 2004. J. Zhou and D. De Roure. FloodNet: Coupling adaptive sampling with energy aware routing in a ﬂood warning system. Journal of Computer Science and Technology, 22(1):121–130, 2007. A. Zohar and J. S. Rosenschein. Mechanisms for information elicitation. Artiﬁcial Intelligence, 172(1617):1917–1939, 2008. 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/43324 