Skip to main content
explain relation to Nash equilibrium
Source Link

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.

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.

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.

Source Link

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.