Online Matching with Controllable Rewards and Arrival Probabilities

Online Matching with Controllable Rewards and Arrival Probabilities

Yuya Hikima, Yasunori Akagi, Naoki Marumo, Hideaki Kim

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 1825-1833. https://doi.org/10.24963/ijcai.2022/254

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.
Keywords:
Constraint Satisfaction and Optimization: Constraint Optimization
Constraint Satisfaction and Optimization: Applications
Constraint Satisfaction and Optimization: Modeling