research-article

Optimal Control of Dynamic Bipartite Matching Models

Authors:

Josu DoncelAuthors Info & Claims

VALUETOOLS 2019: Proceedings of the 12th EAI International Conference on Performance Evaluation Methodologies and Tools

Pages 39 - 46

https://doi.org/10.1145/3306309.3306317

Published: 12 March 2019 Publication History

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 case. We first consider a model with two types of supply and two types of demand items with an N-shaped matching graph. For linear cost function, we prove that an optimal matching policy gives priority to the end edges of the matching graph and is of threshold type for the diagonal edge. In addition, for the average cost problem, we compute the optimal threshold value. According to our numerical experiments, threshold-type policies perform also very well for more general bipartite graphs.

References

[1]

Ivo Adan and Gideon Weiss. 2012. Exact FCFS Matching Rates for Two Infinite Multitype Sequences. Operations Research 60, 2 (2012), 475--489.

Digital Library

[2]

Ivo J. B. F. Adan, Ana Busic, Jean Mairesse, and Gideon Weiss. 2018. Reversibility and Further Properties of FCFS Infinite Bipartite Matching. Math. Oper. Res. 43, 2 (2018), 598--621.

[3]

Itai Ashlagi, Patrick Jaillet, and Vahideh H. Manshadi. 2013. Kidney Exchange in Dynamic Sparse Heterogenous Pools. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce (EC '13). ACM, New York, NY, USA, 25--26.

Digital Library

[4]

Siddhartha Banerjee, Yash Kanoria, and Pengyu Qian. 2018. The Value of State Dependent Control in Ridesharing Systems. ArXiv e-prints (March 2018). arXiv:1803.04959

[5]

Ana Busic, Varun Gupta, and Jean Mairesse. 2013. Stability of the bipartite matching model. Advances in Applied Probability 45, 2 (2013), 351--378. http://arxiv.org/abs/1003.3477

[6]

Ana Busic and Sean P. Meyn. 2014. Approximate optimality with bounded regret in dynamic matching models. ArXiv e-prints (2014). arXiv:1411.1044 http://arxiv.org/abs/1411.1044

[7]

Arnaud Cadas. {n. d.}. Python Code. https://github.com/ArnaudCadas/DynamicMatchingModel.

[8]

Arnaud Cadas, Ana Busic, and Josu Doncel. 2018. Optimal Control of Dynamic Bipartite Matching Models. ArXiv e-prints (Oct. 2018). arXiv:1810.08541

[9]

René Caldentey, Edward H. Kaplan, and Gideon Weiss. 2009. FCFS infinite bipartite matching of servers and customers. Advances in Applied Probability 41, 3 (2009), 695--730. http://www.jstor.org/stable/27793900

[10]

Jon Feldman, Aranyak Mehta, Vahab S. Mirrokni, and S. Muthukrishnan. 2009. Online Stochastic Matching: Beating 1-1/e. In Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society (Ed.). ACM Press, 117--126.

Digital Library

[11]

United Network for Organ Sharing. {n.d.}. Online. https://unos.org/wp-content/uploads/unos/Living_Donation_KidneyPaired.pdf

[12]

Itai Gurvich and Amy Ward. 2014. On the dynamic control of matching queues. Stoch. Syst. 4, 2 (2014), 479--523.

[13]

Emmanuel Hyon and Alain Jean-Marie. 2012. Scheduling Services in a Queuing System with Impatience and Setup Costs. Comput. J. 55, 5 (2012), 553--563.

Digital Library

[14]

Patrick Jaillet and Xin Lu. 2014. Online Stochastic Matching: New Algorithms with Better Bounds. Mathematics of Operations Research 39, 3 (2014), 624--646.

[15]

Jean Mairesse and Pascal Moyal. 2016. Stability of the stochastic matching model. Journal of Applied Probability 53, 4 (2016), 1064--1077.

[16]

Vahideh H. Manshadi, Shayan Oveis Gharan, and Amin Saberi. 2012. Online Stochastic Matching: Online Actions Based on Offline Statistics. Mathematics of Operations Research 37, 4 (2012), 559--573.

Digital Library

[17]

Mohammadreza Nazari and Alexander L. Stolyar. 2018. Reward maximization in general dynamic matching systems. Queueing Systems (12 Nov 2018).

Digital Library

[18]

Martin L. Puterman. 2005. Markov decision processes: discrete stochastic dynamic programming. Wiley-Interscience.

Digital Library

[19]

Robert J. Schalkoff. 1991. Pattern Recognition: Statistical, Structural and Neural Approaches. John Wiley & Sons, Inc., New York, NY, USA.

Digital Library

[20]

Lenka Zdeborová, Aurélien Decelle, and Michael Chertkov. 2009. Message passing for optimization and control of a power grid: Model of a distribution system with redundancy. Phys. Rev. E 80 (Oct 2009), 046112. Issue 4.

Cited By

Ana BArnaud CJosu DJean-Michel F(2024)Performance paradox of dynamic matching models under greedy policiesQueueing Systems: Theory and Applications10.1007/s11134-024-09924-z107:3-4(257-293)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11134-024-09924-z
Moyal PBušić AMairesse J(2024)On the sub-additivity of stochastic matchingQueueing Systems10.1007/s11134-024-09919-w107:3-4(295-339)Online publication date: 23-Jul-2024
https://doi.org/10.1007/s11134-024-09919-w
Begeot JMarcovici IMoyal P(2023)Stability regions of systems with compatibilities and ubiquitous measures on graphsQueueing Systems10.1007/s11134-023-09872-0103:3-4(275-312)Online publication date: 22-Feb-2023
https://doi.org/10.1007/s11134-023-09872-0
Show More Cited By

Index Terms

Optimal Control of Dynamic Bipartite Matching Models
1. Mathematics of computing
  1. Probability and statistics
    1. Stochastic processes
      1. Markov processes
2. Networks
  1. Network performance evaluation

Recommendations

Analysis of an optimal policy in dynamic bipartite matching models
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 ...
Maximum weight induced matching in some subclasses of bipartite graphs
Abstract
A subset $M \subseteq E$ of edges of a graph $G = (V, E)$ is called a matching in G if no two edges in M share a common vertex. A matching M in G is called an induced matching if G[M], the subgraph of G induced by M, is the same as G[S], the subgraph of G induced ...
Dominating induced matching in some subclasses of bipartite graphs
Abstract
A subset M ⊆ E of edges of a graph G = ( V , E ) is called a matching if no two edges of M share a common vertex. An edge e ∈ E is said to dominate itself and all other edges adjacent to it. A matching M in a graph G = ( V , E ) is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

VALUETOOLS 2019: Proceedings of the 12th EAI International Conference on Performance Evaluation Methodologies and Tools

March 2019

202 pages

ISBN:9781450365963

DOI:10.1145/3306309

Copyright © 2019 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

In-Cooperation

EAI: The European Alliance for Innovation
Universitat de les Illes Balears: Universitat de les Illes Balears

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 March 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

VALUETOOLS 2019

VALUETOOLS 2019: 12th EAI International Conference on Performance Evaluation Methodologies and Tools

March 12 - 15, 2019

Palma, Spain

Acceptance Rates

VALUETOOLS 2019 Paper Acceptance Rate 18 of 42 submissions, 43%;

Overall Acceptance Rate 90 of 196 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
103
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ana BArnaud CJosu DJean-Michel F(2024)Performance paradox of dynamic matching models under greedy policiesQueueing Systems: Theory and Applications10.1007/s11134-024-09924-z107:3-4(257-293)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11134-024-09924-z
Moyal PBušić AMairesse J(2024)On the sub-additivity of stochastic matchingQueueing Systems10.1007/s11134-024-09919-w107:3-4(295-339)Online publication date: 23-Jul-2024
https://doi.org/10.1007/s11134-024-09919-w
Begeot JMarcovici IMoyal P(2023)Stability regions of systems with compatibilities and ubiquitous measures on graphsQueueing Systems10.1007/s11134-023-09872-0103:3-4(275-312)Online publication date: 22-Feb-2023
https://doi.org/10.1007/s11134-023-09872-0
Liu HLi Q(2023)Matched Queues with Flexible and Impatient CustomersMethodology and Computing in Applied Probability10.1007/s11009-023-09980-725:1Online publication date: 28-Jan-2023
https://doi.org/10.1007/s11009-023-09980-7
Kerimov SAshlagi IGurvich I(undefined)On the Optimality of Greedy Policies in Dynamic MatchingSSRN Electronic Journal10.2139/ssrn.3918497
https://doi.org/10.2139/ssrn.3918497
Aouad ASaritac O(undefined)Dynamic Stochastic Matching Under Limited TimeSSRN Electronic Journal10.2139/ssrn.3497624
https://doi.org/10.2139/ssrn.3497624

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents