Multiple-objective foundations of the assignment problem

We consider assignment problems in which agents have individual preferences over a finite set of objects which are to be assigned to the agents, by some collective procedure, so that each agent receives just one object. Our approach is to examine the multiple-objective foundations of this problem by investigating Pareto and weak Pareto assignments (i.e. assignments which are nondominated under natural orderings over assignments induced by individual preferences over goods.) We prove a necessary and sufficient characterization of weak Pareto assignments which is also necessary for Pareto assignments and sufficient under a mild additional restriction on preferences. This characterization is used to underpin an algorithm for generating all Pareto assignments. Our results are also used to show that, for a special class of multiple-objective assignment problems, the set of efficient extreme points of the integer-programming formulation is the same as the set of efficient vertices in the linear-programming relaxation; a result which is not valid for general multiple-objective assignment problems and points the way to computational solution procedures.