On Fair Allocations and Indivisibilities

This paper studies the problem of how to distribute a set of indivisible objects with an amount M of money among a number of agents in a fair way. We allow any number of agents and objects. Objects can be desirable or undesirable and the amount of money can be negative as well. In case M is negative, it can be regarded as costs to be shared by the agents. The objects with the money will be completely distributed among the agents in a way that each agent gets a bundle with at most one object if there are more agents than objects, and gets a bundle with at least one object if objects are no less than agents. We prove via an advanced fixed point argument that under rather mild and intuitive conditions the set of envy-free and efficient allocations is nonempty. Furthermore we demonstrate that if the total amount of money varies in an interval [X,Y], then there exists a connected set of fair allocations whose end points are allocations with sums of money equal to X and Y, respectively. Welfare properties are also analyzed when the total amount of money is modeled as a continuous variable. Our proof is based on a substantial generalization of the classic lemma of Knaster, Kuratowski and Mazurkewicz (KKM) in combinatorial topology.