Online Matching with Controllable Rewards and Arrival Probabilities
Yuya Hikima, Yasunori Akagi, Naoki Marumo, Hideaki Kim
Abstract
Online bipartite matching has attracted much attention due to its importance in various applications such as advertising, ride-sharing, and crowdsourcing. In most online matching problems, the rewards and node arrival probabilities are given in advance and are not controllable. However, many real-world matching services require them to be controllable and the decision-maker faces a non-trivial problem of optimizing them. In this study, we formulate a new optimization problem, Online Matching with Controllable Rewards and Arrival probabilities (OM-CRA), to simultaneously determine not only the matching strategy but also the rewards and arrival probabilities. Even though our problem is more complex than the existing ones, we propose a fast 1/2-approximation algorithm for OM-CRA. The proposed approach transforms OM-CRA to a saddle-point problem by approximating the objective function, and then solves it by the Primal-Dual Hybrid Gradient (PDHG) method with acceleration through the use of the problem structure. In simulations on real data from crowdsourcing and ride-sharing platforms, we show that the proposed algorithm can find solutions with high total rewards in practical times.
BibTeX
@inproceedings{ijcai2022p254,
title = {Online Matching with Controllable Rewards and Arrival Probabilities},
author = {Hikima, Yuya and Akagi, Yasunori and Marumo, Naoki and Kim, Hideaki},
booktitle = {Proceedings of the Thirty-First International Joint Conference on
Artificial Intelligence, {IJCAI-22}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Lud De Raedt},
pages = {1825--1833},
year = {2022},
month = {7},
note = {Main Track},
doi = {10.24963/ijcai.2022/254},
url = {https://doi.org/10.24963/ijcai.2022/254},
}