0
$\begingroup$

Suppose that there is a program that matches newly hired employees to vacancies within an organization.

After interviewing all managers who have vacancies, applicants score (NOT RANK) the positions as either a 1 (Highly Interested), 2 (Interested), or 3 (Not Interested). The managers do the same thing.

I don't know how to explain this in formal terms, but with a fairly large group of people (~30) is there a way to maximize the number of matches where applicants who score positions as 1s are assigned to managers who rated them as 2s (and vice versa), but no applicant is assigned to a manager who rated them as a 3 or to a position that they scored as a 3?

This would reduce the number of managers and applicants who both get their first choice, but it would also reduce the number of cases where both parties get their second choice, which is preferable because of the potential negative impact on morale of having lots of 1-1, 2-2 pairings.

  • 0
    I thin you need two distinct steps. First you have to check that it is possible to have no applicant assigned to a manager who rated them as a 3 or to a position that they scored as a 3. Then you can do your optimisation; one approach might be to see if you can move to a "better" solution by swapping a small number of people around, though this may not find a global optimum.2012-05-11

1 Answers 1

1

As suggested by Henry, you need to do this in two step.

First, verify that a solution exist. You can do that check if a perfect matching exist in the bipartite match with every applicants/manager is a node and every edge exist if both score are at least 2 (so no "not interested" in your matching). You can do that finding a maximum flow in the associate graph.

If this matching exist, you want to minimize the number of $(2,2)$ pair (or some other metrics), and you can do that finding a minimum cost maximum flow in that bipartite graph, using cost 1 for the 2,2 pair and 0 for every other match.

Check this link on wikipedia: max flow and maximum matching.

  • 0
    Also, do a search for "stable matching" or "stable marriage".2012-05-12