Incentive Compatible Active Learning

Authors Federico Echenique , Siddharth Prasad



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.67.pdf
  • Filesize: 0.51 MB
  • 20 pages

Document Identifiers

Author Details

Federico Echenique
  • Division of the Humanities and Social Sciences, California Institute of Technology, Pasadena, CA, USA
Siddharth Prasad
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA

Cite AsGet BibTex

Federico Echenique and Siddharth Prasad. Incentive Compatible Active Learning. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 67:1-67:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.67

Abstract

We consider active learning under incentive compatibility constraints. The main application of our results is to economic experiments, in which a learner seeks to infer the parameters of a subject’s preferences: for example their attitudes towards risk, or their beliefs over uncertain events. By cleverly adapting the experimental design, one can save on the time spent by subjects in the laboratory, or maximize the information obtained from each subject in a given laboratory session; but the resulting adaptive design raises complications due to incentive compatibility. A subject in the lab may answer questions strategically, and not truthfully, so as to steer subsequent questions in a profitable direction. We analyze two standard economic problems: inference of preferences over risk from multiple price lists, and belief elicitation in experiments on choice over uncertainty. In the first setting, we tune a simple and fast learning algorithm to retain certain incentive compatibility properties. In the second setting, we provide an incentive compatible learning algorithm based on scoring rules with query complexity that differs from obvious methods of achieving fast learning rates only by subpolynomial factors. Thus, for these areas of application, incentive compatibility may be achieved without paying a large sample complexity price.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of learning
Keywords
  • Active Learning
  • Incentive Compatibility
  • Preference Elicitation

Metrics

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

