# What is the best algorithm for multiple matches?

What is an algorithm that can find the best possible matches given a set of data. I have read up on stable roommates problem and or stable marriage problems. However, from my understanding, these type of algorithms only output a specific match (pairings) and not a set of possible matches. For example, say we have a group of users each with a desire to trade one particular fruit for another.

[] - Has/Have
() - Wants

User 1:
[Apples, Bananas]
(Grapes)

User 2:
[Bananas, Grapes, Peaches]
(Apples)

User 3:
[Grapes, Oranges]
(Bananas)

User 4:
[Mango, Pineapple]
(Strawberry)

User 5:
[Raspberry]
(Pineapple)

User 6:
[Pineapple]
(Raspberry)


In this scenario, matches should be (->)

     User 1 -> (User 2 and User 3)
User 2 -> (User 1)
User 3 -> (User 1)
User 4 -> None
User 5 -> (User 6)
User 6 -> (User 5)


Irving's algorithm requires that a solution have a unique pairing. What is an algorithm that could give me a solution set like above?

• I don't think you really want to find a list of all possible matchings. But what do you want? What does 'User 2 and User 3' really mean here? I think what you're looking for isn't a matching over 'Users', but rather a matching over the items on the one hand and the 'desires' on the other hand. On that graph, you don't need a full matching, but I guess a matching such that most 'desires' are fulfilled is something that might be what you want. Can you confirm whether my reasoning applies to your problem? – Discrete lizard Mar 13 '18 at 9:59
• User 2 and 3 are essentially people. I would like to find multiple matches if they exist. You have the right idea behind what you explained. Thats another way of looking at it. Another way of looking at it is like looking for trading partner. – user40247 Mar 13 '18 at 18:02

Build a graph with one left-vertex per (user, fruit that user has) pair. For instance, in the example above, we'd have one vertex for (User 1, Apples) and another vertex for (User 1, Bananas). Add one-right vertex per user. Draw an edge from (user $i$, $f$) to user $j$ if user $i$ has fruit $f$ and user $j$ wants fruit $f$.