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

Assignment

Context

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.

Objectives

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])

References

 
 
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

Skills

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