← 研踪 PaperTrailarXiv:2611.25988 · v1
Sequential Contract Design for Budgeted Crowdsourcing
首次提交 2026-11-19 20:10
版本更新 2026-11-19 20:10
雷达观测 2026-11-20 16:53
摘要
A principal wishes to crowdsource a collection of tasks under a fixed compensation budget. The quality of a task's outcome is stochastic and depends on the worker's effort level. Since this effort is unobservable, the principal offers contracts to workers specifying their compensation for each possible outcome. The principal offers these contracts sequentially, using previously observed outcomes and payments to decide whom to approach next and what contract to offer. The objective is to maximize the expected value of the work produced while ensuring that total payments never exceed the budget, regardless of the realized outcomes. Contract design must therefore account both for a worker's incentives and for the budget available to incentivize others. For valuations that are additive across tasks, we characterize how the approximability of the optimal adaptive policy depends on the numbers of workers, effort levels, and outcomes. Polynomial-time constant-factor approximation is possible whenever the number of workers, effort levels per worker, or outcomes per task is constant, but impossible in general when all three are unrestricted, unless . We obtain tight guarantees for every fixed number of workers, establish computational hardness even in restricted settings, and obtain exact algorithms and approximation schemes in more structured settings. We also investigate simple contract structures, demonstrating both the benefits of adapting contracts to previous outcomes and the limitations of local contract rules, while identifying conditions under which a local policy achieves a constant-factor guarantee. Finally, we extend our analysis beyond additive valuations, obtaining constant-factor approximations for monotone submodular valuations with binary outcomes, including guarantees against a stronger full-knowledge benchmark under additional assumptions.
作者备注:37 pages
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-19 20:10 · 最新观测版本
Sequential Contract Design for Budgeted Crowdsourcing
A principal wishes to crowdsource a collection of tasks under a fixed compensation budget. The quality of a task's outcome is stochastic and depends on the worker's effort level. Since this effort is unobservable, the principal offers contracts to workers specifying their compensation for each possible outcome. The principal offers these contracts sequentially, using previously observed outcomes and payments to decide whom to approach next and what contract to offer. The objective is to maximize the expected value of the work produced while ensuring that total payments never exceed the budget, regardless of the realized outcomes. Contract design must therefore account both for a worker's incentives and for the budget available to incentivize others. For valuations that are additive across tasks, we characterize how the approximability of the optimal adaptive policy depends on the numbers of workers, effort levels, and outcomes. Polynomial-time constant-factor approximation is possible whenever the number of workers, effort levels per worker, or outcomes per task is constant, but impossible in general when all three are unrestricted, unless . We obtain tight guarantees for every fixed number of workers, establish computational hardness even in restricted settings, and obtain exact algorithms and approximation schemes in more structured settings. We also investigate simple contract structures, demonstrating both the benefits of adapting contracts to previous outcomes and the limitations of local contract rules, while identifying conditions under which a local policy achieves a constant-factor guarantee. Finally, we extend our analysis beyond additive valuations, obtaining constant-factor approximations for monotone submodular valuations with binary outcomes, including guarantees against a stronger full-knowledge benchmark under additional assumptions.
查看此版本解读 →查看此版本原文 ↗