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 2 people, every allocation of the house will be unfair to 1 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 Vi, that assigns a value to each subset of objects. The goal is to partition M into n subsets, X1,...,Xn, and give each subset Xi 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 1 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.
The round-robin procedure returns a complete EF1 allocation with additive utilities. The envy-graph procedure returns a complete EF1 allocation for arbitrary monotone preference relations. Both are guaranteed to return an allocation with no envy-cycles. However, the allocation is not guaranteed to be Pareto-efficient. The Approximate-CEEI mechanism returns a partial EF1 allocation for arbitrary preference relations. It is PE w.r.t. the allocated objects, but not PE w.r.t. all objects (since some objects may remain unallocated). 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:
Cole and Gkatzelis presented a 2.89-factor approximation. Anari, Gharan, Saberi and Singh presented an e-factor approximation. Cole, Devanur, Gkatelis, Jain, Mai, Vazirani and Yazdanbod presented a 2-factor approximation. However, these approximations do not guarantee EF1. Some more recent algorithms guarantee both approximate max-product and fairness:
Barman, Krishanmurthy and Vaish present an algorithm that guarantees PE, (1+epsilon)-EF1 and a 1.45 approximation to the max product, in pseudopolynomial time (see increasing price algorithm below). Garg and McGlaughlin present an algorithm that guarantees PE, PROP1, and a 2-approximation to the max product, in strongly polynomial time. Caragiannis, Gravin and Huang present an algorithm that guarantees EFX, PROP1, and a 2.9-approximation to the max product, by discarding some goods (they also show existence of a 2-approximate allocation).
The max-product solution is particularly appealing when the valuations are binary (the value of each item is either 0 or 1):
Amanatidis, Birmpas, Filos-Ratsikas, Hollender and Voudouris prove that with binary valuations the max-product solution is not only EF1 but also EFX (envy-free up to any good). This holds whenever the value of each item can take one of two values - not necessarily 0 or 1. With general additive valuations, max-product does not imply EFX but implies a natural generalization of it. Halpern, Procaccia, Psomas and Shah prove that with binary valuations the max-product rule with lexicographically tie-breaking can be computed in polynomial time, and it is also group-strategyproof.
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:
Bei, Garg, Hoefer and Mehlhorn and Anari, Mai, Gharan and Vazirani study markets with multiple units of each item-kind, where the valuations are piecewise-linear concave. This means that the utility of a bundle with different item-kinds is the sum of utilities for each single item-kind (this is the meaning of "separable"), but for each item-kind, the valuation has decreasing marginal utilities (this is the meaning of "piecewise-linear concave"). They give a 2-approximation to the max-product. Ortega studies a multi-unit market with binary valuations. He proves that the egalitarian rule is Lorenz dominant (a property stronger than leximin-optimality), unique in utilities, and group-strategyproof. Garg, Hoefer and Mehlhorn study budget-additive valuations - a subclass of submodular utilities. They give a (2.404 + ε)-approximation to the max-product in time polynomial in the input size and 1/ε. Benabbou, Chakraborty, Igarashi and Zick study submodular utilities with binary marginal gains (i.e., each item adds either 0 or 1 to the value of each bundle). They prove that, with such valuations, both the max-product and the leximin allocations are EF1 and maximize the utilitarian welfare (sum of utilities). Babaioff, Ezra and Feige also study submodular utilities with binary ("dichotomous") marginal gains. They present a deterministic truthful mechanism that outputs a Lorenz dominant allocation, which is hence EFX and max-product.
Mixed valuations Aziz, Caragiannis, Igarashi and Walsh proposed a general definition of EF1 that applies not only to goods, but also to chores (items with negative value) and to mixed items, which may be goods for some agents and chores for others. Formally:
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.
The algorithm finds a PE+EF1 allocation in time O(poly(m,n,vmax)), where m is the number of objects, n the number of agents, and vmax the largest value of an item (all the valuations are integers). The same algorithm provides a 1.45 approximation to the maximum Nash welfare. The algorithm also proves the existence of an allocation which is both EF1 and fractionally Pareto optimal.
Basic concepts Their algorithm is based on the notion of competitive equilibrium in a Fisher market. It uses the following concepts.
Approximate EF1 allocation: Given a constant e > 0, an allocation is e-EF1 if it satisfies the EF1 condition up to a multiplicative constant of (1+e). Formally:
Price-vector: a vector assigning a price (a real number) to each item. Bang-for-buck ratio: for an agent i and an object o, it is the ratio of the agent's valuation of the item, to the item price: vij / pj. Maximum bang-for-buck (MBB) set: for an agent i, it is the set of objects maximizing his bang-for-buck ratio (given a price-vector p). MBB allocation: an allocation in which each agent receives only objects from his MBB set. In an MBB allocation, each agent maximizes his utility given his budget (but MBB allocation is a stronger condition). The first welfare theorem implies that an MBB allocation is fractionally Pareto optimal. Price-envy-free (pEF) allocation: an allocation X in which, for every two agents i.j, the price of Xi (called the "income" of i) is at least as large as the price Xj. This implies that all incomes are identical. Moreover, an allocation that is both MBB and pEF is envy-free, since each agent maximizes his utility given his income, and all other agents have the same income. Price-envy-free-except-one (pEF1) allocation: an allocation in which, for every two agents i.j, the price p(Xi) is at least as large as the price of Xj without its most expensive item. This does not imply that the incomes are identical. However, an allocation that is both MBB and pEF1 is also EF1. e-pEF1 allocation, for some constant e > 0: an allocation in which, for every two agents i.j, the product (1+e)·p(Xi) is at least as large as p(Xj) without its most expensive item. Note that the e-pEF1 condition is weaker when e is larger. In particular, a pEF1 allocation is e-pEF1 for every e > 0, but the opposite is not true. An allocation that is both MBB and e-pEF1 is also e-EF1.Least-spender: Given an allocation and a price-vector, it is the agent i such that p(Xi) is smallest (ties are broken based on some prespecified ordering of the agents). Note that an allocation is e-pEF1 iff the e-pEF1 condition is satisfied for the least spender (as agent i).MBB Hierarchy of agent i (given allocation X and price-vector p): a tree-structure built in the following way. Put agent i at the root (this is called level 0). Connect to agent i all objects in his MBB set (given the price-vector p). Connect to each object o the agent owning it in X, if it is not yet in the tree (this is called level 1) Connect to each agent at level 1, all objects in his MBB set that are yet in the tree. Continue adding agents and objects alternately in a similar way: for each agent, add his MBB objects; for each item, add its owning agent.Violator (given allocation X and price-vector p): an agent h that violates the pEF1 condition w.r.t. the least-spender i. So the price of Xh, even when the most expensive item is removed from it, is higher than p(Xi). Similarly, e-violator is an agent that violates the e-pEF1 condition w.r.t. the least-spender.Path-violator (given allocation X and price-vector p, and the MBB hierarchy): an agent h that appears on the MBB hierarchy of the least-spender i, and partially violates the pEF1 condition w.r.t. i. In more detail: suppose there is a path, along the edges of the MBB hierarchy, from the least-spender i to object o, and then an edge from object o to agent h (this means that Xh contains o). If p (Xh \ {o}) > p(Xi), then h is a path-violator. Note that every violator is a path-violator, but the opposite is not true. Similarly, If p (Xh \ {o}) > (1+e)·p(Xi), then h is an e-path-violator.
Algorithm Given a parameter e, the algorithm aims to find an allocation that is both fPO and 3e-pEF1. It proceeds in several phases.Phase 1: Construct an initial MBB allocation+price (X, p).