# Matching algorithm

I'm writing an application which divides a population of users into pairs for the purpose of performing a task together. Each user can specify various preferences about their partner, e.g.

• gender
• language
• age
• location (typically, within X miles/kilometers from where the user lives)

Ideally, I would like the user to be able to specify whether each of these preferences is a "nice to have" or a "must have", e.g. "I would prefer to be matched with a native English speaker, but I must not be matched with a female".

My objective is to maximise the overall average quality of the matches. For example, assume there are 4 users in the system, A, B, C, D. These users can be matched in 3 ways:

Option 1     Match Score
A-B           5
C-D           4
---
Average       4.5

Option 2     Match Score
A-C           2
B-D           3
---
Average       2.5

Option 3     Match Score
A-D           1
B-C           9
---
Average       5


So in this contrived example, the 3rd option would be chosen because it has the highest overall match quality, even though A and D are not very well matched at all.

Is there an algorithm that can help me to:

• calculate the "match scores" shown above
• choose the pairings that will maximise the average match score (while respecting each user's absolute constraints)

It is not absolutely necessary that each user is matched, so given a choice between significantly lowering the overall quality of the matches, and leaving a few users without a match, I would choose the latter.

Obviously, I would like the algorithm that calculates the matches to complete as quickly as possible, because the number of users in the system could be quite large.

Finally, this system of computing match scores and maximizing the overall average is just a heurisitic I've come up with myself. If there's a much better way to calculate the pairings, please let me know.

## Update

The problem I've described seems to be a similar to the stable marriage problem for which there is a well-known solution. However, in this problem I do not require the chosen pairs to be stable. My goal is to choose the pairs so that the average "match score" is maximized

• Hungarian algorithm can be applied to bipartite graphs. I think Edmond's matching algorithm would be more convinient for this problem. for an implementation: xs4all.nl/~rjoris/maximummatching.html – Arman Jan 31 '11 at 18:40
• If the objective function to maximize is the sum of the score of each match, the problem is called “maximum weighted matching in general graphs” (Wikipedia). If you really want to maximize the average score of a match, then it is always the optimal to choose only one match (with the maximum score). The problem is underspecified if you want something in between. – Tsuyoshi Ito Feb 1 '11 at 4:37
• One option is to consider maximum weight matching among all matchings of a given cardinality k which should be also doable in polynomial time. Once you guess k the question of sum and average goes away and it may also be helpful to consider different values of k. – Chandra Chekuri Feb 1 '11 at 17:48
• @Arman: Chandra didn't mean "find all matchings." But for finding a max-weight matching of cardinality k, in the graph terminology, if you have an n-vertex graph G, you add n-2k extra vertices and edges between these n-2k vertices and the n vertices in G (with edge-weight all one, say). Then, in any perfect matching of the new graph, n-2k vertices in G are matched with n new vertices, and 2k vertices in G are matched within G. So a max-weight perfect matching in the new graph gives a max-weight matching of cardinality k in G. – Yoshio Okamoto Feb 2 '11 at 14:33
• If you have a numerical penalty for unmatched vertices, then you can adapt the max-weight perfect matching algorithm to find the best possible matching with penalties, along the same lines as Yoshio explained above. Add a bunch of extra vertices to absorb unmatched vertices in G, put 0 weight on edges between the extra vertices, and put the penalty on edges between vertices in G and the extra vertices. – Peter Shor Feb 5 '11 at 13:49