0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Discrete lizard Mar 13 '18 at 9:59
  • $\begingroup$ 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. $\endgroup$ – user40247 Mar 13 '18 at 18:02
1
$\begingroup$

Use an algorithm for bipartite matching.

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$.

Now find a maximum matching in this bipartite graph. The set of edges in that matching will be exactly what you want.

This does allow one user to be matched to multiple other users: for instance, the vertex (User 1, Apples) might be matched to the vertex User 2, and the vertex (User 1, Bananas) might be matched to the vertex User 3.

$\endgroup$
  • $\begingroup$ Thanks for the detailed response D.W. What about an instance were a new user, User 7, is added to the pool. User 7 is placed on the right side along with User 2 and User 3. User 7 has grapes and wants a banana, would the maximum matching algorithm allow for User 3 and User 7 to be paired with User 1 who has a banana on the left hand side? $\endgroup$ – user40247 Mar 13 '18 at 19:59
  • $\begingroup$ @user40247, no. In the algorithm I describe, the assumption is that User 1 has one banana, and can only give it to a single user. If that's not what you intended in your question to state your problem more clearly, please edit your question, as that's not specified in the question. An example is not a substitute for a clear problem specification. $\endgroup$ – D.W. Mar 13 '18 at 20:06
  • $\begingroup$ Ok, I see. Will look more into this. Thanks for the help. $\endgroup$ – user40247 Mar 13 '18 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.