How to share a box of chocolates

The following problem came up during the festive season: there was a box of chocolates to be shared out amongst family members, using the standard round-robin mechanism. The question that arises is which one should you choose when it’s your turn? If, say, you love marzipan and everyone else hates it, you should probably not choose marzipan right away; you should leave it until later and go for your second-favourite flavour on the grounds that the second-favourite might otherwise get taken. In an attempt to appear scholarly in considering this important question, I hunted around for literature on sharing indivisible goods. Unfortunately, this work seems to focus on topics like fairness and envy-freeness, rather than providing practical guidance to a player intent on manipulating the system^*. I did find this nice article by Steven Brams, at Plus Magazine, which has lots of articles aimed at getting a general audience interested in mathematical topics. Brams’ article addresses the question of how to allocate as many of the items as possible in an envy-free way, setting aside the other “contested” items, which perhaps then have to be handed out with some randomisation.

As in Brams’ article, I assume that players submit to the mechanism a ranking of the items to be shared, and then player 1 is allocated his highest-ranked item, then player 2 is allocated his highest-ranked item amongst the remaining ones, and so on. But now let’s not worry about envy, which is a potential problem whenever a player’s highest-ranked item gets taken; we just fix the mechanism and study the Nash equilibria. I’m pretty sure there’s a pure-strategy Nash equilibrium in which all players use the same ranking, as follows. Player 1’s favourite item is ranked highest, then player 2’s favourite item (amongst the remaining ones) is ranked second-highest, player 3’s favourite item from amongst the remaining ones is third, and so on. To justify this, note that player 1 should want to collect his favourite item right away, since it will certainly go if he takes some other one. The other players should be OK with ranking player 1’s favourite item highest, simply because that item will be taken by player 1, so it costs them nothing to rank it highest. And so on for the other items. It may be of some interest to consider alternative equilibria, but this solution has the benefit of being a pure-strategy solution that’s easy to compute. It also establishes a rational basis for demanding the same item that everyone else wants.

^*Lest we forget, this is the standard system for picking competing teams on the school playground, and it is claimed to be, if not exactly envy-free, at least a way of getting teams that are evenly-matched. (And I’d be prepared to bet that most game theorists would lament that they were not the sought-after items back in the day, which may explain the research interest in alternative mechanisms :-)