Fair-Share Allocations for Agents with Arbitrary Entitlements

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 $\sum_{i}b_{i}=1$) and she buys her highest value affordable set when items are adversarially priced with a total price of $1$. Let ${\cal{P}}=\{(p_{1},p_{2},\ldots,p_{m})|p_{j}\geq 0\ \forall j\in{\cal{M}},\ \ \sum_{j\in{\cal{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:

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.

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 $\frac{3}{5}$ fraction of her AnyPrice share, and moreover, at least $\frac{1}{2-b_{i}}$ fraction of the APS (which is more than $\frac{3}{5}$ if her entitlement is larger than $1/3$). Note that the fraction $\frac{1}{2-b_{i}}$ goes to $1$ as $b_{i}$ grows to $1$.

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\{\frac{3}{5},\frac{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\{\frac{3}{5},\frac{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 $\frac{2}{3}$ fraction of her APS (which is better than the $\frac{3}{5}$ fraction that we get for the arbitrary entitlements case).

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.

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(\frac{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 $\frac{3}{4}+\Omega(\frac{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).

We present two definitions of $AnyPrice(b_{i},v_{i},{\cal{M}})$, the AnyPrice share (APS) of an agent $i$ that has valuation $v_{i}$ and entitlement $b_{i}$ (when $\sum_{i}b_{i}=1$) to items ${\cal{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 ${\cal{P}}=\{(p_{1},p_{2},\ldots,p_{m})|p_{j}\geq 0\ \forall j\in{\cal{M}},\ \ \sum_{j\in{\cal{M}}}p_{j}=1\}$ be the set of item-price vectors that total to $1$. We restate the price-based definition of APS: See 1.1

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).

An equivalent set of constraints that will sometimes be convenient to use is the following. Let ${{\cal{G}}_{i}(z)}$ be the family of sets $T\subseteq{\cal{M}}$ such that $v_{i}(T)\geq z$. The set of constraints now becomes $\sum_{T\in{{\cal{G}}_{i}(z)}}\lambda_{T}=1$, $\lambda_{T}\geq 0\ \forall{T\in{{\cal{G}}_{i}(z)}}$, and $\sum_{T\in{{\cal{G}}_{i}(z)}:j\in T}\lambda_{T}\leq b_{i}\ \forall j\in{\cal{M}}$. 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}=\frac{1}{n}$) by restricting every weight $\lambda_{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 $\lambda_{T}\in\{0,b_{i}\}$ for non-empty sets (which can be thought of as an integer constraint of the form $\lambda_{T}\in\{0,1\}\cdot b_{i}$) to the fractional constraint $0\leq\lambda_{T}\leq 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.

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⁵⁵5For a formal definition of CE see Appendix A. 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.

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 follows from the fact that for $b_{i}=\frac{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.

We next focus on additive valuations. We start by relating the different notions of shares to each other.

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}=\frac{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}=\frac{1}{2}$).

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.

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.⁸⁸8This implies the APS computation problem has a fully polynomial time approximation scheme (FPTAS), while the MMS does not. Note that the MMS problem does have a polynomial time approximation scheme (PTAS) ((Woeginger, 1997)). 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}({\cal{M}})$), which is pseudo-polynomial⁹⁹9Note that a polynomial algorithm would run in time polynomial in $\log z$, not polynomial in $z$.. 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.

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 ${\cal{M}}$, the truncated proportional share of agent $i$ with additive valuation function $v_{i}$ is the largest value $t$ such that $\frac{1}{n}\sum_{j\in{\cal{M}}}\min[v_{j},t]=t$. We extend this definition to the case of arbitrary entitlements in a natural way, by thinking of $\frac{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:

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.

If $v_{i}({\cal{M}}\setminus K)=0$ then if we price all items in $K$ by $\frac{1}{k}$, the agent cannot afford any item she has positive value for ($v_{i}({\cal{M}}\setminus K)=0$ and since $b_{i}<\frac{1}{k}$ she cannot get any item in $K$), and thus $AnyPrice(b_{i},v_{i},{\cal{M}})=0\leq TPS(b_{i},v_{i},{\cal{M}})$.

Else, we have $v_{i}({\cal{M}}\setminus K)>0$. Assume towards contradiction that the value $z^{*}=AnyPrice(b_{i},v_{i},{\cal{M}})$ is strictly more than $w$. Thus, there exists an $\epsilon>0$ such that

Such an $\epsilon>0$ must exist since when $\epsilon\to 0$ then this expression goes to $w$, while when $\epsilon\to\frac{1}{k}-b_{i}$, the expression goes to infinity, and it is continuous in $\epsilon$ for $\epsilon\in(0,\frac{1}{k}-b_{i})$. Consider the pricing $b_{i}+\epsilon$ for every item in $K$, and for every item $j\in{\cal{M}}\setminus K$, we give a price $p_{j}=\frac{v_{i}(j)\cdot(1-k(b_{i}+\epsilon))}{v_{i}({\cal{M}}\setminus K)}$. 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 $\frac{b_{i}}{1-k(b_{i}+\epsilon)}\cdot v_{i}({\cal{M}}\setminus K)$, which is strictly smaller than $z^{*}$, contradicting the definition of $z^{*}$ as her APS. $\blacksquare$

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 $\frac{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 $\frac{3}{5}$ fraction of her APS.

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 $\frac{3}{5}$ fraction of her AnyPrice share, and at least $\frac{1}{2-b_{i}}$ fraction of her Truncated Proportional Share (which is at least her APS). This $\frac{1}{2-b_{i}}$ fraction is more than $\frac{3}{5}$ if the agent entitlement is larger than $\frac{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 $\lfloor 1/b_{i}\rfloor$ 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_{i}^{(t)}$ between $0$ and $b_{i}^{(t)}$. 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_{w^{(t)}}^{(t)}$, agent $w^{(t)}$ selects available items she wants to take, paying $r_{w^{(t)}}^{(t)}$ for each item she takes.

Before moving to the proof, we remark that for the case of equal entitlements ($b_{i}=1/n$ for every $i$), the approximation of $\frac{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 $\frac{1}{2n-1}$. One of the $n$ agents must get at most one item, getting a value of only $\frac{1}{2n-1}$ while her TPS is $\frac{1}{n}$ (identical to her proportional share as no item has value larger than her proportional share). Thus, that agent gets only $\frac{n}{2n-1}$ fraction of her TPS, which equals a $\frac{1}{2-b_{i}}$ fraction of her TPS, as $b_{i}=1/n$. Note that $\frac{n}{2n-1}$ approaches $\frac{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 $\frac{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_{i}^{(t)}$, and the highest value remaining item has value $x_{i}^{(t)}$, then at round $t$ agent $i$ bids $\min\left(\frac{x_{i}^{(t)}}{v_{i}({\cal{M}})},b_{i}^{(t)}\right)$ 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.

Let $t^{*}$ be the latest round such that for every round up to and including $t^{*}$, agent $i$ bids her max value. That is, $\frac{x_{i}^{(t)}}{s_{i}}\leq b_{i}^{(t)}$ for every $t\leq t^{*}$. Let $u_{i}^{(t^{*}+1)}$ denote the total value accumulated by agent $i$ up to the beginning of round $t^{*}+1$.

Observe that $\frac{u_{i}^{(t^{*}+1)}}{s_{i}}=b_{i}-b_{i}^{(t^{*}+1)}$, as up to (and including) round $t^{*}$ agent $i$ always bids exactly her max value, and hence $u_{i}^{(t^{*}+1)}=s_{i}\cdot(b_{i}-b_{i}^{(t^{*}+1)})$. Thus the value accumulated by agent $i$ by the end of the bidding game is at least $\left(b_{i}-b_{i}^{(t^{*}+1)}\right)\cdot v_{i}({\cal{M}})$. Hence if $b_{i}^{(t^{*}+1)}\leq\frac{b_{i}}{k+1}$, the Lemma is proved.

It remains to consider the case that $b_{i}^{(t^{*}+1)}>\frac{b_{i}}{k+1}>0$. We claim that in this case $s_{i}^{(t^{*}+1)}>0$. The claim follows from the following argument. In every round $t\leq t^{*}$ agent $i$ bids her max value $\frac{x_{i}^{(t)}}{s_{i}}$. Hence in every round $t\leq t^{*}$, regardless of which agent won the round, the payment per item consumed in round $t$ was at least $\frac{x_{i}^{(t)}}{s_{i}}$, whereas every item consumed in round $t$ had value at most $x_{i}^{(t)}$ (according to $v_{i}$). As the initial total budget is 1, and $B^{(t^{*}+1)}\geq b_{i}^{(t^{*}+1)}>0$, the total budget consumed up to and including round $t^{*}$, namely, $1-B^{(t^{*}+1)}$, satisfies $1-B^{(t^{*}+1)}<1$. Hence the total value (according to $v_{i}$) consumed is at most $(1-B^{(t^{*}+1)})s_{i}<s_{i}$, implying that $s_{i}^{(t^{*}+1)}>0$, as claimed.

By the maximality of $t^{*}$, in round $t^{*}+1$ agent $i$ bids her budget. This implies that $b_{i}^{(t^{*}+1)}<\frac{x_{i}^{(t^{*}+1)}}{s_{i}}$.

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 $v_{i}(F_{i})+x_{i}^{(t^{*}+1)}\leq b_{i}\cdot v_{i}({\cal{M}})=b_{i}\cdot s_{i}$. Thus, it holds that $\frac{x_{i}^{(t^{*}+1)}}{s_{i}}\leq b_{i}^{(t^{*}+1)}$, 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 $|F_{i}|\geq k$. Since $b_{i}^{(t^{*}+1)}<\frac{x_{i}^{(t^{*}+1)}}{s_{i}}$ and since $b_{i}^{(t^{*}+1)}=b_{i}-\frac{v_{i}(F_{i})}{s_{i}}$, it holds that $v_{i}(F_{i})+x_{i}^{(t^{*}+1)}>b_{i}\cdot s_{i}$. Hence,

where the first inequality holds since every item in $F_{i}$ has a value of at least $x_{i}^{(t^{*}+1)}$ and thus $v_{i}(F_{i})\geq|F_{i}|\cdot x_{i}^{(t^{*}+1)}$. The second inequality holds since $|F_{i}|\geq k$ and $v_{i}(F_{i})+x_{i}^{(t^{*}+1)}>b_{i}\cdot s_{i}$. This concludes the proof. $\blacksquare$

An immediate corollary of Lemma 4.4 (for $k=1$) is that the bid-your-max-value strategy gives the agent half her TPS.

While the analysis of the strategy that gives a $\frac{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.