1
$\begingroup$

The Gale-Shapley algorithm is an established algorithm that finds an optimal one-to-one match between two groups, each individual of which has a preference for the individuals in the other group (the "stable marriage market problem"). The algorithm has been further extended for one-to-many matchings, often called the college admissions problem. In this example, applicants with preferences for certain colleges are optimally matched with colleges that have preferences over applicants and that also have a certain number of vacancies to fill that can be more than one.

Are there further extensions to this algorithm to optimally match many-to-many relationships?. For illustration, I would like to match projects to sources of funds, where a project might receive funding from multiple sources; and a source of funding may be able to fund more than one project. To use the college admissions analogy, this would be the same as specifying a student to attend one or more colleges whilst a college may accept one or more students.

A further extension of this concept would be to encode inclusivities (e.g., fund A must always be used with fund B), exclusivities (e.g., if project A is funded then project B must not be funded), but these added complexities first need the many-to-many algorithm described above.

$\endgroup$
2
  • 3
    $\begingroup$ You should perhaps read through David Manlove's book "Algorithmics of Matching Under Preferences", see for instance optimalmatching.com/AMUP . $\endgroup$ – Gamow Nov 9 '20 at 17:06
  • $\begingroup$ A search turns up "stable many-to-many matchings with contracts": hbs.edu/faculty/Publication%20Files/… $\endgroup$ – usul Nov 17 '20 at 23:55
1
$\begingroup$

I am unsure about matchings of many to many as I haven't seen much of that in the literature but for your extension of exclusivity you may want to look at matching with incomplete lists. This changes the definition of a blocking pair such that they must also find each other acceptable. You could use that to set an agent with only one other agent in its preference list, the result of this would have the agent be unmatched or matched with the agent it ranks. Maybe if many companies can be assigned to one project you could consider this an adaptation of Stable Roommates problem? Where the room is the project and the companies are the people that occupy it. If you want to look further into this I suggest you research: Stable Matching with incomplete lists (SMI) Stable Roommates (SR) Stable roomates with incomplete lists (SRI)

Best of luck!

$\endgroup$

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.