# achieving_envyfreeness_and_equitability_with_monetary_transfers__00070a8b.pdf

Achieving Envy-freeness and Equitability with Monetary Transfers

Haris Aziz UNSW Sydney and Data61 CSIRO haris.aziz@unsw.edu.au

When allocating indivisible resources or tasks, an envy-free allocation or equitable allocation may not exist. We present a sufficient condition and an algorithm to achieve envyfreeness and equitability when monetary transfers are allowed. The approach works for any agent valuation functions as long as they satisfy superadditivity. For the case of additive valuations, we present a characterization of allocations that can simultaneously be made equitable and envy-free via payments. We then present a distributed algorithm to compute an approximately envy-free outcome for any class of valuations.

Introduction A fundamental problem that often arises in several settings is that of allocating items, resources, or tasks in a fair manner. We consider scenarios where agents have valuations over bundles of indivisible items. The goal is to compute allocations of items that are fair. Multi-agent fair allocation has received considerable interest in diverse research communities including computer science, economics, and mathematics. There are several notions of fairness that have been considered in the literature. Among them, two of the strongest ones are envy-freeess (no agent should envy another agent s outcome) and equitability (every agent should get the same utility). When monetary transfers are not allowed, there may not exist any outcome that is envy-free or equitable. We consider outcomes in which each agent gets a bundle of items as well as a payment. Agents have quasi-linear utilities: their utility for an outcome is the sum of the value they have for their bundle of items, and the payment they get. The central question we study is the following one: under what conditions fairness can be achieved via monetary transfers?

Contributions We first present a sufficient condition called transfer-stability for allocations that can lead to equitability and envy-freeness by monetary transfers. In contrast to most of the related results that focus on additive or positive valuations, the statement holds for any superadditive valuations. The result holds if we replace the payment

Copyright 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

balance conditions with the condition that agents get subsidies. For the domain of additive valuations, we provide a complete characterization of allocations that can lead to equitability and envy-freeness by monetary transfers. We also show that if valuations are not superadditive, simultaneously achieving envy-freeness, equitability, and maximum welfare can be impossible. For superadditive valuations, we use our insights to design a polynomial-time distributed algorithm that takes as input a given an allocation and computes an allocation and payment such that the new allocation achieves as much social welfare as the given allocation and the outcome satisfies envy-freeness, equitability, and payment balance. If the valuations need not be superadditive, we propose an alternative distributed algorithm that computes an approximately envyfree outcome. Finally, we discuss issues around computation and bounds for minimal payments to achieve fairness.

Related Work In the fair division literature (see, e.g. Aziz (2020); Bouveret, Chevaleyre, and Lang (2016); Brams and Taylor (1996)), envy-freeness (Foley 1967) and equitability (Dubins and Spanier 1961; Freeman et al. 2019; Robertson and Webb 1997) are well-known fairness properties. When the items are divisible goods, an equitable and envy-free allocation is guaranteed to exist (Alon 1987). On the other hand, when considering indivisible goods, neither of the two properties are guaranteed to be achievable. In this paper, we consider achieving these properties with the help of monetary transfers. Fair allocation with money is well-established, especially in the context of room-rent division. A feature of most of the work in the area is that each agent has demand for exactly one item or room (Aragones 1995; Gal et al. 2017; Klijn 2000; Maskin 1987; Su 1999; Svensson 1983). More general models where envyfreeness is achieved via side-payments have been considered by Haake, Raith, and Su (2002), Meertens, Potters, and Reijnierse (2002), and P apai (2003). Chevaleyre, Endriss, and Maudet (2010, 2017) consider the distributed allocation of goods and focussed on convergence to envy-free and efficient outcomes via trades among agents.

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

More recently, there has been focus on computing envyfree allocations when agents have demands for multiple items and monetary transfers are allowed (Haake, Raith, and Su 2002). In particular, Halpern and Shah (2019) popularized the problem of finding allocations for which minimal subsidies will result in envy-freeness. In followup work, the computational aspects of minimal subsidies has been considered in further depth both from the perspectives of exactly minimal subsidies (Brustle et al. 2020) and approximately minimal subsidies (Caragiannis and Ioannidis 2020). In our model, the valuations can be positive or negative and we also target equitability. In particular, we explore simple distributed algorithms to achieve fairness properties. Even when payments are not available, work on fairness with money can be seen as quantifying the distance from fairness (Hosseini et al. 2020).

