Fair-Share Allocations for Agents with Arbitrary Entitlements

We consider the problem of fair allocation of indivisible goods to $n$ agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin share (MMS) serves as an attractive fairness criterion, where to qualify as fair, an allocation needs to give every agent at least a substantial fraction of her MMS. In this paper we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to unequal entitlements. Our conceptual contribution is the introduction of a new notion of a share, the AnyPrice share (APS), that is appropriate for settings with arbitrary entitlements. Even for the equal entitlements case, this notion is new, and satisfies $APS \ge MMS$, where the inequality is sometimes strict. We present two equivalent definitions for the APS (one as a minimization problem, the other as a maximization problem), and provide comparisons between the APS and previous notions of fairness. Our main result concerns additive valuations and arbitrary entitlements, for which we provide a polynomial-time algorithm that gives every agent at least a $\frac{3}{5}$-fraction of her APS. This algorithm can also be viewed as providing strategies in a certain natural bidding game, and these strategies secure each agent at least a $\frac{3}{5}$-fraction of her APS.


Introduction
There is a vast literature on the problem of fairly allocating indivisible items to agents that have preferences over the items (see, for example, the classic books [Moulin, 2004, Brams andTaylor, 1996] and the recent survey [Bouveret, Chevaleyre, and Maudet, 2016]). While most literature considers the important special case that agents have equal entitlements to the items, there is also a fast growing recent literature on the more general model in which agents may have arbitrary, possibly unequal, entitlements to the items, see, for example, [Babaioff et al., 2020;Farhadi et al., 2019;Chakraborty et al., 2019;Aziz et al., 2019;Aziz et al., 2020]. The settings with arbitrary entitlements are sometimes referred to in the literature as having agents with "asymmetric shares/weights" or "weighted/unequal entitlements".
The general model of arbitrary entitlements captures many settings that are not captured by the equal entitlement model. For example, it captures "agents" that each is actually a representative of a population, and population sizes are different (e.g., states in the US have different population sizes). It can also capture situations in which agents have made unequal prior investments in the goods (as partners that have invested different amounts in a partnership), and can also capture other asymmetries between agents (for additional motivation see examples presented, e.g., in [Chakraborty, Igarashi, Suksompong, and Zick, 2019]). The definition of a "fair division" when agents have unequal entitlements is more illusive than the equal entitlements case. In this paper we explain shortcomings of recent work that aims to capture fairness in allocation of indivisible goods when agents have unequal entitlements. We then suggest a new notion of a share and prove existence of fair allocations with respect to that notion.
A fundamental problem in this space is the allocation of a set M of m indivisible goods (items) to n agents with additive valuations over the items, with no monetary transfers. Every agent i has an additive valuation v i and entitlement of b i > 0 to the items, assuming the entitlements sum up to 1 ( i b i = 1). We want to partition the items between the agents in a "fair" way according to their entitlements, without using money. How should we interpret the meaning of "entitlements" in this setting? If items were divisible then there is a natural interpretation -each agent should get at the least as high value as if getting a b i fraction of each item, which for additive valuations is the same as her proportional share b i · v i (M), which we denote by P roportional(b i ). Yet when items are indivisible, a proportional allocation (one which gives every agent her proportional share) might not exist, nor any finite approximation to it (consider two agents with equal entitlements over a single item -one must get nothing).
To address the problem of indivisibility with equal entitlements, the notion of maximin share (MMS) was suggested by Budish [2011]. This share is equal to the value an agent can ensure she gets if she partitions the items into n bundles, and gets the worst one. Although for some instances it is not possible to give all agents their maximin share, in every instance it is possible to give at least a large constant fraction of it [Kurokawa, Procaccia, and Wang, 2018]. Yet, this notion is clearly inappropriate for agents with unequal entitlements. Consider two agents with entitlements 9/10 and 1/10. With ten identical items, clearly the first agent should not get only five of the items (the maximum she can ensure by splitting the items into two and getting the smaller of the two bundles).
To address this, Farhadi, Ghodsi, Hajiaghayi, Lahaie, Pennock, Seddighin, Seddighin, and Yami [2019] have suggested the notion of Weighted-max-min-share (WMMS). The WMMS of agent i with valuation v i when the vector of entitlements is (b 1 , b 2 , . . . , b n ) is defined to be the maximal value z such that there is an allocation that gives each agent k at least z·b k b i according to v i (see Appendix A for a formal definition). In contrast to the maximin share, the WMMS is influenced by the partition of the entitlements among the other agents. This leads to scenarios in which an agent with arbitrary large entitlement might have a WMMS of 0 even when there are many items. For example, an agent that has entitlement of 99% (b i = 0.99) for 100 items that she values the same, has a WMMS of 0, if the total number of agents is 101. This suggests that the WMMS is sometimes too small. Moreover, that paper presents an impossibility result suggesting the WMMS is sometimes too large: there are instances where in every allocation some agent receives at most a 1 n -fraction of her WMMS. Due to the above examples, we do not view the WMMS as a concept that is aligned well with our intended intuitive understanding of fair allocations when entitlements are unequal. Babaioff, Nisan, and Talgam-Cohen [2020] have suggested a different generalization of MMS to the case of arbitrary entitlements: the l-out-of-d share of an agent is the value she can ensure herself by splitting the set of goods into d bundles and getting the worse l out of them. The Pessimistic share of an agent with entitlement of b i , which we denote 1 by P essimistic(b i ), is defined to be the highest l-out-of-d share of all integers l and d such that l/d ≤ b i . For the equal entitlement case with n agents, b i = 1/n and the P essimistic(b i ) share is the same as the MMS. For the example above, an agent with entitlement of 9/10 will split the items to ten singletons, and will get nine of them. Babaioff et al. [2020] did not prove that there always exists an allocation that concurrently gives each agent some fraction of the pessimistic share. In this paper we present a new share that is always (weakly) larger, and prove existence of a share-approximating allocation 2 even for our larger share. Babaioff et al. [2020] have related the pessimistic share to Competitive Equilibrium (CE), which we discuss next.
A different approach for fair allocation is to try to come up with a fair allocation for each particular instance, instead of defining the share of each agent. For equal entitlements, Varian [1973] has suggested to use Competitive Equilibrium from Equal Income (CEEI) in which each agent has a budget of 1/n and the allocation is according to the Competitive Equilibrium allocation with these budgets. For equal entitlements such a CE allocation is attractive as it ensures several nice fairness properties -it is envy free and thus proportional (and gives each agent at least her MMS).
More generally, the notion of Competitive Equilibrium (CE) is defined for any entitlements, by treating the entitlement of an agent as her budget, and looking for item prices that clear the market. CE allocations are intuitively fair as all agents have access to the same (anonymous) item prices, and in a CE every agent gets her favorite bundle within her budget. For the case of arbitrary entitlements, Babaioff et al. [2020] have proven that the allocation of a CE ensures that an agent with budget b i will get her pessimistic share P essimistic(b i ). Interestingly, unlike the case of equal entitlements, with unequal entitlements a CE allocation need not give every agent her proportional share (see Proposition B.3).
While CE allocations have some nice fairness properties, unfortunately, even for equal entitlements, CE allocations might fail to exist, as one can immediately see from the simple case of two agents with equal budgets and a single item. 3 Thus, as there are instances with no CE, we cannot rely on CE allocations as a method for fair division of indivisible items.
An alternative instance-based approach is to allocate items using the allocation that maximizes the Nash social welfare (NSW), for the equal entitlements case, or the weighted Nash social welfare, for the arbitrary entitlements case. Recall that for valuations v = (v 1 , v 2 , . . . , v n ) and entitlements b = (b 1 , b 2 , . . . , b n ), the weighted Nash social welfare of an allocation A = (A 1 , A 2 , . . . , A n ) is i∈N Caragiannis, Kurokawa, Moulin, Procaccia, Shah, and Wang [2019] showed that an allocation that maximizes NSW is always Pareto optimal, envy-free up to one good (EF1) and always gives each agent at least O( 1 √ n ) fraction of her maximin share, showing that for equal entitlements maximizing NSW ensures a combination of some efficiency and fairness properties.
Unfortunately, for some simple unequal entitlements cases, maximizing the weighted NSW seems to produce unfair allocations. As an example consider an instance with three agents and three items, two of the items are good (value 1 each) and the last item is unattractive. Assume the first two agents have a value 0 for it, while the last agent has a value ε > 0. No matter how high the entitlement of the last agent is, in every allocation that maximizes the weighted NSW she will receive the unattractive item. This seems very unfair to the last agent, as although she has the largest entitlement (possibly by far), she only gets her least preferred item.

Our Contribution
Our first, conceptual contribution, is the definition of a new share, the AnyPrice share, a share definition that is suitable not only for equal entitlements but also for arbitrary entitlements, and makes sense beyond additive valuations. We present two alternative definitions for this share, one based on prices (inspired by CE) and another on item bundling (inspired by MMS).
The first definition, based on prices, defines the share of an agent i to be the value she can guarantee herself whenever her budget is set to her entitlement b i (when i b i = 1) and she buys her highest value affordable set when items are adversarially priced with a total price of 1. Let P = {(p 1 , p 2 , . . . , p m )|p j ≥ 0 ∀j ∈ M, j∈M p j = 1} be the set of item-price vectors that total to 1. The price-based definition of AnyPrice share (APS) is the following: Definition 1.1 [AnyPrice share] Consider a setting in which agent i with valuation v i has entitlement b i to a set of indivisible items M. The AnyPrice share (APS) of agent i, denoted by AnyP rice(b i , v i , M), is the value she can guarantee herself whenever the items in M are adversarially priced with a total price of 1, and she picks her favorite affordable bundle: Observe that the AnyPrice share is well-defined for any instance, and is a definition of a share that depends on the agent valuation and entitlement, but not on the valuations and entitlements of the other agents. This can be contrasted with the value the agent gets under a CE allocation, a value that depends on the entire instance, and additionally, is not well defined as a CE might not exist. The AnyPrice share is defined using prices, but unlike CE, it does not require finding prices that clear the market (which might not exist) but rather use (worst case) prices that define a share for an agent based on her own valuation and entitlement. From the definition it is clear that when a Competitive Equilibrium exists (with entitlements serving as budgets), every agent gets at least her APS (as the CE price vector is one possible price vector in the minimization).
We further present an alternative definition that turns out useful in proving claims regarding APS. Using LP duality we show that the AnyPrice share (APS) of agent i also equals to the maximum value z such that there exists a distribution over bundles for which i has a value of at least z, such that no item is allocated more than b i times in expectation (see Definition 3.1 for a formal definition). We show (Proposition 3.3) that there is always a solution to this optimization problem with small support -at most m sets in the support. While some of our proofs use the priced-based definition, others use the alternative definition, demonstrating the usefulness of both.
The next example illustrates the notion of APS.
Example 1.2 Consider a setting with five items and an agent i with entitlement b i = 2 5 and an additive valuation with values for the items being 2, 1, 1, 1, 0. Her proportional share is 2 5 (2 + 1 + 1 + 1) = 2. Her pessimistic share P essimistic(b i ) is 1, as partitioning the items to five bundles and getting the worst two bundles, or partitioning to four or three bundles and getting the worst bundle, gives a value of only 1. Her APS is at least 2 as for any pricing of the items, either the item of value 2 has price at most 2 5 , or there are two items of value 1 whose total price is at most 2 5 . Her APS is not larger than 2, as by pricing each item at fifth of its value, the agent cannot afford a bundle of value more than 2.
The example illustrates that when valuations are additive, the APS can be larger than the pessimistic share (even twice as large). This is no coincidence, as we show that the APS is always at least the pessimistic share, for any valuations (even non-additive).
The definition of APS does not rely on the valuations being additive, and is well defined for any valuations. Yet, in this paper we mainly focus on proving results for the additive case, leaving the study of more general valuations for future research. We start by making several observations regarding properties of the APS for additive valuations. First, we observe that it is at most the proportional share. Secondly, we show that while the APS is NP-hard to compute (like the MMS), it has a pseudo-polynomial time algorithm, while the MMS does not. We then turn to prove results about the approximation to the APS that can be given to all agents concurrently. We observe that for two agents, it is always possible to give both of them their APS, and turn to study the more involved case of more than two agents. Our main result is that for any number of agents with additive valuations and arbitrary entitlements, it is always possible to give each agent at least a 3 5 fraction of her AnyPrice share, and moreover, at least 1 2−b i fraction of the APS (which is more than 3 5 if her entitlement is larger than 1/3). Note that the fraction 1 2−b i goes to 1 as b i grows to 1.
Theorem 1.3 For any instance with n agents with additive valuations v and entitlements b, there exists an allocation in which every agent gets at least max{ 3 5 , 1 2−b i } fraction of her AnyPrice share. Moreover, such an allocation can be computed in polynomial time.
As far as we know, this is the first positive result that guarantees a constant fraction of any share to agents with arbitrary entitlements. (See Section 6 for clarifications regarding this statement.) Recall that for equal entitlements, with at least three agents it is not possible to give all agents their MMS [Kurokawa, Procaccia, and Wang, 2018]. As the APS is at least as large as the MMS, we thus conclude that when there are more than two agents one cannot hope to give all agents their APS share exactly, even in the equal entitlements case, and constant approximation is the best we can hope for (we leave open the problem of finding the exact constant).
The proof of the theorem is based on analyzing a natural "bidding game", in which entitlements serve as budgets, and at each round the highest bidder wins, taking any items she wants and paying her bid for each item taken. We show that in this game, no matter how other players bid, an agent has a bidding strategy that gives her at least max{ 3 5 , 1 2−b i } fraction of her APS. If the bidding game is used as the mechanism for allocating the items, then in every equilibrium (e.g., of the full-information game), every agent receives at least max{ 3 5 , 1 2−b i } fraction of her AnyPrice share.
Finally, we consider the APS in the special case of equal entitlements. While for equal entitlements the pessimistic share coincides with the MMS, the APS does not. Rather, the APS is at least as large as the MMS, and sometimes strictly larger. Hence existing algorithms that guarantee every agent a positive fraction of the MMS need not guarantee the same fraction with respect to the APS. Nevertheless, we prove that in the equal entitlements case an algorithm of [Barman and Krishnamurthy, 2020] gives every agent at least a 2 3 fraction of her APS (which is better than the 3 5 fraction that we get for the arbitrary entitlements case).
Theorem 1.4 For any instance with n agents with additive valuations v and equal entitlements (b i = 1/n for every i), there exists an allocation in which every agent i gets at least a 2n 3n−1 fraction of her AnyPrice share. Moreover, such an allocation can be computed in polynomial time.
As mentioned above, giving every agent her APS is not possible, even for equal entitlements. Finding the best approximation is open even for the case of equal entitlements. We remark that our results are actually somewhat stronger than the theorems stated above. Some bounds are proven with respect to a notion of a share called the Truncated Proportional Share (TPS) (see Section 4.1) which for additive valuation is at least as large as the APS, and sometimes larger.
The paper is organized as follows. We first present some additional related work in Section 1.2. We then present the model and some prior fairness definitions in Section 2. We introduce the notion of AnyPrice share and discuss its properties in Section 3. We then present our main result for APS with arbitrary entitlements in Section 4, and our result for the special case of equal entitlements in Section 5. All proofs missing from the body of the paper appear in the appendix. The main part of this paper considers only allocation of goods. Extensions of the AnyPrice share to chores and to mixed manna are presented in Appendix F.

