Stable Matching Flashcards

1
Q

What is a stable matching problem? What is a matching? What does it mean that a matching is stable?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Dare la definizione di blocking pair

15/06/2021

A

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’
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Describe Gale-Shapley algorithm (GS).

A

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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly