Dividing up Halloween candy: the strategy to get the best candy for yourself

One of the things I used to enjoy about trick or treating was the surprise factor. Each house offered different candy, resulting in a nice mix.

But the variability lead to some issues too. Many times my brother and I would go to the exact same houses, but we would end up with fairly different candy. When one person scored tastier candy by pure luck, the other was jealous and would get annoyed.

Eventually my brother and I decided to pool our candy together to be more equitable and avoid fights. We then had a rule about finishing the candy: each person was allowed to eat one candy piece per day, of his choice, until the stash finished.

The scenario led to an interesting strategic question: what was the best order to eat the candy, knowing the other person was also thinking strategically? Was it better to pick your favorite candy, or should you instead be more crafty?

This is a question that can be answered using game theory. There is a clever strategy that I will explain below.

A simplified game

To get a grasp on the problem, it can help to consider a smaller, abstract version of the game.

Suppose Alice and Bob want to divvy up 4 candy bars from Halloween. Say the bars are Snickers, Twix, Kit Kat, and Butterfinger. They divide the candy by taking turns picking one bar at a time. Assume Alice goes first because she is the older sibling.

Each person has different preferences over candy, as follows:

Alice likes: Snickers > Twix > Kit Kat > Butterfinger

Bob likes: Twix > Kit Kat > Butterfinger > Snickers

Being close siblings, they are fully knowledgeable about the other person’s preferences.

To make the example concrete, suppose each person gets 4 points/units of enjoyment for getting their favorite candy, 3 points for the second favorite, 2 points for the third favorite, and 1 point for the least favorite.

Which candy bar should Alice pick first to maximize her enjoyment? What’s the general strategy to play the game?

A bit of notation

As usual, a little bit of notation can help us analyze the game.

We know the point preferenes of the two siblings are as follows:

Alice likes: Snickers (4) > Twix (3) > Kit Kat (2) > Butterfinger (1)

Bob likes: Twix (4) > Kit Kat (3)> Butterfinger (2) > Snickers (1)

We can summarize this a bit easier in a table:

The notation that will be useful is to write the candy in terms of ordered pairs:

Snickers (4,1), Twix (3,4), Kit Kat (2,3), and Butterfinger (1,2).

Being greedy might not work

Being a kid, Alice might get greedy and simply go for her favorite bar on the first turn.

But this strategy will not always work, as this game can demonstrate.

If Alice picks Snickers (4,1) on the first turn to get 4 points, then Bob will pick Twix (3,4) in reply. Then Alice will pick Kit Kat (2,3) to score 2 points, and Bob ends up with the Butterfinger (1,2). Using this strategy, Alice ends up with 4 + 2 = 6 points.

Alice got her favorite and third favorite candy which is pretty good. However, if Alice had played smarter, she could have actually ended up with 7 points. How is that possible?

Alice should instead pick Twix (3,4) on her first turn to get 3 points. Because Alice has taken away Bob’s favorite candy, the best thing Bob can do is pick his second favorite candy Kit Kat (2,3). This allows Alice to pick up her favorite candy Snickers (4,1) to get 4 more points, and Bob again ends up with the Butterfinger (1,2). With this strategy, Alice gets her first and second favorite candies, for 3 + 4 = 7 points.

The reason Alice should pick Twix rather than Snickers is the key to the game. Since Bob does not like Snickers at all–it’s his least favorite candy–Alice does not need to pick it right away. She instead picks her second favorite candy Twix on her first turn, and then she can confidently get Snickers on her next turn.

This example illustrates the optimal strategy for the game.

The equilibrium strategy

The strategy in the game is to leave things your opponent does not like, and pick the more contested items first.

More specifically, the strategy is this: you should pick your opponent’s LEAST favorite candy on your LAST turn of the game.

In the example above, Alice could see that Bob’s least favorite candy is Snickers. This is why Alice should wait to pick Snickers and instead pick Twix.

It can be proved, in fact, that both players playing this strategy is a subgame perfect Nash equilibrium.

The gory math details of the proof can be found in the following paper: How to Make the Most of a Shared Meal: Plan the Last Bite First. The paper refers to the generalized problem as an Ethiopian dinner, for that is a situation in which diners eat a meal, morsel by morsel, from a common platter.

The paper is quite interesting and I suggest you read it. Another interesting part of the paper, which I will summarize below, is a geometric way to understand the strategy.

The strategy is referred to as a crossout strategy, and so the geometry is called a crossout board.

Crossout boards

Ethiopian dinners can be mathematically thought of as a set of n ordered pairs. Without loss of generalization, we can write the preferences as:

{(1, b₁), (2, b₂) … (n, b_n)}

The b_i are a permutation of the numbers 1 to n.

A crossout board is an n x n graph of those ordered pairs. The useful part is the grid can be labeled to demonstrate the crossout strategy, and value of the game. Here is how the paper explains the process.

It is helpful to imagine placing the labels on a crossout board one at a time in increasing order. Alice starts at the left and scans rightward, placing the label 1 below her least favorite morsel. Then Bob starts at the bottom and scans upward, placing the label 2 to the left of his least favorite unlabeled morsel. The players alternate in this fashion until all morsels are labeled. Note that the labels on each axis appear in increasing order moving away from the origin.

For the Halloween candy game, we had the ordered pairs: {Snickers (4,1), Twix (3,4), Kit Kat (2,3), and Butterfinger (1,2)}

Here is the crossout board for that game:

Just to reiterate, this is how the crossout board was labeled. Alice first scans from the origin and marks a 1 under her least favorite candy, Butterfinger. Bob then scans and marks a 2 for his least favorite candy of Snickers. Alice then moves one column to the right and marks Kit Kat with the number 3.

Now it is time to mark Bob’s next spot. The next rows up are Butterfinger and Kit Kat, but Alice has already marked those spots. So these spaces are left unlabeled with a dash. The next thing Bob marks is the Twix bar with the number 4.

Alice’s markings are done: the Twix and Snickers are left unlabeled for her.

The crossout board procedure says that players end up with the candy corresponding to the unlabeled spots. So Alice ends up with the Snickers and Twix, and Bob ends up with the Kit Kat and Butterfinger. This is precisely the result we found above by trial and error.

Because the unlabeled spots indicate the final allocation, the crossout board allows us to calculate the payoff to each player quickly. Alice has unlabeled marks at grid points 3 + 4 = 7 and Bob has unlabeled marks at 2 + 3 = 5.

To find the order of play, Alice looks for Bob’s least favorite choice (lowest point vertically) on the unlabeled spaces and marks that as her last turn. In this case, we can see that Alice saves Snickers (4,1) for her second turn and then picks Twix (3,4) on her first turn.

Similarly, Bob will save Butterfinger (1,2) for his second turn and pick Kit Kat (2,3) on his first turn.

I find this geometrical approach is a very clever and compact way to solve the problem.

Closing point

Whether you are splitting Halloween candy or sharing a meal, the crossout strategy tells you the best order to move to maximize your enjoyment.

I should mention the strategy is not generalizable to 3 players, as the game is more complicated and you end up with situations where it is advantageous to pick later (sort of like how the weakest player in a truel can have the best survival odds)

Reference:

Lionel Levine, Katherine E. Stange: How to Make the Most of a Shared Meal: Plan the Last Bite First (2011)