Abstract:

We consider the problem of fairly allocating a set of indivisible goods to equally entitled agents, with no monetary transfers. A share function maps a pair of agent valuation and number of agents to a non-negative value, with the interpretation that if an allocation fails to give the agent a bundle of value at least equal to her share, this serves as evidence that the allocation is not fair towards the agent. We embark on a systematic study of feasible shares – a share is feasible if we can always give every agent her share. We introduce the notion of a self-maximizing share to capture the incentive for truthful valuation reporting.  We prove the inexistence of an “ultimate feasible share”: one that dominates any other feasible share that is self-maximizing. We then present several feasible shares that are self-maximizing and polynomial-time computable, and approximately dominate all other shares.

Joint with Uri Feige