Consider a version of the stable matching problem where there are n students and n colleges...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Consider a version of the stable matching problem where there are n students and n colleges as before. Assume each student ranks the colleges (and vice versa), but now we allow ties in the ranking. In other words, we could have a school that is indifferent two students s₁ and s2, but prefers either of them over some other student s3 (and vice versa). We say a student s prefers college c₁ to c₂ if c₁ is ranked higher on the s's preference list and C₁ and c₂ are not tied. (a) Strong Instability. A strong instability in a matching is a student-college pair, each of which prefer each other to their current pairing. In other words, neither is indifferent about the switch. Does there always exist a matching with no strong instability? Either give an example instance for which all matchings have a strong instability (and prove it), or give and analyze an algorithm that is guaranteed to find a matching with no strong instabilities. (b) Weak Instability. A weak instability in a matching is a student-college pair where one party prefers the other, and the other may be indifferent. Formally, a students and a college c with pairs c' and s' form a weak instability if either • s prefers c to c' and c either prefers s to s' or is indifferent between s and s'. • c prefers s to s' and s either prefers c to c' or is indifferent between c and c'. Does there always exist a perfect matching with no weak instability? Either give an instance with a weak instability or an algorithm that is guaranteed to find one. Consider a version of the stable matching problem where there are n students and n colleges as before. Assume each student ranks the colleges (and vice versa), but now we allow ties in the ranking. In other words, we could have a school that is indifferent two students s₁ and s2, but prefers either of them over some other student s3 (and vice versa). We say a student s prefers college c₁ to c₂ if c₁ is ranked higher on the s's preference list and C₁ and c₂ are not tied. (a) Strong Instability. A strong instability in a matching is a student-college pair, each of which prefer each other to their current pairing. In other words, neither is indifferent about the switch. Does there always exist a matching with no strong instability? Either give an example instance for which all matchings have a strong instability (and prove it), or give and analyze an algorithm that is guaranteed to find a matching with no strong instabilities. (b) Weak Instability. A weak instability in a matching is a student-college pair where one party prefers the other, and the other may be indifferent. Formally, a students and a college c with pairs c' and s' form a weak instability if either • s prefers c to c' and c either prefers s to s' or is indifferent between s and s'. • c prefers s to s' and s either prefers c to c' or is indifferent between c and c'. Does there always exist a perfect matching with no weak instability? Either give an instance with a weak instability or an algorithm that is guaranteed to find one.
Expert Answer:
Answer rating: 100% (QA)
The image shows the following consider a version of the stable matching problem where there are n students and n colleges as before Assume each studen... View the full answer
Related Book For
Microeconomics An Intuitive Approach with Calculus
ISBN: 978-0538453257
1st edition
Authors: Thomas Nechyba
Posted Date:
Students also viewed these algorithms questions
-
Issued 48,000 shares of common stock in exchange for $480,000 in cash. 2. Purchased equipment at a cost of $76,000. $19,000 cash was paid and a note payable to the seller was signed for the balance...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...
-
The current auditor of CTT Company Limited (CTT), the largest property management group in Hong Kong, will resign after the nancial statements audit for the year ended 31 December 2021. Tony, a...
-
The profit- and loss-sharing agreement of the partnership of Ali, Bob, and Kia provides a salary allowance for Ali and Kia of $10,000 each. Partners receive a 10 percent interest allowance on their...
-
The Ethan Allen tour boat capsized and sank in Lake George, New York, and 20 of the 47 passengers drowned. Based on a 1960 assumption of a mean weight of 140 lb for passengers, the boat was rated to...
-
What organizational behavior issues are involved in this case?
-
List all the promotional mix elements used in the Pepsi Refresh campaign. What grade would you give PepsiCo on integrating these elements into an integration marketing communications campaign? This...
-
accounting help fro journal entries thank you please !
-
Situation Russell International, a publicly traded company, reacquired 500,000 shares of its common stock during July 2008 at a cost of $25 per share. The current market price of the stock was $20...
-
The ventral root of a spinal nerve contains a only sensory fibers b. only motor fibers ca ganglion d only afferent fibers e both sensory and motor fibers
-
Consider the two different project types below. For each project type, consider which areas of the Cost Management Plan would be most important, and explain your rationale for each in the space...
-
As set out in the company's organisational processes, you are also required to develop contingency plans to ensure that any risks to the success of goals of the operational plan are identified and...
-
que tecnicas y estrategias podemos usar para un plan de relanzamiento de la marca kellogs rice krispies?
-
This is not considered sexual abuse because there was no action on the caretaker's part. You could inform the parents that the child told you about viewing pornography in their home. Schedule a time...
-
Explain what farm-to-plate/table is to you. How does it positively affect our environment and economy? What do you do to try to be more farm-to-plate? Does a restaurant advertising Farm-to-plate draw...
-
The price-earnings ratio of a stock is given by R(PE)= P E where P is the price of the stock and E is the earnings per share. Recently, the price per share of a certain company was $33.59 and the...
-
Saccharin is an artificial sweetener that is used in diet beverages. In order for it to be metabolized by the body, it must pass into cells. Below are shown the two forms of saccharin. Saccharin has...
-
Subsistence Levels of Consumption: Suppose you are interested in modeling a policy issue involving poor households in an under-developed country. A: The households we are trying to model are...
-
Consider once again my tastes for Coke and Pepsi and my tastes for right and left shoes (as described in end-of-chapter exercise 6.2). A. On two separate graphs one with Coke and Pepsi on the axes,...
-
Scalping College Basketball Tickets: At many universities, college basketball is intensely popular and, were tickets sold at market prices, many students who wish to attend games would not be able to...
-
Part A: Green T Company, whose fiscal year ends December 31, completed the following transactions involving notes payable: 20x7 Nov. 25 Purchased a new loading cart by issuing a 60-day, 10 percent...
-
The management of Pzazz, Inc., took the following actions that went into effect on January 2, 20x7. Each action involved an application of the time value of money. a. Established in one payment of...
-
The Kow Long Products Company manufactures and sells wireless video cell phones, which it guarantees for five years. If a cell phone fails, it is replaced free, but the customer is charged a service...
Study smarter with the SolutionInn App