Accuracy for Sale
Authors:
Open Access
- 11 January 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 317-324
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.Keywords
Funding Information
- National Science Foundation (CCF-1101389, CNS-1065060, CNS-1253345, CNS-1254169)
- United States - Israel Binational Agricultural Research and Development Fund (2012348)
- Microsoft Faculty Fellowship
- Google Faculty Research Award
- Charles Lee Powell Foundation
This publication has 17 references indexed in Scilit:
- Budget Feasible Mechanisms for Experimental DesignLecture Notes in Computer Science, 2014
- Privacy and coordination2013
- Approximately optimal auctions for selling privacy when costs are correlated with data2012
- Truthful and Near-Optimal Mechanism Design via Linear ProgrammingJournal of the ACM, 2011
- On the Power of Randomization in Algorithmic Mechanism Design2009
- Limitations of VCG-based mechanisms2007
- Calibrating Noise to Sensitivity in Private Data Analysis2006
- Optimal Design of Experiments2006
- Convex Optimization2004
- Characterization of Satisfactory Mechanisms for the Revelation of Preferences for Public GoodsEconometrica, 1977