Secret Santa is a popular holiday game in which each participant gives a gift to another participant anonymously. Most of the time, Santas are determined randomly by drawing from a hat. While this may be the easiest way to pair gift-givers to gift-receivers, this randomness leads to suboptimal gift-giving! And who wants that?

Below, I describe an integer programming formulation that I have used for a real-life instance of secret Santa to determine which giver-receiver pairings produce a globally optimal gift exchange.

What is an optimal exchange?

When signing up for this variation of secret Santa (“secret Santa with compatibility”), each participant completes a survey on what kinds of gifts they would like to receive, and what kinds of gifts they are willing and able to give. From this survey, one can calculate a compatibility score $m_{ij}$ for the matching of $i \to j$ (participant $i$ gives a gift to participant $j$).

It is quite likely that $m_{ij} \neq m_{ji}$, as participants’ tastes in gifts can differ from what they themselves would like to give. I’ll define the global compatibility of a solution as the sum of $m_{ij}$’s corresponding to the set of selected giver-receiver pairings, and the optimal exchange as the one that maximizes global compatibility.

What is a feasible exchange?

Unfortunately, most optimal exchanges are not feasible. Because $m_{ij} \ge 0$ for all $i, j$, the best possible exchanges involve each participant giving a multiple gifts to several other participants. Yet this is hardly what we want. Each participant should only have to be responsible for one gift, and thus only receive a single gift from their secret Santa.

Additionally, it would be rather disappointing if you received your assignment only to find out that you have been assigned as your own secret Santa. A feasible solution should not have any cycles of length one. For an exchange with three participants, $1 \to 2 \to 3 \to 1$ is fine, but $1 \to 1$ and $2 \to 3 \to 2$ is not.

Though less problematic, an ideal matching should also exclude cycles of length two because it’s also a little strange being the secret Santa of your secret Santa. This is yet another reason why the second example should not be considered feasible. Cycles of length one and two are unique in that participants understand the full structure of their subgraph through their assignment alone and can tell that they have been placed in a less-than-optimal pairing.

Clearly, the simplest feasible solution for $n$ participants is one single cycle: $1 \to 2 \to \cdots \to n \to 1$. However, this is unlikely to be optimal. It also may not be feasible if there are additional constraints on who can be matched with whom.

In the real-world version of this problem, I use a community constraint to make sure that participants are matched with other people they are familiar with. People can belong to multiple communities, so I define $c_{ij} = 0$ if $i$ and $j$ belong to different communities and $c_{ij} = 1$ if they have at least one community in common.

Integer programming formulation

The goal is to maximize compatibility across all pairings:

$$\textrm{maximize:} ~ ~ ~ \sum_{i=1}^n\sum_{j=1}^n m_{ij}x_{ij}$$

Subject to the single giver / single receiver constraints:

$$\sum_{i=1}^n x_{ij} = 1 ~ ~ \forall j ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ \sum_{j=1}^n x_{ij} = 1 ~~ \forall i$$

As well as the two receiver cycle constraints:

$$x_{ii} = 0 ~ ~ \forall i ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ x_{ij} + x_{ji} \le 1 ~ ~ \forall i, j$$

And finally, the community constraint:

$$x_{ij} \le c_{ij} ~ ~ \forall i,j$$

Where $x_{ij} \in \{0, 1\}$.

Secret Santa as an application of stable marriages

It is tempting to view secret Santa with compatibility as an instance of the stable marriage problem, with the givers and receivers as both the proposers and proposees. However, “stability” is not a highly desirable trait in secret Santa. Unlike marriages, gift givers and receivers do now know who they have been paired up with and do not know if their matching is stable or not.

A further problem is that there is no way to encode the cycle constraints of secret Santa into a stable marriage setup in a way that can be solved using the Gale-Shapley algorithm. If giver $i$ and receiver $i$ are not removed from each other’s preference lists, it is possible that they will be paired with each other. But if they are removed, then it is possible that some givers and receivers (not necessarily the same ones) will be without a matching. Both are considered feasible stable marriages, but are not considered feasible gift exchanges.

With a little luck (and many participants), placing participant $i$ at the bottom of their own giver and receiver lists will make cycles of length one unlikely in real-world exchanges. However, there is no way to encode the restriction of cycles of length two in any way whatsoever.

The relatively nice $O(n^2)$ running time of Gale-Shapley seems great, but there’s no guarantee it can solve secret Santa every time. And when it does, the solution makes less sense as “optimal.”

Egalitarian or utilitarian secret Santas?

An egalitarian secret Santa would attempt to maximize the compatibility of the giver-receiver pair with the lowest compatibility. By doing this, it will set the highest minimum compatibility threshold ($z$) as high as possible:

$$\textrm{maximize:} ~ ~ ~ z ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ \textrm{subject to:} ~ ~ ~ z - m_{ij}x_{ij} \le 0 ~ ~ \forall i,j$$

Both this and the utilitarian formulation are linear, so it’s just a question of preference. And while the egalitarian formulation has more constraints, unfortunately, neither is particularly fast in finding the optimal gift exchange.