Finding Fair and Efficient Allocations When Valuations Don’t Add Up

(Joint work with Nawal Benabbou, Ayumi Igarashi, and Yair Zick)

Finding a good way of distributing a collection of goods/resources among multiple interested parties (also called agents) with subjective valuations for those goods/resources has always been an important question; this question has received considerable attention from the computer science community in recent years. What counts as good is a subjective notion but, broadly speaking, a good allocation is one that strikes a balance between efficiency — which relates to the overall utilization/wastage of the goods— and fairness which captures how each recipient views her allotted share in relation to those of others.

The problem of achieving a fair and efficient allocation becomes especially challenging when the goods under consideration are indivisible, e.g. artwork and antiques in an inheritance situation, seats in courses to which students are to be assigned, etc. A rich body of research has investigated the compatibility (and computational tractability) of carefully defined fairness and efficiency criteria in the allocation of indivisible goods. However, most of this work assumes that agents have additive valuations over subsets of goods (also called bundles). Additivity implies that an agent’s marginal gain (i.e. increase in valuation) from adding an item to her current bundle is a constant independent of that bundle. This can be an untenable assumption in many situations such as when an agent has budget or capacity constraints (e.g. in a course assignment problem, a student may be able to take at most one of two courses she is interested in because of schedule conflicts so that the value of being offered both courses is the same as that for each course individually; some goods may be substitutes for/copies of each other, an agent needing only a limited number of them, etc.).

In this paper, we consider agents whose valuations — denoted by vᵢ(S) for agent i and bundle S—are governed by a particular class of non-additive functions: monotone submodular functions with binary marginal gains. Monotonicity signifies that adding a good to a bundle can never diminish its value; submodularity means that the marginal gain from adding a good to a bundle is never lower than that from adding the same good to a bigger bundle; and marginal gains are called binary if adding a good to a bundle either keeps its value unchanged or increases the value exactly by one unit. This valuation class, which we call (0,1)-SUB, can capture many real-world scenarios including those where agents have underlying dichotomous preferences (i.e. each agent either approves or does not approve an item and does not value the items she approves differently) along with constraints of the type described in the previous paragraph.

Let us now formalize our fairness and efficiency desiderata. We say that an agent i envies another agent j if i values j’s allocated bundle more than her own bundle, i.e. vᵢ(Aᵢ) < vᵢ(Aⱼ), where Aᵣ denotes the bundle received by agent r under an allocation A. Since an efficient allocation where no agent envies another may not exist for indivisible goods (which can be demonstrated by a simple example with just two agents and a single item that both value positively), we adopt a well-known and widely-used approximation to envy-freeness as our fairness criterion. We call an allocation A envy-free up to one item — EF1 for short — if the following condition holds: for every pair of agents i and j such that i envies j under allocation A, the envy can be eliminated by removing one item in j’s bundle from i’s consideration, i.e. vᵢ(Aᵢ) ≥ vᵢ(Aⱼ\{o}) for some o in Aⱼ.

The efficiency criterion we are mainly interested in is Pareto optimality — an allocation is said to be Pareto optimal if there is no way to reallocate goods so as to strictly improve the valuation of one agent without strictly diminishing that of at least one other agent. This property is always possessed by an allocation that optimizes a social welfare function (sometimes further refinement of the optimal allocation is necessary for Pareto optimality: see leximin allocation below) — this refers to a family of functions used in economics to measure, very roughly speaking, the overall “goodness” or “desirability” of an allocation (or, more generally, a social state). The most popular ones are: (1) utilitarian social welfare (USW) defined as the sum of all agents’ valuations, (2) Nash social welfare, the product of all agents’ valuations, and (3) egalitarian social welfare which is the minimum valuation across agents under the allocation. An allocation lexicographically maximizing the last welfare function on the list is called leximin — this means that if we start with all allocations that give the highest valuation to the worst-off agent, then choose among them all allocations that give the highest valuation to the second worst-off agent, and keeping going this way as long as we can, we will arrive at a leximin allocation.

