How to plan (and optimize) a Secret Santa

Wed 18 December 2019

Christopher Chianelli

OptaWeb Employee Rostering developer

Many workplaces host a "Secret Santa", where each employee gets assigned a coworker whom they need to buy a present for. This fosters good relations between the employees and brings them closer together. But what about global companies, where coworkers may be many miles apart? Ideally, we want employees who are further apart to give gifts to each other, since they are the ones who probably know the least about each other. Let’s optimize it with OptaPlanner!

The Constraints

One of the most obvious constraints is that everyone should get a gift. Or phrased a little differently: no one should get multiple gifts.

Here is how one would create this constraint in OptaPlanner using the constraint streams API:

private Constraint sameReceiverConflict(ConstraintFactory constraintFactory) {
    return constraintFactory
            .fromUniquePair(SecretSantaAssignment.class,
                    Joiners.equal(SecretSantaAssignment::getReceiver))
            .penalize("Same Receiver", HardMediumSoftBigDecimalScore.ONE_HARD);
}

Next, we need to reward assignments where the gifter and the receiver are farther apart. Here’s how we do it with constraint streams:

private Constraint largerDistanceAward(ConstraintFactory constraintFactory) {
    return constraintFactory
            .from(SecretSantaAssignment.class)
            .rewardConfigurableBigDecimal("secretFactor", "Larger Distance Award",
                              (m) -> BigDecimal.valueOf(Location.calculateDistanceBetween(m.getGifter().getLocation(),
                                                                       m.getReceiver().getLocation())));
}

Let’s try solving with just these two constraints to see what we get:

Alice is assigned to Daniella, Daniella is assigned to Alice… Bob is assigned to Austin, Austin is assigned to Bob… Something about this solution seems odd; it only has assignments where the gifter is the receiver’s recipient!

What happened?

This is not odd at all, but rather a consequence of how we defined our constraints: if Alice is the person furthest from Daniella, then Daniella is most likely the person furthest from Alice. This means our "Larger Distance Award" constraint will strongly favor pairs of employees.

Is this a bad thing? Yes, it is: imagine if Alice got a $100 gift from Daniella, but only got Daniella a $10 gift. Alice will probably feel bad, and Daniella will feel disappointed. If Alice gave the $10 gift to Bob and Bob gave a $30 gift to Daniella, Alice wouldn’t feel bad and Daniella wouldn’t feel cheated.

Let’s add this constraint (using, you guessed it, constraint streams!)

private Constraint giftPair(ConstraintFactory constraintFactory) {
    return constraintFactory
            .fromUniquePair(SecretSantaAssignment.class,
            // Here, we are joining (a,b) where:
            // a.gifter = b.receiver
            // and
            // a.receiver = b.gifter
            // In other words: a's gifter is getting a gift from b's gifter
            // and b's gifter is getting a gift from a's gifter, which mean
            // we have a pair!
                            Joiners.equal(SecretSantaAssignment::getGifter, SecretSantaAssignment::getReceiver),
                            Joiners.equal(SecretSantaAssignment::getReciever, SecretSantaAssignment::getGifter))
            .penalize("Gifter-Receiver Cycle", HardMediumSoftBigDecimalScore.ONE_MEDIUM);
}

This constraint should be a medium constraint - we want to avoid it if possible, but it isn’t as much of a deal breaker as someone not receiving a gift.

Now let’s try solving again after adding the gift pair constraint:

Much better; we end up with two chains: Alice gives to Austin who gives to Bob who gives to Charlie who gives to Alice; and Dina gives to Dennis who gives to Daniella who gives to Julian who gives to Dina.

This is just the beginning of what you can do to optimize Secret Santa using OptaPlanner. For instance, you can do the following:

Allow each person to input a list of people who they do not want to be Secret Santa for, and add a medium constraint that ensures they are not the Secret Santa for anyone in their list (if possible).
Use a secret factor that sightly influences distance so people cannot find out who their Secret Santa is just by running OptaPlanner.
Pin a Secret Santa assignment to force OptaPlanner to use that assignment in its solution.

You can learn more about OptaPlanner by visting the OptaPlanner website and find the full Secret Santa OptaPlanner example on my GitHub.

Comments Permalink

tagged as use case