PaperlayerView exact revision on arXiv

Source-linked AI summary

Sequential Offering in On-Demand Platforms: On the Optimality of Greedy Ranking

Hongyao Ma, Will Ma, Matias Romero

arXiv:2609.08001v1cs.GTcs.DS

TL;DR

On-demand platforms must fill time-sensitive jobs despite workers rejecting offers, and the interaction between sequential wage increases and worker order has been overlooked. The paper fixes a greedy worker order and optimizes wages conditional on it, finding this approach optimal for a broad class of reservation-wage distributions.

  • Problem

    Platforms must fill time-sensitive jobs with workers who may reject offers, but the interaction between sequential wage increases and worker ordering has been overlooked.

    Source: §1 · pp. 1–2

  • Method

    The paper fixes workers in descending match quality and optimizes sequential wages conditional on that greedy order.

    Source: §1 · p. 2

  • Results

    Greedy ranking with optimized wages is optimal for a broad class of distributions governing workers' willingness to work.

    Source: §1 · p. 3

  • Takeaways & Limitations

    In the stated settings, sending initial low offers to inferior matches cannot improve on greedy ranking with optimized wages.

    Source: §6 · pp. 21–22

    The analysis considers a single job; extending the framework to multiple jobs and parallel offerings is left for future work.

    Source: §6 · p. 22

Abstract

from arXiv · show

On-demand platforms face the fundamental challenge of fulfilling time-sensitive jobs with independent workers who may decline offers. To minimize delays and unfulfilled jobs, platforms frequently raise the offered wage sequentially following each rejection. However, the interaction between these dynamic price adjustments and the specific sequence in which workers are approached has been overlooked. In particular, if the best-suited workers (e.g., closest to the job) are also ranked earliest in the sequence, then those workers would see the lowest offered wages and may decline, leading to poor system outcomes where less-suited workers end up seeing the raised wages and accepting the job. We study the sequential offering problem to maximize expected welfare or platform profit by jointly optimizing the ranking of workers and the pricing trajectory. Surprisingly, our main result establishes that if the reservation wage distribution exhibits a non-increasing and convex density function (e.g., Uniform, Exponential), welfare is maximized by greedy ranking and wages optimized via backward induction. For arbitrary distributions, we prove that greedy ranking achieves a tight $n/(2n - 1)$ fraction of the prophet benchmark. Numerical results for settings beyond the distributional assumptions find welfare losses well below those allowed by the universal guarantee, even in families where greedy is provably suboptimal. This suggests that rather than sending initial "low ball'' offers to worse matches, platforms should stick with greedy ranking and optimize the wage offerings by appropriately taking the continuation value of the downstream offers into consideration.

1. Introduction

The section examines how on-demand platforms should jointly sequence workers and set sequential wages when offers may be rejected, contrasting approximation guarantees with conditions for exact greedy optimality. It also considers how acceptance-probability sequences affect computation of optimal policies.

1. Introduction

  • Sequential wage increases respond to rejections, but offering low wages first to the best matches can lead worse matches to accept higher later offers, motivating greedy ranking with wages optimized conditional on that order.The proposed approach replaces searching worker permutations with sorting by match quality and uses dynamic programming to compute wages.Source: §1 · p. 2

1.1. Model Description

  • The model assigns heterogeneous workers values and independently drawn reservation wages from a common distribution, with the platform choosing the order and wage offers to maximize expected payoff.For welfare, optimal net wages account for the opportunity cost of approaching another worker; total wages weakly increase as continuation value falls, and greedy optimality extends to profit for a restricted class including Exponential and Uniform distributions.Source: §1.1 · p. 3

1.2. Main Contributions

  • Greedy ranking with wages optimized by backward induction is welfare-optimal when reservation-wage density is non-increasing and convex.This class includes Uniform, Exponential, and Pareto distributions; greedy optimality also holds for Half-normal costs, while every ranking gives the same welfare under optimal wages for Logistic costs.Source: §1.2 · pp. 3–4
  • For n workers, greedy ranking’s tight guarantee is n/(2n −1) of the benchmark, approaching 1/2 as n grows.The guarantee applies even when greedy is suboptimal and is tight relative to the best ranking.Source: §1.2 · p. 4

1.3. Connection to an open theoretical problem in prophet inequalities

  • The joint problem is a structured IID location-shift case of the free-order prophet inequality problem, and the paper asks which distributions make greedy ranking with wage optimization optimal under any location shifts.General sequencing is NP-hard; the authors describe their work as the only progress on this distribution-characterization question since Hill and Hordijk (1985).Source: §1.3 · p. 5

1.4. Further Related Work

  • Sequential targeted offers differ from prior platform-pricing work focused on market-level prices and from probing models with exogenous acceptance probabilities, because acceptance here is endogenous to wage choice.The paper frames this distinction against prior literature on pricing, matching, and sequential offering.Source: §1.4 · p. 6
  • Preventing adversarial sequences of acceptance probabilities can make the optimal policy easier to compute.Source: §1.4 · p. 6
  • The paper departs from algorithmic approximation by identifying distributional conditions under which exact dynamic programming aligns with greedy sequencing.This is presented as a return to exact structural optimality.Source: §1.4 · p. 6

2. The Model

The model has a platform assign one job to a heterogeneous worker pool through sequential offers, choosing both the approach order and net wages. Workers share an i.i.d. private-cost distribution, while their observable costs and resulting net values may differ.

2. The Model

  • Each worker's total cost combines a deterministic component with an unobservable private cost, modeled as i.i.d. across workers.The shared private-cost distribution and worker-specific observable costs produce heterogeneous net values.Source: §2 · p. 7
  • The platform chooses a worker ranking and a net wage for each offer; rejection advances the process, while acceptance fulfills the job.Offers are take-it-or-leave-it, and the worker accepts when private cost is no greater than the net wage.Source: §2 · pp. 7–8
  • The objective compares expected welfare across permutations of workers' net values, with greedy ranking ordering them from highest to lowest.For each sequence, the model evaluates the best achievable welfare under its net wages.Source: §2 · p. 8
  • For any fixed sequence, optimal wages can be computed efficiently by dynamic programming, while sequencing is challenging under arbitrary heterogeneous distributions.The model's common private-cost distribution gives workers' realized welfare values a location-shift structure.Source: §2 · p. 8

3. Optimality of Greedy Ranking

The section derives optimal wages by backward induction and establishes that greedy ranking maximizes expected welfare under a non-increasing, convex cost density. Its proof shows that adjacent inversions can be swapped and wages re-optimized without lowering welfare.

3. Optimality of Greedy Ranking

  • The section’s proof strategy derives a recursive solution for wages and welfare under any sequence, then uses adjacent pairwise swaps to analyze ranking optimality.Source: §3 · p. 9

3.1. Optimal Wages

  • The optimal wage at each step equals the current worker’s value minus the downstream continuation value, and total wages rise after each rejection.The wage is set by backward induction to balance immediate expected welfare against continuation value.Source: §3.1 · pp. 9–10

3.2. Local Stability

  • With welfare-optimal wages, greedy ranking is locally stable when the private-cost CDF is concave and its lower support endpoint is normalized to 0.Under these conditions, no alternative ranking achieves higher welfare at the wages optimized for the greedy sequence.Source: §3.2 · pp. 10–11

3.3. Global Optimality

  • GRE(v) = OPT(v) for all v under a non-increasing, convex density, so no worker sequence outperforms greedy ranking.The global argument removes adjacent inversions while re-optimizing wages after each swap.Source: §3.3 · p. 13
  • With a non-increasing, convex cost density, the greedy sequence is globally optimal.The theorem’s proof establishes this by iteratively swapping adjacent inversions and re-optimizing the two wages without lowering welfare.Source: §3.3 · p. 15
  • Decreasing density supports selective early offers that preserve enough acceptance probability to favor better matches, while convexity restricts how quickly that sensitivity changes.Source: §3.3 · p. 15
  • The density assumptions are sufficient, not necessary; the next section gives a distribution-free performance guarantee when they do not hold.Source: §3.3 · p. 15

4. Worst-case Guarantees

Greedy ranking has a finite-sequence welfare guarantee against the prophet benchmark, and the paper establishes that this guarantee is tight. The proof uses the common location-shift structure to improve on the standard half-prophet bound for finite sequences.

