Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems

摘要

Crowdsourcing markets have emerged as a popular platform for matchingavailable workers with tasks to complete. The payment for a particular task istypically set by the task's requester, and may be adjusted based on the qualityof the completed work, for example, through the use of "bonus" payments. Inthis paper, we study the requester's problem of dynamically adjustingquality-contingent payments for tasks. We consider a multi-round version of thewell-known principal-agent model, whereby in each round a worker makes astrategic choice of the effort level which is not directly observable by therequester. In particular, our formulation significantly generalizes thebudget-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, whichdiscretizes the contract space into a finite number of regions, effectivelytreating each region as a single arm. This discretization is adaptivelyrefined, so that more promising regions of the contract space are eventuallydiscretized more finely. We analyze this algorithm, showing that it achievesregret sublinear in the time horizon and substantially improves overnon-adaptive discretization (which is the only competing approach in theliterature). Our results advance the state of art on several different topics: the theoryof crowdsourcing markets, principal-agent problems, multi-armed bandits, anddynamic pricing.