---
title: "Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints"
authors:
  - "Yu Cong"
  - "Chao Xu"
  - "Yi Zhou"
doi: "10.24963/ijcai.2025/287"
url: "https://ijcai.org/proceedings/2025/287"
pdf: "https://ijcai.org/proceedings/2025/0287.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "2575-2582"
track: "Main Track"
keywords:
  - "Constraint Satisfaction and Optimization: CSO: Constraint satisfaction"
  - "Constraint Satisfaction and Optimization: CSO: Constraint optimization problems"
  - "Constraint Satisfaction and Optimization: CSO: Constraint programming"
  - "Constraint Satisfaction and Optimization: CSO: Applications"
---

# Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints

Yu Cong, Chao Xu, Yi Zhou

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 2575-2582. DOI: [10.24963/ijcai.2025/287](https://doi.org/10.24963/ijcai.2025/287)

## 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 time. The application originally comes from assigning coupons to users of the ride-sharing apps, where each user can have a limit on the number of coupons been assigned. We consider a more general form, where the coupons for each user forms a matroid, and the coupon assigned to each user must be an independent set. We show the entire trade-off curve can be maintained approximately in near real time.