Setup We consider the setting in which there is a set N of n agents and a set T of m tasks or items . Each agent i N has a valuation function vi : 2T R. The function vi specifies a value vi(A) for a given bundle A T. The value can be positive or negative. We assume that vi( ) = 0 for all i N. The valuation function of an agent i is supermodular if for each A, B T, vi(A B) vi(A) + vi(B) vi(A B). The valuation function of an agent i is additive if for each A, B T such that A B = , the following holds: vi(A B) = vi(A) + vi(B). The valuation function of an agent i is superadditive if for each A, B T such that A B = , the following holds: vi(A B) vi(A) + vi(B). Note that supermodularity and additivity are stronger conditions than superadditivity. The valuation function of an agent i is submodular if for each A, B T, vi(A B) vi(A) + vi(B) vi(A B). An allocation X = (X1, . . . , Xn) is a partition of the tasks into n bundles where Xi is the bundle allocated to agent i. For an allocation X, the social welfare SW(X) is P i N vi(Xi). An outcome is a pair consisting of the allocation and the payments made by the agents. Formally, an outcome is a pair (X, p) where X = (X1, . . . Xn) is the allocation that specifies bundle Xi T for agent i and p specifies the payment pi made by agent i. If pi is negative, it means agent i gets money. We say that p is balanced if P i N pi = 0. An agent i s utility for a bundle-payment pair (Xj, pj) is ui(Xj, pj) = vi(Xj) pj. In other words, we assume quasi-linear utilities. An outcome (X, p) is envy-free if for all i, j N, it holds that ui(Xi, pi) ui(Xj, pj). An outcome (X, p) is equitable if for all i, j N, ui(Xi, pi) = uj(Xj, pj). An allocation X is envy-freeable if there exists a payment function p such that (X, p) is envy-free. An allocation X is equitable-convertible if there exists a payment function p such that (X, p) is equitable. An allocation X is EFEQ-convertible if there exists a payment function p such that (X, p) is both equitable and envy-free. For any given allocation X, the corresponding envy-graph is a complete directed graph with vertex set N. For any pair of agents i, j N the weight of arc (i, j) is the envy agent i

has for agent j under the allocation X: w(i, j) = vi(Xj) vi(Xi). For any path or cycle C in the graph, the weight of the C is the sum of weights of arcs along C.

Sufficient and Necessary Conditions to Achieve Fairness We note that every allocation is trivially equitableconvertible: each agent can be given money so that their utility is equal to maxi N vi(Xi). On the other hand, not every allocation is envy-freeable or EFEQ-convertible. We say that an allocation is reassignment-stable, if it maximizes the social welfare across all reassignments of its bundles to agents. The following characterization is well-known for envyfreeable allocations. Theorem 1. The following conditions are equivalent for a given allocation: 1. the allocation is envy-freeable 2. the allocation is reassignment-stable 3. for the allocation, there is no positive weight cycle in the corresponding envy-graph The theorem above also holds for any class of valuations. It was stated by Halpern and Shah (2019) for positive additive valuations. The statement for any valuations can be dervived by treating each bundle as a single item. The equivalence between the first two conditions has been proved previously (see e.g., Haake, Raith, and Su (2002) and Mu alem (2009)). Reassignment stability was referred to as local-efficiency by Mu alem (2009). Finally, the theorem also follows from the insights of Klijn (2000). We explore the conditions under which an allocation is EFEQ-convertible. Firstly, we show that even for positive additive utility, reassignment-stability is not sufficient to simultaneously achieve envy-freeness and equitability via payments. Example 1. Even for positive additive valuations and a given envy-freeable allocation, there may not exist any payments to the agents to achieve both envy-freeness and equitability. Consider an instance with the following additive valuations. We consider an allocation X indicated with the squares in which agent 1 gets a and 2 gets b.

1 200 100 2 2 1

The allocation is envy-freeable because it is reassignment-stable. We show that there exist no payments to achieve both envy-freeness and equitability simultaneously. Without loss of generality suppose that agents are paid money. The minimum amount needed to obtain equitability is to pay 199 to agent 2. We can maintain equitability by giving equal amounts of money to both the agents. Note however, that the outcome will continue violating envy-freeness. Agent 1 envies agent 2: ui(X1, p1) = 200 + 0 < 100 + 199 = u1(X2, p2).

