Weighted Bipartite Matching from Compatibility

Let’s say that this diagram represents eight heterosexual people, four of each gender, where the thickness of the black lines joining them represent compatibility:BipartiteForLoveSite

It is clearly possible to match up these people in various ways.  First consider a truly bad way of doing it.  The high divorce rate is evidence that terrible matches do often occur.

Let us first connect Adam with Elaine, the woman least compatible with him.  Trust those two to get together, the idiots.  Bob and Gail are equally unwise.  And wouldn’t you know, Charles and Frances are also utterly incompatible but chose one another, perhaps while drunk.  There is only one man and one woman left on the island, so they can pretend that while far too sensible to make such a poor choice, David and Harriet got together because there was simply no one else available.

Now it should have been obvious to all of them, if not under the influence of strong liquor and perhaps recreational chemicals, that Adam should have gotten together with his true soulmate, Harriet.  How much better the lives of Bob and Frances would be if they were equally perceptive or in touch with their emotional instincts.   Another happy couple would be David and Elaine.  That leaves one man and one woman, and their future is less promising.  Charles would have liked Harriet, or failing her, Elaine.  But both are taken.  It’s either Gail or celibacy.

Gail had no magically compatible options, but wouldn’t even be with Adam, who loves Harriet.  Things could be worse, she could be left with the least compatible man, but no, Bob is with Frances.  That’s a relief.  Gail might have been moderately compatible with either Charles or David, maybe enough to avoid a bitter divorce.  Only one of those dubious options would be available though — David is happy with Elaine.  Gail will end with Charles and have to make the most of it.  Or maybe they will agree to move to the big city where they will have lots of good choices.

Let’s have one more try, for the sake of poor old Charles and Gail.  What they had been clever, and decided to try a dating service while the others were dithering around.  Oops, that’s no good, Gail would end up with maximally incompatible Bob and Charles with worst choice Frances.  OK, OK, just kidding.  Dating services are not that bad.  Perhaps we should just point out how poor their options are, and goad Charles and Gail to take immediate action.  Let’s give Gail the hardest push, because she is the hardest to satisfy.  So, young lady, take the initiate, throw yourself at the man you want the most and try hard to hold onto him.  That would be Adam.  He’d prefer Harriet, but Gail would be his second choice, and either because he is unable to resist her wiles or out of true altruism Adam takes her as his love, and gentleman that he is, will stay with her forever.

With Adam tied to Gail, Charles is free to seek the hand and other anatomical features of the Harriet he wants.  She would have preferred Adam, but Charles was her second choice, and that’s not so bad.  Of the four remaining people, there is no problem at all.  David and Elaine are perfect for one another, and so are Bob and Frances.BipartiteBestForLoveWebsiteSo in this scenario, ever single person has someone sufficiently compatible.  Nobody has worse than their second choice, while four people do get their perfect soulmates.  It is a decent compromise.  Four people have only their second choices, not their first, but nobody is either left alone or due for a divorce.

This is the type of situation a good weighted bipartite matching algorithm can produce, a fair compromise.  You might rebel at the very suggestion of accepting a compromise, however.  In that case, you might think of moving to a larger island.  If there were eighty single people instead of eight, forty heterosexual people of each gender instead of four, then the amount of compromise could be much less.

Using the kind of algorithm which selects all the best matches first, known as a greedy algorithm, several people with limited choices would again be left alone or badly matched.  Using a fair algorithm though, the same few people would be settling for their second or third best, as before, but their second or third best out of forty possibilities.  The larger the pool of candidates, the more good choices are likely to be available, so the second or third out of forty is likely to be much better than the second out of four.

But of course, a few people with near-perfect matches would not get them.  Instead they would also  have to settle for their second or third best out of forty possibilities.  Not ideal, but pretty good.

The bigger the pool of candidates, the less compromise is necessary.  On a still bigger island, there might be four hundred choices for each person.  Having to take the second or third best out of four hundred does not seem like much of a compromise.

Let’s move out of the archipelago now, and onto the mainland.  In the big city we might have 200,000 unmatched people of marriageable or at least mateable age and heterosexual persuasion.  Settling for the second or third best out of 100,000 possible matches is hardly any sacrifice at all.  And in the big city there would be enough possible candidates for even those of the less common sexual preferences to find love.

The key to making this work is not a dating service like eHarmony or Match.com which implements a greedy algorithm, it is the use of a well-designed weighted bipartite matching algorithm.

There are now very good algorithms indeed, some of which are approximately linear in the size of the pool of candidates, and which still work well as people are added or removed from the pool.

There is really no excuse for doing it any other way.  Well, OK, there are lots of reasons.  Perhaps the worst, people lie.  How do we really know people are as they describe themselves?

This is a separate question, addressed elsewhere.  It is not hard to solve.  What is needed is a determination to work on it and use the best possible algorithms.   Our society would be much much better if what is described here on this site were implemented.  It would be possible to drop the divorce rate to almost zero, which would be of enormous benefit to the children of the couples involved.  Moreover, those children, growing up in happy households with parents who truly loved one another would become better people themselves.

We must do this, if not only because of all the single people out there who badly need someone, but because of the children.