Explore the issue of truthfulness in the stable matching

Assignment Help Computer Engineering

Reference no: EM132104982

For this problem, we will explore 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, we 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 purposes of this question.) Resolve this question by doing one of the following two things:

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 Give an example of a set of preference lists for which there is a switch that would improve the partner of a woman who switched preferences.

Reference no: EM132104982

Questions Cloud

Clothing line of business : Should the store drop the clothing line of business based on the sales and cost data above.?

Give a new yes-instance of problem pihs : Can the set V of vertices be partitioned into exactly k disjoint sets V1; V2; V3.... Vk such that, for 1

Income statement for september : The company expects to sell $560 units in September. Example of an income statement for September using contribution margin format.

Implement the method and constructor with added requirement : addAll( ) : adjust the type of the parameter, it is an ArrayBag with the same generic type parameter; the method checks.

Explore the issue of truthfulness in the stable matching : Explore the issue of truthfulness in the Stable Matching Problem and specifically in the Gale-Shapley algorithm.

Determine the big-oh for the performance of your algorithm : The numbers are read by the program from a file. The numbers in the file are not necessarily sorted.

Create a struct that contains four integer fields : To do this problem, you will need to dynamically create a struct that contains 4 integer fields. The fields should be called X, Y, TheSum and TheProduct.

Show the tables in 1nf and 2nf that are created in process : Use the process of normalization to transform the table below into 3NF. Show the tables in 1NF and 2NF that are created in the process.

Concern to entrepreneurs : Why should ethics or social responsibility be of concern to entrepreneurs (how an establishment reacts to the demands of its stakeholders)?

User Account

All Pages