By GUPPI
Matching theory (a branch of game theory) is a mathematical framework attempting to describe the formation of mutually beneficial relationships over time. What other topic could we possibly have chosen for Valentine's day?
Actually, this is a very serious and important field of research in economics. And, in 2012, Alvin Roth and Lloyd Shapley got awarded a Nobel prize for their work on market design and matching theory.
Different types of matching
Matching problems are modelled as 2 sided problems. Meaning that there are 2 sides of participants in the matching, each with their own characteristics and each participant from one side can be matched with one from the other side. There are 3 types of matching situations:
- One-to-one matching, when you are trying to match one entity to only one other one. For example monogamous couples are a one-to-one matching problem (on one side, all the females and on the other side all the males, can also be man to man, or any other type of 2 sided matching). This problem is also called the marriage problem.
- Many-to-one matching, when one entity can be assigned multiple entities. For example, the allocation of students to schools is a many-to-one matching problem, where multiple students are allocated to one school (on one side, the students and on the other, the schools).
- Many-to-many matching, when different entities can be linked to different entities. For example, workers and employers is a type of many-to-many matching problem (on one side all the workers and on the other, the employers).
How to match
Ok, we understand the problems. But how do we determine the matches?
Well, each participant has preferences (A>B) . We also assume transitivity (A>B and B>C => A>C). Concerning the marriage problem, This is a utopic assumption, since we know that humans are full of biases, and not rational (in the economic sense) but don't get me started on the rationality assumption.
In practice, each participant on one side ranks all participants from the other side and vice versa. Let's check this simple example:
What is a good matching?
Now that we know that participants rank their potential partner, what is a good matching?
A matching is stable if there is no pair (A, B) that could be better matched. A pair that could find a better match is if A prefers B to the one it's matched with and B prefers A to the one it's matched with.
In this example, the matching is not stable because you could match A with E and they would both be better off.
The Gale-Shapley algorithm
Gale and Shapley came up with an algorithm to solve the marriage problem.
It is actually quite simple. The algorithm goes like this :
- Each participant from one side (for the sake of understanding, let's say the women) propose to her favorite member of the other side (the men)
- From the proposals received, the men pick the woman with their highest preference and reject the other women (life is not easy)
- Then on the second round, women whom have been rejected propose to their next favorite option
- Again, the men accept and reject the proposals based on their preferences. They can even reject a women that they previously had accepted if they are offered a better proposal (life is very harsh).
- I think you got it, these iterations continue until every one is matched.
It's been proven that this algorithm leads to a stable matching. On top of being stable, this matching is optimal for the men. Well you probably also got it by now that if the men had proposed and the women disposed, the story would have been totally different and yet a stable matching would have been created.
This algorithm can be easily applied to the other matching problems mentioned above.
And beyond
The Gale-Shapley algorithm is quite neat, it has the obvious advantage to solve a quadratic \( O(n^2) \) problem in a linear way \( O(n) \). Yet it does not lead to an optimal matching for both sides.
In practice, it's also not so easy to rank all participants, say Tinder would ask you to rank all its members. I bet this would take quite some time. Preferences are usually depicted as a multitude of subtle criteria, like the distance from the match, the shared interest, etc.
As for any modelling problem, understanding the priorities and setting the objective function right is the most important step. Since the matching problem is essentially an optimisation problem, we could use optimisation techniques to find an optimal matching and include any optimisation criteria we want. Heuristic optimisation algorithms can be used to solve these types of problem. They are agnostic to whether the loss function is differentiable or not and they can find optimal matching.
Matching for good and the story of the kidney donors
Still the Galey-Shapley algorithm has proven very useful. For example, people in need of a kidney transplant do not alway find a donor. Even when friends and family are willing to be donors, they are not necessarily a match, due to the different criteria for a good match (blood type, etc). With the matching algorithm, patients in need of a kidney transplant were matched with donors from other patients, creating a virtuous cycle of giving and receiving.
Is it the same Shapley?
If you are a fellow machine learning practitioner, the name Shapley might have rung a bell. You probably have heard of the shap method or shapley value. This method uses game theory to explain how a machine learning algorithm takes decision (local method). Wait is it the same guy? Indeed, the Shapley value was introduced by Lloyd Shapley! What a small and mathematically intertwined beautiful world we live in.