In Secret Santa, rather than each person in a group getting a present for each other person, everyone receives just one present, from one person assigned to choose theirs. How do you decide who gets who in secret santa? Here are some of the things you might want to be true (with what I hope are some suitably fancy-sounding names):

Secrecy

Weak: No-one knows who has them
Strong: No-one knows who anyone has (except themselves)

Mixing

Minimal: No-one is assigned themself
Medium: No pair are both assigned each other
Strong: Everyone in the group is part of a single chain of gifts

Knowledge

In a group where some people don’t know others, you may want to ensure everyone is assigned someone they know.

Here are some comments on these conditions:

In fact the ‘minimal mixing’ conditions is redundant: if no-one can know who has them, necessarily no-one can be assigned themselves. I include as a separate requirement for emphasis.
Why wouldn’t we want pairs assigned each other? I suppose it feels against the spirit of the thing, maybe because you get to directly compare who gave the better gift.
‘Strong mixing’ can makes for fun present giving sessions, where I give my present first, then the receipient gives their present, and so on, and we never have to start again with someone new.
The ‘knowledge’ condition can also adapt to impose other types of restriction. For example, you might not want for anyone to be assigned their spouse, or their ex. Let’s focus primarily on groups where everyone knows (and likes!) each other so we can ignore the ‘knowledge’ requirement.

Puzzle:

How many people do you need before it’s possible to meet both a mixing condition and a secrecy condition? Have a think about it before you scroll down.
____________________________________
Let’s think about it systematically.

With 1 person we can’t achieve even the minimal mixing condition.
With 2 people we can achieve minimal mixing but never weak secrecy.
With 3 people we can’t achieve weak secrecy and minimal mixing simultaneously. Why not? If we have a scheme that satisfies minimal mixing and I’ve been assigned you, then you can’t have me (because otherwise the third person would have themself). So they must have me.
With 4 people we can achieve strong secrecy and strong mixing. Here are two possible chains:

A has B has C has D has A
A has B has D has C has A

Secret santa schemes

A secret santa scheme or algorithm is a method of assigning to each member of the group someone to buy a present for, and a ‘good’ scheme will satisfy some secrecy condition and some mixing condition. Moreover, if there’s to be any hope of persuading a group (say your family) to agree to an algorithm, it shouldn’t be too complicated. Here are some options.

External assigner: Someone who is not part of the group chooses who each person is assigned

Good traits: It's simple; It can meet whatever secrecy and mixing conditions you want (provided, as with the puzzle, there are enough people); It can even knowledge constraints (provided these aren’t too constrictive).
Bad traits: It requires persuading someone else to do work for you, and they don’t even get a present as a reward.; The assigner could be susceptible to bribes!

Internal assigner: Someone within the group chooses the assignment

Good traits: It's simple; It can meet whatever secrecy and mixing conditions (and knowledge) you want for everyone but the assigner
Bad traits: It obviously fails secrecy for the assigner; The assigner gets to choose who sources their present, so may choose the best gift-giver!

Names in a hat

This is probably the most popular scheme. Everyone puts their name on a bit of paper and they’re shuffled together in a hat. People successively draw a name from the hat, and that’s who they're assigned.

Good traits: It's simple; No-one has any information about who has them unless... (see the bad traits)
Bad traits: You can be assigned yourself! (it fails ‘‘minimal mixing”)

Re-roll names in a hat

Here’s an easy fix for the names in a hat algorithm. You do exactly as described above, but, if anyone has their own name, you put all the names back and start again.

Good traits: It's still fairly simple; No-one knows who has them
Bad traits: You can still have pairs of people both assigned each other (i.e. it fails ‘‘medium mixing”); It might take a lot of attempts! (See the ‘conclusions’ section where this is discussed a little more.)

Names in envelopes

Your might be thinking it’s about time for a not-so-simple algorithm, and you’d be right. Here's one:

I assign everyone a number. For each person, I write a piece of paper with their name on the front and their number on the back.
I leave each piece face down on a table where there are also correspondingly numbered envelopes. I leave the room.
You enter the room and place each piece of paper in an envelope (without looking at the name on the front) then leave again.
I return and hand each person their envelope (I do this with you outside the room so you don’t get to see which envelope goes to who).
You can come back in once I’m down to just your envelope, which I then give to you.
Everyone opens their envelope. The name inside is who they have to get a present for.

As I’ve presented above, this doesn’t meet the minimal mixing requirement, but that can easily be fixed: you’re not allowed to put number 1 in envelope 1 and so on. After this fix it still doesn’t meet the weak secrecy requirement. (Why not? Think about it for a moment!)

__________

Thought about it? For almost everyone it’s weakly secret. However, imagine:

In the step 1 I assign you number 1.
In step 3 you put paper 1 in envelope 2 and paper 2 in envelope 1.

