How I Used Slack to Optimize This Year’s Secret Santa So It Wasn’t Awkward for Anyone Involved 🎅
A full-proof recipe combining emojis, combinatorial optimization, and a dash of eggnog that didn’t make anyone call in sick this year.
It began innocuously enough. Shortly after my co-worker and I returned from the desert where we watched our teammates shoot through a vacuum tube for the very first time in history, my co-worker — a software engineer in the simulation group — posted the following to our team’s general Slack channel:
My Co-worker, 10:03am on just another Monday:
“OFFICIAL SECRET SANTA VOTE: vote ‘thumbs up’ or ‘meh’ emoji below.”
After the group largely voted in favor (with a few cheeky members choosing the third option- a dancing dog), I figured I’d take a stab at making the assignments over Thanksgiving break to see if I could come up with anything interesting.
Secret Santa — to jog your memory — is a guessing game of gift-giving in which members of a group are randomly assigned to give a gift to one other person in that group, only revealing themselves after the gifts are exchanged. As a child, I fondly remember attempting to unmask my Secret Santa hidden amongst my siblings in the weeks leading up to Christmas morning.
I also remember a time in the 6th grade when I was gifted a box of cologne from a classmate I barely knew, despite not having hair under my armpits yet.
Now that I am older, “games” — for better or worse — have technical, theoretical definitions that I learned in textbooks and were seared into my long term memory from the emotional trauma of cramming for final exams. So when my co-worker posed the idea, it got me thinking- what’s the algorithm underneath Secret Santa? Surely it can’t be that complicated; heck, my mother — whose background is definitely not in computational mathematics — had been able to set up the assignments without the help of a computer for over a decade.
From a technical perspective, Secret Santa assignments basically boil down to permutations with the added restriction that, after assignment, no person can be assigned to themselves. After some quick Google-fu, I learned that this variation of a permutation has its own definition, known as a derangement. Generating a derangement is easy enough- a perfectly-acceptable algorithm would just randomize permutations of a set and stop when the condition of a derangement is met (simulation FTW 👍🏽). All you need to do is to find some online Secret Santa generator, throw in people’s names, belt out some yuletide carols, and you can call it a holi-day.
Sure, I could’ve done that, but I wouldn’t be doing the “Machine Intelligence” part of my team’s name any justice if I didn’t ask the question- can we do better?
From an economics standpoint, it can be argued that a randomized Secret Santa pairing leads to an inefficient market. Supporting this thesis is a study from Duke University suggesting that the economic loss of intentional gift-giving is about 25% to 33%. Perhaps this guy was right; anecdotally, I can recall that during my youth somewhere between one-in-three and one-in-four gifts from my aunts seemed to be intended not for me, but for my little brother or sister (if you are reading this, don’t worry Auntie, I still have my Daffy Duck tape dispenser 😇). With randomized assignments in Secret Santa, you might guess the “economic loss” is even higher (I use the academic term “loss” hesitantly, as most us behave like normal human beings during the holidays and believe strongly that “it’s the thought that counts”).
So why does inefficiency in gift-giving happen? In my childhood case, it could be boiled down to the fact that I rarely saw my aunts as they lived 2,000 miles away, and therein lies rub- they didn’t know me in the same way that perhaps my parents did. To rectify this inefficient market, however, we have to incorporate external information into the otherwise blissfully-ignorant Secret Santa game.
A Motivating Example: Bachelor in Paradise, Noah’s Ark Edition
Humor me for a second. You are probably familiar with the story of Noah’s Ark (shout out to all my Old Testament readers). If Noah wanted to maximize the reproduction of the barren Earth after God’s wrath had been laid, he wouldn’t just randomly assign animal pairings now would he? No, of course he wouldn’t do that! We can imagine that if the Holy Ark had private honeymoon suites, Noah would’ve paired up animals based on the external information of their “species”- the assumption being that pairs of the same species are much better at reproducing than pairs of different species.
In order to maximize reproduction of the Earth, Noah used external information to get the most out of his group’s pairings. This absurd example only serves to demonstrate that we can incorporate external information into our Secret Santa pairings in order maximize our group’s well-being.
WARNING: TECHNICAL COMPUTER-RELATED CONTENT AHEAD.
Be warned (or bored), all ye who read further…
(Possibly Boring) Technical Content Part I: Scraping Slack
Enter the workplace “productivity” tool Slack. Slack (and all social media in this context) is great if you are not scared sh*tless by that fact that interpersonal interactions are now etched permanently in bits. There are surely innumerable ways to quantify “interaction” between people in 1s and 0s, but the one my particular team is fond of is the beloved and liberal use of the emoji. We take our emoji game pretty seriously, to that point that the best contributions and ribbings are awarded with custom emojis that capture a team member’s idiosyncrasies for all perpetuity.
Rather than engineer some new-fangled deep learning model that ingests human language Slack messages, I determined that I could capture a measure of how familiar someone is with someone else by simply counting the number of reactions a member has to another’s Slack messages (by way of an aptly applied reaction emoji). To be certain, this method by no means captures all the nuances of human relationships, but true to econometric modeling, it probably provides some positive correlation with it, and is therefore better than the alternative, which is to omit it altogether. So, a plan was hatched to construct a matrix of emoji counts between all members of this year’s Secret Santa game. In the pursuit of counting Slack reactions, I had two problems to overcome.
The first is that, regrettably, I am just an individual contributor in my company and we have a totally reasonable and just (and awesome) IT department that isn’t about to grant administrative privileges to new hires so that they can see all of the quasi-private user information contained in the company’s global Slack database. The second problem was that I am not about to manually scroll through tens of thousands of messages in my limited time off in order to extract by hand the data I was after. Thankfully, there are plenty of open-sourced tools out there that allow you to automate “scraping” that addressed both problems for me, so I took the opportunity to re-familiarize myself with browser automation and fired up a Selenium script using Python and a headless Chrome instance that mimicked the way I would otherwise go about collecting this data.
The script is conceptually simple- you scroll back to the very first post at the beginning of time and enter an indefinite loop that extracts the poster and time, then “hovers” over the emojis and extracts the reactions, all before “scrolling” to the next post and repeating. After building in some time delays to account for lazy-loaded messages and Slack’s event-driven DOM rendering, I had a script that scraped ~45,000 messages and their reactions into a database in about 12 hours. Not exactly production-level performance, but since this was a one-off, it suited my purposes just fine.
In order to cast this measure of familiarity into risks associated with gifting a well-received gift, I normalized each individual’s total reactions to all the others by casting them as percentages and subtracting each value from the maximum (basically taking a complement). What this left me with was a matrix containing, for each team member, a list of “risks” associated with choosing a gift for every other member on the team, ranging from a low of 1 for the person they reacted to the most over the year, to some greater number, bounded by 100, for the person they interacted with the least.
With this measure of familiarity accomplished by way of estimating gift-giving “risks”, I turned my attention to solving the Secret Santa assignment programmatically, and in all hope, for the optimal case.
(Possibly Boring) Technical Content Part II: Optimizing Pairings
Even though I studied this kind of problem solving in graduate school, I was a little rusty and figured I might have to enumerate every possible assignment and take the permutation that minimized the overall sum of everyone’s risk of choosing well-received gifts for their assignments. We have 16 members in our team, so a quick reaction might have you recognizing there are 16! (16 factorial) potential permutations I would have to evaluate in order to find the best. Don’t let that little exclamation mark fool you- “16!” expanded is about 21 trillion, but it turns out it would only amount to a paltry 7 trillion arrangements because a derangement allows you to ignore the arrangements in which a team member was assigned to themselves. In any case, an exhaustive search of this size would probably require me to solve it on a much-faster computer than my MacBook Pro in order to come up with a solution in any reasonable amount of time.
Well, I wasn’t satisfied with the prospect of having to turn to AWS for a simple Secret Santa so I strapped on my Google hat again and started researching ways to optimize a derangement without an exhaustive search. “Secret Santa optimization” turned up little, but after further reading, it turns out that the problem of assignment belongs to the fundamental class of computer science problems known as — you guessed it — assignment problems. After more research, it appeared that this was one of the most straight-forward classes of assignment, and as such, has a whole history of solutions that bring the search for the optimal assignment down from factorial time to polynomial time. In our case, it turns the search for a naïve solution to a 16-person derangement that relies on trillions of comparisons into a “minimum cost flow” problem backed by an iterative algorithm requiring thousands of iterations at most, meaning you can find the optimal solution nearly instantly on virtually any computer you can get your hands on today.
Relieved, I turned back to the code knowing I wouldn’t need a dedicated computer for this task. If this were a grad school project, I would be required to write the solver from scratch, but thankfully, those days are behind me and honestly, who has time for that anyway when freshly roasted turkey is beckoning? Surely not me, so I opted to use Google’s OR-Tools suite that has a convenient Python wrapper and easy-to-follow documentation and examples. All you need to do is pip install the package and fire up a Python interpreter and you have access to some of the world’s fastest optimization algorithms at your fingertips.
After loading up my familiarity matrix and transforming the data into the node and vertex data types that an assignment problem of this type must be cast as, all I needed to do was eliminate some trivial vertices that represent a team member being assigned to themselves. I was pleased — so pleased then — to hit ‘return’ in my interpreter and see an optimal solution pop out with an execution time on the order of a thousandth of a second.
Wow! So cool. After spending many years of my career waiting around for large data processing jobs to complete, I had forgotten how powerful optimization can truly be (optimization FTW 🤟🏾). But enough of the boring implementation details, the best part about this project is the people, so let’s have a look at the pairings!
The Results: Still Technical, but also Human.
To reiterate, each one of the 16 members could’ve been assigned to one of 15 other people on the team, and knowing my team members first-and-foremost as human beings, the assignments had me giddy. After optimization, seven members were assigned to the one person on the team they reacted to the most on Slack, with ten total members being assigned to someone in their top 4. The remaining six were assigned to members falling between their 5th and 10th most-reacted-to, leaving (quite amazingly) not a single member who was assigned to someone that fell in their bottom 5.
Further introspection of the results shows that those who were assigned to someone in their top 5 reacted more often to fewer individuals, whereas those who were assigned to teammates in their respective middle ranges were more uniform in their distribution of reactions across the team. This is not a coincidence, rather it is an incredible feature of the optimization. For example, if you are nearly equally-familiar with all members of a group, the added risk of you choosing a well-received gift for the person you are least-familiar with compared to the person you are most-familiar with is much smaller than the risk someone might face if they had to choose for someone they do not know whatsoever. It is better off for the welfare of the entire group that the latter person, who is familiar with only a few people, is not assigned to someone with whom they are not familiar with at all.
The final analysis that demonstrates rather conclusively that an optimized Secret Santa is better than a random one is to compare the total sum risk of the entire group in the optimized case against the long run average sum risk of the group in the randomized case. Since generating a naïve derangement takes almost no time, I ran one million random assignments and took the average sum risk. And, in the end, by introducing an optimization objective in the form of minimizing risk (as measured by Slack message reactions), the optimal assignment decreases the total risk over a random assignment on average by over 50%. This is a pretty amazing result that demonstrates the power of optimization, and should hopefully lead to happier givers, happier receivers, and a general increase in the team’s well-being during this year’s Secret Santa.
Phew! Now time for that eggnog.
So Justin, how did it turn out?
Well, the one little bit of feedback I have received so far was from my co-worker that originally proposed the idea. He took one look at the assignments and agreed with me- they really do seem “optimal” on a human-to-human level. Beyond that, I am — in all likelihood — not going to attempt to quantify the total economic loss of my team’s Secret Santa this year by polling my teammates about the perceived value of their gifts, as that would completely violate the immeasurable nature of the Christmas Spirit. Besides, we all know what happened to the last guy who let his numbers get too much in the way of Christmas, and the one thing I could really do without this December is three ghosts rapping at my window reminding me of my past failures. I’m just trying to do some good over here, O’ Ye Ghosts of Christmas, so please do me a solid and let us exchange our gifts in good spirits 😇.
Happy Holidays readers- and from my team to yours, may all your gifts be optimal!
By the way, looking for a job? We’re hiring all kinds of engineers at Virgin Hyperloop. Check us out and tell ‘em I sent you. I’d really like a raise next year 😉.
