More Web Proxy on the site http://driver.im/

research-article

Public Access

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

Authors:

Grant SchoenebeckAuthors Info & Claims

ACM Transactions on Economics and Computation (TEAC), Volume 7, Issue 1

Article No.: 2, Pages 1 - 33

https://doi.org/10.1145/3296670

Published: 25 January 2019 Publication History

All formats PDF

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[14]

Radu Jurca and Boi Faltings. 2009. Mechanisms for making crowds truthful. J. Artif. Int. Res. 34, 1 (Mar. 2009).

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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).

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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).

Digital Library

[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.

Digital Library

Cited By

Humayun HMalik MGhazali M(2024)Analysis of Motivational Theories in Crowdsourcing Using Long Tail Theory: A Systematic Literature ReviewInternational Journal of Crowd Science10.26599/IJCS.2023.91000108:1(10-27)Online publication date: Feb-2024
https://doi.org/10.26599/IJCS.2023.9100010
Kong Y(2024)Dominantly Truthful Peer Prediction Mechanisms with a Finite Number of TasksJournal of the ACM10.1145/363823971:2(1-49)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3638239
Xu SZhang YResnick PSchoenebeck GChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Spot Check Equivalence: An Interpretable Metric for Information Elicitation MechanismsProceedings of the ACM Web Conference 202410.1145/3589334.3645679(276-287)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645679
Show More Cited By

Index Terms

An Information Theoretic Framework For Designing Information Elicitation Mechanisms That Reward Truth-telling
1. Mathematics of computing
  1. Information theory
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Algorithmic mechanism design

Recommendations

Crowdsourced judgement elicitation with endogenous proficiency
WWW '13: Proceedings of the 22nd international conference on World Wide Web

Crowdsourcing is now widely used to replace judgement or evaluation by an expert authority with an aggregate evaluation from a number of non-experts, in applications ranging from rating and categorizing online content all the way to evaluation of ...
Putting Peer Prediction Under the Microeconomicscope and Making Truth-Telling Focal
WINE 2016: Proceedings of the 12th International Conference on Web and Internet Economics - Volume 10123

Peer-predictionï ź[19] is a meta-mechanism which, given any proper scoring rule, produces a mechanism to elicit prie information from self-interested agents. Formally, truth-telling is a strict Nash equilibrium of the mechanism. Unfortunately, there may ...
Multi-dimensional mechanism design with limited information
EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

We analyze a nonlinear pricing model with limited information. Each buyer can purchase a large variety, d, of goods. His preference for each good is represented by a scalar and his preference over d goods is represented by a d-dimensional vector. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Economics and Computation

ACM Transactions on Economics and Computation Volume 7, Issue 1

February 2019

123 pages

ISSN:2167-8375

EISSN:2167-8383

DOI:10.1145/3309879

Editors:
David Pennock
Microsoft
,
Ilya Segal
Stanford University

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 January 2019

Accepted: 01 October 2018

Revised: 01 June 2018

Received: 01 January 2018

Published in TEAC Volume 7, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
1,375
Total Downloads

Downloads (Last 12 months)326
Downloads (Last 6 weeks)31

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Humayun HMalik MGhazali M(2024)Analysis of Motivational Theories in Crowdsourcing Using Long Tail Theory: A Systematic Literature ReviewInternational Journal of Crowd Science10.26599/IJCS.2023.91000108:1(10-27)Online publication date: Feb-2024
https://doi.org/10.26599/IJCS.2023.9100010
Kong Y(2024)Dominantly Truthful Peer Prediction Mechanisms with a Finite Number of TasksJournal of the ACM10.1145/363823971:2(1-49)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3638239
Xu SZhang YResnick PSchoenebeck GChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Spot Check Equivalence: An Interpretable Metric for Information Elicitation MechanismsProceedings of the ACM Web Conference 202410.1145/3589334.3645679(276-287)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645679
Shan LZhang SZhang JWang ZChua TNgo CKa-Wei Lee RKumar RLauw H(2024)On Truthful Item-Acquiring Mechanisms for Reward MaximizationProceedings of the ACM Web Conference 202410.1145/3589334.3645345(25-35)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645345
Chen KHuang CHuang J(2023)Information Elicitation from Decentralized Crowd Without Verification2023 21st International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt)10.23919/WiOpt58741.2023.10349884(1-8)Online publication date: 24-Aug-2023
https://doi.org/10.23919/WiOpt58741.2023.10349884
Kamble VShah NMarn DParekh ARamchandran K(2023)The Square Root Agreement Rule for Incentivizing Truthful Feedback on Online PlatformsManagement Science10.1287/mnsc.2022.437569:1(377-403)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1287/mnsc.2022.4375
Liu YLou RWei J(2023)Auditing for Federated Learning: A Model Elicitation ApproachProceedings of the Fifth International Conference on Distributed Artificial Intelligence10.1145/3627676.3627683(1-9)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3627676.3627683
Burrell NSchoenebeck GLeyton-Brown KSamuelson LHartline J(2023)Measurement Integrity in Peer Prediction: A Peer Assessment Case StudyProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597744(369-389)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597744
Schoenebeck GYu F(2023)Two Strongly Truthful Mechanisms for Three Heterogeneous Agents Answering One QuestionACM Transactions on Economics and Computation10.1145/356556010:4(1-26)Online publication date: 21-Feb-2023
https://dl.acm.org/doi/10.1145/3565560
Liu YWang JChen Y(2023)Surrogate Scoring RulesACM Transactions on Economics and Computation10.1145/356555910:3(1-36)Online publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1145/3565559
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents