ImagineThe deferred acceptance algorithm solves the Stable Marriage Problem in a two-sided network that I want, 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 pair up ina stable One-to-One pairs (matching that is male-> Stable Marriage Problem) withoptimal but at the Galesame time female-Shapley Algorithm (also called Deferred Acceptance Algorithm)pessimal. But it is also possible to switch roles and have women propose and men accept/reject, N beingwhich leads to the number offemale-optimal stable matchingsmatching, which at the same time is the male-pessimal.
I thought about the implications ofNow, imagine the following situation: both menmale-optimal matching and the female-optimal variants result in the identical matching, therefore N = 1 are identical, because of my assumptionsas in this simple example (this often is the networkcase when one side has more acteurs):
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
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
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
Above example returns four matches A<->U, B<->V, C<->Y and D<->Z as stable (more women thanwhile men, correlated preferences W and X did not find a match), no possibility of indifferent preferencesregardless if I start with men proposing or truncation)women proposing.
Which of my arguments are correctNow, whichwhat are wrongthe consequences if there is only one stable matching? I would love to understand if my thoughts are correct:
First, I argue doesn't make a difference which variant I use in the end and I can neglect all literature about rotations and optimal solutions.
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, I argue any stable matching is Pareto-efficient, as nobody's position can be improved without making another person's situation worse.
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: I read that the male-optimal variant is strictly strategy-proof for men but for women there is the limited possibility of strategic behaviour by truncation. Given this is both the male-optimal and female-optimal solution, and I am not allowing truncation anyways, this would mean the only stable solution is at the same time a Nash Equilibrium - is this correct? (NE, meaning that, ceteris paribus, nobody can improve their situation by altering their choice)
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
