The Secret Santa game is an end-of-the-year tradition in many places of the world. It is common to play this game among friends, family, and coworkers. Although there are many variations, the game's dynamic is based on the exchange of gifts among the players. In the most known version of the Secret Santa game, all players take two roles: the gifter and the recipient. When in the role of a gifter, the player gifts a recipient, while in the recipient role the player receives a present from a gifter.
Back in the day, the mechanism to assign to each gifter a recipient was simple: draw a name out of a bowl. It is easy to see that in an n-player Secret Santa game there are n! configurations that can happen. The first gifter to draw a name would randomly select one recipient out of n possibilities, while the second gifter would select one out of n-1, and so on. Since the goal of the game is to boost the personal connection between the players, there is a basic assignment rule that must be fulfilled: no player can be its own gifter/recipient. That rule limits the number of configurations to n-subfactorial (equal to [n!/e]). This means that the classic assignment method has approximately a 63.2% chance of generating an infeasible game when there are at least 6 players.
Nowadays, with the help of algorithms, there are multiple online tools available to fulfill the basic configuration rule and organize the game. One possible representation of an n-player game configuration is based on an n-sized list, as shown below. The gifter and the recipient pair roles are assigned based on their positions in the list. The p-th listed player is the gifter of the recipient on position p+1, and the n-th listed player is the gifter of the first listed player. Since a player cannot be assigned to multiple positions, this listed representation always results in a valid game (considering a list of at least two players).
Additionally, this listed representation has a great embedded advantage: it can easily determine games with single or multiple loops (by subdividing the initial list into smaller lists, like the image below). This means that the Secret Santa organizers are able to use algorithms to find game configurations with new assignment rules! Beyond the number of possible loops, they could establish that no consecutive games could repeat a gifter/recipient pair, or that a subgroup of players cannot be one another's gifters/recipients (for instance, parents and their children).
Although those customizations could increase the fun of playing the game, they also drastically reduce the number of feasible configurations. The game can become so over-constrained that just a few, maybe none, assignments can fulfill them all. This hard-to-find assignment solutions context is common to many companies. Resource allocation problems are a classic example:
Like the Secret Santa game algorithm, there are technologies that can support the decision-making process in those cases. Many of them, such as integer programming, constraint programming, and heuristics, are used by Cassotis in its projects. However, the choice of technology should always consider many factors, which have been discussed in previous posts (like Technology-oriented projects and What's a heuristic and when you should use it).
Finally, I hope that the reader's gifter has the same ability as Santa Claus and that you may enjoy this great time of the year. Merry Christmas!
Co-author: Fabio Silva - Senior Manager at Cassotis Consulting
R. da Paisagem, 220, sala 11S, Vila da Serra, Nova Lima - MG, Brasil