Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Information Gathering with Peers: Submodular Optimization with Peer-Prediction Constraints


Singla,  Adish
Group A. Singla, Max Planck Institute for Software Systems, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 693KB

Supplementary Material (public)
There is no public supplementary material available

Radanovic, G., Singla, A., Krause, A., & Faltings, B. (2017). Information Gathering with Peers: Submodular Optimization with Peer-Prediction Constraints. Retrieved from http://arxiv.org/abs/1711.06740.

Cite as: https://hdl.handle.net/21.11116/0000-0000-EEC3-8
We study a problem of optimal information gathering from multiple data providers that need to be incentivized to provide accurate information. This problem arises in many real world applications that rely on crowdsourced data sets, but where the process of obtaining data is costly. A notable example of such a scenario is crowd sensing. To this end, we formulate the problem of optimal information gathering as maximization of a submodular function under a budget constraint, where the budget represents the total expected payment to data providers. Contrary to the existing approaches, we base our payments on incentives for accuracy and truthfulness, in particular, {\em peer-prediction} methods that score each of the selected data providers against its best peer, while ensuring that the minimum expected payment is above a given threshold. We first show that the problem at hand is hard to approximate within a constant factor that is not dependent on the properties of the payment function. However, for given topological and analytical properties of the instance, we construct two greedy algorithms, respectively called PPCGreedy and PPCGreedyIter, and establish theoretical bounds on their performance w.r.t. the optimal solution. Finally, we evaluate our methods using a realistic crowd sensing testbed.