Efficient approximately-fair item allocation
When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as "maximin-share fairness" (MMS)", envy-freeness up to one item" (EF1), "proportionality up to one item" (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately-fair item allocation is to find an  allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then. Setting. There is a finite set of objects, denoted by "M". There are "n" agents. Each agent "i" has a value-function "V", that assigns a value to each subset of objects. The goal is to partition "M" into "n" subsets, "X"...,"X", and give each subset "X" to agent "i", such that the allocation is both Pareto-efficient and approximately-fair. There are various notions of approximate fairness. Efficient approximately-envy -free allocation. An allocation is called envy-free (EF) if for every agent believes that the value of his/her share is at least as high as that of any other agent. It is called envy-free up to one item (EF1) if, for every two agents i and j, if at most one item is removed from the bundle of j, then i does not envy j. Formally: Some early algorithms could find an approximately-fair allocation that satisfies a weak form of efficiency, but not PE. This raised the question of finding an allocation that is both PE  and EF1. Maximum Nash Welfare rule. Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang were the first to prove the existence of a PE+EF1 allocation. They proved that, when all agents have "positive additive utilities", every allocation that maximizes the "product of utilities" (also known as the "Nash welfare") is EF1. Since it is obvious that the maximizing allocation is PE, the existence of PE+EF1 allocation follows. While the max-product allocation has desirable properties, it cannot be computed in polynomial time: finding a max-product allocation is NP-hard and even APX-hard. This led to various works attempting  to approximate the maximum product, with improving approximation factors: However, these approximations do not guarantee EF1. Some more recent algorithms guarantee both approximate max-product and fairness: The max-product solution is particularly appealing when the valuations are binary (the value of each item is either 0 or 1): Non-additive valuations. If the agents' utilities are not additive, the max-product solution is not necessarily EF1; but if the agents' utilities are at least submodular, the max-product solution satisfies a weaker property called "Marginal-Envy-Freeness except-1-item" (MEF1): it means that each agent "i" values his bundle  at least as much as the "marginal utility" of (the bundle of j with the best item removed from it). Formally: Similar approximations have been found for more general utility functions: Mixed valuations. Martin and Walsh show that, with "mixed manna" (- additive valuations that may be both positive and negative), maximizing the product of utilities (or minimizing the product of minus the utilities) does not ensure EF1. They also prove that an EFX3 allocation may not exist even with identical utilities. However, with tertiary utilities, EFX and PO allocations, or EFX3 and PO allocations always exist; and with identical utilities , EFX and PO allocations always exist. For these cases there are polynomial-time algorithms. Increasing price algorithm. Barman, Krishanmurthy and Vaish presented a pseudo-polynomial time algorithm for finding PE+EF1 allocations for positive additive valuations. They proved the following results. Basic concepts. Their algorithm is based on the notion of competitive equilibrium in a Fisher market. It uses the following concepts. Algorithm. Given a parameter "e", the algorithm aims to find an allocation that is both fPO and 3"e"-pEF1. It proceeds in several phases. Phase 1: Construct an initial MBB allocation+price (X, p). Phase 2: Remove price-envy within MBB  hierarchy: Phase 3: Increase the prices. Increase the prices of all objects in the MBB hierarchy by the same multiplicative factor, until one of the following three things happen: Proof of correctness. First, assume that the above algorithm is executed on an instance in which all values are powers of (1+"e"), for some fixed "e">0. Now, assume that we have an instance with general valuations. We run the above algorithm on a "rounded instance", where each valuation is rounded upwards to the nearest power of (1+"e"). Note that for each agent "i" and object "o", the rounded value "V"'("o") is  bounded between "V"("o") and (1+"e")"V"("o"). Generalized Adjusted Winner. Aziz, Caragiannis, Igarashi and Walsh extended the condition of EF1 to "mixed valuations" (objects can have both positive and negative utilities). They presented a generalization of the adjusted winner procedure, for finding a PO+EF1 allocation for two agents in time O("m"). Efficient approximately-proportional allocation. An allocation of objects is proportional (PROP) if every agent values his/her share at least 1/"n" of the value of all items. It is called proportional up to one item (PROP1) if for every agent "i", if at most one item is added to the bundle  of "i", then "i" values the bundle at least 1/"n" of the total. Formally, for all "i" (where "M" is the set of all goods): The PROP1 condition was introduced by Conitzer, Freeman and Shah in the context of fair public decision making. They proved that, in this case, a PE+PROP1 allocation always exists. Since every EF1 allocation is PROP1, a PE+PROP1 allocation exists in indivisible item allocation too; the question is whether such allocations can be found by faster algorithms than the ones for PE+EF1. Barman and Krishnamurthy presented a strongy-polynomial-time algorithm finding a PE+PROP1 allocation for  goods (objects with positive utility). Branzei and Sandomirskiy extended the condition of PROP1 to "chores" (objects with negative utility). Formally, for all "i": They presented an algorithm finding a PE+PROP1 allocation of chores. The algorithm is strongly-polynomial-time if either the number of objects or the number of agents (or both) are fixed. Aziz, Caragiannis, Igarashi and Walsh extended the condition of PROP1 to "mixed valuations" (objects can have both positive and negative utilities). In this setting, an allocation is called PROP1 if, for each agent "i", if we remove one negative item from i's bundle, or add  one positive item to i's bundle, then i's utility is at least 1/"n" of the total. Their Generalized Adjusted Winner algorithm finds a PE+EF1 allocation for two agents; such an allocation is also PROP1. Aziz, Moulin and Sandomirskiy presented a strongly-polynomial-time algorithm for finding an allocation that is fractionally-PE (stronger than PE) and PROP1, with general mixed valuations, even if the number of agents or objects is not fixed, and even if the agents have different entitlements. Efficient approximately-equitable allocation. An allocation of objects is called equitable (EQ) if the subjective value of all  agents is the same. The motivation for studying this notion comes from experiments showing that human subjects prefer equitable allocations to envy-free ones. An allocation is called equitable up to one item (EQ1) if, for every two agents i and j, if at most one item is removed from the bundle of j, then the subjective value of i is at least that of j. Formally, for all "i", "j": A stronger notion is equitable up to any item (EQx): for every two agents i and j, if "any" single item is removed from the bundle of j, then  the subjective value of i is at least that of j: EQx allocations were first studied by Gourves, Monnot and Tlilane, who used a different term: "near jealosy-free". They proved that a partial EQx allocation of always exists, even with the additional requirement that the union of all allocated goods is a basis of a given matroid. They used an algorithm similar to the envy-graph procedure. Suksompong proved that an EQ1 allocation exists even with the additional requirement that all allocations must be contiguous subsets of a line. Freeman, Sidkar, Vaish and Xia proved the following stronger results : Algorithms for a small number of agents. Bredereck, Kaczmarcyk, Knop and Niedermeier study a setting where there are few agents (small "n") and few item-types (small "m"), the utility per item-type is upper-bounded (by "V"), but there can be many items of each type. For this setting, they prove the following meta-theorem (Theorem 2): Given an efficiency criterion E, and a fairness criterion F, if  formula_9 is fixed, then it is possible to decide in polynomial time whether exists an allocation that is both E-efficient and F-fair, as long as E and F satisfy  the following properties: Then, they prove that several common fairness and efficiency criteria satisfy these properties, including: The runtime of their algorithm is polynomial in the input size (in bits) times formula_11, where "d" is the number of variables in the resulting ILP, which is formula_12. They later developed more practical algorithms for some of these problems.