# Uber's Knapsack Problem _Uber's Tarot platform employs a sophisticated Multiple Knapsack Problem solver to optimize incentive allocation, balancing user experience with strict budget constraints._ **Updated:** 2026-08-22 **Published:** 2026-05-28 **Source:** https://www.startuphub.ai/ai-news/technology/2026/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. Incentive Allocation ChallengeDriveroptimizing incentive programs for user experience and budgetFrom the article 2 mentionsThis led to inefficient capital allocation and inconsistent user experiences, as more relevant incentives were often blocked by earlier ones.Multiple Knapsack ProblemContextallocating incentive programs (items) within team budgets (knapsacks)From the articleUber is tackling a classic optimization challenge, the Multiple Knapsack Problem (MKP), at an unprecedented scale to fine-tune its incentive programs.Development ChallengesDriveraddressing scale and complexity in incentive optimizationFrom the article 2 mentionsThis makes the system adaptable for future optimization needs, such as courier positioning, and is a prime example of solving complex distributed systems optimization challenges.solved byTarot PlatformCoreUber's internal platform for incentive distribution and optimizationFrom the article 4 mentionsThe company’s internal platform, Tarot (Targeting Orchestrator), treats incentive distribution as a massive MKP.Calculate ROIContextmeasuring incremental impact on user behavior and marketplace healthFrom the article 7 mentionsThe ultimate goal is to maximize total ROI across Uber's diverse business lines.Budget PacerContextmanaging financial constraints and quarterly budget adherenceFrom the article 9+ mentionsThe 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.Optimizer Solves MKPCorefinding optimal trade-offs between cost and valueleads toMaximize Marketplace EfficiencyEffectachieving strategic allocation of limited resourcesFrom the articleThis 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](/ai-news/tech/2026/uber-s-hybrid-core-allocation) 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. --- Original analysis from [startuphub.ai](https://www.startuphub.ai), the #1 AI startup directory. © StartupHub.ai. All rights reserved. You may not republish this article in full without a license. Search engines and AI research tools may crawl and summarize for reference. Bulk reproduction or model training on this content requires a license. See https://www.startuphub.ai/terms.