Christmas protocol

Question

Since holiday season is coming, here is a little practical-purpose combinatorics question.

Lots of group of friends or families practice the random variant of Secret Santa, where each member buys a gift without knowing who will get it, and then gifts are randomly attributed.

In this context, the natural question is: can you devise a protocol that does not use a computer, and is feasible in practice, such that:

• nobody gets its own gift
• nobody learns any information on who bought which gift
• gifts are assignated randomly, i.e. nobody can choose or assign a gift based on the package appearance.
• the protocol is guaranteed to end in finite bounded time, i.e. avoid things like "retry until it works"

I added the last contraint because for instance for 4 people, the probability to get a fixpoint-free permutation is only $3/8$, so it can be painful to repeat until you get one, I count this as non-practical.

Answer 1

Assign a number to each present and put papers with the respective numbers in a bag, make people take out numbers in turn. if someone gets the paper of his own present everyone puts everything back and they start again, the probability they get this at the first try approaches $\frac{1}{e}$ as $n$ approaches infinity.

---

Answer 2

Note (added later): I just discovered that I have essentially reproduced Henning Makholm's solution at the site he linked to in his comment, all the way down to the colors red and green. I'm leaving this answer up for convenience, at least for now. I swear I didn't peek before I posted! End of note.

Here's a protocol for assigning Secret Santas that I think gives no one any information beyond their assigned recipient, and also avoids "do-overs." It definitely produces a random derangement in a single pass, and I think it does so with uniform distribution.

Imagine yourself as a participant. You begin by writing your name on two slips of paper. You put one inside a red envelope and one inside a green envelope. You seal these envelopes (henceforth I'm going to call them the red card and the green card) and put them together in a (somewhat larger) white envelope, which you leave unsealed. All the participants' white envelopes are identical, as are all the red cards and all the green cards.

The group now gathers, collects the white envelopes, shuffles them like a deck of cards until they are thoroughly, randomly mixed, and deals them out so that everyone now holds a white envelope with someone's names inside the cards inside it.

You now prescribe some linear order among the participants, such as alphabetical or sitting around the table with one person at the "head." The first person (let's say Alice) simply hands the card she is holding to the second person (Bob), who swaps the green card from the envelope he's been holding with the green card from the envelope he's been handed. Bob then "shuffles" the two envelopes to "randomize" them and hands them to the third person (Carol), who chooses one of those two envelopes at random and swaps its green card with the green card from the envelope she's been holding. She also "shuffles" the three white envelopes, and hands them to the fourth person (Dan).

And so forth. When it's your turn, for example, you're handed a stack of white envelopes. You pick one at random and swap its green card with the green card from the white envelope you've been holding, add that envelope to the stack, shuffle the stack of white envelopes to randomize, and hand it on.

After the last person (Zeke) gets done with the final shuffle, the white envelopes are now picked up one by one. Each envelope's green card is opened, revealing the name inside, and the envelope's red card (still sealed) is handed to that person. You can think of the Green card as identifying the Giver, and the Red card as identifying the Receiver. Only each giver looks inside his or her red card to see who they are to be the Secret Santa for -- that's what "secret" means!

I think (but see the "Added later" note below!) the various shufflings of the white envelopes is enough to guarantee that the protocol produces a random derangement with uniform probability, which I think guarantees that no one has any information of any sort except who his or her recipient is to be, but I'd like to see a formal proof of this. (I think simple induction should suffice. Note, however, that there is no secrecy possible until you have at least four people: With three people, as soon as you look at your red card and know who your recipient is, you automatically know that your Secret Santa must be the third person.) In particular, I'm not sure it's necessary for everyone to shuffle after they've made a swap, but I suspect it is, that skipping some may perturb the probability distribution on the set of derangements, so that some people might gain some information beyond whose Secret Santa they are.

Added later: As Henning Makholm astutely points out, the extra shuffles are pointless. Moreover, you do not get a uniform distribution on all derangements, just on the ones that are $n$-cycles. The upshot of this is that each person, on opening their red card, can infer one fact for sure: their recipient is not their Secret Santa. That's because the protocol doesn't produce any $2$-cycles.

You could "fix" this by setting two envelopes aside after the initial shuffle, swapping their green cards (thus creating a $2$-cycle), creating an $(n-2)$-cycle with the rest, and then shuffling all the cards together again before distributing them. This way everyone will calculate that their recipient is their Secret Santa with probability $2/n$ instead of $0$. But what you'd really like is for that probability to be $1/(n-1)$. I can't think of any wrinkle that will achieve that.