License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.67
URN: urn:nbn:de:0030-drops-117525
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11752/
Go to the corresponding LIPIcs Volume Portal

Echenique, Federico ; Prasad, Siddharth

Incentive Compatible Active Learning

pdf-format:
LIPIcs-ITCS-2020-67.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{echenique_et_al:LIPIcs:2020:11752,
  author =	{Federico Echenique and Siddharth Prasad},
  title =	{{Incentive Compatible Active Learning}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{67:1--67:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Thomas Vidick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11752},
  URN =		{urn:nbn:de:0030-drops-117525},
  doi =		{10.4230/LIPIcs.ITCS.2020.67},
  annote =	{Keywords: Active Learning, Incentive Compatibility, Preference Elicitation}
}

Keywords: Active Learning, Incentive Compatibility, Preference Elicitation
Collection: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Issue Date: 2020
Date of publication: 06.01.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI