Truthfulness in stable marriage

Assignment Help Business Economics

Reference no: EM13801625

Problem 1: Truthfulness in Stable Marriage

This problem explores the issue of truthfulness in the Stable Matching Problem and specifically in the Gale-Shapley algorithm. The basic question is: can a man or a woman end up better off by lying about his or her preferences? More concretely, suppose each participant has a true preference order. Now consider a woman w. Suppose w prefers man m to m', but both m and m' are low on her list of preferences. Can it be the case that by switching the order of m and m' on her list of preferences (i.e., by falsely claiming that she prefers m' to m) and running the algorithm with this false preference list, w will end up with a man m'' that she truly prefers to both m and m' ? (We can ask the same question for men but will focus on the case of women for the purposes of this question.)

Resolve this question by doing one of the following two things:

(a) Give a proof that, for any set of preference lists, switching the order of a pair on the list cannot improve a woman's partner in the Gale-Shapley algorithm; or

(b) Give an example of a set of preference list for which there is a switch that would improve the partner of a woman who switched preferences.

Reference no: EM13801625

Questions Cloud

Flight attendants receive a pay increase : Please label the x and y axes, the supply & demand curves and the equilibrium points. You do not need to use any actual numbers. Then, analyze how the changes described in each case affect the equilibrium price and quantity of airline tickets for eac..

Define monetary and fiscal policy : Please define monetary and fiscal policy. What are the key components of each policy? List several strengths and weaknesses of each. Based on what you have learned in class, which policy is more appropriate to manage economic performance or an econom..

Bailout for an industry such as financial or automotive : What are the advantages and disadvantages of a “bailout” for an industry such as financial or automotive? Please give several examples and document any sources/data as appropriate. What is your opinion about government involvement and financial suppo..

Assume that due to an increase in the federal minimum wage : On the left show the market for potatoes and how the competitive market price for potatoes is determined by supply and demand. 2. Now act as if you are a potato farmer in the Midwest of the United States. Assume that due to an increase in the federal..

Truthfulness in stable marriage : This problem explores the issue of truthfulness in the Stable Matching Problem and specifically in the Gale-Shapley algorithm. The basic question is: can a man or a woman end up better off by lying about his or her preferences? More concretely, suppo..

How often should the employee be monitored : Under which circumstances do you think an employee should be monitored? Based on the circumstances you have identified, how often should the employee be monitored?

Relating to the new trade theory and strategic trade policy : Whose interests should be the paramount concern of government trade policy - the interests of producers (businesses and their employees) or those of consumers? Given the arguments relating to the new trade theory and strategic trade policy, what kind..

Diagram of the market for money and the aggregate supply/ : Draw, side by side, a diagram of the market for money and the aggregate supply/ aggregate demand to illustrate how inflation is created. Initiate the process in the AS-AD diagram with negative supply shock that the central bank decides to "accommodat..

Explain why savings is unlikely to equal intended investment : Explain why savings is unlikely to equal intended investment in the Keynesian model. Equilibrium GDP is $5000 while full employment is $6000. What kind of gap is this? What would the Keynesians say the government should do?

User Account

All Pages