Mechanism Design for the truthful elicitation of costly probabilistic estimates in Distributed Information Systems

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. 648-672.

Abstract

This paper reports on the design of a novel two-stage 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
• Language: English
• Keywords: Multiagent systems; Scoring rules; Auction theory; Mechanism design
• Subjects: D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D81 - Criteria for Decision-Making 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

References

G. Adomavicius and A. Tuzhilin. Toward the next generation of recommender systems: A survey of the state-of-the-art 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. Verification 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 Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, pages 98–106, 2004.

R. Day and P. Milgrom. Core-selecting 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 self-verified, 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 principal-agent 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? Earth-Science 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. Efficient 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. Reputation-based 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. Mas-Colell, 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: Efficiency. 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 two-stage mechanism for eliciting probabilistic estimates with unknown costs. In Proceedings of the Eighteenth European Conference on Artificial 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. Artificial 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. Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty. Journal of Artificial Intelligence Research, 35:119–159, 2009.

W. P. Rogerson. The first-order approach to principal-agent 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. Werner-Allen, 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): Storm-scale numerical weather prediction and data assimilation. Meteorology and Atmospheric Physics, 82(1-4):139–170, 2004.

M. Yokoo, Y. Sakurai, and S. Matsubara. The effect of false-name 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 flood warning system. Journal of Computer Science and Technology, 22(1):121–130, 2007.

A. Zohar and J. S. Rosenschein. Mechanisms for information elicitation. Artificial Intelligence, 172(16-17):1917–1939, 2008.