With that said, practically speaking, it’s not worth it unless all participants are programmers / mathematicians. I tried something even simpler that OP’s suggestion with my friends, and people forgot their passwords, didn’t care about any of “math stuff” because they didn’t understand it and were just trusting me anyway. They wanted something simple to understand that they couldn’t mess up. Basically, they wanted a central authority they trusted (we use drawnames.com now). I totally get their perspective.
If you really want to make a trustless scheme, you’d have to put a lot of effort into making the UX as close to as simple as it is with a central authority. Which is very hard, maybe impossible. And then realize that no one other than the hardcore geeks will understand the benefits anyway. It’s almost like a parable for why we don’t have decentralization generally.
All that said, I think this is a cool project and appreciate the ethos myself.
On a pedantic note…
This simple shuffles the participants and then assigns each person to the person after them in the list. It then uses their public keys to encrypt a message telling them who they should buy a gift for.
This doesn’t pick a random derangement for the set of all possible derangements. You may or may not care, but it makes the guessing easier, especially for smaller groups.
This doesn’t pick a random derangement for the set of all possible derangements. You may or may not care, but it makes the guessing easier, especially for smaller groups.
Can you expand further on that? I don’t understand how there could be a less guessable way of doing this than shuffling them in a big random list and then assigning them next to each other.
OH! I understand: my algorithm means that people can be certain that the person they are buying a gift for will not be buying a gift for them, for example. (I argued with ChatGPT about this a bit and it helped me understand).
OH! I understand: my algorithm means that people can be certain that the person they are buying a gift for will not be buying a gift for them, for example.
Exactly. More generally, it reveals information about the cycle structure. It also rules out, eg with 6 people, 2 cycles of length 3 each, etc.
I argued with ChatGPT about this a bit and it helped me understand
So I think the simplest way to fix that is: shuffle the participants, then loop through them and fir each one select one random recipient and remove them from the set yo be considered. That should ensure everyone has a recipient that isn’t them, while avoiding the statistical problem caused by everyone bring in a perfect loop.
This algorithm won’t always work, since sometimes the first (n-1) people will form a cycle (or set of cycles), forcing the last person to be their own Santa.
You could run the algorithm in a loop until you get valid results, and I believe that would be correct. I think that would be equivalent to running Fisher-Yates in a loop and starting over any time you get a fixed point. Practically speaking, I think this is what I’d do for not-small n. Probabilistically, it will find an answer quickly since the number of derangements equals the nearest integer to n!/e.
For a deterministic algorithm:
If n small (no more than 12, 13 say) you can generate all permutations, filter out any with a fixed point, and then uniformly choose one from the rest.
I’m inclined to go with a pretty simple variant of this then:
Attempt the variant that could result in the last participant gifting themselves - keep on running it up to 1000 times to see if it produces a result that works
After the 1000th time that didn’t work, fall back on the shuffle-and-everyone-gifts-in-a-perfect-circle implementation
Since each attempt has a ~1/e chance of success (better than 1/3), you can safely just let it run until it finds one. Unless you plan on doing this with groups of tens of millions :)
I have some experience with this….
All that said, I think this is a cool project and appreciate the ethos myself.
On a pedantic note…
This doesn’t pick a random derangement for the set of all possible derangements. You may or may not care, but it makes the guessing easier, especially for smaller groups.
Can you expand further on that? I don’t understand how there could be a less guessable way of doing this than shuffling them in a big random list and then assigning them next to each other.
OH! I understand: my algorithm means that people can be certain that the person they are buying a gift for will not be buying a gift for them, for example. (I argued with ChatGPT about this a bit and it helped me understand).
Exactly. More generally, it reveals information about the cycle structure. It also rules out, eg with 6 people, 2 cycles of length 3 each, etc.
Love it!
So I think the simplest way to fix that is: shuffle the participants, then loop through them and fir each one select one random recipient and remove them from the set yo be considered. That should ensure everyone has a recipient that isn’t them, while avoiding the statistical problem caused by everyone bring in a perfect loop.
This algorithm won’t always work, since sometimes the first (n-1) people will form a cycle (or set of cycles), forcing the last person to be their own Santa.
You could run the algorithm in a loop until you get valid results, and I believe that would be correct. I think that would be equivalent to running Fisher-Yates in a loop and starting over any time you get a fixed point. Practically speaking, I think this is what I’d do for not-small n. Probabilistically, it will find an answer quickly since the number of derangements equals the nearest integer to n!/e.
For a deterministic algorithm:
I’m inclined to go with a pretty simple variant of this then:
I think that will be good enough for most groups!
Since each attempt has a ~1/e chance of success (better than 1/3), you can safely just let it run until it finds one. Unless you plan on doing this with groups of tens of millions :)
I made a little secret santa game in python for the family to use. It wasn’t as simple as I’d thought, because of their weird requirements:
The last two cause an imbalance, because Steve can give to Brenda, but Brenda can request she doesn’t buy for Steve.
It’s pretty easy once all the requests have come in to end up with people who won’t get gifts at all!
Ended doing a graph with networkx. It’s only a few lines of code but I learnt a lot about never doing my job outside of my job that hateful day.
This doesn’t even take care of the ‘secret’ part of ‘secret santa’, just the matching.
[Comment removed by author]