Fairness Guarantees in Allocation Problems

Abstract

Fair division problems have been vastly studied in the past 60 years. This line of research was initiated by the work of Steinhaus in 1948 in which the author introduced the cake cutting problem as follows: given a heterogeneous cake and a set of agents with different valuation functions, the goal is to find a fair allocation of the cake to the agents. In order to study this problem, several notions of fairness are proposed, the most famous of which are proportionality and envy-freeness, introduced by Steinhaus in 1948 and Foley in 1967. The fair allocation problems have been studied in both divisible and indivisible settings. For the divisible setting, we explore the "Chore Division Problem". The chore division problem is the problem of fairly dividing an object deemed undesirable among a number of agents. The object is possibly heterogeneous, and hence agents may have different valuations for different parts of the object. Chore division is the dual problem of the celebrated cake cutting problem. We give the first discrete and bounded envy-free chore division protocol for any number of agents. For the indivisible setting, we use the maximin share paradigm introduced by Budish as a measure of fairness. We improve previous results on this measure of fairness in the additive setting and generalize our results for submodular, fractionally subadditive, as well as subadditive settings. We also model the maxmin share fairness paradigm for indivisible goods with different entitlements. For the indivisible setting, we also consider the most studied notion of fairness, envy-freeness. It is known that envy-freeness cannot be always guaranteed in the allocation of indivisible items. We suggest envy-freeness up to a random item (EFR) property which is a relaxation of envy-freeness up to any item (EFX) and give an approximation guarantee. For this notion, we provide a polynomial-time 0.72-approximation allocation algorithm.