A winners-take-all incentive mechanism for crowd-powered systems

This paper studies incentive mechanisms for crowd-powered systems, including applications such as collection of personal data for big-data analytics and crowdsourcing. In big-data analytics using personal data, an individual may control the quality of reported data via a privacy-preserving mechanism that randomizes the answer. In crowdsourcing, the quality of the reported answer depends on the amount of effort spent by a worker or a team. In these applications, incentive mechanisms are critical for eliciting data/answers with target quality. This paper focuses the following two fundamental questions: what is the minimum payment required to incentivize an individual to submit a data/answer with quality level ∈? and what incentive mechanisms can achieve the minimum payment? Let ∈ _i denote the quality of the data/answer reported by individual i: In this paper, we first derive a lower bound on the minimum amount of payment required for guaranteeing quality level ∈ _i : Inspired by the lower bound, we propose an incentive mechanism, named Winners-Take-All (WINTALL). WINTALL first decides a winning answer based on the reported data, cost functions of individuals, and some prior distribution; and then pays to individuals whose reported data match the winning answer. Under some assumptions, we show that the expected payment of WINTALL matches the lower bound. In the application of private discrete distribution estimation, we show that WINTALL simply rewards individuals whose reported answers match the most popular answer from the reported ones (the prior distribution is not needed in this case).