# Worst-case fair guarantees when spending a common budget

Pierre Cardi, Laurent Gourvès, Julien Lesca

► To cite this version:

Pierre Cardi, Laurent Gourvès, Julien Lesca. Worst-case fair guarantees when spending a common budget. Theoretical Computer Science, 2025, 1046, pp.115322. 10.1016/J.TCS.2025.115322. hal-05232490

HAL Id: hal-05232490

https://hal.science/hal-05232490v1

Submitted on 1 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Worst-case Fair Guarantees when Spending a Common Budget*

Pierre Cardi¹

Laurent Gourvès¹†

Julien Lesca¹

1. Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, 75016, Paris, France

pierrecardi2@gmail.com, laurent.gourves@dauphine.fr, julien.lesca@dauphine.fr

## Abstract

We study the problem of fairly spending a budget that is common to $n$ agents. Agents submit demands to a central planner who uses the budget to fund a subset of them. The utility of an agent is the part of the budget spent on her own accepted demands. In a fair solution, the successful demands of each agent would represent a $1/n$ fraction of the budget. However, this is rarely possible because every demand is indivisible, i.e., either accepted in its entirety or rejected. We are interested in worst-case bounds on the largest proportion of the budget that is dedicated to the least funded agent. Our approach is not to solve the corresponding max-min problem for every instance, but to tackle the problem from a higher level. The size of the largest demand compared to the budget and the number of agents, are two parameters that significantly influence how much the worst-off agent gets. We propose explicit worst-case bounds on the best utility of the least funded agent for the class of instances where the number of agents and the most expensive demand are fixed to given values. A characterization of this quantity is provided for 1 and 2 agents. For more than 2 agents, we propose lower and upper bounds that constitute a $\frac{14}{15}$-approximation of the optimal value. Every existence result is complemented with a polynomial time algorithm that builds a feasible solution satisfying our bounds.

**Keywords:** Computational social choice, Fairness, Worst-case guarantees, Subset sum problem

## 1 Introduction

We study the problem of fairly spending a budget that is common to $n$ agents. Agents have demands which correspond to indivisible portions of the budget. A solution is to accept a selection of demands which fits within the budget. The setting is versatile enough to capture many situations where people must share a limited resource such as money, time, or space. The problem occurs when, for example, there is a server with a given memory capacity and its users want to store some of their files (see for example [21] for a similar problem). More generally, this example can be applied to the management of a cloud computing system with several competing clients. Another application is when an organization has a given amount of money to be spent for funding the projects (or any kind of expense) of its members (see [28] for an example where the agents are the countries composing the European Union). A final example can be the allocation of the annual carbon budget of a company: demands correspond to the greenhouse gas emissions of the possible activities of different services of the company.

In all these applications, we would like to use the budget in a way that is fair to the agents, knowing that any agent only considers the part of the budget devoted to her. In addition, the indivisible nature of the demands corresponds to situations where an activity cannot be carried out fractionally, and this is an additional source of difficulty in finding a feasible solution.

Let us illustrate our model with a small numerical example. There are two agents named Alice and Bob whose demand sets are {29, 25, 20} and {19, 17, 16}, respectively. The common budget is 100. Several feasible solutions exist, one of them consists of spending 85 by accepting {29, 20} from Alice's set and {19, 17} from Bob's set. Here, it is assumed that every agent's utility is the part of the budget spent on her own accepted demands. One objective is to find a fair solution and *proportionality* is a well accepted notion of fairness [40]. In a proportional solution,

<footnote>*A preliminary version of this work appears in the proceedings of AAMAS 2021 [13].</footnote>

<footnote>†Corresponding author</footnote>
the successful demands of each agent represent a $1/n$ fraction of the budget. However, being proportional is rarely possible with indivisible objects. In the previous example, Alice and Bob have utility 49 and 36, respectively, but no feasible solution gives 50 to both agents.

When proportionality is not achievable, we can strive to be as close as possible to it by maximizing the utility of the worst-off agent. This problem, called the *max-min problem* thereafter, is computationally difficult. A second approach is to meet each agent's *Maximin share* (MMS) [11], defined as the maximum utility that she can obtain by partitioning the items into $n$ parts and taking the part with the minimum utility. Unfortunately, there exist instances with three agents which do not admit any solution guaranteeing MMS for every agent [29]. A third approach is the one proposed by Ted Hill who proposed explicit worst-case bounds on the agents' utilities, not for single instances, but for *classes* of instances [26]. A class is characterized by its number of agents and the fact that every item is valued at most a given parameter. The intuition is that the smaller the parameter, the closer we can get to $1/n$ (i.e., proportionality).

Our approach for the problem of fairly allocating a common budget is neither to solve the corresponding max-min problem for every instance,<fnref n="1" /> nor to meet the agents’ MMS bounds, but to tackle the problem from a higher level as Hill did for the fair allocation of indivisible goods [26]. We are interested in explicit worst-case bounds on the largest proportion of the budget that can be dedicated to the least funded agent. These bounds are based on two parameters: the number $n$ of agents and the proportion $\alpha$ of the largest demand compared with the budget. Our primary objective is to quantify how close to proportionality one can be in the class of instances with parameters $n$ and $\alpha$, and where the sum of the demands of every agent exceeds the budget divided by $n$. Note that if the total sum of demands of an agent can be arbitrarily small compared to the common budget, then only the trivial lower bound of zero on the minimum utility can be derived. That is why we make the necessary assumption that the total sum of demands of every agent is not below the guarantee of proportionality, namely a $1/n$-fraction of the common budget. Different instances with the same parameters $n$ and $\alpha$ are not equivalent: some may admit a solution very close to proportionality, while some others may not. Therefore, we want to lower bound the proportion of the budget that the max-min utility represents, in the worst case. We call $\rho_n(\alpha)$ this quantity for any given pair $(\alpha, n)$. Having an explicit and compact expression of $\rho_n(\alpha)$ provides a quick estimation of how good the utility of the worst-off agent can be. Namely, if $B$ is the common budget, then a feasible solution for which every agent has utility at least $\rho_n(\alpha)B$ is guaranteed to exist. Furthermore, we are interested in the efficient (i.e., polynomial time) computation of a feasible solution exhibiting this guarantee.

## 1.1 The Context

Fairly dividing common resources among agents is one of the most prominent problems in social choice [9]. It has been considered in economics for many years [41], and most recently it has attracted the attention of computer scientists [7]. One of the most studied problems in this area consists in allocating a set of items to $n$ agents. Many concepts of fairness have been considered in the literature, including *envy-freeness* (each agent prefers her share to the share of another) [42, 20], and proportionality (each agent values her share at least a $1/n$ fraction of the whole manna) [40]. The items may be divisible (e.g., cake cutting), or indivisible. In the former case, envy-free or proportional allocations are guaranteed to exist and can be computed efficiently [9, 37]. When items are indivisible, there exist instances without envy-free or proportional allocation. In order to circumvent this impossibility, different relaxations have been proposed, such as bounded maximal envy [31] or envy-freeness up to one good [11] for envy-freeness. Regarding proportionality, one can mention proportionality up to one good [2, 15] and max-min fairness. The latter criterion stipulates that an allocation is fair whenever the utility of the poorest agent is maximized. Unfortunately, computing a max-min allocation is a hard problem, even for two agents [8, 6, 4]. Another relaxation of proportionality is to target a fraction that is smaller than a $\frac{1}{n}$-fraction of the whole manna. Concretely, each agent's utility should be at least $r$ times her utility for the whole set of items, for some $r \le 1/n$. Hill follows this path for the allocation of indivisible goods [26]. When every agent's utility for the whole manna is normalized to 1, their goal is to find a threshold $t_n \in [0, 1]$ such that there always exists an allocation where each agent has a utility of at least $t_n$ for her share. The highest possible value of $t_n$ is sought.

It appears that the largest utility that an agent can have for a single item significantly influences the value of $t_n$. Indeed, if on the one hand there exists an item for which all the agents have a large utility, then the utility for any other

<footnote n="1">¹See [14] for a recent work in this direction.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: $V_n$ for $n = 2$ and $n = 3$.</figcaption></figure>

object must be small,<fnref n="2" /> and every agent who does not get the valuable item must have a low utility for her share. On the other hand, if the utility for any single item is very small, then there must be a huge number of items and a simple way to allocate them so that the minimum agent's utility for her share approaches $1/n$. Thus, the intuition is that the best possible minimum utility decreases when the largest utility for a single item increases. Letting $\alpha$ be the maximum value for an item, Hill described in [26] a monotone non-increasing and continuous function $V_n : [0, 1] \to [0, \frac{1}{n}]$ whose parameter is $\alpha$. Any instance where $\alpha$ is the largest utility for a single good, admits a solution where the utility of the worst-off agent is at least $V_n(\alpha)$. See Figure 1 for an illustration of $V_n$ when $n \in \{2, 3\}$. For some values of $\alpha$, but not for all $\alpha \in [0, 1]$, $V_n(\alpha)$ provides the best guarantee on the utility of the worst-off agent. It turns out that the highest possible value of $t_n$ is not a monotone function of $\alpha$ (the above intuition is just a coarse tendency). Indeed it is possible to guarantee $W_n(\alpha)$ to the utility of worst-off agent, where $W_n(\alpha) \ge V_n(\alpha)$ for all $\alpha \in (0, 1]$, and $W_n(\alpha) > V_n(\alpha)$ when $\alpha$ is in some sub-intervals of $\in [0, 1]$ (see [23] for a formal description of the non-monotone function $W_n$). However, if we restrict ourselves to non-increasing functions, then $V_n(\alpha)$ is the best possible guarantee for all $\alpha \in [0, 1]$.

The work of Hill, along with the follow up article by Demko and Hill [18], inspired Markakis and Psomas [32] who proposed improvements and further algorithmic results. They described a polynomial time algorithm which, for any agent $i$ and her largest value $\alpha_i \in [0, 1]$ for a single item, returns an allocation where the utility of every agent $i$ is at least $V_n(\alpha_i)$. Note that instead of a global parameter $\alpha$, each agent $i$ has its own parameter $\alpha_i$. Markakis and Psomas also considered *truthful* mechanisms (i.e., algorithms where no agent has incentive to report false valuations for the items) for achieving an approximation of the $V_n$ guarantees [32]. Afterwards, an extension of the model to matroids has been proposed in [23] along with improvements on the worst-case guarantees with non-monotone functions. More recently, Li et al. [30] considered the problem of allocating indivisible chores to a set of agents, i.e., items on which the participants have non-positive utilities. In this setting, Li et al. extended the previous works on the guarantees when allocating indivisible goods [26, 32, 23], using $\alpha$ as the largest disutility of an agent for an item. Their bounds depend also on the number of chores.

This article deals with the problem of fairly spending a common budget. Its connection with the fair allocation of indivisible goods comes from the presence of multiple agents having indivisible demands. Our approach is similar to [18, 32, 23] because we derive explicit worst-case bounds on the max-min utility parameterized by the number of agents and the proportion $\alpha$ of the largest demand with respect to the budget. Nevertheless, our results show a significant singularity: the worst-case guarantee in the common budget problem is, as opposed to the fair allocation of indivisible goods, not a continuous function of $\alpha$. One of the main achievements of this article is a characterization of the worst-case guarantee for two agents. Its counterpart in the fair allocation of indivisible goods (i.e., a characterization of the worst-case guarantee that is not restricted to non-increasing functions) remains open.

<footnote n="2">²Every agent's utility for the whole set of items is normalized to 1.</footnote>
## 1.2 The Model

We consider the situation where a set $N$ of $n$ agents shares a common budget $B \in \mathbb{R}_{>0}$. Each agent $j$ has a demand set $D^j = \{d_1^j, \dots, d_{m^j}^j\}$ where $d_i^j \in \mathbb{R}_{>0}$ for all $i \in \{1, \dots, m^j\}$. A feasible solution $(S^1, \dots, S^n)$ consists of a subset of accepted demands $S^j \subseteq D^j$ for each agent $j$, such that $\sum_{j \in N} \sum_{d \in S^j} d \le B$. Every demand belonging to some $S^j$ is said to be accepted, otherwise it is said to be rejected. The utility provided by solution $(S^1, \dots, S^n)$ to agent $j$ corresponds to the sum of her accepted demands: $\sum_{d \in S^j} d$.

The value of a set of demands $X$ is denoted by $v(X)$ and defined as $\sum_{d \in X} d$. Thus, $v(S^j)$ is the utility of agent $j$ under $(S^1, \dots, S^n)$. For any integer $k$, let $[k]$ denote $\{1, \dots, k\}$. In this article, we suppose that the instances satisfy the following assumptions.

$$0 < d_i^j \le B, \quad \forall j \in N \text{ and } \forall i \in [m^j]. \qquad (1)$$

$$\sum_{i=1}^{m^j} d_i^j > B/n, \quad \forall j \in N. \qquad (2)$$

Assumption (1) is without loss of generality because null demands can always be accepted, and demands exceeding the budget must be rejected. The motivation for (2) is that the agents have equal rights [35]. Every agent can enjoy a $1/n$ fraction of the whole budget. If the demands of an agent do not exceed $B/n$, then all her demands can be accepted immediately. Thus, we can reduce the budget by the total value of these demands and remove the agent from the instance. Once all such agents are removed, and the budget is updated accordingly, the resulting instance satisfies (2). Moreover, we assume without loss of generality that

$$d_1^j \ge d_2^j \ge \dots \ge d_{m^j}^j, \quad \forall j \in N. \qquad (3)$$

The largest demand $\max_{j \in N} d_1^j$ is denoted by $d^*$ and parameter $\alpha$ is defined as $d^*/B$. For example, in the previous instance with Alice and Bob, the largest demand is 29, $B = 100$, and $\alpha = 29/100$.

We are interested in the “best” function $\rho_n : (0, 1] \to [0, 1]$ such that any instance with $n$ agents, budget $B$, and parameter $\alpha$ admits a feasible solution $(S^1, \dots, S^n)$ satisfying $v(S^j) \ge \rho_n(\alpha)B$, for any agent $j$, where $v(S^j)$ is, by definition, the utility of agent $j$. By “best” we mean that $\rho_n(\alpha)$ should take the largest possible value. It is easy to check that in the introductory example, the largest share of budget that we can ensure to both agents is 45 (when Alice and Bob receive $\{20, 25\}$ and $\{19, 16, 17\}$, respectively). This means that $\rho_2(29/100)$ cannot be larger than $45/100$. We will see that the value of $\rho_2(29/100)$ is even smaller than $45/100$. More formally, let $\text{Inst}(n, \alpha)$ be the set of all instances with $n$ agents, where the largest demand $d^*$ is equal to $\alpha$ times the budget, and (1) and (2) are satisfied. For a given instance $I$ of $\text{Inst}(n, \alpha)$ with a budget $B_I$, let $Z_I^*B_I$ be the maximum utility of the least funded agent. Then we have

$$\rho_n(\alpha) := \inf_{I \in \text{Inst}(n, \alpha)} Z_I^*.$$

The range of $\alpha$ is $(0, 1]$ because of (1) and $\rho_n(\alpha)$ is in $[0, 1/n]$. The analysis of $\rho_n$ will often be made with the help of the following sub-intervals of $(0, 1]$. For any $n$, any positive integer $k$, and any budget $B$, let

$$\mathcal{I}_0^n := \left(\frac{1}{n}, 1\right] \text{ when } n > 1,$$

$$\mathcal{I}_k^n := \left(\frac{1}{n(k+1)}, \frac{1}{nk}\right], \text{ and}$$

$$\mathcal{I}_k^n(B) := \left(\frac{B}{n(k+1)}, \frac{B}{nk}\right].$$

## 1.3 Results and Organization

We start by studying the case of a single agent ($n = 1$) in Section 2. We fully characterize $\rho_1$ which plays an important role in the analysis of the cases with multiple agents. For two agents or more, we provide in Section 3 a characterization of $\tilde{\rho}_n(\alpha)$, which is the largest non-increasing part of $\rho_n(\alpha)$.
The characterizations of $\rho_1$ and $\tilde{\rho}_n(\alpha)$ are accompanied by polynomial time greedy algorithms which output a feasible solution of value at least $\rho_1(\alpha)B$ and $\tilde{\rho}_n(\alpha)B$ for every agent, respectively.

Afterwards, we provide in Section 4 a characterization of $\rho_2$ and it is the most technical part of the article. The aforementioned greedy algorithms do not work anymore so we need a more intricate, but still working in polynomial time, strategy. Indeed, we elaborate on how the common budget is divided amongst the two agents, and we study how much of the first agent's budget can be saved and reused by the second agent. As already mentioned, similar previous works on the fair allocation of indivisible goods give bounds on the utility of the worst-off agent with non-increasing functions [18, 32]. Although $\rho_n(\alpha)$ is not fully characterized when $n > 2$, we determine lower and upper bounds which approximate it with high precision. The accuracy of these bounds is evaluated in Section 5.

## 1.4 Additional Related Work

Our model comprises a budget shared by a group of agents, a set of indivisible demands, and one has to decide which demands are funded under the budget constraint. Therefore, it can be seen as a multi-agent version of the well studied SUBSET SUM problem [33, 27]. SUBSET SUM is an NP-complete decision problem which consists of deciding if a subset of a given ground set of numbers adds up to some given target [22]. The optimization version of SUBSET SUM is a special case of KNAPSACK [33, 27] where one strives to maximize the total sum of the selected numbers without exceeding the target [16]. Thus, the connection with our model is that each number represents a demand while the target is the budget.

Related to our work is the SUBSET SUM GAME where two agents compete for the usage of a common budget [17, 36]. Each agent has some items represented by their size and the players alternatively decide to include one of their items in a collective knapsack whose capacity corresponds to the budget. As in our common budget model, every agent wants to maximize the total size of her items contained in the collective knapsack. However, our problem does not have any strategic aspect. Instead we focus on fairness like in the KNAPSACK SHARING problem which consists of filling a collective knapsack so that the utility of the poorest agent is maximized. Exact and heuristic methods were developed for the KNAPSACK SHARING problem; see [10, 43, 44, 25].

In the MULTI-AGENT KNAPSACK problem [5, 19], some agents have preferences over a ground set of items which have heterogeneous sizes. A common subset of items that fits into a knapsack of given capacity and best aggregates the voters' preferences is sought. Benabbou and Perny [5] use approval voting to gradually elicit the preferences of the agents over the possible solutions and find a common subset of items. Fluschnik et al. [19] study the parameterized complexity of collective solutions that optimize three aggregation objectives. Another collective budget problem has been introduced and studied by Michorzewski, Peters and Skowron [34]. In their article, there are divisible public projects which can receive any fraction of a common budget. Our model differs from their problem in many ways: the demands are private and indivisible, and the common budget may not be entirely used. Similar differences exist with the aforementioned memory sharing problem [21].

The model studied in this article also shares similarities with PARTICIPATORY BUDGETING which is receiving more and more attention [12, 3, 24]. In PARTICIPATORY BUDGETING, there is a budget, a group of agents, and a set of public projects associated with some costs. Every agent can derive a positive utility from a public project. Agents, who have possibly different preferences over the projects, vote for a subset of projects whose total cost cannot exceed the budget. The main differences between PARTICIPATORY BUDGETING and our model are that demands (which correspond to projects) are valued positively only by a single agent (the one who makes the demand) and agents do not vote for a selection.

To conclude, we can mention that our common budget problem falls within the field of combinatorial optimization problems that have been examined in the context of competition with multiple agents, such as the scheduling problem studied by Agnetis et al. [1].

## 2 The Single Agent Case

We start our study with the case where only one agent has demands. This case will provide a lower bound on $\rho_n(\alpha)$ for the case with more agents since one can solve an instance with $n > 1$ agents by solving $n$ sub-instances with a single agent and where each agent has his own reserved budget (for example, every agent is given a budget of $B/n$).
<figure><img src="image_3.png" /><figcaption>Figure 2: $\rho_1(\alpha)$.</figcaption></figure>

We are given a single agent ($n = 1$), her set of demands $D^1 = \{d_1^1, \dots, d_{m^1}^1\}$ and a positive budget $B$. Only instances satisfying (1) and (2) are considered. Due to assumption (3), $\alpha$ is equal to $\max_{i \in [m^1]} d_i^1/B = d^*/B$. We shall give the following characterization of $\rho_1(\alpha)$. See Figure 2 for an illustration.

**Theorem 1.** For any positive integer $k$, $\rho_1(\alpha) = \frac{k-1+\alpha}{k}$ when $\alpha \in (\frac{1}{k+1}, \frac{1}{k}] = \mathcal{I}_k^1$. Algorithm 1 returns a solution $S$ that verifies $\rho_1(\alpha)B \le v(S) \le B$ when $\alpha \in [\frac{1}{k+1}, \frac{1}{k}]$.

Let us begin with lower bounds on $\rho_1(\alpha)$ which derive from the solution returned by Algorithm 1. The algorithm is greedy: start from scratch and keep adding demands by descending value, until inserting an element would exceed the budget. Because of (2), Algorithm 1 cannot select all the demands.

**Algorithm 1 ($n=1$)**

**Require:** Budget $B$, demand set $\{d_1^1, \dots, d_{m^1}^1\}$ satisfying (1) and (2)

If necessary, sort and rename the demands by non-increasing value in order to satisfy (3)

$S \leftarrow \emptyset$

$i \leftarrow 1$

while $d_i^1 + \sum_{d \in S} d \le B$ do
$S \leftarrow S \cup \{d_i^1\}$
$i \leftarrow i + 1$

end while

return $S$

**Lemma 1.** $\rho_1(\alpha) \ge \max(\alpha, 1 - \alpha) \ge \frac{1}{2}$ when $\alpha \in (0, 1]$.

*Proof.* Consider the set $S$ returned by Algorithm 1 on an instance satisfying (1), (2) and (3). $S$ must contain $d_1^1$ because it fits in the budget (see (1)). Thus, we have a first lower bound of $d_1^1$ on $\sum_{d \in S} d$. Due to (2), the algorithm must reject a demand $d_k^1$ such that $\sum_{i=1}^k d_i^1 > B$. Since $d_1^1 \ge d_k^1$ by (3), we get a second lower bound of $B - d_1^1$ on $\sum_{d \in S} d = \sum_{i=1}^{k-1} d_i^1$. It follows that $\rho_1(\alpha)B \ge \sum_{d \in S} d \ge \max(d_1^1, B - d_1^1) \ge \frac{B}{2}$. Divide this by $B$ and replace $d_1^1/B$ by $\alpha$ to get that $\rho_1(\alpha) \ge \max(\alpha, 1 - \alpha) \ge \frac{1}{2}$. $\square$

**Lemma 2.** For any integer $k \ge 2$, $\rho_1(\alpha) \ge \frac{k-1+\alpha}{k}$ when $\alpha \in [\frac{1}{k+1}, \frac{1}{k}]$ and $\rho_1(\alpha) \ge \frac{k}{k+1}$ when $\alpha \in (0, \frac{1}{k}]$.
**Proof.** Again, we consider the solution $S$ returned by Algorithm 1. The proof is by induction. Let us begin with the base case $k = 2$: $\alpha \in [\frac{1}{3}, \frac{1}{2}]$ and $d_1^1 \in [\frac{B}{3}, \frac{B}{2}]$. The first step of Algorithm 1 is to place $d_1^1$ in $S$. Note that $d_1^1 \in [\frac{B}{3}, \frac{B}{2}]$ implies $d_1^1 \le B - d_1^1$. Thus, since the demands are sorted, for any $i$, it holds that

$$d_i^1 \le d_1^1 \le B - d_1^1. \quad (4)$$

The remaining budget after this first step is $B - d_1^1$. By Lemma 1, the solution $S$ uses at least half of the remaining budget (by (4), condition (1) is satisfied, (2) and (3) are satisfied too). Therefore, the value of $S$ is at least $d_1^1 + \frac{B-d_1^1}{2}$. In other words, $\rho_1(\alpha) \ge \frac{1+\alpha}{2}$ when $\alpha \in (\frac{1}{3}, \frac{1}{2}]$. We have $d_1^1 + \frac{B-d_1^1}{2} \ge \frac{2B}{3}$ because $d_1^1 \ge B/3$. Thus, $\rho_1(\alpha) \ge \frac{2}{3}$ when $\alpha \in [\frac{1}{3}, \frac{1}{2}]$. When $\alpha \in (0, \frac{1}{3}]$, the value of $S$ is at least $(1-\alpha)B$ (see the proof of Lemma 1) which is at least $\frac{2B}{3}$. In all, the value of $S$ is at least $\frac{2B}{3}$ when $\alpha \in (0, \frac{1}{2}]$. In other words, $\rho_1(\alpha) \ge \frac{2}{3}$ when $\alpha \in (0, \frac{1}{2}]$.

Let us prove the lemma for some $k > 2$, provided that it holds for all $t \in \{2, \dots, k-1\}$. Again, Algorithm 1 first places $d_1^1$ in $S$. The remaining budget is $B - d_1^1$ and the parameter $\alpha'$ of an auxiliary instance with budget $B' = B - d_1^1$ and demand set $D^1 \setminus \{d_1^1\}$ is in $(0, \frac{\alpha}{1-\alpha}]$. When $\alpha \in [\frac{1}{k+1}, \frac{1}{k}]$, $\alpha'$ is upper bounded by $\frac{1}{k-1}$. By induction, we know that $\rho_1(\alpha') \ge \frac{k-1}{k}$ when $\alpha' \in (0, \frac{1}{k-1}]$. Thus, Algorithm 1 complements $S = \{d_1^1\}$ with demands whose sum is at least a $\frac{k-1}{k}$ fraction of the remaining budget $B' = B - d_1^1$. The final value of $S$ is at least $d_1^1 + \frac{k-1}{k}(B - d_1^1) = \frac{k-1+\alpha}{k}B$. Thus, $\rho_1(\alpha) \ge \frac{k-1+\alpha}{k}$ when $\alpha \in [\frac{1}{k+1}, \frac{1}{k}]$.

Finally, let us prove that $\rho_1(\alpha)$ is at least $\frac{k}{k+1}$ when $\alpha \in (0, \frac{1}{k}]$. We have just seen that $\rho_1(\alpha) \ge \frac{k-1+\alpha}{k}$ when $\alpha \in [\frac{1}{k+1}, \frac{1}{k}]$. Therefore, $\rho_1(\alpha)$ is at least $\frac{k-1+\frac{1}{k+1}}{k} = \frac{k}{k+1}$ when $\alpha \in [\frac{1}{k+1}, \frac{1}{k}]$. When $\alpha \in (0, \frac{1}{k+1}]$, we have $\rho_1(\alpha) \ge 1 - \alpha$ by Lemma 1, and this is proved with the solution returned by Algorithm 1. Therefore, $\rho_1(\alpha)$ is at least $1 - \frac{1}{k+1} = \frac{k}{k+1}$. In all, $\rho_1(\alpha)$ is at least $\frac{k}{k+1}$ when $\alpha \in (0, \frac{1}{k}]$. $\square$

The next result is a matching upper bound on $\rho_1(\alpha)$.

**Lemma 3.** $\rho_1(\alpha) \le \frac{k-1+\alpha}{k}$ for any integer $k \ge 1$ and $\alpha \in (\frac{1}{k+1}, \frac{1}{k}] = \mathcal{I}_k^1$.

**Proof.** The upper bound derives from the following family of instances.

**Instance 1.** Consider a number $\delta$ in the interval $[\frac{1}{k+1}+\epsilon, \frac{1}{k}]$ for any integer $k \ge 1$, and $0 < \epsilon < \min(\frac{1}{k} - \frac{1}{k+1}, \frac{1-\delta}{k(k-1)})$.

The budget $B$ is equal to 1. The agent has $k+1$ demands: one of value $\delta$ and $k$ others of value $\frac{1-\delta}{k} + \epsilon$. We have $\delta \ge \frac{1}{k+1} + \epsilon > \frac{1}{k+1} + \frac{k\epsilon}{k+1}$ from which we deduce that $\delta \ge \frac{1-\delta}{k} + \epsilon$. The largest demand being $\delta$, we have $\delta = \alpha$.

We cannot accept all demands because $\delta + k(\frac{1-\delta}{k} + \epsilon) = 1 + k\epsilon > B$. However, because $\epsilon < \frac{1-\delta}{k(k-1)}$, we can accept all the demands but the last one whose value is the smallest. By doing so, we get the best feasible solution of value $d_1^1 + \dots + d_k^1 = (\alpha + (k-1)(\frac{1-\alpha}{k} + \epsilon))B = (\frac{k-1+\alpha}{k} + \epsilon(k-1))B$. When $\epsilon \to 0$, the value of this solution tends to $\frac{k-1+\alpha}{k}B$, and the range of $\alpha$ is $(\frac{1}{k+1}, \frac{1}{k}]$. $\square$

Lemmas 1, 2, and 3 give Theorem 1 while Algorithm 1 outputs a feasible solution of value at least $\rho_1(\alpha)B$ in $O(\mu \log \mu)$ time where $\mu$ is the number of demands (see the proofs of Lemmas 1 and 2).

The importance of Lemmas 1, 2, and 3 lies in the fact that they will be reused for any value of $n > 1$. When multiple agents are involved, we will split the budget among the different agents, and then use Algorithm 1 to compute $S^j$ for every $j \in N$ and Theorem 1 for evaluating $v(S^j)$.

# 3 Dealing With Two Agents or More

This section deals with the case of at least two agents ($n > 1$). So far we have provided a characterization of $\rho_1$ for all $\alpha$ (Theorem 1) and we will give later on a characterization of $\rho_2$ (cf. (6) in Section 4). We have seen that $\rho_1$ is not monotone and in fact, the same goes for $\rho_n$ for all $n$. Unfortunately, we do not provide a characterization of $\rho_n$ for any values of $n$ and $\alpha$. However, we can do so when $\alpha \in (\frac{1}{2n}, 1]$. More importantly, we give in this section a characterization of the largest worst-case utility of the least funded agent if we restrict ourselves to non-increasing functions of $\alpha$. Let $\tilde{\rho}_n$ denote the best (i.e., largest) non-increasing function such that, for every instance
with parameters $n$ and $\alpha$, there exists a solution where every agent's utility is at least $\tilde{\rho}_n(\alpha)B$. By definition, $\tilde{\rho}_n$ constitutes a lower bound on $\rho_n$. Note that in their seminal works, Demko and Hill [26, 18], and Markakis and Psomas [32] restricted themselves to non-increasing functions to describe explicit lower bounds on the utility of the worst-off agent in the context of allocating indivisible goods.

Before we proceed with these results, let us make a simple observation.

**Observation 1.** $\rho_n(\alpha) = \tilde{\rho}_n(\alpha) = 0$ when $\alpha > \frac{1}{n}$.

Indeed, if every agent has a unique demand whose value exceeds $B/n$, then the demand of at least one agent cannot be accepted (otherwise the budget is exceeded). If follows that we can focus on the case $\alpha \in (0, 1/n]$ and replace (1) with

$$0 < d_i^j \le B/n, \forall j \in N \text{ and } i \in [m^j]. \qquad (5)$$

In addition to (3), we will suppose without loss of generality that $d_1^1 = d^* = \max_{j \in N} d_1^j$. Therefore, parameter $\alpha$ equals $d_1^1/B$.

The rest of this section is organized as follows. Section 3.1 deals with the characterization of $\tilde{\rho}_n$. Upper bounds on $\rho_n$ for all $\alpha \in (0, \frac{1}{n}]$ are given in Section 3.2. We conclude in Section 3.3 with a characterization of $\rho_n(\alpha)$ when $\alpha \in \mathcal{I}_1^n = (\frac{1}{2n}, \frac{1}{n}]$.

## 3.1 An Optimal Non-Increasing Bound

Our objective here is to characterize $\tilde{\rho}_n$. The following lower bounds derive from the solution of Algorithm 2 which runs in $O(n\mu \log \mu)$ time where $\mu = \max_{j \in N} m^j$. The algorithm consists in reserving a budget of $B/n$ to every agent. Afterwards Algorithm 1 is run for every agent separately.

**Algorithm 2 ($n > 1$)**

**Require:** A budget $B$, a set $N$ of $n$ agents, and a demand set $D^j$ for all $j \in N$ satisfying (5) and (2) for all $j \in N$ do

$S^j \leftarrow$ the solution of Algorithm 1 with input $B/n$ and $D^j$

end for

return $S = (S^1, \dots, S^n)$

**Lemma 4.** For any integer $k \ge 1$, $\tilde{\rho}_n(\alpha) \ge \frac{k}{n(k+1)}$ when $\alpha \le \frac{1}{nk}$.

*Proof.* Suppose $\alpha \le \frac{1}{nk}$ for some positive integer $k$. The value of every demand is at most $\frac{B}{nk}$. Algorithm 2 reserves a budget of $B/n$ for every agent. A demand represents a fraction $\alpha'$ of at most $\frac{B/(nk)}{B/n} = \frac{1}{k}$ of an agent's reserved budget. Since $\alpha' \le 1/k$, Lemma 2 indicates that every agent is guaranteed to receive a fraction of $\frac{k}{k+1}$ of her reserved budget, namely $\frac{k}{k+1} \frac{B}{n}$. Thus, $\tilde{\rho}_n(\alpha) \ge \frac{k}{n(k+1)}$. $\square$

**Lemma 5.** For any integer $k \ge 1$ and any positive $\epsilon < 1/k$, $\tilde{\rho}_n(\alpha) \le \frac{k(1+\epsilon)}{n(k+1)}$ when $\alpha \ge \frac{1+\epsilon}{n(k+1)}$.

*Proof.* Consider the following instance where the budget is equal to 1. Fix an integer $k \ge 1$, and $\delta = \frac{1+\epsilon}{n(k+1)}$ where $0 < \epsilon \le 1/k$. Every agent has $k+1$ demands, each of value $\delta$. We have $\alpha = \delta$. Accepting all the demands would exceed the budget: $n(k+1)\delta = 1 + \epsilon > 1$. Therefore, the least funded agent has at most $k$ accepted demands. Accepting $k$ demands per agent is a feasible solution (the budget constraint is satisfied) because $\epsilon \le 1/k$. This solution guarantees $\frac{k(1+\epsilon)}{n(k+1)}$ to everybody. It follows that $\tilde{\rho}_n(\alpha) \le \frac{k(1+\epsilon)}{n(k+1)}$ when $\alpha = \frac{1+\epsilon}{n(k+1)}$. Since $\tilde{\rho}_n(\alpha)$ is non-increasing, $\tilde{\rho}_n(\alpha) \le \frac{k(1+\epsilon)}{n(k+1)}$ when $\alpha \ge \frac{1+\epsilon}{n(k+1)}$. $\square$

We can derive the following characterization of $\tilde{\rho}_n(\alpha)$ from Observation 1, Lemma 4 and Lemma 5. See Figure 3 for an illustration of $\tilde{\rho}_3(\alpha)$ (in blue).

**Corollary 1.** The largest worst-case guarantee with the help of a non-increasing function is $\tilde{\rho}_n(\alpha) := \frac{k}{n(k+1)}$ when $\alpha \in \mathcal{I}_k^n$, for any $k \ge 0$.
## 3.2 Upper bounds for the Multi-agent Case

The upper bounds on $\rho_n$ rely on families of instances. See Figure 3 for an illustration when $n = 3$ (in red).

**Proposition 1.** For $n > 1$ and $k \ge 1$ it holds that $\rho_n(\alpha) \le \frac{(k-1)/n+\alpha}{k}$ if $\alpha \in (\frac{1}{n(k+1)}, \frac{k^2+n-1}{n((n-1)(k+1)+k^3)}]$, and $\rho_n(\alpha) \le \frac{k(1-k\alpha)}{(n-1)(k+1)}$ if $\alpha \in (\frac{k^2+n-1}{n((n-1)(k+1)+k^3)}, \frac{1}{nk}]$.

*Proof.* Consider the following family of instances.

**Instance 2.** Fix a number $\delta$ in the interval $[\frac{1}{n(k+1)}, \frac{k^2+n-1}{n((n-1)(k+1)+k^3)}]$ for any integer $k \ge 1$, and some positive $\epsilon$ such that $\frac{1}{n(k+1)} + \epsilon \le \frac{k^2+n-1}{n((n-1)(k+1)+k^3)}$. Moreover, $\epsilon$ is upper bounded by $\frac{1/n-\delta}{k(k-1)}$ and $\frac{n(k+1)\delta-1}{n(k+1)}$ when $k > 1$. The budget B is equal to 1. Each agent has $k+1$ demands: one of value $\delta$ and the $k$ others of value $\frac{1/n-\delta}{k} + \epsilon$. Since $\delta \ge \frac{1}{n(k+1)} + \epsilon \ge \frac{1}{n(k+1)} + \frac{k\epsilon}{k+1}$, we deduce that $\delta \ge \frac{1/n-\delta}{k} + \epsilon$ and thus $\alpha = \delta$.

