A Framework for Multi-stage Bonus Allocation in meal delivery Platform

• About 165,000 No-Accept orders occur daily; they account for over 55% of Meituan’s negative reviews and contribute to restaurant food-waste costs.No-Accept orders are canceled after remaining unaccepted for a prolonged period.Source: §1 · p. 1
• The framework targets cases where bonuses can encourage acceptance; insufficient driver supply during extreme weather is outside the study’s scope.Source: §1 · p. 2
• Fixed bonuses applied separately at each stage lack global planning, motivating allocation strategies that use information across an order’s multi-stage lifecycle.Orders may be accepted, canceled, or carried forward at each stage, with forced cancellation after more than 50 minutes without acceptance.Source: §1 · p. 2
• The problem requires millisecond decisions under a limited monthly budget, although the month’s orders are not known beforehand.The paper identifies using historical information and adapting to randomly arriving orders as challenges.Source: §1 · p. 2
• Online A/B tests reduced cancellations by more than 25% versus single-stage allocation, while restaurant food-waste compensation fell by more than 30%.Source: §1 · p. 2
• The MSBA framework combines acceptance and cancellation models, offline Lagrangian dual-based dynamic programming, online allocation, and periodic budget control.The framework uses historical data to estimate stage-specific multipliers and makes online calculations in O(1).Source: §1 · p. 2

2.1 The Acceptance and Cancellation Model

• An order advances to the next allocation stage only if it is neither accepted nor canceled; its stage-transition probability is 1 − p1 − q1.Source: §2.1 · p. 2, Figure 2 · p. 3
• The model assumes an order’s acceptance probability at a stage depends only on its price at that stage, not prices at other stages or other orders.Source: §2.1 · p. 3
• The semi-black-box acceptance model uses a logistic function whose parameters are learned by machine learning from the bonus and contextual order features.Context includes locations, order timing, estimated arrival time, and driver supply-and-demand information.Source: §2.1 · p. 3
• The model trains its acceptance parameters simultaneously but updates different hidden layers with bonus batches and normal, zero-bonus batches.Bonus batches update hidden layers 0 and 1; normal batches update hidden layers 0 and 2.Source: §2.1 · p. 3
• At a $2 bonus, order A’s acceptance probability rises 0.01, while order B’s rises 0.38; the model therefore motivates allocating bonus to B.At zero bonus, A’s acceptance probability is over 95%, compared with approximately 45% for B.Source: §2.1 · p. 3, Figure 5 · p. 4
• Cancellation probability is estimated with XGBoost using stage-entry order attributes, then calibrated by the observed cancellation share within prediction-value intervals.Source: §2.1 · p. 4

2.2 Definition and Mathematical Model

• The optimization maximizes expected accepted orders subject to the expected total bonus cost staying within budget and each order’s bonus remaining under its upper bound.Source: §2.2 · p. 4

3 ALGORITHM

• Offline LDDP calculates an empirical Lagrangian multiplier for each allocation stage, which the online part uses for real-time bonus decisions.LDDP divides the problem into allocating budget across stages with dynamic programming and allocating bonuses within each stage using Lagrangian dual theory.Source: §3 · p. 4, §3.1 · p. 4

3.1 Offline Optimization: The Lagrangian Dual-based Dynamic Programming

• LDDP handles the multi-stage problem by combining dynamic programming for stage budgets with Lagrangian dual theory for within-stage order allocation.The paper describes the original problem as nonlinear, nonconvex, and intractable in practice.Source: §3.1 · p. 4

3.1.1 Dimensionality Reduction.

• The dimensionality reduction sets m to 1 for computational needs, sacrificing some accuracy in exchange for lower dynamic-programming time complexity.The method approximates the transition vector using a predefined projection matrix; for m=1, it chooses H=[1, 1, ... , 1].Source: §3.1.1 · p. 5

3.1.2 Recursion to Dynamic Programming. Formally, as Í

• The recursion computes value functions backward across allocation stages and integral budget levels, using single-stage allocation values for each stage-budget pair.It starts with the last stage and calculates G_|T|-1 through G_1 for budget values from 0 to B.Source: §3.1.2 · p. 5, §3.1 · p. 5

3.1.3 Solve Single-stage Bonus Allocation Problem Based on La-

• For single-stage allocation, the method reformulates the nonconvex problem as a convex one and uses bisection to obtain the optimal multiplier and value.The stated zero duality gap equates the primal and dual optimal values.Source: §3.1.3 · pp. 5–6

3.2 Online Allocation Algorithm

• Online, each order's delivery bonus is found by solving a separate one-dimensional problem; enumerating potential bonuses gives O(1) complexity per order.The separated problems can be solved in parallel.Source: §3.2 · pp. 6–7

3.3 Periodic Control

• Periodic control runs offline decisions daily on the preceding month's order data and adjusts bonuses when real-time spending exceeds 110% or falls below 90% of budget.The adjustment magnitude is positively correlated with the difference between real-time expenditure and total budget; the strategies are intended to keep spending around budget within an acceptable range.Source: §3.3 · p. 7

4.1 Performance of offline experiments

• The offline instances use real Meituan orders from four cities, and allocation stages represent how often bonus decisions are revisited during an order’s life cycle.For example, a 50-minute order life cycle with ten stages means a decision every five minutes.Source: §4.1 · p. 7
• With eight stages, MSBA cut cancellations by over 60% versus no bonus and outperformed unified and single-stage approaches, with reductions of around 20% and 40%, respectively.The evaluation used real-world orders from four cities, with instance sizes ranging from 46,978 to 258,612 orders over one week.Source: §4.1.1 · p. 7, §4.1 · p. 7

4.1.1 Performance of the MSBA.

• Figure 7 shows total bonuses rising and then falling across stages; most orders are accepted at the first stage, and later stages have fewer acceptances.The authors attribute the early increase in total allocation to more orders requiring bonuses, followed by a decline as fewer orders remain.Source: §4.1.1 · p. 7, Figure 7 · p. 8, Figure 8 · p. 8

4.1.2 Performance of bonus allocation methods with different bud-

• MSBA performs especially better at small budgets, while the methods converge at larger budgets when all potential cancellations can be covered.The comparison includes MSBA, single-stage allocation, and the unified bonus mechanism.Source: §4.1.2 · p. 7, Figure 9 · p. 8

4.1.3 Impact of the number of the allocation stages.

• Accepted-order quantity rises as allocation stages increase, but gains flatten beyond ten stages; the authors recommend no more than ten to balance orders and driver experience.The experiments also note that changing bonuses too frequently is detrimental to crowdsourcing drivers’ experience.Source: §4.1.3 · pp. 7–8, Figure 10 · p. 8

4.2 Performance of online A/B tests

• The online tests randomly split orders into multi-stage, single-stage, and unified groups across five cities, with each group budgeted at 0.2 RMB per order.The tests covered 120 delivery areas and 4,960,000 orders per day; empirical Lagrangian multipliers were updated daily from historical data.Source: §4.2 · p. 8
• Under the same budget, the proposed method reduced the NA-canceled order ratio by more than 25% versus single-stage allocation and more than 29% versus unified allocation, while saving more than 30% of restaurant food-waste compensation.Source: §4.2 · p. 8

Meal delivery and attended home delivery

• Prior work on attended home delivery includes methods that approximate delivery costs or account for expected future demand, flexible customer choice, and routing with time windows.The passage describes insertion-cost approximation, expected future demand, and flexible choice with dynamic routing.Source: §5 · pp. 8–9
• Few studies of the meal-delivery problem involve pricing or bonus allocation, despite related work on attended home delivery and meal-delivery operations.The attended-home-delivery studies use time-slot pricing and approximate dynamic programming.Source: §5 · pp. 8–9

Ride-hailing pricing

• Ride-hailing research covers surge pricing and spatial pricing models, but its passenger-facing, spatiotemporal prices differ from meal-delivery bonuses presented to drivers.The passage discusses surge/prime pricing, pricing models, and Global Dynamic Pricing.Source: §5 · p. 9

• The proposed framework combines a semi-black-box acceptance model, LDDP, and online allocation; decisions can be made within milliseconds.Offline results report about 25% and 50% fewer cancellations than single-stage and unified allocation, respectively; online tests report over 25% fewer than single-stage allocation.Source: §6 · p. 9