Perfectly Fair Allocations with Indivisibilities

One set of n objects of type I, another set of n objects of type II, and an amount M of money is to be completely allocated among n agents in such a way that each agent gets one object of each type with some amount of money. We propose a new solution concept to this problem called a perfectly fair allocation. It is a refinement of the concept of fair allocation. An appealing and interesting property of this concept is that every perfectly fair allocation is Pareto optimal. It is also shown that a perfectly fair allocation is envy free and gives each agent what he likes best, and that a fair allocation need not be perfectly fair. Furthermore, we give a necessary and sufficient condition for the existence of a perfectly fair allocation. Precisely, we show that there exists a perfectly fair allocation if and only if the valuation matrix is an optimality preserved matrix. Optimality preserved matrices are a class of new and interesting matrices. An extension of the model is also discussed.