Then when I give you envelope 1 in the final step, you learn that your number is 1, so you can work out that person 2 is assigned to get your present. Usually this wouldn’t be a problem since I didn’t tell you who was assigned number 2. But in this case you have in your envelope a piece of paper marked 2: when you flip to see who you need to buy a present for, you also learn who’ll be buying your present.

We can avoid this (and, as a free bonus, achieve medium mixing) by insisting that you never swap a pair of numbers.

Good traits: It can achieve strong secrecy and medium mixing. In fact we can achieve strong secrecy and strong mixing, if you always to choose a chain when assigning papers to envelopes.
Bad traits: We can’t include any many knowledge-style constraint (see this stack overflow answer where a simple knowledge-style constraint is included, but the fact that secrecy isn’t lost depends on there being lots of symmetry); It’s maybe a little too complicated to persuade your friends to use.

In fact this is only complicated for the two volunteers. So you only need to find one friend willing to carefully follow your instructions (though you also need to persuade the rest to trust your scheme!).

Conclusions

Nowadays probably the best secret santa scheme is a form of external assigner: using a computer programme to do it for you. There are lots of websites designed to do this (just google ‘secret santa websites’). But that ruins the fun! Here are some more challenges you can think about.

Design a scheme which doesn’t require any pens (or other ways of writing things down). Internal/external assigner can do this easily, but suffer the same downfalls as before, while names in envelopes crucially depends on having physical envelopes.
Design an scheme (other than external assigner) which meets secrecy and mixing requirements and works remotely. So if your family want to do a secret santa, and need to assign everyone before your christmas get together, can you do it? Names in envelopes works if you have two people in the same place and are willing to physically post the envelopes. Can you do it with no two people in the same place?
How many times can we expect to have to re-roll before we achieve a permissible assignment (for re-roll names in a hat)? I’ll get you started in the comments.

4 comments:

Kweku Abraham23 January 2020 at 13:32
If you're looking for inspiration for challenges 1 and 2, stackoverflow is a great place to start: eg https://math.stackexchange.com/questions/85470/secret-santa-problem?rq=1, or https://math.stackexchange.com/questions/2896780/secret-santa-algorithm-that-does-not-rely-on-a-trusted-3rd-party
Kweku Abraham23 January 2020 at 13:43
For question 3, if you want to know how to search the answer the keyword is *derangements*: permutations where nothing stays put. Among lots of other things you can find on google there's a numberphile on them https://www.youtube.com/watch?v=pbXg5EI5t4c (gives the answer but not the derivation, but has a link to a follow up one with a derivation). Here's some more prompting from me.

The number of times we have to re-roll is the reciprocal of the probability we get an assignment that works: if we want to roll an even number on a dice, there’s a 1/2 chance with every roll, so on average it will take two rolls; if we want to roll a 4 or less there’s a 2/3 chance each roll, so on average it takes 3/2 rolls. This probability obviously depends on the number of people, so it helps to move to thinking about numbers rather than people so that we can call the number of participants n and work out what happens for each value of n.

What does a secret santa assignment translate to? We give each person a number from 1 to n, and tell them the number of the person they have to buy a present for. No-one receives two presents. That means we get a permutation: a reordering of 1 up to n, where the ordering 5,1,3,2,4 (for example) would mean person 1 buys a present for person 5 (because 5 appears in the first place in the reordering), person 2 for person 1, 3 for themselves (uh-oh), 4 for 2 and 5 for 1.

Provided the pieces of paper we use are all the same, the first person is equally likely to choose any other, then the second is equally likely to choose any one of the remaining people, and so on. Translated, this means each permutation is equally likely.

What does “no-one has their own name” mean? It means in our permutation, no number appears in the corresponding slot: above, 3 appeared in the third slot, which was a problem. As mentioned, such a permutation is called derangement (in contrast to an arrangement I suppose). So, in more formal maths speak, the question we’re left with is

how likely is a randomly chosen permutation to be a derangement?

The answer can obviously be found on wikipedia, or the numberphile or linked, or many other places. Perhaps I’ll write another post about it later.
Harry Jon28 January 2020 at 09:47
Okay Kweku, I claim to have a solution for the second challenge, which at a push you might also consider as a solution to the first. I assume that this group of people all have each other’s mobile number, being a group of good friends and all. I shall call these the “original” phone numbers.
1. Each player orders a new SIM card, to be delivered to their address; a service with many providers will do for free
2. Each player sends a blank text from their new number to everyone else’s original phone number
3. Each player now has all the new phone numbers, which they put in ascending order
4. They find the number after theirs in the list, and send a text to that new number containing their name and a list of gift preferences. Naturally, the player at the bottom of the list wraps round to the top
5. Each player receives a name by text, and buys that person a gift. Adhering to the gift suggestions, if they wish

Kweku's blog

Thursday, 23 January 2020