2020-2FORIF_Hackathon_C-

2020-2 포리프 해커톤 알뚝깨 씨쁠쁠 '같이여행가듀오'

Members from the Algorithm Mentoring group undertook a project for the 2020 Winter Forif Hackathon related to the Stable Roommate Problem. We will be implementing Irving's algorithm and assigning partners for each of the Forif members. We distributed a survey among the Forif members before the Hacackthon, asking their travelling perferences, such as whether they enjoy historical sites or nature more. According to these perfernce data, we will be assigning travelling partners in an algorithmic way that ensures the outcome will lead to biggest overall satisfaction.

Stable Roommate Problem

The stable roommate problem is that of mathing two groups of n people, both of whom has ranked the members of the opposite group in perfernce, so that no unmatched couple perfers each other over their current partner.

For exmample, if John and Peter, Sam and Paul are matched couples, but John perfers Sam over Peter, and Sam also perfers Johm over Paul, this is not a stable match.

Irving's Algorithm

Irving's algorithm [1] was proposed by Irving in 1984 as a way to solve this problem. The algorithm is consisted of three phases.

First Phase

(1) Person x proposes to y   
   (1-1) If y holds no proposal that is from someone they prefe more than x, they hold x's proposal.   
   (1-2) Otherwise, he rejects it.   
(2) x continues proposing according to the order appearing in his/her perference list, until somebody holds the proposal.

Above is a perference list of 6 people, where the goal is to make 3 couples in a stable match. Charlie proposed to Peter, Peter to Kelly, and Elise to Peter. Peter rejects Charlie's proposal since Elise is higher in his perfence list, according to step 1-2 of the algorithm.

So Charlie's proposal to Peter will become invalid, and he will have to propose again to the person on the top of his perfernce list which would be Paul. If we keep perform the step several times, we will end up with a reduced perference table looking like this.

Second Phase

Now everyone holds a unique proposal, so in phase 2 we remove entries from the perference lists that are less prefered than the person's proposed parter. For example, Paul holds a proposal from Charlie, so everyone in Paul's list that is less prefered than Charlie(Sam, Peter, Kelly) will be removed. We do this for everyone and as long as the reuslting table has no empty list, we can find a stable match.

Third Phase

Finally, we check the lists still containing more than one person and find existing cycles. We make two sets of people p and q, where p₀ is the first person in the table with more than one person in their list. In our case p₀ is Charlie since he has Paul and Sam in his list.

We then fill out the table of p and q according to the rules shown below. If someone is repeted in p, that means we have a found a cycle and we eliminate it by making q_i reject the proposal from p_i+1.

Here, Charlie is repeated in p, indicating a cycle has been found, so Pual(q₁) rejects his offer from Charlie(p₂) and Sam(q₀) rejects her offer from Elise(p₁). Now we have our stable match! In some cases, phase three has to be repeated several times for a stable match to be found.

Hackathon Result

We implemented Irving's algorithm here in C++ and applied it to our own perfernce list we made through survey data. This allowed us to come up with a stable match of travelling partners which we presented in the Forif Winter Hackathon.

References

[1] Irving, R.W. (1984). An Efficient Algorithm for the “Stable Roommates” Problem. https://uvacs2102.github.io/docs/roomates.pdf