We cannot accept all the demands of all the agents because it would exceed the budget: $n(\delta + k(\frac{1/n-\delta}{k} + \epsilon)) = 1 + kn\epsilon > 1$ because $\epsilon > 0$, $k \ge 1$ and $n \ge 2$. However, we are going to see that we can accept, for every agent, all her demands but one (the rejected demand has value $\frac{1/n-\delta}{k} + \epsilon$). Under this solution, the total sum of demands is $V := n(\delta + (k-1)(\frac{1/n-\delta}{k} + \epsilon))$ and we need to prove that $V$ does not exceed the budget of 1. If $k = 1$, then $V = n\delta$ and $\delta \le \frac{k^2+n-1}{n((n-1)(k+1)+k^3)} = \frac{1}{2n-1}$. It follows that $V \le 1$ when $k = 1$. Suppose from now on that $k > 1$ and, by hypothesis $\epsilon \le \frac{1}{n-\delta}$, Note that $\frac{1}{n-\delta} > 0$ because $k > 1$ and $\delta \le \frac{k^2+n-1}{n((n-1)(k+1)+k^3)} < 1/n^3$. Some simple calculations give $\epsilon \le \frac{1}{n-\delta}$ $\Leftrightarrow n(\delta + (k-1)(\frac{1}{n-\delta} + \epsilon)) \le 1$. Indeed, $\epsilon \le \frac{1}{n-\delta}$ $\Leftrightarrow (k-1)\epsilon \le \frac{1}{n-\delta}$ $\Leftrightarrow (k-1)(\frac{1}{n-\delta} + \epsilon) + (k-1)\epsilon \le (k-1)(\frac{1}{n-\delta} + \epsilon) + \frac{1}{n-\delta} \Leftrightarrow \delta + (k-1)(\frac{1}{n-\delta} + \epsilon) \le \frac{1}{n} \Leftrightarrow n(\delta + (k-1)(\frac{1}{n-\delta} + \epsilon)) \le 1$. In other words, $V \le 1$ when $k > 1$.

For a positive $\epsilon$ that tends to 0, the guarantee for every agent tends to $\delta + (k-1)(\frac{1}{n-\delta}) = \frac{(k-1)/n+\alpha}{k}$ when $\alpha \in (\frac{1}{n(k+1)}, \frac{k^2+n-1}{n((n-1)(k+1)+k^3)}]$.

The second part of the proof relies on another family of instances.

**Instance 3.** For any integer $k \ge 1$, consider a number $\delta$ in the interval $[\frac{1+\epsilon}{nk+n-1}, \frac{1}{nk}]$ such that $0 < \epsilon \le \frac{1}{k} - \frac{1}{nk}$. Agent 1 has $k+1$ demands of value $\delta$ and every agent $i \ne 1$ has $k+1$ demands of value $r := \frac{1-k\delta+\epsilon}{(n-1)(k+1)}$. The budget B is equal to 1. We infer from $\delta \ge \frac{1+\epsilon}{nk+n-1}$ that $\delta \ge \frac{1-k\delta+\epsilon}{(n-1)(k+1)} = r$.<fnref n="4" /> It follows that $\alpha = \delta$.

If we accept the $k+1$ demands for every agent $i \ne 1$, then the total amount is $(n-1)(k+1)r = 1 - k\delta + \epsilon$. If, in addition, $k$ demands of agent 1 are accepted, then the budget is exceeded by $\epsilon$ which is positive. Thus, we can only accept $k-1$ demands of agent 1 and guarantee her $(k-1)\delta$. We get a first solution which guarantees $\min((k+1)r, (k-1)\delta)$ to the agents.

In a second solution, we accept $k$ demands per agent $i \ne 1$; every agent $i \ne 1$ gets $kr$. At the same time, we can accept $k$ demands of agent 1 and guarantee her $k\delta$. Let us prove that this solution is feasible, i.e., $k((n-1)r+\delta) \le B$. We have $\epsilon \le \frac{1}{k} - \frac{1}{nk}$. Since $\delta \le \frac{1}{nk}$, we deduce that $\epsilon + \delta \le \frac{1}{k} - \delta$. This is equivalent to $\epsilon + \delta \le 1 - k\delta + k\delta + \epsilon + \delta \le 1 + \frac{1}{k} \Leftrightarrow 1 - k\delta + \epsilon + (k+1)\delta \le \frac{k+1}{k} \Leftrightarrow \frac{k(1-k\delta+\epsilon+(k+1)\delta)}{k+1} \le 1 \Leftrightarrow k(\frac{(n-1)(1-k\delta+\epsilon)}{(n-1)(k+1)} + \delta) \le 1 \Leftrightarrow k((n-1)r+\delta) \le 1$. Since $r \le \delta$, the guarantee of the second solution is $kr = \frac{k(1-k\delta+\epsilon)}{(n-1)(k+1)}$.

We are going to prove that $(k-1)\delta \le kr$, meaning that the guarantee of the first solution is worse than the guarantee of the second solution. Since $\delta \le \frac{1}{nk}$, we deduce $1 - k\delta \ge \frac{n-1}{n}$. Multiply this by $\frac{k}{(n-1)(k+1)}$ to get $\frac{k(1-k\delta)}{(n-1)(k+1)} \ge \frac{k}{(k+1)n}$. Use $\frac{k(1-k\delta+\epsilon)}{(n-1)(k+1)} \ge \frac{k(1-k\delta)}{(n-1)(k+1)}$ and $\frac{k}{(k+1)n} \ge \frac{k-1}{kn}$ to get that $\frac{k(1-k\delta+\epsilon)}{(n-1)(k+1)} \ge \frac{k-1}{kn}$. Since $\delta \le \frac{1}{nk}$, we obtain $kr = \frac{k(1-k\delta+\epsilon)}{(n-1)(k+1)} \ge (k-1)\delta$.

<footnote n="3">³This comes from the fact that $k^2 + n - 1 < k^3 + (n - 1)(k + 1)$</footnote>

<footnote n="4">⁴Multiply $\delta \ge \frac{1+\epsilon}{nk+n-1}$ by $-k$ and add $1 + \epsilon$ on both sides to get that $1 - k\delta + \epsilon \le 1 + \epsilon - \frac{k(1+\epsilon)}{nk+n-1}$. Afterwards, divide by $nk+n-1$ to get that $\frac{1-k\delta+\epsilon}{nk+n-1} \le \frac{1+\epsilon}{nk+n-1} - \frac{k(1+\epsilon)}{(nk+n-1)^2}$. Since $\frac{k(1+\epsilon)}{(nk+n-1)^2} \ge 0$, we deduce that $\frac{1-k\delta+\epsilon}{nk+n-1} \le \frac{1+\epsilon}{nk+n-1}$.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 3: $\tilde{\rho}_3(\alpha)$ in blue and upper bounds on $\rho_3(\alpha)$ in red.</figcaption></figure>

Therefore, the best guarantee with Instance 3 is $kr = \frac{k(1-k\delta+\epsilon)}{(n-1)(k+1)}$, which tends to $\frac{k(1-k\alpha)}{(n-1)(k+1)}$ when $\epsilon \to 0$ and using $\delta = \alpha$.

Instance 2 gives an upper bound of $(\frac{k-1}{k})/(n+\alpha)$ for $\alpha \in (\frac{1}{n(k+1)}, \frac{k^2+n-1}{n((n-1)(k+1)+k^3)}]$ and Instance 3 provides an upper bound of $\frac{k(1-k\alpha)}{(n-1)(k+1)}$ for $\alpha \in (\frac{1}{nk+n-1}, \frac{1}{nk}]$, and $(\frac{1}{nk+n-1}, \frac{1}{nk}] \supset (\frac{k^2+n-1}{n((n-1)(k+1)+k^3)}, \frac{1}{nk}]$ holds because $\frac{1}{nk+n-1} \le \frac{k^2+n-1}{n((n-1)(k+1)+k^3)}$ when $n > 1$ and $k \ge 1$. Thus, our upper bound on $\mathcal{I}_k^n$ is $(\frac{k-1}{k})/(n+\alpha)$ for $\alpha \in (\frac{1}{n(k+1)}, \frac{k^2+n-1}{n((n-1)(k+1)+k^3)}]$ and $\frac{k(1-k\alpha)}{(n-1)(k+1)}$ for $\alpha \in (\frac{k^2+n-1}{n((n-1)(k+1)+k^3)}, \frac{1}{nk}]$, for all $k \ge 1$ and $n > 1$. $\square$

### 3.3 A Characterization of $\rho_n(\alpha)$ When $\alpha \in \mathcal{I}_1^n$

Although $\rho_n$ is not characterized for all value of $\alpha$ in the interval $(0, 1]$, the following lemma provides the exact value of $\rho_n(\alpha)$ when $\alpha \in (\frac{1}{2n}, \frac{1}{n}] = \mathcal{I}_1^n$ (the case $\alpha \in (\frac{1}{n}, 1]$ is given in Observation 1).

**Lemma 6.** $\rho_n(\alpha) = \min(\alpha, \frac{1-\alpha}{2(n-1)})$ when $\alpha \in \mathcal{I}_1^n$.

*Proof.* Suppose $\alpha \in (\frac{1}{2n}, \frac{1}{n}] = \mathcal{I}_1^n$. By assumption, agent 1 has the largest demand $d_1^1 = d^* = \alpha B$. Consider the solution where $d_1^1$ is the only accepted demand for agent 1. The utility of agent 1 is $\alpha B$. The remaining budget is $B - d_1^1$, and every agent $j \ne 1$ may have a reserved budget of $\frac{B-d_1^1}{n-1} = \frac{1-\alpha}{n-1}B$. Fix an agent $j \ne 1$. If $\sum_{i=1}^{m^j} d_i^j \le \frac{1-\alpha}{n-1}B$, then we can accept all her demands. We know from (2) that $\sum_{i=1}^{m^j} d_i^j > B/n$, and $B/n \ge \alpha B$ because $\alpha \le 1/n$. Therefore, the value of agent $j$ for her whole set of demands is at least $\alpha B$. Now suppose that $\sum_{i=1}^{m^j} d_i^j > \frac{1-\alpha}{n-1}B$. Since $\alpha \le 1/n$, we get that $\alpha B \le \frac{1-\alpha}{n-1}B$. No demand of agent $j$ exceeds her reserved budget of $\frac{1-\alpha}{n-1}B$. We can apply Lemma 1 which indicates that $\frac{1}{2} \cdot \frac{1-\alpha}{n-1}B$ is guaranteed to agent $j$. The solution is built with Algorithm 1.

It follows that every agent in $N$ has at least $\min(\alpha B, \frac{(1-\alpha)B}{2(n-1)})$. Thus, $\rho_n(\alpha) \ge \min(\alpha, \frac{1-\alpha}{2(n-1)})$ when $\alpha \in \mathcal{I}_1^n$. To conclude, Instances 2 and 3 with $k=1$ give an upper bound of $\alpha$ when $\alpha \in \mathcal{I}_1^n$, and of $\frac{1-\alpha}{2(n-1)}$ when $\alpha \in (\frac{1}{2n-1}, \frac{1}{n}]$, respectively. $\square$

From an algorithmic perspective, we use Algorithm 3 when $\alpha \in \mathcal{I}_1^n$. The algorithm accepts $d^*$ (it belongs to agent 1 by hypothesis) and proceeds as follows for every $j \ne 1$. Reserve a budget of $\frac{1-\alpha}{n-1}B$. If all the demands of $j$ fit in her reserved budget, then accept them all. Otherwise, run Algorithm 1.
**Algorithm 3**

**Require:** A budget $B$, $n$ agents, and $n$ sets of demands $D^1, \dots, D^n$

$$S^1 \leftarrow \{d^*\}$$

**for all** $j \neq 1$ **do**

$$B^j \leftarrow \frac{1-\alpha}{n-1} B$$

**if** $v(D^j) \leq B^j$ **then**

$$S^j \leftarrow D^j$$

**else**

$$S^j \leftarrow \text{Algorithm 1}(B^j, D^j)$$

**end if**

**end for**

**return** $(S^1, \dots, S^n)$

<figure><img src="image_5.png" /><figcaption>Figure 4: $\rho_2(\alpha)$.</figcaption></figure>

# 4 A Characterization for Two Agents

This section deals with a characterization of $\rho_2(\alpha)$ which is given in (6) and depicted in Figure 4.

$$\rho_2(\alpha) = \begin{cases} \frac{k-1+2\alpha}{2k}, & \text{if } \frac{1}{2(k+1)} < \alpha \le \frac{k^2+1}{2(k^3+k+1)} \text{ and } k > 2 \\ \frac{k(1-k\alpha)}{k+1}, & \text{if } \frac{k^2+1}{2(k^3+k+1)} < \alpha \le \frac{1}{2k} \text{ and } k > 2 \\ \frac{1}{4} + \frac{\alpha}{2}, & \text{if } 1/6 < \alpha \le 11/50 \\ \frac{6(1-\alpha)}{2-\frac{1}{4\alpha}}, & \text{if } 11/50 < \alpha \le 4/17 \\ \frac{\alpha}{3}, & \text{if } 4/17 < \alpha \le 1/4 \\ \frac{1-\alpha}{2}, & \text{if } 1/4 < \alpha \le 1/3 \\ 0, & \text{if } 1/3 < \alpha \le 1/2 \\ 0, & \text{if } 1/2 < \alpha \le 1 \end{cases} \quad (6)$$

We also propose a polynomial algorithm which builds a solution $(S^1, S^2)$ such that $\min(v(S^1), v(S^2)) \geq \rho_2(\alpha)B$ for every instance.

## 4.1 Roadmap

Let us explain how (6) is proved and what is the corresponding algorithmic approach. Our strategy is to split the budget between the two agents, and to reduce the problem to two single-agent problems. Hence, Algorithm 1 and the characterization of $\rho_1(\alpha)$ given in Theorem 1 can be reused but what was successful in Section 3 is now insufficient.
### 4.1.1 Pitfalls

A direct approach would be to cut the budget evenly and to apply Algorithm 1 separately for each agent (as done in Section 3). However, this strategy may fail to give the best guarantee. Let us illustrate this with the following example.

**Instance 4.** There are two agents ($n = 2$), $B = 400$, $D^1 = \{80, 59, 59, 59\}$, and $D^2 = \{75, 64, 64\}$.

If we reserve a budget of $B/2 = 200$ to both agents, then the best subsets for the agents are $\{80, 59, 59\}$ and $\{75, 64\}$, respectively. Agents 1 and 2 have utility 198 and 139, respectively. The minimum utility is 139 and no additional demand of agent 2 can be accepted without exceeding the budget. However, (6) indicates that a solution with minimum utility at least $\rho_2(80/400) * 400 = 140$ must exist<fnref n="5" />. Under solution $(\{59, 59, 59\}, \{75, 64, 64\})$, the minimum utility is larger (177 instead of 139) but agent 2's utility exceeds $B/2$. Therefore, reserving a budget of $B/2$ to both agents can be an obstacle to the achievement of the best possible guarantee on the minimum utility.

Furthermore, the two-agent case differs also from the results of Sections 2 and 3 because, sometimes, the best guarantee cannot be reached by a simple greedy algorithm where the demands are taken by non-increasing value until the desired guarantee is obtained. In Instance 4, a feasible solution with minimum utility at least 140 exists. Taking the demands by non-increasing value in order to guarantee 140 to both agents would lead to the solution $(\{80, 59, 59\}, \{75, 64, 64\})$ which is infeasible because it violates the budget constraint. Therefore, it is sometimes necessary to depart from the greedy approach to build solutions that meet the guarantee defined in (6).

### 4.1.2 Proving Strategy

Our strategy requires to decide how the common budget $B$ is split. Concretely, agent 1, which is the agent with the largest demand has a reserved budget of $B/2 - \Delta$ where $0 \le \Delta < B/2$. A subset of demands $S^1$ is accepted for agent 1 but $v(S^1)$ may be strictly smaller than $B/2 - \Delta$, meaning that a part $E := B/2 - \Delta - v(S^1)$ can be saved and transferred to the reserved budget of agent 2. Therefore, $B/2 + \Delta + E$ becomes the reserved budget of agent 2, and a subset of demands $S^2$ is accepted for agent 2. Finally, $(S^1, S^2)$ is output and it satisfies (6), i.e., $\min(v(S^1), v(S^2)) \ge \rho_2(\alpha)B$.

Therefore, our proving strategy relies on an accurate definition of $\Delta$ and a characterization of $E$ in the worst case. Section 4.2 contains a characterization of $E$ which depends on the budget reserved to agent 1 (i.e., $B/2 - \Delta$) and her largest demand $\alpha B$ (the proof is deferred to the appendix, Section 7). Algorithms are also given for building a solution where at least $E$ is saved. The values of $\Delta$ are defined in Section 4.3 so that (6) can be proved. Algorithm 6 (given in Section 4.3) applied on an instance with two agents outputs a solution such that the utility values of both agents is at least $\rho_2(\alpha)B$.

As a reminder, we suppose that an instance satisfies (1), (2) and (3), and $d^* = \max_{j \in N} d_j^1 = \alpha B$. We also suppose without loss of generality that the largest demand belongs to agent 1: $d^* = d_1^1 \ge d_1^2$. Thereafter, we will denote by $\gamma_j$ the following function.

$$ \gamma_j(d^*, B) := \rho_j(d^*/B)B = \rho_j(\alpha)B \quad (7) $$

Therefore, the characterization of $\rho_1$ (Theorem 1) gives the following characterization of $\gamma_1$.

$$ \gamma_1(d^*, B) = d^* + \frac{k-1}{k}(B-d^*) = \frac{(k-1)B + d^*}{k} \quad \text{when } d^* \in \mathcal{I}_k^1(B) \quad (8) $$

for any positive integer $k$. In terms of interpretation, $\gamma_j(d^*, B)$ is the quantity that is guaranteed to the worst-off agent while $\rho_j(\alpha)$ represents the guaranteed proportion of the budget. Of course, characterizing $\rho_j$ is strictly equivalent to characterizing $\gamma_j$ but we will find convenient to use $\gamma_j$ instead of $\rho_j$.

## 4.2 Bounding the Budget Saving for a Single Agent

The goal of this section is to determine how much can be saved, in the worst case, from the reserved budget of an agent, while a certain quantity is guaranteed to her. We also present polynomial algorithms that determine the corresponding subset of accepted demands.

<footnote n="5">⁵Note that $\alpha = 1/5$ implies $1/6 < \alpha \le 11/50$ and therefore $\rho_2(1/5) = 1/4 + 1/10$ holds according to (6)</footnote>
Let $\text{Inst}_1(d^*, B)$ denote the set of all instances with a single agent ($n = 1$), such that the budget is $B$, the largest demand is equal to $d^*$, and (1) and (2) are satisfied. For any single agent instance $I \in \text{Inst}_1(d^*, B)$ with demand set $D_I$, let $R_I$ be a subset of demands of minimum value within the set $\{S \subseteq D_I | v(S) \ge \gamma_1(d^*, B)\}$. If $R_I$ is not unique, then select one arbitrarily. We then define:

$$R(d^*, B) := \sup\{v(R_I) \mid I \in \text{Inst}_1(d^*, B)\}. \qquad (9)$$

Thus, any instance in $\text{Inst}_1(d^*, B)$ admits a solution $S$ such that $\gamma_1(d^*, B) \le v(S) \le R(d^*, B)$. At least $B - R(d^*, B)$ can be saved from the budget, so we are interested in the saving $E(d^*, B)$ defined as follows.

$$E(d^*, B) = B - R(d^*, B) \qquad (10)$$

Moreover, we aim at constructing in polynomial time a solution $S$ which satisfies $\gamma_1(d^*, B) \le v(S) \le R(d^*, B) = B - E(d^*, B)$. Note that $B$ in this section refers to the budget of a single agent instance $I \in \text{Inst}_1(d^*, B)$, but it is not equal to the common budget of the 2-agent instance mentioned in Section 4.1.2.

**Theorem 2.** For every single agent instance $I \in \text{Inst}_1(d^*, B)$ with demand set $D_I$, one can build in polynomial time a solution $S \subseteq D_I$ such that $\gamma_1(d^*, B) \le v(S) \le B - E(d^*, B)$ where

$$E(d^*, B) = \begin{cases} B - \frac{k+1}{k}(B - d^*), & \text{for } \frac{1}{k+1}B < d^* \le \frac{k+1}{k^2+k+1}B \text{ and } k > 2 \\ B - kd^*, & \text{for } \frac{k+1}{k^2+k+1}B < d^* \le \frac{1}{k}B \text{ and } k > 2 \\ \frac{1}{2}(3d^* - B), & \text{for } B/3 < d^* \le 7B/17 \\ \frac{2}{3}(B - 2d^*), & \text{for } 7B/17 < d^* \le B/2 \\ B - d^*, & \text{for } B/2 < d^* \le B \end{cases}.$$

The proof of Theorem 2 is given in the appendix, Section 7. On our way to proving Theorem 2, the first step is to observe that, instead of studying the entire set $\text{Inst}_1(d^*, B)$, one can suppose that an instance satisfies the following two hypotheses.

**Hypothesis 1.** At most one demand of $D_I$ is strictly smaller than $d^*/2$.

**Hypothesis 2.** $v(D_I) - v(\{d\}) \le B$ holds for all $d \in D_I$.

Said differently, Hypothesis 2 imposes that the removal of any single demand would violate (2) since $n = 1$. Every instance can be modified in polynomial time to satisfy these hypotheses: use Algorithm 4 to do so.

**Algorithm 4 Enforcing Hypotheses 1 and 2**

**Require:** An instance $I \in \text{Inst}_1(d^*, B)$ with demand set $D_I$

**Ensure:** A modification of $I$ which satisfies Hypotheses 1 and 2

**while** $D_I$ contains two demands $d$ and $d'$ such that $d \le d' < d^*/2$ **do**

$$D_I \leftarrow (D_I \setminus \{d, d'\}) \cup \{d+d'\}$$

**end while**

Rename the demands of $D_I$ by non-increasing value

Let $t$ be the index such that $\sum_{i=1}^{t-1} d_i^1 \le B$ and $\sum_{i=1}^{t} d_i^1 > B$

$$D_I \leftarrow \{d_1^1, \dots, d_t^1\}$$

**return** $D_I$

Algorithm 4, which runs in $O(|D_I| \log |D_I|)$ time, bundles the demands while maintaining the following properties: $B$ and $d^*$ remain unchanged, and (1) and (2) are preserved. One advantage of the bundling phase is to drastically reduce the number of demands so that a complete enumeration of all the subsets of (bundled) demands takes constant time. We can also observe that, although Algorithm 4 modifies the original instance, a feasible solution $S$ of the original instance can be easily retrieved from any subset of demands $S'$ of the modified instance built by Algorithm 4, and $v(S) = v(S')$. Indeed, by construction, every demand of $S'$ corresponds to a bundle of demands of the original instance. Our strategy is to prove Theorem 2 for any instance of $\text{Inst}_1(d^*, B)$ satisfying Hypotheses 1 and 2. Then, we
proceed as follows. Take $I \in \text{Inst}_1(d^*, B)$ and run Algorithm 4. Find a subset of demands $S'$ that satisfies Theorem 2. Derive from $S'$ a feasible solution $S$ of $I$ which also satisfies Theorem 2. See Algorithm 5 for the construction of $S'$.

Algorithm 5 returns a demand set $S$ that verifies $\gamma_1(d^*, B) \le v(S) \le B - E(d^*, B)$. It runs as follows: start with a set of $m^1$ demands, apply Algorithm 4 to obtain a modified instance with $m$ demands satisfying Hypotheses 1 and 2. This is done in $O(m^1 \log m^1)$ time. When $B/3 < d^* \le B$, Hypotheses 1 and 2 allow us to assert that the number of demands is at most six$^6$. A set $S'$ such that $\gamma_1(d^*, B) \le v(S') \le B - E(d^*, B)$ is found in constant time by a simple exhaustive search$^7$. When $0 < d^* \le B/3$, $S'$ is built by Algorithm 7 (see Section 7.2 in the appendix for the description of Algorithm 7) which runs in $O(m)$ time (see Lemma 13). Finally, Algorithm 5 retrieves $S$, solution of the original instance, from $S'$. Concretely, every demand of $S$ originally comes from a group of demands which were bundled during the execution of Algorithm 4. Thus, the task is made in $O(m^1)$ operations. Finally, Algorithm 5 runs in $O(m^1 \log m^1)$ time.

**Algorithm 5**

**Require:** A single agent instance $I \in \text{Inst}_1(d^*, B)$

**Ensure:** A subset of demands $S$ such that $\gamma_1(d^*, B) \le v(S) \le B - E(d^*, B)$

Run Algorithm 4 on $I$ in order to satisfy Hypotheses 1 and 2

The new demands, denoted by $D = \{d_1, \dots, d_m\}$, satisfy $d_1 \ge \dots \ge d_m$, where $d_1 = d^*$

$S \leftarrow \emptyset$

$S' \leftarrow \emptyset$

**if** $B/3 < d^* \le B$ **then**

Find $A \subseteq D$ such that $\gamma_1(d^*, B) \le v(A) \le B - E(d^*, B)$ by exhaustive search

$S' \leftarrow A$

**else**

$S' \leftarrow$ Algorithm 7 $(B, D)$

**end if**

Retrieve $S$ from $S'$

**return** $S$

## 4.3 Characterization for Two Agents

The goal of this section is to characterize $\rho_2(\alpha)$ and to build a solution in which the worst-off agent has utility at least $\rho_2(\alpha)B$.

When $d^* \in (B/4, B]$, the characterization of $\rho_2(\alpha)$ is immediate from Observation 1 and Lemma 6 with $n = 2$. It corresponds to $\alpha \in (1/4, 1]$ (lines 6, 7 and 8 of (6)). For $d^* \in (B/2, B]$ nothing can be guaranteed because $\rho_2(\alpha) = 0$. See Algorithm 3 for the polynomial construction of a solution which guarantees $\rho_2(\alpha)B$ to both agents when $d^* \in (B/4, B/2]$.

It remains to tackle the case $d^* \in (0, B/4]$. To do so, we characterize $\gamma_2(d^*, B)$ and the characterization of $\rho_2(\alpha)$ follows because $\gamma_2(d^*, B) = \rho_2(\alpha)B$. The proof is split into two parts, whether $d^* \in (0, B/6]$ or $d^* \in (B/6, B/4]$. These cases correspond to $\alpha \in (0, 1/6]$ (lines 1 and 2 of (6)), and $\alpha \in (1/6, 1/4]$ (lines 3, 4 and 5 of (6)), respectively.

Thereafter $B'$ denotes the semi-budget, namely $B' := B/2$. We suppose without loss of generality that agent 1 (also denoted by $A1$) has a demand of value $d^*$. $A2$ stands for agent 2 and we denote by $d_2^*$ her largest demand, namely $d_2^* := \max(D^2)$. Algorithm 6 describes how to build a solution in which the worst-off agent has utility at least $\rho_2(\alpha)B$ when $d^* \in (0, B/4]$. Note that Algorithm 6 is polynomial because Algorithm 5 and Algorithm 1 are polynomial. Thus, it remains to prove the correctness of Algorithm 6: see Sections 4.3.1 and 4.3.2 for $d^* \in (0, B/6]$ and $d^* \in (B/6, B/4]$, respectively.

Let us give two intermediate results related to $\gamma_1$ (Lemmas 7 and 8) before proving the characterization (6) of $\gamma_2(d^*, B)$.

<footnote>$^6$When $d^* > B/3$, each demand is greater than $B/6$ by Hypothesis 1. Then, 6 demands necessarily exceed the budget, and by Hypothesis 2, we cannot have more than 6 demands. Thus, the exhaustive search tests at most $2^6$ sets of demands and runs in constant time.</footnote>

<footnote>$^7$Such a demand set exists by definition of $E$</footnote>
**Algorithm 6**

**Require:** Budget $B$ and demand sets $D^j$ for all $j \in \{1, 2\}$ satisfying (1) and (2)

$B' \leftarrow B/2$

$$
\text{Let } \Delta := \begin{cases} \frac{25d^*-11B'}{13}, & \text{if } \frac{11}{25}B' < d^* \le \frac{8}{17}B' \text{ and } \frac{B'}{3} < d_2^* \\ B' - 2d^*, & \text{if } \frac{8}{17}B' < d^* < B'/2 \text{ and } \frac{B'}{3} < d_2^* \\ 0, & \text{otherwise} \end{cases}
$$

$B^{A1} \leftarrow B' - \Delta$

Use Algorithm 5 to build $S^1 \subseteq D^1$ of value at least $\gamma_1(d^*, B^{A1})$ such that $E(d^*, B^{A1})$ is saved

$B^{A2} \leftarrow B' + \Delta + E(d^*, B^{A1})$

Use Algorithm 1 to build $S^2 \subseteq D^2$ of value at least $\gamma_1(d_2^*, B^{A2})$

$\textbf{return} (S^1, S^2)$

**Lemma 7.** It holds that:

(i) $\gamma_B : x \mapsto \gamma_1(x, B)$ is increasing on each interval $\mathcal{I}_k^1(B)$.

(ii) $\gamma_{d^*} : t \mapsto \gamma_1(d^*, t)$ is a non-decreasing function.

(iii) For any $k' > k \ge 2$ and $x \in \mathcal{I}_k^1(B)$, $x' \in \mathcal{I}_{k'}^1(B)$ it holds that $\gamma_1(x, B) \le \gamma_1(x', B)$.

*Proof.* (i) Using (8), $\gamma_1(d^*, B)$ can be re-written as: $\gamma_1(d^*, B) = \frac{1}{k}d^* + \frac{k-1}{k}B$ for any $d^* \in \mathcal{I}_k^1(B)$. Thus, on each interval $\mathcal{I}_k^1(B)$, $\gamma_B$ is a linear function with a positive slope.

(ii) Let $d^*, B_1$ and $B_2$ be three real numbers that verify $d^* \le B_1 \le B_2$. We want to show that $\gamma_1(d^*, B_1) \le \gamma_1(d^*, B_2)$. Let $I \in \text{Inst}_1(d^*, B_2)$ and consider the instance $I'$ where the budget is $B_1$ and $D_{I'} = D_I$. Since, $I$ verifies (1), (2), and $d^* \le B_1$, $I'$ verifies (1) and (2) as well. Thus, $I' \in \text{Inst}_1(d^*, B_1)$ and by definition of $\gamma_1$ there exists a subset of demands $S \subset D_{I'}$ such that $\gamma_1(d^*, B_1) \le v(S) \le B_1$. Since $D_I = D_{I'}$ and $B_1 \le B_2$, this solution is also feasible with respect to $B_2$. Thus, given any instance of $\text{Inst}_1(d^*, B_2)$, there always exists a solution with a value at least $\gamma_1(d^*, B_1)$, which proves that $\gamma_1(d^*, B_1) \le \gamma_1(d^*, B_2)$ and that $\gamma_{d^*}$ is a non-decreasing function.

(iii) Let $x \in \mathcal{I}_k^1(B)$ and $x' \in \mathcal{I}_{k'}^1(B)$ be such that $k' > k \ge 2$. By (8) we have $\gamma_1(x', B) - \gamma_1(x, B) = \frac{(k'-1)B+x'}{k'} - \frac{(k-1)B+x}{k} = B(\frac{k'-1+\frac{x'}{B}}{k'} - \frac{k-1+\frac{x}{B}}{k})$. Then, since $x \in \mathcal{I}_k^1(B)$ and $x' \in \mathcal{I}_{k'}^1(B)$, this last quantity is greater than or equal to $B(\frac{k'-1+\frac{1}{k'+1}}{k'} - \frac{k-1+\frac{1}{k}}{k}) = B(\frac{k'}{k'+1} - \frac{k^2-k+1}{k^2}) = B(\frac{k^2k'-k^2(k'+1)+k(k'+1)-k'-1}{k^2(k'+1)}) = B(\frac{(k-1)(k'+1)-k^2}{k^2(k'+1)})$. We want to show that this term is positive. We can focus on $(k-1)(k'+1) - k^2$ which is the only term that could be negative. We have $(k-1)(k'+1) - k^2 \ge 0 \Leftrightarrow k' \ge k + \frac{1}{k-1}$ which is always true when $k \ge 2$ since $k' > k \Leftrightarrow k' \ge k + 1$. $\square$

In the sequel, we use the following result multiple times where $t_{B,k} := \lim_{x \to B/(k+1)+} \gamma_1(x, B)$ for any $k \ge 2$.

**Lemma 8.** For any $k \ge 2$ we have that $\inf_{x \le \frac{B}{k}} \gamma_1(x, B) = t_{B,k} = \frac{k}{k+1}B$.

*Proof.* When $k \ge 2$, we have by Lemma 7-(iii) that $\gamma_1(x, B) \le \gamma_1(x', B)$ for any $x \in \mathcal{I}_k^1(B)$ and $x' \in (0, \frac{B}{k+1}]$. Thus, we get that $\inf_{x \le \frac{B}{k}} \gamma_1(x, B) = \inf_{x \in \mathcal{I}_k^1(B)} \gamma_1(x, B)$ for any $k \ge 2$. Since by Lemma 7-(i) $\gamma_B : x \mapsto \gamma_1(x, B)$ is an increasing function on $\mathcal{I}_k^1(B)$, we directly get that $\inf_{x \in \mathcal{I}_k^1(B)} \gamma_1(x, B) = t_{B,k}$. The expression of $t_{B,k}$ simply comes by taking $d^* = \frac{B}{k+1}$ in (8). Thus, $\inf_{x \le \frac{B}{k}} \gamma_1(x, B) = t_{B,k}$. $\square$

**4.3.1 When $d^* \in (0, B/6]$**

In this section we suppose that $d^* \in \mathcal{I}_k^1(B') = \mathcal{I}_k^2(B)$ (recall that $B' = B/2$) with $k > 2$, which corresponds to $d^* \in (0, B/6]$. Based on the characterization of $E(d^*, B)$ given in Theorem 2 (first two lines), we will distinguish two cases: $\frac{B'}{k+1} < d^* \le \frac{k+1}{k^2+k+1}B'$ and $\frac{k+1}{k^2+k+1}B' < d^* \le \frac{B'}{k}$.

**Lemma 9.** It holds that $\gamma_2(d^*, B) \ge \gamma_1(d^*, B')$ when $\frac{B'}{k+1} < d^* \le \frac{k+1}{k^2+k+1}B'$.
Proof. Suppose that we assign half of the budget to A1, as indicated in Algorithm 6. Then, there exists a solution guaranteeing $\gamma_1(d^*, B')$ to her, and $E(d^*, B')$ can be saved from the budget of A1 (use Algorithm 5 to build such a solution). Thus, we can reserve a budget of $B^{A2} = B' + E(d^*, B')$ for the second agent. Theorem 2 gives

$$B^{A2} \geq B - \frac{k+1}{k}(B' - d^*). \qquad (11)$$

Then, we can guarantee $\gamma_1(d_2^*, B^{A2})$ to the second agent (use Algorithm 1). Because $d_2^* \leq d^* \leq \frac{B'}{k} \leq \frac{B^{A2}}{k}$, we get $\gamma_1(d_2^*, B^{A2}) \geq \frac{k}{k+1} B^{A2}$ by Lemma 8. Furthermore, by using (11) and (8), we can verify that $\frac{k}{k+1} B^{A2} \geq \gamma_1(d^*, B')$. Indeed, by (11) it holds that $\frac{k}{k+1} B^{A2} \geq \frac{k}{k+1} B - (B' - d^*)$. Then we have that $\frac{k}{k+1} B - (B' - d^*) \geq \gamma_1(d^*, B') \Leftrightarrow \frac{k}{k+1} B - (B' - d^*) \geq d^* + \frac{k-1}{k}(B' - d^*) \Leftrightarrow d^* \geq \frac{B'}{k+1}$, which is true by hypothesis. The fact that $\gamma_1(d_2^*, B^{A2}) \geq \gamma_1(d^*, B')$ ensures that we can guarantee at least $\gamma_1(d^*, B')$ to both agents, i.e., $\gamma_2(d^*, B) \geq \gamma_1(d^*, B')$, when $\frac{B'}{k+1} < d^* \leq \frac{k+1}{k^2+k+1} B'$. $\square$

**Lemma 10.** We have the following lower bounds on $\gamma_2(d^*, B)$ when $\frac{k+1}{k^2+k+1} B' < d^* \leq \frac{B'}{k}$.

$$\gamma_2(d^*, B) \geq \begin{cases} \gamma_1(d^*, B'), & \text{if } \frac{(k+1)B'}{k^2+k+1} < d^* \leq \frac{(k^2+1)B'}{k^3+k+1} \\ \frac{k}{k+1}(B - kd^*), & \text{if } \frac{(k^2+1)B'}{k^3+k+1} < d^* \leq \frac{B'}{k} \end{cases}$$

*Proof.* Let $B^{A1} = B'$, as indicated in Algorithm 6 (note that $\Delta = 0$ when $d^* \leq \frac{1}{6}B < \frac{11}{50}B$). Use Algorithm 5 to select a subset $S^1$ of agent 1's demands so that:

$$v(S^1) \geq \gamma_1(d^*, B'). \qquad (12)$$

At least $E(d^*, B') = B' - kd^*$ is saved according to Theorem 2. This quantity is added to the budget of agent 2.

$$B^{A2} = B' + E(d^*, B') = B - kd^* \qquad (13)$$

Knowing this, we can select with Algorithm 1 a subset of agent 2's demands $S^2$ such that $v(S^2) \geq \gamma_1(d_2^*, B^{A2})$. Here again, since $B' \leq B^{A2}$ and $d_2^* \leq d^* \leq \frac{B'}{k}$ we get that $d_2^* \leq \frac{B^{A2}}{k}$. Thus, we can apply Lemma 8 and get that $v(S^2) \geq \frac{k}{k+1} B^{A2}$. It follows from (13) that

$$v(S^2) \geq \frac{k}{k+1}(B - kd^*). \qquad (14)$$

In addition, we obtain from (8) that

$$\frac{k}{k+1}(B - kd^*) < \gamma_1(d^*, B') \iff d^* > \frac{k^2+1}{k^3+k+1} B'. \qquad (15)$$

Note that we always have $\frac{k^2+1}{k^3+k+1} B' \in (\frac{(k+1)B'}{k^2+k+1}, \frac{B'}{k}]$. Indeed, it holds that $k(k^2+1) \leq k^3 + k + 1$ and $(k+1)(k^3 + k + 1) < (k^2+1)(k^2 + k + 1) \Leftrightarrow k < k^2$. Finally, the expected result follows from (12), (14) and (15). $\square$

Lemmas 9 and 10 provide the following lower bounds on $\gamma_2(d^*, B)$ when $d^* \in \mathcal{I}_k^2(B)$ and $k > 2$. These lower bounds are obtained with the solution returned by Algorithm 6.

$$\gamma_2(d^*, B) \geq \begin{cases} \gamma_1(d^*, B'), & \text{for } \frac{1}{k+1} B' < d^* \leq \frac{k^2+1}{k^3+k+1} B' \\ \frac{k}{k+1}(B - kd^*), & \text{for } \frac{k^2+1}{k^3+k+1} B' < d^* \leq \frac{1}{k} B' \end{cases} \qquad (16)$$

**Corollary 2.** For $k > 2$ and $\alpha \in \mathcal{I}_k^2$ it holds that

$$\rho_2(\alpha) = \begin{cases} \frac{k-1+2\alpha}{2k}, & \text{if } \frac{1}{2(k+1)} < \alpha \leq \frac{k^2+1}{2(k^3+k+1)} \\ \frac{k(1-k\alpha)}{k+1}, & \text{if } \frac{k^2+1}{2(k^3+k+1)} < \alpha \leq \frac{1}{2k} \end{cases}.$$
<figure><img src="image_6.png" /><figcaption>Figure 5: $\gamma_1$ and $b$ for $B = 1$ and $d^* \in [\frac{1}{6}, \frac{1}{4}]$.</figcaption></figure>

*Proof.* We obtain $\rho_2(\alpha) \ge \frac{k-1+2\alpha}{2k}$ if $\frac{1}{2(k+1)} < \alpha \le \frac{k^2+1}{2(k^3+k+1)}$, and $\rho_2(\alpha) \ge \frac{k(1-k\alpha)}{k+1}$ if $\frac{k^2+1}{2(k^3+k+1)} < \alpha \le \frac{1}{2k}$ from (16) with the help of $\rho_2(\alpha)B = \gamma_2(d^*, B)$, $B' = B/2$, $d^* = \alpha B$, and the definition of $\gamma_1$ given in (8). Conversely, we know that $\rho_2(\alpha) \le \frac{k-1+2\alpha}{2k}$ if $\frac{1}{2(k+1)} < \alpha \le \frac{k^2+1}{2(k^3+k+1)}$, and $\rho_2(\alpha) \le \frac{k(1-k\alpha)}{k+1}$ if $\frac{k^2+1}{2(k^3+k+1)} < \alpha \le \frac{1}{2k}$ from Proposition 1 where $n = 2$. $\square$

Thus, Corollary 2 gives a characterization of $\rho_2(\alpha)$ when $\alpha \in (0, B/6]$ as claimed in (6), and Algorithm 6 produces a solution where the utility of the worst-off agent is at least $\rho_2(\alpha)B$ when $\alpha \in (0, B/6]$.

### 4.3.2 When $d^* \in (B/6, B/4]$

Now we consider the case where $k = 2$, $d^* \in \mathcal{I}_2^1(B') = \mathcal{I}_2^2(B)$, which corresponds to $d^* \in (B/6, B/4] = (B'/3, B'/2]$. The bounds are obtained with the solution built by Algorithm 6 where $\Delta$ is as defined as follows.

$$ \Delta := \begin{cases} 0, & \text{for } \frac{1}{3}B' < d^* \le \frac{11}{25}B' \\ \frac{25d^* - 11B'}{13}, & \text{for } \frac{11}{25}B' < d^* \le \frac{8}{17}B' \\ B' - 2d^*, & \text{for } \frac{8}{17}B' < d^* \le \frac{1}{2}B' \end{cases} $$

Note that

$$ 0 \le \Delta \le B' - 2d^* \quad (17) $$

is always true.

**Lemma 11.** For $d^* \in \mathcal{I}_2^1(B')$, it holds that

$$ \gamma_2(d^*, B) \ge b(d^*, B) := \begin{cases} \gamma_1(d^*, B'), & \text{for } B'/3 < d^* \le \frac{11}{25}B' \\ \gamma_1(d^*, B' - \Delta), & \text{for } \frac{11}{25}B' < d^* \le \frac{8}{17}B' \\ \frac{4}{3}(B' - d^*), & \text{for } \frac{8}{17}B' < d^* \le B'/2 \end{cases} $$

*Proof.* We are going to prove that the solution returned by Algorithm 6 guarantees $b(d^*, B)$ to both agents. Let us first observe that

$$ b(d^*, B) \le \gamma_1(d^*, B') \quad (18) $$

holds for any $d^* \in [B/6, B/4]$. Indeed, given that $t \mapsto \gamma_1(x, t)$ is a non-decreasing function for a fixed $x$ (see Lemma 7-(ii)) and the fact that $\Delta \ge 0$, Inequality (18) is clear for $d^* \le \frac{8}{17}B'$. When $d^* > \frac{8}{17}B'$, we have $\frac{4}{3}(B' - d^*) \le d^* + (B' - d^*)/2 = \gamma_1(d^*, B') \Leftrightarrow d^* \ge \frac{5}{11}B'$ which holds because $\frac{8}{17} > \frac{5}{11}$.

In order to prove Lemma 11, we have to show that $\gamma_2(d^*, B) \ge b(d^*, B)$. A case study is conducted.
Suppose that $d_2^* \le \frac{1}{3}B'$. In Algorithm 6, a budget of $B'$ is given to A1, the second agent receives at least $B'$ ($\Delta = 0$ in this case). Then, we can guarantee $v(S^1) \ge \gamma_1(d^*, B')$ to A1 and $v(S^2) \ge \gamma_1(d_2^*, B')$ to A2. Since $d_2^* \le \frac{1}{3}B'$ and $d^* > \frac{1}{3}B'$, we have $\gamma_1(d_2^*, B') \ge \gamma_1(d^*, B')$ by Lemma 7 - (iii). Thus, the worst-off agent gets at least $\gamma_1(d^*, B')$. By (18), we obtain in particular $\min(v(S^1), v(S^2)) \ge b(d^*, B)$ for any instance where $d_2^* \le \frac{1}{3}B'$.

From now on we suppose that $\frac{1}{3}B' < d_2^* \le d^*$. Since $x \mapsto \gamma_1(x, B')$ is increasing when $B'/3 < x \le B'/2$ (see Lemma 7 - (i)), we have that $\gamma_1(d^*, B') \ge \gamma_1(d_2^*, B')$. This means that the guarantee of A1 would be better than the one of A2 if the same budget $B'$ were allocated to both agents. That is why in Algorithm 6 the budget of A1 is decreased by $\Delta$, while the budget of A2 is increased.

Suppose that $d^* \le \frac{7}{17}B'$. A budget of $B^{A1} = B'$ is given to A1 in Algorithm 6 (since $\frac{7}{17} \le \frac{11}{25}$). Using Algorithm 6, at least $E(d^*, B^{A1})$ is saved while guaranteeing $\gamma_1(d^*, B^{A1})$ to A1, and one can give a budget of $B^{A2} = B' + E(d^*, B^{A1})$ to A2. Algorithm 6 guarantees at least $\gamma_1(d^*, B^{A1})$ to A1 and $\gamma_1(d_2^*, B^{A2})$ to A2. Let us show that $\gamma_1(d_2^*, B^{A2}) \ge \gamma_1(d^*, B^{A1})$ when $B'/3 < d_2^* \le d^* \le \frac{7}{17}B'$. Since $B^{A2} = B' + E(d^*, B')$, we have that

$$ 
\begin{align*}
\gamma_1(d_2^*, B^{A2}) &\ge t_{B^{A2}, 2} = \frac{2}{3}B^{A2} \quad (\text{by Lemma 8 because } d_2^* \le d^* \le B'/2 \le B^{A2}/2) \\
&= \frac{2}{3}(B' + E(d^*, B')) = \frac{2}{3}(B' + \frac{1}{2}(3d^* - B')) \\
&= \frac{1}{3}(3d^* + B') \ge \gamma_1(d^*, B').
\end{align*}
$$

The second line is due to Theorem 2 and $d^* \le 7B'/17$, whereas the third line comes from (8) and $d^* > \frac{B'}{3}$. Indeed, we have $\frac{1}{3}(3d^* + B') \ge \gamma_1(d^*, B') \Leftrightarrow \frac{1}{3}(3d^* + B') \ge \frac{B'+d^*}{2} \Leftrightarrow 6d^* + 2B' \ge 3B' + 3d^* \Leftrightarrow 3d^* \ge B'$ which is true since $d^* > B'/3$. Therefore, one can guarantee $\gamma_1(d^*, B')$ to both agents. It follows that $\gamma_2(d^*, B) \ge \gamma_1(d^*, B')$ for all $d^* \in (\frac{1}{3}B', \frac{7}{17}B']$.

Now suppose that $\frac{7}{17}B' < d^* \le \frac{11}{25}B'$. As in the previous case, the reserved budgets are $B^{A1} = B'$ and $B^{A2} = B' + E(d^*, B^{A1})$. By the same reasoning, we can verify that $\gamma_1(d_2^*, B^{A2}) \ge \gamma_1(d^*, B^{A1})$ for all $d_2^* \le d^*$, which gives $\gamma_2(d^*, B) \ge \gamma_1(d^*, B')$ for all $d^* \in (\frac{7}{17}B', \frac{11}{25}B']$.

Suppose that $\frac{11}{25}B' < d^* \le \frac{8}{17}B'$. Algorithm 6 indicates that $\Delta = \frac{25d^*-11B'}{13}$. We have $B^{A1} = B' - \Delta$ and $\frac{11}{25}B' < d^* \le \frac{8}{17}B' \Rightarrow \frac{B'-\Delta}{3} < d^* \le \frac{B'-\Delta}{2}$ when $\Delta = \frac{25d^*-11B'}{13}$, which means that $d^* \in \mathcal{I}_2^1(B' - \Delta)$. Thus, according to (8), the guarantee of A1 is $\gamma_1(d^*, B' - \Delta) = d^* + (B' - \Delta - d^*)/2$. We have $E(d^*, B' - \Delta) = \frac{2}{3}(B' - \Delta - 2d^*)$ by Theorem 2 because $d^* > \frac{11}{25}B' \Rightarrow d^* > \frac{7}{17}(B' - \Delta)$, see footnote<fnref n="8" /> for an explanation, and we have just seen that $d^* \le \frac{B'-\Delta}{2}$. Thus, $B^{A2} = B' + \Delta + \frac{2}{3}(B' - \Delta - 2d^*)$. Since $d_2^* \le \frac{B'+\Delta+\frac{2}{3}(B' - \Delta - 2d^*)}{2}$, we know from Lemma 8 that the guarantee of A2 is at least $\frac{2}{3}(B' + \Delta + \frac{2}{3}(B' - \Delta - 2d^*))$. It turns out that $d^* + (B' - \Delta - d^*)/2$ is equal to $\frac{2}{3}(B' + \Delta + \frac{2}{3}(B' - \Delta - 2d^*))$ when $\Delta = \frac{25d^*-11B'}{13}$. Therefore, $\gamma_1(d^*, B' - \Delta) = d^* + (B' - \Delta - d^*)/2 = b(d^*, B)$ is guaranteed to both agents.

Suppose that $\frac{8}{17}B' < d^* \le \frac{B'}{2}$. Algorithm 6 indicates that $\Delta = B' - 2d^*$. Thus, $B^{A1} = B' - (B' - 2d^*) = 2d^*$. By (8), the guarantee of A1 is $\gamma_1(d^*, 2d^*) = d^* + (2d^* - d^*)/2 = 3d^*/2$. Thus, $B^{A2} \ge B' + B' - 2d^* = 2(B' - d^*)$. The guarantee of A2 is at least $\gamma_1(d_2^*, 2(B' - d^*))$. Since $d_2^* \le d^* \le B'/2$, it holds that $d_2^* \le B' - d^*$. Thus, we know from Lemma 8 that $\gamma_1(d_2^*, 2(B' - d^*)) \ge \frac{2}{3}(2(B' - d^*)) = \frac{4}{3}(B' - d^*)$. Since $\frac{8}{17}B' < d^* \Leftrightarrow \frac{4}{3}(B' - d^*) < \frac{3}{2}d^*$, we deduce that both agents have utility at least $\frac{4}{3}(B' - d^*) = b(d^*, B)$.

To conclude, $\gamma_2(d^*, B) \ge b(d^*, B)$ holds because we can guarantee $b(d^*, B)$ to both agents.

<figure><img src="image_7.png" /></figure>

Now, Lemma 11 allows us to conclude on the value of $\rho_2(\alpha)$ when $\alpha \in (\frac{1}{6}, \frac{1}{4}]$.

**Corollary 3.** It holds that

$$ \rho_2(\alpha) = \begin{cases} 1/4 + \alpha/2, & \text{if } 1/6 < \alpha \le 11/50 \\ \frac{6}{13}(1 - \alpha), & \text{if } 11/50 < \alpha \le 4/17 \\ 2/3 - 4\alpha/3, & \text{if } 4/17 < \alpha \le 1/4 \end{cases}. $$

<footnote n="8">⁸This comes from the fact that $\Delta > 0$ and $\frac{11}{25} > \frac{7}{17}$</footnote>

<footnote n="9">⁹By (17), it holds that $B' \le B' + \Delta + \frac{2}{3}(B' - \Delta - 2d^*)$. Thus we have $d_2^* \le d^* \le \frac{8}{17}B' \le B'/2 \le \frac{B'+\Delta+\frac{2}{3}(B' - \Delta - 2d^*)}{2}$.</footnote>
Proof. In the cases where $1/6 < \alpha \le 11/50$ and $4/17 < \alpha \le 1/4$ the lower bounds on $\rho_2(\alpha)$ are immediate from Lemma 11 where $B' = B/2$, $d^* = \alpha B$, $\gamma_2(d^*, B) = \rho_2(\alpha)B$, and the definition of $\gamma_1$ given in (8) with $k = 2$. Now we focus on the case where $11/50 < \alpha \le 4/17$. By Lemma 11, when $\frac{11}{25}B' < d^* \le \frac{8}{17}B'$, it holds that

$$
\begin{align*}
\gamma_2(d^*, B) &\ge \frac{1}{2}(B' - \Delta - d^*) \\
&= \frac{1}{2}(B' - \frac{25d^* - 11B'}{13} - d^*) = d^* + \frac{24B' - 38d^*}{26} \\
&= \frac{24B' - 12d^*}{26} = \frac{6B - 6d^*}{13} = \frac{6}{13}(1 - \frac{d^*}{B})B, \\
\gamma_2(d^*, B) &\ge \frac{6}{13}(1 - \alpha)B.
\end{align*}
$$

It follows that $\rho_2(\alpha) \ge \frac{6}{13}(1 - \alpha)$ when $\frac{11}{25}B' < d^* \le \frac{8}{17}B'$.

These lower bounds can be paired with matching upper bounds as follows. Use Proposition 1 with $n = k = 2$ to get that $\rho_2(\alpha) \le 1/4 + \alpha/2$ if $1/6 < \alpha \le 5/22$, and $\rho_2(\alpha) \le 2/3 - 4\alpha/3$ if $5/22 < \alpha \le 1/4$. Since $11/50 < 5/22 < 4/17$, it follows that

$$
\rho_2(\alpha) \le \begin{cases} 1/4 + \alpha/2, & \text{if } 1/6 < \alpha \le 11/50 \\ 2/3 - 4\alpha/3, & \text{if } 4/17 < \alpha \le 1/4 \end{cases} .
$$

The remaining part is obtained with the following instance.

**Instance 5.** Suppose $B = 17 - \delta$ with $\delta \in [0, 1/3]$. Agent 1 has 4 demands of values $4 - \delta, 2 + \epsilon, 2 + \epsilon$, and 2, where $1 \gg \epsilon > 0$. Agent 2 has 3 demands, each of value 3. Thus, $\alpha = \frac{4-\delta}{17-\delta}$ and $\alpha \in [11/50, 4/17]$.

If we accept 1, 2 or 3 demands of agent 2 then she gets 3, 6, or 9, respectively. An exhaustive search of all the
possible subsets of demands for agent 1 provides the following positive amounts: 2, 2 + ϵ, 4 − δ, 4 + ϵ, 4 + 2ϵ, 6 − δ,
6 − δ + ϵ, 6 + 2ϵ, 8 − δ + ϵ, 8 − δ + 2ϵ, and 10 − δ + 2ϵ. If we accept the 3 demands of agent 2, then the remaining
budget is 8 − δ. In that case we can give at most 6 + 2ϵ to agent 1. If we accept two demands of agent 2 then she gets 6.
The best guarantee for this instance when ϵ → 0 is 6/17−δ. Since 6/17−δ = 6/13(1 − α) when α = 4−δ/17−δ, the best guarantee
for this instance is 6/13(1 − α) when α ∈ [11/50, 4/17]. Thus, we can conclude that ρ₂(α) ≤ 6/13(1 − α) if 11/50 < α ≤ 4/17. □

Therefore, Corollary 3 gives the characterization of $\rho_2(\alpha)$ when $\alpha \in (1/6, 1/4]$ as claimed in (6), and Algorithm 6 produces a solution where the utility of the worst-off agent is at least $\rho_2(\alpha)B$ when $\alpha \in (1/6, 1/4]$.

5 Accuracy

So far we have presented a characterization of $\rho_n$ when $n \in \{1, 2\}$. When $n > 2$, we have an optimal non-increasing function $\tilde{\rho}_n$ which constitutes a lower bound on $\rho_n$, and some families of instances which give upper bounds on $\rho_n$. Thus, an interesting question is to evaluate the distance between these bounds, and see if they provide an accurate approximation of $\rho_n$.

For $n$ agents, let $\text{Acc}(n)$ be the accuracy of our bounds on $\rho_n$. It is defined as the largest ratio between the best known lower bound and the best known upper bound.

$$
\text{Acc}(n) = \sup_{\alpha \in (0, 1/n]} \frac{\text{best known lower bound on } \rho_n(\alpha)}{\text{best known upper bound on } \rho_n(\alpha)}.
$$

We exclude $\alpha \in (\frac{1}{n}, 1] = \mathcal{I}_0^n$ in the definition of $\text{Acc}(n)$ because we know that $\rho_n(\alpha) = 0$ on $\mathcal{I}_0^n$ (see Observation 1). The accuracy is between 0 and 1. The closer to 1 the better the accuracy. Having $\text{Acc}(n) = 1$ would mean that we have a characterization of $\rho_n$.

**Proposition 2.** *Acc*(n) restricted to *I*<sub>*k*</sub><sup>*n*</sup> is equal to <sup>(n−1)(k+1)+k<sup>3</sup></sup>⁄<sub>(n−1)(k+1)+k<sup>3</sup>+1</sub>.
Proof. As our bounds on $\rho_n$ are tight in $\mathcal{I}_1^n \cup \mathcal{I}_0^n$ (c.f. Lemma 6 for $\mathcal{I}_1^n$), the largest ratio between lower and upper bound occurs for some $\alpha \in \mathcal{I}_k^n$ with $k \ge 2$. Instance 2 provides an upper bound of $\frac{(k-1)/n+\alpha}{k}$ in $(\frac{1}{n(k+1)}, \frac{k^2+n-1}{n((n-1)(k+1)+k^3)}}] \subset \mathcal{I}_k^n$ which increases with $\alpha$. Instance 3 provides an upper bound of $\frac{k(1-k\alpha)}{(n-1)(k+1)}$ in $(\frac{1}{nk+n-1}, \frac{1}{nk}] \subset \mathcal{I}_k^n$ which decreases with $\alpha$. These upper bounds intersect at $\alpha_{n,k} := \frac{k^2+n-1}{n((n-1)(k+1)+k^3)}$. Our lower bound on $\rho_n$ in $\mathcal{I}_k^n$ is $\tilde{\rho}_n(\alpha) = \frac{k}{n(k+1)}$, which is independent of $\alpha$. Thus, the accuracy restricted to $\mathcal{I}_k^n$ is $\frac{k}{n(k+1)} \frac{k}{(k-1)/n+\alpha_{n,k}}$. After some omitted calculations, we get a ratio of $\frac{(n-1)(k+1)+k^3}{(n-1)(k+1)+k^3+1}$. $\square$

Since a characterization of $\rho_n$ is known for $n = 1, 2$, the worst accuracy is for $n > 2$. Following Proposition 2, the worst case occurs when $k = 2$ and $n = 3$, namely $\text{Acc}(n) \ge 14/15$. Therefore, although we do not provide a characterization of $\rho_n$ for all $n$, we have an accurate approximation of $\rho_n$ since, in the worst case, the ratio between our lower and upper bounds is a constant close to 1.

# 6 Conclusion and Future Work

The goal of this article was to study the fair division of a common budget amongst multiple agents. We obtained a characterization of $\rho_n$ for $n = 1, 2$. When $n > 2$, a characterization of $\tilde{\rho}_n$, which is the largest non-increasing part of $\rho_n$, has been given. Polynomial time algorithms outputting a solution which satisfies the bounds $\rho_1(\alpha)$, $\rho_2(\alpha)$, and $\tilde{\rho}_n(\alpha)$, have been proposed. We finally showed that our bounds $\tilde{\rho}_n$ are, in the worst case, a 14/15-approximation of $\rho_n$.

Our results are in the same spirit as [26, 18, 32, 23, 30] where a worst-case bound and a polynomial time algorithm, are provided for the fair allocation of indivisible goods or chores. As with these results, it appears that $\rho_n(\alpha)$ is close to $n^{-1}$ when $\alpha$ is small (i.e., close to 0), and $\rho_n(\alpha)$ is small when $\alpha$ is large (i.e., close to 1). As opposed to $V_n$ (the original guarantee proposed by Hill [26]), $\rho_n$ is neither a continuous nor a monotone function of $\alpha$. Our worst-case bounds are defined for a class of instances (with parameters $n$ and $\alpha$) but it does not prevent to reach a better guarantee for a fixed instance within this class (e.g. MMS).

An immediate future work would be to characterize $\rho_n$ for any number of agents, or to provide an approximation with a ratio better than 14/15. Experiments on randomly generated instances could help to identify the exact shape of $\rho_n$ for $n \ge 3$. The present work proposed a common worst-case bound and it depends on $\alpha$ defined as the largest demand (over all agents) divided by $B$. However, as done by Markakis and Psomas [32], each agent $j$ may have her own worst-case guarantee as a function of $\alpha_j$ where $\alpha_j$ is agent $j$'s largest demand divided by $B$.

A second extension of our work would be to consider the case where the agents have different rights or claims. In the concrete example of the European Union evoked in the introduction, the agents are the European countries and they have heterogeneous numbers of inhabitants. Therefore, one can think of a version of the common budget problem where each country claims a fraction $\pi(j)$ of the common budget where $\pi(j)$ corresponds to $j$'s proportion of the entire European population.

The common budget problem studied in this article is cast as a SUBSET SUM problem with multiple agents. The utility for a demand corresponds to its value. However, studying a multi-agent KNAPSACK problem where the utility for an object is not necessarily aligned with its size would be interesting [5, 19]. In that case, one needs significant parameters (analogous to $\alpha$) before determining worst-case bounds on the value of an agent. We believe that determining such significant parameters (if they exist) is not trivial, and any positive result in this direction would be of great value. In the same vein, one can think of a bi-dimensional version of the problem studied in this article. Suppose there is a common piece of land where multiple agents want to locate private facilities (see for example [39] for a recent work on the fair division of land). The problem can be to place some geometric shapes (the facilities) on a given area (the piece of land) in such a way that the shapes fit in the area and do not overlap. Then, which surface an agent is guaranteed to cover?

A possible extension of our work would be on evolving instances. Instead of having a fixed input, the demands can be made sequentially, or the budget may change over time. These hypotheses of a dynamic instance would fit with many practical situations where online algorithms and feedback mechanisms are needed. Since we have conducted a worst-case analysis of the fair allocation of a common budget, another immediate future work would be to consider algorithmic techniques to go beyond, such as the use of machine-learned predictions [38].
Finally, the strategic aspect of the common budget problem deserves attention. If the agents submit their demands to a central authority, then the selection of accepted demands should incentivize the agents to report the true values of their demands. At first glance, the fact that we accept all the demands of an agent if their sum is at most $B/n$, does not promote truthfulness. Indeed, every agent is tempted to submit her largest subset of demands which is below $B/n$. However, the agents are not necessarily aware of $B$ and $n$ when they communicate their demands.

**Acknowledgements:** Laurent Gourvès is supported by Agence Nationale de la Recherche (ANR), project THEMIS ANR-20-CE23-0018.

## References

[1] Alessandro Agnetis, Pitu B. Mirchandani, Dario Pacciarelli, and Andrea Pacifici. Scheduling problems with two competing agents. *Oper. Res.*, 52(2):229-242, 2004.

[2] Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy. A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation. *Operations Research Letters*, 48(5):573-578, 2020.

[3] Haris Aziz and Nisarg Shah. Participatory budgeting: Models and approaches. In *Pathways between Social Science and Computational Social Science*, pages 215-236. Springer International Publishing, New York, USA, 2021.

[4] Nikhil Bansal and Maxim Sviridenko. The Santa Claus problem. In *Proceedings of the 38th Annual ACM Symposium on Theory of Computing*, pages 31-40, 2006.

[5] Nawal Benabbou and Patrice Perny. Solving multi-agent knapsack problems using incremental approval voting. In *Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI'16)*, pages 1318-1326, 2016.

[6] Ivona Bezáková and Varsha Dani. Allocating indivisible goods. *SIGecom Exchanges*, 5(3):11-18, 2005.

[7] Sylvain Bouveret, Yann Chevaleyre, and Nicolas Maudet. Fair Division of Indivisible Goods. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, *Handbook of Computational Social Choice*, pages 284-310. Cambridge University Press, 2016.

[8] Sylvain Bouveret, Michel Lemaître, Hélène Fargier, and Jérôme Lang. Allocation of indivisible goods: A general model and some complexity results. In *Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'05)*, pages 1309-1310, 2005.

[9] Steven J. Brams and Alan D. Taylor. *Fair Division: From Cake-Cutting to Dispute Resolution*. Cambridge University Press, Cambridge, UK, 1996.

[10] J. Randall Brown. The knapsack sharing problem. *Operations Research*, 27(2):341-355, 1979.

[11] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. *Journal of Political Economy*, 119(6):1061-1103, 2011.

[12] Yves Cabannes. Participatory budgeting: a significant contribution to participatory democracy. *Environment and Urbanization*, 16(1):27-46, 2004.

[13] Pierre Cardi, Laurent Gourvès, and Julien Lesca. Worst-case bounds for spending a common budget. In *Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'21)*, pages 288-296, 2021.

[14] Pierre Cardi, Laurent Gourvès, and Julien Lesca. On fair and efficient solutions for budget apportionment. In *21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, Auckland, New Zealand, May 9-13, 2022*, pages 1560-1562, 2022.
[15] Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, and Yair Zick. Weighted envy-freeness in indivisible item allocation. *ACM Trans. Economics and Comput.*, 9(3):18:1–18:39, 2021.

[16] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *Introduction to Algorithms*, Third Edition. The MIT Press, Cambridge, Massachusetts, USA, 3rd edition, 2009.

[17] Andreas Darmann, Gaia Nicosia, Ulrich Pferschy, and Joachim Schauer. The subset sum game. *European Journal of Operational Research*, 233(3):539–549, 2014.

[18] Stephen Demko and Theodore P. Hill. Equitable distribution of indivisible objects. *Mathematical Social Sciences*, 16(2):145–158, 1988.

[19] Till Fluschnik, Piotr Skowron, Mervin Triphaus, and Kai Wilker. Fair knapsack. In *Proceedings of the 33rd AAAI Conference on Artificial Intelligence, (AAAI’19)*, pages 1941–1948, 2019.

[20] Duncan K. Foley. Resource allocation and the public sector. *Yale Economic Essays*, 7(1):45–98, 1967.

[21] Eric J. Friedman, Vasilis Gkatzelis, Christos-Alexandros Psomas, and Scott Shenker. Fair and efficient memory sharing: Confronting free riders. In *Proceedings of the 33rd AAAI Conference on Artificial Intelligence, (AAAI’19)*, pages 1965–1972, 2019.

[22] Michael R. Garey and David S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. W. H. Freeman, US, 1979.

[23] Laurent Gourvès, Jérôme Monnot, and Lydia Tlilane. Worst case compromises in matroids with applications to the allocation of indivisible goods. *Theoretical Computer Science*, 589:121–140, 2015.

[24] D. Ellis Hershkowitz, Anson Kahng, Dominik Peters, and Ariel D. Procaccia. District-fair participatory budgeting. In *Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021*, pages 5464–5471. AAAI Press, 2021.

[25] Mhand Hifi, Hedi M’Halla, and Slim Sadfi. An exact algorithm for the knapsack sharing problem. *Computers & Operations Research*, 32:1311–1324, 2005.

[26] Theodore P. Hill. Partitioning general probability measures. *The Annals of Probability*, 15(2):804–813, 1987.

[27] Hans Kellerer, Ulrich Pferschy, and David Pisinger. *Knapsack Problems*. Springer, Berlin, Germany, 2004.

[28] Ewa Kiryluk-Dryjska. Fair division approach for the european union’s structural policy budget allocation: An application study. *Group Decision and Negotiation*, 23:597–615, 2014.

[29] David Kurokawa, Ariel D. Procaccia, and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. *Journal of the ACM*, 65(2):8:1–8:27, 2018.

[30] Bo Li, Hervé Moulin, Ankang Sun, and Yu Zhou. On hill’s worst-case guarantee for indivisible bads. *CoRR*, abs/2302.00323, 2023.

[31] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In *Proceedings of the 5th ACM Conference on Electronic Commerce (EC’04)*, pages 125–131, 2004.

[32] Evangelos Markakis and Christos-Alexandros Psomas. On worst-case allocations in the presence of indivisible goods. In *Proceedings of the 7th International Workshop on Internet and Network Economics (WINE’11)*, volume 7090 of *Lecture Notes in Computer Science*, pages 278–289, 2011.

[33] Silvano Martello and Paolo Toth. *Knapsack Problems: Algorithms and Computer Implementations*. John Wiley & Sons, Inc., USA, 1990.
[34] Marcin Michorzewski, Dominik Peters, and Piotr Skowron. Price of fairness in budget division and probabilistic social choice. In *The 34th AAAI Conference on Artificial Intelligence (AAAI'20)*, pages 2184–2191, 2020.

[35] Hervé Moulin. Fair division in the internet age. *Annual Review of Economics*, 11(1):407–441, 2019.

[36] Astrid Pieterse and Gerhard J. Woeginger. The subset sum game revisited. In *Algorithmic Decision Theory - 5th International Conference, ADT 2017, Luxembourg, Luxembourg, October 25-27, 2017, Proceedings*, pages 228–240, 2017.

[37] Ariel D. Procaccia. Cake cutting algorithms. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, *Handbook of Computational Social Choice*, pages 311–330. Cambridge University Press, 2016.

[38] Tim Roughgarden, editor. *Beyond the Worst-Case Analysis of Algorithms*. Cambridge University Press, 2020.

[39] Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, and Yonatan Aumann. Envy-free division of land. *Mathematics of Operations Research*, 45(3):896–922, 2020.

[40] Hugo Steinhaus. The problem of fair division. *Econometrica*, 16(1):101–104, 1948.

[41] William Thomson. Chapter Twenty-One - Fair Allocation Rules. In Kenneth J. Arrow, Amartya Sen, and Kotaro Suzumura, editors, *Handbook of Social Choice and Welfare*, volume 2 of *Handbook of Social Choice and Welfare*, pages 393 – 506. Elsevier, Amsterdam, The Netherlands, 2011.

[42] Hal R. Varian. Equity, envy, and efficiency. *Journal of Economic Theory*, 9(1):63–91, 1974.

[43] Takeo Yamada and Mayumi Futakawa. Heuristic and reduction algorithms for the knapsack sharing problem. *Computers & Operations Research*, 24(10):961–967, 1997.

[44] Takeo Yamada, Mayumi Futakawa, and Seiji Kataoka. Some exact algorithms for the knapsack sharing problem. *European Journal of Operational Research*, 106(1):177–183, 1998.

# 7 Appendix: Characterization of the Budget Saving E

This section contains the proof of Theorem 2. We provide upper bounds on E followed by matching lower bounds.

## 7.1 Upper Bounding the Budget Saving E

In this section, we upper bound $E(d^*, B)$ by exhibiting several instances which all have a single agent and a budget $B$.

**Lemma 12.** *The following upper bounds on $E(d^*, B)$ hold.*

$$ E(d^*, B) \le \begin{cases} B - \frac{k+1}{k}(B - d^*), & \text{for } \frac{1}{k+1}B < d^* \le \frac{k+1}{k^2+k+1}B \text{ and } k > 2 \\ B - kd^*, & \text{for } \frac{k+1}{k^2+k+1}B < d^* \le \frac{1}{k}B \text{ and } k > 2 \\ \frac{1}{2}(3d^* - B), & \text{for } B/3 < d^* \le 7B/17 \\ \frac{2}{3}(B - 2d^*), & \text{for } 7B/17 < d^* \le B/2 \\ B - d^*, & \text{for } B/2 < d^* \le B \end{cases}. \quad (19) $$

Before giving the proof of Lemma 12, we make the following remark which will be used several times in this section.

**Remark 1.** $d^* > \frac{B-d^*}{k}$ holds when $d^* \in \mathcal{I}_k^1(B)$.
Proof. $d^* \in \mathcal{I}_k^1(B)$ implies $d^* > \frac{B}{k+1}$ from which we get $0 > B - (k+1)d^* \Leftrightarrow kB > (k+1)(B - d^*) \Leftrightarrow \frac{B}{k+1} > \frac{B-d^*}{k}$. Thus, $d^* > \frac{B}{k+1} > \frac{B-d^*}{k}$. $\square$

The proof of Lemma 12 follows.

Proof. Let us first observe that

$$E(d^*, B) \le B - d^* \text{ when } d^* \in (B/2, B]. \qquad (20)$$

To see this, consider the instance where the agent has two demands of value $d \in (B/2, B]$. In this case $d = d^* \in \mathcal{I}_k^1(B)$ with $k = 1$, and $\gamma_1(d^*, B) = d^*$ according to (8). One demand is accepted in order to guarantee $d^*$, and $B - d^*$ is saved. The expected upper bound on $E(d^*, B)$ (line 5 of (19)) is obtained.

Afterwards, we note that

$$E(d^*, B) = 0 \text{ when } d^* = B/2. \qquad (21)$$

In this case $d^* \in \mathcal{I}_k^1(B)$ with $k = 2$, and $\gamma_1(d^*, B) = \frac{3}{4}B$ according to (8). Consider the instance where the agent has 3 demands of value $B/2$. In order to guarantee $\frac{3}{4}B$, two demands must be accepted and nothing can be saved.

Because of (10), upper bounding $E(d^*, B)$ is equivalent to lower bounding $R(d^*, B)$. We are going to consider three other instances where $\epsilon > 0$. Because the case $d^* = B/2$ is already covered by (21), we can suppose that $d^* < B/2$ when $d^* \in \mathcal{I}_2^1$.

**Instance 6.** Consider that $d^* \in \mathcal{I}_k^1(B)$ for $k \ge 2$ and $d^* < B/2$. The demands are the following.

$$\left\{ \begin{array}{l} d_1^1 = d^* \\ d_j^1 = \frac{1}{k}(B - d^*) - \epsilon \quad \text{for } j = 2, \dots, k+2 \end{array} \right.$$

Thereafter, $I_6$ refers to Instance 6. Note that $I_6$ is valid, meaning that $v(D_{I_6}) > B$ and the largest demand is valued $d^*$. The latter is clear by Remark 1. In addition, we have

$$v(D_{I_6}) = d^* + \frac{k+1}{k}(B-d^*) - (k+1)\epsilon = B + \frac{1}{k}(B-d^*) - (k+1)\epsilon$$

which is larger than $B$ for $\epsilon$ sufficiently small since $B > d^*$.

We are going to show that

$$v(R_{I_6}) = \frac{k+1}{k}(B-d^*) - (k+1)\epsilon \qquad (22)$$

for $k \ge 2$ and $\epsilon > 0$ sufficiently small.

If $d_1^1$ of value $d^*$ belongs to $R_{I_6}$, then note that $d^* + d_2^1 + \dots + d_k^1 = d^* + \frac{k-1}{k}(B - d^*) - (k-1)\epsilon < \gamma_1(d^*, B) = d^* + \frac{k-1}{k}(B - d^*)$ and $d^* + d_2^1 + \dots + d_{k+1}^1 = B - k\epsilon > \gamma_1(d^*, B)$ for $\epsilon$ sufficiently small. Thus, we would have $R_{I_6} = \{d^*, d_2^1, \dots, d_{k+1}^1\}$ and $v(R_{I_6}) = B - k\epsilon$. We then have a first candidate $S_1 = \{d^*, d_2^1, \dots, d_{k+1}^1\}$ with a value of $B - k\epsilon$. Now, let us build a second candidate $S_2$ such as $d^* \notin S_2$. First, it holds that

$$B - d^* < \gamma_1(d^*, B) < \frac{k+1}{k}(B - d^*). \qquad (23)$$

Indeed, we can verify by (8) that $B - d^* < \gamma_1(d^*, B) \Leftrightarrow \frac{1}{k}(B - d^*) < d^*$, which is true by Remark 1. One can also see that $\frac{k+1}{k}(B - d^*) > \gamma_1(d^*, B) \Leftrightarrow \frac{2}{k}(B - d^*) > d^* \Leftrightarrow d^* < \frac{2}{k+2}B$. If $k = 2$ then we get $d^* < \frac{B}{2}$ which is true by assumption in Instance $I_6$. Otherwise $d^* \in \mathcal{I}_k^1 = (\frac{B}{k+1}, \frac{B}{k}]$ with $k > 2$, which means that $d^* \le \frac{B}{k}$ and $\frac{B}{k} < \frac{2B}{k+2} \Leftrightarrow k > 2$. The left hand (resp., right hand) side of (23) corresponds to the value of $k$ (resp., $k+1$) demands within $\{d_2^1, \dots, d_{k+2}^1\}$ when $\epsilon$ goes to zero. This means that $S_2 = \{d_2^1, \dots, d_{k+2}^1\}$.

Now, we just have to compare $v(S_1)$ with $v(S_2)$. $v(S_1) > v(S_2)$ is clear given that $S_1$ can be obtained by replacing $d_{k+2}^1$ by $d^*$ in $S_2$ and $d^* > d_{k+2}^1$. Thus, we get (22) for $\epsilon$ sufficiently small.

**Instance 7.** Consider that $d^* \in \mathcal{I}_k^1(B)$ for $k > 2$. The demands are $d_j^1 = d^*$ for $j = 1, \dots, k+1$.
Let $I_7$ denote Instance 7 which is valid since $d^* > \frac{1}{k+1}B$. We going to show that for $k > 2$ and $\epsilon > 0$ sufficiently small, we have

$$v(R_{I_7}) = kd^*. \qquad (24)$$

To this end, we want to verify that

$$(k-1)d^* < \gamma_1(d^*, B) \le kd^*. \qquad (25)$$

Using (8) and Remark 1, it holds that $\gamma_1(d^*, B) \le kd^*$. In addition, we have $(k-1)d^* < \gamma_1(d^*, B) = d^* + \frac{k-1}{k}(B - d^*) \Leftrightarrow (k-2)d^* < \frac{k-1}{k}(B - d^*) \Leftrightarrow k(k-2)d^* < (k-1)B - (k-1)d^* \Leftrightarrow (k^2 - k - 1)d^* < (k-1)B \Leftrightarrow d^* < \frac{k-1}{k^2-k-1}B$. This last inequality is true since $d^* \le \frac{1}{k}B$ and $\frac{1}{k} < \frac{k-1}{k^2-k-1}$. Thus, the fact that (25) holds proves (24).

**Instance 8.** Consider that $d^* \in \mathcal{I}_k^1(B)$ for $k = 2$ and $d^* < B/2$. The demands are the following.

$$\left\{ \begin{array}{l} d_1^1 = d^* \\ d_2^1 = d_3^1 = \frac{1}{6}(B + d^*) \\ d_4^1 = \frac{1}{6}(B + d^*) - \epsilon \end{array} \right.$$

Let us first show that $I_8$, which denotes Instance 8, is valid. We have that $v(D_{I_8}) = d^* + \frac{1}{2}(B+d^*) - \epsilon = \frac{B+3d^*}{2} - \epsilon$ which is strictly larger than $B$ for $\epsilon$ sufficiently small because $d^* > \frac{1}{3}B$. Now we have to show that all the demands are smaller than $d^*$. This is true because $d^* \in \mathcal{I}_2^1(B)$ and $\frac{1}{6}(B+d^*) \le d^* \Leftrightarrow d^* \ge \frac{1}{3}B$.

We are going to show that for $k = 2$ and $\epsilon$ sufficiently small, it holds that

$$v(R_{I_8}) = 2d^* + \frac{B - 2d^*}{3} - \epsilon. \qquad (26)$$

We have $d_2^1 + d_3^1 + d_4^1 = \frac{1}{2}(B + d^*) - \epsilon$ which is, by (8), strictly smaller than $\gamma_1(d^*, B) = \frac{B+d^*}{2}$. It follows that $d^* \in R_{I_8}$. In addition, we can verify that $d^* + d_2^1 < \gamma_1(d^*, B)$, because it is equivalent to $d^* < B/2$ which holds for $I_8$. Now we consider $S = \{d^*, d_2^1, d_4^1\}$, and let us verify that $v(S) > \gamma_1(d^*, B)$. It holds that $v(S) = d^* + \frac{1}{3}(B+d^*) - \epsilon \ge \gamma_1(d^*, B) = d^* + \frac{1}{2}(B - d^*) \Leftrightarrow \frac{1}{3}(B+d^*) - \epsilon \ge \frac{1}{2}(B - d^*) \Leftrightarrow 5d^* - 6\epsilon \ge B \Leftrightarrow d^* \ge \frac{1}{5}(B + 6\epsilon)$ which is true for $\epsilon$ sufficiently small, since $d^* > \frac{1}{3}B$. Finally, we obtain that $R_{I_8} = S$ and $v(R_{I_8}) = d^* + \frac{1}{3}(B + d^*) - \epsilon = d^* + \frac{1}{3}(B + d^* + 3d^* - 3d^*) - \epsilon = 2d^* + \frac{1}{3}(B - 2d^*) - \epsilon$, proving (26).

Since $\epsilon$ can be as small as we want, $R(d^*, B)$ represents the maximum value of $v(R_I)$ for any instance of $\text{Inst}_1(d^*, B)$. We obtain the following lower bounds on $R(d^*, B)$:

$$R(d^*, B) \ge \max\left(2d^* + \frac{B - 2d^*}{3}, \frac{3}{2}(B - d^*)\right) \quad \text{for } k = 2, \qquad (27)$$

$$R(d^*, B) \ge \max\left(\frac{k+1}{k}(B-d^*), kd^*\right) \quad \text{for } k > 2, \qquad (28)$$

where (27) derives from $I_6$ and $I_8$, while (28) derives from $I_6$ and $I_7$.

Having $k = 2$ means that $d^* \in \mathcal{I}_2^1 = (\frac{B}{3}, \frac{B}{2}]$, and $2d^* + \frac{B-2d^*}{3} \le \frac{3}{2}(B-d^*) \Leftrightarrow d^* \le \frac{7}{17}B$. Therefore, we deduce that $R(d^*, B) \ge \frac{3}{2}(B-d^*)$ when $d^* \in (\frac{B}{3}, \frac{7}{17}B]$, and $R(d^*, B) \ge 2d^* + \frac{B-2d^*}{3}$ when $d^* \in (\frac{7}{17}B, \frac{B}{2}]$. Using (10) which states that $\tilde{E}(d^*, B) = B - R(d^*, B)$, we immediately obtain the expected upper bounds on $E(d^*, B)$ (lines 3 and 4 of (19)).

Finally, having $k > 2$ means that $d^* \in \mathcal{I}_k^1 = (\frac{B}{k+1}, \frac{B}{k}]$, and $\frac{k+1}{k}(B - d^*) \le kd^* \Leftrightarrow d^* \ge \frac{k+1}{k^2+k+1}B$. We deduce that $R(d^*, B) \ge kd^*$ when $d^* \in (\frac{k+1}{k^2+k+1}B, \frac{B}{k}]$, and $R(d^*, B) \ge \frac{k+1}{k}(B - d^*)$ when $d^* \in (\frac{B}{k+1}, \frac{k+1}{k^2+k+1}B]$. Using (10), we get the expected upper bounds on $E(d^*, B)$ (lines 1 and 2 of (19)). $\square$
## 7.2 Lower Bounding the Budget Saving

This section contains the following lower bounds on $E(d^*, B)$ which are obtained by constructing feasible solutions in polynomial time for any single agent instance of budget $B$ and largest demand $d^*$.

$$ E(d^*, B) \ge \begin{cases} B - \frac{k+1}{k}(B - d^*), & \text{for } \frac{1}{k+1}B < d^* \le \frac{k+1}{k^2+k+1}B \text{ and } k > 2 \\ B - kd^*, & \text{for } \frac{k+1}{k^2+k+1}B < d^* \le \frac{1}{k}B \text{ and } k > 2 \\ \frac{1}{2}(3d^* - B), & \text{for } B/3 < d^* \le 7B/17 \\ \frac{2}{3}(B - 2d^*), & \text{for } 7B/17 < d^* \le B/2 \\ B - d^*, & \text{for } B/2 < d^* \le B \end{cases} \tag{29} $$

The proof is cut into three parts: when $d^* \in \mathcal{I}_k^1(B)$ for any $k > 2$ which corresponds to the first two lines of (29), when $d^* \in \mathcal{I}_2^1(B)$ which corresponds to the third and fourth lines of (29), and when $d^* \in \mathcal{I}_1^1(B)$ which corresponds to the fifth line of (29).

### 7.2.1 Lower bounding $E(d^*, B)$ when $d^* \in \mathcal{I}_k^1(B)$ for any $k > 2$

We are going to show that $R(d^*, B) \le \max(kd^*, \frac{k+1}{k}(B - d^*))$ holds when $k > 2$. To this end, we will see that no matter the instance, there always exists a solution $A$ such that

$$ \gamma_1(d^*, B) \le v(A) \le \max(kd^*, \frac{k+1}{k}(B - d^*)), \tag{30} $$

Solution $A$ is built with Algorithm 7 which is almost greedy in the sense that it produces a first solution $A_1$ in a greedy manner (this part of Algorithm 7 is similar to Algorithm 1 and $A_1$ satisfies the properties of Algorithm 1 shown in Section 2). Then, two other solutions $A_2$ and $A_3$, which are close to $A_1$, are computed. We are going to see that one of them satisfies (30).

**Algorithm 7**

**Require:** A budget $B$ and a demand set $\{d_1^1, \dots, d_{m_1}^1\}$, with $d^* = d_1^1 \in \mathcal{I}_k^1(B)$, satisfying (1), (2) and (3) as well as Hypotheses 1 and 2.

$A_1 \leftarrow \emptyset, A_2 \leftarrow \emptyset, A_3 \leftarrow \emptyset$

$i \leftarrow 1$

**while** $v(A_1) < \gamma_1(d^*, B)$ **do**

$A_1 \leftarrow A_1 \cup \{d_i^1\}$

$i \leftarrow i + 1$

**end while**

$A_2 \leftarrow A_1 \setminus \{d_{i-1}^1\} \cup \{d_i^1\}$

$A_3 \leftarrow A_1 \setminus \{d^*\} \cup \{d_i^1\}$

**if** $v(A_1) > \max(kd^*, \frac{k+1}{k}(B - d^*))$ **then**

**if** $v(A_2) > p$ **then**

**return** $A_3$

**else**

**return** $A_2$

**end if**

**else**

**return** $A_1$

**end if**

**Lemma 13.** Algorithm 7 runs in $O(m^1)$ time and returns a solution $A$ satisfying (30) when $d^* \in \mathcal{I}_k^1(B)$ and $k > 2$.

*Proof.* We assume that $A_1$, $A_2$ and $A_3$ are the subsets of demands computed during the algorithm and $i$ denotes the value of variable $i$ at the end of the algorithm. If $A_1$ is returned, then $\gamma_1(d^*, B) \le v(A_1) \le \max(kd^*, \frac{k+1}{k}(B - d^*))$,
and we are done because $A_1$ satisfies (30). Let us suppose that $A_1$ is not returned. We have $v(A_1) \ge \gamma_1(d^*, B)$ by construction and $v(A_1) > \max(kd^*, \frac{k+1}{k}(B - d^*))$ by hypothesis. There exist $\epsilon_1 > 0$ and $\epsilon_2 > 0$ such that

$$ \left\{ \begin{array}{l} v(A_1) = kd^* + \epsilon_1, \\ v(A_1) = \frac{k+1}{k}(B - d^*) + \epsilon_2. \end{array} \right. \qquad (31) $$

Let $\delta := \gamma_1(d^*, B) - v(A_1) + d_{i-1}^1$ and $J := D^1 \setminus A_1$. $A_1$ is depicted in Figure 6. We have $d_{i-1}^1 = v(A_1) - \gamma_1(d^*, B) + \delta$ which, with (31) and (8), gives

$$ d_{i-1}^1 = kd^* + \epsilon_1 - d^* - \frac{k-1}{k}(B - d^*) + \delta. \qquad (32) $$

Since $v(A_1) > kd^*$ and because any demand is at most $d^*$, we get that $A_1 = \{d^*, d_2^1, \dots, d_{i-1}^1\}$ contains at least $k+1$ demands. Since Algorithm 1 is a greedy algorithm and it returns a feasible solution guaranteeing $\gamma_1(d^*, B)$, the set $A_1$ computed in Algorithm 7 is also feasible (i.e., $v(A_1) \le B$). Then we have that

$$ v(A_1 \setminus \{d^*\}) \le B - d^*. \qquad (33) $$

Since $A_1$ contains at least $k+1$ elements, $A_1 \setminus \{d^*\}$ contains at least $k$ demands. Thus by (33), there exists a demand of $A_1 \setminus \{d^*\}$ smaller than or equal to $\frac{1}{k}(B - d^*)$. The demands being sorted by non increasing value, we get that

$$ d_i^1 \le d_{i-1}^1 \le \frac{1}{k}(B - d^*). \qquad (34) $$

Furthermore, (32) and (34) imply that $kd^* + \epsilon_1 - d^* - \frac{k-1}{k}(B - d^*) + \delta \le \frac{1}{k}(B - d^*) \Leftrightarrow (k-1)d^* + \epsilon_1 + \delta \le B - d^*$, and the last inequality is equivalent to

$$ \delta \le B - kd^* - \epsilon_1. \qquad (35) $$

At this stage, an important observation is that we actually have $|J| = 1$. Indeed, $d^* \le \frac{1}{k}B$ and $k > 2$ give $\frac{k+1}{k}(B - d^*) + d^*/2 > B$. Then, by (31) and $\epsilon_2 > 0$, we obtain

$$ v(A_1) + d^*/2 > B. \qquad (36) $$

By Hypothesis 1, if $|J| \ge 2$ then at least one demand $d'$ of $J$ is greater than or equal to $d^*/2$. But in this case, for any $d \in J \setminus \{d'\}$ we have by (36) that $v(D_I) - d > B$, which contradicts Hypothesis 2. Thus we have $|J| = 1$, (i.e., $J = \{d_i^1\}$).

By (2), we have $v(A_1) + d_i^1 > B$. Using this last equation and (31), we obtain $d_i^1 > B - kd^* - \epsilon_1$ which, by (35), implies that $d_i^1 > \delta$. Use $\delta = \gamma_1(d^*, B) - v(A_1 \setminus \{d_{i-1}^1\})$ to get that $v(A_2) = v(A_1 \setminus \{d_{i-1}^1\} \cup \{d_i^1\}) \ge \gamma_1(d^*, B)$. Because of that, one can directly return $A_2$ when $v(A_2)$ is smaller or equal to $\max(kd^*, \frac{k+1}{k}(B - d^*))$. No need to check whether $v(A_2) \ge \gamma_1(d^*, B)$, since we just have seen that this condition is automatically verified. Now, in case $A_2$ is not returned (i.e., when $v(A_2) > \max(kd^*, \frac{k+1}{k}(B - d^*))$), we have that

$$ \begin{align*} v(A_1) - d_{i-1}^1 + d_i^1 &= v(A_2) > \max(kd^*, \frac{k+1}{k}(B - d^*)) \\ \Rightarrow \quad \gamma_1(d^*, B) - \delta + d_i^1 &> \frac{k+1}{k}(B - d^*) \\ \Leftrightarrow \quad d^* + \frac{k-1}{k}(B - d^*) - \delta + d_i^1 &> \frac{k+1}{k}(B - d^*) \\ \Leftrightarrow \quad d_i^1 - \delta &> \frac{2}{k}(B - d^*) - d^*. \end{align*} $$

The second and third inequalities are due to $v(A_1) - d_{i-1}^1 = \gamma_1(d^*, B) - \delta$ and (8), respectively. Since $\delta \ge 0$, this last inequality implies that

$$ d_i^1 \ge \frac{2}{k}(B - d^*) - d^*. \qquad (37) $$
<figure><img src="image_8.png" /><figcaption>Figure 6: Representation of $A_1$</figcaption></figure>

Now our goal is to show that the algorithm can return $A_3$, i.e., $\gamma_1(d^*, B) \le v(A_3) \le \max(kd^*, \frac{k+1}{k}(B-d^*))$. We have $v(A_3) = v(A^1 \setminus \{d^*\} \cup \{d_i^1\}) = v(A_1) - d^* + d_i^1$. Then (31), (37) and $\epsilon_1 > 0$ give

$$v(A_3) \ge (k-1)d^* + \frac{2}{k}(B-d^*) - d^*. \quad (38)$$

We know from Remark 1 that

$$d^* > \frac{1}{k}(B - d^*). \quad (39)$$

Thus, it follows from $k > 2$ that $(k-1)d^* + \frac{2}{k}(B-d^*) - d^* \ge d^* + \frac{k-1}{k}(B-d^*) = \gamma_1(d^*, B)^{11}$. Together with (38), this proves that $v(A_3) \ge \gamma_1(d^*, B)$. Finally, (33) and (34) give $v(A_3) = v(A_1 \setminus \{d^*\}) + d_i^1 \le \frac{k+1}{k}(B-d^*) \le \max(kd^*, \frac{k+1}{k}(B-d^*))$ and this completes the proof. $\square$

Lemma 13 implies that $R(d^*, B) \le \max(kd^*, \frac{k+1}{k}(B-d^*))$ when $d^* \in \mathcal{I}_k^1(B)$ and $k > 2$. Combined with $E(d^*, B) = B - R(d^*, B)$, we obtain the following bound.

**Corollary 4.** For $d^* \in \mathcal{I}_k^1(B)$ and $k > 2$, it holds that

$$E(d^*, B) \ge \begin{cases} B - \frac{k+1}{k}(B - d^*), & \text{for } \frac{B}{k+1} < d^* \le \frac{k+1}{k^2+k+1}B \\ B - kd^*, & \text{for } \frac{k+1}{k^2+k+1}B < d^* \le \frac{B}{k} \end{cases}.$$

### 7.2.2 Lower bounding $E(d^*, B)$ when $d^* \in \mathcal{I}_2^1(B)$

The case $k = 2$ is now considered. The result is slightly different from $k > 2$ since $v(R_I)$ can be greater than $\max(kd^*, \frac{k+1}{k}(B-d^*))$ for some instance $I$ when $k = 2$. We are going to show that $R(d^*, B)$ is smaller than or equal to $\max(2d^* + \frac{B-d^*}{3}, \frac{3}{2}(B-d^*))$ for any $d^* \in \mathcal{I}_2^1(B)$. Our proof strategy consists of separating the cases where the largest demand is in or out of $R_I$.

**Lemma 14.** $v(R_I) \le \max(2d^* + \frac{B-2d^*}{3}, \frac{3}{2}(B-d^*))$ holds for all instance $I$ such that the largest demand $d^*$ belongs to $R_I$ and $d^* \in \mathcal{I}_2^1(B)$.

*Proof.* If $v(R_I) \le \max(2d^*, \frac{3}{2}(B-d^*))$, then it is immediate that $v(R_I) \le \max(2d^* + \frac{B-2d^*}{3}, \frac{3}{2}(B-d^*))$. In the following we will be interested in the case where $v(R_I) > \max(2d^*, \frac{3}{2}(B-d^*))$. Thus, let us suppose that

$$v(R_I) > \max(2d^*, \frac{3}{2}(B - d^*)), \quad (40)$$

Then, there exists $\epsilon_1 > 0$ such that

$$v(R_I) = 2d^* + \epsilon_1. \quad (41)$$

<footnote>$^{10}$ $\frac{k+1}{k}(B-d^*) + d^*/2 > B$ is equivalent to $\frac{1}{k}B - \frac{k+1}{k^2}d^* + d^*/2 > 0$. Moreover, it holds that $\frac{1}{k}B > d^*$ and $d^*/2 > \frac{d^*}{k}$.</footnote>

<footnote>$^{11}$ It holds that $(k-1)d^* + \frac{2}{k}(B-d^*) - d^* \ge d^* + \frac{k-1}{k}(B-d^*) \Leftrightarrow (k-3)d^* \ge \frac{k-3}{k}(B-d^*)$. This last inequality is trivially verified when $k=3$, and is equivalent to (39) when $k > 3$.</footnote>
<figure><img src="image_9.png" /><figcaption>Figure 7: Instance I</figcaption></figure>

Our goal is to show that $\epsilon_1 < \frac{B-2d^*}{3}$. Let $R_I = \{d_{i_1}^1, \dots, d_{i_r}^1\}$. Note that since in general $R_I$ is not assumed to be obtained with a greedy approach, we do not necessarily have $i_1 = 1$ nor $i_{j+1} = i_j + 1$. In order to simplify $R_I$, we group its demands as follows. Assume that $R_I$ is built with demands taken in decreasing order. Then $\gamma_1(d^*, B)$ is reached or surpassed with the last inserted demand, and $v(R_I)$ is equal to $2d^* + \epsilon_1$. Let us denote by $m^*$ the last inserted demand which is the smallest demand of $R_I$. By the optimality of $R_I$, we know that $v(R_I) - m^* < \gamma_1(d^*, B)$, and $v(R_I) - m^*$ is at a certain distance $\delta \ge 0$ from $\gamma_1(d^*, B)$, namely $\delta := \gamma_1(d^*, B) - (v(R_I) - m^*)$. Let $\bar{m}$ be the value (i.e., total sum) of the remaining demands of $R_I$ apart from $d^*$, namely $\bar{m} := \sum_{d \in R_I \setminus \{d^*, m^*\}} d$. Note that $\bar{m}$ can be the sum of multiple demands. Since each demand is no larger than $d^*$, and $v(R_I) > 2d^*$, $R_I$ contains at least 3 demands, and then $\bar{m}$ is the sum of at least one demand. We obtain the following expression of $v(R_I)$.

$$v(R_I) = d^* + \bar{m} + m^* = 2d^* + \epsilon_1 \quad (42)$$

Let $J := D_I \setminus R_I$ be the set of demands that are not in $R_I$. Note that $J$ cannot be empty because $v(R_I) \le B$ and $v(D_I) > B$ (see (2)). Since $d^* \in \mathcal{I}_2^1(B)$, we have $d^* \le \frac{1}{2}B$ from which we deduce that $\frac{3}{2}(B - d^*) + d^*/2 \ge B$. Then, by (40), we obtain

$$v(R_I) + d^*/2 > B. \quad (43)$$

Now, we will prove that $|J| < 2$ by contradiction. Suppose that $|J| \ge 2$ then, by Hypothesis 1, at least one demand of $J$ is greater than or equal to $d^*/2$. But in this case, for any other demand $d$ of $J$, (43) gives $v(D_I) - d > B$, and this contradicts Hypothesis 2. It follows that $|J| = 1$. Instance $I$ is depicted in Figure 7.

Let us recall that $\gamma_1(d^*, B) = d^* + \frac{1}{2}(B - d^*)$. After some basic calculations, we obtain from (42) and the definition of $\delta$ that

$$\bar{m} = \frac{1}{2}(B - d^*) - \delta, \quad (44)$$

$$m^* = \frac{1}{2}(3d^* - B) + \delta + \epsilon_1. \quad (45)$$

We claim that for any demand $d' \in D_I \setminus \{d^*\}$, it holds that

$$d' < \frac{1}{2}(B - d^*). \quad (46)$$

By contradiction, if there exists a demand $d' \ge \frac{1}{2}(B - d^*)$, then $d^* + d' \ge \gamma_1(d^*, B)$. But, by the optimality of $R_I$ and $v(R_I) > 2d^*$ (recall that $\epsilon_1 > 0$), we would have $d^* + d' \ge v(R_I) > 2d^*$, which leads to, $d' > d^*$, contradicting that $d^*$ is the largest demand. Using (46) with $d' = m^*$ and (45) we obtain

$$\delta + \epsilon_1 < B - 2d^*. \quad (47)$$

Let $\hat{d}$ be the single demand of $J$. Use (41) and (2) to get that

$$\hat{d} > B - 2d^* - \epsilon_1. \quad (48)$$

Note that (47) gives $B - 2d^* - \epsilon_1 > \delta$ and then together with (48) we obtain $\hat{d} > \delta$. By (44), we have that $d^* + \bar{m} = \gamma_1(d^*, B) - \delta$. Due to $\hat{d} > \delta$, we have that $d^* + \bar{m} + \hat{d} > \gamma_1(d^*, B)$. By optimality of $R_I$, we necessarily have $v(R_I) = d^* + \bar{m} + m^* \le d^* + \bar{m} + \hat{d}$, which gives

$$\hat{d} \ge m^*. \quad (49)$$
We can also verify that $d^* + m^* + \hat{d} > \gamma_1(d^*, B)$. Indeed we have by (45) and (48) that

$$ 
\begin{aligned}
d^* + m^* + \hat{d} &> d^* + \frac{1}{2}(3d^* - B) + \delta + \epsilon_1 + B - 2d^* - \epsilon_1 \\
&\geq d^* + \frac{1}{2}(B - d^*) = \gamma_1(d^*, B).
\end{aligned}
$$

Then again, by optimality of $R_I$ and $v(R_I) = d^* + m^* + \bar{m}$, we have that

$$ \hat{d} \geq \bar{m}. \qquad (50) $$

Since $d^* \in \mathcal{I}_2^1(B)$, we have $d^* > B/3 > \frac{1}{2}(B - d^*)$. Use (46) to get that $\hat{d} < \frac{1}{2}(B - d^*) < d^*$. Furthermore, $m^* + \bar{m} = d^* + \epsilon_1$ follows from (42). Because $\hat{d} < d^*$, we have that $\hat{d} + \bar{m} + m^* < 2d^* + \epsilon_1 = v(R_I)$. By the optimality of $R_I$, this implies that $\hat{d} + \bar{m} + m^* < \gamma_1(d^*, B)$. Use (44) and (45) to get that

$$ \hat{d} < \frac{1}{2}(B - d^*) - \epsilon_1. \qquad (51) $$

The following system is obtained by combining (44) with (50), (45) with (49), and (51).

$$ 
\left\{ 
\begin{array}{l}
\hat{d} \geq (B - d^*)/2 - \delta \\
\hat{d} \geq (3d^* - B)/2 + \delta + \epsilon_1 \\
\hat{d} < (B - d^*)/2 - \epsilon_1
\end{array}
\right.
$$

This system imposes $\frac{1}{2}(B - d^*) - \epsilon_1 > \frac{1}{2}(B - d^*) - \delta$ and $\frac{1}{2}(B - d^*) - \epsilon_1 > \frac{1}{2}(3d^* - B) + \delta + \epsilon_1$ which are equivalent to $\delta > \epsilon_1$ and $\delta + 2\epsilon_1 < B - 2d^*$. We then get $\epsilon_1 < \frac{B-2d^*}{3}$ as desired. $\square$

We have shown in the proof of Lemma 14 that $J$ contains a single demand. Therefore, finding $R_I$ in this case can be done by a simple exhaustive search (take all the demands except one). Thereafter we show that $v(R_I) \leq \max(2d^*, \frac{3}{2}(B - d^*))$ when $d^*$ is out of $R_I$.

**Lemma 15.** $v(R_I) \leq \max(2d^*, \frac{3}{2}(B - d^*))$ holds for all instance $I$ such that the largest demand $d^*$ is out of $R_I$ and $d^* \in \mathcal{I}_2^1(B)$.

*Proof.* Let us pick an instance $I$ such that $d^* \notin R_I$ and $v(R_I) > \gamma_1(d^*, B)$. We want to show that $v(R_I) \leq \max(2d^*, \frac{3}{2}(B - d^*))$. By contradiction, suppose that $v(R_I) > 2d^*$ and $v(R_I) > \frac{3}{2}(B - d^*)$ hold. For some $\epsilon_1 > 0$ and some $\epsilon_2 > 0$ we have

$$ v(R_I) = 2d^* + \epsilon_1, \qquad (52) $$

$$ v(R_I) = \frac{3}{2}(B - d^*) + \epsilon_2. \qquad (53) $$

Note that by the optimality of $R_I$ we have that

$$ \sum_{d \in R_I \setminus \{d'\}} d < \gamma_1(d^*, B) \text{ for any } d' \in R_I. \qquad (54) $$

Let us decompose $R_I$ in two sets and a single demand denoted by $M_1$, $M_2$ and $m^*$, respectively. The decomposition of $R_I$ is explained in Algorithm 8. The algorithm takes the demands of $R_I$ by non-increasing value and add them into $M_1$ without exceeding $d^*$. Then, the following demands are added to $M_2$ without exceeding $\gamma_1(d^*, B)$. Let us denote by $m_1$ and $m_2$ the value of $M_1$ and $M_2$, respectively. Furthermore, let us denote by $\delta_1$ the distance between $d^*$ and $m_1$ i.e.,

$$ m_1 = d^* - \delta_1. \qquad (55) $$

Note that if $\delta_1 = 0$, then $m_1 = d^*$, and the whole set of demands $M_1$ can be replaced with a single demand of value $d^*$, without changing the value of $R_I$. We would get that $d^* \in R_I$, and this case is already treated by Lemma 14. We then suppose that $\delta_1 > 0$.
**Algorithm 8**

**Require:** $R_I$ such that $d^* \notin R_I$, $v(R_I) > \gamma_1(d^*, B)$ and (54) hold

Sort the demands of $R_I$ in non-increasing order and rename them as $l_1, l_2, \dots, l_r$

$$M_1 \leftarrow \emptyset, M_2 \leftarrow \emptyset$$

$i \leftarrow 1$

**while** $v(M_1) + l_i \le d^*$ **do**

$$M_1 \leftarrow M_1 \cup \{l_i\}$$

$i \leftarrow i + 1$

**end while**

**while** $v(M_1) + v(M_2) + l_i \le \gamma_1(d^*, B)$ **do**

$$M_2 \leftarrow M_2 \cup \{l_i\}$$

$i \leftarrow i + 1$

**end while**

$m^* \leftarrow l_i \{\text{Note that we necessarily have } l_i = l_r \text{ because of } v(R_I) > \gamma_1(d^*, B) \text{ and (54)}\}$

**return** $M_1, M_2, m^*$

<figure><img src="image_10.png" /><figcaption>Figure 8: $R_I$ such that $d^* \notin R_I$</figcaption></figure>

Let us denote by $\delta$ the distance between $v(M_1) + v(M_2)$ and $\gamma_1(d^*, B)$, i.e.,

$$m_1 + m_2 = \gamma_1(d^*, B) - \delta.$$

By construction we have $v(R_I) = m_1 + m_2 + m^* = 2d^* + \epsilon_1 = \frac{3}{2}(B - d^*) + \epsilon_2$. $R_I$ is depicted in Figure 8$^{12}$. We can see on Figure 8 that $m_2 = \gamma_1(d^*, B) - \delta - m_1$. Using (55) and (8) we obtain the following system.

$$\left\{ \begin{array}{l} m_1 = d^* - \delta_1, \\ m_2 = \frac{1}{2}(B - d^*) + \delta_1 - \delta. \end{array} \right. \qquad (56)$$

Our goal in the following is to show that this situation leads to a contradiction. The first step is to show that the three quantities $m_1, m_2$ and $m^*$ are all upper bounded by $d^*$. It is clear for $m_1$ (by construction) and $m^*$ ($m^*$ is a single demand) so it remains to show that $m_2 \le d^*$.

Suppose by contradiction that $m_2 > d^*$. The first thing we can notice is that

$$m_i > 2d^* - \gamma_1(d^*, B) = d^* - \frac{1}{2}(B - d^*) \quad \text{for } i = 1, 2. \qquad (57)$$

Indeed, by contradiction, if $m_i \le 2d^* - \gamma_1(d^*, B)$ holds for some $i \in \{1, 2\}$, since $v(R_I) > 2d^*$ (see (52)) then we have $v(R_I) - m_i \ge \gamma_1(d^*, B)$ which contradicts the optimality of $R_I$. Since $m_2 > d^*$ by hypothesis, we have $v(R_I) - m_2 + d^* < v(R_I)$ and by the optimality of $R_I$, it must be $v(R_I) - m_2 + d^* < \gamma_1(d^*, B)$. Furthermore, by using (53), (56) and (8) we have that $v(R_I) - m_2 + d^* < \gamma_1(d^*, B) \Leftrightarrow \frac{3}{2}(B - d^*) + \epsilon_2 - \frac{1}{2}(B - d^*) - \delta_1 + \delta + d^* < d^* + \frac{1}{2}(B - d^*) \Leftrightarrow \frac{1}{2}(B - d^*) + \epsilon_2 - \delta_1 + \delta < 0 \Leftrightarrow \epsilon_2 < \delta_1 - \delta - \frac{1}{2}(B - d^*)$. Since $\epsilon_2 > 0$, we have $\delta_1 > \delta + \frac{1}{2}(B - d^*) \implies \delta_1 > \frac{1}{2}(B - d^*)$. It follows that $m_1 = d^* - \delta_1 < d^* - \frac{1}{2}(B - d^*)$ which contradicts (57) and proves that $m_2 \le d^*$.

We have just seen that $d' \le d^*$ for any $d' \in \{m_1, m_2, m^*\}$ so $d^* + d' < 2d^* + \epsilon_1 = v(R_I)$ and by the optimality of $R_I$, we have $d^* + d' < \gamma_1(d^*, B)$ which by (8), proves that $d' < \frac{1}{2}(B - d^*)$ for any $d' \in \{m_1, m_2, m^*\}$. Since

<footnote>$^{12}$J := $D^1 \setminus \{m_1, m_2, m^*\}$.</footnote>
$v(R_I) = m_1 + m_2 + m^*$, we can affirm that $v(R_I) < \frac{3}{2}(B - d^*)$ which contradicts (53). To conclude, $v(R_I)$ cannot be strictly larger than $2d^*$ and $\frac{3}{2}(B - d^*)$ at the same time. □

Lemmas 14 and 15 indicate that $v(R_I) \le \max(2d^* + \frac{B-2d^*}{3}, \frac{3}{2}(B - d^*))$. Using the fact that $E(d^*, B) = B - R(d^*, B)$, we obtain the following lower bound.

**Corollary 5.** For any $d^* \in \mathcal{I}_2^1(B)$ we have

$$E(d^*, B) \ge \begin{cases} \frac{1}{2}(3d^* - B), & \text{for } B/3 < d^* \le 7B/17 \\ \frac{2}{3}(B - 2d^*), & \text{for } 7B/17 < d^* \le B/2 \end{cases}.$$

### 7.2.3 Lower bounding $E(d^*, B)$ when $d^* \in \mathcal{I}_1^1(B)$

It turns out that $\gamma_1(d^*, B) = d^* = B - E(d^*, B)$ when $d^* \in \mathcal{I}_1^1(B)$. Thus, from an algorithmic viewpoint, we just need to take $S = \{d^*\}$ so that $\gamma_1(d^*, B) \le v(S) \le B - E(d^*, B)$.

**Lemma 16.** $E(d^*, B) = B - d^*$ when $d^* \in \mathcal{I}_1^1(B)$.

*Proof.* If we just select the largest demand then we get a solution $\{d^*\}$ of value $d^*$ and the remaining budget is $B - d^*$. We have $\gamma_1(d^*, B) = d^* = v(\{d^*\})$ when $d^* \in \mathcal{I}_1^1(B)$, see (8). We cannot save more than $B - \gamma_1(d^*, B)$ so $E(d^*, B) = B - d^*$ when $d^* \in \mathcal{I}_1^1(B)$. □

## 7.3 Proof of Theorem 2

The values of $E$ announced in Theorem 2 follow from Lemma 12, Corollaries 4 and 5, and Lemma 16. The solution $S$ such that $\gamma_1(d^*, B) \le v(S) \le B - E(d^*, B)$ is built with Algorithm 5. More precisely, Algorithm 7 is run when $0 < d^* \le B/3$, and an exhaustive search is used when $B/3 < d^* \le B$.

Let us first argue that Algorithm 5 finds a correct solution. We know from Lemma 13 that the solution $S$ returned by Algorithm 7 satisfies $\gamma_1(d^*, B) \le v(S) \le B - E(d^*, B)$ when $0 < d^* \le B/3$. Lemmas 14 and 15 indicate that $v(R_I) \le B - E(d^*, B)$ when $B/3 < d^* \le B/2$, whereas $\gamma_1(d^*, B) \le v(R_I)$ holds by the definition of $R_I$. There exists a feasible solution $S$ such that $\gamma_1(d^*, B) \le v(S) \le B - E(d^*, B)$ when $B/3 < d^* \le B$, and we shall see that a simple exhaustive search finds it. In all, Algorithm 5 is correct.

It remains to prove that Algorithm 5 runs in polynomial time. Starting with a set of $m^1$ demands, Algorithm 4 is run. It takes $O(m^1 \log m^1)$ time to get a modified instance with $m$ demands satisfying Hypotheses 1 and 2. If $B/3 < d^* \le B$ then $S'$ such that $\gamma_1(d^*, B) \le v(S') \le B - E(d^*, B)$ is found by exhaustive search. Observe that an instance satisfying Hypotheses 1 and 2, with $d^* \in \mathcal{I}_k^1(B)$, contains at most $2k + 1$ demands: one demand of value $d^*$ with $d^* > B/(k + 1)$ because $d^* \in \mathcal{I}_k^1(B)$, and at most $2k$ other smaller demands because at most one demand is strictly smaller than $d^*/2$. We have $k \le 2$ when $B/3 < d^* \le B$. Therefore the instance contains at most 5 demands and a simple exhaustive search gives $S'$ (see Algorithm 5) in constant time. If $0 < d^* \le B/3$ then $S'$ is found with Algorithm 7 whose running time is $O(m)$ (see Lemma 13). Finally, Algorithm 5 retrieves $S$, solution of the original instance, from $S'$. Concretely, every demand of $S$ originally comes from a group of demands which were bundled during the execution of Algorithm 4. Thus, the task is made in $O(m^1)$ operations.