4. Worst-case Guarantees

  • The classical half-prophet guarantee is tight for general heterogeneous variables, but its worst-case construction cannot be represented by the paper’s location-shift structure.For any fixed order, an optimal stopping policy achieves at least half the prophet benchmark.Source: §4 · p. 16
  • With common additive cost noise, location shifts and monotone expected positive surplus yield a tighter finite-sequence lower bound that still converges to 1/2.The result applies to net values ordered v1≥···≥vn and cost distributions with E[Z−] < ∞.Source: §4 · p. 16
  • The greedy-to-prophet lower bound n/(2n −1) converges to 1/2, and the construction makes the bound tight against both benchmarks for every n≥2.The benchmarks are the online optimum over worker sequences and the offline prophet, which observes all cost realizations in hindsight.Source: §4 · pp. 15–18

5. Numerical Results

Numerical searches found no counterexamples for several distributions outside the theorem’s sufficient conditions, while other families allow greedy to be suboptimal. Even in deliberately adverse families, the lowest observed welfare ratios remained above the universal guarantee, though they are not stronger guarantees.

5.1. Simulation setup

  • Searches covering more than five million grid points found no counterexample for Normal, Log-normal, Log-logistic, or Gumbel-for-maxima costs within the tested domains.The search used a fine grid, optimization between grid points, and high-precision checks of the most adverse candidates.Source: §5.1 · pp. 18–19, Table 1 · p. 19

5.2. When Greedy is Suboptimal

  • When mean cost lies below the median, two-worker counterexamples exist; approaching the lower-value worker first can preserve the better match as a fallback.The construction uses two high, closely spaced match values.Source: §5.2 · p. 19
  • For Beta(α,1), counterexamples exist for every α > 1; Weibull is optimal for k ≤1, while Gumbel minima also admits counterexamples.For Beta, the mean falls below the median for α > 1; the Weibull search found no counterexamples for tested shapes between 1 and k0.Source: §5.2 · pp. 19–20

5.3. How Much Welfare Does Greedy Lose?

  • 91.566% at two workers and 88.589% at eight: Beta’s lowest observed ratio fell as costs concentrated near their upper endpoint, versus the 53.3% universal guarantee at eight.Lowest observed ratios were also 97.6% for Weibull with k = 10 and 95.0% for Gumbel minima.Source: §5.3 · pp. 20–21, Figure 2 · p. 21

6. Concluding Remarks and Future Work

The paper studies jointly choosing worker order and wages in sequential offers, and identifies conditions under which greedy ranking with dynamically optimized wages is optimal. Numerical findings support greedy ranking beyond those conditions, while the model leaves several operational extensions open.

6. Concluding Remarks and Future Work

  • A non-increasing, convex cost density makes greedy ranking by observable net value with wages optimized by backward induction globally optimal.Under these conditions, initial low offers to inferior matches cannot improve on greedy ranking with optimized wages.Source: §6 · pp. 21–22
  • Numerical results find no counterexample for several relevant distributions, and adverse instances where greedy is suboptimal retain more welfare than the worst-case guarantee allows.The findings motivate sharper guarantees for specific cost distributions while preserving the prescription to rank by match value and account for later offers when setting wages.Source: §6 · p. 22
  • The model focuses on sequential search for a single job; multiple jobs, parallel offers, and correlated values are extensions that would capture additional operational complexities.The paper also identifies online learning to account for shifts in the platform’s belief about the cost distribution as a direction for future work.Source: §6 · p. 22

Appendix A: Additional Optimality Results

Appendix A extends greedy-ranking optimality to half-normal costs and shows that rankings are welfare-equivalent under logistic costs. Appendix B describes the numerical search and its bounded coverage for finding cases where greedy ranking is suboptimal.

Appendix A: Additional Optimality Results

  • Appendix A’s two additional cases extend greedy-ranking optimality beyond Theorem 1’s density conditions.The half-normal case uses an adjacent-swap proof with an additional bound, while logistic costs make all rankings welfare-equivalent.Source: Appendix A · p. 26, §A.2 · p. 27

A.1. Half-normal Costs

  • Half-normal costs retain global optimality of greedy ranking with welfare-optimal wages for every finite worker pool and real net-value vector.The proof extends the adjacent-swap argument with an additional bound in place of density convexity.Source: §A.1 · p. 26, Appendix A · p. 26

A.2. Logistic Costs: Every Ranking Has the Same Welfare

  • Under logistic costs, every worker ranking has the same welfare once wages are optimized.The proof uses a closed-form continuation value that is unchanged by permutation.Source: §A.2 · p. 27

Appendix B: Searching for Counterexamples to Greedy Optimality

  • The counterexample search seeks worker values for which approaching the lower-value worker first improves on greedy ranking.The appendix distinguishes this search from separate experiments measuring greedy welfare when it is suboptimal.Source: Appendix B · p. 27

