## Sunday, January 04, 2015

### 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 :-)

Anonymous said...

See http://arxiv.org/abs/1104.0961 for a two-player version of this problem. It lists the multi-player version as an open problem at the end.

Paul Goldberg said...

Thanks for that pointer! I should have read the full version of the Brams et al paper (which is linked-to from the short version I found), which mentions the paper you pointed out. The paper assumes the cardinal utilities are known, while I thinking more in terms of using just the rankings of the items, however the "crossout strategy" seems to apply given just the players' rankings of the items. (My solution, if it works, looks different; maybe I should now check it more carefully.)

Haris said...

Here are more pointers to the literature:

Computing the subgame perfect Nash equilibrium is PSPACE-complete:

http://www.nicta.com.au/pub?id=6902

Assuming the manipulator knows the preferences of the other agents, his optimal manipulation can be computed in polynomial time. The optimal manipulation does not depend on the cardinal utilities:

www.cs.cmu.edu/~arielpro/comsoc-14/papers/BouveretLang2014.pdf

The cross out strategy only works for the case of 2 agents as far as I know but your solution works for any number of agents. Both strategies work for any cardinal utilities consistent with the ordinal preferences. This stems from a general insight of Bouveret and Lang that for computing the best response under sequential allocation, the cardinal utilities do not matter.

Your solution works for the "strict alternating" sequence 123123123. It can be suitably formalized to also work for arbitrary sequences:
Initialize all preferences list to empty. If agent i's turn is next, his most preferred among the remaining objects is appended to his preference list and well as the preference lists of all other agents. The argument for PNE is still the same.

I like your idea to compute a PNE for sequential allocation. It also gives the same allocation as the truthful preference profile.
Up till now I have only seen hardness results such as PSPACE-completeness for computation of pure equilibria for sequential allocation or polynomial-time algorithms for constant number of agents. We used a somewhat similar idea of "threats" for the case of 2 agents and different allocation mechanism for divisible goods:

http://arxiv.org/abs/1401.6523

Paul Goldberg said...

Haris, thanks, very useful!