Stable Marriage problems Problem 4. (10 points) Let I be an instance of STABLEMA

Question

Stable Marriage problems

Problem 4. (10 points) Let I be an instance of STABLEMARRIAGE with all men having identical preference lists. Show that I has exactly one stable matching Problem 5. (10 points) For STABLEMARRIAGE what is the minimum and maximum number of proposals Propose-Dispose will perform for N 2, N = 3, N = 4, and for an arbitary value of N? Find an instance that achieves the minimum. Show that no other instance can be less. Find an instance that achieves the maximum. Show that no other instance can be greater Problem 6. (10 points) For the STA BLEMARRIAGE problern with n = 2 (two men and two women) is it possible for all matchings to be stable? What if n 3? For each question either state yes and give an instance with al matches stable or state no and prove it cannot occur.

Explanation / Answer

Solution:

The first question is done as per Chegg guidelines, please repost others.

4)

If I is an instance of StableMarriage then at I = 1

There is only one matching since one man and one women is there

This means that one stable matching

preference list contain only one women.

at I= 2.

Since the preference list for men is same

let's say for man A(1, 2), then for B as well it will be (1, 2)

and if the womwn preference is (B, A), and (A, B)

there is a certainity of one stablke matching

similarly for evry I there is one stable matching.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.