Beyond Prediction: Solving the Multiple Knapsack Problem at Scale: How Uber Optimizes Incentives

This post details the evolution of Uber's incentive optimization platform, Tarot, by framing the problem as a large-scale Multiple Knapsack Problem (MKP). It introduces the core components: Orchestrator, Segmentation Platform, Budget Pacer, Multi-Lever Optimizer (using Google OR-Tools CP-SAT solver), ML Platform, and Domain Services. A key technical contribution is the two-layer ROI calculation, which uses a state vector of predicted metric uplifts and a dynamic weight vector to account for complex trade-offs like cross-vertical cannibalization and strategic weighting. The Budget Pacer is described as a control-loop component for managing spend velocity against quarterly budget constraints.