Nearly Tight Bounds for Proportional Group Fair Divisions and One-Sided Discrepancy

Introduction

Fair division

Allocation of indivisible goods among several agents is an important theoretical and practical problem. In the classical setting, we have $k$ agents and a set $G$ of commodities to be divided among them. Each agent has their own nonnegative evaluation of the commodities. A typical goal is to provide a nearly-fair partition subject to different fairness notions. We refer the reader to [1] for survey on fair division of indivisible goods.

In recent years, group fair divisions gained a significant amount of attention. In group fair division, individual agents are replaced by groups of agents that share the same commodities. Formally, we are given $k$ groups of $n_1 \ge\cdots\ge n_k$ agents, and a set of objects $G$. Denote by $\mu^{(i,j)}(g)$ the value that the $j$-th agent in the $i$-th group accord to a commodity $g \in G$. Importantly, all valuations are nonnegative: $\mu^{(i,j)}(g) \ge0$. The goal of the partition is again to produce nearly-fair parts, now evaluated by each agent in the group. We work with the following well-studied fairness notion.

Definition 1. Let $c$ be a positive integer. A partition $G = B_1 \sqcup B_2 \sqcup\ldots\sqcup B_k$ satisfies PROP-$c$, if for any $i,j$ there is a subset $C \subseteq G \setminus B_i$, $|C| \le c$ such that

Given $k$ and $n_1,\ldots,n_k$, let us denote by $\operatorname{PROP}(n_1,\ldots,n_k)$ the smallest $c$ such that for $k$ groups of agents of sizes $n_1,\ldots,n_k$ with any valuations there exists a partition that satisfies PROP-$c$.

In a recent paper [17], the authors proved the following upper and lower bounds for this problem.

Theorem 1 (Manurangsi–Meka, [17]). We have

While being tight for groups of nearly equal size, these bounds are far apart for asymmetric groups. The main result of this paper is an almost tight upper and lower bounds for this setting in general.

Theorem 2. Fix some positive integers $n_1 \ge\ldots\ge n_k$ and put $n = \sum_{i=1}^{k} n_i$. We have

The authors of [17] related the problem of determining PROP to a multicolor discrepancy problem. Certain tools from discrepancy theory underlie both lower and upper bounds. In earlier papers, the authors also related fair division and discrepancy questions ([11, 19, 8, 17]). However, all previous work always worked with two-sided discrepancy problems. In private communication, Pasin Manurangsi mentioned that developing an approach to benefit from one-sided discrepancy constraints is an important challenge. In this paper, we managed to develop such an approach.

Our contributions

• We provide nearly tight bounds for PROP;

• We develop an approach to benefit from one-sided discrepancy constraints in discrepancy problems via the gifting mechanism;

• We prove a discrepancy result on the so-called Top-down Beck-Fiala problem, which could be seen as its sharper, non-uniform analogue.

Next, we describe the discrepancy theory counterpart. We start with some background.

Discrepancy

Discrepancy theory studies how to color a set system so that every set remains nearly balanced. In the standard two-color matrix formulation, given a matrix $A \in\mathbb{R}^{n \times m}$, a coloring is a vector $\chi\in\{-1,1\}^{m}$, and the discrepancy of $A$ is defined as

Several classical results provide general-purpose upper bounds for discrepancy. If every column of a 0-1 matrix $A$ has at most $t$ nonzero entries, then $\operatorname{disc}(A) \le2t - 1$ ([7]). For every matrix $A \in[-1,1]^{n \times m}$, one has $\operatorname{disc}(A) = O(\sqrt{n})$ ([26]). More generally, for vectors of small Euclidean norm and any convex body of Gaussian measure at least $1/2$, there are signs whose signed sum lies in that body; in particular, this implies an $O(\sqrt{\log n})$ discrepancy bound in the $\ell_{\infty}$ norm for matrices with $n$ rows and columns of unit $\ell_{2}$ norm ([2]). Recent work improves Banaszczyk-type bounds for the Beck–Fiala and Komlós settings and gives efficient algorithms for finding the corresponding colorings ([4]).

For the fair-division setting considered here, the most relevant notion is that of multi-color and multi-matrix discrepancy.

Definition 2 ($k$-matrix discrepancy). Let $A^{1} \in[0,1]^{n_{1} \times m}, \ldots, A^{k} \in[0,1]^{n_{k} \times m}$ be matrices. Define $\operatorname{disc}^{k}(A^{1},\ldots,A^{k})$ to be the smallest $c$, such that there exists a partition $v_{1},\ldots,v_{k} \in\{0,1\}^{m}$, $\sum v_{i}=1$, with the following property. For all $i \in[k]$ and $j \in[n_{i}]$ we have

Here $A^{i}_{j}$ denotes the $j$-th row of matrix $A^{i}$.

$k$-matrix discrepancy was called asymmetric $k$-color discrepancy in [17].

We put

where the maximum is taken over $A^{i} \in[0,1]^{n_{i} \times m}$, where $m$ could be arbitrary. We use the same notational conventions for other types of discrepancy.

Definition 3 (One-sided $k$-matrix discrepancy). Let $A^{1} \in[0,1]^{n_{1} \times m},\ldots,A^{k} \in[0,1]^{n_{k} \times m}$ be matrices. Define $\operatorname{disc}^{k}_{>}(A^{1},\ldots,A^{k})$ similar to $\operatorname{disc}^{k}$, only with a different set of inequalities imposed:

for each row $A^{i}_{j}$ of $A^{i}$.

Note that we may renormalize the valuations of each agent so that for each $i,j$ we have

If there is a PROP-$c$ partition when agents utilities are represented by matrices $A^{1},\ldots,A^{k}$, then $\operatorname{disc}^{k}_{>}(A^{1},\ldots,A^{k}) \le c$. It implies the left inequality in the theorem below.

Lemma 3. *For any $k \ge2$ and $n_{1} \ge\ldots\ge n_{k} \ge1$,

The right inequality was essentially proved in [17] (Theorem 5.3). They have also showed the following.

Using Lemma 3, we get that Theorem 2 is equivalent to the following result.

Theorem 4. Fix some positive integers $n_1 \ge\ldots\ge n_k$ and put $n=\sum_{i=1}^{k}n_i$. We have

The bounds in Theorem 4 and the displayed equality before it are very different for skewed matrix sizes. Thus the one-sided nature of the problem makes it genuinely different. Little was known concerning rounding of one-sided constraints from this point of view. In this work, we develop the techniques that take advantage of the one-sided inequalities. Specifically, we introduce the gifting algorithm, described in Section 3.1. As is witnessed by our main result, the resulting approach is optimal up to polylog factors. Below, we summarize the main ideas of the proofs.

