Tutorial: Eliciting High-Quality Information

AI systems often depend on information provided by other agents, for example sensor data or crowdsourced human computation. Usually, providing accurate and relevant data requires costly effort that agents may not always be willing to provide. Thus, it becomes important both to verify the correctness of data, but also to provide incentives so that agents that provide high-quality data are rewarded while those that do not are discouraged by low rewards.

We will cover different settings and the assumptions they admit, including sensing, human computation, peer grading, reviews and predictions. We will survey different incentive mechanisms, including proper scoring rules, prediction markets and peer prediction, Bayesian Truth Serum, Peer Truth Serum, and the settings where each of them would be suitable. As an alternative, we also consider reputation mechanisms. We complement the game-theoretic analysis with practical examples of applications in prediction platforms, community sensing and peer grading.



Content

The tutorial addresses two basic types of information elicitation scenarios that are relevant for the AI audience.

In the first scenario, we study the elicitation process of fully or partially verifiable information, as in forecasting or crowdsourcing with gold standard tasks. We show how to elicit predictions about a future event from multiple individuals, either explicitly by using strictly proper scoring rules, or implicitly by using a prediction market approach or a reputation based approach.

In the second scenario, we investigate how to elicit information that cannot be directly verified, such as product reviews or sensor measurements in crowd-sensing. We show the range of peer-consistency-based methods that have been developed over the past years, and several examples that show how they work in real scenarios.

Throughout the tutorial, we present three types of material: specific mechanisms, game-theoretic analysis of these mechanisms, and experience with practical application. The tentative schedule of the tutorial is:

  1. Introduction
    1. Motivation and practical scenarios
    2. Quality control approaches
    3. Formal setting
  2. Eliciting verifiable information
    1. Basic incentive mechanisms
    2. Proper scoring rules
    3. Prediction markets with market makers
    4. Reputation based approach: the influence limiter
  3. Eliciting unverifiable information
    1. Output agreement
    2. Peer-prediction
    3. The shadowing method and the peer truth serum
    4. The peer truth serum for crowdsourcing
    5. Overview of other techniques, e.g. Bayesian Truth Serums
  4. Open questions



Presenters

Boi Faltings

Boi Faltings is a full professor at the Swiss Federal Institute of Technology in Lausanne (EPFL) and has worked in AI since 1983, and has been one of the pioneers on the topic of mechanisms for truthful information elicitation, with the first work dating back to 2003. He has taught AI and multi-agent systems to students at EPFL for 28 years. He is a fellow of AAAI and ECCAI and an area chair of IJCAI-16, and served as tutorial chair of IJCAI-13.

Goran Radanovic

Goran Radanovic is a Ph.D. student at the Swiss Federal Institute of Technology in Lausanne (EPFL) and has worked on the topic of mechanisms for information elicitation since 2011. His work has been published mainly at AI conferences. He has participated in the teaching of a course on multi-agent systems since 2012.



Material

To access the tutorial slides, click on the download button:



