Uber's Knapsack Problem

Uber is tackling a classic optimization challenge, the Multiple Knapsack Problem (MKP), at an unprecedented scale to fine-tune its incentive programs. This isn't just about predicting user behavior; it's about strategically allocating limited resources to maximize marketplace efficiency.

The company’s internal platform, Tarot (Targeting Orchestrator), treats incentive distribution as a massive MKP. It aims to find the optimal trade-off between enhancing user experience and adhering to strict quarterly budgets, a complex negotiation with inherent constraints.

The Incentive Challenge: A Textbook Multi-Knapsack Problem

At Uber, the MKP translates into allocating specific incentive programs (the 'items') within defined team budgets (the 'knapsacks'). Each incentive has a monetary cost ('weight'), and its predicted incremental impact on user behavior and marketplace health represents its 'value'. The ultimate goal is to maximize total ROI across Uber's diverse business lines.

This framework maps directly to the five core components of a classic MKP:

• The Knapsacks (Team Budgets): Each organizational unit has a finite quarterly budget.
• The Items (The Treatments): These are the specific incentive programs, like sign-up bonuses or streak rewards.
• The Weight (The Cost): The monetary cost of each incentive.
• The Value (The Objective): The predicted incremental impact of the incentive.
• The Goal (The Optimization): Maximizing total ROI across all teams and geographies.

Historically, Uber relied on a 'first-in, first-out' approach and manual adjustments for budget management. This led to inefficient capital allocation and inconsistent user experiences, as more relevant incentives were often blocked by earlier ones.

Architecture and Execution Flow

Tarot features a modular architecture coordinating data platforms, budget services, and optimization solvers. The Orchestrator manages the targeting lifecycle, interacting with the Segmentation Platform for user cohorts, the Budget Pacer for spend velocity, and the ML Platform for prediction data.

The execution flow transforms eligible users into optimized assignments. It begins with opportunity generation, creating a vast list of potential user-incentive pairs. These opportunities are then scored by the ML Platform for predicted ROI and cost.

A crucial component is the Budget Pacer, which dynamically adjusts available budget based on configured limits, realized spend, and projected future costs. This ensures spending stays within quarterly targets without overspending.

The core decision-making happens in the Multi-Lever Optimizer. Formulated as an MKP, it selects the subset of assignments that maximizes total value while respecting all constraints. Finally, these optimized assignments are sent to Domain Services for execution.

Calculating ROI: Beyond Simple Metrics

Calculating ROI at Uber's scale is complex, especially when different business lines intersect. A campaign boosting one area might inadvertently harm another through cross-vertical cannibalization.

To address this, Uber employs a two-layer ROI calculation. The prediction layer forecasts uplift across a state vector of metrics (e.g., trips, orders, driver utilization). The valuation layer applies dynamic strategic weights to these metrics based on market context and business priorities.

This allows for a single, comparable ROI score that reflects both immediate engagement and long-term strategic goals, without needing to retrain prediction models for every business shift.

The Budget Pacer: Managing Financial Constraints

The Budget Pacer acts as a feedback control loop, reconciling deterministic financial budgets with probabilistic predictions. It continuously recalculates remaining budget by comparing configured limits, observed spend, and predicted future costs.

This self-correcting mechanism smooths out spending fluctuations. If actual costs exceed predictions, the Pacer constrains future budgets, ensuring near-perfect utilization without overspending.

The Optimizer: Solving the Core Problem

The Optimizer synthesizes paced budgets, predicted ROI, and costs to make mathematically optimal investment decisions for every user. Its directive is computationally intensive, aiming to exhaust available budget for maximum return.

Uber’s approach uses a plug-and-play architecture for the optimizer, allowing different solvers to be swapped in based on scale and complexity. This makes the system adaptable for future optimization needs, such as courier positioning, and is a prime example of solving complex distributed systems optimization challenges.

Development Challenges and Solutions

Initially, modeling costs as time-series curves introduced significant complexity and latency. Shifting to attributing the total predicted cost to the day of assignment simplified the problem space, eliminating artificial bottlenecks and drastically improving budget utilization from approximately 68% to near 100%.

The team also faced scaling pains with its initial solver choice. A Linear Programming (LP) approach with HiGHS performed well for small batches but faltered under large-scale traffic, with job runtimes spiraling out of control. Recognizing the problem’s discrete nature, Uber pivoted to CP-SAT, a more suitable solver for combinatorial optimization, which resolved the convergence issues.