The example above shows that reassignment-stability is not sufficient to achieve envy-freeness and equitability. In our quest to achieve both envy-freeness and equitability via monetary transfers, we focus on allocations that are transferstable. We say that an allocation X is transfer-stable if there exist no i, j N such that vi(Xi Xj) > vi(Xi)+vj(Xj). We note that under additive valuations, transfer-stability is stronger than the reassignment-stability property. Lemma 1. Under additive valuations, if an allocation is transfer-stable, then it is reassignment-stable.

Proof. Suppose there exists a reassignment which increases the total welfare. This means that the movement of at least one bundle Xj to some agent i increases the social welfare: vi(Xj) > vj(Xj). Since the valuations are additive, it follows that vi(Xi Xj) = vi(Xi) + vi(Xj) > vi(Xi) + vj(Xj). Hence, the allocation is not transfer-stable.

Since transfer-stability is a stronger property than reassignment-stability under additive valuations, a natural question is whether it can be used to achieve stronger fairness guarantees. We answer the question in the affirmative in the following lemma. The lemma applies to the class of superadditive valuations. Lemma 2. For a transfer-stable allocation X, suppose each agent i makes a payment equal to pi = vi(Xi) SW(X)/n. Then if agent valuations are superadditive, the outcome (X, p) is envy-free and equitable.

Proof. We first want to prove envy-freeness: for all i, j N, it holds that ui(Xi, pi) ui(Xj, pj). By transfer-stability of allocation X, vi(Xi) + vj(Xj) vi(Xi Xj). Since vi is superadditive, it follows that vi(Xi Xj) vi(Xi) + vi(Xj). By combining the two inequalities above, we get

vi(Xi) + vj(Xj) vi(Xi) + vi(Xj) 0 vi(Xj) vj(Xj) vi(Xi) vi(Xi) + SW(X)/n vi(Xj) vj(Xj) + SW(X)/n vi(Xi) (vi(Xi) SW(X)/n) vi(Xj) (vj(Xj) SW(X)/n) vi(Xi) pi vi(Xj) pj ui(Xi, pi) ui(Xj, pj).

The last inequality indicates that agent i is not envious of j and hence (X, p) satisfies envy-freeness. Next, we argue that the outcome (X, p) satisfies equitability. Each agent i N gets utility vi(Xi) pi = vi(Xi) (vi(Xi) SW(X)/n) = SW(X)/n. Since each agent has the same utility SW(X)/n, the outcome satisfies equitability.

The payment function pi = vi(Xi) SW(X)/n used in the lemma is not new. It is referred to as the Knaster payments (Knaster 1946) and is inspired by the idea that each agent should get utility that is at least the proportionality guarantee vi(T)/n that was popularized by Steinhaus (1948).

i Xi Xj vi(Xi) vi(Xj)

j vj(Xi) vj(Xj)

Figure 1: Assumption that X is not transfer-stable in the proof of Lemma 3

Remark 1. Note that the Knaster payments are balanced: P i N pi = 0. In the literature on fair allocation with money, Knaster payments have typically been applied on welfare maximizing allocations. Raith (2000) discusses them prominently in the context of 2 agents and additive valuations. We show that it is sufficient to consider superadditive valuations and transfer-stable allocations for Knaster payments to achieve both equitability and envy-freeness. Our insights also show that any social welfare maximizing allocation is EFEQ-convertible. Corollary 1. For superadditive valuations, a social welfare maximizing allocation is EFEQ-convertible.

Proof. A social welfare maximizing allocation is transferstable. By Lemma 2, it is EFEQ-convertible.

In Lemma 2, we have shown that for additive valuations, transfer-stability is a sufficient condition to simultaneously achieve equitability and envy-freeness via payments. Next, we show that transfer-stability is also a necessary condition. Lemma 3. Under additive valuations, if an allocation is EFEQ-convertible, then it is transfer-stable.

Proof. Suppose an allocation X is not transfer-stable. Then there exist agents i, j N such that

vi(Xj) > vj(Xj)

The inequality is depicted in Figure 1. If X is not envy-freeable, we are done so we assume that X is envy-freeable. Then it must be that

vj(Xi) vi(Xi)

or we can swap the allocations of i and j to get a welfare improvement which means that it is not envy-freeable which implies that it is not EFEQ-convertible. The case is depicted in Figure 2.

By Theorem 1, we know that X does not admit an envycycle. Therefore, either vi(Xi) vi(Xj) or vj(Xj) vj(Xi). We first consider the case vi(Xi) vi(Xj) which is depicted in Figure 3. Since vi(Xj) > vj(Xj), it follows that

vi(Xi) vi(Xj) > vj(Xj).

Since i gets a strictly higher value than j from her allocation, we need to pay money to agent j to ensure equitability. In particular, agent j is paid amount vi(Xi)

i Xi Xj vi(Xi) vi(Xj)

j vj(Xi) vj(Xj)

Figure 2: Assumption that X is envy-freeable but not transfer-stable in the proof of Lemma 3

i Xi Xj vi(Xi) vi(Xj)

j vj(Xi) vj(Xj)

Figure 3: A case in the proof of Lemma 3

vj(Xj). In that case agent i s estimation of agent j s outcome is vi(Xj) + (vi(Xi) vj(Xj)) where we know that vi(Xi) vj(Xj) > 0. Therefore agent i is envious of agent j. Hence X is not EFEQ-convertible. In Figure 3, note that vj(Xj) < vj(Xi). Next we consider the other case vj(Xj) vj(Xi) which is depicted in Figure 4.

We distinguish between two cases (a) vi(Xi) vi(Xj) and (b) vi(Xi) < vi(Xj). We already considered case (a) vi(Xi) vi(Xj) in the previous analysis (Figure 3). Therefore, we now consider case (b) and assume that vi(Xi) < vi(Xj) which is depicted in Figure 5. We distinguish between two further final cases: case vi(Xi) vj(Xj) and the case vi(Xi) < vj(Xj).

1. vi(Xi) vj(Xj) which is depicted in Figure 6. Since vi(Xi) < vi(Xj), agent 1 is envious of agent 2 and needs money to remove the envy. On other hand, we know that vi(Xj) > vj(Xj) so agent 2 needs more money to achieve equitability. Both the properties cannot be met. 2. vi(Xi) < vj(Xj) which is depicted in Figure 7. Since vi(Xi) < vi(Xj), agent 1 is envious of agent 2 and needs money to remove the envy. The exact amount needed to remove envy is vi(Xj) vi(Xi). But then the new utility of agent i is vi(Xj) which we know (see Figure 7) is more than vj(Xj) so equitability is violated.

We have proved that in all the cases, if an allocation is not transfer-stable, then it is not EFEQ-convertible.

The lemma above does not hold for the case of superadditive valuations. Example 2. Consider the following superadditive valuations of two agents for subsets of three tasks.

i Xi Xj vi(Xi) vi(Xj)

j vj(Xi) vj(Xj)

Figure 4: A case in the proof of Lemma 3

i Xi Xj vi(Xi) vi(Xj)

j vj(Xi) vj(Xj)

Figure 5: A case in the proof of Lemma 3

{a} {b} {c} {a, b} {a, c} {b, c} {a, b, c}

1 0 0 0 100 0 0 120 2 0 0 10 0 10 10 10

Consider the allocation X in which X1 = {a, b} and X2 = {c}. The allocation is not transfer-stable as transfering c to 1 increases social welfare. Now suppose agent 2 gets 90 dollars and agent 1 gets or pays no money. In that case both agents get utility 100 so equitability is satisfied. Agent 1 is not envious of agent 2 as she has utility 90 for 2 s outcome. Agent 2 is not envious of agent 1 as she has utility 0 for agent 1 s outcome. Next, we obtain the following result: transfer-stability characterizes EFEQ-convertible allocations. Theorem 2. Under additive valuations, an allocation is EFEQ-convertible if and only if it is transfer-stable.

Proof. The statement follows from Lemma 2 and Lemma 3.

Corollary 2. For additive valuations, there exists a O(n2) algorithm to check whether a given allocation is EFEQconvertible.

Proof. By Theorem 2, we need to check whether the allocation is transfer-stable or not.

Our main result in this section is a sufficient condition for allocations that lead to envy-freeness and equitability. In particular, we show that for superadditive valutions, welfare maximization, envy-freeness, and equitability can be achieved simultaneously (Corollary 1). Next, we show that if valuations are not superadditive, then the welfaremaximizing and hence transfer-stable allocation may not be EFEQ-convertible. Lemma 4. If valuations are not superadditive, then the welfare-maximizing and hence transfer-stable allocation may not be EFEQ-convertible.

i Xi Xj vi(Xi) vi(Xj)

j vj(Xi) vj(Xj)

Figure 6: A case in the proof of Lemma 3

i Xi Xj vi(Xi) vi(Xj)

j vj(Xi) vj(Xj)

Figure 7: A case in the proof of Lemma 3

Proof. Consider the following instance with monotone valuations that are not superadditive.

{a} {b} {a, b}

1 99 10 100 2 1 2 2 3 1 1 1

The only two reassignment-stable (equivalently EFconvertible) allocations are the following ones:

X: X1 = {a}, X2 = {b}, X3 = . Y : Y1 = {a, b}, Y2 = Y3 = .

For allocation X (that is the unique welfare maximizing allocation), in order to ensure equitability, agent 2 needs to get 97 more dollars than agent 1. However, in that case, agent 1 is envious. Therefore the allocation is not EFEQconvertible.

Combining Lemma 4 with Lemma 2 we obtain the following conclusion: superadditive valuations constitute a maximal class of valuations for which a welfare-maximizing allocation is EFEQ-convertible. Lemma 4 raises the question whether an EF and equitable outcome exists for any valuation function. We use our insights from Lemma 2 to prove that an EFEQ-covertible allocation exists for any valuations. Theorem 3. For any valuations of agents, consider the allocation X that gives T to an agent in arg maxi n vi(T). Suppose each agent i makes a payment equal to pi = vi(Xi) SW(X)/n. Then, the outcome (X, p) is envy-free and equitable.

Proof. Suppose agent i = arg maxi n vi(T). Denote by X the allocation in which T is given to i . We claim the outcome (X, p) is equitable and EF. Each agent j N gets utility SW(X)/n so equitability is satisfied. Agent i is not

envious as she has utility SW(X)/n for each agent s outcome. Any agent j N \{i } is not envious of i as her utility for i s outcome is vj(T) n 1

n SW(X). Any agent j N \ {i } is not envious of k N \ {i } because their personal outcomes are the same.

Although we have pointed out that an EF and equitable outcome exists for any valuations, the argument relies on bundling all the tasks together. The drawback of bundling all tasks together is that it may give poor welfare guarantees. Another drawback could be the bundle of all tasks may simply not be feasible because of size constraints on the bundle. In the next section, we explore distributed algorithms that circumvent these drawbacks.

Algorithms to Achieve Fairness In this section, we discuss distributed algorithms to compute fair outcomes. These algorithms do not require centralized operations to converge to desirable outcomes.

An Algorithm for Equitability and Envy-freeness The following lemma shows that a greedy distributed approach can achieve a transfer-stable allocation. Lemma 5. Suppose there exists an oracle that computes the value of an agent for a bundle of tasks in time f(I). Then, for any given allocation Y , a transfer-stable allocation X can be computed in O(n4f(I)) such that SW(X) SW(Y ).

Proof. We initialize allocation X to Y . We take any pair of agents i, j N and check if vi(Xi Xj) > vi(Xi) + vj(Xj). This can be checked in time O(f(I)) for a pair of agents and in O(f(I)n2) for all pairs of agents. If vi(Xi Xj) > vi(Xi)+vj(Xj), we give the allocation of j to agent i which results in agent j getting an empty bundle. With each such operation the total social welfare increases. Hence, the process terminates. Next, we prove that the process terminates in a polynomial number of steps. With each operation, one of the two cases occurs. The first case is that an additional agent j completely loses her bundle. When a bundle goes to another agent who has a nonempty bundle, then the number of agents who have an empty bundle increases. Such operations can happen at most n 1 times. Now suppose that the number of agents who have an empty bundle does not increase. This is only possible in the case that that agent i had an empty allocation who gets the bundle Xj. Since each transfer of a bundle is welfare improving, it cannot happen that a bundle is returned to an agent i. Therefore such operations can happen at most n 1 times until the bundle will not move to any agent with an empty allocation. Hence these operations can happen at most n2 times until no more transfers are possible.

Lemma 2 and Lemma 5 give us a simple method to achieve envy-freeness and equitability. The method is presented as Algorithm 1. We use the algorithm in the proof of Lemma 5 to obtain a transfer-stable allocation. After that we use the payment function specified in Lemma 2 to achieve envy-freeness and equitability. Algorithm 1 leads to the following theorem.

Algorithm 1 Envy-freeness and equitability with payments

Input: Allocation Y and valuations functions vi for each agent i N. Output: Allocation X and payment function p 1: Allocation X Y 2: while there exists some i, j N s.t. vi(Xi Xj) > vi(Xi) + vj(Xj) do 3: Xi Xi Xj; Xj 4: end while 5: For each agent i, pi vi(Xi) SW(X)/n 6: return (X, p) where p is balanced

