PhD Position F/M Learning in dynamic matching models (Campagne CORDI-S)


2023-06314 – PhD Position F/M Learning in dynamic matching models (Campagne CORDI-S)

Contract type :
Fixed-term contract

Level of qualifications required :
Graduate degree or equivalent

Fonction :
PhD Position



The theory of matching has a long history in economics, mathematics, and graph theory [7], with applications found in many other areas such as medicine and information theory. Most of the work is in a static setting. The dynamic model has received recent attention in [5, 3, 6]. One of the most compelling application is organ donation: United Network for Organ Sharing (UNOS) offers kidney paired donation (KPD). This is a transplant option for candidates who have a living donor who is medically able, but cannot donate a kidney to their intended candidate because they are incompatible (i.e., poorly matched) [1]. In this and many other applications, data arrives sequentially and randomly, so that matching decisions must be made in real-time, taking into account the uncertainty of future requirements for supply or demand.

We will consider a dynamic matching model with random arrivals – a dynamic version of the bipartite matching model. As in the static setting, it is based on a bipartite graph. In the discrete-time dynamic model there are arrivals of units of ‘supply’ and ‘demand’ that can wait in queues located at the nodes in the network. A control policy determines which items are matched at each time.

The choice of matching decisions can be cast as an optimal control problem for a dynamic matching model. Some first results were obtained in [4] on the properties of optimal matching policies.


The main objectives of this thesis are:

  • minimize the mean waiting time in the system using reinforcement learning [8] and recent results on some properties of optimal matching policies [4];

  • extending the results in [4] to the case of a compatibility graph that is non-bipartite;

  • generalizing the model: for example to include impatience (unmatched items; may leave the system after some delay), or different degrees of the compatibility between items given by the weights on the edges;

  • consider various applications, some examples being organ donation or ride sharing platforms.

Contact: Ana Busic ([email protected])


  • [1]  United Network for Organ Sharing. Online, KidneyPaired.pdf.

  • [2]  I. Adan, A. Busic, J. Mairesse, G. Weiss. Reversibility and further properties of FCFS infinite bipartite matching. Mathematics of Operations Research 43 (2), 598-621. 2018.

  • [3]  A. Bušić, V. Gupta, and J. Mairesse. Stability of the bipartite matching model. Adv. in Appl. Probab., 45(2):351–378, 2013.

  • [4]  Arnaud Cadas, Josu Doncel, Ana Busic: Analysis of an optimal policy in dynamic bipartite matching models. Perform. Evaluation 154: 102286, 2022.

  • [5]  R. Caldentey, E.H. Kaplan, and G. Weiss. FCFS infinite bipartite matching of servers and cus- tomers. Adv. Appl. Probab, 41(3):695-730, 2009.

  • [6]  I. Gurvich and A. Ward. On the dynamic control of matching queues. Stochastic Systems, 4:1–45, 2014.

  • [7]  L. Lovász and M. Plummer. Matching theory, volume 367. American Mathematical Society, 2009.

  • [8]  R. S. Sutton and A. G. Barto. Reinforcement learning – an introduction. Adaptive computation and machine learning. MIT Press, 1998. Second edition online: book/RLbook2020.pdf


    Main activities

    Main activities (5 maximum):
        Litterature study
        Develop new results and algorithms
        Implement the proposed algorithms in Python or Matlab
        Write research papers and present the results at seminar talks and conference


    Technical skills and level required: master degree in computer science, applied mathematics or electrical engineering with courses probability covering Markov chains; Phython or Matlab, good knowledge or reinforcement learning is optional but will be highly appreciated
    Languages: English, French is not required

    Benefits package

    • Subsidized meals
    • Partial reimbursement of public transport costs
    • Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.)
    • Possibility of teleworking and flexible organization of working hours
    • Professional equipment available (videoconferencing, loan of computer equipment, etc.)
    • Social, cultural and sports events and activities
    • Access to vocational training
    • Social security coverage

    View or Apply
    To help us track our recruitment effort, please indicate in your cover//motivation letter where ( you saw this job posting.

    Job Location