Introduction to Graph Matching

Given a graph G(V,E), a matching is a subgraph in G if each vertex has a degree one. No edge shares a vertex with another edge.

Size of a matching

Size of a matching is equal is to the number of edges present in the matching.

Perfect Matching

A matching is called perfect if it contains all the vertices present in the graph. Perfect matching is also known as Complete matching.

Bipartite graphs

A bipartite graph is a graph whose vertices can be divided into
two disjoint sets such that no edge connects two vertices of the same set.

Bipartite graph or Bigraph is a graph whose vertices can be divided into 2 disjoint sets such that no 2 vertices belonging to the same set have an edge between them.
A balanced bipartite is said to be graph which as equal number of vertices in both the sets.

Introduction to Stable Matching

You need to associate or match elements of one set with the elements of another set keeping in mind individual preferences. A well known example of stable matching is hospital residents problem which matches certain students to their choice of medical program keeping in mind the merit list of each program.
Another example is the stable roommates problem which assigns roommates to a group of students such that their individual preferences are satisfied. Friends should stay together and frenemies should stay away.
Stable marriage problem is another such example in which plays the role of a matchmaker and pairs couples such that each one gets to marry the person of their choice. Rogue couples must be avoided. A rogue couple is a matching of a man and a woman such that they prefer someone else over the person they are presently paired with.

A stable matching is a matching with no rogue couples. Gale Shapley Algorithm produces a stable matching. The algorithm takes at most N(N-1)+1 rounds.

Stable marriage problem:
A person’s optimal mate is that person’s favorite from the realm
of possibility.
A person’s pessimal mate is that person’s least favorite from the
realm of possibility.
Some shocking results:

• The algorithm pairs every man with his optimal mate!
• The algorithm pairs every woman with her pessimal mate!

Let's discuss some problems on stable matching in detail. These will give us a good idea about the kind of problems belonging to this domain and their appropriate solutions. We will mainly be discussing 3 problems:

