Source-linked AI summary
Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems
Chien-Ju Ho, Aleksandrs Slivkins, Jennifer Wortman Vaughan
TL;DR
The paper studies how a requester can learn quality-contingent contracts in repeated crowdsourcing interactions when workers’ effort is strategic and unobservable. It models contracts as bandit arms and introduces AgnosticZooming, which adaptively refines promising regions of the contract space. The algorithm achieves sublinear regret under favorable width-dimension conditions and improves over uniform discretization and prior pricing results.
Problem
The paper asks how requesters can dynamically set quality-contingent payments when worker types and effort choices are unobserved across repeated tasks.
Method
The paper models each potential contract as a bandit arm and uses AgnosticZooming to adaptively discretize and refine contract regions.
Results
AgnosticZooming achieves sublinear regret for small width dimension, with rate O(log T · T^(d+1)/(d+2)), and improves over uniform discretization and prior dynamic pricing results.
Takeaways & Limitations
The adaptive discretization approach provides regret guarantees for dynamic contract design without relying on Lipschitz-continuity assumptions.
Takeaways & Limitations
The analysis relies on worker-behavior assumptions to establish the width bound, although later developments require only the resulting lemma.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper formulates dynamic quality-contingent contracting in crowdsourcing as a repeated principal-agent problem with unobservable effort, and approaches it as a bandit problem over a large contract space. AgnosticZooming adaptively refines promising contract regions and achieves sublinear regret under a width-dimension condition.
- Crowdsourcing platforms match workers with requester-posted tasks, while quality-contingent bonuses can reward valuable output.
- The requester repeatedly posts contracts, observes output but not effort, updates payments, and seeks to maximize value from work minus payments.
- The problem is modeled as a multi-armed bandit in which each arm is a potential contract over a potentially infinite action space.
- AgnosticZooming partitions contracts into regions treated as meta-arms and adaptively refines more promising regions.
- Regret is sublinear for instances with small width dimension, with rate O(log T · T^(d+1)/(d+2)) after T rounds.
- The framework extends beyond prior single-price, budget-constrained pricing models and improves results for the accept-or-reject special case.
2 Our setting: the dynamic contract design problem
The setting extends the principal-agent model across rounds: each arriving worker strategically chooses unobservable effort under a posted contract, while the requester learns from observed outcomes. The requester optimizes expected utility relative to bounded, monotone candidate contracts, despite unknown worker types and benchmark limitations.
- Workers choose effort strategically, effort remains unobserved, and only the resulting outcome is observed before payment.
- A worker’s type consists of effort costs and outcome-production probabilities, and the requester observes neither the type nor a prior distribution.
- The dynamic model repeats a static requester-worker interaction with a new i.i.d. worker each round and an unknown supply distribution over types.
- The algorithm selects contracts to maximize requester utility, defined as the value of completed work minus expected payments, over candidate contracts.
- The benchmark restricts contracts to bounded monotone payments, but monotone contracts are not always optimal and discretization error may be difficult to bound generally.
- Worker-behavior assumptions are used to establish a natural monotonicity property: increasing an increment payment raises the probability of obtaining an outcome at least that good.
3 Our algorithm: AgnosticZooming
AgnosticZooming adaptively discretizes the contract increment space into active cells, selecting promising cells with confidence indices and refining them when uncertainty from sampling becomes smaller than discretization uncertainty. Its width proxy is justified by the worker-behavior structure.
- AgnosticZooming zooms into promising contract regions without requiring a precise similarity measure between contracts.
- Contracts are represented by nonnegative increment payments in [0,1]^m, and axis-aligned cubes in this increment space serve as cells.
- Composite cells use maximal and minimal corner contracts as anchors, while atomic cells use their unique candidate contract.
- Under FOSD and consistent tie-breaking, the true width of every composite cell is bounded by its virtual width.
- The algorithm maintains cells covering the increment space, chooses a cell by an upper-confidence index, samples an anchor, and activates relevant half-sized quadrants when it zooms.
- Zooming occurs when sampling uncertainty becomes sufficiently small relative to virtual width, and atomic cells are never refined.
4 Regret bounds and discussion
The paper develops a regret bound for AgnosticZooming based on width dimension and compares it with non-adaptive and similarity-aware bandit methods. The resulting bounds can improve substantially on worst-case discretization, while larger outcome spaces create exponential dependence.
- The main result: Theorem 4.1 bounds AgnosticZooming’s regret using candidate-contract near-optimality sets and feasible cells with sufficiently large virtual width.The bound is parameterized by Xcand and applies under the FOSD assumption with a constant number of outcomes.
- Discussion: Larger numbers of outcomes impose exponential dependence in the bound and typically generate exponentially many candidate policies for a fixed granularity.The analysis therefore targets settings with a small number of outcomes.
- Discussion: The regret bounds do not depend on the number of worker types because bandit guarantees depend on expected arm rewards, and sometimes their variance, rather than finer distributional details.This matches the paper’s comparison with prior dynamic-pricing work.
- Comparison to prior work: Worst-case corollaries show that AgnosticZooming has bounds comparable to NonAdaptive up to poly-logarithmic factors, while instance-specific bounds can be significantly better.The paper explicitly notes that Theorem 4.1 may substantially improve on the worst-case corollaries.
- Comparison to prior work: AgnosticZooming can match regret bounds for D-aware algorithms despite receiving no precise similarity metric between contracts.D-aware methods assume a function D satisfying |U(x) − U(y)| ≤ D(x,y), whereas this paper does not provide that information to the algorithm.
5 A special case: the “high-low example”
The high-low example reduces hidden-effort contract design to a structured pricing problem while retaining moral hazard. Under strongly Lipschitz-concave supply, adaptive discretization achieves lower regret than non-adaptive discretization.
- Dynamic task pricing: Adaptive discretization significantly improves prior dynamic task-pricing results, including the special case where workers only accept or reject a task.Dynamic task pricing uses a single price p for the non-null outcome and can have an arbitrary non-decreasing supply function S(p).
- The high-low example: In the high-low example, workers choose between low and high effort, but the requester observes only outcomes, making effort strategically hidden.Low effort deterministically produces low quality, while high effort can produce high quality at a worker-specific cost.
- Dynamic task pricing: The high-low model generalizes dynamic task pricing because dynamic pricing is recovered when high effort produces high outcome with probability one.The requester generally cannot assume the simplifying restriction x(low) = 0 because effort levels are unobservable.
- The high-low example: The probability of high outcome depends only on the payment increment p = x(high) − x(low), and this function S(p) is non-decreasing.Expected utility is U(x) = S(p)(v − p) − x(low).
- Width dimension: For any candidate-contract set, AgnosticZooming has small width dimension when the supply distribution is strongly Lipschitz-concave.The assumptions require Lipschitz-continuous S(p) and strongly concave ˜U(p).
- Regret comparison: Regret is O(log T) T 3/5 for AgnosticZooming in this setting, whereas NonAdaptive cannot improve beyond O(T 3/4) over the relevant candidate-contract choices.The comparison is with respect to the best contract in X.
6 Proof of the main regret bound (Theorem 4.1)
The proof analyzes AgnosticZooming through clean executions, confidence events, and cell-selection invariants. It then bounds how often suboptimal cells are selected and aggregates their regret using badness and virtual width.
- Algorithmic invariants: AgnosticZooming maintains active cells that remain relevant, cover candidate contracts, and satisfy Wt(C) ≤ 5 radt(C).The zooming rule is essential for maintaining the width-radius invariant.
- Clean executions: A clean execution is defined through high-probability concentration events controlling empirical utilities and related estimates across active cells.Chernoff bounds and union bounds establish that an execution is clean with probability at least 1 − 1/T.
- Index bounds: On a clean execution, the index of each selected cell is bounded by its utility plus confidence-radius terms, including I(Ct) ≤ U(x) + O(radt(Ct)) for composite cells.This connects the algorithm’s optimistic index to the utility of every contract inside a selected composite cell.
- Badness control: Clean executions also guarantee that each active cell’s badness is O(radt(C)), linking suboptimality to statistical uncertainty.The argument uses the index bounds and the most recent selection time of each cell.
- Selection counts: A cell with badness ∆(C) is selected at most O(log T/(∆(C))2) times, so highly suboptimal cells receive limited exploration.This selection bound is the key step for converting confidence control into a regret bound.
- Regret aggregation: The final clean-execution analysis groups cells by badness, bounds their cumulative contribution, and uses the probability of cleanliness to complete Theorem 4.1.Cells with badness at most δ contribute at most δT, while higher-badness groups are controlled through their counts and widths.
7 Simulations
Simulations compare AgnosticZooming with NonAdaptive across worker markets and discretization choices. AgnosticZooming generally matches or exceeds NonAdaptive, converges faster with adequate or small ψ, and remains competitive when ψ is large.
- Overview of the results: Across all simulations, AgnosticZooming performs comparably to or better than NonAdaptive across the evaluated worker markets.The simulations use Uniform Worker, Homogeneous Worker, and Two-Type markets, with each algorithm run 100 times.
- Payoff versus discretization: AgnosticZooming either matches or outperforms both NonAdaptive variants across all markets and tested ψ values, with a large advantage when ψ is small.Performance is measured by time-averaged cumulative utility after 5K rounds.
- Performance over time: AgnosticZooming converges faster than NonAdaptive when ψ is adequate or small, but converges slower when ψ is large before eventually matching NonAdaptive.The comparison uses ψ values representing too small, adequate, and too large initial discretizations.
- Practical tuning: If T is known and ψ can be optimized for that horizon, NonAdaptive can achieve similar performance to AgnosticZooming.The authors note that approximately optimal ψ may be difficult to calculate in applications, and T may be unknown in advance.
- Small initial discretization: With small ψ, AgnosticZooming converges nearly as fast as NonAdaptive with larger ψ for small T and reaches a better payoff for large T.This comparison evaluates payoff trajectories over time.
- Experimental procedure: The reported standard errors are approximately 0.001 or less, with each plotted point averaging 100 runs and all previous rounds.The averaging procedure applies across the simulation plots.
8 Application to dynamic task pricing
The paper applies AgnosticZooming to dynamic task pricing, where prices are offered sequentially to agents with private costs. It obtains sublinear regret and improves on NonAdaptive under structured cost distributions.
- Problem setting: Dynamic task pricing is the special case in which one buyer sequentially offers prices to sellers with private costs and obtains value from purchased items.A sale corresponds to the sole non-null outcome in the contract-design formulation.
- Pricing representation: The dynamic pricing application uses a one-dimensional price representation, with expected utility U(p) = F(p)(v − p).F(p) is the probability of acceptance at price p, and v is the buyer’s value per purchased item.
- General case: AgnosticZooming with Xcand = X achieves regret O(T 2/3 log T) in dynamic task pricing.This is the general worst-case result for the pricing problem.
- Structured cost distributions: For k-piecewise-uniform costs with λ-bounded density, AgnosticZooming achieves regret ˜O(T 3/5).The result assumes constant k and λ satisfying the stated bounded-density conditions.
- Comparison with NonAdaptive: NonAdaptive with its worst-case granularity achieves regret ˜O(T 2/3), while AgnosticZooming outperforms it on the specified nice problem instances.The comparison concerns 2-piecewise-uniform costs with sufficiently bounded density.
- NonAdaptive lower bound: For arbitrary ψ, NonAdaptive has maximal regret Rψ(T) = Ω(ψT + T/ψ), and discretization contributes an additional Ω(ψT) term.These bounds capture the tradeoff between discretization error and learning regret.
9 Related work
The paper situates dynamic contract design at the intersection of contract theory, crowdsourcing incentive mechanisms, and sequential decision problems. It extends prior online task-pricing and principal-agent settings by combining multiple agents, online contract adjustment, and unobservable strategic effort.
- Contract theory: Dynamic contract design extends the principal-agent model to multiple agents and online contract adjustment over time.Unlike the classic setting, the requester interacts with multiple agents and may revise contracts online.
- Incentives in crowdsourcing systems: Prior crowdsourcing incentive research studies mechanisms for encouraging high-quality work, including virtual points and performance-based payments.Empirical studies find that financial incentives affect worker behavior, though bonus effects can vary across settings.
- Incentives in crowdsourcing systems: Workers respond to financial incentives, but their behavior does not always follow the traditional rational-worker model.The paper allows its results to hold under a generalized worker model satisfying natural behavioral properties.
- Sequential decision problems: The setting is modeled as prior-independent stochastic-reward MAB with a potentially large or infinite arm set and limited similarity information.The paper connects this formulation to adaptive discretization and zooming methods for continuous-action bandits.
- Sequential decision problems: The paper’s adaptive-discretization approach addresses settings where the numerical similarity information required by Lipschitz MAB is unavailable.This distinguishes the problem from standard Lipschitz formulations that assume a distance function and reward continuity.
- Dynamic pricing: Dynamic task pricing is a special case in which workers accept or reject a posted price, whereas this paper allows broader contract choices with strategic effort.In the related task-pricing formulation, the worker’s strategic choice is directly observable.
10 Conclusions
The paper defines dynamic contract design as a multi-round principal-agent problem with unobservable strategic decisions and analyzes it using adaptive discretization. It reports favorable regret comparisons with uniform discretization and identifies unresolved questions about optimality, practical tuning, candidate-contract design, and scope extensions.
- Contributions: The paper defines dynamic contract design as a multi-round principal-agent problem with unobservable strategic decisions and derives regret bounds using adaptive discretization.The approach does not rely on Lipschitz-continuity assumptions and is supported by simulations.
- Contributions: The paper provably improves over uniform discretization in the general case and in some illustrative special cases.These comparisons are made against the uniform-discretization approach from prior work.
- Open questions: No lower bounds for dynamic contract design are currently known, leaving the optimality of the provable results unresolved.The authors identify lower bounds as necessary for arguing about optimality.
- Open questions: The adaptive discretization index could be refined using richer within-cell information, information from other cells, or smoother probabilistic definitions.The authors give Thompson Sampling as an example of a smoother probabilistic alternative.
- Open questions: The theory lacks a general bound on discretization error as candidate-contract granularity changes, and the optimal mesh need not be known to be uniform.The paper leaves open whether such bounds exist in the general case.
- Open questions: The significance of restricting attention to monotone contracts remains unclear because monotone contracts may be suboptimal.The authors seek conditions under which the restriction is harmless or causes significant loss.
- Open questions: Further analysis is needed for special cases, including mixtures of a small number of worker types and simple parameterized supply distributions.Such work could include clearer corollaries, improved algorithms, and specialized lower bounds.
- Open questions: A natural extension is adding a budget constraint, where distributions over contracts may outperform every fixed contract.The authors identify optimization over contract distributions as the main difficulty in that setting.
A Monotone contracts may not be optimal
A constructed single-worker-type example shows that the requester’s unique optimal contract can be non-monotone. The example compares contracts inducing null, low, and high effort and derives the high-effort contract’s superior value under a stated cost condition.
- Example setup: The example has three non-null outcomes, two non-null effort levels, and a single worker type.The effort levels are low and high, with the worker’s cost function written without a type subscript.
- Example setup: The optimal contract can be found by separately comparing contracts that induce null, low, or high effort.Because all workers have the same type and tie-breaking behavior, each induced-effort case can be optimized separately.
- Low-effort contracts: No contract induces null effort because workers break ties between low and null effort in favor of low effort when c(e_l)=0.Workers therefore always prefer low effort to null effort in this example.
- Low-effort contracts: The best low-effort contract sets x(1)=x(3)=0 and can set x(2)=0, yielding requester value 0.5(v(1)+v(3)).The payment is kept low enough that workers are not induced to choose high effort.
- High-effort contracts: The high-effort optimum sets x(1)=x(3)=0 and x(2)=2c(e_h), satisfying the high-effort incentive constraint.The result follows by maximizing the requester’s expected value subject to the condition inducing high effort.
- High-effort contracts: Under c(e_h)<0.5(v(2)-v(1)), the high-effort contract is uniquely optimal and has value 0.5(v(2)+v(3))-c(e_h).Because x(2)>x(3), this unique optimal contract is not monotonic.