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:
- 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.
- 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?