What is a stable matching problem? What is a matching? What does it mean that a matching is stable?
Stable Matching Problems
- Two sets of agents
- Agents of one set express preferences over agents of the other set
- Goal: to choose a matching among the agents of the two sets based on their preferences
Matching: set of pairs (A1, A2), where A1 comes from the first set and A2 comes from the second set
Stable Marriage: a marriage with no pair (man, woman) not married to each other that would prefer to be together. OR marriage with no blocking pairs.
Idealization: assumes no cost in breaking a match
Dare la definizione di blocking pair
15/06/2021
Marriage: is a one-to-one correspondence between men and women
Idealization: everyone marries at the same time
Blocking pair: pair (m,w), where m is a man and w is a woman such that:
- the marriage contains (m,w’) and (m’,w) , but
- m prefers w to w’
- w prefers m to m’
Describe Gale-Shapley algorithm (GS).
Initialize every person to be free
while exist a free man:
find the best woman he han not proposed to yet
if this woman is free then declare them engaged
else:
if this woman prefer this proposal to her current partner then declare them engaged (and free her current partner)
else: this woman prefer her current partner and she rejects the proposal
Properties:
- Time O(n^2): Each of n men can make at most proposals.
- Terminates with everyone married.
- Finds man optimal solution: There is no stable matching in which any man does better
- Finds woman pessimal solution: In all stable marriages, every woman does at least as well or better.
- Terminates with a stable marriage.
