Improving Nash Social Welfare Approximations

1 Introduction

We study the age old problem of fair allocation of goods among agents with additive valuations. The formal study of fair division of goods dates back to the cake cutting problem introduced by [Steinhaus, 1948]. In the simplest version, two agents must agree on a way to split a heterogeneous cake. The well known cut and choose protocol achieves two standard notions of fairness: envy-freeness where every agent weakly prefers their allocation over any other agents' allocation, and proportionality where every agent receives at least a 1/n share of the goods.

Another fairness criterion, max Nash social welfare (NSW), i.e., geometric mean of the agents' valuations, also yields envy-free and proportional allocations. NSW strikes a balance between the perfectly efficient utilitarian objective, maximizing the sum of agents' valuations, and the undoubtedly fair egalitarian objective, maximizing the minimum valued bundle. Further, an allocation which maximizes NSW

(max NSW) corresponds to a certain equilibrium of a linear Fisher market which defines a fractional allocation and a set of prices. This equilibrium, known as a competitive equilibrium of equal incomes, yields an allocation that is not only envy-free and proportional [Varian, 1976], but also Pareto optimal (PO), a standard notion of economic efficiency. Then, fractional max NSW allocations are both fair and efficient.

When goods are indivisible, no algorithm can ensure either envy-freeness or proportionality, e.g., consider allocating a single good between two agents. This motivates the need for alternate concepts of fairness. One choice is to provide additive approximations. In an envy-free up to one good (EF-1) allocation each agent weakly prefers her bundle after removing some good from another agent's bundle. Similarly, an allocation is proportional up to one good (Prop-1), if each agent values her bundle at least a 1/n share of the goods after adding some good not allocated to her. A maximin share (MMS) offers an intriguing alternative relaxation to proportionality. The idea is a natural generalization of the cut and choose protocol from the cake cutting problem. Suppose we allow one agent to choose a partition of the goods into n bundles (one for each agent), with the caveat that the other agents get to choose a bundle before her. In the worst case, she receives her least preferred bundle. Clearly, the agent must select a partition that maximizes the value of her least preferred bundle. We call the value of this bundle the agent's maximin share (MMS). In an α MMS allocation, α ∈ [0, 1], each agent receives a bundle she values at least α MMS.

NSW also serves as a major focal point in fair division of indivisible goods. Caragiannis et al. [2016] present a compelling argument in favor of the 'unreasonable' fairness of max NSW allocations. Analogous to the case of divisible goods, an integral max NSW allocation is EF-1 (and therefore Prop-1 [Conitzer et al., 2017]), Ω(n-1/2 ) MMS, and PO.

1.1 Our Contribution

As a testament to its inherent fairness, NSW has been rediscovered in multiple contexts and employed in wide variety of applications to ensure fair outcomes. Much of its 'unreasonable' fairness stems from the fact a max NSW allocation also meets multiple, sometimes conflicting, fairness notions simultaneously, all while still satisfying the standard economic notion of efficiency, Pareto optimality.

However, finding an integral max NSW allocation is APXhard [Lee, 2017]. Moreover, existing approximations only target the NSW objective, falling short of the array of fairness properties found in a true max NSW allocation. Thus, current literature leaves a clear gap between all of the strong fairness guarantees offered by a max NSW allocation and its approximations. This begs the question: Does an approximation exist that more closely resembles all the remarkable properties of a true max NSW allocation? In this paper, we definitively answer yes. Specifically, we provide an algorithm which yields a 2 max NSW, Prop-1, 1/(2n) MMS, and PO allocation. We also note that none of the previous algorithms achieves these bounds, and we provide counterexamples in Section 5.

Our techniques rely on a market interpretation of fractional max NSW allocations. First, we present novel bounds on any agent's Prop and MMS guarantees in terms of market prices. Then, we design a new scheme to round a market equilibrium into an integral allocation in a way that provides most fairness properties of an integral max NSW allocation.

1.2 RelatedWork

We focus on three of the most common notions of a fair allocation: NSW, MMS, and Prop-1. 1