References

  1. Jacob Abernethy, Yiling Chen, Chien-Ju Ho, and Bo Waggoner. Low-cost learning via active data procurement. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 619-636. ACM, 2015. Google Scholar
  2. David S. Ahn, Syngjoo Choi, Douglas Gale, and Shachar Kariv. Estimating Ambiguity Aversion in a Portfolio Choice Experiment. Quantitative Economics, 5(2):195-223, 2014. Google Scholar
  3. Steffen Andersen, Glenn W Harrison, Morten Igel Lau, and E Elisabet Rutström. Elicitation using multiple price list formats. Experimental Economics, 9(4):383-405, 2006. Google Scholar
  4. James Andreoni, Marco Castillo, and Ragan Petrie. What Do Bargainers' Preferences Look Like? Experiments with a Convex Ultimatum Game. American Economic Review, 93(3):672-685, 2003. Google Scholar
  5. James Andreoni and John Miller. Giving According to GARP: An Experimental Test of the Consistency of Preferences for Altruism. Econometrica, 70(2):737-753, 2002. Google Scholar
  6. Ned Augenblick, Muriel Niederle, and Charles Sprenger. Working over Time: Dynamic Inconsistency in Real Effort Tasks *. The Quarterly Journal of Economics, 130(3):1067-1115, May 2015. URL: https://doi.org/10.1093/qje/qjv020.
  7. Yaron Azrieli, Christopher P Chambers, and Paul J Healy. Incentives in experiments: A theoretical analysis. Journal of Political Economy, 126(4):1472-1503, 2018. Google Scholar
  8. Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-89, 2009. Google Scholar
  9. Maria-Florina Balcan, Amit Daniely, Ruta Mehta, Ruth Urner, and Vijay V Vazirani. Learning economic parameters from revealed preferences. In International Conference on Web and Internet Economics, pages 338-353. Springer, 2014. Google Scholar
  10. Pathikrit Basu. Learnability and Stochastic Choice. SSRN 3338991, 2019. Google Scholar
  11. Pathikrit Basu and Federico Echenique. Learnability and Models of Decision Making under Uncertainty. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 53-53. ACM, 2018. Google Scholar
  12. Eyal Beigman and Rakesh Vohra. Learning from revealed preference. In Proceedings of the 7th ACM Conference on Electronic Commerce, pages 36-42. ACM, 2006. Google Scholar
  13. Hans P Binswanger. Attitudes toward risk: Theoretical implications of an experiment in rural India. The Economic Journal, 91(364):867-890, 1981. Google Scholar
  14. Christopher P Chambers and Federico Echenique. Spherical Preferences. arXiv preprint, 2019. URL: http://arxiv.org/abs/1905.02917.
  15. Christopher P Chambers and Nicholas S Lambert. Dynamic belief elicitation, 2017. Google Scholar
  16. Jonathan Chapman, Erik Snowberg, Stephanie Wang, and Colin Camerer. Loss Attitudes in the US Population: Evidence from Dynamically Optimized Sequential Experimentation (DOSE). Technical report, National Bureau of Economic Research, 2018. Google Scholar
  17. Zachary Chase and Siddharth Prasad. Learning Time Dependent Choice. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  18. Yiling Chen, Chara Podimata, Ariel D Procaccia, and Nisarg Shah. Strategyproof linear regression in high dimensions. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 9-26. ACM, 2018. Google Scholar
  19. Syngjoo Choi, Raymond Fisman, Douglas Gale, and Shacher Kariv. Consistency and Heterogeneity of Individual Behavior under Uncertainty. American Economic Review, 97(5):1921-1938, 2007. Google Scholar
  20. Vincent Conitzer. Prediction markets, mechanism design, and cooperative game theory. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 101-108. AUAI Press, 2009. Google Scholar
  21. Sanjoy Dasgupta. Two faces of active learning. Theoretical computer science, 412(19):1767-1781, 2011. Google Scholar
  22. Ofer Dekel, Felix Fischer, and Ariel D Procaccia. Incentive compatible regression learning. Journal of Computer and System Sciences, 76(8):759-777, 2010. Google Scholar
  23. Mahmoud A El-Gamal, Richard D McKelvey, and Thomas R Palfrey. A Bayesian sequential experimental study of learning in games. Journal of the American Statistical Association, 88(422):428-435, 1993. Google Scholar
  24. Daniel Friedman. Effective scoring rules for probabilistic forecasts. Management Science, 29(4):447-454, 1983. Google Scholar
  25. Daniel Friedman, Sameh Habib, Duncan James, and Sean Crockett. Varieties of Risk Elicitation. Unpublished manuscript, 2018. Google Scholar
  26. Steve Hanneke. A bound on the label complexity of agnostic active learning. In Proceedings of the 24th international conference on Machine learning, pages 353-360. ACM, 2007. Google Scholar
  27. Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science (STOC), pages 111-122. ACM, 2016. Google Scholar
  28. Charles A Holt and Susan K Laury. Risk aversion and incentive effects. American economic review, 92(5):1644-1655, 2002. Google Scholar
  29. Taisuke Imai and Colin F Camerer. Estimating Time Preferences from Budget Set Choices Using Optimal Adaptive Design. Technical report, Caltech Working Paper, 2016. Google Scholar
  30. Gil Kalai. Learnability and rationality of choice. Journal of Economic theory, 113(1):104-117, 2003. Google Scholar
  31. Yang Liu and Yiling Chen. Machine-learning aided peer prediction. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 63-80. ACM, 2017. Google Scholar
  32. Debajyoti Ray, Daniel Golovin, Andreas Krause, and Colin Camerer. Bayesian rapid optimal adaptive design (broad): Method and application distinguishing models of risky choice. California Institute of Technology working paper, 2012. Google Scholar
  33. Leonard J Savage. The foundations of statistics. Courier Corporation, 1972. Google Scholar
  34. John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior (commemorative edition). Princeton university press, 1953. Google Scholar
  35. Morteza Zadimoghaddam and Aaron Roth. Efficiently learning from revealed preference. In International Workshop on Internet and Network Economics, pages 114-127. Springer, 2012. 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