Reference no: EM13103456

Implementation of both the algorithms using C/C++ code 1. roommates problem 2. Intern Problem

1. The Roommate Problem

The roommate problem involves a single set of agents of even cardinality n, each agent having a preference list over the other n - 1 agents. A stable matching in this case is a partition of this single set into n/2 pairs so that no two unmatched members both prefer each other over their partners under the matching. There exist instances of the roommate problem (both with and without ties) for which no stable matching exists. One such instance is due to Gale and Shapley [l], Example 1.1:

Anyone assigned to 4 will find a person whom he prefers and who prefers him.

An efficient algorithm to constructively determine for any instance of the roommate problem without ties whether a stable assignment exists (and if one exists to determine one) has recently been discovered by Irving [3]. This algorithm is dependent on properties of the roommate problem that hold only for the case without ties. A result of this paper, to be demonstrated in Section 2 is that this dependency is unavoidable. When ties are allowed, the roommate problem is NP-complete.

The marriage problem is a special case of the roommate problem. Every instance I of the marriage problem can be converted to an instance of the roommate problem by adding to the bottom of the preference list of every agent A of I a list of the agents of the same gener as A (other than A itself) in arbitrary order. It is easy to see that the set of stable matchings of this generated instance of the roommate problem coincides with the set of stable matchings of the original marriage problem.

2. The Intern Assignment Problem (IAP)

The intern assignment problem is merely the polygamous form of the marriage problem, in which the members of one of the geners can take on up to a (preset) number of partners of the opposite gender. An algorithm that solves this problem, called the NIMP (National Internship Matching Program) algorithm, has been used since 1953 to assign graduating medical students as interns in hospitals throughout the United States (hence the name of the problem). The NIMP algorithm can be considered a generalization of the Gale-Shapley method. A description of the method and a history of this program can be found in Roth [9].

Formally stated, the intern assignment problem is a stable matching problem where a set of interns are assigned to a set of hospitals. Each
hospital has a preset number of positions it wants to fill and a priority list that ranks the interns in accordance with its preferences over whom to hire to fill those positions. Note that since a hospital's preferences are one- dimensional, one should regard these multiple positions as identical. Different sections in the same hospital should be considered as different hospitals in this scheme. A hospital can rank in its preference list the possibility of leaving a position unassigned over being assigned to some of the interns.

On the other hand, each of the interns has a preference list over the hospitals that specifies which hospitals the intern would like to be assigned to. An intern can rank in his preference list the possibility of remaining unassigned to any one among a list of undesired hospital positions.

An assignment of interns to hospitals is unstable if one of the following holds:

There exists a hospital or an intern that prefers to remain unassigned rather than accept the assignment under the matching; or There exist a hospital and an intern such that the intern prefers that hospital over the one to which the intern had been assigned and the hospital prefers that intern over the current assignment of that position.

As mentioned, the marriage problem is a special case of the intern assignment problem. An instance of the marriage problem is an instance of the intern assignment problem. The difference is that the options of polygamy and not assigning some of the agents are not used.