How to Divide Indivisible Objects?

Dividing valuable objects must often takes place without cash changing hands: think of family heirlooms among siblings, shifts among interchangeable workers, seats in overbooked classes to students, or computing resources in peer-to-peer platforms. The challenge is to find a convincingly fair division that exploits efficiently the heterogeneity of individual preferences.

Assuming utilities additive over the objects rules out economies of scale, complementarities, and many other important aspects of preferences. Yet they are essentially the only kind we can elicit in practice. Several websites (Adjusted Winner, SPLIDDIT) apply then the two prominent solutions identified by the microeconomic literature: the Egalitarian Equivalent (EE) solution, and the Competitive Equilibrium with Equal Incomes (CEEI) solution (aka the Nash product maximizer, or the Proportionally fair division). They both require to divide a limited number of objects, which is often feasible by time-sharing or randomization.

We first argue that with three or more participants, CEEI performs better than EE on several fronts. EE ensures equal relative utilities, while CEEI ensures No Envy: the latter is manifest without public posting of all utilities, hence is less vulnerable to strategic misreporting.

The addition of new objects could be bad news to some agents under EE (with perverse incentive consequences), but not under CEEI. Next CEEI is invariant to the partial distribution of shares, a property that is close to characteristic. Finally the CEEI allocation is often integral (does not divide any object) while EE almost always requires to split some objects.

When objects cannot be divided at all, and the CEEI allocation is not integral, we can instead partition the objects to maximize the Nash product. This is still efficient and even non envious “up to one object”. Unfortunately it is hard to compute. Alternatively we can round up the virtual CEEI allocation, which can be done in time polynomial in the number of objects. But we may lose any approximation of No Envy, and the other good features of CEEI as well.