Chapter Notes[3]

Ch 10 - Matching MarketsStable Marriages Given a set of n males and m females we wish to find a matching of men and women that is at least pareto optimal i.e. stable meaning that no women or man would have the incentive to run of with another women or man that is not their partner, i.e. a BLOCKING PAIR!Each women and man has a preference ranking for the opposite sex. Gale Shapley Algorithm -You can have Female Proposing Deferred Algorithm (FPDA) or a Male Proposing Deferred Algorithm (MPDA).Algorithm for Females (Male algorithm is the same but with males instead)1. Women propose to their most preferred male who they have not already proposed to in a sequence of rounds. In each round each unengaged women proposes to one man, i.e. in the first round all women will make a proposal.2. Each male who has been proposed to will accept the offer from their most preferred women and they now become 'married'.3. In the circumstance that a male is proposed to but is already 'married' then the male will only accept the proposal if the women is more preferred than the women he is currently married to, if not he will reject the offer. If he decides to accept the proposal then is previous wife will not become unengaged so must make another proposal in the next round.4. This continuous until all women are engaged.Gale Shapely Algorithm ensures that there is a set of stable marriages with no blocking pairs due to the fact that if there was a blocking pair (m,w) then using the steps of the algorithm then either w would have proposed to m before his current partner which means that m would have accepted the offer and not changed his choice when his current partner proposed as she is less preferred. Or if w had proposed after m's current partner then m would have rejected his current partner for w as w is more preferred over m's current partner.FPDA produces a female optimal solution if each women is matched to her most optimal partner. This does not mean they are well off just that a women's most optimal partner is the 'best' partner she could have been matched with in any of the possible stable matchings.The disadvantage of using the Gale Shapely Algorithm is that it is prone to manipulation meaning a person can end up with a better partner if they do not reveal their true preferences i.e. rejecting a proposal from a more preferred women than the one assigned to them. This is not the case for the sex proposing.

Ch 10