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 -&gt; (User 2 and User 3)
     User 2 -&gt; (User 1)
     User 3 -&gt; (User 1)
     User 4 -&gt; None
     User 5 -&gt; (User 6)
     User 6 -&gt; (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?
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.