A Mathematical Exchange of Gifts

BLOG: Heidelberg Laureate Forum

Laureates of mathematics and computer science meet the next generation
Heidelberg Laureate Forum
Image credits: Julia Larson

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!

Avatar photo

Posted by

is a mathematician based in Manchester, who gives talks and workshops on different areas of maths. She finished her PhD in 2011, and since then has talked about maths in schools, at science festivals, on BBC radio, at music festivals, as part of theatre shows and on the internet. Katie writes blog posts and editorials for The Aperiodical, a semi-regular maths news site.

5 comments

  1. Katie Steckles wrote (20. Dec 2023):
    > […] a true ‘shuffle’, known mathematically as a derangement. As the number of objects grows, the proportion of shuffles with this property [… approaches …] the value \( \frac{1}{e}\)

    > […] For \(N\) people who wish to participate in a secret gift exchange: […]

    > […] at least one person (and possibly more than one) […] buying themselves a present […] is mathematically unsatisfying. There is not really an easy fix for this […]

    Let \(\mathcal S\) and \(\mathcal T\) be (not necessarily distinct) subsets, each with at least two elements, of the set \(\text{DER}_N\) of all distinct derangements of \(N\) elements, such that

    \(\forall p \in \mathcal S, q \in \mathcal T : q \circ p \in \text{DER}_N\)

    where \(q \circ p\) denotes the successive execution of permutation \(p\) followed by permutation \(q\).

    (Such sets \(\mathcal S\) and \(\mathcal T\) are garanteed to exist for each \(N \geq 5\); e.g. \(\mathcal S\) and \(\mathcal T\) being equal, both consisting only of the derangement “all-shift-one-place-up-and-wrap-the-end” and the derangement “all-shift-two-places-up-and-wrap”.)

    With this, I can think of the following “easy fix” secret gift exchange procedure:

    • Given the number \(N \geq \) of participants in the procedure, all know and agree on their identity as participant \(P_1\) through participant \(P_N\).

    • Participants \(P_1\) and \(P_N\) agree (in public, as applicable) on two specific subsets \(\mathcal S\) and \(\mathcal T\) of derangements with properties as described above.

    • Participant \(P_1\) chooses (and remembers) an arbitrary number \(x_1\) and mails it to \(P_2\), as the first entry in an ordered list \(\mathcal X\).

    • Participant \(P_2\) chooses (and remembers) a number \(x_2\) different from \(x_1\), appends the list accordingly, and mails it to \(P_3\).

    • Participant \(P_3\) chooses (and remembers) a number \(x_3\) different from any number in the received list, appends the list accordingly, etc.

    • Participant \(P_N\) chooses (and remembers) a number \(x_N\) different from any number in the received list, and appends it, thus obtained the complete list \(\mathcal X\).

    • From the agreed set of derangements \(\mathcal S\), Participant \(P_N\) chooses (secretly) one permutation \(p \in \mathcal S\) and applies it to list \(\mathcal X\) (exactly once), mailing the resulting list
    \( \mathcal Y := p[ ~ \mathcal X ~] \)
    to participant \(P_1\).

    • From the agreed set of derangements \(\mathcal T\), participant \(P_1\) chooses (secretly) one permutation \(q \in \mathcal T\) and applies it to list \(\mathcal Y\) (exactly once; and honestly, of course). The resulting position index of entry \(x_1\) in the resulting list
    \(\mathcal Z_0 = q[ ~ \mathcal Y ~ ] = (q \circ p)[ ~ \mathcal X ~ ]\)
    identifies the participant for whom participant \(P_1\) will buy/prepare a gift.

    (The properties of the agreed sets of derangements, \(\mathcal S\) and \(\mathcal T\), guarantee that the index of entry \(x_1\) in the list \(\mathcal Z_0\) differs from \(1\).)

    And now: …

    • Participant \(P_1\) chooses yet another number, \(z_1\), which must be different from any entry in list \(\mathcal Z_0\), replaces entry \(x_1\) with \(z_1\), and mails the thereby resulting list \(\mathcal Z_1\) to \(P_2\).

    • In list \(\mathcal Z_1\) participant \(P_2\) finds entry \(x_2\), whose “position” index identifies the participant for whom participant \(P_2\) will buy/prepare a gift.

    (The value \(x_1\), which participant \(P_2\) could have recognized as being associated with participant \(P_1\), is not included in list \(\mathcal Z_1\). And the value \(z_1\), which is included in list \(\mathcal Z_1\) since it was put there by \(P_1\), cannot be recognized by participant \(P_2\) nor by any of the following, as being associated with participant \(P_1\).)

    • Participant \(P_2\) then chooses yet another number, \(z_2\), which must be different from any entry in list \(\mathcal Z_1\) (and which might differ from value \(x_1\), too), replaces entry \(x_2\) with \(z_2\), and mails the thereby resulting list \(\mathcal Z_2\) to \(P_3\). And so on, until …

    • Participant \(P_N\) receives list \(\mathcal Z_{(N – 1)}\) and finds entry \(x_N\) whose “position” index identifies the participant for whom participant \(P_N\) will buy/prepare a gift.

    (Other entries in list \(\mathcal Z_{(N – 1)}\) don’t allow any association to the entries in the ordered list \(X\) which participant \(P_N\) had seen before.)

    Wishing y’all a merry secret gift exchange!

  2. Nice work! This solves some of the issues – but isn’t Person 1 now able to choose who they buy a gift for, in the same way that Person N could in the other example? Maybe not a completely free choice, but given a large enough subset of permutations they would be able to influence the outcome, I think?

    I’d also be interested to see an example of two subsets S and T that include some more non-trivial permutations – obviously your example was a minimal version, but how large can those sets be and still have the property required? I’ve considered something where they each consist of permutations that fix and derange different subsets of the indices… but I guess that kind of means you’re just doing two separate gift exchanges 🙂

    Also: is there a way to set up the two subsets so that all derangements are possible (and, pipedream: equally likely)? This is a strength of the original – that if the permutation is a random one, any arrangement is equally probable, but obviously this is why it’s so likely to fail to be a derangement…

    Thanks for your comment, and I hope you enjoyed playing with this!

  3. Wie funktioniert der Prozess, um eine zufällige Permutation zuzuweisen, ohne dass jemand unerwünschte Informationen erhält? Gibt es mögliche Schwächen in dieser Methode?
    Tel U

  4. Katie wrote (22.12.2023, 00:11 o’clock):
    > Nice work! [… (21.12.2023, 12:59 o’clock)]

    Thanks; but I can’t take full credit because — without realizing it at first — I had precisely duplicated the part of the procedure to which the above SciLog article referred as “swapping”.

    > This

    … “compatible sets of derangements”, i.e. my remaining original contribution in the preceding comment …

    > solves some of the issues – but isn’t Person 1 now able to choose who they buy a gift for, in the same way that Person N could in the other example? […]

    Yes, although only within the choices available in the applicable set \(\mathcal T\) of derangements.

    But I can suggest more improvement, namely to completely conceal/anonymize/encode “the number” \(x_1\) by which \(P_1\) could recognize and prejudge the outcome. The implementation practicalities:

    Start out as above; but instead of player \(P_N\), let player \(P_{(N – 1)}\) apply a (secretely chosen) derangement from the fixed applicable set \(\mathcal S\) to the available ordered list

    \[ \{ x_1, x_2, …, x_{(N – 1)}, N \}. \]

    Of course the rules for coming up with “the numbers” \(x\) must therefore be amended such that the value \(N\) appears only once.

    The resulting “once-deranged” list is passed to \(P_N\), who is then supposed to apply (and memorize) a secret, invertable and “generally hard to guess” encoding

    \( \mathcal C : \mathbb R \longrightarrow \mathbb R \)

    to each entry.

    The resulting “once-deranged and encoded” list is passed to \(P_0\), who applies the (secretely chosen) derangement from the fixed applicable set \(\mathcal T\); at least without thereby being able to tell right away for whom to buy a gift.

    (However, some more general clues may still derive from the specificities of the proposed sets \(\mathcal S\) and \(\mathcal T\).)

    The resulting “twice-deranged (finalized) but still encoded” list is passed along the step-by-step chain of one-way-communication all the way back to player \(P_N\), who is now supposed to decode — honestly, i.e. by applying precisely the inverse function \(\mathcal C^{(-1)}\) to each entry in the list; without any additional permutation.

    In doing so, \(P_N\) will find the value \(N\) at a certain position in the decoded finalized list; by construction (of compatible sets derangements) not at the very end of the list. \(P_N\) now swaps some other unique value \(z_N\) for the value \(N\) at this position, and passes the resulting list to player \(P_1\); who recognizes and notes the position of entry \(x_1\), swaps it for value \(z_1\), and so on until it finally remains for player \(P_{(N – 1)}\) to recognize and note the position of entry \(x_{(N – 1)}\).

    > I’d also be interested to see an example of two subsets S and T that include some more non-trivial permutations […]

    > Also: is there a way to set up the two subsets so that all derangements are possible [as composition] (and, […])

    Those are surely worthwhile interests of mathematicians.

    Yet another question is how to check the presumed “honesty and diligence” without the “Secret Santa” becoming too much of a “Public Santa”; especially if the outcome doesn’t give outright cause for complaint.

    p.s.
    I plan — hopefully within a week — to submit this improved proposal as an answer to the corresponding MSE question; of course acknowleding the groundwork laid already by the answer linked in the above SciLog article.

Leave a Reply


E-Mail-Benachrichtigung bei weiteren Kommentaren.
-- Auch möglich: Abo ohne Kommentar. +