  The set of core imputations of the assignment game forms a (non-finite)
distributive lattice. So far, efficient algorithms were known for computing
only its two extreme imputations; however, each of them maximally favors one
side and disfavors the other side of the bipartition, leading to inequitable
profit sharing. Another issue is that a sub-coalition consisting of one player
(or a set of players from the same side of the bipartition) can make zero
profit, therefore a core imputation is not obliged to give them any profit.
Hence core imputations make no fairness guarantee at the level of individual
agents. This raises the question of computing {\em more equitable core
imputations}.
  In this paper, we give combinatorial (i.e., the mechanism does not invoke an
LP-solver) polynomial time mechanisms for computing the leximin and leximax
core imputations for the assignment game. These imputations achieve
``fairness'' in different ways: whereas leximin tries to make poor agents more
rich, leximax tries to make rich agents less rich. In general, the two
imputations are different.
  Our mechanisms were derived by a suitable adaptation of the classical
primal-dual paradigm from combinatorial optimization. The ``engine'' driving
them involves recent insights, obtained via complementarity, into core
imputations \cite{Va.New-characterizations} and the pristine combinatorial
structure of matching. We have identified other natural games which could
benefit from our approach.
