2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm having a hard time understanding your post. Could you clarify the following: 1) 'doesn't matter which variant...' What are the 'variants' you consider? 2) As far as I know, women can strategize in the standard variant, which is without truncation iirc. How does your variant(s) differ? 3) I'm not sure if your usage of the Nash Equilibrium is correct here. A Nash equilibrium differs a lot from strategy proofness (for instance, strategy proofness requires that we have preferences, while the Nash Equilibrium doesn't) $\endgroup$ – Discrete lizard Feb 17 '18 at 16:13
  • $\begingroup$ Thanks for your comment. I edited my initial question in hope it's clearer now. 1. Variants: male-optimal vs. female-optimal 2. Yes, they can strategize. As far as I understand to end up at a different stable matching. But if only one stable matching exists - doesn't that mean that this solution is strategy-proof on both sides? 3. I must admit I am not really familiar with the NE. I understand that, given a non-cooperative game, no agent can improve their outcome by altering their strategy. This is true in above example, or am I wrong? $\endgroup$ – Maximilian Bredow Feb 17 '18 at 17:25
  • $\begingroup$ Ok, thanks for the clarifications, they help. I'm still unsure about one thing: are you claiming that in the presence of more men than women, the male optimal matching must coincide with the female optimal matching? Or are you assuming that the male optimal matching coincides with the female one? $\endgroup$ – Discrete lizard Feb 17 '18 at 18:51
  • $\begingroup$ Thanks for your help. I generated several different networks under a variety of different assumptions and I observed that only under the assumption of equal set sizes and uncorrelated preferences there was a difference between the male-optimal and female-optimal variant of the algorithm. Assuming different set sizes or preferences with correlation and intercorrelation always led to one unique stable matching. I don't know how to prove this mathematically. I am more interested in what this means for my players. Unique matching, being pareto-optimal and strategy-proof are great to work with! $\endgroup$ – Maximilian Bredow Feb 18 '18 at 10:39
2
$\begingroup$

First, while the Gale-Shapely algorithm guarantees that at least one stable matching exists, it need not be unique$^*$.

However, note that when the male-optimal and female-optimal matchings are the same, the stable matching is indeed unique, as shown in this answer.

As the male-optimal and female-optimal matchings coincide, both can be considered the 'optimal' side and therefore is Pareto optimal for both sides.

Your third argument however, is incorrect. While it is true the matching is unique, this is under the assumption that all preferences are true. As this is not the case, we cannot use this fact to conclude strategy-proofness on both sides.

However, we have the stronger property that the female and male optimal matchings coincide. This again means that the properties the algorithm assigns to the male side automatically apply to the female side and therefore the matching is strategy-proof for both sides.

(Another way to argue is that any manipulation cannot give the woman them a better result than switching sides with the men. But they already have the result they would get by switching! So they cannot improve by manipulation.)

*: Further conditions for uniqueness are explored in a paper by Jan Eeckhout:

The 'sufficient' condition for uniqueness (Theorem 1) basically says that if we order all men and women and if

  1. All women of rank $i$ prefer the man of rank $i$ to any man of higher rank; and
  2. All men of rank $i$ prefer the woman of rank $i$ to any woman of higher rank.

Furthermore, the paper mentions that if we match among a total of $4$ or $6$ persons, these conditions are also necessary for uniqueness.


If we want to talk about a Nash-Equilibrium, we have to phrase the matching process as a game. We can consider all men and women to be 'players' and their 'strategy' to be the preference profile they submit (which may differ from their actual preference, which determines the payoff). A set of strategies is said to be a Nash-Equilibrium if changing a single strategy of a single player cannot improve the results for that player. As we know that the current matching process is strategy-proof for all players involved, improving on 'everyone reports truthfully' is impossible. So, in this sense, the 'everyone reports truthfully' set of strategies is a Nash-Equilibrium.

In fact, we can say that strategy-proofness of our matching means precisely that the 'every reports truthfully' is a Nash-Equilibrium in the associated game we defined.

$\endgroup$
  • $\begingroup$ Thank you so much! So I understand my first and second assumptions were correct. The third assumption, being strategy-proof on both sides if female-optimal and male-optimal solution coincide, is also correct but my argumentation was wrong. Basically, the best stable solution for women is by proposing themselves - as this procedure results in the identical matching, the properties for men apply for women as well --> matching is strategy-proof for each agent. But I cannot call this a Nash Equilibrium - is this correct? $\endgroup$ – Maximilian Bredow Feb 18 '18 at 10:53
  • $\begingroup$ @MaximilianBredow Yes, you understand my points. I've updated my answer to discuss the Nash-Equilibrium, please have look. $\endgroup$ – Discrete lizard Feb 18 '18 at 11:16
  • $\begingroup$ Thanks again! I guess I have difficulties differentiating between "strategyproof for each user" and "Nash Equilibrium". As far as I understand strategyproof is a description of the network, saying your best strategy is your actual preferences. I understand NE as a state in which no player in a game can improve her situation by altering her strategy. Doesn't this mean then that strategyproof is 'stronger' than the existence of a NE, because not only does it describe that a NE exists, but also where (= set of strategies that reflect actual preferences of each player)? $\endgroup$ – Maximilian Bredow Feb 18 '18 at 13:25
  • $\begingroup$ @MaximilianBredow Yes, strategy-proofness is a NE on a single fixed set of strategies (i.e. everyone is honest.) In theory, there could be another NE with some people lying and others not (although I have no idea whether this is actually possible, we can't exclude it yet) $\endgroup$ – Discrete lizard Feb 18 '18 at 16:06
  • $\begingroup$ Okay perfect, you helped me very much! $\endgroup$ – Maximilian Bredow Feb 18 '18 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.