Effect of changes in preferences

Assignment Help Basic Computer Science
Reference no: EM131220610

The Problem

This problem is inspired by a question raised by Devashish in class. As Devashish's question pointed out, the stable marriage problem does not handles "divorces." This is because we assume everyone is interested in everyone else of the opposite gender and we assume that the preferences do not change.

In this problem, we will see the effect of changes in preferences in the outcome of the Gale-Shapley algorithm (for this problem you can assume the version of the Gale-Shapley algorithm that we did in class where the women do all the proposing).

Given an instance of the stable marriage problem (i.e. set of men MM and the set of women WW along with their preference lists: LmLm and LwLw for every m∈Mm∈M and w∈Ww∈Wrespectively), call a man m∈Mm∈M a home-wrecker if the following property holds. There exists an L′mLm′ such that if mm changes his preference list to L′mLm′ (from LmLm) then the Gale-Shapley algorithm matches everyone to someone else. In other words, let SorigSorig be the stable marriage output by the Gale-Shapley algorithm for the original input and SnewSnew be the stable marriage output by the Gale-Shapley algorithm for the new instance of the problem where mm's preference list is replaced by L′mLm′ (but everyone else has the same preference list as before). Then Sorig∩Snew=∅Sorig∩Snew=∅.

For every integer n≥2n≥2 prove the following: There exists an instance of the stable marriage problem with nn men and nn women such that there is a man who is a home-wrecker.

Reference no: EM131220610

Questions Cloud

Presents the perfect opportunity to apply loops : Include a copy of the code that either (A) exemplifies concise, generalized code or (B) presents the perfect opportunity to apply loops, arrays, and lists to reduce the length of the program using a more elegant solution. Do not undertake a length..
What is the molecular mass of sodium bicarbonate : You get curious as you are weighing out the 2.25 moles and wonder how many molecules are there in your 2.25 moles of Sodium Bicarbonate sample. What is the molecular Mass of Sodium Bicarbonate?
Ratings for the bonds evaluations : Suppose these rating companies went out of business. - What effect would this have on the bond market? - What effect would it have on banks?
Developing an operating budget-theory and practice : Important to consider several outputs, which depend on the perspectives of the individuals developing the budget. There are certain best practices to keep in mind when developing budgets - Internet, research the value of budgeting as well as method..
Effect of changes in preferences : In this problem, we will see the effect of changes in preferences in the outcome of the Gale-Shapley algorithm (for this problem you can assume the version of the Gale-Shapley algorithm that we did in class where the women do all the proposing).
Is the encoded language regular : Show that if a language is regular over one alphabet, then it is still regular when encoded in a different alphabet, by any substitution code.
Recursive method written by you or taken from web : What elements should be considered to be included in any recursive method? Discuss these elements using an example (code required) of a recursive method written by you or taken from Web. Try choosing one different from that of any posted thus far.
National credit bureaus collect information on peoples : Suppose that a new privacy law makes it illegal for credit bureaus to collect this information. - What effect would this have on the banking industry?
Description of the network technologies and components : Prepare a Word document that is approximately 3-5 pages in APA format. It should be professional in appearance and suitable for review by network novices. Present the information in laymen's terms.

Reviews

Write a Review

 

Basic Computer Science Questions & Answers

  Conditions and requirements of application security

This seminal publication outlines a set of basic principles that define a logical way to classify and respond to threat. It also describes the critical things you should consider while building software. These underlying principles dictate the con..

  What constants are needed for block sizes of 64 and 128 bit

The second subkey is derived in the same manner from thefirst subkey.a. What constants are needed for block sizes of 64 and 128 bits?

  What does the top box, middle box and last box contain

There are three boxes in a Unified Mark-Up Language class diagram. What does the top box, middle box, and last box contain?

  Problem regarding the enumeration techniques

Enhance and elaborate on the port scanning and/or enumeration techniques (attacks) Share any additional thoughts you may have on them and explain how they can be detected and/or prevented.

  What are the estimated cell yield coefficients based

The composition of the off-gas on a volumetric basis is listed below. What are the estimated cell yield coefficients based on ammonia and oxygen for the consumption of glucose? 4.7 PROBLEMS 115 Substrate % nitrogen % carbon dioxide % oxygen glucos..

  Cloud services

Cloud Services

  Design a payroll class

Write the appropriate accessor and mutator methods and a constructor that accepts the employee's name and ID number as arguments.

  Problem regarding the constrained optimization

A company produces and sells four grades of industrial solvents - A, B, C, and D. The selling price per gallon of each grade of solventis $6.40, $5.00, $4.20, and $3.50 respectively.  Because of demand limitations, the company can sell at most 100..

  Program to implement the alternative strategy

a. Write a program to implement the alternative strategy. b. If the output polynomial has about O(M + N) terms, what is the running time of both methods?

  Consider a hypothetic experiment

One of the most widely used applications of spectroscopy is for the quantitative determination of the concentration of biological molecules in solution. The absorbance of a solution.

  Where is the search and replace utility in powerpoint

You need to edit all of your PowerPoint presentations to replace burtshardware.com with tomshardware.com. Where is the search and replace utility in PowerPoint?

  Draw an entity-relationship diagram

Draw an entity-relationship diagram that describes the following business environment. Must be done by hand, on paper. Not on the computer and include relationship types, ( i.e. Many to many, one to one represented by crows feet etc.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd