Localhost Part 2
Hello! Sorry it’s been a while! So, we’ve rewritten our hosting algorithm to give hosts and hackers the best experience possible for Fall 2018. Although there is still a lot of work to be done, we are excited to share our current model and talk about future improvements.
Hosts with Multiple Spaces
First, Princeton has quite a few large suites, meaning that to eke out the space available on campus, we need to allow people to host multiple hackers. In itself, this isn’t hard to deal with. What HackMIT does is duplicate the host node — that is, treat hosts with multiple spaces as if they were multiple distinct hosts when matching.
Our approach took this idea a step further and introduced what we call “fairness” into the algorithm. In situations where there are many more hosts than hackers (which is not common but happened in Spring 2018), we want to distribute the hackers as fairly as possible. After all, is it really fair for one person to host 5 people while another hosts none?
If space is tight, it’s not going to be the case that any person hosts significantly more hackers than another person with comparable capacity. Although, in any case it’s bad if someone signs up in good will and doesn’t get to host. It makes it feel like we don’t actually need their help which is false, which is not the case. We tend to be short of hosts and need all the volunteers that we can get. So it is imperative that prospective hosts feel that they are treated fairly.
Fortunately, we only need to make a couple small modifications to make the algorithm fair. As it turns out, doing it this way makes fairness much easier. Rather than using Edmonds-Karp, which uses breadth-first search to find potential matches, we can use a best-first search, and define “best” as the edge with the least flow to capacity ratio. The order we pick matches doesn’t affect optimality; like Edmonds-Karp, our modified algorithm is still an implementation of Ford-Fulkerson, and so still computes a maxflow. But by adding hosts in this order, we can make sure that hackers are distributed as evenly is possible.
It’s also possible to modify best-first search to look at the edges with least flow, which is useful because it means that hosts will be assigned hackers evenly, rather than proportionally with respect to the space available in the hosts’ rooms.
So, it looks like the algorithm is now fair. Okay, what’s next?
Gender Preference
Second, and very critically, we need to respect what we’ve dubbed “gender preference,” when someone, a host or a hacker, is not comfortable staying with someone of a different gender. Hosting people regardless of gender is a huge boon to the matching, because this means there are more eligible hosts available for any given hacker, but it’s also a matter of personal comfort.
What this means for our algorithm is that if anyone has a gender preference in a room, nobody in that room can be of a different gender, including other hackers. Now, using a maxflow algorithm is no longer possible, since we’d need to start deleting possible matchings mid-algorithm.
We’re going have to do something a bit more here. First of all, this modification means that we may not match as many hosts and hackers as possible. As a design choice, we decided that it was most important that people have desirable matchups rather than a random matchup. In particular, if a host/hacker has a strict gender preference, we will respect it even if this leaves a hacker temporarily without a place to stay, or a host’s room largely unused.
That said, within this restriction, we still want to be able to match up as many people as possible. To optimize this, we want to avoid placing inflexible hackers with flexible hosts, since that would reduce the flexibility of our matching algorithm. Thus, the first step is to match as many inflexible hackers and hosts as possible.
Unless we are very lucky, we will be leftover with either hackers or hosts with a gender preference. In the latter case, there is nothing we can do to improve in the given situation. We just match as many guests of the preferred gender to the host. In the former, we fill all the inflexible guests in rooms with their preferred gender to avoid adding restrictions to the algorithm’s performance.
One caveat to this method is that fairness is sacrificed to favor inflexible hosts. This is unavoidable if there are many more hosts than hackers under our algorithm. However, in the event where there are barely enough hosts, the algorithm guarantees maximum fullness which we prioritize over fairness as we want all hackers to have somewhere to stay.
Finally, we are left with matching the remaining hosts and hackers. In this step, as with all the steps above, we assign hosts to hackers according to the priority queue first mentioned in “Hosts with Multiple Spaces” and further described below.
Sleeping Times
Understandably, sleeping times are a concern for our hosts. Not every student is willing to stay up as late as hackathons typically demand, and the hackers need students to let them in to the rooms. This brings us to our last thing to consider: when hackers and hosts plan on going to bed. Our current implementation brings with it several issues (as one may expect when an algorithm is designed and implemented with a last-minute deadline).
The “best-fit” search mentioned earlier is implemented as a priority queue. We rank rooms by a metric defined as a combination of sleeping time and full-ness. Specifically, empty rooms with early sleeping times are ranked at the top. This did allow us to match hackers and hosts with compatible sleeping times, and most assignments made in the Fall 2018 hackathon resulted in sleeping times that differed by an hour or less.
However, this combined metric meant our efforts to distribute hackers evenly among our hosts were hindered. Hosts who gave sleeping times later into the night, for example 3 or 4AM often had very few hackers compared to those who put in sleeping times around 10PM to midnight. This was a result of a metric that combines two completely unrelated factors. Another issue is that students often do not adhere to the prescribed sleeping times, and many things can certainly affect this, say a burst of inspiration while coding or if the host has an event at night. There’s an easy fix to this: stop considering sleeping times. More often than not, hackers fail to adhere to the agreed upon sleeping time (good, they enjoy the hackathon!), so there is certainly a solid argument for not considering sleeping times.
Of course, there is a better one. Currently we have an option for every hour. This is too much and overly restrictive: few students stuck to their sleeping times within the hour. For Spring 2019, we will change the options to broader ranges, say before and after 1AM and remove sleeping time from the priority queue comparator. Instead, we will treat it much like gender preference, and try to match students to those with similar sleeping times. However, we will prefer mismatched sleeping times to no match at all in contrast to gender preference. This will certainly improve distributive fairness and hopefully allow students to find hosts and hosts find students with more desirable sleeping times as well. Most importantly, this method avoids interference of two completely unrelated factors and allows fair and equal consideration of both of them without creating a mixed up metric that fails to achieve optimal performance with respect to either.
