  We analyze the run-time complexity of computing allocations that are both
fair and maximize the utilitarian social welfare, defined as the sum of agents'
utilities. We focus on two tractable fairness concepts: envy-freeness up to one
item (EF1) and proportionality up to one item (PROP1). We consider two
computational problems: (1) Among the utilitarian-maximal allocations, decide
whether there exists one that is also fair; (2) among the fair allocations,
compute one that maximizes the utilitarian welfare. We show that both problems
are strongly NP-hard when the number of agents is variable, and remain NP-hard
for a fixed number of agents greater than two. For the special case of two
agents, we find that problem (1) is polynomial-time solvable, while problem (2)
remains NP-hard. Finally, with a fixed number of agents, we design
pseudopolynomial-time algorithms for both problems. We extend our results to
the stronger fairness notions envy-freeness up to any item (EFx) and
proportionality up to any item (PROPx).
