{"ID":23507404,"CreatedAt":"2026-09-18T02:21:44.056544415Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.20699","arxiv_id":"2609.20699","title":"Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints","abstract":"We consider a large-scale incentive allocation problem where the entire trade-off curve between budget and profit has to be maintained approximately at all times. The application originally comes from assigning coupons to users of ride-sharing apps, where each user can have a limit on the number of coupons assigned to them. We consider a more general form, where the coupons for each user form a matroid, and the set of coupons assigned to each user must be an independent set. We show the entire trade-off curve can be maintained approximately in near real time.","short_abstract":"We consider a large-scale incentive allocation problem where the entire trade-off curve between budget and profit has to be maintained approximately at all times. The application originally comes from assigning coupons to users of ride-sharing apps, where each user can have a limit on the number of coupons assigned to...","url_abs":"https://arxiv.org/abs/2609.20699","url_pdf":"https://arxiv.org/pdf/2609.20699v1","authors":"[\"Yu Cong\",\"Chao Xu\",\"Yi Zhou\"]","published":"2026-09-17T17:02:48Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}