NSW. [Cole and Gkatzelis, 2015] gave the first constant factor (2.89) approximation algorithm to the NSW objective. Later, [Cole et al., 2017] refined the analysis of the algorithm, showing it yields a 2 max NSW allocation. More recently, [Barman et al., 2018] designed an FPTAS that yields a 1.45 max NSW, PO, and a (1 + ϵ) EF-1 allocation.

Prop-1. [Conitzer et al., 2017] introduced Prop-1 in the context of fair division of public goods, i.e., where all agents receive the same allocation. This generalizes the private goods case we consider. The authors demonstrate a polynomial time procedure to achieve a Prop-1 allocation, but leave the problem of finding a Prop-1 and PO allocation in polynomial time. The recent work of [Barman and Krishnamurthy, 2019] resolves this issue for private good setting by providing an algorithm that yields a Prop-1 and PO allocation.

MMS. [Budish, 2011] defined maximin share which gives an intuitive local measure of fairness of an allocation. [Bouveret and Lemaˆıtre, 2014] showed that an MMS allocation exists in certain special settings. [Procaccia and Wang, 2014; Kurokawa et al., 2016] obtained the surprising result that MMS allocations might not exist, and showed the existence of a 2/3 MMS allocation. [Amanatidis et al., 2017] obtained a PTAS which finds a (2/3-ϵ) MMS allocation. Later, [Barman and Krishna Murthy, 2017] and [Garg et al., 2019] obtained simple algorithms to find a 2/3 MMS allocation. More recently, [Ghodsi et al., 2018] gave a PTAS to find a (3/4-ϵ) MMS allocation, and [Garg and Taki, 2019] obtained an algorithm to find a state of the art 3/4 MMS allocation.

We note that none of the above algorithms yields a constant factor approximation to max NSW, Prop-1, 1/(2n) MMS, and PO allocation simultaneously in poly-time.

1 [Amanatidis et al., 2018] survey the current landscape of fair division and the relationship between various fairness concepts.

2 Preliminaries

We consider the fair allocation of a set M of m indivisible goods among a set N of n agents. A fractional allocation x = (xi)i∈N is an assignment of goods to agents. Agent i's bundle is xi = (xij)j∈M where xij ∈ [0, 1] is the fraction of good j allocated to i. An allocation is integral, corresponding to the case of indivisible goods, if xij ∈ {0, 1}, ∀i, j. We use the notation A = (Ai)i∈N to denote integral allocations to avoid confusion between fractional and integral allocations. That is, Ai = {j ∈ M : xij = 1}. Let X = {x : ∑i∈N xij ≤ 1, ∀j ∈ M} be the set of feasible fractional allocations, and A be the set of feasible integral allocations.

Let vij denote agent i's valuation of good j, and for a bundle xi, i's valuation is vi(xi) = ∑j∈M vijxij . When x is an integral allocation, we overload the definition of vi as follows. For any subset of goods S ⊆ M, define vi(S) = ∑j∈S vij .

NSW of an allocation is defined as

A max NSW allocation maximizes NSW over all feasible allocations, i.e., x∗ ∈ argmaxx∈X NSW(x). An allocation x is an α max NSW allocation if αNSW(x) ≥ NSW(x∗ ) for some α ≥ 1.

MMS of agent i ∈ N is defined as

A maximin share allocation A satisfies vi(Ai) ≥ MMSi, ∀i ∈ N. For any α ∈ (0, 1), an α MMS allocation gives each agent a bundle with value vi(Ai) ≥ αMMSi.

Prop-1 Proportionality (Prop) requires that each agent receive a bundle they value as at least as much as an equal share of the goods, i.e., vi(Ai) ≥ 1n vi(M), ∀i. AProp-1 allocation is proportional after adding a good not allocated to the agent.

PO An allocation x′ Pareto dominates another allocation x if vi(x′i ) ≥ vi(xi), ∀i ∈ N, and vk(x′k ) > vk(xk) for some agent k, i.e., if at least one agent's utility improves without sacrificing the utility of any other agent. An allocation x is PO if no allocation x′ dominates x.

3 Linear Fisher Markets

Our algorithm relies on rounding a fractional allocation x obtained from market equilibrium. In this section, we summarize the relationship between the fractional NSW, the Eisenberg-Gale (EG) program, and linear Fisher markets. Although the agents in our problem do not spend any money, the fictitious market interpretation provides useful information to aid in rounding the fractional allocation.

Consider maximizing the NSW over fractional allocations, which is equivalent to maximizing the sum of logarithms of the agent valuations. This turns out to be a special case of well known Eisenberg-Gale program [1959] where ei = 1, ∀i.

3.1 AMarket Interpretation

The central concept in the design of our algorithm plays off an interpretation of solutions to (EG) as the equilibrium of a linear Fisher market. A Fisher market is the tuple 〈N,M, V, e〉, where N is a set of n agents, M is a set of m goods, V = (vi)i∈N defines the agents valuations, and e = (ei)i∈N gives the agents' budgets. In this setting, each agent seeks to spend their budget on fractions of goods. The utility of agent i for receiving xij amount of each good j is ∑mj=1 vijxij.

A fractional allocation x and a price vector p = (pj)j∈M correspond to primal and dual variables of (EG) respectively. A pair (¯x, ¯ p) which solve (EG) defines an equilibrium.

Definition 1. The pair (¯x, ¯ p) are an equilibrium if: (i) all goods are fully allocated ∑ni=1 ¯xij = 1, ∀j ∈ M, (ii) all agents spend their budget ∑mj=1 ¯xij ¯ pj = ei, ∀i ∈ N, and (iii) all agents only purchase maximum bang per buck (MBB) goods, i.e., if ¯xij > 0, then j ∈ argmaxk∈M vik/¯ pk .

We define the set of MBB goods for agent i as

Spending Graph. Our algorithm exploits some structural properties of equilibria. Namely, an equilibrium (¯x, ¯ p) admits a representation as a forest. First, we define a bipartite graph using the vertices N ∪ M, with the set of agents N on one side and the set of goods M on the other. Using the fractional allocation ¯x, we create the spending graph Q(¯x, ¯ p) by adding a weighted edge (i, j) between agent i and good j with weight ¯xij ¯ pj, if ¯xij > 0. Due to equilibrium condition (iii), j ∈ MBBi for each edge (i, j) of the spending graph.

Lemma 1. [Duan et al., 2016] It is always possible to rearrange the agents' spending to ensure the spending graph is a forest.

Theorem 2. [Mas-Colell et al., 1995] Every Fisher market equilibrium is Pareto optimal.

3.2 Spending Restricted Equilibrium

Equilibria of linear Fisher markets define fractional allocations ¯x. Naturally, one hopes to devise a way to round ¯x into an integral allocation A that, at least approximately, preserves its strong fairness guarantees. However, [Cole and Gkatzelis, 2015] demonstrated that no rounding procedure yields a meaningful approximation to the fractional max NSW, and they gave a clever modification. Specifically, they relax the constraint that all goods need to be fully allocated, and instead require that the total spending on any good does not exceed 1, the budget of an agent. That is, for all goods j ∈M, the total spending on good j is ∑ni=1 ¯xij ¯ pj = min(1, ¯ pj). The modified constraint slightly changes the equilibrium conditions.

Definition 2. A spending restricted (SR) equilibrium is a fractional allocation ¯x and prices ¯ p such that: (i') the total spending on each good j is ∑ni=1 ¯xij ¯ pj = min(1, ¯ pj), and conditions (ii) and (iii) of Definition 1 hold.

The condition (i') of Definition 2 is the defining characteristic of an SR equilibrium, and the only difference between SR and Fisher equilibria. Notably, in an SR equilibrium all agents still purchase only MBB goods, and we can rearrange agents' spending so that the resulting spending graph is a forest. Further, [Cole and Gkatzelis, 2015] provide a strongly polynomial time algorithm to compute an SR equilibrium. Note that we always compute SR equilibrium using agents' budgets ei = 1, ∀i ∈ N.

4 Approximation Algorithm

We present an algorithm that takes as input an SR equilibrium (¯x, ¯ p), and outputs an integral allocation A = (Ai)i∈N that is 2 max NSW, 1/(2n) MMS, Prop-1, and PO.

We start with the important observation that the NSW, MMS, and Prop-1 of an agent are scale invariant, i.e., for any agent i and any c ∈ R+, scaling i's valuations as vij ← cvij, ∀j ∈ M doesn't change the problem. Define i's MBB ratio αi := maxj vij/¯ pj. It is useful to rescale agents' valuations, vij ← vij/αi. Notice that this implies vij = ¯ pj, ∀j ∈ MBBi, and vij < ¯ pj otherwise.

Definition 3. Given an equilibrium price vector ¯ p, we say that an agent's valuations are scaled to prices if: vij = ¯ pj for all j ∈MBBi, and vij < ¯ pj otherwise.

4.1 Basic Bounds

Before discussing specifics of the rounding scheme, we establish upper bounds on the various fairness metrics. These results rely on a few properties of SR equilibria which provides some insight on how to approach rounding the fractional allocation ¯x. To avoid repetition, let (¯x, ¯ p) be an SR equilibrium and assume agents' valuations are scaled to prices.

Lemma 3. [Cole and Gkatzelis, 2015] Let x∗ be an integral max NSW allocation. Then, ∏ni=1 vi(x∗i ) ≤ ∏¯ pj>1 ¯ pj .

Next, we provide upper bounds on any agents' proportionality, Propi = vi(M)/n, and MMSi guarantees in an SR equilibrium. Let H = {¯ pj ∈ M : ¯ pj > 1} be the set of high priced goods, and L = M \H be the set of low priced goods.

Lemma 4. For agent i ∈ N, Propi(M) = vi(M)/n ≤ max(1, maxj∈M vij ).

Proof. Since the budget of each agent is 1, the total spending on all goods in an equilibrium is n. Also, the spending on any good is capped at 1, so that the total spending on high valued goods H is |H|. Therefore, since agents' valuations are scaled to prices

Fix an agent i and let v∗ i = maxj∈M vij, then since agents' valuations are scaled to prices vi(M) = ∑j∈L vij + ∑j∈H vij ≤ n-|H|+v∗ i |H|. By considering the two cases: v∗ i > 1 or v∗ i ≤ 1, the result follows easily.

Lemma 5. For any agent i ∈ N, MMSi ≤ 1.

Proof. Let MMSn i (M) be agent i's MMS given the goods M and n agents, i.e., i must partition the goods of M into n bundles in a way that maximizes the minimum valued bundle. We first show that for any agent i, if we remove any other agent l and any good j, then MMSn-1 i (M \ j) ≥ MMSn i (M).

Let B = (Bi)i∈N be the bundles i selects when calculating her MMSn i (M), i.e., vi(Bk) ≥ MMSn i (M), ∀Bk ∈ B. Wlog, assume Bn contains j. Suppose we redistribute the goods of Bn \ j arbitrarily to the other bundles of B to create a partition of M \j into n-1 bundles B′ = (B′1 , . . . , B′n-1 ). Then, vi(B′k ) ≥ vi(Bk) ≥ MMSn i (M), ∀k ≤ n-1.

Clearly, the above argument generalizes to the case of removing k agents and k goods, i.e., MMSn-k i (M \ {j1, . . . , jk}) ≥ MMSn i (M), for any k < n and {jl}kl=1 ⊆ M. Applying this to the set of high valued goods H yields MMSn i (M) ≤ MMSn-|H| i (M \ H) = MMSn-|H| i (L). Further, MMSn-|H| i (L) ≤ vi(L)/(n - |H|). Then, using (2), MMSn i (M) ≤ vi(L) n-|H| ≤ 1 n-|H| ∑j∈L pj ≤ 1.

4.2 Rounding Algorithm

We explain the steps of our algorithm below and provide a formal description in Algorithm 1, which we refer to as ALG. Let (¯x, ¯ p) be an SR equilibrium. We assume agents' valuations are scaled for the prices ¯ p, and that the spending graph is a forest, by Lemma 1. Let T denote the forest in the spending graph. In a tree t ∈ T, let Mt and kt be the set of goods and the number of agents respectively. We note that the initial steps are similar to ones in [Cole and Gkatzelis, 2015].

In Step 0, for each tree t ∈ T , we pick an arbitrary agent to serve as the root, which we refer to as the root agent. Notice that this gives the levels of each tree a particular structure. All vertices at depth 1 are goods that the root agent spends on in the fractional allocation ¯x, vertices at depth 2 correspond to agents purchasing some fraction of the goods at depth 1, and so on. Since the tree t is part of the spending graph, all edges connecting an agent i to goods j ∈ Mt are in fact MMBi.

Observe that, if good j ∈ Mt is a leaf node with parent agent i, then i is the only agent buying j in ¯x. Hence, we assign every leaf good to its parent agent in Step 1.

Step 2 assigns all goods j ∈ Mt such that ¯ pj < 1/2 to their parent agent i. For any child agent k of good j, we make k the root agent of the new tree formed by cutting the edge between k and j in the spending graph, i.e., k becomes the root of the subtree containing all goods and agents below her. Notice that, since agents spend their entire budget of 1 and ¯ pj < 1/2, the newly created root agent k loses no more than half her budget in this step.

In Step 3, for any j ∈ Mt with two or more child agents, we cut the edges of all child agents except the one spending the most on j, i.e., the agent i with the largest ¯xij. Similar to Step 2, any other child agent k of j becomes the root agent of a new tree. Also, notice that the root agent k of the newly formed tree loses no more than half of her budget in this step since the total spending on any good is capped at 1. Steps 2 and 3 endow the remaining trees with a specific structure. Each tree t ∈ T contains kt agents and exactly kt - 1 unassigned goods from Mt. Further, each unassigned good has exactly one parent agent and one child agent. In addition, all unassigned goods are worth a least ¯ pj ≥ 1/2 to both the parent and child agents. We offer a recursive rounding scheme to meet all stated fairness notions in Step 4.

Algorithm 1: Rounding Algorithm

p)

Input : SR equilibrium (¯x, ¯

Output: A 2 max NSW, Prop-1, PO, 1 2n MMS allocation

• 1 Initialize: Ai = ∅ for all i ∈ N.
• 2 Step 0: Select a root agent in each tree.
• 3 Step 1: Assign all leaf goods to their parent agents.
• 4 Step 2: Assign agents all child goods j s.t. ¯ pj < 1/2.
• 5 Step 3: For all goods j s.t. ¯ pj ≥ 1/2, cut edges between j and all child agents except the one spending the most on j, i.e., the largest ¯xij.
• 6 Step 4: For tree t with kt ≥ 2 agents, let Ni be the neighbors of agent i in the tree t (parent and child goods). Sort and relabel agents in decreasing order of current total value, i.e., vi(Ai). Let i∗ = min{i ∈ t : vi(Ai) +maxj∈Ni vij ≥ 1}, and remove i∗ from the tree.
• 7 Step 5: Assign all remaining goods in the tree.

In the recursion, we select the agent receiving the highest value allocation before the assignment of any remaining goods in the tree, i.e., i ∈ argmaxk∈t vk(Ak) (ties are broken arbitrarily). We test if adding either the agent's parent good or any of its child goods satisfy her Prop-1 guarantee. Formally, let Ni = {j ∈ Mt : j is parent or child of i} be the neighbors of i in the tree. Then, we check if vi(Ai)+maxj∈Ni vij ≥ 1. If this condition is satisfied, then we remove i from the tree. Otherwise, we test the same condition for the second highest spending agent in the tree, and so on until we find an agent that values her current allocation enough so that she can meet the Prop-1 guarantee without receiving any item from the matching tree (refer to Lemma 8).

At the start of Step 4, there are matchings that assign kt - 1 agents a good in the matching tree. Removing one agent ensures that a perfect matching between remaining agents and goods exists. In Step 5, we allocate all unassigned goods.

Theorem 6. ALG returns a 2 max NSW, Prop-1, 1/(2n) MMS, PO allocation in strongly polynomial time.

4.3 Proof of Theorem 6

Observe that each step of ALG runs in strongly polynomial time, and therefore so does ALG. In the following lemmas we verify that all fairness concepts are satisfied. Let A = (A1, . . . , An) be the final integral allocation output by ALG.

Lemma 7. A is Pareto optimal.

Proof. We define a modified Fisher market instance (N,M, V, e′ ) using the same set of agents, goods and agent valuations, but with different budgets. For each agent i, we set their new budget as e′i = ∑j∈Ai ¯ pj. By Theorem 2, it is enough to check the allocation A and prices ¯ p satisfy the equilibrium conditions (Definition 1). Obviously, all goods are allocated, and each agent spends their entire budget by construction. Observe that agent i's allocation is a subset of goods she spent on in the SR equilibrium, i.e., i purchases only MMB goods. It follows that A and prices ¯ p are market equilibrium for the Fisher market instance (N,M, V, e′ ).

The following observations play a key role the remaining analysis. First, in the fractional allocation each agent receives a bundle they value at 1. This follows from equilibrium condition (ii) and the fact that valuations are scaled to prices, i.e., vi(¯xi) = ∑j∈M ¯ pj ¯xij = ei = 1. Second, after completing Steps 0-3, all remaining trees t have exactly kt agents and kt - 1 unassigned goods. We call these matching trees. Further, every unassigned good in a matching tree has one parent agent and one child agent. Finally, in each matching tree t ∈ T, there exists at most one good j /∈ Mt such that some agent i was spending on j in ¯x, i.e., ¯xij > 0. To see this, notice that we only cut edges of the spending graph in Steps 2 and 3. If the edge between i and j is cut in either step, then i was a child of j. After cutting the edge, i becomes the root of a new tree. Since edges between root agents and their child goods are never cut, then only the root agent can lose one edge from the original spending graph.

The following lemma lower bounds the value of the bundle any agent receives in a matching tree. This lemma is crucial to proving the various fairness properties of ALG.

Lemma 8. In each matching tree t, the agent i removed in Step 4 of ALG receives a bundle such that vi(Ai) ≥ 1/(2kt).

Proof. Let A′ = (A′1 , . . . ,A′n ) be the agents' allocations at the beginning of Step 4. Also, let Ni be the neighbors of agent i in the matching tree (parent and child goods). Recall agent i is removed from the tree if vi(A′i ) +maxj∈Ni vij ≥ 1.

First, we show that we can always find an agent satisfying this condition. Observe that, at the beginning of Step 4, any leaf agent i retains all edges in the original spending graph. Also, she values her fractional allocation vi(¯xi) = 1, and she has exactly one parent good, say j, in the matching tree. Then, vi(A′i ) = vi(¯xi)-¯xijvij . Since good j is not integrally assigned to i, ¯xij < 1. It follows that vi(A′i )+vij = vi(¯xi)+ (1 - ¯xij)vij > vi(¯xi) = 1.

We show that i∗ removed from the tree in Step 4 receives a bundle such that vi∗(Ai∗) ≥ 1/(2kt). Observe that there is at most one good j /∈ Mt that the root agent was spending on in ¯x, and the root spent no more than ¯xijpj ≤ 1/2. Therefore, the total spending of agents in the tree on the goods of Mt, together with the goods already assigned is at least kt - 1/2, since all agents spend their entire budget in the equilibrium. Also, the agents spend no more than kt -1 on the unassigned goods in the matching tree, since (¯x, ¯ p) is an SR equilibrium. This implies that some agent must receive at least 1/(2kt) before Step 4. Recall that we check the agents in decreasing order of the value of their bundle at the beginning of Step 4. If the first agent is removed, then clearly she receives a bundle worth at least 1/(2kt).

Suppose that the agent receiving the most at the beginning of Step 4, say i, does not satisfy the condition. Then, vi(A′i )+ vij = ∑k∈A′i ¯ pk + ¯ pj < 1, ∀j ∈ Ni, since valuations are scaled to prices. Therefore, if i and any good j ∈ Ni are removed from the tree, then the remaining kt-1 agents spend at least kt-1/2-(∑k∈A′i ¯ pk + ¯ pj ) ≥ kt -3/2 on the goods of Mt \ j, and no more than kt -2 is spent on the other kt -2

unassigned goods of Mt \ j. Therefore, some agent must receive a bundle worth at least 1/[2(kt - 1)]. Noting that all leaf agents satisfy vi(A′i ) +maxj∈Ni vij ≥ 1, we can iterate this argument to ensure the agent removed in Step 4 receives a bundle worth at least 1/(2kt).

Lemma 9. ALG returns a 1/(2n) MMS allocation.

Proof. By Lemma 5, MMSi ≤ 1 for all agents. Observe that if agent i was never part of a matching tree, then she receives a bundle worth at least 1/2. In a matching tree, every agent, except the one removed in Step 4, receives one of the unassigned goods they value vij = ¯ pj ≥ 1/2. Lemma 8 shows that i∗ removed from the tree receives bundle worth at least 1/(2kt). Obviously, the size of any tree kt ≤ n. It follows that all agents receive at least 1/(2n)MMSi.

Lemma 10. ALG returns a Prop-1 allocation.

Proof. Recall that Propi ≤ max(1,maxj∈M vij), by Lemma 4. Therefore, for any i, if maxj∈M vij > 1, then the Prop-1 condition is trivially satisfied. For this reason, assume that maxj∈M vij ≤ 1, ∀i ∈ N.

The agent i∗ removed from a matching tree t during Step 4 clearly satisfies Prop-1. Suppose agent i receives good j in a matching tree, i.e., vij = ¯ pj ≥ 1/2. We consider two cases. If i has two or more child goods, then at least one child good, say k, is not in her integral allocation Ai, and vik = ¯ pk ≥ 1/2. Therefore, vi(Ai) + vik ≥ vij + vik ≥ 1. If i has at most one child good (or is in a tree of size kt = 1), then there is at most one good k in her fractional allocation that is not in her integral allocation, i.e., vi(Ai) + vik ≥ vi(¯xi) = 1.

The next part is an adaptation of the analysis given in [Cole et al., 2017]. Notice that all but one agent in each matching tree receives a good with value ¯ pj ≥ 1/2. The remaining agent, say r, was removed from the tree in Step 4, and she receives at least vr = vr(Ar) ≥ 1/(2kt), by Lemma 8.

Lemma 11. In any matching tree t with kt ≥ 2 agents, the minimum product of agents' valuations is achieved when at least k1 = ⌊(kt - 2vr)/(1 + 2vr)⌋ agents receive a bundle worth at least 1.

Proof. Let A be an allocation with minimum product of the agents' valuations, and let A′ = (A′i )i∈N be the agents' bundles before Step 4. Recall that the agent r removed from the tree satisfies vr(A′r ) + vrj ≥ 1 for some j ∈ Nr, and we check this condition in decreasing order of vi(A′i ). Therefore, for any i such that vi(A′i ) > vr(A′r ), we have vi(Ai) < 1 since i receives a good j ∈ Ni. It follows that for any of the agents receiving a bundle vi(Ai) ≥ 1, the total spending on the goods of Ai is no more than 1 + vr, i.e., ∑j∈Ai ¯ pj ≤ 1 + vr.

The proof follows by contradiction. Let qj ≤ 1 denote the total spending on good j ∈ Mt, and let M ′ t be goods allocated to the k1 agents receiving at least 1 and agent r. Then

Suppose, for contradiction, k1+1 ≤ ⌊(kt-2vr)/(1+2vr)⌋. Then the remaining kt - k1 - 1 agents have value at least (kt - k1)/2. Further, at least two of these agents receive a bundle worth vi(Ai) > 1/2, otherwise the remaining agent receives a bundle worth at least (kt-k1)/2-(kt-k1-2)/2 = 1, contradicting the definition of k1. However, if two agents, say 1 and 2, receive bundles they value v1, v2 ∈ (1/2, 1), then clearly giving agent 1 a bundle worth 1/2 and agent 2 a bundle worth v1 + v2 - 1/2 produces a lower product of the agents' valuations, a contradiction.

Lemma 12. [Cole et al., 2017] For any tree t with kt agents

Proof. This follows from Lemma 11 and the argument of Lemma 26 in [Cole et al., 2017].

Lemma 13. ALG returns a 2 max NSW allocation.

Proof. Using the upper bound on the optimal integral NSW from Lemma 3, we want to show that

From Lemma 12, it follows that

Proof. (Theorem 6) The approximation guarantees follow immediately from Lemmas 7, 9, 10, and 13.

5 Examples

In this section we provide explicit examples to demonstrate that existing approximation algorithms fail to satisfy either: Prop-1, or a constant factor max NSW and MMS allocation.

Example 1. We show that the algorithm of [Barman and Krishnamurthy, 2019], which gives a Prop-1 and PO allocation, does not yield a α max NSW or β MMS allocation for any α, β > 0. The algorithm relies on rounding a Fisher market equilibrium. Consider n identical agents, i.e., vi(·) = vj(·), ∀i, j ∈ N. We let v denote their common valuation function. There are n goods where v(1) = n-1+1/n, and v(j) = 1/n, ∀j ≥ 2. Clearly, the max NSW is positive. Also, MMSi = 1/n for each agent i, since |M| = n.

Consider the fractional allocation x, where x1 = (1/[n(n - 1 + 1/n)], 1, . . . , 1), and xi = (1/[n - 1 + 1/n], 0, · · · , 0), ∀i ≥ 2. In words, agents 2 through n spend their budget on good 1 and receive nothing else, while agent 1 receives a smaller portion of good 1 and all goods 2 through n. Define the prices pj = v(j), i.e., price of every good is equal to the agents' valuation. It is easily verified that equilibrium conditions (Definition 1) hold. Therefore, (x, p) defines an equilibrium. However, regardless of rounding procedure, n - 2 agents receive nothing in the integral allocation.

Example 2. We show that the algorithm of [Barman et al., 2018] may not give a Prop-1 allocation. Recall, their algorithm yields an (1 + ϵ) EF-1 allocation, i.e., (1 + ϵ)vi(Ai) ≥ vi(Aj \ g) for some g ∈ Aj . Fix ϵ > 0, and let k = ⌈2/ϵ⌉.

Consider an instance with two identical agents and |M| = k + 4 goods, where v(j) = 1/k for all j ∈ {1, . . . , k + 3}, and v(k+4) = 1. Let the allocation be A1 = {1, . . . , k+3}, and A2 = {k + 4}. Then (1 + ϵ)v(A2) ≥ 1 + 2/k = (k + 3 - 1)/k = v(A1 \ j) ∀j ∈ A1, so that the allocation is (1 + ϵ) EF-1. However, v(M) = 2 + 3/k. Then, Prop2 = 1 + 3/(2k) > 1 + 1/k = v2(A2) + vij , ∀j ∈ A1. We note that if ϵ is chosen small enough based on instance size, then [Barman et al., 2018] algorithm yields an EF-1, hence Prop-1 allocation. However, the runtime may not be polynomial.

Example 3. We show that [Cole and Gkatzelis, 2015] may fail to yield a Prop-1 allocation. Figure 1 shows the spending graph of an SR equilibrium. Agents are shown as circles, and goods as squares. Directed arrows show the spending of each agent. All agents, except b, share the same valuations, shown below of each good. Agent b values all goods, except 7, the same as other agents. However, b values good 7 at vb7 = 0.5 as shown in parenthesis. Their algorithm starts by selecting a root agent for each tree. If agent a is picked, then goods 1, 2, and 3 are assigned to a, cutting the edge between b and good 3, and making b the root of the tree shown in the dashed box.

First all leaf goods are assigned to their parent agent's, creating a partial allocation A′ . Then the algorithm computes a maximum weight matching to assign the remaining goods in the dashed box. Weights in the matching are set as log(vi(A′i ) + vij) between i and j s.t. ¯xij > 0. It is easily verified that all matchings have maximum weight, therefore b may not be assigned to any additional goods. In this case, b's final allocation is good 4 with value vb(A′b ) = 0.4. We compute P ropb = 11/12 > vb(Ab) + vbj , ∀j ∈ M.

6 Conclusions and FutureWork

We presented a market based approach to approximate max NSW allocations. First, we gave novel bounds on any agent's Prop and MMS guarantees in terms of market prices. Then, we designed a new scheme to round an SR equilibrium into a 2 max NSW, Prop-1, 1/(2n) MMS, and PO allocation. One interesting direction for future work is improving the approximation to meet EF-1 guarantees. Another avenue to pursue is obtaining a constant factor NSW and MMS allocation.

Acknowledgments

Work on this paper supported by NSF CRII Award 1755619.