Our techniques. The proof of the upper bound has two main ingredients. The first ingredient is Theorem 13 that essentially allows to bound $\operatorname{disc}^{k}$ using a binary tree-type procedure. In its core is a discrepancy theory result (Top-down Beck-Fiala) which we believe is interesting in its own right. In a nutshell, it is based on a careful accounting of the $\ell_1$-norms of rows and uses the Partial Coloring Lemma. It allows to get discrepancy bounds that incorporate average row complexity after several columns were deleted.

The problem with Theorem 13 is that it gives worse errors for larger groups and for rows with larger $\ell_1$-norm. As a result, its direct application would lead to suboptimal bounds. To address this issue, we introduce a rebalancing procedure called the gifting algorithm, which carefully distributes a small part of commodities between (mostly large) groups. As a result, the most problematic agents (from large groups and with large $\ell_1$-norm of their valuation get the most gifts. This provides us with a necessary correction that then allows to apply Theorem 13. We note that the absence of the inequality from the other side spares us from a more elaborate tracking the weight of commodities that these ‘heavy’ agents get and gives us the necessary freedom in action.

Our lower bound is inspired by the construction used in [17]. The improvement comes from the intuition that rows of very different $\ell_1$-norm should make fair division more complicated. In the construction, we have some groups consisting of all-ones vectors, and the other (larger) groups get sparse valuations that look like block-diagonal matrices with the construction of Manurangsi and Meka as a block.

Organization. In Section 1.3, we formulate our generalization of the Beck–Fiala problem. In Section 2, we prove an upper bound for this problem. In Section 3, we use this result to obtain the upper bound in Theorem 2. The gifting algorithm, another important part of the proof of the upper bound, is presented in Section 3.1. Finally, in Section 4, we prove the lower bound in Theorem 2.

Discrepancy and the Top-down Beck-Fiala Problem

In the last decade, there has been great progress on the algorithmic aspects of discrepancy. One major development was the paper [16], where the authors provided a polynomial algorithm for the classical Spencer’s ‘six standard deviations’ result [26]. They introduced the following powerful tool.

Theorem 5 (Partial Coloring Lemma, ([16]).) Let $v_1,\ldots,v_n \in\mathbb{R}^m$ be vectors, and $y \in[-1,1]^m$ be a “starting” point. Let $c_1,\ldots,c_n \ge0$ be thresholds such that $\sum_{i=1}^n \exp(-c_i^2/16) \le m/16$. Let $\delta> 0$ be a small approximation parameter. Then there exists an efficient randomized algorithm that with probability at least $0.1$ finds a point $y' \in[-1,1]^m$ such that

(i) $|\langle y-y',v_i\rangle| \le c_i\|v_i\|_2$.

(ii) $|y'_i| \ge1-\delta$ for at least $m/2$ indices $i \in[m]$.

Moreover, the algorithm runs in time $O((m+n)^3\cdot\delta^{-2}\cdot\log(nm/\delta))$.

Another classical discrepancy result is the Beck–Fiala theorem ([7]), which states that, if each column of $A$ has $\ell_1$-norm at most $\Delta$, then the upper bound can be improved to $O(\Delta)$. They conjectured that the right upper bound is $O(\sqrt{\Delta})$. [2] proved a $O(\sqrt{\Delta}\cdot\ln n)$ bound, and the result of [16] gives the same bound and a polynomial construction. In a recent breakthrough paper, [4] showed the $O(\sqrt{\Delta})$ bound in the regime $\Delta\ge\log^2 n$. Still, the question remains open in general.

In this paper, we prove and apply the following theorem, which deals with an asymmetric generalization of the Beck-Fiala problem.¹

Definition 4 (($(\Delta_i)$-structured matrix).) Given positive reals $\Delta_1 \ge\Delta_2 \ge\ldots\ge\Delta_n$, we say that a matrix $A \in[0,1]^{n \times m}$ is $(\Delta_i)$-structured if for any $i \in[n]$, the maximum column sum in a submatrix $A_{i,\ldots,n}$ is at most $\Delta_i$. Formally,

We remark that the setting of the Beck–Fiala theorem and, importantly, the procedure underlying its proof, works with the setting $\Delta_1 = \ldots= \Delta_n$. However, as we illustrate in our proofs, one could draw benefits from this asymmetric setting. Let us define the linear discrepancy problem for $(\Delta_i)$-structured matrices.

Theorem 6 (Bound on the top-down Beck-Fiala problem). There exists an absolute constant $C > 0$, such that the following holds. Let $n \ge\Delta_1 \ge\Delta_2 \ge\ldots\ge\Delta_n > 0$ be a sequence of reals. Let $A \in[0,1]^{n \times m}$ be a $(\Delta_i)$-structured matrix and $x_0 \in[0,1]^m$ be a point. Then there exists $x \in\{0,1\}^m$, such that for all $1 \le i \le n$ we have

We prove this theorem in Section 2. For convenience, let us introduce the following function

where $C$ is a constant from Theorem 6. With this notation, the bound from Theorem 6 becomes

The proof is based on the idea that we can bound the number of rows having $\ell_1$-norm above a certain threshold. The idea of bounding large-norm rows has been instrumental in discrepancy. It has been used in random walk techniques ([16]; [4]) and in the foundational work of ([7]). Besides this, we use the partial coloring lemma from ([16]) and draw on some of the ideas from that paper. We suspect that the polylogarithmic term $\sqrt{\log_2(4r)}$ in Theorem 6 is necessary, see Lemma 8.

Related work

Group fair division. Fair division among groups (families), models settings in which each group receives a common bundle while agents within the same group may have different valuations. For divisible resources, several fairness notions for families have been studied, including average, unanimous, and democratic variants of proportionality and envy-freeness [23]. Another line of work considers cake divisions among groups of prescribed sizes, with the additional requirement that every group receives a connected piece [25].

For indivisible goods, early work studied the asymptotic existence of envy-free allocations for groups under random additive valuations [18], as well as approximate maximin-share guarantees for groups [27]. Since unanimous guarantees can be too demanding when agents in the same group have heterogeneous preferences, democratic fairness notions have also been proposed for indivisible goods [24]. Further work studied EF1- and EFX-type guarantees for group allocations under several valuation classes and group models [14]. More recent directions include ordinal maximin-share guarantees, variable groups, and allocations among couples or other small groups [20]; [13]; [12].

The line of work closest to the present paper connects group fair division with discrepancy theory. There, the properties of approximate proportionality, envy-freeness, and consensus division for groups are translated into multi-color and weighted discrepancy problems [19]. Subsequent sharper lower bounds used further developed the apparatus of multi-color and weighted discrepancy techniques [8]; [17]; [12].

Discrepancy. Constructive discrepancy results often rely on random walk and semidefinite programming ideas [3]; [16]; [22]; [6]; [5]; [4]. A more detailed introduction to discrepancy theory can be found in the standard books on the discrepancy method and geometric discrepancy [9]; [21].

In the fair-division setting considered here, the relevant notions are not only ordinary two-color discrepancy, but also multi-color and weighted variants. For $k$ colors, one natural objective is to minimize, over all relevant rows, the largest imbalance between any two color classes. Multi-color discrepancy and its weighted variants provide a natural language for studying allocations among several groups: colors can be interpreted as groups, and a coloring can be viewed as rounding the ideal fractional allocation in which every group receives a $1/k$ fraction of every good [10]; [11]. This viewpoint underlies discrepancy-based bounds for group fair division, including bounds for approximate proportionality, envy-freeness, and consensus division [19]; [8]; [17]; [12]. Recent work also extends discrepancy-based fair-division techniques beyond additive valuations by defining discrepancy notions for non-additive valuations and applying them to fair-division problems [15].

Notation

We denote $[n] = \{1,2,\ldots,n\}$.

For a matrix $A \in\mathbb{R}^{n \times m}$ and an index $i \in[n]$, by $A_i \in\mathbb{R}^m$ we denote the vector representing the $i$-th row of the matrix $A$. If $I \subseteq[n]$, then we denote by $A_I \in\mathbb{R}^{|I| \times m}$ the submatrix of $A obtained by retaining only the rows $i$ that lie in $I$. If $1 \le i \le j \le n$, then we define$A_{i\ldots j}$to be$A_I$where$I = {i,i+1,\ldots,j}$. For a vector$v \in \mathbb{R}^m$and a subset$I \subseteq [m]$, we denote by$v_I \in \mathbb{R}^{|I|}$the restriction of$v$to the coordinates$I$.

For a vector $v \in\mathbb{R}^m$, let $\lVert v\rVert_1$, $\lVert v\rVert_2$, $\lVert v\rVert_\infty$ denote its 1-norm, 2-norm, and $\infty$-norm, respectively.

Proof of Theorem 6

We first prove the following simple, but important lemma.

Lemma 7. Let $n,m \in\mathbb{N}$ and $A \in[0,1]^{n \times m}$ be a $(\Delta_i)$-structured matrix where $\Delta_1/\Delta_n \le r$ for $r > 0$. Then, for any $t > 0$, the number of rows $i$ which satisfy

is at most $m/t$.

Proof. Let $k$ be an integer such that $(\log_2 \Delta_n) - 1 \le k \le\log_2 \Delta_1$ and assume there is at least one $i$, such that $2^k \le\Delta_i \le2^{k+1}$. Let $d$ be the smallest index, such that $\Delta_d \le2^{k+1}$, and let $u \ge d$ be the largest index, such that $\Delta_u \ge2^k$.

The sum in each column of the matrix $A_{d,\ldots,u}$ is at most $2^{k+1}$. So, the total sum of all entries of rows $d,\ldots,u$ is at most $m \cdot2^{k+1}$. Therefore, the number of rows $i \in[d,u]$ that have sum of entries exceeding $2 \cdot t \cdot(\log_2 r + 2) \cdot\Delta_i$ is at most

where we used $\Delta_i \ge2^k$.

Since for every $\Delta_i$, there is an integer $(\log_2 \Delta_n) - 1 \le k \le\log_2 \Delta_1$, such that $2^k \le\Delta_i \le2^{k+1}$, summing over all such $k$, we obtain that the number of rows satisfying (2) is at most

We remark that the $\log_2 r$ term in Lemma 7 cannot be reduced as shown by the following lemma.

Lemma 8. There exists an absolute constant $m_0 > 0$, such that for every $m \ge m_0$, there exists $n \ge2 \cdot m$, positive integers $(\Delta_i)$ where $n \ge\Delta_1 \ge\Delta_2 \ge\ldots\ge\Delta_n \ge1$, and a matrix $A \in[0,1]^{n \times m}$ that is $(\Delta_i)$-structured and all its rows satisfy

Proof. We construct the matrix $A$ as a vertical concatenation of matrices $A_1,\ldots,A_k$, where the maximum column sum in each matrix $A_i$ is 1:

If we look at a row $r$ of matrix $A$ that is a part of a matrix $A_i$, then the maximum column sum in rows $\ge r$ is at most $i$. Let us set $\Delta_r=i$.

For each $i$, we design matrix $A_i$ to have $(i\cdot\ln m)/3$ ones in each row. We can make $A_i$ to have at least $\lfloor3m/(i\cdot\ln m)\rfloor$ rows, so that ones in each row are in disjoint set of columns. Therefore, choosing $k=\lfloor m/\ln m\rfloor$ the total number of rows $n$ across all matrices is

for sufficiently large $m\ge m_0$.

We rely on the following corollary from [16].

Corollary 9 (corollary from [16]). Let $A\in[0,1]^{n\times m}$ be a matrix and let $c_1,\ldots,c_n\ge0$ be such that $\sum_{j=1}^{n}\exp(-c_j^2/16)\le m/16$. Let $\delta>0$ be a small approximation parameter. Then there exists an efficient randomized algorithm which for any point $x\in[0,1]^m$ with probability at least $0.1$ finds a point $x'\in[0,1]^m$ such that

(i) $|\langle x-x',A_i\rangle|\le c_i\lVert A_i\rVert_2$.

(ii) $x'_i\ge1-\delta$ or $x'_i\le\delta$ for at least $m/2$ indices $i\in[m]$.

Moreover, the algorithm runs in time $\operatorname{poly}(n,m,\delta^{-1})$.

We also need to use the following standard lemma.

Lemma 10 ([7]). Let $m>n>0$ be integers, let $A\in[0,1]^{n\times m}$ be a matrix, and $x\in[0,1]^m$ be a point. Then, there exists a point $x'\in[0,1]^m$, such that $Ax=Ax'$ and all but $n$ coordinates of $x'$ are rounded (either $1$ or $0$).

Now, let us recall the statement of Theorem 6 and pose its proof. Our proof is based on the ideas that [16] use to prove their Theorem 2.

Theorem 11 (Restatement of Theorem 6). There exists an absolute constant $C>0$, such that the following holds. Let $n\ge\Delta_1\ge\Delta_2\ge\ldots\ge\Delta_n>0$ be a sequence of reals. Let $A\in[0,1]^{n\times m}$ be a $(\Delta_i)$-structured matrix and $x_0\in[0,1]^m$ be a point, then there exists $x\in\{0,1\}^m$, such that for all $1\le i\le n$,

Proof of Theorem 6. Let $r=\Delta_1/\Delta_n$. By Lemma 10 we can round $m-n$ coordinates of $x_0$ if $m>n$. Therefore, let us assume that $m\le n$.

Let us choose $c_i=C\cdot\sqrt{(\log_2(r)+2)\cdot\Delta_i/\lVert A_i\rVert_2}$ and show that $\sum_{i=1}^{n}\exp(-c_i^2/16)\le m/16$ for $C$ to be chosen later. For each integer $s$, let $q_s$ denote the number of rows for which it holds

Note that $\lVert A_i\rVert_2^2\le\lVert A_i\rVert_1$ and, thus, by Lemma 7, we have $q_s\le m/2^{s-1}$. Thus,

for sufficiently large $C > 0$.

Now, apply Corollary 9 for $c_1,\ldots,c_n$ and $\delta= \sqrt{\Delta_n}/(3n^2)$, obtaining a vector $x_1$ that has at least $m/2$ coordinates nearly rounded and $\left|\langle x_1-x_0,A_i\rangle\right| \le c_i\|A_i\|_2 = C \cdot\sqrt{(\log_2(r)+2)\cdot\Delta_i}$. Let $I_1 \subseteq[m]$ denote the coordinates of $x_1$ that are not $\delta$-close to 0 or 1. Let us recursively apply this procedure to $(x_1)|_{I_1}$, obtaining a new point $x_2 \in[0,1]^m$ with a set $I_2 \subseteq I_1$ of at most $m/4$ coordinates not $\delta$-close to 0 or 1. By iterating this at most $\log_2(m/\Delta_n)+2$ times, we get a sequence of points $x_1,x_2,\ldots,x_l$, for which $l \le\log_2(m/\Delta_n)+2$ and $x_l$ has all but $\min(\Delta_n,n/4)$ coordinates nearly rounded, denoted by $I_l$. By triangle inequality, for each $i$ we have

Now, let us nearly round the remaining $m' \le\min(\Delta_n,n/4)$ coordinates. For this, we choose $c_i=8\cdot\sqrt{\ln(n/m')}$. Then, $\sum_{i=1}^n\exp(-c_i^2/16)=\sum_{i=1}^n\exp(-4\cdot\ln(n/m'))=n\cdot(m'/n)^4\le m'/16$. Applying Corollary 9 to the sequence $c_i$, $\delta=\sqrt{\Delta_n}/(3n^2)$, and point $(x_l)|_{I_l}$, we get a point $x_{l+1}\in[0,1]^m$ that has at most $m'/2$ coordinates $I_{l+1}\subseteq I_l$ not $\delta$-close to 0 or 1 and $|\langle x_l-x_{l+1},A_i\rangle|\le c_i\cdot\sqrt{m'}=8\sqrt{\ln(n/m')}\cdot\sqrt{m'}$ for every $i$. We iterate this procedure until all coordinates get nearly rounded. Denote $x_{l+l'}$ to be the resulting point. Then, by triangle inequality, for every $i$,

