What's the best way to optimally match rated pairs?

Question

Lets says I have a list of men and women. Each man(x) rates each woman, and each woman(y) rates each man, on a scale 0-9.

e.g.

x1: {y1: 0, y2: 5, y3: 9}

x2: {y1: 1, y2: 0, y3: 9}

x3: {y1: 5, y2: 5, y3: 8}

y1: {x1: 3, x2: 3, x3: 5}

y2: {x1: 8, x2: 2, x3: 2}

y3: {x1: 9, x2: 5, x3: 9}

I'm looking for an algorimthm that pairs all x & y as to maximise the total ratings.

In this case the optimal pairings would be x2:y3 = 9+9 = 18, x1:y2 = 5+8 = 13, x3:y1 = 5+9 = 14. for a total rating of 45. At least I think it is by eye.

I think its a simplified version of the maximum independent set problem, that isn't an NP-hard optimization problem.

Answer 1

This problem is known as the stable marriage problem and the Nobel Prize in Economics was awarded for the solution. Algorithm is described in some detail on wikipedia:

http://en.wikipedia.org/wiki/Stable_marriage_problem

Pseudo-code cut/pasted from wikipedia:

function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = m's highest ranked woman to whom he has not yet proposed
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
           (m, w) become engaged
           m' becomes free
         else
           (m', w) remain engaged
    }
}