References

  1. Berg J., and Rietz T. 2006. The Iowa Electronic Markets: Stylized Facts and Open Issues. In Information Markets: A New Way of Making Decisions.
  2. Buchegger S., and Le Boudec J.-Y. 2003. A robust reputation system for mobile ad-hoc networks. Technical report, Proceedings of P2PEcon.
  3. Chen Y., and David P. 2007. A utility framework for bounded-loss market makers. In Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence (UAI2007).
  4. Dasgupta A., and Ghosh A. 2013. Crowdsourced judgement elicitation with endogenous proficiency. In Proceedings of the 22nd ACM International World Wide Web Conference (WWW’13).
  5. Faltings B., Li J., and Jurca R. 2014. Incentive Mechanisms for Community Sensing. IEEE Transactions on Computers, 63(1):115-128.
  6. Faltings B., Pu P., Tran B. D., and Jurca R. 2014 Incentives to Counter Bias in Human Computation. In Proceedings of AAAI Conference on Human Computation and Crowdsourcing (HCOMP'14).
  7. Frongillo R., Chen Y., and Kash I. 2015. Elicitation for Aggregation. In Proceedings of the 29th AAAI Conference on Artificial Intelligence
  8. Frongillo R., and Kash I. 2014. General truthfulness characterizations via convex analysis. In Web and Internet Economics.
  9. Frongillo R., and Witkowski J. 2016. A Geometric Method to Construct Minimal Peer Prediction Mechanisms. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI’16).
  10. Garcin F., and Faltings B. 2014. Swissnoise: online polls with game-theoretic incentives. In Proceedings of the 26th Conference on Innovative Applications of AI.
  11. Gneiting T., and Raftery A. 2007. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102:359–378.
  12. Hanson R. 2007. Logarithmic market scoring rules for modular combinatorial information aggregation. Journal of Prediction Markets, 1(1): 1-15.
  13. Huang K., Kanhere S, and Hu W. 2014. On the need for a reputation system in mobile phone based sensing. Ad Hoc Networks.
  14. Josang A., and Ismail R. 2002. The beta reputation system. In Proceedings of the Electronic Commerce Conference.
  15. Jurca R., and Faltings B. 2006. Minimum payments that reward honest reputation feedback. In Proceedings of the 7th ACM Conference on Electronic Commerce (EC’06), 190–199.
  16. Jurca R., Binder W. and Faltings B. 2007. Reliable QoS monitoring based on client feedback. In Proceedings of the 16th International World Wide Web Conference (WWW'07).
  17. Jurca R., and Faltings B. 2011. Incentives for answering hypothetical questions. In Workshop on Social Computing and User Generated Content (EC-11).
  18. Jurca R., and Faltings B. 2009. Mechanisms for making crowds truthful. Journal of Artificial Intelligence Research (JAIR), 34, 209-253.
  19. Kamble V., Shah N., Marn D., Parekh A., and Ramachandran K. 2015. Truth serums for massively crowdsourced evaluation tasks. CoRR abs/1507.07045.
  20. Kong Y., Schoenebeck G., and Ligett K. 2016. Putting peer prediction under the micro(economic)scope and making truth-telling focal. CoRR:abs/1603.07319.
  21. Kong Y., and Schoenebeck G. 2016. Equilibrium selection in information elicitation without verification via information monotonicity. CoRR: abs/1603.07751.
  22. Kong Y., and Schoenebeck G. 2016. A framework for designing information elicitation mechanisms that reward truth-telling. CoRR: abs/1605.01021.
  23. Lambert N., Pennock D., and Shoham Y. 2008. Eliciting properties of probability distributions. In Proceedings of the 9th ACM Conference on Electronic Commerce.
  24. Lambert N., and Shoham Y. 2009. Eliciting truthful answers to multiple-choice questions. In Proceedings of the 10th ACM conference on Electronic commerce.
  25. Miller N., Resnick P., and Zeckhauser R. 2005. Eliciting informative feedback: the peer prediction method. Management Science, 51:1359–1373.
  26. Prelec D. 2004. A bayesian truth serum for subjective data. Science, 34(5695): 462–466.
  27. Radanovic G., and Faltings B. 2013. A robust Bayesian truth serum for non-binary Signals. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI’13).
  28. Radanovic G., and Faltings B. 2014. Incentives for truthful information elicitation of continuous signals. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI'14).
  29. Radanovic G., and Faltings B. 2015. Incentives for subjective evaluations with private beliefs. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI'15).
  30. Radanovic G., and Faltings B. 2015. Incentive schemes for participatory sensing. In Proceedings of the 14th international conference on autonomous agents and multiagent systems (AAMAS'15).
  31. Radanovic G., and Faltings B. 2016. Limiting the influence of low quality information in community sensing. In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’16).
  32. Radanovic G., Faltings B, and Jurca R. 2016. Incentives for effort in crowdsourcing using the peer truth serum. ACM Transactions on Intelligent Systems and Technology, 7(4):48:1-48:28.
  33. Resnick P. and Sami R. 2007. The influence limiter: provably manipulation-resistant recommender systems. In Proceedings of the 2007 ACM Conference on Recommender Systems.
  34. Riley B. 2014. Minimum truth serums with optional predictions. The 4th Workshop on Social Computing and User Generated Content.
  35. Savage L. 1971. Elicitation of personal probabilities and expectations. Journal of the American Statistical Association, 66(336): 783–801.
  36. Shah N., Zhou D., and Peres Y. 2015. Approval voting and incentives in crowdsourcing. In Proceedings of the 32nd International Conference on Machine Learning (ICML’15).
  37. Shah N., and Zhou D. 2015. Double or nothing: Multiplicative incentive mechanisms for crowdsourcing. In Advances in Neural Information Processing Systems (NIPS'15).
  38. Shaw A., Chen L., and Horton J. 2011. Designing incentives for inexpert human raters. In Proceedings of the ACM 2011 Conference on Computer Supported Cooperative Work (CSCW 11).
  39. Shnayder V., Agarwal A., Frongillo R., and Parkes D. 2016. Informed truthfulness in multi-task peer prediction. Corr:abs/1603.03151.
  40. Shnayder V., Frongillo R., and Parkes D. 2016. Measuring performance of peer prediction mechanisms using replicator dynamics. In Proceedings of the25th International Joint Conference on Artificial Intelligence (IJCAI'16).
  41. Ugander J., Drapeau R. and Guestrin C. 2015. The wisdom of multiple guesses. In Proceedings of the Sixteenth ACM Conference on Economics and Computation.
  42. von Ahn, L. and Dabbish, L.2004. Labeling images with a computer game. In Proc. SIGCHI Conf. on Human Factors in Computing Systems.
  43. von Ahn, L. and Dabbish, L. 2008. Designing games with a purpose. Communications of the ACM.
  44. Waggoner B., and Chen Y. 2014. Output agreement mechanisms and common knowledge. In Proceedings of the 2nd AAAI Conference on Human Computation and Crowdsourcing (HCOMP'14).
  45. Weaver R., and Prelec D. 2013. Creating truth-telling incentives with the bayesian truth serum. Journal of Marketing Research 50:289–302.
  46. Witkowski J., and Parkes D. 2012. A robust Bayesian truth serum for small populations. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI’12).
  47. Witkowski J., and Parkes D. 2012. Peer prediction without a common prior. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC’ 12).
  48. Witkowski J., and Parkes D. 2013. Learning the prior in minimal peer prediction. In Proceedings of the 3rd Workshop on Social Computing and User Generated Content (SC 2013).
  49. Witkowski J., Bachrach Y., Key P., and Parkes D. 2013. Dwelling on the negative: incentivizing effort in peer prediction. In Proceedings of the 1st AAAI Conference on Human Computation and Crowdsourcing.
  50. Zhang P., and Chen Y. 2014. Elicitability and knowledgefree elicitation with peer prediction. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems (AAMAS ’14).