Abstract
In this paper, we study the problem of matching
a set of items to a set of agents partitioned into
types so as to balance fairness towards the types
against overall utility/efficiency. We extend multiple desirable properties of indivisible goods allocation to our model and investigate the possibility
and hardness of achieving combinations of these
properties, e.g. we prove that maximizing utilitarian social welfare under constraints of typewise
envy-freeness up to one item (TEF1) is computationally intractable. We also define a new concept of waste for this setting, show experimentally that augmenting an existing algorithm with
a marginal utility maximization heuristic can produce a TEF1 solution with reduced waste, and
also provide a polynomial-time algorithm for computing a non-wasteful TEF1 allocation for binary
agent-item utilities