  In this paper, we present new results on the fair and efficient allocation of
indivisible goods to agents whose preferences correspond to {\em matroid rank
functions}. This is a versatile valuation class with several desirable
properties (such as monotonicity and submodularity), which naturally lends
itself to a number of real-world domains. We use these properties to our
advantage; first, we show that when agent valuations are matroid rank
functions, a socially optimal (i.e. utilitarian social welfare-maximizing)
allocation that achieves envy-freeness up to one item (EF1) exists and is
computationally tractable. We also prove that the Nash welfare-maximizing and
the leximin allocations both exhibit this fairness/efficiency combination, by
showing that they can be achieved by minimizing any symmetric strictly convex
function over utilitarian optimal outcomes. To the best of our knowledge, this
is the first valuation function class not subsumed by additive valuations for
which it has been established that an allocation maximizing Nash welfare is
EF1. Moreover, for a subclass of these valuation functions based on maximum
(unweighted) bipartite matching, we show that a leximin allocation can be
computed in polynomial time. Additionally, we explore possible extensions of
our results to fairness criteria other than EF1 as well as to generalizations
of the above valuation classes.
