Question

2. A stable roommate problem with 4 students a, b, c, d is defined as follows. Each student ranks the other three in strict order of preference. 4 match- ing is defined as the separation of the students into two disjoint pairs. A matching is stable if no two separated students prefer each other to their current roommates. Does a stable matching always exist? If yes, give a proof. Otherwise give an example roommate preference where no stable matching exists.
0 0
Add a comment Improve this question Transcribed image text
Answer #1

Answer

A stable matching need not exist.Consider the following list of prefer-ences.Leta,b,call have d last on their list.Say a prefers b over c,b prefers c over a, and c prefers a over b. In every matching, one of a,b,c should be paired withdand the other two with each other. Now,d’sroommate and the one for whom d’s roommate is the first choice prefer to be with each other. Thus every matching is unstable no stable matching exists in this case.

Add a comment
Know the answer?
Add Answer to:
2. A stable roommate problem with 4 students a, b, c, d is defined as follows....
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • 2.        Early English courts a.        relied exclusively on Norman Law. b.        included courts of law and...

    2.        Early English courts a.        relied exclusively on Norman Law. b.        included courts of law and equity. c.         heard cases that only applied to the nobility. d.        were often subject to bribery. 4.        A legal precedent a.        is no longer valid 50 years after the case is decided. b.        is no longer valid 100 years after the case is decided. c.         cannot be overruled. d.        remains valid unless and until overruled by a later case or statute. 5.        Judicial...

  • Edit a C program based on the surface code(which is after the question's instruction.) that will...

    Edit a C program based on the surface code(which is after the question's instruction.) that will implement a customer waiting list that might be used by a restaurant. Use the base code to finish the project. When people want to be seated in the restaurant, they give their name and group size to the host/hostess and then wait until those in front of them have been seated. The program must use a linked list to implement the queue-like data structure....

  • What an Executive Summary Is An executive summary is a specific type of document that does...

    What an Executive Summary Is An executive summary is a specific type of document that does two things: it summarizes a research article, and it offers recommendations as to how information from the article can be used. Some long reports can contain an executive summary section, as indicated in the Pearson handbook. Write a 2 pahe Executive Summary In business contexts, an executive summary is always written for a specific purpose: to explain the information in the article to a...

  • Using the book, write another paragraph or two: write 170 words: Q: Compare the assumptions of...

    Using the book, write another paragraph or two: write 170 words: Q: Compare the assumptions of physician-centered and collaborative communication. How is the caregiver’s role different in each model? How is the patient’s role different? Answer: Physical-centered communication involves the specialists taking control of the conversation. They decide on the topics of discussion and when to end the process. The patient responds to the issues raised by the caregiver and acts accordingly. On the other hand, Collaborative communication involves a...

  • summarizr the followung info and write them in your own words and break them into different...

    summarizr the followung info and write them in your own words and break them into different key points.   6.5 Metering Chamber: 6.5.1 The minimum size of the metering box is governed by the metering area required to obtain a representative test area for the specimen (see 7.2) and for maintenance of reasonable test accuracy. For example, for specimens incorporating air spaces or stud spaces, the metering area shall span an integral number of spaces (see 5.5). The depth of...

  • summatize the following info and break them into differeng key points. write them in yojr own...

    summatize the following info and break them into differeng key points. write them in yojr own words   apartus 6.1 Introduction—The design of a successful hot box appa- ratus is influenced by many factors. Before beginning the design of an apparatus meeting this standard, the designer shall review the discussion on the limitations and accuracy, Section 13, discussions of the energy flows in a hot box, Annex A2, the metering box wall loss flow, Annex A3, and flanking loss, Annex...

  • 10. Write a one-page summary of the attached paper? INTRODUCTION Many problems can develop in activated...

    10. Write a one-page summary of the attached paper? INTRODUCTION Many problems can develop in activated sludge operation that adversely affect effluent quality with origins in the engineering, hydraulic and microbiological components of the process. The real "heart" of the activated sludge system is the development and maintenance of a mixed microbial culture (activated sludge) that treats wastewater and which can be managed. One definition of a wastewater treatment plant operator is a "bug farmer", one who controls the aeration...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT