We study the problem of fair allocation for indivisible goods. We use the maxmin share paradigm introduced by Budish [16] as a measure for fairness. Kurokawa, Procaccia, and Wang [36] were the first to investigate this fundamental problem in the additive setting. They show that a maxmin guarantee (1-MMS allocation) is not always possible even when the number of agents is limited to 3. While the existence of an approximation solution (e.g. a 1/2-MMS allocation) is quite straightforward, improving the guarantee becomes subtler for larger constants. Kurokawa et al. [36] provide a proof for the existence of a 2/3-MMS allocation and leave the question open for better guarantees. Our main contribution is an answer to the above question. We improve the result of Kurokawa et al. to a 3/4 factor in the additive setting. The main idea for our 3/4-MMS allocation method is clustering the agents. To this end, we introduce three notions and techniques, namely reducibility, matching allocation, and cycle-envy-freeness, and prove the approximation guarantee of our algorithm via non-trivial applications of these techniques. Our analysis involves coloring and double counting arguments that might be of independent interest. One major shortcoming of the current studies on fair allocation is the additivity assumption on the valuations. We alleviate this by extending our results to the case of submodular, fractionally subadditive, and subadditive settings. More precisely, we give constant approximation guarantees for submodular and XOS agents, and a logarithmic approximation for the case of subadditive agents. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for additive, submodular, and XOS settings in polynomial time. The reader can find a summary of our results in Table 1. 1 Suppose we have a set of m indivisible items, and wish to distribute them among n agents. Agents have valuations for each set of items that are not necessarily identical. How hard is it to divide the items between the agents to make sure everyone receives a fair share? Fair division problems have been vastly studied in the past 60 years, (see, e.g. [3, 5, 13, 16, 21, 36, 42] ). This line of research was initiated by the work of Steinhaus [42] 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 have been proposed, the most famous of which are proportionality and envy-freeness, introduced by Steinhaus [42] and Foley [28] . A division is called proportional, if the total value of the allocated pieces to each agent is at least 1/n fraction of his total value for the entire cake, where n is the number of agents. In an envy-free division, no agent wishes to exchange his share with another agent, i.e., every agent's valuation for his share is at least as much as his valuation for the other agents' shares. Clearly, proportionality is implied by envy-freeness. Dubins and Spanier [21] propose a simple moving knife procedure that can guarantee a proportional division of the cake. For envy-freeness, Selfridge and Conway design an algorithm that guarantees envy-freeness when the number of agents is limited to 3. Later, Brams and Taylor extend this guarantee to an arbitrary number of agents in the additive setting [14] . However, their method for allocating the cake makes an un-bounded number of cuts. Recently, bounded protocols are proposed for envy-free allocation of cake and chore [6, 19] . The problem becomes even more subtle when we assume the items are indivisible. It is not hard to show that for indivisible items, neither proportionality nor envy-freeness can be guaranteed; for instance, when the number of items is smaller than the number of agents, at least one agent receives no items. From a theoretical standpoint, proportionality and envy-freeness are too strong to be delivered in the case of indivisible goods. Therefore, Budish [16] proposed a newer notion of fairness for indivisible goods, namely the maxmin share, which has attracted a lot of attention in recent years [1-3, 7-9, 13, 23, 36]. Imagine that we ask an agent a i to partition a set M of m items into n bundles and collect the bundle with the smallest value. To maximize his profits, agent a i tries to divide M in a way that maximizes the value of the bundle with the lowest value to him. Based on this, the maxmin share of an agent a i , denoted by MMS i , is the value of the least valuable bundle in agent a i 's allocation; that is, the maximum profit a i can obtain in this procedure. Clearly, MMS i is the most that can be guaranteed to an agent, since if all valuations are the same, at least one agent obtains a valuation of at most MMS i from his allocated set. The question is then, whether there exists an allocation which guarantees MMS i for every agent a i ? Therefore, we call an allocation MMS, if every agent a i receives a collection of items that are together worth at least MMS i to him. Bouveret and Lemaitre [13] showed that for the restricted cases, when the valuations of the items for each agent are either 0 or 1, or when m ≤ n + 3, an MMS allocation is guaranteed to exist. In other words, each a i can be guaranteed to receive a profit of at least MMS i from his allocated items. While the experiments support the existence of an MMS allocation in general [13] , this conjecture was refuted by the pioneering work of Kurokawa, Procaccia, and Wang [36]. Kurokawa et al. [36] provided a surprising counter-example that admits no MMS allocation. They also show that a 2/3-MMS allocation always exists, i.e. there exists an algorithm that allocates the items to the agents in such a way that every agent a i receives a share that is worth at least 2/3MMS i to him. Session 9a: Fair Allocation
The approximation guarantee for MMS was further improved to 3/4 by REF .
Fair Allocation of Indivisible Goods: Improvements and Generalizations
EC '18
Computer Science Mathematics