In this section, we consider an interesting version of bipartite matching called the stable marriage problem. Consider a set Y = {m1, m2, . . . , mn} of n men and a set X = {w1, w2, . . . , wn } of n women.

**The Stable Marriage Problem**

In this section, we consider
an interesting version of bipartite matching called the stable marriage
problem. Consider a set ** Y** = {

A *marriage matching*** M** is a set of

**
**is paired with exactly one woman

and ** X** as vertices of a complete bipartite graph with
edges connecting possible marriage partners, then a marriage matching is a
perfect matching in such a graph.)

A pair ** (m, w),** where

Surprisingly, this problem
always has a solution. (Can you find it for the instance in Figure 10.11?) It
can be found by the following algorithm.

**Stable
marriage algorithm**

Input: A set of ** n** men and a set of

Output: A stable marriage
matching

**Step 0 **Start with all the men and women being free.

**Step 1 **While there are free men, arbitrarily select one of them and do the** **following:

*Proposal *The selected free man* **m** *proposes to* **w,** *the next* *woman on his preference list (who is the highest-ranked woman who
has not rejected him before).

*Response *If* **w** *is free, she accepts the
proposal to be matched* *with ** m**. If she is not free, she compares

**Step 2 **Return the set of** ***n*** **matched pairs.

Before we analyze this
algorithm, it is useful to trace it on some input. Such an example is presented
in Figure 10.12.

Let us discuss properties of
the stable marriage algorithm.

**THEOREM
**The
stable marriage algorithm terminates after no more than** n**

**PROOF
**The
algorithm starts with** n **men having the total of

Let us now prove that the
final matching ** M** is a stable marriage
matching. Since the algorithm stops after all the

The stable marriage algorithm
has a notable shortcoming. It is not “gender neutral.” In the form presented
above, it favors men’s preferences over women’s preferences. We can easily see
this by tracing the algorithm on the following instance of the problem:

The algorithm obviously
yields the stable matching ** M** = {(man 1, woman 1), (man 2,
woman 2)}. In this matching, both men are matched to their first choices, which
is not the case for the women. One can prove that the algorithm always yields a
stable matching that is

There is another important
corollary to the fact that the stable marriage algorithm always yields a
gender-optimal stable matching. It is easy to prove that a man (woman)-optimal
matching is unique for a given set of participant preferences. Therefore the
algorithm’s output does not depend on the order in which the free men (women)
make their proposals. Consequently, we can use any data structure we might
prefer—e.g., a queue or a stack—for representing this set with no impact on the
algorithm’s outcome.

The notion of the stable
matching as well as the algorithm discussed above was introduced by D. Gale and
L. S. Shapley in the paper titled “College Admissions and the Stability of
Marriage” [Gal62]. I do not know which of the two applications mentioned in the
title you would consider more important. The point is that stability is a
matching property that can be desirable in a variety of applications. For
example, it has been used for many years in the United States for matching
medical-school graduates with hospitals for residency training. For a brief
history of this application and an in-depth discussion of the stable marriage
problem and its extensions, see the monograph by Gusfield and Irwing [Gus89].

**Exercises 10.4**

Consider an instance of the
stable marriage problem given by the following ranking matrix:

For each of its marriage
matchings, indicate whether it is stable or not. For the unstable matchings,
specify a blocking pair. For the stable matchings, indicate whether they are
man-optimal, woman-optimal, or neither. (Assume that the Greek and Roman
letters denote the men and women, respectively.)

**
**Design a simple algorithm for checking whether a given marriage
matching is stable and determine its time efficiency class.

**
**Find a stable marriage matching for the instance given in Problem 1
by apply-ing the stable marriage algorithm

**
**in its men-proposing version.

**
**in its women-proposing version.

Find a stable marriage
matching for the instance defined by the following ranking matrix:

**
**Determine the time-efficiency class of the stable marriage
algorithm

**
**in the worst case.

**
**in the best case.

**
**Prove that a man-optimal stable marriage set is always unique. Is
it also true for a woman-optimal stable marriage matching?

**
**Prove that in the man-optimal stable matching, each woman has the
worst partner that she can have in any stable marriage matching.

**
**Implement the stable-marriage algorithm given in Section 10.4 so
that its running time is in *O(n*^{2}** ).** Run an experiment to ascertain its
average-case efficiency.

**
**Write a report on the ** college admission problem**
(residents-hospitals assign-ment) that generalizes the stable marriage problem
in that a college can accept “proposals” from more than one applicant.

**
**Consider the ** problem of the roommates**, which is
related to but more difficult than the stable marriage problem: “An even number
of boys wish to divide up into pairs of roommates. A set of pairings is called
stable if under it there are no two boys who are not roommates and who prefer
each other to their actual roommates.” [Gal62] Give an instance of this problem
that does

**SUMMARY**

The *iterative-improvement technique* involves finding a solution to an
op-timization problem by generating a sequence of feasible solutions with
improving values of the problem’s objective function. Each subsequent so-lution
in such a sequence typically involves a small, localized change in the previous
feasible solution. When no such change improves the value of the objective
function, the algorithm returns the last feasible solution as optimal and
stops.

Important problems that can
be solved exactly by iterative-improvement algorithms include linear
programming, maximizing the flow in a network, and matching the maximum
possible number of vertices in a graph.

The *simplex method* is the classic method for solving the general linear
programming problem. It works by generating a sequence of adjacent extreme
points of the problem’s feasible region with improving values of the objective
function.

The *maximum-flow problem* asks to find the maximum flow possible in a
network, a weighted directed graph with a source and a sink.

The *Ford-Fulkerson method* is a classic template for solving the
maximum-flow problem by the iterative-improvement approach. The *shortest-augmenting-path method *implements
this idea by labeling network vertices* *in
the breadth-first search manner.

The Ford-Fulkerson method
also finds a *minimum cut* in a given
network.

A *maximum cardinality matching* is the largest subset of edges in a
graph such that no two edges share the same vertex. For a bipartite graph, it
can be found by a sequence of augmentations of previously obtained matchings.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Iterative Improvement : The Stable Marriage Problem |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.