Unique Stable Solution in Stable Marriage Problem: Is it Pareto-efficient and a Nash Equilibrium?

cs.stackexchange https://cs.stackexchange.com/questions/88215

  •  05-11-2019
  •  | 
  •  

Question

The deferred acceptance algorithm solves the Stable Marriage Problem in a two-sided network, where each agent has complete preferences over each agent of the other side. There is always at least one stable matching but there can be several. Traditionally, the problem was solved by having men propose and women accept/reject a proposition, which leads to a stable matching that is male-optimal but at the same time female-pessimal. But it is also possible to switch roles and have women propose and men accept/reject, which leads to the female-optimal stable matching, which at the same time is the male-pessimal.

Now, imagine a network with more men than women. I observed that in this case the male-optimal matching and the female-optimal matching are (so far) always identical, as in this simple example:

    Women's preferences         
        A   B   C   D
M   U   1   1   1   2
e   V   2   2   2   1
n   W   3   6   5   4
    X   6   3   4   5
    Y   5   4   3   6
    Z   4   5   6   3
Read: Woman A's 1st choice is Man U

    Men's preferences               
        U   V   W   X   Y   Z
W   A   1   1   2   2   1   1
o   B   2   2   1   4   2   2
m   C   3   4   3   1   3   3
e   D   4   3   4   3   4   4
n
Read: Men W's 4th choice is Woman D

    M   F   pM  pF
    U   A   1   1
    V   B   2   2
    Y   C   3   3
    Z   D   4   3
    W   NA  0   NA
    X   NA  0   NA
    Read: Man Z is matched up with Woman D. She is his 4th choice, while he is her 3rd choice

Above example returns the stable matching consisting of four matches A<->U, B<->V, C<->Y and D<->Z (while men W and X did not find a match), regardless if I start with men proposing or women proposing.

Now, what are the consequences if there is only one stable matching? I would love to understand if my thoughts are correct:

  • First, I observed in my model always the same result, regardless if I used female-optimal algorithm or male-optimal. Since male-optimal solution = female-optimal solution, I claim there exists only one stable solution, which naturally is the optimal (and pessimal) solution for both genders.
  • Second, given this stable matching, I cannot improve anybody's position in a ranking without making another person's situation worse. The algorithm stops once there is no blocking pair. Therefore, this matching is pareto efficient.
  • Third, if only one stable matching exists, there is no possibility for any of the players to improve their situation by changing their strategy and creating a fake preference list (stating their actual preferences is their best strategy). I claim therefore that this is a Nash Equilibrium.

Example: In above example, U and A both have received their very first choice. They cannot be possibly happier. V and B would have liked A and A better than each other, but as U and A are already matched up with their ideal partner, V and B are the next best option. This continues until W and X, who both ended up without a match. However, no matter how they would have ranked their preferences, they always would have ended up without a match

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top