Additional Related Work
One approach taken for fairness when agents have equal entitlement is to require the allocation to be envy free (EF). With indivisible items, such envy-free allocation might not exist, and relaxations as envy-free up to one good (EF1) were considered [Budish, 2011]. EF1 allocations were shown to exist in [Lipton, Markakis, Mossel, and Saberi, 2004]. Clearly, when agents have different entitlements, naively using this notion is inappropriate. Chakraborty, Igarashi, Suksompong, and Zick [2019] have extended envy-freeness to settings with agents having arbitrary entitlements (introducing notions of strong and weak weighted EF1, WEF1), and proved existence result for Pareto optimal allocations satisfying these notions. We remark that even in the equal entitlements settings, there are instances with an EF1 allocation (that is Pareto optimal) that has an agent that only gets an O( 1 n ) fraction of her MMS. Hence WEF1 allocations do not guarantee agents a constant fraction of their APS.
While we consider fair allocation of indivisible goods to agents with arbitrary entitlement, Aziz, Chan, and Li [2019] considered the related problem of fair assignment of indivisible chores (negative value items). Aziz, Moulin, and Sandomirskiy [2020] considered the case that every item value might have mixed signs (a good for some agents, a bad for others) when agents have arbitrary entitlements, and show that there always exists an allocation that is not Pareto dominated by any fractional allocation and also gives each agent her proportional share up to one item. Moreover, they show that such an allocation can be found in polynomial time.
Our result for agents with equal entitlements shows that we can give each agent 2/3 of her APS. As the APS is at least the MMS, this result relates to the literature on MMS and approximate MMS allocations. The maximin share (MMS) was first introduced by Budish [2011] as a relaxation of the proportional share. Kurokawa, Procaccia, and Wang [2018] showed that for agents with additive valuations, an allocation that gives each agent her MMS may not exists. A series of papers [Kurokawa et al., 2018;Amanatidis et al., 2017;Barman and Krishnamurthy, 2020;Ghodsi et al., 2018;Garg et al., 2019;Garg and Taki, 2020] considered the best fraction of the MMS that can be concurrently guaranteed to all agents, and the current state of the art (for additive valuations) is 3 4 + Ω( 1 n ) fraction of the MMS. In our proofs we consider a natural bidding game in which agents have budgets, and bid for the right to select items (as many items as their budget allows, given the bid). We design and analyse strategies for the agents that guarantee that they obtain a high value in the game. Our bidding game is a variant of the Poorman game introduced by Lazarus, Loeb, Propp, and Ullman [1995] where the agents start with budgets, and in each turn, the agents perform a first price auction in order to determine who selects the next action of the game. Variants of these games were later studied in the context of allocating items in multiple papers, for example, [Huang et al., 2012, Meir et al., 2018.

Model
We consider fair allocation of a set M of m indivisible goods (items) to a set N of n agents, with entitlements to the items that are potentially different. Each agent i is also associated with an entitlement b i > 0, and the sum of entitlements of the agents is 1 (i.e., i∈N b i = 1). We use b = (b 1 , . . . , b n ) to denote the vector of agents' entitlements, and say that agents have arbitrary entitlements. If b i = 1/n for every i then we say that agents have equal entitlements. In this work we consider deterministic allocations. An allocation A is a partition of the items to n disjoint bundles A 1 , . . . , A n (some of which might be empty), where A i ⊆ M for every i ∈ N . 4 We denote the set of all allocations of M to the n agents by A. A valuation v over the set of goods M is called additive if each item j ∈ M is associated with a value v(j) ≥ 0, and the value of a set of items S ⊆ M is v(S) = j∈S v(j). A valuation v is called subadditive if for every two sets of items S, T ⊆ M, it holds that v(S) + v(T ) ≥ v(S ∪ T ). In this work we assume that all valuations are monotone (i.e., v(S) ≥ v(T ) for every T ⊆ S), and normalized (i.e., v(∅) = 0.) Let v i (·) denote the valuation of agent i, and let v = (v 1 , . . . , v n ) denote the vector of agents' valuations. We assume that the valuation functions of the agents as well as the entitlements are known to the social planner, and that there are no transfers (no money involved).
We formally define some shares from the literature. The proportional share of agent i with valuation v i and entitlement When v i and M are clear from context we omit them from the notation and denote this share by P roportional(b i ). We next define the maximin share (MMS), which is defined for the equal entitlements case.
Definition 2.1 (maximin Share (MMS)) The maximin share (MMS) of agent i with valuation v i over M, when there are n agents, which we denote by M M S n (v i , M), is defined to be the highest value she can ensure herself by splitting the goods to n bundles and getting the worst one. Formally: When v i and M are clear from context, we denote this share by M M S n , and when n is also clear from context, we simply use the term MMS. In order to formalize the notion of pessimistic share, we first present the definition of the ℓ-out-of-d share, a generalization of the MMS.
Definition 2.2 (ℓ-out-of-d share) The ℓ-out-of-d share of agent i with valuation v i over M is the value she can ensure herself by splitting the goods to d bundles and getting the worse ℓ out of them. Formally: where Z is the set of all partitions of M into d disjoint sets.
, is defined to be the highest ℓ-out-of-d share for all integers ℓ and d such that ℓ d ≤ b i . Formally: When v i and M are clear from context we omit them from the notation and denote this share by P essimistic(b i ).

The AnyPrice Share (APS)
In this section we introduce a new share definition that is well defined for arbitrary entitlements (even for non-additive valuations), presents some of its properties and compare it to previous suggested shares.

The Definition of the AnyPrice Share
We present two definitions of AnyP rice(b i , v i , M), the AnyPrice share (APS) of an agent i that has valuation v i and entitlement b i (when i b i = 1) to items M. The definitions are general and well defined for every valuations, not requiring that the valuations are necessarily additive. Our first definition is based on prices and was presented as Definition 1.1 in Section 1.
The first definition, based on prices, defines the share of an agent i to be the value she can guarantee herself whenever her budget is b i and she buys her highest value affordable set when items are adversarially priced with total price of 1. Let P = {(p 1 , p 2 , . . . , p m )|p j ≥ 0 ∀j ∈ M, j∈M p j = 1} be the set of item-price vectors that total to 1. We restate the price-based definition of APS: Definition 1.1 [AnyPrice share] Consider a setting in which agent i with valuation v i has entitlement b i to a set of indivisible items M. The AnyPrice share (APS) of agent i, denoted by AnyP rice(b i , v i , M), is the value she can guarantee herself whenever the items in M are adversarially priced with a total price of 1, and she picks her favorite affordable bundle: When M and v i are clear from context we denote the APS share of an agent i with entitle- We next present the second definition of the AnyPrice share, using item packing (in Proposition 3.2 we show that the two definitions are equivalent).
, is the maximum value z she can get by coming up with nonnegative weights {λ T } T ⊆M that total to 1 (a distribution over sets), such that any set T of value below z has a weight of zero, and any item appears in sets of total weight at most b i : subject to the following set of constraints being feasible for z: An equivalent set of constraints that will sometimes be convenient to use is the following. Let G i (z) be the family of sets T ⊆ M such that v i (T ) ≥ z. The set of constraints now becomes For the case of equal entitlements this definition can be viewed as a fractional relaxation of the definition of MMS (and hence implying that the APS is at least as large as the MMS). Specifically, one can get the definition of the MMS (with n agents, hence b i = 1 n ) by restricting every weight λ T to be either b i or 0 for any non-empty set. As the total weight is 1, there must be at most n bundles with non-zero weight. The constraint that every item belongs to bundles with total weight of at most b i implies that all non-empty positive-weight bundles are disjoint. The APS on the other hand, relaxes the constraint λ T ∈ {0, b i } for non-empty sets (which can be thought of as an integer constraint of the form λ T ∈ {0, 1} · b i ) to the fractional constraint 0 ≤ λ T ≤ b i , and maintains the constraint that every item belongs to bundles with total weight of at most b i .
While the price-based definition (Definition 1.1) is very useful in proving that the APS is not larger than some value, by simply presenting prices for which the agent cannot afford any bundle of that value, the weight-based definition (Definition 3.1) is very useful in proving the APS is at least as large as some value z -by simply presenting weights that satisfy the definition for some value z. Indeed, let us go back to Example 1.2 to illustrate this point. Recall that the example considers a setting with five items and an agent i with entitlement b i = 2/5 and an additive valuation with values for the items being 2, 1, 1, 1, 0. Using the price-based definition one could easily see that the APS of the agent is at most 2, by pricing each item at fifth of its value. To see that the APS is at least 2 using the alternative definition, consider a distribution over four sets of value 2, one set contains the item of value 2 and weight 2/5, and three sets each contains a different pair of items of value 1, and each of the sets has a weight of 1/5. Each of the four sets has a value of 2, and the total weight of the sets that contain any item is at most 2/5, thus showing the APS is at least 2.
We start with several simple observations. We first show, using linear programming duality, that Definitions 3.1 and 1.1 are indeed equivalent.
Proposition 3.2 The two shares defined in Definition 3.1 and Definition 1.1 are equivalent.
We further observe that there is always a solution with small support to the feasibility problem of Definition 3.1 -at most m sets in the support. We observe that in any Competitive Equilibrium 5 in which the entitlement of an agent is her budget, every agent gets her AnyPrice share. This follows immediately from Definition 1.1 as the APS of an agent is the value the agent can secure for any possible prices, and in particular, at least that value can be secured for the CE prices.
Observation 3.4 Assume that the pair (A, p) is an allocation-prices pair that forms a Competitive Equilibrium when agents have valuations v and budgets (=entitlements) b. Then the allocation A is an APS allocation, that is, for every agent i it holds that We next show the APS of an agent is at least as large as the pessimistic share.  Computationally, the problem of computing the APS is NP-hard, much like the problem of computing the MMS.
Proposition 3.6 The problem of computing the AnyPrice share of an agent is NP-hard. This is true even for b i = 1 2 (the case of two equally entitled agents) and even when the valuations are additive.
Proposition 3.6 follows from the fact that for b i = 1 2 the APS and the MMS are identical (Observation 3.8), and as MMS is hard to compute in the case of two additive agents with equal entitlements (need to solve PARTITION ), so is the APS.
The APS definition is general and applies to all valuations, not only additive. Yet, ex-post fairness is problematic for some super-additive valuations (even for equal entitlements). To illustrate the problem, consider the simple setting with agents that each has zero value for her set, unless she gets all items. Splitting the set of items makes little sense, and any reasonable solution will allocate all items to one agent (possibly at random, to get some ex-ante fairness). Thus we view ex-post fairness notions (APS, as well as all other ex-post notions like MMS, CE, etc.) as unsuitable for some super-additive valuations. In contrast, for sub-additive valuations, splitting the set of items does make sense, and so do ex-post fairness notions, and the APS in particular. Before moving to our main interest in this paper, the case of additive valuations, we briefly illustrate the AnyPrice share on unit-demand valuations (which, like additive valuations, is a simple family of sub-additive valuations), illustrating that the APS is indeed a reasonable notion of a share for some sub-additive valuations.

Unit-Demand valuations
A valuation is unit demand if it assigns a value for each item, and the value of any set is the maximal value of any item in the set. We first note that unit-demand valuations illustrate that the proportional share is not attractive as a share definition for non-additive valuations, even for equal entitlements. Consider for example the simple case of an agent that has a unit-demand valuation over n identical items (same value of 1 for each, and no additional value for more than one item). While n such agents can get a value of 1 each, the proportional share of such an agent is only 1/n, 6 so the proportional share is not even as large as the worst of the n items. In contrast, the APS share in this example is 1.
More generally, we observe that for unit-demand valuations with any entitlements, the value of the APS of an agent with entitlement b i is the value of her ⌈1/b i ⌉ ranked item. 7 There is always an allocation that gives each player her APS: simply let the agents pick items sequentially in the order of their entitlements, breaking ties arbitrarily.

Basic Properties of APS with Additive Valuations
We next focus on additive valuations. We start by relating the different notions of shares to each other.
Proposition 3.7 For any additive valuation v i over a set of items M, and any entitlement b i it holds that Moreover, for each of the above inequalities there is a setting in which it holds as equality. Finally, even for the case of equal entitlements (b i = 1 k for an integer k), in which the pessimistic share is equal to the MMS, for each inequality above there is a setting in which it holds as a strict inequality.
In particular, this claim shows that the APS is at least as large as the pessimistic share of [Babaioff, Nisan, and Talgam-Cohen, 2020], and thus obtaining share approximating allocations for the APS is harder. Note that for equal entitlements (b i = 1 k for an integer k) the MMS and the pessimistic shares are the same, so the above says that even for equal entitlements, the APS and the MMS are different. Yet, they are the same in the special case of two agents with equal entitlements (b i = 1 2 ).
Observation 3.8 For any additive valuation v i over a set of items M, it holds that With two agents, the cut-and-choose procedure ensures that each of the two agents gets her MMS (when b 1 = b 2 = 1/2). We next observe that for the case of two agents, even with arbitrary entitlements, there is always an allocation that gives each agent her AnyPrice share.
Observation 3.9 For any setting with two agents with additive valuations (v 1 , v 2 ) and arbitrary entitlements (b 1 , b 2 ) there is an allocation A = (A 1 , A 2 ) that is an APS allocation. That is, for Recall that we have observed that the problem of computing the AnyPrice share of an agent with an additive valuation is NP-hard, like the problem of computing the MMS. Yet, we next show that it has a pseudo-polynomial time algorithm, while the MMS does not. 8 That is, for any integer additive valuation v i and entitlement b i , if the value of the APS of an agent is z then the APS can be computed exactly in time polynomial in the input size and z (note that z is at most v i (M)), which is pseudo-polynomial 9 . This is in contrast to the MMS which is computationally harder -it is known to be strongly NP-hard when the number of agents is large ( [Woeginger, 1997], can be proven by a reduction from 3-PARTITION) and hence it does not have a pseudo-polynomial time algorithm, unless P=NP.
Proposition 3.10 Consider the problem of computing, for any integer additive valuation v i and There is an algorithm that computes the APS in time polynomial in the input size (representation of the valuations and entitlement) and z.

APS Approximation for Additive Agents: Arbitrary Entitlements
In this section we present our main result regarding fair-share approximation for additive agents with arbitrary entitlements. We start with extending the definition of Truncated Proportional Share (TPS) of Babaioff, Ezra, and Feige [2021] to arbitrary entitlements, and show it is at least as high as the APS, and thus can serve as a tool in proving results for APS. Then, we present our main result -showing that for agents with additive valuations and arbitrary entitlements there is a bidding game in which each agent can always secure herself a 3 5 fraction of her AnyPrice share, and can also secure at least 1 2−b i fraction of her Truncated Proportional Share (which is at least her APS). As the analysis of the strategies for these bounds is rather involved, most details of the proofs are deferred to the appendix. To give the reader a sense of some ideas that we use, we present some weaker bounds that are easier to analyze, along with their analysis. In particular, we present a natural strategy that secures half the TPS, and a strategy that obtains some constant fraction, that is strictly larger than half, of the APS.

The Truncated Proportional Share (TPS)
The Truncated Proportional Share (TPS) was defined in [Babaioff, Ezra, and Feige, 2021] for additive agents with equal entitlements. In this section we extend their definition to arbitrary entitlements and show that for additive agents the TPS is always at least as large as the APS. We then present a polynomial time algorithm that gives every agent a constant fraction of her TPS, and thus also that fraction of her APS share. Babaioff et al. [2021] have defined the TPS for equal entitlements. For equal entitlements setting with n agents and a set of items M, the truncated proportional share of agent i with additive valuation function v i is the largest value t such that 1 n j∈M min[v j , t] = t. We extend this definition to the case of arbitrary entitlements in a natural way, by thinking of 1 n as the entitlement of the agent in the equal entitlement setting, and replacing it by the agent's entitlement b i in the arbitrary entitlement case: (1) When M and v i are clear from the context we denote this share by T P S(b i ).
Observe that it is immediate from Definition 4.1 that the TPS is at most the proportional share, and that the TPS is exactly the proportional share of the instance after capping the value of each item at the TPS. Alternative, one can think about the following continuous process to reach the TPS by capping the valuation: a cap on item values is reduced until the point that no item has a capped value which is strictly greater than the proportional share of the current capped valuation.
We next show that the TPS is always at least as large as the APS. Thus, by obtaining a guarantee with respect to the TPS, we will also obtain the same guarantee with respect to the APS.
We denote the set of items that have values strictly more than w by K, and let k = |K|. If k = 0 then the T P S( , and thus by Proposition 3.7 the proposition holds. Assume k > 0. By Definition 4.1, it holds that w = b i · k · w + j∈M\K v i (j) . It also holds that b i · k < 1. To see this, first observe that if Thus ℓ satisfies Equation (1) and hence the TPS is at least ℓ > w, which is a contradiction. We thus conclude that b i · k < 1.
If v i (M \ K) = 0 then if we price all items in K by 1 k , the agent cannot afford any item she has positive value for (v i (M \ K) = 0 and since b i < 1 k she cannot get any item in K), and thus is strictly more than w. Thus, there exists an ǫ > 0 such that Such an ǫ > 0 must exist since when ǫ → 0 then this expression goes to w, while when ǫ → 1 k −b i , the expression goes to infinity, and it is continuous in ǫ for ǫ ∈ (0, 1 k − b i ). Consider the pricing b i + ǫ for every item in K, and for every item j ∈ M \ K, we give a price The agent cannot afford any item among K. Among the other items, her value is proportional to the budget spent and thus is at most , which is strictly smaller than z * , contradicting the definition of z * as her APS.
In Appendix B we discuss some other properties of the TPS. We show that the TPS might be much larger than the APS (Observation B.1). We observe that while the APS is (weakly) NP-hard to compute, the TPS can be computed in polynomial time (Observation B.2). Yet, we only use TPS as a tool, and do not consider it as the most appropriate share for agents with arbitrary entitlements, as it has some significant drawbacks. The main drawback of TPS is that, similarly to the proportional share, it seems unattractive beyond additive valuation: the unit-demand valuations (with identical items) example in Section 3.1.1 is one in which the TPS is identical to PS, and the proportional share (and TPS) seem too small (only 1/n instead of 1).
We also show (Proposition B.3) that a competitive equilibrium (CE) does not necessarily guarantee that every agent gets her TPS, unlike the case for APS (in which in every CE, every agent gets her APS). Finally, we note (see Observation B.4) that even for equal entitlements, it is not possible to give every agent more than a n 2n−1 fraction of her TPS. This is in contrast to the APS for which our main result shows that it is possible to give every agent a 3 5 fraction of her APS.

Main Result: Approximate APS Allocations
We next turn to present and prove our main result: for agents with additive valuations and arbitrary entitlements, it is always possible to give each agent at least a 3 5 fraction of her AnyPrice share, and at least 1 2−b i fraction of her Truncated Proportional Share (which is at least her APS). This 1 2−b i fraction is more than 3 5 if the agent entitlement is larger than 1 3 , and it goes to 1 as b i grows to 1. Moreover, we show that agent i also gets a value that is at least the value of her ⌊1/b i ⌋ ranked item. Note that this result implies Theorem 1.3 (it is a stronger version of it). Our result follows from presenting a natural "bidding game", and showing that each agent has a strategy to secure each of the guarantees mentioned above.
Consider the following "bidding game" among the agents: Every agent i starts with a budget of b i . As long as there are still items left, in each round t, every agent bids an amount r (t) i between 0 and b (t) i . An agent with the highest bid (breaking ties arbitrarily) is the winner of the round, we denote that winning agent by w (t) . Within her remaining budget b (t) w (t) , agent w (t) selects available items she wants to take, paying r We have the following notations for the beginning of round t: M (t) -the available items at the beginning of round t. s i -the budget available to i at the beginning of round t.
k -the total budget remaining at the beginning of round t. 2: Initialize: t = 1, for every agent i, b (1) i (breaking ties arbitrarily) be the winning agent of round t.

6:
Agent w (t) selects a non-empty set W (t) ⊆ M (t) that she can afford:

9:
Remove allocated items: 10: t ← t + 1 11: end while Theorem 4.3 There exists an allocation mechanism for settings with n agents that have additive valuations and arbitrary entitlements, which has the following properties. In that mechanism (the Bidding Game) every agent i has a strategy that regardless of the strategies of the other agents, ensures she gets a bundle of value at least the largest of the following three values: • 60% of her AnyPrice share.
• the value of her ⌊1/b i ⌋ ranked item.
Moreover, that mechanism runs in polynomial time.
Before moving to the proof, we remark that for the case of equal entitlements (b i = 1/n for every i), the approximation of 1 2−b i for the TPS in the theorem is tight and cannot be improved. Indeed, consider n agents with equal entitlements and 2n − 1 identical items, each of value 1 2n−1 . One of the n agents must get at most one item, getting a value of only 1 2n−1 while her TPS is 1 n (identical to her proportional share as no item has value larger than her proportional share).
Thus, that agent gets only n 2n−1 fraction of her TPS, which equals a 1 2−b i fraction of her TPS, as b i = 1/n. Note that n 2n−1 approaches 1 2 when n goes to infinity, and thus any constant approximation to the TPS that is larger than 50% is impossible, while we are able to obtain 60% of the weaker benchmark of APS.
The proof of the theorem is based on presenting three strategies, each guaranteeing one of the bounds promised by the theorem. By picking the one with the highest guarantee, the agent gets all three guarantees. While the last bound (with respect to the ranked items) is simple, the other two bounds are substantially more difficult. As a warm-up, we will start by presenting a simple strategy that ensures that agent i gets at least half of her TPS. We leave the proof that agent i can secure the stronger bound 1 2−b i fraction of her TPS to the appendix. The claim that there is a strategy for agent i that guarantees 60% of her APS appears in Lemma 4.6. As presenting the strategy and its analysis in full is rather complex, in the body of the paper we show how the most involved part can be substituted with a simpler step (presented in Lemma 4.4) that is enough to guarantee a smaller fraction of 8/15 (while leaving the more difficult proof of the stronger bound of 3/5 to the appendix). We note that this fraction of 8/15 still illustrates an important qualitative point -that it is possible for an agent to guarantee herself some constant fraction that is strictly more than 50% of her APS.
To illustrate the use of the bidding game, and likewise, the usefulness of the TPS as an upper bound on the APS, we first present a relatively easy proof that there is an allocation that gives every agent at least half of her TPS (and hence of her APS).
The bid-your-max-value strategy is the strategy in which at each round agent i bids her normalized value of her highest-value remaining item, unless it is higher than her remaining budget -in this case she bids her entire remaining budget. If she wins she picks that item. Formally: If at the beginning of round t, the remaining budget of i is b (t) i , and the highest value remaining item has value x (t) i , then at round t agent i bids min and chooses the maximal value remaining item when winning.
It is immediate from the definition of the strategy that if an agent i is able to spend her entire budget, she will get her proportional share. The following lemma plays a key role in reasoning about those instances in which i fails to spend her full budget. It considers only the special case that no single item has a value larger than the proportional share, but other cases can be reduced to this special case, as will be seen in Corollary 4.5. For this special case, any time that agent i bids her max value but does not win, the total budget of the other agents decreases by at least her max value. It follows that the total available budget of all agents decreases at a rate that is at least as fast as the rate of decrease of the total value of the remaining items. Hence either agent i wins some items, or the other agents run out of budget before they manage to buy all the items that agent i values.
Lemma 4.4 The bid-your-max-value strategy of agent i with additive valuation v i and entitlement b i provides the following guarantee, regardless of the strategies of the other agents. If for some positive integer k no subset of k items has a value larger than the proportional share b i · v i (M), then the value agent i gets is at least a k k+1 -fraction of her proportional share (i.e., at least k k+1 · b i · v i (M)).
Proof. We denote v i (M) by s i . Recall that we consider the strategy in which at round t agent i bids min , and selects the item of highest value if she wins. We shall say that agent i bids her max value at round t if i , and that i bids her budget if Let t * be the latest round such that for every round up to and including t * , agent i bids her max value. That is, denote the total value accumulated by agent i up to the beginning of round t * + 1.
Observe that , as up to (and including) round t * agent i always bids exactly her max value, and hence u ). Thus the value accumulated by agent i by the end of the bidding game is at least It remains to consider the case that b The claim follows from the following argument. In every round t ≤ t * agent i bids her max value Hence in every round t ≤ t * , regardless of which agent won the round, the payment per item consumed in round t was at least i (according to v i ). As the initial total budget is 1, and By the maximality of t * , in round t * + 1 agent i bids her budget. This implies that b Let F i denote the set of items that agent i received up to round t * + 1. If |F i | < k then by the assumption of the lemma, it holds that , and agent i can afford to bid her max value, a contradiction to the definition of t * .
We are left to handle the case of where the first inequality holds since every item in F i has a value of at least x This concludes the proof.
An immediate corollary of Lemma 4.4 (for k = 1) is that the bid-your-max-value strategy gives the agent half her TPS.
Corollary 4.5 Agent i with additive valuation v i and a budget of b i has a strategy in the bidding game that guarantees herself a value of at least 1 2 · T P S(b i ), regardless of the strategies of the other agents. Hence for any additive valuations and arbitrary entitlements there is an allocation that gives every agent at least half of her TPS.
, and thus agent i gets at least half of While the analysis of the strategy that gives a 1 2−b i fraction of the TPS is rather involved and deferred to the appendix, the strategy itself is not very different from the bid-your-max-value strategy presented above. At each round, bid as follows. If there is one item that suffices by itself to obtain the goal, bid your whole budget. Else, if two items suffice, bid half your budget (and take both items if you win). Otherwise, use the bid-your-max-value strategy.
We next turn to present the proof of Theorem 4.3. Proof.(of Theorem 4.3) We present three strategies for agent i that plays in the bidding game, each ensures one of the required guarantees. Among the suggested strategies, depending on her valuation and entitlement, the agent can choose the strategy for which the corresponding guarantee has the highest value. In Lemma D.3 we present a strategy that guarantees agent i at least 1 2−b i -fraction of her TPS. In Lemma 4.6 we present a strategy that guarantees agent i at least 60% of her APS. In order to guarantee the ⌊1/b i ⌋ ranked item the agent can use the strategy of bidding b i , and selecting the maximal available item if she wins. She is guaranteed to select one of the top ⌊1/b i ⌋ ranked items, since otherwise the other agents spent a budget of ⌊1/b i ⌋ · b i which is strictly more than their budget 1 − b i .
One can readily see that all aspects of the strategies above can be implemented in polynomial time, except for one issue. While Observation B.2 shows that the TPS can be computed efficiently, computing the APS is NP-hard, and hence potentially the agent cannot compute beforehand which of the three guarantees is highest (as she cannot compare 3 5 · AP S with the other two guarantees). Moreover, to run the strategy of Lemma 4.6, it appears that the agent needs to know her own APS.
There are two ways of addressing this problem. The simple way is to settle for a pseudopolynomial time algorithm, and use Proposition 3.10. However, there is a better solution that does give a truly polynomial time algorithm. The basic idea is to show that the strategy of Lemma 4.6 does not just guarantee a value of 3 5 · AP S, but in fact a value of 3 5 · V , where V ≥ AP S, and moreover, V can be computed exactly in polynomial time. See more details in Appendix D.1.
Lemma 4.6 shows that an agent can secure a 3 5 fraction of her APS. Let us provide here a brief overview of the proof. In Step 1 of the algorithm, if there is a single item of value at least 3 5 · AP S, the agent bids her whole budget, attempting to win the item. In step 2, if there are two items whose sum of values is at least 3 5 · AP S, she bids half her budget, attempting to win both items. A difficulty arises if there are items of value strictly less than 3 5 · AP S but strictly more than 1 2 · AP S, the agent bids b i 2 (attempting to win two items), but fails to win these items. In this case the budget of the remaining agents is consumed at a rate that is slower than the rate at which the total value of items decreases. This difficulty is handled in Step 3 of the algorithm. The difficulty is counter-balanced by a positive effect: each of the remaining items has relatively low value, and we have already seen in Lemma 4.4 that in such cases the agent can secure herself strictly more than half her TPS (and hence strictly more than half her APS). We show that the positive effect is more significant than the negative effect. For this purpose, we introduce Lemma 4.7, that for the APS provides better bounds than Lemma 4.4 does, though requires stronger assumptions, and its proof is significantly more involved.
For those readers who prefer not to follow the more involved proof of Lemma 4.7, we remark that one can use Lemma 4.4 instead, without changing anything in the proof of Lemma 4.6. This gives a bound of 8 15 · AP S (which is already better than half the APS) instead of 3 5 · AP S. Specifically, let M ′ be the set of remaining items at the beginning of step 3 of the strategy described in Lemma 4.6, and let B ′ be the total remaining budget of all agents at this point. By the definition of step 2 of the strategy described in Lemma 4.6 it holds that there are no two items worth together more than 3 5 · AnyP rice(b i , v i , M). Moreover, it holds that the proportional share of agent i with a normalized budget of b i B ′ over a set of items M ′ satisfies: The equality is by definition of proportionality. The first inequality is by Proposition 3.5. The second inequality follows directly from Equation (2), that states that AnyP rice whenever reaching step 3. Thus, we can apply at this point the strategy of Lemma 4.4 for k = 2 and guarantee a value of at least 2 Lemma 4.6 Agent i with additive valuation v i over M and entitlement b i has a strategy that guarantees a value of at least 60% of AnyP rice(b i , v i , M), regardless of the strategies of the other agents.
. By Definition 3.1 there exists a list of bundles S = {S j } j and associated nonnegative weights {λ j } j such that: We propose the following strategy for the agent.
i . If the agent wins, she selects an item with the highest value, among the available items.
If the agent wins any such round, she selects a pair of items with the highest total value, among the available items.
3. Let t ′ be the first round such that x 5 (so the pre-conditions for both steps above do not hold). Let the total remaining budget be B Agent i runs the strategy of Lemma 4.7 on the instance defined by these budgets and the set of items M ′ = M (t ′ ) .
If the agent wins a bid in either step 1 or step 2 then we are done. Hence we may assume that the agent does not win any such bid. We show that if the agent does not win any item in steps 1 and 2, then If the agent plays according to the strategy defined in Lemma 4.7, the agent guarantees a value of 3 2 · γ ≥ 3z 5 , as desired. To complete the proof it remains to prove Equation (2). To prove that it holds we use the bundles S = {S j } j and associated nonnegative weights {λ j } j , and construct bundles S ′ = {S ′ j } j and weights {β j } j , as required by Definition 3.1, for entitlement b i 2B ′ and share that is at least 2z 5 . Let Q = Q 1 ∪ Q 2 denote the set of items consumed by the adversary in the first two steps (Q 1 for rounds of step 1, Q 2 for rounds of step 2). For each S j ∈ S • If S j ∩ Q 1 = ∅ or |S j ∩ Q 2 | > 1, then S j is discarded.
• If S j ∩ Q 1 = ∅ and |S j ∩ Q 2 | = 0, then S j is split to C j , D j as defined below, and both C j and D j are added to S ′ , each with weight The way we split S j to C j , D j is as follows. We start by setting both C j , D j = ∅, and go over the items in S j in order of decreasing values. As long as v i (C j ) < 2z 5 we add an item to C j . When v i (C j ) ≥ 2z 5 , we add all remaining items to D j . In order to prove that γ ≥ 2z 5 , we need to show that all sets in S ′ have a value of at least 2z 5 . By definition v i (C j ) ≥ 2z 5 . It holds that v i (C j ) ≤ 3z 5 since the first two items in S j are worth together less than 3z 5 (otherwise we are not finished with step 2). If their value is at least 2z 5 , then no more items will be added to C j . Else, the second item has a value of at most z 5 , and therefore any other item in S j will increase the value of C j by at most z The second type of sets that are added to S ′ , are sets S j \ Q 2 where |S j ∩ Q 2 | = 1 (and |S j ∩ Q 1 | = 0). For these sets, notice that since items in Q 2 have a value of at most 3z 5 , then it holds that Observe that for every item e ∈ M ′ , if it belongs to S j , then the weight for the corresponding sets added to S ′ is at most λ j 2B ′ . This is since we either discard this set, or e is added to exactly one set (notice that e cannot be in both C j and D j ). Thus, the total weight of every element is at most b i 2B ′ as needed. It remains to show that the sum of weights of the sets added to S ′ is at least 1.
Let α 1 = j | S j ∩Q 1 =∅ λ j denote the sum of weights of all sets that have items from Q 1 . Let α 2 = j | |S j ∩Q 2 |>1∧|S j ∩Q 1 |=0 λ j denote the sum of weights of all sets that have at least two items from Q 2 and no item from Q 1 . Let α 3 = j | |S j ∩Q 2 |=1∧|S j ∩Q 1 |=0 λ j denote the sum of weights of all sets that have one item from Q 2 and no item from Q 1 .
Observe that α 1 ≤ b i · |Q 1 |, since every item is in at most b i weight of the sets. Likewise, 2 · α 2 + α 3 ≤ b i · |Q 2 |. The sum of weights of all sets that have no items from Q 1 ∪ Q 2 is at least In addition, it holds that B ′ = 1 − |Q 1 | · b i − |Q 2 | · b i 2 since every item in Q 1 was paid b i , and every item in Q 2 was paid b i 2 . The sum of weights of S ′ is which proves inequality (2) and concludes the proof.
The next lemma (whose proof is deferred to Appendix D) states that there is a strategy for agent i that guarantees herself a value of 3 2 · AnyP rice( b i 2 , v i , M). This Lemma (with a suitable assignment to the parameters b i and M) is used in step 3 of Lemma 4.6.
Lemma 4.7 Agent i with additive valuation v i and entitlement b i has a strategy that guarantees herself a value of at least 3 2 ·AnyP rice( b i 2 , v i , M) in the bidding game that allocates M, regardless of the strategies of the other agents.

APS Approximation for Additive Agents: Equal Entitlements
In this section we consider approximating the APS in the special case of equal entitlements. For only two agents with equal entitlements, there is always an allocation giving both their APS, which equals to their MMS (Observation 3.8). We saw (Proposition 3.7) that beyond two agents, even for equal entitlements, the APS is different than the shares defined in prior work (like MMS). As the APS is at least as large as the MMS (Proposition 3.7), and as Kurokawa et al. [2018] showed that for three agents with equal entitlements, simultaneously giving every agent her MMS is not possible, we cannot hope to give every agent her APS exactly, and thus look for an approximation. While for arbitrary entitlements we saw that each agent can guarantee herself at least a 3 5 fraction of the APS (Theorem 4.3), in the equal entitlements case we show that the greedy-EFX algorithm proposed by Barman and Krishnamurthy [2020] gives a stronger guarantee.
In this section we prove the following theorem.
Theorem 5.1 When n agents have additive valuations and equal entitlements, there is an allocation that gives every agent at least the minimum of the following two values: a 3 4 fraction of her APS, and a 2n 3n−1 fraction of her TPS. Moreover, such an allocation can be found in polynomial time.
Recall that for n ≤ 2 there is an allocation that gives every agent at least her AnyPrice share (see Observation 3.9). Hence there is interest in Theorem 5.1 only when n ≥ 3. Note that Theorem 5.1 ensures that each agent always gets at least 2 3 of her APS (as the TPS is always at least the APS).
In proving Theorem 5.1, we shall follow an approach of Barman and Krishnamurthy [2020] who proved the existence of allocations that give every agent at least a 2n 3n−1 fraction of her MMS. The algorithm is identical to that of Barman and Krishnamurthy [2020], but the proof of the key lemma (Lemma 5.3) is different, as we need to establish stronger guarantees than those established in [Barman and Krishnamurthy, 2020].
The first step of the proof of Theorem 5.1 is a reduction to ordered instances. Given an instance of an allocation problem with additive valuations and a fixed order σ among the items (from 1 to m), its ordered version is obtained by each agent permuting the values of items so that values are non-increasing in σ. The following theorem is due to [Bouveret and Lemaître, 2016].
Theorem 5.2 ( [Bouveret and Lemaître, 2016]) For every instance with additive valuations, every allocation for its ordered version can be transformed in polynomial time to an allocation for the original instance. Using this transformation, every agent derives at least as high value in the original instance as derived by the allocation for the ordered instance.
For completeness, we sketch the proof of Theorem 5.2 in Appendix E. Given Theorem 5.2, it suffices to prove Theorem 5.1 in the special case in which the input instance is ordered (and n ≥ 3). For such instances we use an algorithm proposed by [Lipton et al., 2004, Barman andKrishnamurthy, 2020], that we refer to as Greedy-EFX. Greedy-EFX assumes that the instance is ordered, with item e 1 of highest value and item e m of lowest value.
The Greedy-EFX works as follows (see formal definition in Appendix E). Each bundle is associated with one agent. Greedy-EFX proceeds in rounds. In rounds 1 to n the items e 1 up to e n are placed in bundles B 1 up to B n respectively. At a round r > n, if there is an agent whose bundle no one envies, then e r is added to her bundle. Else, if there is no such agent, then there must be envy cycles (in such an envy cycle, each agent envies the next in the cycle). An envy cycle can be resolved by rotating the sets along the cycle, each agent getting the set of the agent she envies. The cycles are iteratively resolved until there are no more envy cycles. At this point, there must be an agent whose bundle no one envies, and then e r is added to her bundle.
Clearly, the greedy-EFX algorithm runs in polynomial time. Hence in order to prove Theorem 5.1, it suffices to prove the following lemma.
Lemma 5.3 When n agents have additive valuations and equal entitlements, the greedy-EFX allocation gives every agent at least the minimum of the following two values: a 3 4 fraction of her APS, or a 2n 3n−1 fraction of her TPS.
The proof of Lemma 5.3 is based on the following principles. Consider an arbitrary agent i. We may assume that under Greedy-EFX agent i receives at least one item of positive value, as otherwise her APS is 0 (as there are less than n items she values). Without loss of generality, assume that the final value received by i is 1. The main part of the proof focuses on one particular item, e k , which is the item of smallest value among those that serve as a first item to enter a bundle that eventually has more than two items. If v i (e k ) ≤ 3 4 , a fairly simple argument shows that the TPS is at most 3n−1 2n , proving that i received at least a 2n 3n−1 fraction of her TPS. If v i (e k ) > 3 4 then we show that the APS is less than 4 3 , and hence that i gets more than a 3 4 fraction of the APS. To upper bound the APS, we exhibit prices that certify this upper bound.
In fact, the prices that we exhibit depend on the exact value of e k , with one set of prices if 3 4 < v i (e k ) ≤ 5 6 , and a different set of prices when v i (e k ) > 5 6 . The full proof of Lemma 5.3 appears in Appendix E.
An immediate corollary of Lemma 5.3 is that for the case of equal entitlements (or for an entitlement which is an inverse of an integer), the MMS is at least 3 4 of the APS. Corollary 5.4 For every additive valuation v i and an entitlement b i = 1 n for some integer n, it holds that Proof. Let S be the allocation returned by greedy-EFX when all agents have the same valuation v i . By Lemma 5.3 every agent receives a value of at least 3 4 of the APS. By definition of the MMS, the least satisfied agent received at most the MMS. This concludes the proof.
We next show that the analysis of the greedy-EFX Algorithm is essentially tight. As the upper bound claimed in the following proposition applies also to the MMS, the proposition may have been previously known. However, we are not aware of an explicit reference to this result, and hence we state it and provide its proof in the appendix.
Proposition 5.5 For every ǫ > 0, there is an instance with additive valuations and equal entitlements in which the greedy-EFX algorithm does not provide some agent more than a 2 3 + ǫ of her MMS (and thus also does not provide more than a 2 3 + ǫ of her APS).
In the appendix we also show that if all agents have identical additive valuation functions (and equal entitlements), then greedy-EFX gives every agent at least a 3 4 of her APS. This ratio is the best possible guarantee that holds for greedy-EFX, even for MMS, as we show that for every ǫ > 0 there are such instances in which greedy-EFX does not give an agent more than a 3 4 + ǫ fraction of her MMS.

Discussion
In this paper we have studied fair allocation for agents with arbitrary (not necessarily equal) entitlements. We have introduced the concept of the AnyPrice share (APS) and have presented a positive constant fair-share approximation result for agents with arbitrary entitlements, showing that for agents with additive valuation functions there always is an allocation that gives each agent a 3 5 fraction of her APS. Following the statement of Theorem 1.3, we claimed that (as far as we know), this is the first positive result that guarantees a constant fraction of any share to agents with arbitrary entitlements. We clarify here what we mean by the term "share".

The Notion of a Share
Intuitively, a share of an agent with some valuation and relative entitlement, represents what value she can reasonably expect to receive in any setting in which the items are partitioned, without any further knowledge (as the valuations of others, or the way entitlements are distributed among others).
Consider an allocation setting with a set M of items, in which every valuation function v i is normalized (v i (∅) = 0) and monotone (v i (S) ≤ v i (T ) for every S ⊆ T ⊆ M). We think of a share as a function f that maps the valuation function v i of an agent and her normalized where this function f needs to satisfy some natural properties, such as the following: • Value Scaling: if the valuation function is scaled by a multiplicative factor of c, then the share is scaled by the same multiplicative factor. (Note that we do not require scaling with respect to the entitlement.) Of course, for a notion of a share to be useful, we want f to have additional properties beyond those listed above. It should strike a good balance between being as large as possible, yet still allowing for allocations that give every agent some substantial fraction of her share. We shall not attempt to rigorously define what makes a notion of a share useful.
When one defines a share as a function satisfying all the above properties, then the proportional share, the pessimistic share and our AnyPrice share (APS) are indeed shares. Likewise, the maximin share (MMS) is a share, if one restricts the entitlements b i to be of the form b i = 1 k i for an integer k i > 1. The weighted maximin share (WMMS) of Farhadi et al. [2019] is not a share under our definition, as its value depends not only of v i and b i , but also on how the remaining 1 − b i entitlement is distributed among the remaining agents. However, we may relax our definition of a share so that it also includes WMMS (this requires a certain adaptation of the entitlement monotonicity property). Among all the above notions of shares, indeed Theorem 1.3 is the first positive result that guarantees a constant fraction of a share to agents with arbitrary entitlements. This guarantee is given with respect to the AnyPrice share, and hence it holds also with respect to the pessimistic share (which is never larger than the AnyPrice share).
To further clarify our use of the term share, let us briefly discuss Prop1, which is a "close relative" to the proportional share. An allocation is Prop1 if every agent gets at least her proportional share, up to one item. Prop1 is a property of a solution rather than a mapping of v i and b i to a value, and hence it is not a notion of a share. However, one can try to define a share based on Prop1. A natural definition would be a value equal to the proportional share, minus the value of the most valuable item (namely, b i v i (M) − max e∈M v i (e)), as this is a lower bound on the value that the agent gets in any Prop1 allocation. 10 However, this definition does not satisfy valuation monotonicity (by increasing the value of the most valuable item, the "share" value decreases rather than increases). Hence we do not view neither Prop1 nor its derivatives as a notion of a share.

Interpretation of the AnyPrice Share as an Analog of Cut and Choose
The MMS can be thought of as being motivated by the cut-and-choose paradigm, where the agent plays the role of the "cutter". The value of the MMS for an agent is the maximum value she can secure to herself if she were to partition ("cut") the grand bundle into n bundles, and allow every other agent to choose a bundle before she does. The APS can also be thought of as being motivated by the cut-and-choose paradigm, as we explain below.
Recall that we provided two equivalent definitions for the APS. Definition 3.1 (that we referred to as the dual definition) can be thought of as a natural variation on the definition of MMS. Instead of insisting on an integral partition into bundles, one allows a fractional partition, with the advantage that fractional partitions can be easily extended to situations in which agents do not have equal entitlements. In this respect, the APS is motivated by MMS, and hence, indirectly by the cut-and-choose paradigm. However, even in the case of equal entitlements, the APS is not the same as the MMS, and so some of the cut and choose motivation (with the agent as the cutter) may be lost in this adaptation.
Consider now the price based definition of APS, Definition 1.1. This definition can be viewed as being motivated by the cut-and-choose paradigm, but with the agent playing the role of the chooser, not the cutter. Recall that the APS depends only on the valuation function of the agent and her entitlement, but not on valuation functions and entitlements of other agents. Hence pretend that there are no other agents. Instead, there is just a single current owner of all items, and our agent that has a b i entitlement to the items. Our agent comes to claim her fair share of items from this owner, whereas the owner is interested in keeping the items for himself. Which items should our agent be allowed to take? Here we may use a price-and-choose paradigm, in the spirit of the cut-and-choose paradigm. As the situation is not symmetric (there is a current owner of the item and our agents that has claims on the items), the current owner is the one who is allowed to price the items in any way he wishes, provided that the prices are non-negative and sum up to 1. Now our agent with a budget of b i plays the role of the chooser, and is allowed to choose any bundle that she can afford. Her APS is the maximum value that she can guarantee herself as a chooser in such price-and-choose games.

Directions for Future Work and Open Questions
Several approximability results appearing in this paper provide constant factor approximation ratios that are not known to be best possible. It would be interesting to improve over any of them. We list the known lower bounds and upper bounds for three such results (all for additive valuation functions).
1. What is the largest possible gap between the APS and the MMS when agents have equal entitlements (or equivalently, when the entitlement b i is the inverse of a positive integer)? Theorem E.5 shows that in this case the value of the MMS is at least a 3 4 fraction of the value of the APS, and Lemma C.1 shows that sometimes the ratio is no better than 96 97 . 2. How much of the APS can one guarantee to agents with equal entitlements? Theorem 5.1 shows that there always is an allocation that gives every agent at least a 2 3 fraction of her APS. In [Feige, Sapir, and Tauber, 2021] it is shown that there are allocation instances for which there is no allocation that gives every agent more than a 39 40 of her MMS. This negative result applies also to the APS (as the APS is at least as large as the MMS).
3. How much of the APS can one guarantee to agents with arbitrary entitlements? Theorem 1.3 shows that there always is an allocation that gives every agent at least a 3 5 fraction of her APS. The negative result of 39 40 still applies (as equal entitlements is a special case of arbitrary entitlement).
A natural direction for future work for additive valuations is to obtain best-of-both-worlds results for agents with arbitrary entitlements, for example, simultaneously achieving ex-ante proportionality as well as APS approximation ex-post. Such results are known for agents with equal entitlements [Babaioff, Ezra, and Feige, 2021].
More generally, one would like to study the APS for additional classes of valuation functions, such as submodular valuations.

A Some Formal Definitions
In this section we present some formal definitions that are omitted from the body of the paper.
Definition A.1 (Competitive Equilibrium (CE)) Given the valuations of the agents v = (v 1 , . . . , v n ), and a vector of budgets b = (b 1 , . . . , b n ), a Competitive Equilibrium (CE) is a pair (A, p) of an allocation A of all items and a vector of item prices p, where the price of a bundle received by each agent is at most her budget (i.e., p(A i ) = j∈A i p j ≤ b i ), and every agent's bundle is utility maximizing under her budget (i.e., for all S ⊆ M, p Definition A.2 (Weighted maximin share (WMMS)) The weighted maximin share (WMMS) of agent i with valuation v i over M, when the vector of entitlements is (b 1 , b 2 , is defined to be the maximal value z such that there is an allocation that gives each agent k at least z·b k b i according to v i . Formally:

B Properties of The Truncated Proportional Share (TPS)
Observation B.1 shows that the TPS might be much larger than the APS.
Observation B.1 For any ε > 0 there exist an additive valuation and an entitlement b i such that ε · T P S(b i ) ≥ AnyP rice(b i ).
Proof. Consider the case of entitlement b i = 1 k+ǫ and k + 1 items, k of them with value b i , and one item with value r = ǫ k+ǫ . The APS is r = ǫ k+ǫ , since if we set the prices of the high value items at price 1 k , while pricing the low value item at 0, the agent can only afford the low value item. The APS is not lower since the agent can always afford at least one item. In contrast, the TPS is 1 k+ǫ , since no item is worth more than the entitlement, so the TPS is the same as the proportional share.
The next observation shows that the TPS can be computed efficiently.
Observation B.2 Consider the problem of computing, for any integer additive valuation v i and entitlement b i (were b i ≤ 1 is a rational number), the truncated proportional T P S(b i , v i , M). There is an algorithm that computes the TPS in time polynomial in the input size.
Proof. Compute the proportional share P S i = b i ·v i (M). Let j denote an item of highest value under v i . If v i (j) ≤ P S i then the TPS is P S i . If v i (j) > P S i then there are two cases to consider. In one case, b i ≥ 1 2 . In this case the TPS is z = . This can be verified, as after reducing the value of v i (j) to z, no item other than j has value larger than z (because b 1−b ≥ 1), and it indeed holds that z In the other case b i < 1 2 . In this case Lemma D.1 implies that the TPS equals . As in this case the number of items decreases, it takes no more than m iterations to compute the TPS.

Proposition B.3
There exists an instance with additive valuations v and entitlements b such that no allocation gives every agent her truncated proportional share (or her proportional share), yet a competitive equilibrium with entitlements as budgets does exist.
Proof.Consider an instance with two agents 1, 2, and three identical items M = {a, b, c}. Every agent has value of 1 3 for each item. The agents entitlements are b 1 = 0.4, b 2 = 0.6. The allocation where agent 1 receives item a while agent 2 receives both b and c, with prices p a = 0.4, p b = p c = 0.3, is a CE, and thus competitive equilibria exist. Moreover, in every CE, agent 2 receives at least as many items as agent 1 (since she has a larger budget), and thus, she must receive two items, as all items must be allocated in a CE. Thus, in every CE of this instance, agent 1 receives a value of 1 3 . However, in this instance the TPS of every agent is the same as her proportional share (and the same as the entitlement). So T P S(b 1 , v 1 , M) = 0.4 > 1 3 , and agent 1 gets less than her TPS in every CE. Babaioff et al. [2021] observe that even for equal entitlements, it is not possible to give every agent more than half her TPS. More precisely, for any constant ρ larger than half, there is an instance (with equal entitlements) in which some agent does not get ρ-fraction of her TPS.
Observation B.4 For every n, there exists an instance with n agents with equal entitlements and identical valuations, such that in every allocation at least one agent gets at most n 2n−1fraction of her TPS.
Proof. Consider an instance with n agents and 2n − 1 identical items, each of value 1 2n−1 for all agents. The TPS of every agent is 1 n , while in every allocation there is at least one agent that receives only one item, so her value is at most 1 2n−1 ≤ n 2n−1 · 1 n , as desired.

C Missing Proofs from Section 3
Proposition 3.2 The two shares defined in Definition 3.1 and Definition 1.1 are equivalent.
Proof. Let z D (resp., z P ) be the value according to Definition 1.1 (resp., Definition 3.1). We first prove that z D ≥ z P . Let p be the corresponding minimal prices with respect to z D . Assume towards contradiction z P > z D . By Definition 3.1, there exists a distribution F over sets T 1 , . . . , T k , with weights λ 1 , . . . , λ k (i.e., the probability of T r according to F is λ r ) such that r λ r = 1 and for all r, v i (T r ) ≥ z P > z D , such that for every item j ∈ M, r:j∈Tr λ r ≤ b i . It holds that where p(T ) is the price of bundle T according to p. Thus, there must be a set T r in the support of F that is priced at most b i and has a value strictly greater than z D , which leads to a contradiction. To see the other direction, assume that z D > z P and fix z satisfying z D > z > z P . Consider the following LP over the variables {λ T | T ∈ G i (z)}: Maximize T ∈G i (z) λ T subject to: • λ T ≥ 0 for all T ∈ G i (z).
Note that since z > z P , the solution for this LP is strictly less than 1. The dual of this LP is over the variables {q j } j∈M : Minimize b i · j∈M q j subject to: • j∈T q j ≥ 1 for all T ∈ G i (z).
• q j ≥ 0 for all j ∈ M.
By LP duality we get that the minimum is also strictly less than 1. By replacing p j = q j · b i we get: Minimize min j∈M p j subject to: This means that the minimum of the last LP is also strictly less than 1. Thus, if we consider the prices p j + ǫ for small enough ǫ for p j that minimizes this LP, it holds that j (p j + ǫ) ≤ 1, and every (non empty) bundle of value at least z (which is strictly more than 0), is priced strictly more than b i . Thus we get that z D must be smaller than z, a contradiction. Proof. As shown in the proof of Proposition 3.2, for the AnyPrice share z, it holds that the LP over the variables {λ T | T ∈ G i (z)} Maximize max T ∈G i (z) λ T subject to: has solution of at least 1 (since z is feasible). There are only m constraints (other than positivity constraints), thus there is a solution where at most m variables are not zero. Proof. By Definition 2.3, we need to prove that the AnyP rice(b i ) ≥ ℓ-out-of-d-Share holds for every integers ℓ, d satisfying ℓ d ≤ b i . Let A = (A 1 , . . . , A q ) be the partition of M to d bundles with respect to Definition 2.2. For every vector of prices p that sums up to 1, the expected price of a union of ℓ different bundles among A, picked uniformly over all d ℓ unions, is exactly ℓ d . This holds as every item is picked with probability ℓ d (as it belongs to one set, and ℓ sets are picked out of d). Recall that ℓ d ≤ b i . Thus, there are ℓ different bundles that their sum of prices is at most b i and thus can be purchased. By Definition 2.2, the value of their union is at least the value of the ℓ-out-of-d-Share.
Proposition 3.7 For any additive valuation v i over a set of items M, and any entitlement b i it holds that Moreover, for each of the above inequalities there is a setting in which it holds as equality. Finally, even for the case of equal entitlements (b i = 1 k for an integer k), in which the pessimistic share is equal to the MMS, for each inequality above there is a setting in which it holds as a strict inequality. Proof. The inequality P roportional(b i ) ≥ AnyP rice(b i ) follows by setting the price vector to be M) . Then, the price of a bundle is proportional to the value of it, and every affordable bundle has value of at most b i · v i (M). The middle inequality follows by Proposition 3.5. Each of these two inequalities might hold as equality: when there are 2 items each of value 1/2, and b 1 = b 2 = 1/2 then all three shares are 1/2. The rightmost inequality is proven in Lemma C.2, and it can hold as equality by Example 1.2.
We next argue that each of the inequalities might be strict even for equal entitlements (b i = 1 k for some integer k). The leftmost inequality is strict in the case of a single item and b i = 1/2, where the proportional share is b i = 1/2, while the APS is 0. The rightmost inequality is strict in the example for which AnyP rice(b i ) = P essimistic(b i ) presented above (2 identical items, 2 agents with equal entitlements). Finally, Lemma C.1 shows that the middle inequality is sometimes strict, even for agents with equal entitlements (it is much simpler to prove strict inequality for unequal entitlements, e.g., Example 1.2).
Lemma C.1 There exists an additive valuation (over 15 items) such that for b i = 1 3 (corresponding to three agents with equal entitlements) it holds that AnyP rice( 1 3 ) > P essimistic( 1 3 ) = M M S 3 .
It will be convenient to index each item by a pair of different integers in {1, 2, 3, 4, 5, 6}, that is, the set of items is M = {{k, j}|1 ≤ k < j ≤ 6}. We can now write the items in the following six-by-six table (for convenience each value appears twice).
By Definition 3.1, the APS is at least 97: the sets in the support will be the six rows T k = {{j, k} | j = k} for k ∈ [6], each has value of 97. Set λ T k = 1 6 for each row T k , and set λ T = 0 for every other bundle T . Then every bundle T k has value of 97, and every item {j, k} as total weight at most 1/3 as it appears in exactly two sets of positive weight (once in T j and once in T k ): T :{j,k}∈T λ T = λ T k + λ T j = 1 6 + 1 6 = 1 3 ≤ b i as needed. The APS is not more than 97 since it is bounded by the proportional share, which is 97.
In contrast, we next prove that the MMS is strictly less than 97 (it cannot be larger than 97, as the MMS is at most the APS.) Assume towards a contradiction that the MMS is 97. By definition of the MMS, there must exist a partition of M to three bundles P 1 , P 2 , P 3 , each with value of exactly 97. To complete the proof we show that such a partition does not exist, deriving a contradiction.
W.l.o.g., we assume that the item of value 65 is in P 1 . The only two ways to complete P 1 to have a value of exactly 97 is by adding the items with values 5, 5, 5, 17 or adding the items with values 7, 7, 7, 11. This is since if we add an item with value 31, then we get a value of 96 and the is no item with value 1. If we add an item of value 23 then we get value of 88, and there is no subset of items worth 9. In order to add a value of 32, one must use on of the 11, 17 valued items, since otherwise, the maximal value that can be achieved is 36, and the second maximal value is 31. If the 11 value is added, then the only way to achieve an additional value of 21 is by adding the three 7 valued items, and if the 17 value is added, then the only way to achieve an additional value of 15 is by adding the three 5 valued items.
W.l.o.g., we assume that at least two items of value 31 (among the remaining three) are in P 2 . It cannot be that the third 31 value is also in P 2 , since otherwise we have accumulated a value of 93 and cannot be completed to exactly 97. It must be that at least one of the 23 valued items is in P 2 , since otherwise the value of P 3 is at least 3 · 23 + 31 = 100 > 97. It must be that at most one of the 23 valued items is in P 2 since otherwise the value of P 2 is at least 2 · 31 + 2 · 23 = 108 > 97. In order to complete P 2 to have a value of 97, we need to add items with total value of 12, and the only way to do so, is by adding on item of value 5, and one item of value 7. But it must be that either all three items of value 5 are in P 1 , or all three items of value 7 are in P 1 , thus P 2 cannot be completed to have a value of 97. Thus there is no such partition, and the MMS is smaller than 97 (and as it is an integer, it is at most 96).

Lemma C.2 For any additive valuation v i and any entitlement
Proof. Let z be the value of the AnyP rice(b i ) share. Then there is a collection S 1 , . . . , S t of bundles and positive coefficients λ 1 , . . . λ t satisfying {ℓ≤t} λ ℓ = 1, v(S ℓ ) ≥ z for every bundle S ℓ , and ℓ|j∈S ℓ λ ℓ ≤ b i for every item j. Let k be the smallest integer satisfying b i ≥ 1 k . We need to show that one can partition all items into k disjoint bundles T 1 , . . . , T k such that v(T ℓ ) ≥ z 2 for every T ℓ . To distinguish between the bundles of type S ℓ and those of type T ℓ , we refer to the latter as bins. We shall place items in bins, and close a bin once its value reaches (or exceeds) z 2 .
Call an item large if its value is at least z 2 . We first present an argument that shows that we can assume that there are no large items.
Let h denote the number of large items. Each large item closes a bin by itself. If h ≥ k we are done, and hence we assume that h ≤ k − 1. This leaves us k − h bins to fill. As to the original bundles, discard (change its coefficient λ ℓ to 0) every bundle S ℓ that contains a large item. As the coefficients λ ℓ of bundles that contain an item sum up to at most b i , the sum of coefficients that remain is at least 1 − b i h > 0. (Note that the choice of k satisfies b i < 1 k−1 , and together with h ≤ k − 1, this implies that b i h < 1.) W.l.o.g., assume that the sum of coefficients that remain is exactly 1 − b i h. If h = k − 1 we are also done for the following reason. k − 1 bins are closed by using the h = k − 1 large items. As the sum of coefficients that remain is positive, at least one bundle (say S ℓ ) has a nonzero coefficient. This bundle has no large items, implying that all its items remain. As the sum of their values is at least z, these items suffice in order to close the last remaining bin. In other words, we may choose T k = S ℓ . Given the above, we may assume that h ≤ k − 2.
Scale every coefficient by Renaming k ′ by k and b ′ i by b i , we return to the starting point of the theorem, except that now every item has value below z 2 .
Having concluded that we can assume that no item has value above z 2 , consider first the case that 1 > b i ≥ 1 2 , for which k = 2. Let x be the highest value item. As at least one of the bundles does not contain x, the total value of items is at least z + v i (x) (the bundle not containing x contributes at least z, and x itself contributes v i (x)). Bin T 1 will have value at most z 2 + v i (x) (as its value grows by steps not larger than v i (x), and we stop adding to it the first time the value is at least z/2), and consequently value of at least z 2 remains for bin T 2 , as desired.
Consider now the case that b i < 1 2 , for which k ≥ 3. For j ≥ 1, let u j denote the value of the jth most valuable item. We consider two cases.
• u 2k−2 < z 4 . For 1 ≤ j ≤ k, put u j in bin T j . Thereafter add items to the bins, closing each bin as soon as its value reaches z 2 . Note that at most k − 3 bins can close at a value above 3z 4 (as only 2k − 3 items have value at least z 4 , and every item has value smaller than z 2 ), and no bin can close at value above z (because no single item has value larger or equal to z 2 ). Consequently, even after all but one bin close, the total value left for the last bin is at least (k − 1)z − (k − 3)z − 2 3z 4 ≥ z 2 , as desired.
• u 2k−2 ≥ z 4 . Then we can cover the first k − 1 bins by partitioning the first 2k − 2 items to k − 1 disjoint pairs, and putting a pair in each of these bins. We claim that value above z 2 remains for bin T k . This is because among the original bundles, at least one bundle S i contains at most one of the first 2k − 2 items. (Every item is in at most a b i -weightedfraction of the bundles for b i < 1 k−1 . The expected number of items among the top 2k − 2 items distributed according to λ (i.e., bundle S ℓ w.p. λ ℓ ), is at most (2k − 2) · b i < 2. Thus, there must be a bundle S ℓ that contains at most one element among the top 2k − 2.) This bundle S ℓ has value of at least z − u 1 ≥ z 2 left.

Proof.
For an entitlement of the form b i = 1 n , the pessimistic share is the same as the MMS of n players (i.e., P essimistic( 1 n ) = M M S n ). Then by Proposition 3.7 it holds that AnyP rice( 1 2 ) ≥ P essimistic( 1 2 ) = M M S 2 , and hence the APS is at least as large as the MMS. On the other hand, the MMS of two player is the maximal value of any bundle that has a value of at most v i (M) 2 , and the APS cannot be larger as then it will be larger than the proportional share, contradicting Proposition 3.7.
Remark C.3 Observation 3.8 uses in an essential way the fact that valuations are additive. The following example shows that for b i = 1 2 , the APS and the MMS might be different for submodular valuations. Consider a setting with six items M = {1, 2, 3, 4, 5, 6}, and let A = {{1, 2, 3}, {1, 5, 6}, {2, 4, 6}, {3, 4, 5}}. For every agent i, let v i (S) = 6 if there exists T ∈ A such that T ⊆ S (i.e., S contains a set in A), or if |S| ≥ 4. Let v i (S) = 2 for any set S of size 1. Let v i (S) = 4 for any set S of size 2, and let v i (S) = 5 for any set S of size 3, such that S / ∈ A. This is a submodular valuation since the marginal of every item is in 0, 1, 2, and can only decrease as more items are added. The MMS is at most 5 since there is no partition (S 1 , S 2 ) in which both S 1 , S 2 have value 6 (either contain a set in A, or are of size at least 4). The APS is at least 6 since if we set λ S = 1 4 for every S ∈ A we get that the APS is at least 6, by Definition 3.1.
Subadditive: If we change the value of the non-empty sets that have value less than 6 to be 3, then the function is no longer submodular, but is still subadditive. The APS of the modified function is still 6, whereas the MMS drops to 3.
Observation 3.9 For any setting with two agents with additive valuations (v 1 , v 2 ) and arbitrary entitlements (b 1 , b 2 ) there is an allocation A = (A 1 , A 2 ) that is an APS allocation. That is, for Proof. Let F be the distribution over sets (non-negative weights {λ T } T ⊆M that total to 1), that by Definition 3.1 define AnyP rice (v 1 , b 1 , M), the APS of agent 1 that has valuation v 1 and entitlement b 1 . The expected value for the other agent, agent 2, for the complement of a random set sampled from F is , using the fact that v 2 is additive and as T ⊆M λ T ·v 2 (T ) ≤ b 1 ·v 2 (M), since each item has total weight at most b 1 . As b 2 ·v 2 (M) is the proportional share of agent 2, it is at least her APS according to Proposition 3.7. Thus, for at least one set S in the support of F , agent 2 values the set M \ S at least at her APS. As every set in the support of F gives agent 1 her APS, the allocation A = (S, M \ S) gives each of the two agents her AnyPrice share.
Proposition 3.10 Consider the problem of computing, for any integer additive valuation v i and There is an algorithm that computes the APS in time polynomial in the input size (representation of the valuations and entitlement) and z.
Proof. Under the conditions of the proposition, the AnyPrice share z = AnyP rice(b i , v i , M) is an integer. It suffices to design a polynomial time testing algorithm that given a candidate value for t, tests in time polynomial in t whether z < t. Using such a testing algorithm, the value of z can be found by binary search over values of t (without need to ever test a value of t larger than 2z), invoking the testing algorithm only a polynomial number of times.
For testing a candidate value of t, we use the following linear program. Its variables are p j , the prices for the items.
Minimize j∈M p j subject to the following constraints: • p j ≥ 0 for every item j ∈ M.
If z < t then the optimal value of the LP is strictly smaller than 1. This is because by definition of the AnyPrice share, there is a price vector p with respect to which every bundle of value t has price at least b i + ǫ, for some ǫ > 0. Scaling all prices by b i b i +ǫ gives a feasible solution to the LP, and its value is strictly smaller than 1.
The LP has exponentially many constraints, one for each set S with value v i (S) ≥ t. Nevertheless, it can be solved in pseudo-polynomial time. This is because given a candidate assignment to the p j variables, one can test if there is a violated constraint by solving a knapsack problem over the items M, with b j as the knapsack size, the p j serve as item sizes, and the values v i (j) are the item values. Knapsack can be solved in time pseudo-polynomial in the value of the solution, hence in time pseudo-polynomial in t.

D Missing Proofs from Section 4
Before we prove Theorem 4.3, we first observe the following property regarding the TPS.
Lemma D.1 For every subset of items K ⊂ M, and for every b i ≤ 1 |K|+1 and additive valuation v i over the set of items M, it holds that Proof. It suffices to prove this lemma for K which is a singleton. The proof of the lemma then follows by observing that if The lemma follows by partitioning K into |K| singletons, and iterating over the singletons.
Fix K = {j} and b i ≤ 1 2 . By definition By rearranging, we get that: , which concludes the proof.
A similar result holds for the APS (with a somewhat relaxed constraint on b i ).
Lemma D.2 For every subset of items K ⊂ M, and for every b i < 1 |K| and additive valuations v i over the set of items M, it holds that Proof. Let p be the prices according to Definition 3.1 with respect to items M \ K and entitlement b i 1−|K|·b i . From p we derive prices p ′ for M. For every item j ∈ K the price is p ′ j = b i + ǫ, and for every item j ∈ M \ K the price is p ′ j = p j · (1 − |K| · (b i + ǫ ′ )). The ratio between ǫ and ǫ ′ is chosen so that the sum of prices is 1, and ǫ ′ is chosen to be small enough so that agent i with budget b i and prices p ′ cannot afford any bundle that could not be afforded with budget b i 1−|K|·b i and prices p.
The following lemma presents a strategy for agent i with a budget of b i that she can use in the bidding game to guarantee herself a value of at least 1 2−b i fraction of her TPS. At each round of bidding she should do as follows. If there is one item that suffices by itself to obtain the goal, bid your whole budget. Else, if two items suffice, bid half your budget (and take both items if you win). If at least three items are needed, make a bid proportional to the value of the most valuable remaining item, and pick that item if you win.
Before moving to present the formal strategy, we repeat the notations we use in the proofs (defined in the bidding game). We denote by s (t) i = v i (M (t) ) the sum of values of the remaining items at the beginning of round t, and denote by x the value of the most and second most valued items among M (t) . We use the notation of s i to denote s (1) i = v i (M). Finally, we denote the total remaining budget at the beginning of round t by k is the budget available to agent k at the beginning of round t.
We next show that agent i has a strategy that guarantees her 1 2−b i -fraction of her TPS.

Lemma D.3
The following strategy guarantees agent i with additive valuation function v i and entitlement b i a value of at least 1 2−b i · T P S(b i , v i , M) in the bidding game, regardless of the strategies of the other agents.
i . If the bid wins select item 1 and drop out.
2 . If the bid wins select items 1 and 2 and drop out.

Else bid
If the bid wins select the most preferred item. (Observe that the bid is Proof. We divide the rounds into two stages. The first stage (that may be empty) holds while t) . In this stage the agent bids her whole budget. If she wins, she gets her TPS, and we are done. If she does not win, then Lemma D.1 implies that T P S i with respect to the new instance does not decrease. Moreover, the relative budget of agent i (after some other agent paid for an item and the budgets are scaled back to sum to 1) increases, and so does the term 1 2−b i . Consequently, a guarantee of 1 2−b i · T P S i with respect to the instance at the beginning of the second stage implies at least as good a guarantee with respect to the original instance. Hence we may assume without loss of generality that we start directly in the second stage.
In the beginning of the second stage, we have that We prove by induction on the number of items m that as long as agent i in the game, it holds that The base case is m = 1 (and x i , and the assumption that t) . By rule 3 the agent will bid b (t) i , win the item, and obtain value x i , as desired. We now assume that the inductive hypothesis holds whenever the number of items is at most m, and we prove that it holds also when the number of items is m + 1. The proof breaks into cases depending on which of the two rules (rules 2 and 3) is used in the current round, and on whether the agent won the bid in the current round.
• Rule 3 was invoked, but the agent did not win the bid. As the agent's bid under Rule 3 is , whoever wins the round pays at least the number of items taken in the first round, and note that k ≤ . As each item has value at most x (t) i for our agent, the value left by the next round is at least i , so there is enough value left for the agent to potentially reach a value of We now verify that the invariant where the middle inequality holds because of the invariant As the invariant holds in the second round, we can apply the inductive hypothesis and obtain that the value achieved by the agent is at least i .
• Rule 3 was invoked, and the agent won the bid. We have s i . The invariant holds because: where the second inequality holds because x i and we are done. Given i , we use the fact that Rule 2 was not invoked to infer that i . The invariant holds because: As the inductive hypothesis holds regardless of the value of x (t) i , we can apply the inductive hypothesis and obtain that the value achieved by the agent is at least (the x (t) i term comes from the first round): Verifying the last inequality involves tedious but straightforward algebraic manipulations, multiplying both sides by the denominators, and rearranging. After canceling matching terms the inequality becomes B 2 − 2Bb + b 2 ≥ 0, which of course holds.
• Rule 2 was invoked, and the agent won the bid. In this case the agent selects items 1 and 2 for a value of i and we are done.
• Rule 2 was invoked, but the agent did not win the bid. As the agent's bid under Rule 2 is b (t) i 2 , whoever wins the round pays at least b (t) i 2 per item. Let k denote the number of items taken in the first round, and note that k ≤ . As each item has value at most x (t) i for our agent, and Rule 2 requires that x there is enough value left for the agent to potentially reach a value of (t) holds in the second round because: where the middle inequality holds because k ≤ We can now apply the inductive hypothesis and obtain that the value achieved by the agent is at least The next lemma which is used in Step 3 of the strategy described in Lemma 4.6 shows that in the bidding game, agent i with a budget b i can guarantee a value of at least 3 2 · AnyP rice(b i /2, v i , M).
Lemma 4.7 Agent i with additive valuation v i and entitlement b i has a strategy that guarantees herself a value of at least 3 2 ·AnyP rice( b i 2 , v i , M) in the bidding game that allocates M, regardless of the strategies of the other agents.
Proof. Let z = AnyP rice(b i /2, v i , M). By Definition 3.1 there is a finite list of bundles {B j } and associated nonnegative weights λ j such that: • For every item e we have j|e∈B j λ j ≤ b i 2 .
• v i (B j ) ≥ z for all j.
We may assume that v i (e) ≤ z for all items e, as if there is an item of value above z we can reduce its value to z without affecting the condition above, and any strategy that guarantees 3z 2 with respect to the reduced valuation also guarantees it with respect to the original valuation.
We denote by u (t) i the total value accumulated by the agent up to the beginning of round t. We present a strategy for the agent. Without loss of generality, we assume that whoever wins the item in a given round pays the amount that was bid by our agent in that round (this is the worst case for our agent). The strategy is composed of two stages. For the first stage the strategy has two rules.
s i (and choose one item).

If x
i (and choose one item). Here, if i , we say that the item is underpriced, and if i we say that the item is overpriced.
The first stage ends if one of the following two stopping conditions holds: 1. The agent accumulates a value of 3z 2 (and then we are done).
2. The first round r for which both the following condition holds: in round r − 1 rule 2 was applied, whereas in round r rule 1 applies. In this case in round r, the agent plays according to the second stage.
If the agent wins an overpriced item her accumulated value reaches 3z 2 , and we are done. Hence we may assume that the agent never wins an overpriced item. Making this assumption, it follows that if the adversary never wins underpriced items, then the total value won by the agent is at least 2 · z. This is since the total value of all items is at least s i ≥ 2·z b i , and the other agents hold a 1 − b i fraction of the budget. If the other agents do not win an underpriced item, the value that they win (according to v i ) is at most s i · (1 − b i ), and the value remaining for agent i is at least b i · s i ≥ 2z. Hence it remains to analyze the situations in which the adversary does win underpriced items.
The adversary can win an underpriced item only if in the given round we have that i . This, together with the fact that x (t) i ≤ z for every t, implies that the agent wins at least two items before the adversary wins an underpriced item. Denoting by w 1 the value of the first item won by the agent and by w 2 ≤ w 1 the value of the second item won by the agent, we may assume that w 1 + w 2 < 3z 2 , as otherwise we are done. Hence w 2 < 3z 4 . Moreover, we may assume that w 1 + 2w 2 > 2 · z, as otherwise we cannot reach a round in which u (t) i < 3z 2 and i . In particular, this implies that w 2 > z 2 , and that w 1 + w 2 > 4z 3 . After the agent wins two items, we reach for the first time a round in which b s i might hold. Thereafter, we might have a sequence of rounds in which the adversary wins underpriced items. We refer to this sequence of rounds as the bad sequence. The value of an underpriced item is at most w 2 ≤ 3z 4 , and the amount paid by the adversary is at least b After the end of the bad sequence, if there are items of value at least 3z 2 − w 1 − w 2 , the agent bids its full remaining budget (b (t) i ) on them (by rule 2). If the agent wins any such bid, we are done. Hence we may assume that the adversary wins all such items. This marks the end of the first stage of the agent's bidding strategy, as we have reached the second stopping condition.
Before continuing to the second stage, we show that not all items are exhausted in the first stage. (Later we will address the question of the value of the items that remain.) Proposition D.4 By the end of the first stage, either the agent accumulated a value of at least 3z 2 , or there are still items remaining for the second stage.
Proof. Assume for the sake of contradiction that the agent accumulated a value smaller than 3z 2 , but no items remain. The agent then has a budget of b (r) i > b i 4 remaining. We show that the fact that no items remain implies that the total budget of the adversary and the agent is exhausted, contradicting the fact that the agent's budget is not exhausted.
Recall the bundles {B j } implied to exist by the condition for the APS. For every item e, let p(e) denote the price paid for the item. Charge this price to the bundles that contain e, where if e ∈ B j , bundle B j is charged 2λ j b i p(e). By the condition j|e∈B j λ j ≤ b i 2 , the bundles are not charged more than the total price of the items. Let C j denote the total charge to bundle j. We show that C j ≥ λ j .
For a bundle B j that contains only one item e, we have that v i (e) ≥ z. Such an item cannot be underpriced. Hence p(e) ≥ b i 2 , and C j ≥ 2λ j b i · b 2 2 = λ j . Consider now a bundle B j that contains at least two items, and let e 1 and e 2 be items in B j . Both items must be consumed in the first stage. In the first stage, the agent always bids b (t) i which is at least b i 4 (since all items until w 2 are not underpriced and thus priced at least b i 4 , and between item w 2 and round r, the agent always bids b Hence the total price of all items is at least j C j ≥ j λ j = 1, implying that the total budget (which was 1) is exhausted.
For the items that remain, we change the valuation function of the agent tov i , where for every item e we definev i (e) = min[b Observe thatv i (e) ≥ v i (e) for every item e, because when the first stage ends there is no remaining item with v i (e) > b (r) i · s i (otherwise the agent will still play according to rule 2), and also 3 . We will usex (t) i to denote the corresponding maximal value with respect tov i at time t. In the second stage, the bidder bids "truthfully" with respect tov i .
• In every round t ≥ r, ifx The analysis will show that if in a round it holds thatx We claim that when the second stage begins, the total valueŝ (r) i of all items (according tov i ) is at least B (r) · s i . We postpone the proof of this claim, and first show that the claim implies our lemma. As i · s i , Lemma 4.4 (for t = 1) implies that the agent can guarantee (by following the strategy described in the lemma) a value (according tov i ) of at least i ·s i 2 . Scaling back to values according to v i , this gives at least . Recall that the value accumulated by the agent in the first stage is i ), and hence in the second stage it suffices that the agent accumulates . And indeed, (Dividing by s i then multiplying by the denominator gives (b i , and moving everything to the left hand side and completing a square gives ( √ 5b It remains to prove the claim. Consider the prices and the charging mechanism explained in the proof of Proposition D.4. Let L j ("leftover budget for bundle j") be L (Here e ranges only over items consumed in the first stage.) The total budget left at the end of the first stage can be seen to satisfy Let V j denote the value left in bundle B j at the end of the first stage according to v i , and letV j ≥ V j denote the value after scaling v i tov i . Then the total value according tov i at the beginning of the second stage satisfiesŝ If bundle B j does not contain any underpriced item, then V j ≥ L j ·s i , and we are done. If two or more items are consumed in B j in the first stage then L j = 0 (see proof of Proposition D.4) and again V j ≥ L j · s i = 0. It remains to consider the cases in which exactly one item e ∈ B j was consumed in the first stage, and this item e was underpriced. In this case, p(e) = b (r) i i = L j , so indeed we have thatV j ≥ L j · s i , as desired.

D.1 A Polynomial Time 3 5 -APS Allocation
The fact that the APS is NP-hard to compute in polynomial time might cause a problem for those algorithms that make explicit use of the value of the APS. In our work, there are several such algorithms, one in Theorem 4.3, one in Lemma 4.6 (this lemma is used by Theorem 4.3), and one in Lemma 4.7 (this lemma is used by Lemma 4.6). In this section we show how in these cases the need to compute the value of the APS can be avoided, while still obtaining the guarantees of the underlying algorithms. We assume the value of every item is a non-negative integer, and the entitlement is a rational positive number. These algorithms use a parameter z that they initially set to be equal to the APS. Given z, the algorithms run in polynomial time. Moreover, their guarantees are with respect to z (e.g., giving at least 3 5 z Lemma 4.6), and not with respect to the APS.
One can ask what guarantees do these algorithms give if one initializes z with a value not equal to the APS. Inspecting these algorithms, we see that if z is smaller than the APS, the guarantees with respect to z still hold, but they do not necessarily imply the corresponding guarantee with respect to the APS (as 3 5 z is smaller than 3 5 · AP S). On the other hand, if z is larger than the APS, the guarantees with respect to z need not hold, but if they do hold, they do imply the desired guarantees also with respect to the APS.
In general, we can partition the possible values of z into two classes. The good class contains those z for which the guarantees of the algorithm do hold with respect to z. In particular, all values of z up to and including the APS are good. The bad class contains all values of z for which the guarantees of the algorithm do not hold with respect to z.
Suppose that we had a polynomial time algorithm to determine whether a given value of z is good or bad. Then in polynomial time, we could do a binary search on all values of z up to v i (M), and find a z that is good, and satisfies also that z + 1 is bad. This z is at least as large as the APS, and using it in the respective algorithm provides the desired guarantees also with respect to the APS.
It remains to design a polynomial time algorithm that determines whether a given value of z is good. For the algorithms that concern us here, there are two observations whose combination implies that this can be done.
One observation is that given z, these algorithms present an explicit strategy for the bidding game, and moreover, the guarantee holds regardless of the strategies of other agents in this game. Hence to see if the guarantee holds, it suffices to consider a worst case adversary for the bidding game. This adversary knows v i and z, and pools together the combined budgets of all other agents, as if there is just one other agent. (Here we use the fact that the value of the APS with entitlement b i does not depend on how the remaining entitlement is distributed among the other agents.) The adversary views the bidding game as a zero sum game between himself as one player and agent i as the other player, and the adversary's goal is to bid and select items in a way that would minimize the final value obtained by agent i. As the strategy of agent i is known, the optimal strategy for the adversary is a solution of a well defined optimization problem (there are no game theoretic aspects involved).
Summarizing, the first observation shows that in order to test whether z is good, it suffices to solve a well defined optimization problem. E.g., for Lemma 4.6 this problem is to determine whether the adversary has a strategy that limits the value received by agent i to below 3 5 z. The second observation is that the algorithms of Lemma 4.6 and Lemma 4.7 have the following property. Once agent i wins two items, we know whether the guarantees are met. For Lemma 4.7 this holds because at the time we switch to the second stage of that algorithm, the agent has won two items (denoted to w 1 and w 2 ). As the second stage of the algorithm uses the algorithm of Lemma 4.4, we can at that point check whether the conditions of Lemma 4.4 hold. These conditions can be checked in polynomial time, and they compare the maximum valued item to the proportional share. If the conditions hold, we are sure to succeed. If the conditions do not hold, z was bad (too large). As for Lemma 4.6, its first steps either win one or two items and give a value of 3 5 , or win no item and instead call Lemma 4.7. Hence again, after the agent wins two items (in the algorithm of Lemma 4.7), we can tell whether the value of z is good or bad.
Given the second observation, it is easy to solve the optimization problem of the adversary, as there are at most m 2 adversarial strategies that we need to try. In each such strategy, we order the items in descending order of value according to v i , and fix two items that agent i is supposed to win, say items k and ℓ in this order. In the first k − 1 rounds the adversary wins all items and pays the bids of agent i, thereafter agent i wins item k and pays her bid, thereafter the adversary wins the items up to ℓ − 1 and pays the bids of agent i, and then agent i wins item ℓ and pays her bid. If at least one of these strategies is feasible for the adversary (the adversary can afford all its payments using its budget) and certifies that z is bad, then z is indeed larger than the APS. Else, z is good.
Hence using the second observation we have a polynomial time algorithm that tests whether a given value of z is good or bad. As explained above, this shows that the guarantee of 3 5 · AP S can be achieved in polynomial time, even without knowing the exact value of the APS. Likewise, one can decide in the algorithm of Theorem 4.3 which of the three strategies offers the highest of the three guarantees, even without knowing the value of the APS.

E Missing Proofs from Section 5
Here we present the definition of the Greedy-EFX algorithm.
Greedy-EFX [Lipton et al., 2004, Barman andKrishnamurthy, 2020]  Give item e t to an agent that no one envies, breaking ties arbitrarily 4: while There exists an envy cycle do

5:
Resolve an (arbitrary) envy cycle by rotating sets along the cycle 6: end while 7: end for Theorem 5.2 ( [Bouveret and Lemaître, 2016]) For every instance with additive valuations, every allocation for its ordered version can be transformed in polynomial time to an allocation for the original instance. Using this transformation, every agent derives at least as high value in the original instance as derived by the allocation for the ordered instance.

Proof.[Sketch]
A choosing sequence is a sequence on names of agents (repetitions are allowed). Starting with the beginning of the choosing sequence, in each round the agent whose name appears in the choosing sequence selects an item of her choice. The allocation A for the ordered instance naturally induces a choosing sequence, where for every round r, the agent to choose in round r is the one to which A allocated the rth most valuable item in the ordered instance. Using this choosing sequence (and the pigeon-hole principle), in every round, every agent can choose an item that she values at least as much as the corresponding item that she got under A.
Lemma 5.3 When n agents have additive valuations and equal entitlements, the greedy-EFX allocation gives every agent at least the minimum of the following two values: a 3 4 fraction of her APS, or a 2n 3n−1 fraction of her TPS.
Proof. Observe that under greedy-EFX, every agent q gets at least her nth most preferred item. Hence if her TPS is nonzero (which can only happen if there are at least n items of positive value for q), then the allocation gives the agent positive value. Consider an arbitrary agent q, who gets bundle B q , and let v q be her valuation function. We may assume without loss of generality that v q (B q ) > 0, because if v q (B q ) = 0 the TPS (and APS) of agent q is 0. To simplify subsequent notation, we scale the valuation function of q by a multiplicative factor, so that that v q (B q ) = 1. Consequently, in order to prove Lemma 5.3, we need to either show that AP S q ≤ 4 3 , or to show that T P S q ≤ 3n−1 2n . We shall use the following properties of greedy-EFX. (Values in these properties are taken with respect to v q , and inequalities implicit in these properties need not be strict.) 1. Within a bundle, the items enter the bundle in order of decreasing value.
2. If i < j and B i and B j each contain at least two items, then the first item in B i is more valuable than the first item in B j , and the second item in B i is less valuable than the second item in B j .
3. Removing the last item of any bundle, the value that remains in the bundle is at most v q (B q ) = 1. (This is the EFX property.) Let k 1 denote the highest index of a bundle that contains only one item (with k 1 = 0 if there is no such bundle).
Claim E.1 If in the allocation produced by greedy-EFX every bundle contains at most two items, then AP S q ≤ 1.
Proof. Observe that every bundle up to B k 1 contains one item, and each of the remaining bundles (if k 1 < n) contains two items. Fix ǫ < 1 4n 2 . There are two cases to consider. If q ≤ k 1 (in which case q receives only one item, e q ), we upper bound AP S q by considering the following price function p for the items. For i ≤ k 1 we have p(e i ) = 1 n + ǫ, with the exception that p(e q ) = 1 n − 2nǫ. For i > k 1 we have p(e i ) = 1 2n + ǫ. The total price of all items is less than 1, because the price of every bundle is at most 1 n + 2ǫ, except for bundle B q that has price 1 n − 2nǫ. Agent q who has budget 1 n can afford to buy only a single item, as the sum of prices of any two items exceeds 1 n . Among the items priced at most 1 n , the most valuable item is e q , and we assumed that v q (e q ) = 1. Hence AP S q ≤ 1.
If q > k 1 (in which case q receives two items, e q and e 2n−q+1 ), we consider the following price function p. For i ≤ k 1 we have p(e i ) = 1 n + ǫ. For k 1 < i < q we have p(e i ) = 2 3n + ǫ. For q ≤ i ≤ 2n − q we have p(e i ) = 1 2n + ǫ. For i ≥ 2n − q + 1 we have p(e i ) = 1 3n + ǫ. The total price of all items is less than 1, because the price of every bundle is at most 1 n + 2ǫ, except for bundle B q that has price 5 6n + 2ǫ. Agent q can afford to buy either a single item among e k 1 +1 , . . . , e q−1 , or two items: one among e q . . . , e m , and the other among e 2n−q+1 , . . . , e m . When buying two items, the most valuable two are e q and e 2n−q+1 , because the instance is ordered. These are precisely the items in bundle B q . The value of every item among e k 1 +1 , . . . , e q−1 is at most 1, by property 3 above. Hence q can afford to buy a bundle of value at most 1, implying that AP S q ≤ 1.
It remains to handle the case that some bundle has at least three items. Let k be the largest index of a bundle that has more than two items. The first item added to B k was e k , the second item was e 2n−k+1 , and B k has at least one more item. We shall refer to all items from e 2n−k+1 onwards as small. Note that v q (e k ) + v q (e 2n−k+1 ) ≤ 1, because otherwise B k would not get a third item. The fact that the instance is ordered then implies that small items have value at most min[ 1 2 , 1 − v q (e k )]. We now perform a case analysis over the possible values of v q (e k ).
Proof. Suppose first that every bundle (except possibly for B q ) has at least two items. Then the inequality v q (e k ) ≤ 3 4 , together with the fact that small items have value at most 1 2 , implies Every small item has value at most 1 − v q (e k ), and under the conditions of the claim this value is strictly smaller than 1 4 . Every bundle up to k 1 has price 1. Every bundle in the range [k 1 + 1, k] contains one item e of value v q (e) ≥ v q (e k ) > 3 4 , and either one small item (of value strictly less than 1 4 ), or several small items of total value at most 2(1 − v q (e)). In either case, p(e i ) = max[ 1 2 , v q (e i ) − 1 3 ] implies that the price of the bundle is strictly smaller than 1. Every bundle from k + 1 onwards has two items, none of which has value above 5 6 , and hence the price of the bundle is at most 1. Agent q can afford at most one item among e k 1 +1 , . . . , e 2n−k , and hence can buy at most one item at a price below its value. As q's budget is less than 1, and the gain of value compared to price paid is at most 1 3 , she obtains value less than 4 3 . Hence AP S q < 4 3 .
The four claims above complete the proof of Lemma 5.3.
Recall that in every round, the greedy-EFX allocation algorithm gives an item to an agent that has a bundle that no one envies. If there are several such agents, it may select one of them arbitrarily. Depending on the arbitration rule, we get different versions of greedy-EFX. The positive results of Lemma 5.3 hold for all such versions. The negative results of the following Proposition 5.5 are proved with respect to one such natural version. The key assumption of our version is that the first item goes to agent 1. (For convenience we also assume that if in a certain round the arbitration rule preferred an agent i over an agent j, then in the next round in which both i and j are eligible candidates to receive an item, agent j is preferred over agent i. However, this last assumption can be removed by slightly perturbing the values of items in the example. Details of how to perform these perturbations are omitted.) Proposition 5.5 For every ǫ > 0, there is an instance with additive valuations and equal entitlements in which the greedy-EFX algorithm does not provide some agent more than a 2 3 + ǫ of her MMS (and thus also does not provide more than a 2 3 + ǫ of her APS).
We next claim that if the first item that the greedy-EFX algorithm allocates is assigned to agent 1, then agent 1 gets the three items of group 0, with values 1, 0 and 0. When agent 1 receives the first item (the large item of group 0), then each other agent receives a single large item (as they value all large items by at least half, while all small items by less than half). After the allocation of the large items, the greedy-EFX allocates the small items in decreasing order of the groups. Each agent that received a large item of group i also receives two small items of the same group. Thus, agent 1 won't get another item until all items but the small items of group 0 are allocated.
While the greedy-EFX algorithm gives agent 1 value of 1, we next show that the MMS of agent 1 is at least 3 2 − ǫ. This holds since the agent can partition the items to n bundles, each with value at least 3 2 − ǫ, in the following way: For each a ∈ {1, 2, . . . , k}, the agent creates 2 · 4 a−1 bundles by taking two large items of group a and one small item of group a − 1. The value of such bundle is 2(1 − a 2k ) + a−1 2k = 2 − a+1 2k ≥ 3 2 − ǫ. The agent also creates 2·4 k −2 3 bundles, each containing three small items of group k, and each such bundle has a value of 3 2 . Note that 2 · 4 k − 2 is divisible by 3. The agent also creates another bundle using the two remaining small Proof. Let z be a value for which the LP of Definition F.1 is feasible. Then z is the smallest value of a bundle in the support of the underlying distribution, whereas the proportional value is the average value (due to additivity).
If all items are chores (even without assuming additivity), then the value of every non-empty bundle is negative. It is convenient to view the absolute values of these negative values as positive disutilities. Thus we replace the non-positive valuation function v i by the non-negative disutility function c i , where for every S ⊆ M we have c i (S) = −v i (S). With respect to disutilities, the APS is positive, and the agents wish to receive bundles of small disutility. There are allocation instances in which every allocation gives some agent a bundle of disutility larger than her APS. (This follows from a similar result concerning MMS for chores and agents with equal entitlements [Aziz, Rauchecker, Schryen, and Walsh, 2017], because with equal entitlements, the APS disutility is never larger than the MMS disutility.) Consequently, we wish to find allocations that give every agent a bundle of disutility no more than ρ times her APS, with ρ being as small as possible. For ρ = 2, this can be achieved for additive valuations, using standard approaches.
Proposition F.6 Consider an allocation instance with n agents with valuations (v 1 , v 2 , . . . , v n ) and arbitrary entitlements (b 1 , b 2 , . . . , b n ) for a set M of indivisible chores. If all disutility functions are additive, then there is an allocation in which every agent i gets a bundle of disutility at most 2 · AnyP rice(b i , v i , M).
Proof. Consider a fractional allocation in which every agent i (with entitlement b i ) gets a fraction b i of every item j. This fractional allocation gives every agent her proportional share. It is well known that every fractional allocation can be rounded to give an integral allocation in which every agent gets a bundle whose disutility is the same as the disutility of her original fractional bundle, up to the disutility of one item [Lenstra, Shmoys, and Tardos, 1990]. As her fractional disutility is at most her APS disutility(Proposition F.5, after transforming values to disutilities) and every item has value at most the APS (Proposition F.4, after transforming values to disutilities), the proposition follows.
For completeness, we present the price based definition of the APS for chores (in analogy to Definition 1.1 for goods). The price based definition is derived by considering the dual of the fractional MMS definition. We have shown the equivalence of the two definitions for the case of goods in Proposition 3.2. Similar arguments (which are omitted) show the equivalence in the case of chores.
Definition F.7 Consider a setting in which agent i with disutility function c i has entitlement b i to a set of indivisible chores M. The AnyPrice share (APS) of agent i, denoted by AnyP rice(b i , c i , M), is the disutility she can limit herself to whenever the chores in M are adversarially priced with a total price of 1, and she picks her bundle of chores among those bundles of total price at least b i : Observe that both in Definition 1.1 (for goods) and in Definition F.7 (for chores), all prices are non-negative. The difference between the definitions is that for the case of goods, the feasible bundles for an agent i are those priced at most b i , whereas for chores the feasible bundles are those priced at least b i . We note that the APS in Definition F.7 measures dis-utility, and thus has a positive value which equals to minus the value of Definition F.1.
For allocation instances that involve a mixture of goods and chores, there are instances in which agents have additive valuations, equal entitlements, the MMS of every agent is strictly positive, whereas in every allocation (that allocates all items) some agent receives a bundle of value at most 0 [Kulkarni, Mehta, and Taki, 2020]. As the APS is at least as large as the MMS, it follows that for mixed manna it is not always possible to find an allocation that gives every agent a positive fraction of her APS.