Fair division studies how to allocate items among agents while satisfying fairness requirements. This work focuses on indivisible items with nonnegative marginal values. For binary submodular valuations, where each marginal value is either zero or one, the Yankee Swap algorithm computes an allocation that simultaneously satisfies envy-freeness up to any good (EFX), maximum utilitarian social welfare (Max-USW), and maximum Nash welfare (MNW) in polynomial time. We introduce Submodular Preferences Over Complements (SPOC), where each agent specifies a matching over the goods and has a binary submodular valuation over these complements. This captures applications such as course allocation, where a student may value two complementary courses only when taken together.
For SPOC valuations, we show that envy-freeness up to one good (EF1) and Pareto optimality (PO) need not coexist, ruling out a general guarantee of EFX and Max-USW. However, we give a polynomial-time algorithm that simultaneously achieves EFX, a (1/3)-approximation to Max-USW, and a (1/(3+1/n))-approximation to the maximin share (MMS), where n is the number of agents. The welfare guarantee is almost to tight: there are instances where no EF1 allocation achieves more than half the optimal utilitarian welfare. We also prove that maximizing utilitarian welfare is APX-hard and provide polynomial-time algorithms for a (1/2)-approximation to Max-USW and later another polytime algorithm that produces an allocation which is ((5,1))-MNW allocation.
