Accuracy for sale: Aggregating data with a variance constraint

Rachel Cummings, Katrina Ligett, Aaron Roth, Zhiwei Steven Wu, Juba Ziani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

We consider the problem of a data analyst who may purchase an unbiased estimate of some statistic from multiple data providers. From each provider i, the analyst has a choice: she may purchase an estimate from that provider that has variance chosen from a finite menu of options. Each level of variance has a cost associated with it, reported (possibly strategically) by the data provider. The analyst wants to choose the minimum cost set of variance levels, one from each provider, that will let her combine her purchased estimators into an aggregate estimator that has variance at most some fixed desired level. Moreover, she wants to do so in such a way that incentivizes the data providers to truthfully report their costs to the mechanism. We give a dominant strategy truthful solution to this problem that yields an estimator that has optimal expected cost, and violates the variance constraint by at most an additive term that tends to zero as the number of data providers grows large.

Original languageEnglish (US)
Title of host publicationITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science
PublisherAssociation for Computing Machinery, Inc
Pages317-324
Number of pages8
ISBN (Electronic)9781450333337
DOIs
StatePublished - Jan 11 2015
Externally publishedYes
Event6th Conference on Innovations in Theoretical Computer Science, ITCS 2015 - Rehovot, Israel
Duration: Jan 11 2015Jan 13 2015

Publication series

NameITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science

Other

Other6th Conference on Innovations in Theoretical Computer Science, ITCS 2015
CountryIsrael
CityRehovot
Period1/11/151/13/15

Keywords

  • Buying data
  • Mechanism design
  • VCG mechanism

Fingerprint Dive into the research topics of 'Accuracy for sale: Aggregating data with a variance constraint'. Together they form a unique fingerprint.

Cite this