# Polygamous stable marriage/ assignment problem

I'm not sure under which 'algorithm' it falls under, but here is the problem:
I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all guy-girl matchings/'edges' are possible, and the edges are weights. Also, I'm not looking for a perfect solution - just a reasonable approximation where most people get as close as possible to 5 matches.

Any idea how to go about it? The traditional stable marriage and assignment solutions don's work in this case.

p.s For context: the real world problem is matching users to girls/guys in their extended social network.

• When there are G1 ... G5 ... and g1 ... g5 ..., at least five of each, then G's can select g1 ... g5, and g's can select G1 ... G5. Simple. Except that it's not what you want. Then what do you? – Włodzimierz Holsztyński Oct 27 '14 at 22:46
• What is your objective function? Maximize the weighted matching? (Then max-flow should work, right?) Or do you actually want a stable solution, or just any feasible solution, or.... – usul Oct 28 '14 at 1:04
• @usul - The objective is to maximize the weight. Wouldn't I need a Minimum-cost flow or Hungarian method to solve this? – EugeneMi Oct 28 '14 at 20:20
• I think you're right, max-flow doesn't work. But something like the Hungarian algorithm should, or using an LP as Robert Israel suggests might be the fastest. – usul Oct 28 '14 at 23:10

You can do this as a weighted network-flow problem where each guy is a source of $5$ units, each girl is a sink of $5$ units, and each possible arc has capacity of $1$ unit. You can solve it using linear programming, and the integrality theorem guarantees that a basic optimal solution is in integers.