At this time of year, it is common to run a gift exchange between family members or co-workers. This way, instead of everyone buying gifts for everyone else (or, more awkwardly, not everyone else!) there is an organised pool where everyone buys one gift for a randomly-assigned friend, relative or colleague, and similarly everyone receives one gift. These gift exchanges are often called ‘Secret Santa’, since the identity of the person buying each gift is kept secret.

In order to administer this, the traditional method is to put the names of everyone participating on small, identical pieces of paper into some kind of container (traditionally: a Santa hat) and for everyone to pull out a piece of paper. But what if everyone is working remotely? Or you will not see all of your family until Christmas itself? Or what if, like me, you would like to organise a festive gift exchange between a group of your friends, who a) all live in different parts of the country and b) are all mathematicians, and so would appreciate a more mathematical way of doing things?

Maths to the Rescue!

Do not worry: There definitely is a mathematical way of doing this. Many possible ways, in fact, with varying levels of complexity. What we are essentially looking for is a way to assign a random permutation to a group of people – rearranging the ordering, to assign each person someone to buy a gift for – without anyone finding out what that permutation is.

In maths and computer science, there are a variety of clever protocols used to transmit and record information which allow for such things to happen without passing on unnecessary information. Back at the 8th HLF in 2021, we heard from laureate Avi Widgerson, who in his lecture mentioned Zero-Knowledge Proof Protocols, which I wrote an article about at the time. These allow someone to prove they know a piece of information – like a secret password, or the solution to a sudoku – without actually revealing what that information is.

Zero-knowledge protocols can also be designed to send other forms of information too – in this case, we need each person to find out only who they need to buy a gift for, but without finding out who is buying a gift for them (or for anyone else). I looked around online to find something simple I could use for this, and found an answer in the traditional place – a post on Math Stack Exchange.

The protocol described there can be summarised as follows. For N people who wish to participate in a secret gift exchange:

• Person 1 chooses a random number \(x_1\), and sends it to Person 2.
• Person 2 chooses their own random number \(x_2\), and creates a list of the two numbers so far. They then choose a way to reorder this list so they can pass it on without anyone knowing which was the number they added. They send this list of two numbers to Person 3.
• Person 3 chooses a random number \(x_3\), adds it to the list and shuffles again, and this process repeats until Person N receives a list of \(N-1\) numbers, appends \(x_N\) to the list, shuffles one final time and sends it back to Person 1.

At this point, each person has contributed a number to the list, and the ordering of the numbers has been randomly shuffled. 

• Person 1 finds their own number in the list, and notes where it is to determine who they need to send a gift to. For example, if it is in position 4 on the list, they need to send a gift to Person 4.
• Before passing the list on, Person 1 changes their own number in the list to a new random number, \(y_1\). Without changing the ordering, they send this list to Person 2.
• Person 2 can also find where their own number sits in the list, and notes its position before swapping it out for a new number \(y_2\), and sending it on to Person 3.
• This continues until the list makes it back to Person N, who can also note who they are buying for.

This gives a random shuffle, and at each stage nobody can find out any information they are not supposed to. In particular, even though Person 2 saw what Person 1’s first random number \(x_1\) was, when the list comes back to them, that number has been swapped out for \(y_1\) (and all the other numbers are \(x_i\) they have not seen before), so they cannot see where Person 1’s number is in the list any more. This continues through the list, so nobody can determine any information about their Secret Santa, but they can see who to buy for.

This protocol is reasonably simple – the two runs around the list are necessary to prevent people being able to determine information they should not – but two goes around is not too onerous, and picking random numbers (and random list shuffles) is simple enough to do. But as is so often the case in mathematics, something being simple means it is less likely to be optimal. This method is not perfect, for a few reasons:

Firstly, while nobody necessarily has information they should not, one person gets to make a very important decision. Person N, who is picking the final permutation, decides the final ordering of gift-giving. Now, since they do not know which random numbers anyone else picked, they cannot use this power much – there is no way to influence who is buying a gift for them, for example – but they do get to choose who they are buying a gift for, since they just need to put their own number in that position in the list.

Assuming your mathematicians are being honest and fair (and enjoy generating random permutations as much as I do), you should be able to trust Person N to pick a random permutation and not try to influence the result. In the Stack Exchange post, the original author suggests a way to prevent this by using a seed to generate the ordering: Given a particular shuffling method that uses an input number, such a number can be mutually agreed upon – and after the gifts have all been opened, it can then be checked whether the shuffle used by Person N was the one you get from that seed number using that process, to make sure there was no cheating.

This feels like an additional complication, and makes the process slightly more fiddly for everyone (plus, it means everyone can eventually find out who all the Secret Santas were, and depending on how well-received the gifts were, that may be a bad idea). But this is only one of the ways in which this method falls down.

Totally Deranged

Another important factor in the usefulness of this method is that when you pick a random shuffle, or permutation, you are not guaranteed that the shuffle will not leave anyone buying a gift for themselves. In fact, this is actually more likely than not. Just think about the possible orderings you could shuffle just a set of three things into:

123 132 213 231 312 321

Of these, four end up with someone buying their own gift and only two are a true ‘shuffle’, known mathematically as a derangement. As the number of objects grows, the proportion of shuffles with this property stays relatively constant, getting closer and closer to the value \(\frac{1}{e}\), which is about 0.36. This means about two thirds of the time, you will find that at least one person (and possibly more than one) is buying themselves a present.

As much as this might suit some people (they can get something they really want, and pretend to be impressed by how thoughtful the gift is), it is mathematically unsatisfying. There is not really an easy fix for this – the original Stack Exchange post suggests that if this happens, whoever has pulled out their own number can announce this to the group – but this would then mean starting the whole process again.

Since this has a \(\frac{1}{e}\) chance of happening, you will expect on average to restart the process \(e\) times before you find a true derangement. If each restart involves two rounds of list-sending, and your participants are as slow at replying to emails as some of my mathematical friends are, this could take a good while. Interestingly though, when I ran this with seven people, we (thankfully) got a derangement first time.

For seven people, the amount of the time you would expect it to work would be around 36.56% – there are 5040 possible permutations on 7 objects (calculated as 7! = 7 × 6 × 5 × … × 2 × 1, as I discussed in my previous blog post on permutations) and of these, 1854 are derangements. (For more detail on how to calculate this, there are a variety of formulae given in the Wikipedia post on derangements).

But in this case, I think our chances were actually higher. Even though our Person N promised they had honestly stuck to the brief and generated a truly random permutation, they would have been able to see immediately if the permutation they chose was one in which they have to buy their own gift. In this case, I suspect they might have re-run their randomising process to create a new one where this was not the case.

This means that we can exclude all the permutations in which person N (in our case, \(N=7\)) was permuted to position 7 of the list – and the number of possible such permutations is simply 6! – the number of ways to rearrange six people. Removing these from the equation means we actually had more like a 42% chance of success, and on that basis I am slightly less surprised we managed it first time.

Even though this method has its flaws, I am pleased with the compromise of simplicity and just-about-usefulness you get with it. But I am sure there are many other ways to do this, and it is a mere hint of the kind of ingenious protocols that are out there, being used in computer authentication and verification systems, and for proving the identity of parties and sharing data securely online.

So if you are organising a Secret Santa or equivalent seasonal gift exchange, consider letting maths do the thinking for you, and use a zero-knowledge protocol to guarantee you keep Santa a secret!