Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Optimal Control of Dynamic Bipartite Matching Models

Arnaud Cadas 1 Josu Doncel 2 Ana Bušić 3 
3 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique - ENS Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Abstract : A dynamic bipartite matching model is given by a bipartite matching graph which determines the possible matchings between the various types of supply and demand items. Both supply and demand items arrive to the system according to a stochastic process. Matched pairs leave the system and the others wait in the queues, which induces a holding cost. We model this problem as a Markov Decision Process and study the discounted cost and the average cost problem. We fully characterize the optimal matching policy for complete matching graphs and for the N-shaped matching graph. In the former case, the optimal policy consists of matching everything and, in the latter case, it prioritizes the matchings in the extreme edges and is of threshold type for the diagonal edge. In addition, for the average cost problem, we compute the optimal threshold value. For more general graphs, we need to consider some assumptions on the cost of the nodes. For complete graphs minus one edge, we provide conditions on the cost of the nodes such that the optimal policy of the N-shaped matching graph extends to this case. For acyclic graphs, we show that, when the cost of the extreme edges is large, the optimal matching policy prioritizes the matchings in the extreme edges. We also study the W-shaped matching graph and, using simulations, we show that there are cases where it is not optimal to prioritize to matchings in the extreme edges.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Arnaud Cadas Connect in order to contact the contributor
Submitted on : Thursday, September 10, 2020 - 5:39:29 PM
Last modification on : Wednesday, June 8, 2022 - 12:50:03 PM
Long-term archiving on: : Thursday, December 3, 2020 - 2:12:30 AM


Files produced by the author(s)


  • HAL Id : hal-02935921, version 1



Arnaud Cadas, Josu Doncel, Ana Bušić. Optimal Control of Dynamic Bipartite Matching Models. 2020. ⟨hal-02935921⟩



Record views


Files downloads