Fair division problems arise when indivisible resources—such as property, computational resources, or tasks—must be allocated among participants with different preferences. We seek allocations that are both fair and efficient: for example, those satisfying EFX (envy-freeness up to any good), meaning that any envy disappears after removing any single item from another agent’s bundle, and Pareto optimality, meaning that no participant can be made better off without making another worse off.
Researchers at Markov Lab study the existence and computational complexity of such allocations and develop algorithms for constructing them. For the case of two types of items, the existence of an EFX and Pareto-optimal allocation has been established, together with a quasi-linear-time algorithm; for more general settings, methods based on integer programming are being explored. Another research direction focuses on mixed settings in which money is allocated alongside indivisible goods for example, when dividing an inheritance.