B.1. Objective and Numerical Accuracy

  • The search minimizes G(x,y) = D(x,y)/(y − x), preserving the sign of the welfare difference while reducing numerical cancellation.The integral representation and higher-order quadrature support the accuracy checks.Source: §B.1 · p. 28

B.2. Distributions and Search Domains

  • The search uses standardized cost laws and probability-based worker values, with grids spanning central probabilities and both tails.Affine changes to costs and values preserve the sign of the comparison.Source: §B.2 · pp. 28–29

B.3. Searching Between Grid Points

  • Differential-evolution optimization supplements the grid, but neither method guarantees finding every adverse region.The search leaves more extreme tails, shapes outside displayed ranges, and points missed within the continuous domains unexamined.Source: §B.3 · pp. 29–30

B.4. Results and Accuracy Checks

The numerical checks remove all initial Gumbel-max flags at higher precision, while selected Weibull and Gumbel-minima cases retain negative welfare differences. The following appendix covers proofs and experiments underlying the performance analysis when greedy ranking is suboptimal.

B.4. Results and Accuracy Checks

  • All 7,887 initial Gumbel-max flags disappear at higher quadrature orders, while selected Weibull and Gumbel-minima pairs retain negative differences at high precision.The table reports screening flags and their rechecks; selected pairs are also checked at 100-digit precision.Source: §B.4 · p. 30, Table EC.2 · p. 30

Appendix C: Performance When Greedy Is Suboptimal

  • Appendix C supplies proofs and experiments for the performance analysis, including the mean–median condition and numerical search procedures.It also describes welfare evaluation, the bounded Beta search, and experiments for concentrated costs.Source: Appendix C · p. 31

C.1. Why Counterexamples Exist

The mean–median condition identifies distributions for which greedy ranking can fail, while backward recursions evaluate greedy and optimal rankings. The appendix applies this condition to Beta, Weibull, and Gumbel costs.

C.1. Why Counterexamples Exist

  • If F(µ) < 1/2, some two-worker instance makes greedy ranking strictly suboptimal.For Beta(α,1), greedy is globally welfare-optimal for every worker count and value vector exactly when 0 < α ≤ 1; every α > 1 admits a strict two-worker counterexample.Source: §C.1 · p. 31
  • When worker values are close and high, the greedy first offer approaches µ + d; if F(µ) < 1/2, it is accepted less often than the fallback offer for small d.In this case reversing the ranking and reoptimizing wages can improve welfare.Source: §C.1 · p. 31
  • For unit-scale Weibull costs, the mean and median cross once at k0 = 3.439540619..., and the lemma proves suboptimality for every k > k0.Standard Gumbel minima also satisfy the condition, so the lemma applies to them as well.Source: §C.1 · p. 32

C.2. Evaluating Greedy and the Best Ranking

  • For a fixed order, backward induction updates continuation value q to q + ψ(vi − q), while trying each worker first over subsets computes OPT(v) without listing all n! rankings.The update is nondecreasing in downstream value, so the best order for the remaining subset is optimal.Source: §C.2 · p. 32
  • The ranking optimization is exhaustive, but the search over worker values may miss better candidates; reported ratios are numerical upper bounds on the unknown minimum.Selected minima are recomputed at 80-digit precision, while Theorem 2 supplies the rigorous lower bound.Source: §C.2 · p. 32

C.3. Beta Costs: A Compact Search and a Concentrated-Cost Limit

The appendix reduces two-worker Beta searches to a bounded region and analyzes concentrated-cost limits. These limits yield an explicit greedy loss for Beta costs and transfer strict counterexamples from Gumbel minima to sufficiently high-shape Weibull costs.

C.3. Beta Costs: A Compact Search and a Concentrated-Cost Limit

  • For α > 1, the infimum two-worker Beta ratio can be searched over a compact region, and every counterexample outside it has a counterpart inside with weakly lower welfare ratio.The limiting Beta analysis justifies the limiting curve but does not establish the worst ratio over all values or allow an unrestricted interchange of limits.Source: §C.3 · pp. 33, 35
  • As Beta costs concentrate near one, α(1 − Z) converges to an Exponential variable, yielding a limiting welfare recursion for fixed worker-value vectors.Every fixed limiting vector with positive optimal welfare can be approximated by finite-α instances with converging ratios.Source: §C.3 · p. 35
  • The explicit two-worker Beta construction has limiting ratio 91.5663731...%, so greedy can lose at least 8.4336% with only two workers.Numerical optimization of the limiting two-worker problem gives a slightly lower ratio, 91.5661...%, but only the explicit construction provides the stated analytical ratio.Source: §C.3 · pp. 34–35

