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 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.
Cite
Text
Cong et al. "Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints." International Joint Conference on Artificial Intelligence, 2025. doi:10.24963/IJCAI.2025/287Markdown
[Cong et al. "Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints." International Joint Conference on Artificial Intelligence, 2025.](https://mlanthology.org/ijcai/2025/cong2025ijcai-large/) doi:10.24963/IJCAI.2025/287BibTeX
@inproceedings{cong2025ijcai-large,
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 = {International Joint Conference on Artificial Intelligence},
year = {2025},
pages = {2575-2582},
doi = {10.24963/IJCAI.2025/287},
url = {https://mlanthology.org/ijcai/2025/cong2025ijcai-large/}
}