Stable Marriage Problem

Since there hasn't been much excitement happening the political world in the last week or so to comment on, I thought I'd do something a little different this time. It's something of a fusion between my interest in mathematics and my interest in politics. A while back, I learned about a mathematical problem known as the stable marriage problem. The professor, of course, warned us about drawing any social implications from this problem. I, of course, promptly ignored her and when I got home wrote an article on the social implications on this problem. I tried unsuccessfully to get the article printed in the actual print media, so I'm publishing it here instead. Here goes:

In the mathematical theory of algorithms we discuss what is known as the stable marriage problem. The problem goes as follows. Suppose we have some number of men and an equal number of women. We will assume all marriages are between a man and a woman. (This is merely to simplify the mathematics. It is not a political statement.) Each man lists all of the women in his order of preference for who he would want to marry. Each woman lists all of the men in her order of preference for who she would want to marry. We will assume everyone would prefer being married, even to the last person on their list, to being single. (Again, this is to simplify the mathematics, and is not a political statement.) The stable marriage problem asks if we can pair up the men and women into couples so that there are no blocking pairs. A blocking pair is defined as a man and women who both prefer each other to their spouses in the given solution. If no such blocking pair exists, we call the set of marriages stable. We can prove that a stable set of marriages always exists. In fact, in most cases, many possible stable marriages exist.

The algorithm to find the stable marriage partners is rather simple to understand. On day 1, each man will propose to the first woman on his list. Any woman who receives just one proposal will accept and the couple gets engaged. If a woman receives more than one proposal, she will accept from the one who is highest up on her list, get engaged to him, and reject the rest. On the second day all the men who are not engaged propose to the next woman down on their list. As before, the women accept the best proposal offered to them. This means even if they were already engaged, they will break the engagement, and instead get engaged to the man they prefer more. This process continues until all men and all women are engaged, and then all the engaged couples get married. I’m not going to give the proof here, as it’s fairly mathematically involved, but take my word for it that these marriages will be stable.

Now, here’s where it gets interesting. Mathematically, the people are just lists of numbers, so it doesn’t matter who we call the men and who we call the women. We can equally well run the algorithm with the men proposing and the women accepting, as with the women proposing and the men accepting. Both ways will give us a set of stable marriages, but not the same set. Let me define one more term. A partner is said to be feasible to you if there exists some arrangement where you could have a stable marriage with them. We can prove that if the men do the proposing, every man will end up with his most preferred feasible partner and every woman will end up with her least preferred feasible partner. Conversely, if the women do the proposing, every woman will wind up with her most preferred feasible partner and every man will wind up with his least preferred feasible partner. Without going into the details of the proof, let me give some intuition as to why this is true. Think about the preference list for the average person. On the top, you’re going to have the people who are out of your league. On the bottom will be the people you are too good for. Somewhere in the middle will be the feasible partners. If you’re doing the proposals, you start from the top, and work your way down to someone who is in your league. If you’re accepting the proposals, you start by getting proposals from the people you wouldn’t even consider, and accept as soon as you get someone who’s “good enough.”

Obviously, real life marriages do not work quite like this highly simplified mathematical problem, but its social implications still bear tremendous relevance. Though it is starting to change, the dominant social norm in our society is that the men do the marriage proposals. Of course, we can’t say with the same mathematical certainty as we could in our problem that this means every man will end up with his most preferred feasible partner and every woman with her least preferred feasible partner. However, the basic intuition that this system is going to mostly benefit the men still applies. This may seem surprising to some. After all, the system is designed to portray the woman as the one in charge. The man is supposed to make the proposal all romantic, get down on one knee, put the woman up on a pedestal, buy her expensive gifts, etc. This is all an illusion, though. Patriarchal society would never knowingly adopt a social norm that would really give women an edge over men. This all gives lie to conservative apologists who would point to things like this as evidence that old-fashioned socio-cultural norms in fact give more respect to women than modern feminist ones. In reality, the very institutions that seem to give the most respect to the women are mere clever ploys to manipulate the women for the benefit of the men.

However interesting marriage proposals might be, the implications go far beyond marriage proposals or gender dynamics. Any time one person or entity is in a position of power over another, they will tend to maintain this power by giving the other person the illusion of choice. Go to the supermarket to buy laundry detergent. You might see over 15 different brands on the shelf. You might think, “Wow. Look at all the different choices I have. This is really capitalism at its best.” If you read the labels, though, you will see that most of the brands are manufactured by one of three companies. The companies know that people are happier thinking there are 15 different companies competing to make the best product for them than knowing there is a 3-company oligopoly manipulating them for profit. If the one you are dominating thinks they are really in control and does not know you are dominating them, they are far less likely to revolt against the status quo.

It can often be difficult to know when a choice life presents you is a real choice or a fake choice someone is offering you to maintain their dominance over you. However, I think the mathematics of the stable marriage problem holds the keys to the solution. When you get to actively choose what you really prefer, you are the one in control. If you are presented with options and can only passively accept or reject them, someone else may be manipulating you. Now I don’t mean to say that active choices are all good and passive ones all bad. A society without any kind of power relationships may have been the communist dream, but it certainly is not realistic, and probably not even desirable. However, an equitable society must have a proper balance of the power relationships so there aren’t classes of people, some that are always in the active role, and others that are always in the passive role. An awareness of the nature of our relationships is the first step to bring about this positive change.