Abstract:
Fair allocation under feasibility constraints is computationally challenging, even for relaxed notions such as envy-freeness up to any item (FEFx). Under generalized assignment constraints and general additive valuations, finding such FEFx allocations is weakly NP-hard. In this thesis, I discuss our investigation of constrained fair division through a structural lens by restricting attention to lexicographic preferences. Unlike general additive valuations, lexicographic preferences is a purely ordinal and highly structured subclass of additive valuations where an agent's evaluation of a bundle is determined entirely by its highest-ranked differing item. By focusing on this restricted domain, we obtain a sharp structural characterization of FEFx and FEF1 allocations in terms of forbidden pairs. This characterization allows us to provide a detailed picture of the landscape: we establish existence and non-existence results for various combinations of fairness and efficiency requirements, identify computational hardness barriers and also develop algorithmic solutions in tractable cases. The results demonstrate how domain restriction and structural analysis allow us to deconstruct worst-case hardness, isolate the true source of combinatorial difficulty, and design algorithms that exploit structure.