Theorem 4. Suppose agents have superadditive valuations. Then for a given allocation Y , an allocation X and payment function p can be computed in polynomial time such that 1. the outcome (X, p) is equitable and envy-free, 2. SW(X) SW(Y ), and 3. p is balanced. Note that Theorem 4 helps us achieve envy-freeness and equitability after starting from any given allocation Y . If the initial allocation Y achieves a reasonable approximation of maximum social welfare, then we can achieve fairness properties in conjunction with good approximations of social welfare. Having said that, maximimizing social welfare is notoriously hard for superadditive valuations. Note that our result allows for some payments to be positive, i.e., some agents need to pay money. If we insist on simply using subsidies from a third party to achieve envyfreeness, then we can find the largest payment p i made by an agent i and give each agent an additional amount of p i so that agents only get money and do not need to give money. To be precise, if the balanced payment is p, we can get negative or zero payments p as follows: p i is set to pi max{pj : j N, pj > 0}.

An Algorithm for Envy-freeness Next, we present a distributed algorithm to compute an approximately envy-free outcome. For any ϵ 0, we say that an outcome (X, p) is ϵ-envy-free if for all i, j N, it holds that ui(Xi, pi) ui(Xj, pj) ϵ. The algorithm is a generalization and adaptation of a brilliant algorithm by Bertsekas (1988) for the maximum assignment problem, the problem of computing a maximum weight matching. The algorithm of Bertsekas (1988) assumes that the weights of the edges are positive. Phrased in terms of agents and tasks, the outcome of the algorithm computes an allocation in which each agent gets one task and the goal is to maximize utilitarian social welfare. In order to compute the maximum weight matching, the algorithm takes an auction-based approach in which the prices of tasks are computed and each agent gets a task that gives it almost the maximum possible utility. Although the algorithm of Bertsekas has important ramifications on issues around fair division, it has surprisingly not caught attention in the fair division literature focussed on envy-freeness with money (see e.g., Aragones (1995); Feld-

man, Gravin, and Lucier (2016); Klijn (2000); Su (1999); Meertens, Potters, and Reijnierse (2002)). We present an adaptation (Algorithm 2) of the original algorithm of Bertsekas to compute an envy-free outcome in a more general setting: (1) instead of allocating one task to each agent, we allow any number of tasks and any kind of allocations (2) agents can have any valuation over bundles of tasks (3) the individual tasks do not have posted price and we only consider agents making payments for their bundles. Importantly, the algorithm runs in a distributed manner that does not require centralized operations such as solving a linear program to compute the payments (Halpern and Shah 2019), or doing centralized operations on the assessment matrix (Haake, Raith, and Su 2002) or examining the paths and cycles of the underlying weighted envy-graph (Klijn 2000; Brustle et al. 2020).

Algorithm 2 Generalized Bertsekas Envy Swap (GBES) Algorithm

Input: (N, T, v), ϵ > 0 and a given allocation Y Output: Outcome (X, p) which is ϵ-EF. 1: X Y 2: pi = 0 for all i N (each agent can start its payment being zero) 3: while there exists an agent i N who is not ϵ-envyfree: vi(Xi) pi < maxj N(vi(Xj) pj) ϵ do 4: j arg maxj N(vi(Xj) pj) 5: u1 i (vi(Xj ) pj ); u2 i maxj N\{j }(vi(Xj) pj) 6: B Xj ; Xj Xi; Xi B {Swap allocations of i and j } 7: c pi; pi pj + u1 i u2 i + ϵ 8: pj c 9: end while 10: return X

Theorem 5. Suppose there exists an oracle that computes the value of an agent for a bundle of tasks in time f(I). Algorithm GBES takes an input allocation Y and ϵ > 0 and computes an outcome (X, p) and (X, p) is ϵ-EF. The running time of the algorithm is O(n3f(I) C

ϵ ) where C = maxi,j N vi(Xj) min(0, mini,j N vi(Xj)). If all values are integers and ϵ < 1/n, then GBES returns an ϵ-EF outcome (X, p) where the returned allocation X is reassignment-stable and SW(X) SW(Y ).

Proof. If an agent i gets a bundle B and makes payment pi, we will view pi as the payment made to get B. In the algorithm, if a bundle B = Xj is the cause of the ϵ-envy and hence a swap, we will refer to the bundle B as a targetted bundle. At the start of the while loop, ϵ-envy is checked which takes time O(n2f(I)). We note that once a bundle B is targeted and given from one agent j to some other agent i, then such a bundle remains in the hands of some agent who is ϵ-EF. If each swap involves a targetted new bundle, then we will reach a state in n swaps such that each agent is now ϵ-EF.

