An Information Theoretic Framework For Designing Information Elicitation Mechanisms That Reward Truth-telling

Abstract

In the setting where information cannot be verified, we propose a simple yet powerful information theoretical framework—the Mutual Information Paradigm—for information elicitation mechanisms. Our framework pays every agent a measure of mutual information between her signal and a peer’s signal. We require that the mutual information measurement has the key property that any “data processing” on the two random variables will decrease the mutual information between them. We identify such information measures that generalize Shannon mutual information.

Our Mutual Information Paradigm overcomes the two main challenges in information elicitation without verification: (1) how to incentivize high-quality reports and avoid agents colluding to report random or identical responses; (2) how to motivate agents who believe they are in the minority to report truthfully.

Aided by the information measures, we found (1) we use the paradigm to design a family of novel mechanisms where truth-telling is a dominant strategy and pays better than any other strategy profile (in the multi-question, detail free, minimal setting where the number of questions is large); (2) we show the versatility of our framework by providing a unified theoretical understanding of existing mechanisms—Bayesian Truth Serum Prelec (2004) and Dasgupta and Ghosh (2013)—by mapping them into our framework such that theoretical results of those existing mechanisms can be reconstructed easily.

We also give an impossibility result that illustrates, in a certain sense, the the optimality of our framework.

References

