Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

first dropping the link that will serve as reference: NRMP Residency Matching

I have a sort of side project (nothing riding on it, computational performance not an issue, so feel free to go wild, I love learning new things) and I am attempting to match members of group L to members of group B. All members will provide a list (potentially incomplete) of the members in the other group, ordered by preference (ranked list). The groups are not necessarily equal in size, with B generally being larger than L.

Potential Twist!: How about allowing each other member of group B to provide a list of who they consider as best Li for Bi (best member of group L for each member of group B)? Does this make the situation more interesting? Yes, power play struggles by intentionally throwing off rankings would count as interesting here ;)

This, from my limited Googling due to near-zero domain knowledge, appears to be closely related to the Stable Marriage Problem, which appears to be the algorithm used in the above given NRMP algorithm.

Note I have already seen this question, which is close, but not quite right, with score versus rankings making it a completely different question (in my mind at least...is it?)

QUESTIONs:

  1. I am not well versed at formal mathematics at all (engineer here), so what is this type of problem called?
  2. What category does it fall under? (Graph, etc or is that what category a solution would fall under?)
  3. What concrete conclusions can we derive from the algorithm? (Is it optimal? -SMP is, but with differing sized groups, is it? Does order of members passed through the algorithm affect the outcome in any way?)
  4. Is there a better (more efficient in my circumstance, cooler, newer, technically outrageous but mathematically more interesting) way to do this? Implementing this is meant to be entertainment for me - real cool right? - so no restrictions really.

Thanks,

AK

P.S. A crazy idea I had - introducing a questionnaire, providing features that can then be used in a fuzzy classification system for matching???

EDIT: I've been lurking here a while and realize that people here are much smarter than me, so feel free to stretch the question's restrictions within reason and have fun with it. (IE a small group F overseeing the matching system may have more influence on the outcome in case of conflicts)

share|improve this question
add comment

1 Answer

Lots of good ideas here!

The general problem is called stable matching, usually stable bipartite matching (look up: bipartite graphs, matching on graphs). The Gale-Shapley algorithm that you mentioned is the original solution, but new variations are a current hot topic of research at the interface between computer science and economics. (In fact, last year Shapley shared the Nobel in Econ with Al Roth for work on matching such as the residency program.) I haven't read it, but probably a good reference would be Roth's book on the subject.

For current research on matching, you can check out publications or slides on Roth's page; someone else I know of who is active in this area is Itai Ashlagi. Recent matching models focuses on questions like, what if I introduce extra constraints (for instance, a married couple in the residency program want to go to the same city); or how do I update a matching as people arrive one by one.


So, the basic concept to keep in mind here is that agents are strategic and will cheat and lie to maximize their happiness. It's up to us to design a system where they can maximize their happiness (and we can maximize overall happiness) when they tell the truth.

The idea behind a stable matching is that, once we've matched everyone in B to someone in L and vice versa, there's no pair (b,l) who would like to "cheat" by getting rid of their assigned partners and matching to each other instead. If we think of matchings as marriages, there will never be any affairs because if person b is willing to cheat on their partner with person l, then person l is not willing to cheat on their partner with person b.

If we did not have strategic agents, we could think of a purely computer science problem: You have a bipartite graph with weights on the edges, and you want to find the matching (set of edges so that each vertex is picked at most once) with the maximum total weight. But this won't work for two reasons. First, it's hard to ask people to quantify how much they would like a particular partner (they'd just say a value of infinity). Second, they might not tell you the truth because lying could manipulate your algorithm into giving a better outcome. So we usually ask people to give a preference ordering and our solution concept is "stability" (the property I explained above).

Your suggestion for asking people's opinion about other's matchings doesn't seem at first glance to help, because one shouldn't know another's opinion as well as that person knows their own opinion. But maybe in some cases it would help.


That was all rambling, but let me try to answer your questions.

  1. Stable bipartite matching, usually, or the stable marriage problem.

  2. Algorithms, graph algorithms, game theory, computer science, economics.

  3. Right, so, this depends on your goals, solution concept, and model. Do you assume people can lie to you? If so, you're in a game theoretic setting and usually we look for stable matchings. However, there are multiple stable matchings (and in fact Gale-Shapley will produce the one that is overall optimal for the side that "proposes" in each round of the algorithm). It's not obvious how to select the best stable matching.

  4. I think the original Gale-Shapley matching algorithm will solve your problem as you described it, and I think it's still state-of-the-art for that basic problem (not positive though).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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