Adaptive contract design for crowdsourcing markets: bandit algorithms for repeated principal-agent problems

DOI10.1613/JAIR.4940MaRDI QIDQ3467653zbMATH OpenOpenAlexWikidataFDO

Authors Chien-Ju Ho, Aleksandrs Slivkins, Jennifer Wortman Vaughan

Publication date 4 February 2016

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.2875

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Agent technology and artificial intelligence (68T42)

Abstract: Crowdsourcing markets have emerged as a popular platform for matching available workers with tasks to complete. The payment for a particular task is typically set by the task's requester, and may be adjusted based on the quality of the completed work, for example, through the use of "bonus" payments. In this paper, we study the requester's problem of dynamically adjusting quality-contingent payments for tasks. We consider a multi-round version of the well-known principal-agent model, whereby in each round a worker makes a strategic choice of the effort level which is not directly observable by the requester. In particular, our formulation significantly generalizes the budget-free online task pricing problems studied in prior work. We treat this problem as a multi-armed bandit problem, with each "arm" representing a potential contract. To cope with the large (and in fact, infinite) number of arms, we propose a new algorithm, AgnosticZooming, which discretizes the contract space into a finite number of regions, effectively treating each region as a single arm. This discretization is adaptively refined, so that more promising regions of the contract space are eventually discretized more finely. We analyze this algorithm, showing that it achieves regret sublinear in the time horizon and substantially improves over non-adaptive discretization (which is the only competing approach in the literature). Our results advance the state of art on several different topics: the theory of crowdsourcing markets, principal-agent problems, multi-armed bandits, and dynamic pricing.

Recommendations

• Efficient crowdsourcing of unknown experts using bounded multi-armed bandits
• Efficient crowdsourcing of unknown experts using multi-armed bandits
• Learning approximately optimal contracts
• Optimal crowdsourcing contests
• Optimal crowdsourcing contests

Cited in

(19)

• Designing menus of contracts efficiently: the power of randomization
• More for less: adaptive labeling payments in online labor markets
• The complexity of contracts
• An optimal bidimensional multi-armed bandit auction for multi-unit procurement
• On improved interval cover mechanisms for crowdsourcing markets
• A quality assuring, cost optimal multi-armed bandit mechanism for expertsourcing
• Robustness and approximation for the linear contract design
• Bayesian exploration: incentivizing exploration in Bayesian games
• Learning approximately optimal contracts
• Competing bandits: learning under competition
• Bayesian Incentive-Compatible Bandit Exploration
• A differential privacy mechanism that accounts for network effects for crowdsourcing systems
• Incentivizing exploration with heterogeneous value of money
• Efficient crowdsourcing of unknown experts using multi-armed bandits
• Efficient crowdsourcing of unknown experts using bounded multi-armed bandits
• Learning approximately optimal contracts
• An \(\alpha \)-regret analysis of adversarial bilateral trade
• Principal-agent problem under the linear contract
• Bayesian agency: linear versus tractable contracts

This page was built for publication: Adaptive contract design for crowdsourcing markets: bandit algorithms for repeated principal-agent problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3467653)