Document Open Access Logo

Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity

Authors Yuqing Kong, Grant Schoenebeck

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.13.pdf
  • Filesize: 2.84 MB
  • 20 pages

Document Identifiers

Author Details

Yuqing Kong
Grant Schoenebeck

Cite As Get BibTex

Yuqing Kong and Grant Schoenebeck. Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.13

Abstract

In this paper, we propose a new mechanism - the Disagreement Mechanism - which elicits privately-held, non-variable information from self-interested agents in the single question (peer-prediction) setting.  

To the best of our knowledge, our Disagreement Mechanism is the first strictly truthful mechanism in the single-question setting that is simultaneously: 

- Detail-Free: does not need to know the common prior;
- Focal: truth-telling pays strictly higher than any other symmetric equilibria excluding some unnatural permutation equilibria;
- Small group: the properties of the mechanism hold even for a small number of agents, even in binary signal setting. Our mechanism only asks each agent her signal as well as a forecast of the other agents' signals.  

Additionally, we show that the focal result is both tight and robust, and we extend it to the case of asymmetric equilibria when the number of agents is sufficiently large.

Subject Classification

Keywords
  • peer prediction
  • equilibrium selection
  • information theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Arpit Agarwal, Debmalya Mandal, David C. Parkes, and Nisarg Shah. Peer prediction with heterogeneous users. In Constantinos Daskalakis, Moshe Babaioff, and Hervé Moulin, editors, Proceedings of the 2017 ACM Conference on Economics and Computation, EC '17, Cambridge, MA, USA, June 26-30, 2017, pages 81-98. ACM, 2017. URL: http://dx.doi.org/10.1145/3033274.3085127.
  2. Syed Mumtaz Ali and Samuel D Silvey. A general class of coefficients of divergence of one distribution from another. Journal of the Royal Statistical Society. Series B (Methodological), pages 131-142, 1966. Google Scholar
  3. S-I Amari and A Cichocki. Information geometry of divergence functions. Bulletin of the Polish Academy of Sciences: Technical Sciences, 58(1):183-195, 2010. Google Scholar
  4. Yang Cai, Constantinos Daskalakis, and Christos H Papadimitriou. Optimum statistical estimation with strategic data sources. arXiv preprint arXiv:1408.2539, 2014. Google Scholar
  5. Imre Csiszár, Paul C Shields, et al. Information theory and statistics: A tutorial. Foundations and Trendsregistered in Communications and Information Theory, 1(4):417-528, 2004. Google Scholar
  6. Anirban Dasgupta and Arpita Ghosh. Crowdsourced judgement elicitation with endogenous proficiency. In Proceedings of the 22nd international conference on World Wide Web, pages 319-330. International World Wide Web Conferences Steering Committee, 2013. Google Scholar
  7. Boi Faltings, Radu Jurca, Pearl Pu, and Bao Duy Tran. Incentives to counter bias in human computation. In Second AAAI Conference on Human Computation and Crowdsourcing, 2014. Google Scholar
  8. Rafael M Frongillo and Jens Witkowski. A geometric method to construct minimal peer prediction mechanisms. In AAAI, pages 502-508, 2016. Google Scholar
  9. Xi Alice Gao, Andrew Mao, Yiling Chen, and Ryan Prescott Adams. Trick or treat: putting peer prediction to the test. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 507-524. ACM, 2014. Google Scholar
  10. Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359-378, 2007. Google Scholar
  11. Radu Jurca and Boi Faltings. Collusion-resistant, incentive-compatible feedback payments. In Proceedings of the 8th ACM conference on Electronic commerce, pages 200-209. ACM, 2007. Google Scholar
  12. Radu Jurca and Boi Faltings. Mechanisms for making crowds truthful. J. Artif. Int. Res., 34(1), 2009. Google Scholar
  13. Vijay Kamble, Nihar Shah, David Marn, Abhay Parekh, and Kannan Ramachandran. Truth serums for massively crowdsourced evaluation tasks. arXiv preprint arXiv:1507.07045, 2015. Google Scholar
  14. Y. Kong and G. Schoenebeck. A Framework For Designing Information Elicitation Mechanisms That Reward Truth-telling. ArXiv e-prints, 2016. URL: http://arxiv.org/abs/1605.01021.
  15. Y. Kong and G. Schoenebeck. Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity. ArXiv e-prints, mar 2016. URL: http://arxiv.org/abs/1603.07751.
  16. Y. Kong, G. Schoenebeck, and K. Ligett. Putting Peer Prediction Under the Micro(economic)scope and Making Truth-telling Focal. ArXiv e-prints, mar 2016. URL: http://arxiv.org/abs/1603.07319.
  17. Yang Liu and Yiling Chen. Machine-learning aided peer prediction. In Constantinos Daskalakis, Moshe Babaioff, and Hervé Moulin, editors, Proceedings of the 2017 ACM Conference on Economics and Computation, EC '17, Cambridge, MA, USA, June 26-30, 2017, pages 63-80. ACM, 2017. URL: http://dx.doi.org/10.1145/3033274.3085126.
  18. Debmalya Mandal, Matthew Leifer, David C Parkes, Galen Pickard, and Victor Shnayder. Peer prediction with heterogeneous tasks. arXiv preprint arXiv:1612.00928, 2016. Google Scholar
  19. N. Miller, P. Resnick, and R. Zeckhauser. Eliciting informative feedback: The peer-prediction method. Management Science, pages 1359-1373, 2005. Google Scholar
  20. D. Prelec. A Bayesian Truth Serum for subjective data. Science, 306(5695):462-466, 2004. Google Scholar
  21. Goran Radanovic and Boi Faltings. A robust bayesian truth serum for non-binary signals. In Marie desJardins and Michael L. Littman, editors, Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA. Press, 2013. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI13/paper/view/6451.
  22. Goran Radanovic and Boi Faltings. Incentives for truthful information elicitation of continuous signals. In Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014. Google Scholar
  23. Goran Radanovic and Boi Faltings. Incentive schemes for participatory sensing. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pages 1081-1089. International Foundation for Autonomous Agents and Multiagent Systems, 2015. Google Scholar
  24. Blake Riley. Minimum truth serums with optional predictions. In Proceedings of the 4th Workshop on Social Computing and User Generated Content (SC14), 2014. Google Scholar
  25. V. Shnayder, A. Agarwal, R. Frongillo, and D. C. Parkes. Informed Truthfulness in Multi-Task Peer Prediction. ArXiv e-prints, mar 2016. URL: http://arxiv.org/abs/1603.03151.
  26. Jens Witkowski, Bernhard Nebel, and David C Parkes. Robust Peer Prediction Mechanisms. PhD thesis, Ph. D. Dissertation, Albert-Ludwigs-Universitat Freiburg: Institut fur Informatik, 2014. Google Scholar
  27. Jens Witkowski and David C. Parkes. A Robust Bayesian Truth Serum for Small Populations. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI 2012), 2011. Google Scholar
  28. Jens Witkowski and David C Parkes. Peer prediction without a common prior. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 964-981. ACM, 2012. Google Scholar
  29. Jens Witkowski and David C Parkes. Learning the prior in minimal peer prediction. In Proceedings of the 3rd Workshop on Social Computing and User Generated Content at the ACM Conference on Electronic Commerce, page 14. Citeseer, 2013. Google Scholar
  30. Peter Zhang and Yiling Chen. Elicitability and knowledge-free elicitation with peer prediction. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, pages 245-252. International Foundation for Autonomous Agents and Multiagent Systems, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact