You run growth marketing at a large ride-sharing and delivery marketplace. You have millions of eligible drivers and couriers, hundreds of concurrent incentive programs (sign-up bonuses, streak rewards, quest challenges), and a set of team-level quarterly budgets — one per line of business — that are hard caps. Your current approach is first-come, first-served: whichever incentive program registers a user first wins, and budget is managed manually at the end of each period.
You've been asked to design a system that replaces this with an optimized, automated allocation: given predicted uplift per user-incentive pair from your ML models, select which incentive to assign to which user (or no incentive at all) to maximize total predicted ROI across all lines of business without violating any team's budget.
Walk me through the optimization formulation, the solver you'd choose at this scale and why, and how you'd keep spend inside hard quarterly budgets when your cost predictions drift.
Practice against the follow-up probes
- Your uplift models give you predicted ROI, but ROI for a delivery incentive might cannibalize ride bookings for the same driver. How do you represent and optimize for net marketplace impact rather than siloed metric gains?
- Budgets are quarterly, but you're running assignments daily or weekly. How do you pace spend so you neither blow the budget in week one nor leave 40% unspent in week twelve?
- You originally modeled costs as time-series curves over each incentive's duration, but that caused the solver to time out. What went wrong, and what trade-off did you make to fix it?
- Your LP solver works fine on 10,000 users but takes over 24 hours on 100,000. What's the underlying cause, and what class of solver would you switch to and why?
- A new product line has poor immediate engagement metrics but is strategically important. How does your system avoid always starving it of budget in favor of well-established, high-ROI programs?
Show answer guide
What the interviewer is probing
This question tests whether the candidate can bridge ML prediction with combinatorial optimization at scale — recognizing that 'pick the highest-uplift treatment per user' is wrong when budgets couple decisions across millions of users. It probes metric judgment (cross-vertical ROI, strategic weights), architecture (prediction layer decoupled from valuation layer, budget feedback control), and scale-and-failure reasoning (solver choice, time-series cost complexity, pacing under model drift). Strong candidates will identify the NP-hard nature of the assignment problem and reason about the solver trade-off without needing to know CP-SAT by name.
Strong answer outline
Problem framing - Clarify: How many users, levers, budget buckets? What's the assignment cadence? Are assignments one-per-user or can a user receive multiple incentives? - The core constraint: this is a multiple knapsack problem — knapsacks are team budgets, items are user-incentive pairs with predicted cost and value, goal is to maximize total value subject to per-knapsack budget constraints. - Naive per-user greedy (assign each user their highest-uplift option) ignores coupling: high-cost incentives burn budget that could serve more users at lower cost.
ROI signal design - Wrong turn: predict a single engagement metric per incentive. Fails because a delivery incentive that pulls a driver away from rides improves one metric while hurting another — net effect is negative. - Better: predict a vector of metric uplifts (rides trips, eats orders, driver utilization, earnings per hour) using uplift models trained on randomized experiment data. - Apply a strategic weight vector — set by business context — to convert the metric vector to a scalar ROI via dot product. Weights for a new market expansion emphasize growth; mature markets emphasize efficiency. Separating prediction (objective) from valuation (subjective) lets the same model serve different strategic priorities without retraining. - Guardrails: include cross-vertical cannibalization as a negative-weight term. Monitor net marketplace metrics, not just primary metrics, in holdout evaluation.
Budget pacing across time
- Problem: quarterly budgets with weekly or daily assignment cycles. ML cost predictions drift; if predictions underestimate cost, you overspend early.
- Control loop design: at each cycle, compute remaining_budget = configured_budget - observed_spend - predicted_liability, where predicted liability is the forecasted future cost of already-assigned active incentives not yet paid out.
- This self-corrects: if actual costs exceed predictions, the pacer tightens the cap for future cycles, smoothing over the quarter.
- Trade-off on cost modeling: modeling cost as a daily time-series over the incentive duration is accurate but explodes solver dimensionality (N users × T days constraints vs. N scalar constraints) and creates artificial bottlenecks when a predicted spike on one day blocks otherwise-viable assignments. Collapsing total predicted cost to the assignment day sacrifices granularity but makes the solver tractable and dramatically improves budget utilization.
Optimizer design - Scale challenge: with millions of users and hundreds of levers, the candidate space is the Cartesian product — potentially billions of user-incentive pairs. - Why LP fails at scale: LP relaxes the binary assignment decision to a continuous variable, then rounds. For large combinatorial problems the LP relaxation's solution is far from integer-feasible, and branch-and-bound search explodes. Runtime can exceed 24 hours on 100K users. - Better fit: constraint programming solvers (e.g., CP-SAT) natively handle discrete, binary assignment variables and use propagation + intelligent pruning to eliminate infeasible branches early. Same 100K-user instance solved in minutes. - Plug-and-play solver interface: abstract the problem definition (variables, constraints, objective) from the solver implementation so you can swap solvers as problem structure evolves without rewriting business logic. - Common wrong turn: trying to scale a greedy heuristic (rank by ROI/cost ratio, assign greedily until budget exhausted). This is fast but suboptimal and provides no optimality guarantees or constraint flexibility.
System architecture - Offline/batch flow: cron-triggered orchestrator → fetch eligible user pools from segmentation → generate user × lever candidate pairs → score with ML platform (uplift, cost) → pacer computes available budget cap → optimizer solves MKP → push assignments to downstream execution services. - Latency: optimization is offline/batch, so SLA is minutes to hours, not milliseconds. Decouple from real-time serving. - Scale pressure points: candidate generation (Cartesian product can be billions of rows — pre-filter ineligible pairs before scoring), ML scoring (batch inference at scale), solver memory (large binary programs; may need to shard by geography or time window). - Failure modes: solver timeout (set a time limit, return best feasible solution found); ML model staleness (monitor feature drift; degrade gracefully to simpler heuristic if model is stale); budget overrun from late-arriving cost signals (pacer's predicted liability must account for settlement lag).
Evaluation - Offline: simulate allocations on historical data; compare total assigned ROI and budget utilization vs. FIFO baseline. - Online: holdout experiment — randomly assign a fraction of users to the optimizer vs. baseline; measure net marketplace metrics (trips, earnings, utilization) per dollar spent, with guardrails on cross-vertical cannibalization. - Exploration vs. exploitation: current system requires manual intervention to test new incentive structures. Flag as open problem: auto-allocate a small exploration budget to novel incentives, gather uplift signal, retrain models, inject validated structures — closing the loop.
The underlying concept
Incentive allocation at scale is a multiple knapsack problem (MKP): you must assign binary decisions (give user U incentive I or not) to maximize a global objective subject to coupling budget constraints, which makes the decisions across users non-independent. This is fundamentally combinatorial and NP-hard, which is why greedy or LP approaches break down as the problem scales — LP's continuous relaxation poorly approximates the integer solution when the problem is highly combinatorial, while constraint programming solvers exploit problem structure (propagation, pruning) to find near-optimal integer solutions efficiently. The two-layer ROI design — predicting metric uplifts separately from applying strategic weights — is a classic separation of concerns: the prediction layer is a calibration problem (train once, reuse), while the valuation layer is a business policy problem (change without retraining). Budget pacing as a feedback control loop is the standard engineering answer to the tension between probabilistic ML predictions and hard financial constraints: rather than trusting the model's cost forecast, continuously reconcile predictions against observed reality and adjust the constraint fed into future optimization runs.
Source
Derived from Beyond Prediction: Solving the Multiple Knapsack Problem at Scale: How Uber Optimizes Incentives