Does there always exist a perfect matching with no strong

Assignment Help Computer Engineering

Reference no: EM132135995

Question

The Stable Matching Problem, as discussed in the text, assumes that all men and women have a fully ordered list of preferences. In this problem we will consider a version of the problem in which men and women can be indifferent between certain options. As before we have a set M of n men and a set W of n women. Assume each man and each woman ranks the members of the opposite gender, but now we allow ties in the ranking.

For example (with n = 4), a woman could say that m1 is ranked in first place; second place is a tie between m2 and m3 (she has no preference between them); and m4 is in last place. We will say that w prefers m to m0 if m is ranked higher than m0 on her preference list (they are not tied). With indifferences in the rankings, there could be two natural notions for stability. And for each, we can ask about the existence of stable matchings, as follows.

1 1. A strong instability in a perfect matching S consists of a man m and woman w, such that each of m and w prefers the other to their partner in S. Does there always exist a perfect matching with no strong instability?

Either give an example of a set of men and women with preference lists for which every perfect matching has a strong instability; or give an algorithm that is guaranteed to find a perfect matching with no strong instability and prove the guarantee.

2. A weak instability in a perfect matching S consists of a man m and a woman w such that their partners in S are w 0 and m0 , respectively, and one of the following holds:

• m prefers w to w 0 , and either w prefers m to m0 or is indifferent; or

• w prefers m to m0 , and m either prefers w to w 0 or is indifferent.

In other words, the pairing between m and w is either preferred by both, or preferred by one while the other is indifferent. Does there always exist a perfect matching with no weak instability?

Either give an example of a set of men and women with preference lists for which every perfect matching has a weak instability; or give an algorithm that is guaranteed to find a perfect matching with no weak instability and prove the guarantee.

Reference no: EM132135995

Questions Cloud

Write a main function that declares an array of 100 doubles : In a for loop, assign each of the doubles a random number between 0.50 and 50.00. Here's how. array[i] = (double) (rand() % 100 + 1) / 2.0;

Determine the internal rate of return for a project : Determine the internal rate of return for a project that costs -$149,500 and would yield after-tax cash flows of $23,000 the first year

What was the strategy used in the case : What improvements could you offer as an IT leader managing the strategy for the situation covered by the case?

The task is to remove suffix from last name column : The task is to remove suffix from last name column (e.g. Smith Sr. or Stevens Jr.) and put into the preexisting suffix column in the DB.

Does there always exist a perfect matching with no strong : Does there always exist a perfect matching with no strong instability? Does there always exist a perfect matching with no weak instability?

Eliminate the problem and turn the initiative into a success : Explore and elaborate on this reason for failure. Provide a solution that will eliminate the problem and turn the initiative into a success

Write a program that lets the user enter the initial height : Write a program that lets the user enter the initial height of the ball and the number of times the ball is allowed to continue bouncing.

Write function called closer_root that takes two numbers : Write another function called closer_root that takes two real numbers and returns the one whose square root is closer to the number 10.

Write a function to determine the squareroot of a number : Write a function to determine the squareroot of a number. The squareroot of a number can be approximated by repeated calculation using the formula.

User Account

All Pages