• Stable Marriage Problem (Gale Shapley Algorithm)
• Stable Roommates Problem (Irving's Algorithm)
• Hospital Residents Problem

Other Applications of Stable Matching

• Apart from the above mentioned problems, stable matching is widely used in many resource allocation problems. It has also been used in economic sciences: "for the theory of stable allocations and practice of market design".
• Another wide scale application is in assigning servers to users across the internet. Content delivery networks, responsible for delivery of information or data across the worls use stable matching algorithms to match users to servers. This is done to minimize the cost of connection and improve efficiency. A user prefers a server that provides a fast response and a server prefers to serve users at a lower cost.

Stable marriage problem

Let us discuss discuss the problem first:
We have 2 sets of people:

• The first set contains females.

• The second set contains males.
  Each person in each set has a list of preferences which includes all the people from the opposite set. That is, every woman in the set has a preference list that contains all the men in the other set. Similarly, every man has a preference list that contains all the women in the other set.

• We assume that females can be matched to only males and vice versa.

• Also, there is no male who also identifies as female and no female identifies as male.

• A person can be of the same preference to many people in the opposite set i.e A woman named QWERTY may be the first preference of 2 men Adelson and Velskii.

• The preferences are not reciprocated i.e If Qwerty is the first preference of Velskii, but Velskii need not be Qwerty's first preference.

Under these conditions, we need to perform a matching so that every person is engaged to his/her most preferable choice.
Before going on to solving this problem, we need to choose the proposers' side i.e the people who will be proposing to the other set.
The result obtained might vary slightly on this choice, but both the results will be stable matchings even if they are not the same.

Now that we have a clear idea about the problem, let's look at the possible solution. Gale Shapley algorithm is used to solve the stable marriage problem efficiently. We discuss that next.

Gale Shapley Algorithm

1. All individuals have ranked members of opposite set in order of preference.
2. One of the 2 sets is chosen to make proposal.(Either set will produce stable matchings)
3. One individual from the proposing group who is not already engaged will propose to their most preferable option who has not already rejected them.
4. The person being proposed to will

• Accept if this is their first offer.
• Reject if this is worse than their current offer
• Accept if this is better than their current offer.In this case they will jilt their previous offer.

5. When all members of proposing group are matched the loop terminates.The currently engaged pairs are stably matched.

Next, we discuss a small example which improve our understanding of the above mentioned algorithm.

Example

Males = {A,B,C}
Females = {X,Y,Z}
And following is their preference list:

A	B	C
X	X	Y
Y	Z	Z
Z	Y	X

x	Y	Z
B	B	C
A	C	A
C	A	B

To find the stable matching for the information, we use Gale Shapley Algorithm. The algorithm undergoes 3 iterations which is equal to the number of people in the proposing group. We also switch the proposing group to get another matching for the same set of data. This confirms the matching for both sides.

For a more detailed discussion on this algorithm(with example), refer to this link.

Advantages and disadvantages

Advantages

• Gives the best match possible to the proposing group
• Follows the concept of 'Luck favours the brave'. The goup that takes initiative and pursues it, gets the top choice.

Disadvantages

• Highly sensitive to the number of people involved in the matching. If a new pair is added to the matching, the entire matching can topple.
• Cannot be applied to unequal sized sets.

Stable Roommates Problem

The problem goes like this:
We are given an even-sized set in which each member has a preference list which consists of all other members of the set. We need to match the members of the set such that every member has his/her most preferred choice as their roommate. If such a matching exists, we say that a stable matching exists otherwise not.

To solve the Stable Roommates problem, Robert W. Irving developed an algorithm back in 1985.This algorithm has 2 phases :

1. Platonic Proposal
2. Rotation Elimination
   This algorithm helps in determing whether or not a stable matching exists and if it does what is it.

Irving's Algorithm

1. Participants order the other memebers by preference and then propose to everyone on their list in order continuing to the next person if their proposal is rejected.
2. A proposal is rejected when a person holds a proposal from someone they prefer. A proposal can also be rejected when a person of higher preference proposes and we reject the previously accepted offer.
3. If a person is the last preference of all others and is rejected by eveyone, a stable matching does not exist. An example of this is shown in the next section.
4. Phase one ends when everyone has made a proposal and received a proposal from someone else.
5. Now, we eliminate all the preferences which are lower than the one who's proposal has been accepted and symmetrically.
6. Next, we eliminate rotations. Check the detailed algorithm for that in the example mentioned below.
7. When all members have only one person remaining on their list, we stop. This is the stable roommates matching.

Example

Let us consider a set of 4 people {A,B,C,D} where A,D are females and B,C are males and following is their preference list :

A	B	C	D
C	A	D	B
B	C	B	A
D	D	A	C

We obtain the stable matching for this data as using Irving's algorithm: (A,B) and (C,D)

For a more detailed discussion on this algorithm(with example), refer to this link.

Advantages and disadvantages

Advantages

• Efficient: O(N^2) complexity
• Availability of software implementations on various platforms:Python, Java, R, MATLAB, Web App(Dyad Finder)

Disadvantages

• Long and complex

Hospital Residents Problem

This problem is quite close to stable marriage problem and we use an algorithm similar to gale shapley to solve this. The problem says:

We have two groups: Applicants and Programmes.

• Each member of the group will have a choice list. All the hospital programmes will release a choice list of the preferred applicants and all the applicants will also rank the programmes in their choice list. In this matching algorithm, it is not necessary to rank all the available options in the choice list, unlike stable matching problem. An applicant may rank a few programmes in his/her choice list and the programmes may choose to extend offers to only a few shortlisted applicants.
• Also, each programme announces certain number of vacancies beforhand and takes in only those many residents for that year.
• This algorithm is applicant proposing i.e it produces a matching based on the applicants preferred choice of programmes. Here, the proposing group is always the applicant group.
• For a match to occur both the applicant and the programme should rank each other.
  It may happen that an applicant is not matched to any programme and that a programme is left with vacant positions after the matching is completed. It is observed that applicants with more choices in the choice list have a higher probability of being matched to a residency programme. Similarly, programmes which have less shortlists may be left with vacant positions at the end of the matching.

Example

We have 5 applicants {Anthony,Samantha,Jos,Lara,Darry} and 3 programmes {City,Mercy,General} each with 2 vacancies.

The choice lists of applicants are as follows :

ANTHONY	SAMANTHA	JOS	LARA	DARRY
City	City	City	Mercy	City
-	Mercy	General	City	Mercy
-	-	Mercy	General	General

The choice lists of programmes are as follows :

MERCY	CITY	GENERAL
Darry	Darry	Darry
Jos	Anthony	Anthony
-	Samantha	Jos
-	Lara	Lara
-	Jos	-

Using this algorithm, the final matches obtained are:

• Anthony - City
• Darry - City
• Jos - General
• Lara - General
• Samantha is left unmatched.

For a more detailed discussion on this algorithm(with example), refer to this link.

Other variations

• Stable matching with indifference: Some women may be indifferent between 2 or more men. Similarly, some men may also be indifferent between 2 or more women. This means a that a person can have no top preference or that the top preference is shared between 2 or more people.

• Hospital Residents problem with couples: This problem takes into account couples who might be applying for the residency program and would like to get into the same program so as to stay together.

• Assignment problem: The problem has a number of agents and a number of tasks. A task is to be assigned to any agent such that the costincurred is minimum. This problem requires a maximum weighted match of the bipartitie graph (of agents and tasks) and might not require a stable match.