Another case is that the same bundles keep changing without a new bundle being targetted for a swap by an agent. Note however after at most |C|/ϵ targetted swaps of any given bundle B, each agent will be at least as interested in a bundle that has not yet been targetted (and hence for which the price is zero). Hence after at most n|C|/ϵ swaps, a new bundle is targetted. We have shown that the algorithm converges to an allocation in at most n + n|C|/ϵ swaps. We now argue that each agent is ϵ-EF. This follows from the fact that the algorithm only terminates once the while loop terminates which only terminates once all the agents are ϵ-EF. Finally, the algorithm works in the same way as the one by Bertsekas (1988), if we view each bundle as one meta-item and we scale up the valuations by adding a large enough constant to each value (to make valuations positive). For his setting, Bertsekas (1988) proved that the total welfare of the new allocation is at most nϵ less than the maximum welfare among all reassignments of the same bundles. If the valuations are integers and ϵ < 1/n, then the returned allocation X is reassignment stable and hence SW(X) SW(Y ).

The payment computed in Algorithm 2 may not be balanced. However we can modify the payments p to balanced payments q as follows: qi = pi 1

n P j N pi. Note that uniform change in the payments of agents does not affect the envy-freeness of the outcome. The algorithm starts off with an initial allocation Y . We can make sure Y satisfies welfare guarantees especially when the valuation functions have additional structure. For example, under submodular valuations, a greedy algorithm can be used to obtain a 2-approximation of maximum welfare (Lehmann, Lehmann, and Nisan 2006). We can combine the result with our insights to derive the following statement. Theorem 6. If agents have integral submodular valuations, there exists a pseudo polynomial-time algorithm to compute an ϵ-envy-free outcome in which the allocation gives a 2approximation of the maximum welfare.

Discussion In this paper, we focussed on envy-freeness and equitability and presented a characterization of allocations that are EFEQ-convertible. Figure 8 highlights some of the insights from this paper and the paper of Halpern and Shah (2019). When using payments to achieve fairness, one may want to use the minimal exchange of money or subsidy to achieve fairness. The problem has been explored by Halpern and Shah (2019) and Brustle et al. (2020) when the goal is envyfreeness. Suppose a given allocation X is EFEQ-convertible. Then there is a linear-time algorithm to compute the minimal payments to achieve both envy-freeness and equitability. For EFEQ-convertible allocations, it is sufficient to focus on achieving equitability. Any additional (uniform) payment for all agents does not affect envy-freeness. Therefore, we can give agents sufficient money to ensure that each agent has utility equal to maxi N vi(Xi). Next, we consider the

EFEQ-convertible

envy-freeable

transfer-stable

reassignment-stable

equitable-convertible

no restriction

Figure 8: Properties of allocations under additive valuations

problem in which we can choose a suitable allocation so as to require minimal payments to acheive fairness. We can derive the following statement. Computing the minimum payments to simultaneously achieve envy-freeness and equitability is strongly NP-hard. Unless P = NP, there exists no deterministic polynomial-time algorithm that approximates within any given positive factor the minimum payments to simultaneously achieve envy-freeness and equitability. The proof follows from the fact that checking whether there exists an envy-free allocation is NP-complete if the agents have identical valuations. In this paper, we focussed on two fairness concepts namely envy-freeness and equitability. It will be interesting to explore other desirable fairness properties such as envyfreeness for mixed goods (Bei et al. 2020) and proportionality (see e.g (Chevaleyre, Endriss, and Maudet 2017)). The field of mechanism design and auction design with money is largely focussed on mechanisms that maximize welfare or revenue. A possible research direction is a deeper study of how well fairness can be achieved by such mechanisms and their variants.

Acknowledgements Aziz is supported by the Australian Defence Science and Technology Group (DSTG) under the project Auctioning for distributed multi vehicle planning (MYIP 9953) and by US Dept. of Airforce under the project Efficient and fair decentralized task allocation algorithms for autonomous vehicles (FA2386-20-1-4063). He thanks Ioannis Caragiannis, Alex Lam and Bo Li for helpful comments and pointers. He also thanks the anonymous reviewers at AAAI-2021.

References Alon, N. 1987. Splitting Necklaces. Advances in Mathematics 63(3): 247 253. Aragones, E. 1995. A derivation of the money Rawlsian solution. Social Choice and Welfare 12(3): 267 276. Aziz, H. 2020. Developments in Multi-agent Fair Allocation. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI). Bei, X.; Li, Z.; Liu, J.; Liu, S.; and Lu, X. 2020. Fair Division of Mixed Divisible and Indivisible Goods. In Proceed-

ings of the 34th AAAI Conference on Artificial Intelligence (AAAI), volume 1814 1821. Bertsekas, D. P. 1988. The auction algorithm: a distributed relaxation method for the assignment problem. Annals of Operations Research 14(1): 105 123. Bouveret, S.; Chevaleyre, Y.; and Lang, J. 2016. Fair Allocation of Indivisible Goods. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice, chapter 12, 284 311. Cambridge University Press. Brams, S. J.; and Taylor, A. D. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press. Brustle, J.; Dippel, J.; Narayan, V. V.; Suzuki, M.; and Vetta, A. 2020. One Dollar Each Eliminates Envy. In EC 20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020, 23 39. ACM. Caragiannis, I.; and Ioannidis, S. 2020. Computing envy-freeable allocations with limited subsidies. Co RR abs/2002.02789. URL https://arxiv.org/abs/2002.02789. Chevaleyre, Y.; Endriss, U.; and Maudet, N. 2010. Simple negotiation schemes for agents with simple preferences: sufficiency, necessity and maximality. Auton. Agents Multi Agent Syst. 20(2): 234 259. Chevaleyre, Y.; Endriss, U.; and Maudet, N. 2017. Distributed fair allocation of indivisible goods. Artificial intelligence 242: 1 22. Dubins, L. E.; and Spanier, E. H. 1961. How to cut a cake fairly. American Mathematical Monthly 68(1): 1 17. Feldman, M.; Gravin, N.; and Lucier, B. 2016. Combinatorial Walrasian Equilibrium. SIAM Journal on Computing 45(1): 29 48. Foley, D. 1967. Resource allocation and the public sector. Yale Econ Essays 7: 45 98. Freeman, R.; Sikdar, S.; Vaish, R.; and Xia, L. 2019. Equitable Allocations of Indivisible Goods. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 280 286. Gal, Y.; Mash, M.; Procaccia, A. D.; and Zick, Y. 2017. Which Is the Fairest (Rent Division) of Them All? J. ACM 64(6): 39:1 39:22. Haake, C.-J.; Raith, M. G.; and Su, F. E. 2002. Bidding for envy-freeness: A procedural approach to n-player fairdivision problems. Social Choice and Welfare 19: 723 749. Halpern, D.; and Shah, N. 2019. Fair Division with Subsidy. In Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT), 374 389. Hosseini, H.; Sikdar, S.; Vaish, R.; Wang, H.; and Xia, L. 2020. Fair Division Through Information Withholding. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The

Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, 2014 2021. AAAI Press. Klijn, F. 2000. An algorithm for envy-free allocations in an economy with indivisible objects and money. Social Choice and Welfare 17: 201 215. Knaster, B. 1946. Sur le probleme du partage pragmatique. de H. Steinhaus. Annales de le Societ e Polanaise Mathematique 19: 228 230. Lehmann, B.; Lehmann, D.; and Nisan, N. 2006. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior 55(2): 270 296. Maskin, E. 1987. On the Fair Allocation of Indivisible Goods. In Feiwel, G., ed., Arrow and the Foundations of the Theory of Economic Policy, 341 349. Mac Millan. Meertens, M.; Potters, J. A. M.; and Reijnierse, H. 2002. Envy-free and Pareto efficient allocations in economies with indivisible goods and money. Mathematical Social Sciences 44(3): 223 233. Mu alem, A. 2009. On Multi-dimensional Envy-Free Mechanisms. In Algorithmic Decision Theory, First International Conference, ADT 2009, Venice, Italy, October 20-23, 2009. Proceedings, 120 131. P apai, S. 2003. Groves sealed bid auctions of heterogeneous objects with fair prices. Social Choice and Welfare 20(3): 371 385. Raith, M. G. 2000. Fair-negotiation procedures. Math. Soc. Sci. 39(3): 303 322. Robertson, J. M.; and Webb, W. 1997. Near exact and envyfree cake division. Ars Combinatorica 45: 97 108. Steinhaus, H. 1948. The problem of fair division. Econometrica 16: 101 104. Su, F. E. 1999. Rental Harmony: Sperner s Lemma in Fair Division. American Mathematical Monthly 10: 930 942. Svensson, L.-G. 1983. Large indivisibles: an analysis with respect to price equilibrium and fairness. Econometrica 939 954.