A Truthful Two-Stage Mechanism for Eliciting Probabilistic Estimates with Unknown Costs

Papakonstantinou, A. and Rogers, A. and Gerding, E. H. and Jennings, N. R (2008): A Truthful Two-Stage Mechanism for Eliciting Probabilistic Estimates with Unknown Costs. Published in: Proceedings of the 18th European Conference on Artificial Intelligence (ECAI'08) : pp. 448-452.

Abstract

This paper reports on the design of a novel two-stage mechanism, based on strictly proper scoring rules, that motivates selfish rational agents to make a costly probabilistic estimate or forecast of a specified precision and report it truthfully to a centre. Our mechanism is applied in a setting where the centre is faced with multiple agents, and has no knowledge about their costs. Thus, in the first stage of the mechanism, the centre uses a reverse second price auction to allocate the estimation task to the agent who reveals the lowest cost. While, in the second stage, the centre issues a payment based on a strictly proper scoring rule. When taken together, the two stages motivate agents to reveal their true costs, and then to truthfully reveal their estimate. We prove that this mechanism is incentive compatible and individually rational, and then present empirical results comparing the performance of the well known quadratic, spherical and logarithmic scoring rules. We show that the quadratic and the logarithmic rules result in the centre making the highest and the lowest expected payment to agents respectively. At the same time, however, the payments of the latter rule are unbounded, and thus the spherical rule proves to be the best candidate in this setting.

• Item Type: MPRA Paper
• Language: English
• Keywords: mechanism design; computer science; artificial intelligence; multi-agent systems; scoring rules
• Subjects: D - Microeconomics > D4 - Market Structure, Pricing, and Design > D44 - Auctions; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D82 - Asymmetric and Private Information ; Mechanism Design; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D83 - Search ; Learning ; Information and Knowledge ; Communication ; Belief ; Unawareness

References

1. A. D. Hendrickson and R. J. Buehler, ‘Proper scores for probability forecasters’, The Annals of Mathematical Statistics, 42(6), 1916–1921, (1971).

2. R. Jurca and B. Faltings, ‘Reputation-based service level agreements for web services’, in Proceedings of the International Conference on Service Oriented Computing (ICSOC), pp. 396–409, (2005).

3. J. E. Matheson and R. L. Winkler, ‘Scoring rules for continuous probability distributions’, Management Science, 22(10), 1087–1096, (1976).

4. N. Miller, P. Resnick, and R. Zeckhauser, ‘Eliciting honest feedback: The peer prediction method’, Management Science, 51(9), 1359–1373, (2005).

5. L. J. Savage, ‘Elicitation of personal probabilities and expectations’, Journal of the American Statistical Association, 66(336), 783–801, (1977).

6. R. Selten, ‘Axiomatic characterization of the quadratic scoring rule’, Experimental Economics, 1(1), 43–61, (1998).

7. A. Zohar and J. S. Rosenschein, ‘Robust mechanisms for information elicitation’, in Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1202–1204, (2006).