Online Allocation with Heterogeneous Supply and Minimum Workload Guarantees

We study the design of allocation policies for platforms in which workers may churn if they do not receive a minimum level of work. Motivated by our collaboration with a labor marketplace, we propose a novel model of online allocation with heterogeneous workers who differ in quality, capacity, and minimum work requirements. Jobs arrive sequentially, the platform must allocate each job online, and workers remain active only if their long-run average allocation meets their stated requirement. This creates a new variant of the online allocation problem in which the platform must simultaneously maximize allocation quality and satisfy minimum allocation constraints in order to retain high-value workers. We show that commonly used policies—such as first-come-first-served and quality-based greedy allocation—may lead to arbitrarily poor equilibria because they ignore worker-level preferences. To address these shortcomings, we develop Tracker, an online policy that uses a carefully constructed static deterministic relaxation of the underlying dynamic stochastic optimization problem to compute worker-specific target allocation levels and then dynamically “tracks” these targets over time. Despite its simplicity, Tracker is optimal, which we establish via a careful Lyapunov-based analysis. Computing the target allocation levels requires solving a nonlinear optimization problem with binary variables and exponentially many constraints. We develop two tractable solution methods—one based on convexity and submodular function minimization and one based on a sample average approximation—and provide provable performance guarantees. Using data-calibrated simulations from the collaborating platform, we find that Tracker improves average allocation quality by more than $10\%$ relative to benchmark policies. We further show that Tracker remains robust under high-probability minimum workload guarantees, periodic churn, and strategic misreporting of worker preferences. Our work influenced the labor platform to change their allocation policy, and they observed gains of similar magnitude.

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2024.1196.