• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q60E

Expert-verified
Found in: Page 204

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Suppose we have three men ${m}_{1},{m}_{2}\text{, and}{m}_{3}$ and three women ${w}_{1},{w}_{2},\text{and}{\mathrm{w}}_{3}$ . Furthermore, suppose that the preference rankings of the men for the three women, from highest to lowest, are ${m}_{1}:{w}_{3},{w}_{1},{w}_{2};{m}_{2}:{w}_{1},{w}_{2},{w}_{3};{m}_{3}:{w}_{2},{w}_{3},{w}_{1}$ and the preference rankings of the women for the three men, from highest to lowest, are ${w}_{1}:{m}_{1},{m}_{1},{m}_{3};{w}_{2}:{m}_{2},{m}_{1},{m}_{3};{w}_{3}:{m}_{3},{m}_{2},{m}_{1}$ . For each of the six possible matchings of men and women to form three couples, determine whether this matching is stable.

First matching: ${m}_{1}-{w}_{1},{m}_{2}-{w}_{2},{m}_{3}-{w}_{3}$ is stable.

Second matching: ${m}_{1}-{w}_{1},{m}_{2}-{w}_{3},{m}_{3}-{w}_{2}$ is not stable.

Third matching: ${m}_{1}-{w}_{2},{m}_{2}-{w}_{1},{m}_{3}-{w}_{3}$ is not stable.

Fourth matching: ${m}_{1}-{w}_{2},{m}_{2}-{w}_{3},{m}_{3}-{w}_{1}$ is not stable.

Fifth matching: ${m}_{1}-{w}_{3},{m}_{2}-{w}_{1},{m}_{3}-{w}_{2}$ is stable.

Sixth matching: ${m}_{1}-{w}_{3},{m}_{2}-{w}_{2},{m}_{3}-{w}_{1}$ is not stable.

See the step by step solution

## Step 1:

We have given three men: ${m}_{1},{m}_{2},{m}_{3}$ and three women ${w}_{1},{w}_{2},{w}_{3}$ .

For stable matching, we have:

$\begin{array}{r}{m}_{1}:{w}_{3}>{w}_{2}>{w}_{1}\\ {m}_{2}:{w}_{1}>{w}_{2}>{w}_{3}\\ {m}_{3}:{w}_{2}>{w}_{3}>{w}_{1}\end{array}$

And

$\begin{array}{r}{w}_{1}:{m}_{1}>{m}_{2}>{m}_{3}\\ {w}_{2}:{m}_{2}>{m}_{1}>{m}_{3}\\ {w}_{3}:{m}_{3}>{m}_{2}>{m}_{1}\end{array}$

## Step 2:

Now, we will have six possible matching; we will check whether they are stable or unstable.

First matching: ${m}_{1}-{w}_{1},{m}_{2}-{w}_{2},{m}_{3}-{w}_{3}$ .

This is stable because all the women assigned their preferred partners.

Second matching: ${m}_{1}-{w}_{1},{m}_{2}-{w}_{3},{m}_{3}-{w}_{2}$ .

This is not stable because ${m}_{2}$ prefers ${w}_{2}$ over his current partner and ${w}_{2}$ prefers ${m}_{2}$ over her current partner.

Third matching: ${m}_{1}-{w}_{2},{m}_{2}-{w}_{1},{m}_{3}-{w}_{3}$ .

This is not stable because ${m}_{1}$ prefers ${w}_{1}$ over his current partner and ${w}_{1}$ prefers ${m}_{1}$ over her current partner.

## Step 3:

Fourth matching: ${m}_{1}-{w}_{2},{m}_{2}-{w}_{3},{m}_{3}-{w}_{1}$ .

This is not stable because ${m}_{1}$ prefers ${w}_{1}$ over his current partner and ${w}_{1}$ prefers ${m}_{1}$ over her current partner.

Fifth matching: ${m}_{1}-{w}_{3},{m}_{2}-{w}_{1},{m}_{3}-{w}_{2}$ .

This is stable because all the men assigned their preferred partners.

Sixth matching: ${m}_{1}-{w}_{3},{m}_{2}-{w}_{2},{m}_{3}-{w}_{1}$ .

This is not stable because ${m}_{3}$ prefers ${w}_{3}$ over his current partner and ${w}_{3}$ prefers ${m}_{3}$ over her current partner.

## Step 4:

Hence, we have

First matching: ${m}_{1}-{w}_{1},{m}_{2}-{w}_{2},{m}_{3}-{w}_{3}$ is stable.

Second matching: ${m}_{1}-{w}_{1},{m}_{2}-{w}_{3},{m}_{3}-{w}_{2}$ is not stable.

Third matching: ${m}_{1}-{w}_{2},{m}_{2}-{w}_{1},{m}_{3}-{w}_{3}$ is not stable.

Fourth matching: ${m}_{1}-{w}_{2},{m}_{2}-{w}_{3},{m}_{3}-{w}_{1}$ is not stable.

Fifth matching: ${m}_{1}-{w}_{3},{m}_{2}-{w}_{1},{m}_{3}-{w}_{2}$ is stable.

Sixth matching: ${m}_{1}-{w}_{3},{m}_{2}-{w}_{2},{m}_{3}-{w}_{1}$ is not stable.