Yusuke Tsutsumi Just talking about whatever interests me

House Jobs and The Stable Marriage Problem

Being the steward for a fraternity has it’s ups and downs. Being appointed as one this summer, my role comes with several responsibilities: making sure everyone does their jobs, collecting money, and choosing everyone’s cleaning job for the Summer.

So let’s talk about the last responsibility: Choosing people’s jobs. Identifying this problem, there are several factors to consider:

1. Everyone’s Job preference
2. Who’s preference has higher priority
3. The location of that person’s room relative to the location of the job.

So why is the last one important? Because people are more likely to do house jobs that affect them: cleaning a bathroom closer to you has a lot of incentive compared to cleaning one that you never use.

My love for applications of my abilities made me pose the problem in a way solvable using math and computer science. So I present the “Stable Marriage” problem.

Stable Marriage Problem

Our problem has the following backstory: Let us suppose that we have an even amount of men and women. Everyone has a preference list, ordering who they want to marry. What are the best matchups?

Of course, I don’t know what kind of people would actually create a problem like this. Seriously, what kind of person would say: “Hey, there’s four of us, there’s four of you, so let’s get hitched! But wait, we all like different people, so how are we going to decide who’s going to marry who?”

Regardless of how rediculous the problem is, here’s the way it works:

1. Start with the first guy, and see if the girl he prefers is available:

i. If she is, then pair them up!
ii. If she isn’t, then check to see if she prefers our guy more:
a. If she does, then pair them up!
b.If she doesn’t, then our guy goes on to the next girl, starting again with step 1.
2. Once the guy is paired up, we start with the next guy, repeating at step 1.

Eventually, every guy will end up with the highest-ranking girl on his list that doesn’t prefer some else who prefers her. Thus, since every guy with such a girl, everyone is more or less “happy”. Thus, the marriage are “stable”.

Now, you probably notice that we could have done the same thing for girls. The method listed above find the optimal pairing for guys: Every guy gets with who they want, but this is not necessarily true for girls. If you interchange it so that the girls get to choose, then the opposite happens: girls get who they want, and guys maybe not.

So I guess the bottom line is that there’s two ways this problem could go: Optimizing for girls or for guys. Either way though, these solutions will look very similar.

What’s this got to do with house jobs?

The hypothetical problem that you saw above is just a part of Stable Matching. That’s the official name for this particular problem. It’s just finding a Stable Match – A situation in which one object does not prefer any other object that prefers it over their current pairing.

I bet you see where I’m going here.

We essentially have two groups of equal number that must be paired up: house jobs, and the people who live in the house. It’s easy enough to get the preferences of the people: you can just ask them to give you their choice in order. But how exactly does the house job prefer one person over another?

This is where math comes in. I generated a function that will the algorithm determine the preference of a house job. Here it is:

(Distance of job from person in question)*2 + (#of that person in the queue) = priority of person to housejob.

The lower the number, the more the house jobs prefers the person. Distances in this algorithm have three levels (so integers 1,2 and 3). This is multiplied by two to increase the effect that location has on the priority due to a house job. Otherwise, the number of the person wins over.

So, a perfect example of a Stable Marriage Problem.

[EDIT] I guess due to some difficulties, our house is getting shut down. Thus, no need to code this thing. Oh well, it was fun anyway.