Is Gale Shapley globally optimal?

Question

Let us have a set of N men and N women, and we have two matrices of affinities $M$ and $W$ such that $M(i,j)$ is the affinity of the ith man towards the jth woman and $W(i,j)$ is the affinity of the ith woman towards the jth man.

The problem at hand is to find an optimal stable marriage, which satisfies that:

1. There is no couple of man and woman not married such that they would prefer to be with each other (have higher affinity towards) rather than their actual partners.
2. The sum of the affinities of each couple is maximal among the stable marriages.

Does vanilla Gale Shapley solve this problem? If not, is it NP-complete or is there any hope of solving it polynomially?

Answer 1

No, Gale-Shapley optimizes a different set of criteria; see https://en.wikipedia.org/wiki/Stable_marriage_problem. It maximizes the men's happiness, which doesn't necessarily maximize the total happiness sums. It is easy to come up with counterexamples by taking any stable marriage solution where some woman doesn't get her first choice -- say, Alice's first choice is Bob, but she isn't assigned to Bob in the assignment output by Gale-Shapley -- and then making Alice's affinity towards Bob be some enormous number, far larger than all other affinities.

I don't know if it can be solved in polynomial time. Without the stability requirement, it's an instance of the assignment problem. With the stability requirement added on, I don't know whether it can be solved in polynomial time.