C.4. Weibull Costs: The Gumbel Limit

  • For unit-scale Weibull costs, Tk = k(Zk − 1) converges to a standard Gumbel-for-minima variable, and welfare comparisons converge for every fixed vector and ranking.A strict Gumbel-minimum counterexample therefore generates Weibull counterexamples for all sufficiently large k.Source: §C.4 · p. 36

C.5. Search Settings and Numerical Results

The numerical section searches for low greedy-to-optimal welfare ratios across cost families and worker counts. Its reported adverse-instance losses remain well below the universal guarantee, but the numerical search does not establish global optimality.

C.5. Search Settings and Numerical Results

  • The search combines grids and numerical refinement across the tested shapes, but its checks do not establish global optimality of the search.The experiments also reuse promising candidate vectors across worker counts and refine selected projections.Source: §C.5 · pp. 36–37
  • The two-worker Beta figure distinguishes proved optimality from lowest ratios found and marks the explicit limiting construction separately from an optimal-limit proof.Green denotes proved optimality, blue the lowest ratios found, and dashed red the explicit construction's ratio.Source: Figure EC.1 · p. 38
  • In the adverse instances tested, the lowest ratios found remain well above the universal guarantee, including as worker counts increase.The results table reports numerical ratios for its first three rows and the rigorous bound in its last row; its Beta row uses the limiting model.Source: Table EC.4 · p. 38

Appendix D: A Unified Quantile Framework for Sequential Offering

The unified quantile framework represents objectives through an effective cost distribution, allowing the welfare optimality result to extend to other objectives. Greedy is optimal when the effective density meets the required shape and endpoint conditions, including for truncated-Exponential costs across welfare, profit, and their convex combinations.

Appendix D: A Unified Quantile Framework for Sequential Offering

  • The framework expresses acceptance choices through a target probability q and maps generalized objectives to an effective cost distribution, making their recursion equivalent to the welfare recursion.The effective distribution is defined probabilistically, so the generalized objective is isomorphic to the welfare problem rather than merely analogous.Source: Appendix D · p. 39
  • Greedy ranking is globally optimal when the effective density is non-increasing and convex and its endpoint behavior satisfies Theorem 1's conditions.For profit, the relevant effective cost is the physical cost transformed by the increasing profit function; its virtual-cost density must meet those conditions.Source: Appendix D · pp. 39–40
  • A non-increasing physical density alone does not imply convexity of the effective density, so it is insufficient to establish global optimality.The second inequality in (EC.27), or direct verification of (EC.29), is still required.Source: Appendix D · p. 40
  • For truncated-Exponential physical costs, greedy ranking is globally optimal for every convex combination of welfare and profit objectives.The family includes the Exponential law and, in the β ↓ 0 limit for finite B, the Uniform distribution on [0,B].Source: Appendix D · pp. 40–41

Appendix E: Robustness to Deterministically Decaying Markets

The appendix studies deterministically decaying markets, where acceptance becomes weakly less likely at later offer positions. Under a condition on downstream distributions, greedy ranking with optimal wages is globally optimal without a density-shape restriction on the first distribution.

Appendix E: Robustness to Deterministically Decaying Markets

  • The model allows known position-specific cost distributions independent of past rejections while keeping observable net values and the worker pool fixed.Rising private costs as the delivery window shrinks are one motivating example.Source: Appendix E · p. 41
  • The model excludes learning an unknown common cost distribution and changes to the eligible worker set.Source: Appendix E · p. 41
  • A deterministically decaying market has F1(w) ≥ F2(w) ≥ ··· ≥ Fn(w) at every wage, so acceptance becomes weakly less likely at later positions.Theorem EC.4 considers such a market with weakly decreasing net values.Source: Appendix E · p. 41
  • Greedy ranking with optimal wages is globally optimal when downstream distributions have non-negative stationary swap differences; no density-shape condition is needed for the first distribution.The condition holds under Theorem 1's hypotheses after translating its lower endpoint, or under Theorem EC.1.Source: Appendix E · p. 41
Loading 2609.08001v1…