# Valentine’s Day Blog

By Julieanna Luo

Last Saturday, I stumbled upon something that made me think of Valentine’s Day in a new light, and I want to share it with you.

I learned from a friend that in mathematics, economics, and computer science, there is something called “the stable marriage problem” (also stable matching problem, or SMP) which is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. To put it in a way that is easily understood — thanks to Wikipedia — the stable marriage problem has been stated as follows:

Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable. (Note the requirement that the marriages be heterosexual)

It turns out, Gale and Shapley not only offered the problem, but also presented a famous solution to the problem, proving that for any equal number of men and women, it is always possible to solve the SMP and make all marriages stable.

First, let each unengaged man propose to the woman he prefers most (whoa, not so fast please!) and then each woman replies “maybe” to her suitor she most prefers. She is then provisionally “engaged” to the suitor she most prefers so far, and that suitor is likewise provisionally engaged to her. For the girls who receive no proposals yet, don’t worry, there will be.

We call the above one round. The Gale–Shapley algorithm involves a number of rounds. In each subsequent round, we follow the same procedure. Each unengaged man proposes to the most-preferred woman to whom he has not yet proposed, regardless of whether the woman is already engaged. Then each woman replies “maybe” if she is currently not engaged. Or, if she prefers this guy over her current provisional partner, don’t hesitate, just reject the current one and that guy becomes unengaged.

This process is repeated until everyone is engaged. It is guaranteed that this process will end, which means, no dead-loop. Once it ends, everyone gets married. More importantly, the process finally reaches a stable marriage: there exists no guy or girl who prefers another partner more than their current partner.

A very comforting theory, isn’t it? There’s just only one thing: there is more than one solution to the stable marriage problem, and this particular one articulated above is the one most advantageous to guys and worst to girls. How so?

It is the most advantageous for guys because, according to this process, the final partner is definitely the partner he likes the most among all other stable marriage options (which is not to say that he will marry his favorite girl). Some girls are great, but cannot form a stable marriage with him.

On the other hand, it turns out the worst for girls because in the end, her partner could be the one she likes the least among all the other stable marriage options. Again, not to say that she will always marry the worst guy in her eyes, but the most tolerable among all the possible stable marriage options. That sounds sad enough.

The conclusion is not that great for ladies, which is somewhat weird because it seems like ladies are on the bright side during the whole process. Guys have to keep proposing and risk getting rejected and proposing again, and all ladies need to do is to choose, and they have the right to change boyfriends anytime. However, guys do have one advantage, if not the most important one: they are the initiator.  Even if he gets rejected a million times, in the end he still gets to be with the one he likes the most among all the rest. Girls may have a million choices, but they may never wait till their favorite guy to pick them, or before he comes, the game is already over.

“The stable marriage problem” is not really designed to say something about love — mathematicians are not crazy enough to actually believe logic can solve the problems of emotion. However, it is true that in all classic love story narrations, girls are supposed to wait for the one to come and save her, and love her forever. Really? Aren’t the title “man” and “woman” in Gale and Shapley’s theory just demonstrative pronouns? And we may discover, to our surprise, that what we have needed more that anything was not so much to be loved, as to love. To quote a line from “He’s just not that into you”—“Maybe the happy ending is this: knowing after all the unreturned phone calls and broken-hearts, through the blunders and misread signals, through all the pain and embarrassment…you never gave up hope”. Throughout history, we have gazed upon the brave kids who, despite all their failed effort, still tried to fall in love. They are, after all, a lot closer to love.