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

Cong, Yu; Xu, Chao; Zhou, Yi

doi:10.24963/ijcai.2025/287

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

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 2575-2582.

https://doi.org/10.24963/ijcai.2025/287

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

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.

Yu Cong, Chao Xu, and Yi Zhou. 2025. Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 2575–2582. https://doi.org/10.24963/ijcai.2025/287

@inproceedings{ijcai2025p287,
  title     = {Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints},
  author    = {Cong, Yu and Xu, Chao and Zhou, Yi},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {2575--2582},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/287},
  url       = {https://doi.org/10.24963/ijcai.2025/287},
}

TY  - CPAPER
TI  - Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints
AU  - Cong, Yu
AU  - Xu, Chao
AU  - Zhou, Yi
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 2575
EP  - 2582
DO  - 10.24963/ijcai.2025/287
UR  - https://doi.org/10.24963/ijcai.2025/287
ER  -