Playing Tricks For the Best Treats
Halloween is an inherently vicious holiday. No, not because of the gorey decorations or fake blood that run rampant in stores for a full month before the holiday itself, but rather because of the sugar-deprived children (and children at-heart) stopping at nothing to sate their gastronomic pleasures, even if that means disregarding the consequences for their companions.
In layman’s terms, that means every man for himself when it comes to choosing candy out of a communal stash of candy. So how should one pick their candy? Is there a way to game a supposedly equitable game?
Here’s the game: Alice and Bob are choosing candy out of a pile of 4 candies, say, Snickers, Kit Kat, Reese’s, and Twix. They each take turns, picking one at a time, and each has a preference in candies (for this example, we’ll have Alice like Reese’s > Twix > Kit Kat > Snickers and Bob like Twix > Kit Kat > Snickers > Reese’s). They both gain 4 units of enjoyment from their favorite candy, 3 for their second favorite, 2 for their third, and 1 one their least favorite. The goal here is to maximize their enjoyment, which is represented by the sum of their candies’ ratings.
One may think that the best strategy for the first picker is to go straight for their favorite candy. This makes sense; bigger score components means bigger final sum, right? If we play this through, however, things aren’t quite as they seem. Say Alice picks first, and she goes for her favorite, Reese’s (4). Bob will then choose Twix (4), prompting Alice to pick Kit Kat (2) next and Bob to pick Snickers (2) last. This gives Alice a sum of 4+2=6 units of enjoyment.
6 points is pretty decent, but what if I said that Alice could’ve gotten 7 units of enjoyment by playing a little more cleverly?
Let’s say Alice picks Twix (3) on her first turn. Bob no longer can choose his favorite, so the best he can do is pick Kit Kat (3). Alice can now pick her favorite, Reese’s (4), and Bob is left with a Snickers (1). Alice now has 3+4=7 units of enjoyment!
Why is this? In a situation where there is a competitive market for limited items, the equilibrium strategy is actually to pick not the most desirable items, but the most contested items first – that is, the items with the most demand or the candy with the highest rating sum across the players, not the item with the highest personal value. Because Bob’s least favorite candy is Reese’s, Alice doesn’t have to pick it right away. She can pick her second favorite candy and still rely on getting Reese’s on the second turn. For this game in particular, one should leave the opponent’s last choice for one’s last turn, and this strategy ends up being a Nash Equilibrium (see this paper for more details: http://pi.math.cornell.edu/~levine/EthiopianDinner.pdf). This situation also serves as a modified Matching Market of sorts, but rather than having an equal number of buyers and sellers, we have a few buyers contesting for multiple items. While the logistics of finding an equilibrium is undoubtedly more complicated, the goal of maximizing each buyer’s payoff remains.
Of course, this problem is still quite simplified. If there were more players or unknown values, complicated situations will arise where it might actually be more advantageous to pick later or in a different fashion. It’s in these instances where game theory is even more essential.