The main theme of our results is that the EF1 property can be achieved in conjunction with each of the optimal welfare concepts above, and hence with Pareto optimality, for our valuation class. To achieve this fairness-efficiency combination, we admit allocations that may be incomplete (i.e. there may be items not assigned to any agent) but are clean: a clean allocation is one in which no agent’s bundle contains an item for which she has zero marginal gain; i.e. under a clean allocation A, vᵢ(Aᵢ\{o}) < vᵢ(Aᵢ) for every o in Aᵢ for each i. With all relevant definitions in place, we are ready to summarize our main contributions:

• We prove that an allocation that is EF1 and maximizes the USW always exists for any problem instance with (0,1)-SUB valuations. This is a remarkably positive result since, in general, the EF1 property is not compatible with maximum USW (see Example A.1, where valuations are additive, in the full version of our paper). Moreover, we provide a polynomial-time algorithm that computes such an allocation. The details are, of course, in the paper, but one point worth highlighting here is that the design of the algorithm exploits deep connections of the problem of computing a clean, maximum-USW allocation in our setting to matroid theory (in fact, the (0,1)-SUB valuation class is identical to the class of matroid rank functions) — this may be of independent interest.
• Our second major result does not relate to envy directly but offers interesting connections among all the welfare/efficiency concepts we defined above that hold for our valuation function class: a leximin allocation is equivalent to a maximum Nash welfare allocation as well as to a minimizer of any symmetric, strictly convex function of agents’ valuations among all utilitarian optimal allocations. Examples of such functions include the sum of vᵢ(Aᵢ)² or –log(vᵢ(Aᵢ)) or vᵢ(Aᵢ)log(vᵢ(Aᵢ)) over all agents i.

Equivalences and implications among properties for the (0, 1)-SUB valuation class under clean allocations

• We also prove that a clean, leximin (equivalently, maximum Nash welfare) allocation is EF1. One of the most interesting relatively recent papers on fair division showed that, for additive valuations, an allocation maximizing Nash welfare is also EF1 (and, of course, Pareto optimal as well); to our knowledge, (0, 1)-SUB is the first valuation class not subsumed by additive valuations for which a similar guarantee has been established.

An illustration of the (0,1)-OXS valuation class

One important question for (0,1)-SUB valuations that is still open is that of the computational complexity of the leximin allocation for (0,1)-SUB valuations (the polynomial algorithm mentioned above may not return a leximin allocation: see Example 2.9 in the full version). However, we do have the answer for an important subclass: assignment (or OXS) valuations with binary marginal gains that we call (0,1)-OXS. Under this valuation class, each agent can be viewed as a group with multiple members such that each member has dichotomous preferences over items as defined in the third paragraph above; then vᵢ(S) is defined as the size of the maximum matching of members of group i to their approved items in S (“matching” signifies that each item goes to at most one member and each member gets at most one item). This could be a useful model when one wants to be fair towards several pre-specified groups or communities while respecting the idiosyncratic preferences of the unit-demand individual members of those groups; e.g. in Singapore public housing, applicant families are assigned apartments in public housing estates that they approve but subject to policies that promote diversity with respect to the three recognized ethnic groups in the country. This leads us to our final main result:

• If all agents have (0,1)-OXS valuation functions, the leximin (equivalently, maximum Nash welfare) allocation can be computed in polynomial time. We prove this by constructing a flow network such that the problem under consideration reduces to that of finding an integral balanced flow on this network, which has been recently shown to be polynomial-time solvable.

This was our paper in a nutshell. If this piques your interest, you can read the workshop paper here. Further insights and implications of our results as well as attempts to generalize our results to more general submodular valuation functions can be found in the full version here. Feel free to check out the pre-recorded presentation as well. Thanks for reading the post!