for some constant $C'>0$.

Let $x$ be $x_{l+l'}$ in which we round each coordinate to the nearest integer. Then, the error of the $i$-th row is estimated by

In fact, in the proof of the upper bound for PROP, we shall need a slight generalization of Theorem 6 for a vertical concatenation of $(\Delta_i)$-structured matrices.

Theorem 12. Let $n_1,\ldots,n_k$ and $m$ be positive integers. Let $A^1 \in[0,1]^{n_1 \times m},\ldots,A^k \in[0,1]^{n_k \times m}$ be $(\Delta^1_j),(\Delta^2_j),\ldots,(\Delta^k_j)$-structured matrices respectively. Let $r$ be the maximum ratio $r = \max_{i,j,i',j'} \frac{\Delta^i_j}{\Delta^{i'}_{j'}}$, and let $d$ be the minimum $d = \min_{i,j} \Delta^i_j$. Then, for any $x_0 \in[0,1]^m$, there exists $x \in\{0,1\}^m$, such that for all $i=1\ldots k$ and $j=1\ldots n_i$

Proof. Let $n=n_1+\ldots+n_k$ denote the total number of rows in all matrices. Let us sort all values of $\Delta^i_j$ in decreasing order: $\Delta^{i_1}_{j_1} \ge\Delta^{i_2}_{j_2} \ge\ldots\ge\Delta^{i_n}_{j_n}$. Consider a matrix $A$ obtained from matrices $A^1,\ldots,A^k$ by stacking vertically their rows in the order $(i_1,j_1),(i_2,j_2),\ldots,(i_n,j_n)$

We claim that this is a $(k\cdot\Delta^{i_l}_{j_l})_{l=1}^n$-structured matrix. Indeed, consider $l$-th row of this matrix. Since we sorted $\Delta^i_j$ in decreasing order, only rows that have $\Delta$ less or equal to $\Delta^{i_l}_{j_l}$ are below $l$-th row. Let us fix one of the initial matrices $r \in\{1,2,\ldots,k\}$ and look only at the subset of its rows $I=\{q\mid\Delta^r_q\le\Delta^{i_l}_{j_l}\}$. By definition, we know that the maximum sum in a column in $A^r_I$ is at most $\Delta^{i_l}_{j_l}$. Therefore, the maximum sum in a column of the submatrix

can be bounded by $k\cdot\Delta^{i_l}_{j_l}$ by summing over all $k$ matrices. Now, applying Theorem 6 to matrix $A$, we obtain the desired bound of $\Xi(n/d,r)\cdot\sqrt{k\cdot\Delta^{i_l}_{j_l}}$ on linear discrepancy.

Upper Bound in Theorem 4

Recall, that the goal is to prove

Throughout this section, we use group fair division interpretation of $\operatorname{disc}(A^1,\ldots,A^k)$. Let $n_1\ge\ldots\ge n_k\ge1$ be the group sizes, where $n=n_1+\ldots+n_k$ is the total number of agents. The matrices $A^1\in[0,1]^{n_1\times m},\ldots,A^k\in[0,1]^{n_k\times m}$ denote agents utilities, and the goal is to find a partition $v_1,\ldots,v_k\in\{0,1\}^m$, $\sum v_i=1$, such that for any $i,j$ we have

with $c$ as small as possible.

The following theorem describes a partition algorithm that control the discrepancy of rows in terms of the $(\Delta_j)$-structure of the group matrices.

Theorem 13. There exists an absolute constant $C' > 0$, such that the following holds. Suppose agents valuations are presented by matrices $A^1 \in[0,1]^{n_1 \times m}, \ldots, A^k \in[0,1]^{n_k \times m}$ that are $(\Delta^1_j),(\Delta^2_j),\ldots,(\Delta^k_j)$-structured, respectively. Let $r$ upper bound the ratio between $\Delta^i_j$:

Let $d \le n_1$ be the lower bound on the minimum value of $\Delta$: $d \le\min_{i,j} \Delta^i_j$. Then, there is an allocation $v_1,\ldots,v_k \in\{0,1\}^m$, $\sum v_i = 1$, such that for any $i \in[k]$ and $j \in[n_i]$ we have

Proof. The role of this theorem is to provide a high-level partition of our goods.

Let us recursively divide objects between groups. If $k = 1$, we give all the objects to the only group, incurring zero error. For $k \ge2$, we divide all groups into two parts. The first part consists of the first $\lfloor k/2\rfloor$ groups, and the second part consists of the remaining $\lceil k/2\rceil$ groups. We apply Theorem 12 with $x_0 = 1 \cdot\frac{\lfloor k/2\rfloor}{k}$ to obtain a rounded vector $x \in\{0,1\}^m$. We recursively divide objects that correspond to ones in $x$ between the first $\lfloor k/2\rfloor$ groups and divide objects that correspond to zeros in $x$ between the remaining $\lceil k/2\rceil$ groups. Let $v_i$ be the indicator vector of the set of objects that the $i$-th groups receives at the end of this division.

This division procedure can be viewed as a binary tree. In every node of the tree, we have a segment of groups between which we divide the set of objects assigned to this node. If this is a non-leaf node, then some objects go to the left child and then rest of the objects go to the right child.

For the $j$-th agent from the $i$-th group, let us estimate his evaluation of the goods received. Take the path $P$ from the root of the binary tree to the leaf which corresponds to the $i$-th group. Define $k_t$ to be the number of groups that participated in the division in $t$-th node of path $P$. We have $k_1 = k$ and $k_l = 1$ where $l$ is the number of nodes in $P$. Moreover, we also have $k_{t+1}$ to be equal either to $\lfloor k_t/2\rfloor$ or $\lceil k_t/2\rceil$ for every $1 \le t \le l-1$.

For $t = 1\ldots l$, let $x_t \in\{0,1\}^m$ denote the indicator of the set of goods that was divided in the $t$-th node of the path $P$. We have $x_1 = 1$ and $x_l = v_i$. Let us check that

To divide objects in the $t$-th node, we apply Theorem 12 to the submatrix of $A$ narrowed down to rows and columns that correspond to agents and objects that participate in this division. The theorem gives us a vector $x''$. Let $x' \in\{0,1\}^m$ be the vector $x''$ padded with zeros for objects that did not participate in this division. By guarantees of Theorem 12, $x'$ satisfies

Here we used that the total number of agents in groups that participated in the division in the $t$-th node of the path $P$ can be bounded by $n_1\cdot k_t$, since $n_1$ is the largest number of agents in any group.

If the $i$-th group is in the first $\lfloor k_t/2\rfloor$ groups in this division, then we have $x_{t+1}=x'$, concluding (3) in this case. If it is among the remaining $\lceil k_t/2\rceil$ groups, then we have $x_{t+1}=x_t-x'$. Since

we have

which concludes (3).

By the triangle inequality, we have:

In the last inequality, we used (1) and the identity $\Xi(a\cdot b,r)=\Xi(a,r)+C\cdot\sqrt{\log_2(4r)}\cdot\log_2 b$. We have $k_{t+1}\leq\lfloor k_t/2\rfloor\leq\frac{2}{3}k_t$ for $k_t\geq3$. Thus the expressions

and

can be upper bounded by a constant. Since $n_1\geq d$, we have $\Xi\left(\frac{n_1}{d},r\right)\geq C\cdot\sqrt{\log_2(4r)}$. Therefore, the final expression can be bounded by

for some constant $C'>0$.

Let $A^1\in[0,1]^{n_1\times m},\ldots,A^k\in[0,1]^{n_k\times m}$ be agents valuations of objects. Note that $A^i$ is an $(n_i,n_i,\ldots,n_i)$-structured matrix since it has $n_i$ rows. If we directly apply Theorem 13 with $\Delta^i_j=n_i$, then we obtain a division of goods where the agents from the $i$-th group are at most

unsatisfied. This is an acceptable error if the sizes of all groups are equal $n_1=n_2=\ldots=n_k$. However, in an unbalanced case where, for example, $n_1$ is large and $n_2=n_3=\ldots=n_k=1$, the algorithm in Theorem 13 is disadvantageous for the large group and, as a result, gives an error of $\Omega(\sqrt{n_1})$, which is too large.

To deal with this issue, we show that it is possible to rebalance the advantage/disadvantage that the groups get when applying Theorem 13 by gifting, or simply assigning, a carefully chosen amount of goods to the larger groups.

Theorem 14. Let $C^{\prime\prime} > 0$. Let $A^{1} \in[0,1]^{n_{1}\times m},\ldots,A^{k} \in[0,1]^{n_{k}\times m}$ be agents valuations of objects. Then, there exists a partial assignment of goods to groups $v_{1},\ldots,v_{k} \in\{0,1\}^{m}$, $\sum v_{i} \le1$, such that the following properties are satisfied. Let $l = \langle1,v_{1}+\cdots+v_{k}\rangle$ denote the number of assigned goods. Let the matrix $\hat{A}^{i} \in[0,1]^{n_{i}\times(m-l)}$ be obtained from $A^{i}$ by removing columns that correspond to the assigned items (the ones in $v_{1},\ldots,v_{k}$). Let $\Upsilon:= \Xi\left(\frac{n_{1}k}{n},\frac{n_{1}k}{n}\right)$ where $n=n_{1}+\cdots+n_{k}$. Then,

(1) $l \le C^{\prime\prime}\cdot\sqrt{\Upsilon}\cdot n\cdot k$.

(2) For every group $i$, there is a permutation of agents $p^{i}_{1},\ldots,p^{i}_{n_{i}}$ in this group and values $n_{1}\ge\Delta^{i}_{1}\ge\cdots\ge\Delta^{i}_{n_{i}}\ge n/(\Upsilon\cdot k)$, such that the matrix $B^{i}$ obtained from rearranging rows of $\hat{A}^{i}$ according to the permutation $p^{i}$

is $(\Delta^{i}_{p^{i}_{1}},\Delta^{i}_{p^{i}_{2}},\ldots,\Delta^{i}_{p^{i}_{n_{i}}})$-structured and for every $j\in[n_{i}]$,

Let us comment on the statement of the theorem. The bound on $l$ is chosen so that the gifted items have negative affect that is covered by the error term. The condition of being $(\Delta^{i}_{j})$-structured is a technical condition needed for an application of the discrepancy results and essentially allows to bound the row norms of a matrix and its submatrices. The maximum in the statement encodes the two scenarios. One option is that a given row has small $\ell_{1}$-norm. In this case, we do not need to rebalance it for the application of Theorem 13 and may ignore the contribution of gifting. The other option is that a row has large $\ell_{1}$-norm, and Theorem 13 gives a large error on this row. Then the gifting completely covers this possible error.

We first derive the main theorem from these ingredients. To this end, we need the following auxiliary technical lemma.

Lemma 15. There exists a constant $C^{\prime\prime}>0$, such that for all $r\ge1$,

Proof.

for some $C^{\prime\prime}>0$.

Now we are ready to combine the procedure in Theorem 13 and the gifting of Theorem 14 to establish the upper bound in Theorem 2.

Proof of the upper bound in Theorem 2. Let $C'$ be the constant from Theorem 13. Denote $n = n_1 + \ldots+ n_k$ and let $\Upsilon:= \Xi\left(\frac{n_1 k}{n},\frac{n_1 k}{n}\right)$. By Lemma 15, there is a constant $C'' > 0$, such that

Apply Theorem 14 with constant $C''$ to obtain a partial assignment $v_1,\ldots,v_k \in\{0,1\}^m$ and matrices $B^1,\ldots,B^k$ that are $(\Delta^1_{p^1_j}),(\Delta^2_{p^2_j}),\ldots,(\Delta^k_{p^k_j})$ structured, respectively. Let $l = \langle1,v_1+\ldots+v_k\rangle$ denote the number of goods that were assigned by the application of Theorem 14.

Now, we apply Theorem 13 to matrices $B^1,\ldots,B^k$ with $r = \Upsilon\cdot\frac{n_1 k}{n}$ and $d = n/(\Upsilon\cdot k)$ to divide the remaining $m-l$ objects among $k$ groups. Note that $dr=n_1$, and the matrices $B^i$ obviously satisfy $\Delta^i_{p^i_j}\le n_1$. Thus, such a choice of $r,d$ is valid. Denote by $u_1,\ldots,u_k \in\{0,1\}^{m-l}$ the division given by the theorem. We are guaranteed that for the $j$-th agent from the $i$-th group, it holds

Observe that $\max\left\{\langle A^i_j,v_i\rangle,C''\cdot\sqrt{\Upsilon\cdot\frac{n}{k}}\right\}\ge C''\cdot\Upsilon\cdot\sqrt{\Delta^i_j}$ implies $\langle A^i_j,v_i\rangle\ge C''\cdot\Upsilon\cdot\sqrt{\Delta^i_j}-C''\cdot\sqrt{\Upsilon\cdot\frac{n}{k}}$.

In addition, since at most $l$ objects are gifted, we have $\langle B^i_{p^i_j},1/k\rangle\ge\langle A^i_j,1/k\rangle-l/k\ge\langle A^i_j,1/k\rangle-C''\cdot\sqrt{\Upsilon\cdot\frac{n}{k}}$.

Therefore, combined with the gifted objects $v_i$, the $j$-th agent from the $i$-th group values the assigned objects at least by

Thus, we have obtained the desired $2\cdot C''\cdot\sqrt{\Upsilon\cdot\frac{n}{k}}$ bound on PROP'.

In order to complete the proof of the main theorem, we are left to prove Theorem 14. This is done in the following section.

Proof of Theorem 14

The overall assignment is simply a combination of partial assignments obtained for each group individually using the following theorem.

Theorem 16. Let $C''>0$ be a real, and let $n>0$, $n_1>0$, $k>0$ be integers, such that $n\ge n_1\ge n/k$. Let $A\in[0,1]^{n_s\times m}$ be agents valuations of objects for the $s$-th group with $n_s\le n_1$ agents. Then, there exists a partial assignment of goods $v\in\{0,1\}^m$, such that the following properties are satisfied. Let $l=\langle1,v\rangle$ denote the number of assigned goods, and let $\Upsilon:=\Xi\left(\frac{n_1\cdot k}{n},\frac{n_1\cdot k}{n}\right)$. Let matrix $A'\in[0,1]^{n_s\times(m-l)}$ be obtained from $A$ by removing columns that correspond to the assigned items (ones in $v$). Then,

1. $l\le C''\cdot n_s\cdot\sqrt{\Upsilon\cdot\frac{k}{n}}$

2. There is a permutation of agents $p_1,\ldots,p_{n_s}$ and values $n_1\ge\Delta_1\ge\ldots\ge\Delta_{n_s}\ge n/(\Upsilon\cdot k)$, such that the matrix obtained from rearranging rows of $A'$ according to the permutation $p$

is $(\Delta_{p_1}, \Delta_{p_2}, \ldots, \Delta_{p_{n_s}})$-structured and for every $j \in[n_s]$,

Let us show how to combine these partial assignments and prove Theorem 14.

Proof of Theorem 14 via Theorem 16. The procedure has $k$ iterations, where at the $i$-th iteration we select goods for the $i$-th group.

• As an input, we get the matrices $\hat{A}^{1}(i),\ldots,\hat{A}^{k}(i),B^{1}(i),\ldots,B^{i-1}(i)$. Initially (iteration 1), we have $\hat{A}^{j}(1)=A^{j}$.

• We apply Theorem 16 to the $i$-th group with the assignment matrix $\hat{A}^{i}(i)$ playing the role of $A$ and with $s=i$ to obtain a partial assignment $v_i:=v$, a permutation $p^{i}:=p$, and a matrix $B^{i}(i):=B$.

• We then obtain $\hat{A}^{1}(i+1),\ldots,\hat{A}^{k}(i+1),B^{1}(i+1),\ldots,B^{i}(i+1)$ by removing the columns that correspond to the items that were gifted at this step from the matrices $\hat{A}^{1}(i),\ldots,\hat{A}^{k}(i),B^{1}(i),\ldots,B^{i}(i)$.

• After the last step $k$, we output $\hat{A}^{j}:=\hat{A}^{j}(k+1)$ and $B^{j}=B^{j}(k+1)$.

Note that in total the procedure assigns at most $C''\cdot(n_1+\ldots+n_k)\cdot\sqrt{\gamma\cdot k/n}=4\cdot\sqrt{\gamma\cdot n\cdot k}$ objects. Moreover, for every $i$, the matrix $B^{i}$ is $(\Delta^{i}_{p^{i}_{j}})$ structured, since it was $(\Delta^{i}_{p^{i}_{j}})$-structured at step $i$ and this property is hereditary w.r.t. removing columns. At last, for every $i\in[k],j\in[n_i]$, we have $\langle B^{i}_{j},v_i\rangle=\langle B^{i}_{j}(i),v_i\rangle$, and

since it was guaranteed by Theorem 16.

The rest of the section is devoted to the proof of Theorem 16. We begin with the description of the following algorithm that iteratively constructs the partial assignment $v$. See Algorithm 1 for the pseudocode.

Gifting algorithm. The algorithm starts with an empty assignment $v:=0^{m}$ and sequentially selects an object that is given to the group. During its execution, the algorithm also maintains a set $S$ of active agents. Initially, every agent is active, i.e. $S=\{1,2,\ldots,n_s\}$.

On each iteration, the algorithm finds a column $j\in[m]$, such that $v_j=0$ and the sum of active agents valuations of the $j$-th object is maximized: $\sum_{i\in S}A_{i,j}\to\max$. Let $\lambda:=\sum_{i\in S}A_{i,j}$ denote the column sum over active agents. We iterate over active agents $i\in S$ and look if $\langle A_i,v\rangle\ge C''\cdot\gamma\cdot\sqrt{\lambda}$. If this holds, then we consider the $i$-th agent to already be fulfilled and remove him from the set of active agents $S\leftarrow S\setminus\{i\}$. If at least one agent is removed after the filtration, we recalculate $j$ and $\lambda$ that maximizes the column sum over the modified set of active agents and perform the filtration again.

After that, at the end of the iteration, if $\lambda<\frac{1}{\gamma}\cdot\frac{n}{k}$ or $S=\varnothing$, then the algorithm terminates. Otherwise, we give the $j$-th item to the group: $v_j\leftarrow1$ and continue with the next iteration.

Algorithm 1 Gifting Algorithm

1: $v \leftarrow0^{m}$ ▷ Initially no object is gifted 2: $S \leftarrow\{1,2,\ldots,n_{s}\}$ ▷ Initially every agent is active 3: for $t=1,2,\ldots$ do 4: $j \leftarrow\arg\max_{j:v_{j}=0}\sum_{i\in S} A_{i,j}$ ▷ Find item most desirable by the active agents 5: $\lambda\leftarrow\sum_{i\in S} A_{i,j}$ 6: atLeastOneRemoved $\leftarrow$ False 7: for $i\in S$ do 8: if $\langle A_{i},v\rangle\ge C''\cdot\Upsilon\cdot\sqrt{\lambda}$ then 9: $S\leftarrow S\setminus\{i\}$ ▷ Make the $i$-th agent inactive 10: atLeastOneRemoved $\leftarrow$ True 11: end if 12: end for 13: if atLeastOneRemoved then 14: goto Step 4 ▷ Update $j$ and $\lambda$ and repeat filtration 15: end if 16: if $\lambda<\frac{1}{\Upsilon}\cdot\frac{n}{k}$ or $S=\varnothing$ then 17: terminate and return $v$ ▷ $\lambda$ is small or all agents are fulfilled 18: else 19: $v_{j}\leftarrow1$ ▷ Give the $j$-th object to the group 20: end if 21: end for

Denote $T=\lVert v\rVert_{1}$ to be the number of items that the algorithm has gifted. Note that the algorithm made $T+1$ iterations in total. The $T$-th iteration was the last when an item was added to the group. For $t=1\ldots T+1$, denote $S_{t}$ to be the set of active agents at the end of the $t$-th iteration, and denote by $\lambda_{t}$ the column sum over active agents at the end of the $t$-th iteration.

Let us note that $\lambda_{T}\ge\frac{1}{\Upsilon}\cdot\frac{n}{k}$ since the algorithm did not terminate at $T$-th iteration. Moreover, observe that $\lambda_{t}$ is monotone in $t$, $\lambda_{1}\ge\lambda_{2}\ge\lambda_{3}\ge\ldots\ge\lambda_{T}$, since the space of active agents and columns over which we maximize and take the sum only shrinks.

Let $t_{i}$ be the iteration when the $i$-th agent is removed from the active set. If the agent $i$ is never removed from the active set, we set $t_{i}:=T+1$.

Let us show that $\lVert v\rVert_{1}$ is bounded.

Claim 17. The algorithm described above assigns no more than $C''\cdot n_{s}\cdot\sqrt{\Upsilon}\cdot k/n$ objects to the group. That is, $\lVert v\rVert_{1}\le C''\cdot n_{s}\cdot\sqrt{\Upsilon}\cdot k/n$.

Proof. For $t=1\ldots T$, let us denote by $j_{t}$ the object given to the group on the $t$-th iteration. Let us calculate the following sum in two different ways:

Firstly, note that for every $t=1\ldots T$, we have $\sum_{i\in S_{t}}A_{i,j_{t}}=\lambda_{t}$ by the definition of $\lambda_{t}$. Therefore, on the one hand

On the other hand, we can swap the summations to sum over rows first:

Therefore, we obtain the desired bound

To conclude the proof of Theorem 16, let us define the matrix $B$, the permutation of agents $p$, and the sequence $\Delta_i$.

We define $\Delta_i$ to be the value of $\lambda$ right at the moment when the $i$-th agent is removed from the set $S$. If the agent is never removed from the set $S$, we set $\Delta_i:=\max\left(\lambda_{T+1},\frac{1}{\Upsilon}\cdot\frac{n}{k}\right)$. Let $p_1,p_2,\ldots,p_{n_s}$ be the sequence at which agents are removed from the active set ($p_1$ is the first agent that is removed, $p_2$ is the second, and so on). The agents that are not removed from the active set by the end of the algorithm are placed at the end of the sequence $p$ in any order. Observe that $n_1\ge\Delta_{p_1}\ge\Delta_{p_2}\ge\ldots\ge\Delta_{p_{n_s}}\ge n/(k\cdot\Upsilon)$ since $\lambda$ can only decrease over time.

Let $A'$ be matrix obtained from $A$ by removing all columns corresponding to the gifted items (ones in $v$). Define the matrix $B$ by arranging the rows of matrix $A'$ in the following sequence

Let us show that the matrix $B$ is top-down structured. Claim 18. The matrix $B$ is $(\Delta_{p_1},\Delta_{p_2},\ldots,\Delta_{p_{n_s}})$-structured.

Proof. Consider the $i$-th row of the matrix $B$. We consider two cases whether the $p_i$-th agent was removed from the set $S$ or not.

If the $p_i$-th agent is never removed from the set $S$, then $p_i,p_{i+1},\ldots,p_{n_s} \in S_{T+1}$. By definition, $\lambda_{T+1}$ is the maximum column sum over rows corresponding to agents from $S_{T+1}$. Therefore, $\Delta_{p_i}=\max\left(\lambda_{T+1},\frac{n}{r}\right)$ is also an upper bound on the column sum of the submatrix $B_{i,\ldots,n_s}$.

Now, suppose the $p_i$-th agent is removed from the set $S$ at some point. Consider the moment just before $p_i$-th agent is removed from $S$. The agents $p_i,p_{i+1},\ldots,p_{n_s}$ all lie in the set $S$. We also have that the current value of $\lambda$ is an upper bound on the maximum column sum over rows corresponding to agents from $S$. Therefore, $\Delta_{p_i}=\lambda$ is also an upper bound on the column sum of the submatrix $B_{i,\ldots,n_s}$.

Thus, the matrix $B$ is $(\Delta_{p_1},\ldots,\Delta_{p_{n_s}})$-structured.

Finally, let us show that every agent values gifted objects at the desired threshold.

Claim 19. For every agent $i \in[n_s]$, it holds that

Proof. Let us condition on whether the $i$-th agent was removed from the set $S$ or not.

If it was not removed, then $\Delta_i=\lambda_{T+1}<\frac{1}{\Upsilon}\cdot\frac{n}{k}$. Therefore, $\sqrt{\Upsilon\cdot\frac{n}{k}}\ge\Upsilon\cdot\sqrt{\Delta_i}$.

If it was removed, then it could happen only if $\langle A_i,v\rangle\ge C''\cdot\Upsilon\cdot\sqrt{\lambda}$ was true at that moment. Since $\Delta_i=\lambda$, we get the desired bound.

Therefore, in both cases we can conclude (5).

The claims 18 and 19 together conclude the proof of Theorem 16.

Lower Bound in Theorem 4

In this section, we prove that $\operatorname{disc}_{>}^{k}=\Omega\left(\sqrt{n/k}\right)$. We start with a trivial lower bound on $\operatorname{osasymdisc}_{>}^{\max}$.

Lemma 20.

Proof. Let $k\ge2$ be the number of groups. Let $n_1,\ldots,n_k>0$ be group sizes, and let $n=n_1+\ldots+n_k$ be the total number of agents.

Suppose there are $k-1$ objects, and each of them is valued by 1 by every agent. Then, in any allocation at least one group receives no objects. The fair share for this group is $\frac{k-1}{k}$. Therefore, agents from this group are at least $\frac{k-1}{k}$ unsatisfied.

To prove our lower bound, we rely on the following lower bound on weighted discrepancy.

Theorem 21 (Theorem 3.2 from [17]). For any integers $r>0$ and $k>0$, there exists a matrix $A\in[0,1]^{r\times(r\cdot k)}$, such that for any $v\in\{0,1\}^{m}$, it holds

The theorem guarantees that the maximum of the absolute value of deviation of $\langle A_i,(v-1/k)\rangle$ from 0 is at least $\sqrt{r-1}/16$. If the deviation is downwards then we immediately infer that some agent is unsatisfied. However, an upward deviation is only welcomed by an agent and thus does not immediately imply any lower bounds for group division. To deal with this, we introduce agents with complementary valuations. This converts an upward deviation into a downward one. Similarly to [17], we derive the following result.

Lemma 22. For any $r \ge1$, there exists $m_0$, such that for any $m \ge m_0$ there exists a matrix $B \in\{0,1\}^{2r \times m}$ that satisfies the following. For any $v \in\{0,1\}^m$, there exists $i$, such that

Proof. Let $A \in\{0,1\}^{r \times m_0}$ be a matrix given by Theorem 21. For $m \ge m_0$, let a matrix $A' \in\{0,1\}^{r \times m}$ be obtained from $A$ by padding extra columns with zeroes. Note that the matrix $A'$ still satisfies the property from Theorem 21 since zero columns do not change the product.

Define $C$ to be the matrix of rows complementary to $A'$: $C_{i,j}=1-A'_{i,j}$ for all $i,j$. Let $B$ be a vertical concatenation of matrices $A'$ and $C$:

Consider a vector $v \in\{0,1\}^m$ and let us show that the matrix $B$ satisfies the required property. By Theorem 21, for any $v \in\{0,1\}^m$, there exists $i$, such that

Let us consider the two cases how the absolute value can be expanded.

If $-\langle A'_i,v-1/k\rangle\ge\sqrt{r-1}/16$ then $\langle A'_i,v\rangle\le\langle A'_i,1/k\rangle-\sqrt{r-1}/16$, which implies (8).

If $\langle A'_i,v-1/k\rangle\ge\sqrt{r-1}/16$, then

Since $1-A'_i$ is a row of $B$, we get the desired conclusion.

Proof of the Lower Bound

Lemma 20 gives a lower bound $\operatorname{disc}^k(n_1,\ldots,n_k) \ge\frac{1}{2}$. This allows us to assume that $n \ge2^{14}\cdot k$. Denote $r=\lfloor n/(4\cdot k)\rfloor\ge2^{12}$, and let $m_0$ be the integer from Lemma 22 when applied with $r$. Let $M=n\cdot m_0$ be the number of objects. We design agents valuations for the $i$-th group as follows.

• If $n_i < 2r$, then we set all of the agents from the $i$-th group to valuate any object by 1.

• If $n_i \ge2r$, then we divide all agents into subgroups of size $2r$ with $<2r$ agents left in no subgroup. In total, this gives $s_i=\lfloor n_i/(2r_i)\rfloor$ subgroups. Let $m_i=\lfloor M/s_i\rfloor\ge m_0$, and let the matrix $B \in\{0,1\}^{2r\times m_i}$ be given by Lemma 22. For the $j$-th subgroup we set the valuations of the objects $(j-1)\cdot m_i+1,\ldots,j\cdot m_i$ according to the matrix $B$. All other objects are valuated by 0 by the agents of this subgroup. See Figure 1 for an illustration of the chosen valuations.

Let us give some intuition behind the construction. Note that $r$ is essentially an average size of a group. Thus, large groups get valuations in the spirit of the construction from [17], while small groups evaluate everything to 1. The evaluation of small groups thus forces that roughly a correct proportion of goods go to the large groups. There, the goods are partitioned between subgroups. This way, we are able to apply the bound of Lemma 22 inside a subgroup, rather than inside the whole group.

We go on to the proof. Arguing indirectly, assume that there is an allocation $v_1,\ldots,v_k$, such that every agent is at most $2^{-15} \cdot\sqrt{n/k}$ unsatisfied.

Define $d_i = \sum_{j=1}^{M} v_{i,j} - \frac{M}{k}$ to be the difference between the number of allocated goods and the fair share for the $i$-th group. Note that $\sum_{i=1}^{k} d_i = 0$. Let us estimate $\sum_{n_i \ge2r} d_i$ and $\sum_{n_i < 2r} d_i$ separately.

Consider a group $i$ for which $n_i \ge2r$. We have $s_i = \lfloor n_i/2r \rfloor$ subgroups in this group. The $j$-th subgroup has non-zero valuations for the segment of objects $(j-1)\cdot m_i+1,\ldots,j\cdot m_i$. By the pigeonhole principle, there is a subgroup $j$, such that $\sum_{l=(j-1)\cdot m_i+1}^{j\cdot m_i} v_{i,l}-\frac{M}{k\cdot s_i}\le\frac{d_i}{s_i}$. By (6), there is an agent in this subgroup that is at least $\frac{\sqrt{r-1}}{16}-\max(0,d_i/s_i+1/k)$ unsatisfied (here we used $|m_i-M/s_i|\le1$). If $d_i/s_i<\frac{\sqrt{r-1}}{32}$, then we get a contradiction since this agent’s unsatisfaction is at least

Thus, we have $d_i\ge s_i\cdot\sqrt{r-1}/32\ge2^{-11}\cdot s_i\cdot\sqrt{n/k}$. Therefore,

Consider any agent from group $i$ for which $n_i<2r$. Recall that it evaluates every good to $1$, and thus $d_i$ is exactly the measure of how unsatisfied he is. Thus, $d_i$ cannot be less than $-2^{-15}\cdot\sqrt{n/k}$. Therefore, we have

Combining two bounds, we have

reaching a contradiction.