1. Arpit Agarwal, Debmalya Mandal, David C. Parkes, and Nisarg Shah. 2017. Peer prediction with heterogeneous users. In Proceedings of the ACM Conference on Economics and Computation (EC’17). 81--98.
2. Syed Mumtaz Ali and Samuel D. Silvey. 1966. A general class of coefficients of divergence of one distribution from another. J. Roy. Stat. Soc. Ser. B (Methodol.) 28, 1 (1966), 131--142.
3. S.-I. Amari and A. Cichocki. 2010. Information geometry of divergence functions. Bull. Polish Acad. Sci.: Tech. Sci. 58, 1 (2010), 183--195.
4. Lev M. Bregman. 1967. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7, 3 (1967), 200--217.
5. Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory, 2nd ed. Wiley Interscience.
6. Imre Csiszár, Paul C. Shields et al. 2004. Information theory and statistics: A tutorial. Found. Trends Commun. Info. Theory 1, 4 (2004), 417--528.
7. Anirban Dasgupta and Arpita Ghosh. 2013. Crowdsourced judgement elicitation with endogenous proficiency. In Proceedings of the 22nd International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 319--330.
8. Boi Faltings, Radu Jurca, Pearl Pu, and Bao Duy Tran. 2014. Incentives to counter bias in human computation. In Proceedings of the 2nd AAAI Conference on Human Computation and Crowdsourcing.
9. Rafael M. Frongillo and Jens Witkowski. 2016. A geometric method to construct minimal peer prediction mechanisms. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI’16). 502--508.
10. A. Gao, J. R. Wright, and K. Leyton-Brown. 2016. Incentivizing evaluation via limited access to ground truth: Peer-prediction makes things worse. ArXiv e-prints. arxiv:cs.GT/1606.07042
11. Tilmann Gneiting and Adrian E. Raftery. 2007. Strictly proper scoring rules, prediction, and estimation. J. Amer. Statist. Assoc. 102, 477 (2007), 359--378.
12. Harold V. Henderson and Shayle R. Searle. 1981. The vec-permutation matrix, the vec operator and Kronecker products: A review. Linear Multilinear Algebra 9, 4 (1981), 271--288.
13. Radu Jurca and Boi Faltings. 2007. Collusion-resistant, incentive-compatible feedback payments. In Proceedings of the 8th ACM Conference on Electronic Commerce. ACM, 200--209.
14. Radu Jurca and Boi Faltings. 2009. Mechanisms for making crowds truthful. J. Artif. Int. Res. 34, 1 (Mar. 2009).
15. Vijay Kamble, Nihar Shah, David Marn, Abhay Parekh, and Kannan Ramachandran. 2015. Truth serums for massively crowdsourced evaluation tasks. arXiv preprint arXiv:1507.07045 (2015).
16. Yuqing Kong, Katrina Ligett, and Grant Schoenebeck. 2016. Putting peer prediction under the micro (economic) scope and making truth-telling focal. In Proceedings of the International Conference on Web and Internet Economics. Springer, 251--264.
17. Y. Kong and G. Schoenebeck. 2016. A framework for designing information elicitation mechanisms that reward truth-telling. ArXiv e-prints. arxiv:cs.GT/1605.01021
18. Yuqing Kong and Grant Schoenebeck. 2018b. Eliciting expertise without verification. In Proceedings of the ACM Conference on Economics and Computation. ACM, 195--212.
19. Yuqing Kong and Grant Schoenebeck. 2018a. Equilibrium selection in information elicitation without verification via information monotonicity. In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science (ITCS’18), Vol. 94.
20. Yuqing Kong and Grant Schoenebeck. 2018c. Water from two rocks: Maximizing the mutual information. In Proceedings of the ACM Conference on Economics and Computation. ACM, 177--194.
21. Friedrich Liese and Igor Vajda. 2006. On divergences and informations in statistics and information theory. IEEE Trans. Info. Theory 52, 10 (2006), 4394--4412.
22. Yang Liu and Yiling Chen. 2017. Machine-learning aided peer prediction. In Proceedings of the ACM Conference on Economics and Computation (EC’17). ACM, New York, NY, 63--80.
23. Yang Liu and Yiling Chen. 2018. Surrogate scoring rules and a dominant truth serum for information elicitation. CoRR abs/1802.09158 (2018). arxiv:1802.09158. Retrieved from http://arxiv.org/abs/1802.09158.
24. Debmalya Mandal, Matthew Leifer, David C. Parkes, Galen Pickard, and Victor Shnayder. 2016. Peer prediction with heterogeneous tasks. arXiv preprint arXiv:1612.00928 (2016).
25. N. Miller, P. Resnick, and R. Zeckhauser. 2005. Eliciting informative feedback: The peer-prediction method. Manage. Sci. 51, 9 (2005), 1359--1373.
26. D. Prelec. 2004. A Bayesian truth serum for subjective data. Science 306, 5695 (2004), 462--466.
27. Goran Radanovic and Boi Faltings. 2013. A robust Bayesian truth serum for non-binary signals. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI’13). 833--839.
28. Goran Radanovic and Boi Faltings. 2014. Incentives for truthful information elicitation of continuous signals. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI’14).
29. Goran Radanovic and Boi Faltings. 2015. Incentive schemes for participatory sensing. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1081--1089.
30. Blake Riley. 2014. Minimum truth serums with optional predictions. In Proceedings of the 4th Workshop on Social Computing and User Generated Content (SC’14).
31. William E. Roth. 1934. On direct product matrices. Bull. Amer. Math. Soc. 40, 6 (1934), 461--468.
32. Victor Shnayder, Arpit Agarwal, Rafael Frongillo, and David C. Parkes. 2016. Informed truthfulness in multi-task peer prediction. In Proceedings of the 2016 ACM Conference on Economics and Computation (EC’16). ACM, New York, NY, 179--196.
33. Robert L. Winkler. 1969. Scoring rules and the evaluation of probability assessors. J. Amer. Statist. Assoc. 64, 327 (1969), 1073--1078.
34. Jens Witkowski. 2014. Robust Peer Prediction Mechanisms. Ph.D. Dissertation. Department of Computer Science, Albert-Ludwigs-Universität Freiburg.
35. Jens Witkowski, Pavel Atanasov, Lyle H. Ungar, and Andreas Krause. 2017. Proper proxy scoring rules. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI’17). 743--749.
36. J. Witkowski and D. Parkes. 2012. A robust Bayesian truth serum for small populations. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI’12).
37. Peter Zhang and Yiling Chen. 2014. Elicitability and knowledge-free elicitation with peer prediction. In Proceedings of the International Conference on Autonomous Agents and Multi-agent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 245--252.

Index Terms

• Mathematics of computing

  • Information theory

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Algorithmic mechanism design