In one of the homework assignments, it was shown that when we run the Gale-Shapl

ID: 3789476 • Letter: I

Question

In one of the homework assignments, it was shown that when we run the Gale-Shapley algorithm with the men proposing, the women can sometimes improve their partner by giving false answers. The following specific example was given in the posted solution to the homework. If w1 falsely says she prefers m3 to m1, both w1 and w2 will end up with better partners than if she had told the truth. The matching when she gives this false answer is (m1, w2), (m1, w1), (m2, w3). Note that in this matching, every woman is paired with her best valid partner. Suppose we run Gale-Shapley with the men proposing. Is it always possible for the women to state their preferences (possibly telling the truth and possibly not) in such a way that every woman ends up with her best valid partner? Answer YES or NO. If your answer is YES, prove that this is true for every set of preferences. If your answer is NO, give a specific example of a set of preferences for which this is not. possible. To receive credit for this question, the first word of your answer must be either YES or NO. Please note that on the grading for this problem, you may receive 0 points if your proof or example is incorrect, even if you happen to get the YES/NO portion of the answer correct.

Explanation / Answer

GALE SHAPLEY ALGORITHM: gale shapley method is generaly used for matching problemss or we can say that it provides solution to the marriage problems,just like in marriage there are two person girl and a boy and they have to be matched,just like that only in gale shapley also there are two sets that has to be matched and it is done in various methds.

Suppose that n men and n women seek life-long partners. Each of them has a preference list of the members of the other sex and submits it to a centralized authority. In the spirit of making all the participants maintain a long-term relationship, the authority has to make sure that the matching does not involve any blocking pair : a couple each of whom prefers the other over his (her) partner in the matching. A matching without any blocking pair is stable. The goal of the authority, given the men’s and women’s preference lists, is to find a stable matching.

In gale-shapley algorithms we use the following notations and rules,which has to be followed while matching.

One way to view the Gale–Shapley algorithm is as maintaining a graph GG of possible matches. Here is pseudo-code for the Gale–Shapley algorithm from this point of view:

now moving towards the question,

let A be the process of the algorithm,let P be the proposal, and Pa THE output of A.

FOR every (m,w) in A ,so that w prefers her husband in P over Pa.record the time that m refuses and broke his marriage with w during A.

NOW WE CAN ASSUME THAT THE SET IS NON EMPTY SET.

let(m0,w0) be the pair with minimum time together,let

let m1 be the husband of w0 in Pa.

since w0 asked m0 before m1 during A,but ended up marriying m1,now since we knnow that m0 is not married to w0,but with m1.

And that m0 prefers w1 over w0. (w1 is not necessarily married to m0; they were just engaged.)

Let m1 be the husband of w1 in P.

There are two cases:

If w1 prefers m1 over m0: This means that prior to the engagement of w1 and m0, woman w1 asked m1. This happened before w0 was rejected by m0, by the choice of w1. Since w1,w1m1,m1 are not married in Pa, this means that m1 rejected w1 before m0 rejected w0. A contradiction to the minimality.

If w1 prefers m0 over m1: This is a contradiction to the stability of P, since m0 also prefers w1 over w0

Navigate

In one of the experiments, two convex lenses with focal lengths f_1 and f_2 were

In one of the largest actions brought to date against charity fraud, on May 19,

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

In one of the homework assignments, it was shown that when we run the Gale-Shapl

Question

Explanation / Answer

Related Questions

Navigate