Matching Architectures that Connect heterogeneous users and healthcare Efficient Systems – MATCHES

In the current boom of numerical economy and on-line services, billion dollar firms promote applications that offer their users an interface to interact and collaborate. In many cases, we can think of the users as members gathered in classes, using the application as an interface to find a match among other members. To name a few, let us mention the Uber services, food delivery dispatching, Online dating and Online gaming websites, job search applications (Brigad, Meteojob, Indeed), peer-to-peer sharing platforms (Blablacar, Le Bon Coin), and so on. Many other physical systems are subject to the same compatibility constraints: kidney allocation networks, blood banks, public housing allocations and assemble-to-order systems.

The aforementioned applications have a clear common ground: the arrivals of requests are random, and their sojourn in the system are finalized to finding a match (a date for next Saturday, a compatible kidney, a qualified cook for next evening, a buyer for my end table, etc.), identified as such according to fixed compatibility rules. In all cases, the system designer aims at guaranteeing a level of Quality of Service to its users, e.g. in terms of delay before finding a match (which is particularly critical whenever waiting can have severe consequences, such as with organ transplants or blood transfusions).

Depending on the application, the system controller may also need to organize the traffic dynamically to avoid congestion or interferences, or to specify a pricing algorithm, for instance. Our aim is to propose a unified mathematical modeling and analysis of this class of systems, and to provide the tools to control their behavior, and optimize their efficiency. The general model we have in mind is the following: items enter a system at random times, gathered into classes. A graph determines the compatibilities between classes. Each entered item aims at finding a compatible match, which is selected according to a prescribed matching policy in case of a multiple choice. Each matched couple leaves the system right away.

The objective of this Project is to analyze the main mathematical properties of this stochastic matching model, and to develop the tools to optimize its behavior. For this, we will follow four main theoretical lines of research:

(1) Developing fluid approximation techniques to estimate the stability region of the system, or control its instability by identifying the source of the overload.
(2) Constructing tools to explicitly derive, simulate or characterize its steady state, to allow a comparison of the matching policies, or an optimization scheme for a given criterion, at equilibrium.
(3) Proposing extensions of the basic model to better suit its wide range of applications: real-time systems, systems on hypergraphs, interferences or pricing mechanisms.
(4) Addressing the related problems of construction of maximal matchings and maximal independent sets on graphs and large random graphs, which have become prevalent in many networking applications.

To transpose our theoretical achievements into tools that will be tractable in practice, we will collect and analyze data from kidney allocation programs, to implement simulation protocols and build optimization algorithms, in the ultimate goal of developing a software environment for the optimal control and design of stochastic systems with matching mechanisms.