On the complexity of the assignment problem with ordinal data

We consider a variant of the assignment problem where entries of the matrix belong to an ordinal scale L. The objective is to find the set of optimal assignments according to a particular dominance criterion which is relevant in the context of ordinal data. This paper aims is to explore the frontier between easy and hard cases depending on vertical bar L vertical bar, the size of the ordinal scale. We give a polynomial time algorithm that solve the problem for vertical bar L vertical bar = 3. When vertical bar L vertical bar is polynomial in the size of the instance we show that the decision version of the problem is NP-complete.