Exploring Relations among Fairness Notions in Discrete Fair Division

Fair allocation of indivisible items among agents is a fundamental and extensively studied problem. However, fairness does not have a single universally accepted definition, leading to a variety of competing fairness notions. Some of these notions are considered stronger or more desirable, but they are also more difficult to guarantee. In this work, we examine 22 different notions of fairness and organize them into a hierarchy. Formally, we say that a fairness notion F1 implies another notion F2 if every F1-fair allocation is also F2-fair. We give a near-complete picture of implications among fairness notions: for almost every pair of notions, we either prove an implication or give a counterexample demonstrating that the implication does not hold. Although some of these results are already known, many are new. We examine multiple settings, including the allocation of goods, chores, and mixed manna. We believe this work clarifies the relative strengths and applicability of these notions, providing a foundation for future research in fair division. Moreover, we developed an inference engine to automate part of our work. It is available as a user-friendly web application and may have broader applications beyond fair division.