## 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 language | English (US) |
---|---|

Title of host publication | ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science |

Publisher | Association for Computing Machinery, Inc |

Pages | 317-324 |

Number of pages | 8 |

ISBN (Electronic) | 9781450333337 |

DOIs | |

State | Published - Jan 11 2015 |

Externally published | Yes |

Event | 6th Conference on Innovations in Theoretical Computer Science, ITCS 2015 - Rehovot, Israel Duration: Jan 11 2015 → Jan 13 2015 |

### Publication series

Name | ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science |
---|

### Other

Other | 6th Conference on Innovations in Theoretical Computer Science, ITCS 2015 |
---|---|

Country/Territory | Israel |

City | Rehovot |

Period | 1/11/15 → 1/13/15 |

### Bibliographical note

Publisher Copyright:Copyright © 2015 ACM.

## Keywords

- Buying data
- Mechanism design
- VCG mechanism