# Improving Approximation Guarantees for Maximin Share

Hannaneh Akrami
<EMAIL_ADDRESS>Max Planck Institute for Informatics and
Graduiertenschule Informatik, Universität des Saarlandes Jugal Garg
<EMAIL_ADDRESS>University of Illinois at Urbana-Champaign. Supported by
NSF Grant CCF-1942321 Eklavya Sharma†
<EMAIL_ADDRESS>Setareh Taki
<EMAIL_ADDRESS>Grubhub, USA

###### Abstract

We consider fair division of a set of indivisible goods among $n$ agents with
additive valuations using the fairness notion of maximin share (MMS). MMS is
the most popular share-based notion, in which an agent finds an allocation
fair to her if she receives goods worth at least her ($1$-out-of-$n$) MMS
value. An allocation is called MMS if all agents receive their MMS values.
However, since MMS allocations do not always exist [KPW18], the focus shifted
to investigating its ordinal and multiplicative approximations.

In the ordinal approximation, the goal is to show the existence of $1$-out-
of-$d$ MMS allocations (for the smallest possible $d>n$). A series of works
led to the state-of-the-art factor of $d=\lfloor 3n/2\rfloor$ [HSSH21]. We
show that $1$-out-of-$4\lceil n/3\rceil$ MMS allocations always exist, thereby
improving the state-of-the-art of ordinal approximation.

In the multiplicative approximation, the goal is to show the existence of
$\alpha$-MMS allocations (for the largest possible $\alpha<1$), which
guarantees each agent at least $\alpha$ times her MMS value. A series of works
in the last decade led to the state-of-the-art factor of
$\alpha=\frac{3}{4}+\frac{3}{3836}$ [AG24].

We introduce a general framework of _approximate MMS with agent priority
ranking_. We order the agents, and agents earlier in the order are considered
more _important_. An allocation is said to be $T$-MMS, for a non-increasing
sequence $T:=(\tau_{1},\ldots,\tau_{n})$ of numbers, if the agent at rank $i$
in the order gets a bundle of value at least $\tau_{i}$ times her MMS value.
This framework captures both ordinal approximation and multiplicative
approximation as special cases. We show the existence of $T$-MMS allocations
where $\tau_{i}\geq\max(\frac{3}{4}+\frac{1}{12n},\frac{2n}{2n+i-1})$ for all
$i$. Furthermore, by ordering the agents randomly, we can get allocations that
are $(\frac{3}{4}+\frac{1}{12n})$-MMS ex-post and $(0.8253+\frac{1}{36n})$-MMS
ex-ante. We also investigate the limitations of our algorithm and show that it
does not give better than $(0.8631+\frac{1}{2n})$-MMS ex-ante.

##  1 Introduction

Fair allocation of resources (goods) is a fundamental problem in multiple
disciples, including computer science, economics, and social choice theory,
where the goal is to divide a set $M$ of $m$ goods among a set $N$ of $n$
agents in a _fair_ manner. This field has received significant attention since
the seminal work of Steinhaus in the 1940s [Ste48]. When the goods are
divisible, the two standard fairness notions are _envy-freeness_ and
_proportionality_ , based on envy and share, respectively. In an envy-free
allocation, no agent prefers another agent’s allocation, and in a proportional
allocation, each agent receives her proportionate share, i.e., at least a
$1/n$ fraction of her value of all the goods. In the case of divisible goods,
an envy-free and proportional allocation exists; see [Var74, Fol67, AM16].

We study the discrete setting, in which each good can be given to exactly one
agent. Let $v_{i}:2^{M}\rightarrow\mathbb{R}_{\geq 0}$ denote the valuation
function of agent $i$. We assume that $v_{i}(.)$’s are additive, i.e.,
$v_{i}(S)=\sum_{g\in S}v_{i}(\\{g\\})$. Simple examples show that in the
discrete case, neither envy-freeness nor proportionality can be
guaranteed.***Consider an instance with two agents and one good with positive
value to both agents. This necessitates the refinement of these notions.

We consider the natural and most popular discrete analog of proportionality
called _maximin share_ (MMS) introduced in [Bud11]. It is also shown to be
preferred by participating agents in real-life experiments [GGD20]. The MMS
value of an agent is the maximum value she can guarantee if she divides the
goods into $n$ bundles (one for each agent) and then receives a bundle with
the minimum value. Formally, for a set $S$ of goods and an integer $d$, let
$\Pi_{d}(S)$ denote the set of all partitions of $S$ into $d$ bundles. Then,

$\displaystyle\text{MMS}_{i}^{d}(S):=\max_{(P_{1},\ldots,P_{d})\in\Pi_{d}(S)}\min_{j}v_{i}(P_{j}).$

The MMS value of agent $i$ is denoted by
$\text{MMS}_{i}:=\text{MMS}_{i}^{n}(M)$. An allocation is said to be MMS if
each agent receives at least their MMS value. However, MMS is an unfeasible
share guarantee that cannot always be satisfied when there are more than two
agents with additive valuations [PW14, KPW18, FST21]. Therefore, the MMS share
guarantee needs to be relaxed, and the two natural ways are its multiplicative
and ordinal approximations.

#####  $\alpha$-MMS

Since we need to lower the share threshold, a natural way is to consider
$\alpha<1$ times the MMS value. Formally, an allocation
$X=(X_{1},\ldots,X_{n})$ is $\alpha$-MMS if for each agent $i$,
$v_{i}(X_{i})\geq\alpha\cdot\text{MMS}_{i}$. Earlier works showed the
existence of $2/3$-MMS allocations using several different approaches [PW14,
AMNS17, BK20, GMT18, KPW18]. Later, in a groundbreaking work [GHS+18], the
existence of $3/4$-MMS allocations was obtained through more sophisticated
techniques and involved analysis. This factor was slightly improved to
$3/4+1/(12n)$ in [GT21], then more recently to
$\frac{3}{4}+\min(\frac{1}{36},\frac{3}{16n-4})$ [AGST23], and finally to
$3/4+3/3836$ [AG24]. On the other hand, $\alpha$-MMS allocations need not
exist for $\alpha>1-1/n^{4}$ [FST21].

#####  $1$-out-of-$d$ MMS

Another natural way of relaxing MMS is to consider the share value of
$\text{MMS}_{i}^{d}(M)$ for $d>n$ for each agent $i$, which is the maximum
value that $i$ can guarantee if she divides the goods into $d$ bundles and
then takes a bundle with the minimum value. This notion was introduced
together with the MMS notion in [Bud11], which also shows the existence of
$1$-out-of-$(n+1)$ MMS after _adding excess goods_. Unlike $\alpha$-MMS, this
notion is robust to small perturbations in the values of goods because it only
depends on the bundles’ ordinal ranking and is not affected by small
perturbations as long as the ordinal ranking of the bundles does not
change.†††The $\alpha$-MMS is very sensitive to agents’ precise cardinal
valuations: Consider the example mentioned in [HSSH21]. Assume $n=3$ and there
are four goods $g_{1}$, $g_{2}$, $g_{3}$ and $g_{4}$ with values $30$, $39$,
$40$ and $41$ respectively for agent $1$. Assume the goal is to guarantee the
$3/4$-MMS value of each agent. We have $\text{MMS}_{1}=40$, and therefore any
non-empty bundle satisfies $3/4$-MMS for agent $1$. However, if the value of
$g_{3}$ gets slightly perturbed and becomes $40+\epsilon$ for any
$\epsilon>0$, then $\text{MMS}_{1}>40$ and then $3/4\cdot\text{MMS}_{1}>30$
and the bundle $\\{g_{1}\\}$ does not satisfy agent $1$. Thus, the
acceptability of a bundle (in this example, $\\{g_{1}\\}$) might be affected
by an arbitrarily small perturbation in the value of an irrelevant good (i.e.,
$g_{3}$). Observe that in this example, whether the value of $g_{3}$ is $40$
or $40+\epsilon$ for any $\epsilon\in\mathbb{R}$, $\\{g_{1}\\}$ is an
acceptable $1$-out-of-$4$ MMS bundle for agent $1$.

In the standard setting (i.e., without excess goods), the first non-trivial
ordinal approximation was the existence of $1$-out-of-$(2n-2)$ MMS allocations
[AHSH19], which was later improved to $1$-out-of-$\lceil 3n/2\rceil$ [HS21],
and then to the current state-of-the-art $1$-out-of-$\lfloor 3n/2\rfloor$
[HSSH21]. On the other hand, the (non-)existence of $1$-out-of-$(n+1)$ MMS
allocations is open to date.

Our first main result in the following theorem shows that $1$-out-of-$4\lceil
n/3\rceil$ MMS allocations always exist, thereby improving the state-of-the-
art of $1$-out-of-$d$ MMS.

######  Theorem 1.

$1$-out-of-$4\lceil n/3\rceil$ MMS allocations always exist.

Our proof is constructive; we give a simple algorithm to achieve $1$-out-
of-$4\lceil n/3\rceil$ MMS allocations. Our algorithm just utilizes _bag-
filling_ , where we initialize $n$ bags $\\{B_{1},\dots,B_{n}\\}$ with a
particular set of two goods in each. Then, we iterate over the bags, and in
each round $j$, we keep adding more goods to the bag $B_{j}$ until its value
is at least $\text{MMS}^{d}_{i}$ for some agent $i$, who has not received a
bag yet, and $d=4\lceil\frac{n}{3}\rceil$. Then, we allocate $B_{j}$ to any
such agent $i$ and proceed.

We note that our algorithm is very similar to the bag-filling phase of
algorithms in [GT21, AGST23] which obtain $\frac{3}{4}+O(\frac{1}{n})$-MMS
allocations. However, these algorithms use another critical phase called
_valid reductions_ before bag-filling. Valid reductions allocate a set of
goods to an agent $i$ such that while $i$ gets her desired share
($\alpha\cdot\text{MMS}_{i}$), the MMS values of the other agents do not drop.
The bag-filling phase in these algorithms is run only when no more valid
reductions are feasible. It provides strong bounds on the values of the
remaining goods utilized in the analysis of the bag-filling phase. However, it
is unclear how to use valid reduction in an algorithm to find $1$-out-of-$d$
MMS allocations. This is because $d$ is not the same as $n$, and our goal is
to guarantee exact $1$-out-of-$d$ MMS allocations and not an $\alpha$
approximation of it. Consequently, our analysis is totally different from the
ones in [GT21, AGST23], and much more involved and challenging. We give an
overview of our analysis in Section 3.1. We also give a tight example showing
that Theorem 1 has the best factor possible with this approach (Section 3.5).

Another way to interpret $1$-out-of-$d$ MMS allocations is giving $n/d$
fraction of agents their MMS value and nothing to the remaining agents. We
prove this equivalence in Section 2. Both ordinal and multiplicative
approximations focus on extremes. In $1$-out-of-$d$ MMS, some agents get
nothing, and others are guaranteed their _full_ MMS value. In $\alpha$-MMS,
each agent receives (the same factor) $\alpha<1$ fraction of their MMS value.
As a middle ground between these two extreme notions, we introduce a general
framework of _approximate MMS with agent priority ranking_ , where each agent
has a unique _priority rank_ from the set $\\{1,\ldots,n\\}$. We are also
given a list of _thresholds_ $T:=(\tau_{1},\tau_{2},\ldots,\tau_{n})$ where
$1\geq\tau_{1}\geq\ldots\geq\tau_{n}\geq 0$. An allocation is said to be
$T$-MMS if the agent with priority rank $i$ gets a bundle of value at least
$\tau_{i}$ times her MMS value. This framework captures both ordinal and
multiplicative approximations as special cases. Namely, an $\alpha$-MMS
allocation corresponds to the case where $\tau_{i}=\alpha$ for all $i\in[n]$,
and $1$-out-of-$d$ allocations correspond to the case where the first $n/d$
thresholds in $T$ are 1 and the rest are 0. Furthermore, the
$(\alpha,\beta)$-framework introduced in [HS21], where $\alpha$ fraction of
agents receive $\beta$-MMS, is another special case where the first $n\alpha$
thresholds in $T$ are $\beta$ and the rest are 0.

Our second main result in the following theorem shows that a $T$-MMS
allocation always exists where
$\tau_{i}=\max(\frac{3}{4}+\frac{1}{12n},\frac{2n}{2n+i-1})$ for all
$i\in[n]$.

######  Theorem 2.

$T=(\tau_{1},\ldots,\tau_{n})$-MMS allocations exist when
$\tau_{i}:=\max\left(\frac{2n}{2n+i-1},\frac{3}{4}+\frac{1}{12n}\right)$ for
all $i\in N$.

We prove Theorem 2 constructively by giving an allocation algorithm. Our
algorithm is almost identical to that of [GT21]. The main difference is that
when multiple agents are eligible to receive a bundle, we give the bundle to
the agent with the smallest priority rank. However, despite a similar
algorithm, our analysis is totally different from theirs. Our algorithm, like
theirs, performs a few _reduction_ operations (phase 1) until the instance
becomes _irreducible_ , and then does bag filling (phase 2). They prove that
reduction operations in their algorithm are _valid_ , so they only need to
prove their claim for irreducible instances. In our setting, reduction
operations may not be valid, so we need to prove our claim for non-irreducible
instances too. To do this, we bound the values of bundles from both phases
together.

Another approach to get fair allocations is to use randomization. For example,
when there is a single good, giving the good to an agent selected uniformly
randomly is fair. Hence, one can also consider the fairness of probability
distributions of allocations. However, randomness by itself is unsatisfactory:
giving all the goods to a random agent is fair because each agent has equal
opportunity, but is unfair after the randomness is realized due to the large
disparity in this allocation. To fix this, one can aim for a _best-of-both-
worlds_ approach (see, e.g., [AAGW15, FSV20, BEF22, AFSV23, FMNP23]) i.e.,
find a distribution of allocations where each allocation in the support of the
distribution is fair (ex-post fairness), and the entire distribution is fair
in a randomized sense (ex-ante fairness). For example, Babaioff et al. [BEF22]
gave an algorithm whose output is ex-post $1/2$-MMS and ex-ante proportional,
i.e., it outputs a distribution over $1/2$-MMS allocations, such that each
agent’s expected value of her bundle is at least $v_{i}(M)/n$.

By ordering the agents randomly in Theorem 2, we can get allocations that are
$(\frac{3}{4}+\frac{1}{12n})$-MMS ex-post and $(0.8253+\frac{1}{36n})$-MMS ex-
ante. On the other hand, we show that our algorithm cannot give better than
ex-ante $(0.8631+\frac{1}{2n})$-MMS, regardless of how we pick the thresholds
(Section 4.3). The analysis of many MMS-approximation algorithms has a natural
property called _obliviousness_. In Appendix B, we show that obtaining better
than ex-ante $(0.8578+\frac{1}{3n})$-MMS with our algorithm (for some choice
of thresholds) requires non-oblivious proof techniques.

###  1.1 Further Related Work

Since the MMS notion and its variants have been intensively studied, we mainly
focus on closely related work here. Computing the MMS value of an agent is NP-
hard, but a PTAS exists [Woe97]. For $n=2$, MMS allocations always exist
[BL16]. For $n=3$, a series of work has improved the MMS approximation from
$3/4$ [PW14] to $7/8$ [AMNS17] to $8/9$ [GM19], and then to $11/12$ [FN22].
For $n=4$, $(4/5)$-MMS allocations exist [GHS+18, BF22].

Babaioff et al. [BNT21] considered $\ell$-out-of-$d$ MMS, in which the MMS
value of an agent is the maximum value that can be guaranteed by partitioning
goods into $d$ bundles and selecting the $\ell$ least-valuable ones. This was
further studied by Segal-Halevi [SH19, SH17]. Currently, the best result is
the existence of $\ell$-out-of-$\lfloor(\ell+\frac{1}{2})n\rfloor$ MMS
[HSSH21]. The MMS and its ordinal approximations have also been applied in the
context of cake-cutting problems [ESHS21a, ESHS21b, ESHS20, BM23].

Many works have analyzed randomly generated instances. Bouveret and Lemaître
[BL16] showed that MMS allocations usually exist (for data generated randomly
using uniform or Gaussian valuations). MMS allocations exist with high
probability when the valuation of each good is drawn independently and
randomly from the uniform distribution on $[0,1]$ [AMNS17] or for arbitrary
distributions of sufficiently large variance [KPW16].

MMS can be analogously defined for fair division of chores where items provide
negative value. Like the case of the goods, MMS allocations do not always
exist for chores [ARSW17]. Many papers studied approximate MMS for chores
[ARSW17, BK20, HL21], with the current best approximation ratio being $13/11$
[HSH23]. For three agents, $19/18$-MMS allocations exist [FN22]. Also, ordinal
MMS approximation for chores has been studied, and it is known that $1$-out-
of-$\lfloor 3n/4\rfloor$ MMS allocations exist [HSSH22]. The chores case turns
out to be easier than goods due to its close relation with the well-studied
variants of bin-packing and job scheduling problems.

MMS has also been studied for non-additive valuations [ASMS23, GHS+18, LV21].
Generalizations have been studied where restrictions are imposed on the set of
allowed allocations, like matroid constraints [GM19], cardinality constraints
[BB18], and graph connectivity constraints [BILS22, TL20]. Stretegyproof
versions of fair division have also been studied [BGJ+19, ABM16, ABCM17,
ALW19]. MMS has also inspired other notions of fairness, like weighted MMS
[FGH+19], AnyPrice Share (APS) [BEF21], Groupwise MMS [BBMN18, CKMS21], and
self-maximizing shares [BF22].

##  2 Preliminaries

For $t\in\mathbb{N}$, we denote the set $\\{1,2,\ldots,t\\}$ by $[t]$. A
discrete fair division instance is denoted by $(N,M,\mathcal{V})$, where $N$
is the set of $n$ agents, $M$ is the set of $m$ indivisible goods, and
$\mathcal{V}=(v_{1},\ldots,v_{n})$ is the vector of agents’ valuation
function. Often, we assume (without loss of generality) that $N=[n]$ and
$M=[m]$. For all $i\in[n]$, $v_{i}:2^{M}\rightarrow\mathbb{R}_{\geq 0}$ is the
valuation function of agent $i$ over all subsets of the goods. In this paper,
we assume $v_{i}(\cdot)$ is additive for all $i\in[n]$, i.e.,
$v_{i}(S)=\sum_{g\in S}v_{i}(\\{g\\})$ for all $S\subseteq M$. For ease of
notation, we also use $v_{i}(g)$ and $v_{i,g}$ instead of $v_{i}(\\{g\\})$. An
allocation $X=(X_{1},\ldots,X_{n})$ is a partition of the goods into $n$
bundles such that each agent $i\in[n]$ receives $X_{i}$.

For a set $S$ of goods and any positive integers $d$, let $\Pi_{d}(S)$ denote
the set of all partitions of $S$ into $d$ bundles. Then,

$\displaystyle\text{MMS}_{i}^{d}(S):=\max_{P\in\Pi_{d}(S)}\min_{j=1}^{d}v_{i}(P_{j}).$
(1)

Setting $d=n$, we obtain the standard MMS notion. Formally,
$\text{MMS}_{i}=\text{MMS}^{n}_{i}(M)$. We call an allocation $X$ _$1$ -out-
of-$d$ MMS_, if for all agents $i$, $v_{i}(X_{i})\geq\text{MMS}^{d}_{i}(M)$.
For each agent $i$, $d$-MMS partition of $i$ is a partition
$P=(P_{1},\ldots,P_{d})$ of $M$ into $d$ bundles such that
$\min_{j=1}^{d}v_{i}(P_{j})$ is maximized. Basically, for a $d$-MMS partition
$P$ of agent $i$, $\text{MMS}_{i}^{d}(M)=\min_{j=1}^{d}v_{i}(P_{j})$. In the
rest of the paper, for each agent $i$, we denote a $d$-MMS partition of $i$ by
$P^{i}=(P^{i}_{1},\ldots,P^{i}_{d})$.

Consider a fair division instance with $n$ agents, where each agent $i$ has a
unique priority rank $r_{i}\in[n]$. Let $T:=(\tau_{1},\ldots,\tau_{n})$ be a
list of numbers, where $1\geq\tau_{1}\geq\ldots\geq\tau_{n}\geq 0$. An
allocation $X$ is $T$-MMS if for all $i\in[n]$, we have
$v_{i}(X_{i})\geq\tau_{r_{i}}\cdot\text{MMS}_{i}$. Henceforth, unless stated
otherwise, we assume that $r_{i}=i$ for all $i\in[n]$. This assumption is
without loss of generality, since we can just renumber the agents.

######  Lemma 1.

For integers $d\geq n$, let $T$ be a list of length $d$ having $n$ ones and
$d-n$ zeros. Then $1$-out-of-$d$ MMS allocations exist for all instances with
$n$ agents and additive valuations if and only if $T$-MMS allocations exist
for all instances with $d$ agents and additive valuations.

###### Proof.

All valuations considered in this proof are additive.

First, assume $1$-out-of-$d$ MMS allocations exist for all instances with $n$
agents. Consider any instance $\mathcal{I}=([d],M,(v_{1},\ldots,v_{d}))$ with
$d$ agents. Then for the instance
$\mathcal{I}^{\prime}=([n],M,(v_{1},\ldots,v_{n}))$, a $1$-out-of-$d$ MMS
allocation $X^{\prime}$ exists. Hence,
$v_{i}(X_{i}^{\prime})\geq\text{MMS}_{i}^{d}(M)$ for all $i\in[n]$. Let $X$ be
an allocation of $M$ over $d$ agents where $X_{i}=X_{i}^{\prime}$ for
$i\in[n]$ and $X_{i}=\emptyset$ for $i\in[d]\setminus[n]$. Then $X$ is a
$T$-MMS allocation for $\mathcal{I}$. Since the choice of $\mathcal{I}$ was
arbitrary, we get that $T$-MMS allocations exist for all instances with $d$
agents.

Now assume $T$-MMS allocations exist for all instances with $d$ agents.
Consider any instance $\mathcal{I}=([n],M,(v_{1},\ldots,v_{n}))$. Add $d-n$
dummy agents with arbitrary additive valuations $v_{n+1},\ldots,v_{d}$. Let
$\mathcal{I}^{\prime}=([d],M,(v_{1},\ldots,v_{d}))$ be the resulting instance.
Then a $T$-MMS allocation $X^{\prime}$ exists for $\mathcal{I}^{\prime}$,
i.e., $v_{i}(X_{i}^{\prime})\geq\text{MMS}_{i}^{d}(M)$ for all $i\in[n]$.
Hence, $X=(X_{1}^{\prime},\ldots,X_{n}^{\prime})$ is a 1-out-of-$d$ MMS
allocation for $\mathcal{I}$. Since the choice of $\mathcal{I}$ was arbitrary,
we get that 1-out-of-$d$ MMS allocations exist for all instances with $n$
agents. ∎

######  Definition 1.

An instance $\mathcal{I}=(N,M,\mathcal{V})$ is _ordered_ if there exists an
ordering $[g_{1},\ldots,g_{m}]$ of the goods such that for all agents $i$,
$v_{i}(g_{1})\geq\ldots\geq v_{i}(g_{m})$.

######  Definition 2.

An instance $\mathcal{I}=(N,M,\mathcal{V})$ is $d$-normalized if for all
agents $i$, there exists a partition $P=(P_{1},\ldots,P_{d})$ of $M$ into $d$
bundles such that $v_{i}(P_{j})=1$ for all $j\in[d]$.

Barman and Krishnamurthy [BK20] proved that when the goal is to guarantee a
minimum threshold of $\alpha_{i}$ for each agent $i$, it is without loss of
generality to assume the instance is ordered. Akrami et al. [AGST23] proved
that when the goal is to find an approximate MMS allocation, it is without
loss of generality to assume the instance is $n$-normalized and ordered. Their
proof does not rely on the number of agents. Formally, for any
$d\in\mathbb{N}$, when the goal is to find a $1$-out-of-$d$ MMS allocation, it
is without loss of generality to assume the instance is ordered and
$d$-normalized, as shown in the following lemma (proof is in Appendix A).

######  Lemma 2.

For any $d\in\mathbb{N}$, if $1$-out-of-$d$ MMS allocations exist for
$d$-normalized ordered instances, then $1$-out-of-$d$ MMS allocations exist
for all instances.

From now on, even if not mentioned, we assume the instance is ordered and
$d$-normalized. Without loss of generality, for all $i\in[n]$, we assume
$v_{i}(1)\geq v_{i}(2)\geq\ldots\geq v_{i}(m)$. In Section 2.1, we prove some
properties of ordered $d$-normalized instances for arbitrary $d$. In Section
3, we set $d=4\lceil n/3\rceil$ and prove $1$-out-of-$4\lceil n/3\rceil$ MMS
allocations always exist.

###  2.1 1-out-of-d MMS

We prove the existence of $1$-out-of-$4\lceil n/3\rceil$ MMS assuming that $n$
is a multiple of 3. This is without loss of generality, because otherwise we
can copy one of the agents $1$ or $2$ times (depending on $n\bmod 3$) so that
the new instance has $n^{\prime}:=3\lceil n/3\rceil$ agents. Since we prove
the existence of $1$-out-of-$4n^{\prime}/3$ MMS for the new instance, we prove
the existence of an allocation that gives all the agents $i$ in the original
instance their $\text{MMS}^{4n^{\prime}/3}_{i}(M)=\text{MMS}^{4\lceil
n/3\rceil}_{i}(M)$ value. Hence, the existence of $1$-out-of-$4\lceil
n/3\rceil$ MMS allocations follows.

Recall that for a given instance $\mathcal{I}$ and integer $d$, for each agent
$i$, $P^{i}=(P^{i}_{1},\ldots,P^{i}_{d})$ is a $d$-MMS partition of agent $i$.

######  Proposition 1.

Given a $d$-normalized instance for all $i\in N$ and $k\in[d]$, we have

  1. 1.

$v_{i}(P^{i}_{k})=1$, and

  2. 2.

$v_{i}(M)=d$.

We note that it is without loss of generality to assume $m\geq 2d$. Otherwise,
we can add $2d-m$ dummy goods with a value of $0$ for all the agents. The
normalized and ordered properties of the instance would be preserved. Consider
the bag setting with $d$ bags as follow.

$C_{k}:=\\{k,2d-k+1\\}\text{ for }k\in[d]$ (2)

See Figure 1 for more intuition. Next, we show some important properties of
the values of the goods in $C_{k}$’s.

$\scriptstyle{2d}$$\scriptstyle{1}$$\scriptstyle{C_{1}}$$\scriptstyle{2d-k+1}$$\scriptstyle{k}$$\scriptstyle{C_{k}}$$\scriptstyle{d+1}$$\scriptstyle{d}$$\scriptstyle{C_{d}}$
Figure 1: For all $k\in[d]$, we define $C_{k}:=\\{k,2d-k+1\\}$.

######  Proposition 2.

For all agents $i\in N$, we have

  1. 1.

$v_{i}(1)\leq 1$,

  2. 2.

$v_{i}(C_{d})\leq 1$, and

  3. 3.

$v_{i}(d+1)\leq\tfrac{1}{2}$.

###### Proof.

For the first part, fix an agent $i$. Let $1\in P^{i}_{1}$. By Proposition 1,
$v_{i}(1)\leq v_{i}(P^{i}_{1})=1$.

For the second part, by the pigeonhole principle, there exists a bundle
$P^{i}_{k}$ and two goods $j,j^{\prime}\in\\{1,2,\ldots,d+1\\}$ such that
$\\{j,j^{\prime}\\}\subseteq P^{i}_{k}$. Without loss of generality, assume
$j<j^{\prime}$. We have

$\displaystyle v_{i}(C_{d})$ $\displaystyle=v_{i}(d)+v_{i}(d+1)$
($C_{d}=\\{d,d+1\\}$) $\displaystyle\leq v_{i}(j)+v_{i}(j^{\prime})$ ($j\leq
d$ and $j^{\prime}\leq d+1$) $\displaystyle\leq v_{i}(P^{i}_{k})=1.$
($\\{j,j^{\prime}\\}\in P^{i}_{k}$)

For the third part, we have

$\displaystyle 1$ $\displaystyle\geq v_{i}(C_{d})=v_{i}(d)+v_{i}(d+1)\geq
2v_{i}(d+1).$

Thus, $v_{i}(d+1)\leq\tfrac{1}{2}$. ∎

######  Lemma 3.

For all $i\in N$ and $k\in[d]$, $\sum_{j=k}^{d}v_{i}(C_{j})\leq d-k+1$.

###### Proof.

For the sake of contradiction, assume the claim does not hold for some agent
$i$ and let $\ell\geq 1$ be the largest index for which we have
$\sum_{j=\ell}^{d}v_{i}(C_{j})>d-\ell+1$. Proposition 2(2) implies that
$\ell<d$. We have

$\displaystyle v_{i}(\ell)+v_{i}(2d-\ell+1)$ $\displaystyle=v_{i}(C_{\ell})$
$\displaystyle=\sum_{j=\ell}^{d}v_{i}(C_{j})-\sum_{j=\ell+1}^{d}v_{i}(C_{j})$
$\displaystyle>(d-\ell+1)-(d-(\ell+1)+1)$ ($\sum_{j=k}^{d}v_{i}(C_{j})\leq
d-k+1$ for $k>\ell$) $\displaystyle=1.$

For all $j,j^{\prime}<\ell$, $v_{i}(j)+v_{i}(j^{\prime})\geq
v_{i}(\ell)+v_{i}(2d-\ell+1)>1$. Therefore, $j$ and $j^{\prime}$ cannot be in
the same bundle in any $d$-MMS partition of $i$. For $j<\ell$, let $j\in
P^{i}_{j}$. For all $j<\ell$ and $\ell\leq j^{\prime}\leq 2d-\ell+1$,

$\displaystyle v_{i}(j)+v_{i}(j^{\prime})$ $\displaystyle\geq
v_{i}(\ell)+v_{i}(2d-\ell+1)$ $\displaystyle=v_{i}(C_{\ell})>1.$

Therefore, $j^{\prime}\notin P_{j}$. Also, since
$\sum_{j=\ell}^{d}v_{i}(C_{j})>d-\ell+1$, there are at least $t\geq d-\ell+2$
different bundles $Q_{1},\ldots,Q_{t}$ in $P$ such that
$Q_{j}\cap\\{\ell,\ldots,2d-\ell+1\\}\neq\emptyset$. It is a contradiction
since these $t\geq d-\ell+2$ bundles must be different from $P^{i}_{1},\ldots
P^{i}_{\ell-1}$. ∎

##  3 1-out-of-$\mathbf{4\lceil n/3\rceil}$ MMS Algorithm

###  3.1 Technical Overview

For $\alpha$-MMS problem, the algorithms for $\alpha\geq 3/4$ [GHS+18, GT21,
AGST23] utilize the two-phase approach: _valid reductions_ and _bag filling_.
In a valid reduction, the instance is reduced by removing an agent $a$ and a
subset of goods $S$ such that $v_{a}(S)\geq\alpha$, and the MMS values of the
remaining agents do not decrease. The valid reduction phase is crucial for the
bag filling to work in the analysis of these algorithms. However, it is not
clear how to define valid reductions in the case of $1$-out-of-$d$ MMS because
$d$ is not the same as the number of agents $n$. Therefore, we only use bag
filling in our algorithm, which makes its analysis quite involved and entirely
different than from $\alpha$-MMS algorithms.

Algorithm 1 $1$-out-of-$4\lceil n/3\rceil$ MMS

Input: Ordered $4\lceil n/3\rceil$-normalized instance
$\mathcal{I}=(N,[m],\mathcal{V})$.
Output: Allocation $\hat{B}=(\hat{B}_{1},\ldots,\hat{B}_{n})$.

1:for $k\in[n]$ do // Initialization

2: $B_{k}=\\{k,2n-k+1\\}$

3:end for

4:$j\leftarrow 2n+1$

5:for $k\in[n]$ do // Bag-filling

6: while $\nexists i\in N$ s.t. $v_{i}(B_{k})\geq 1$ do

7: $B_{k}\leftarrow B_{k}\cup\\{j\\}$

8: $j\leftarrow j+1$

9: if $j>m$ then

10: Terminate

11: end if

12: end while

13: Let $i\in N$ be s.t. $v_{i}(B_{k})\geq 1$

14: $\hat{B}_{i}\leftarrow B_{k}$

15: $N\leftarrow N\setminus\\{i\\}$

16:end for

17:$\hat{B}_{n}\leftarrow\hat{B}_{n}\cup(M\setminus[j])$

18:return $\hat{B}$

The algorithm is described in Algorithm 1. Given an ordered $d$-normalized
instance, we initialize $n$ bags (one for each agent) with the first $2n$
(highest valued) goods as follows.

$B_{k}:=\\{k,2n-k+1\\}\text{ for }k\in[n].$ (3)

See Figure 2 for a better intuition. Then, we do bag-filling. That is, at each
round $j$, we keep adding goods in decreasing values to the bag $B_{j}$ until
some agent with no assigned bag values it at least $1$ (recall that $1$-out-
of-$d$ MMS value of each agent is 1 in a $d$-normalized instance). Then, we
allocate it to an arbitrary such agent. We note that in contrast to [GT21,
AGST23], in the bag-filling phase we do not add arbitrary goods to the bags
but we add the goods in the decreasing order of their values.

To prove that the output of Algorithm 1 is $1$-out-of-$d$ MMS, it is
sufficient to prove that we never run out of goods in any round or,
equivalently, each agent receives a bag in some round. Towards contradiction,
assume that agent $i$ does not receive a bag and the algorithm terminates. It
can be easily argued that agent $i$’s value for at least one of the initial
bags $\\{B_{1},\ldots,B_{n}\\}$ must be strictly less than $1$. Let $\ell^{*}$
be the smallest such that $v_{i}(B_{\ell^{*}})<1$. We consider two cases based
on the value of $v_{i}(2n-\ell^{*})$. In Section 3.3, we reach a contradiction
assuming $v_{i}(2n-\ell^{*})\geq 1/3$ and in Section 3.4, we reach a
contradiction assuming $v_{i}(2n-\ell^{*})<1/3$.

Let $\hat{B}_{j}$ denote the $j$-th bag at the end of the algorithm. The
overall idea is to categorize the bags into different groups and prove an
upper bound on the value of each bag $(\hat{B}_{j})$ for agent $i$ depending
on which group it belongs to. Since $v_{i}(M)=n$ due to the instance being
$d$-normalized, we get upper and lower bounds on the size of the groups. For
example, if we know that for all bags $\hat{B}_{j}$ in a certain group
$v_{i}(\hat{B}_{j})<1$, we get the trivial upper bound of $n-1$ on the size of
this group since $n=v_{i}(M)=\sum_{j\in[n]}v_{i}(\hat{B}_{j})$.

Unfortunately, upper bounding the value of the bags is not enough to reach a
contradiction in all cases. However, for these cases, we have upper and lower
bounds on the size of each group, and in general, we show several additional
properties to make it work. For example, we obtain nontrivial upper bounds on
the values of certain subsets of goods using the fact that all bundles in a
$d$-MMS partition of agent $i$ have value $1$ (see Lemmas 6 and 14).

###  3.2 Algorithm

Our algorithm (shown in Algorithm 1) consists of _initialization_ and _bag-
filling_. First, we remark that assuming $|M|\geq 2n$ is without loss of
generality. This is because we can always add dummy goods to $M$ with a value
of $0$ for all the agents. The resulting instance is ordered and
$d$-normalized if the original instance has these properties.

As mentioned in Section 3.1, the algorithm first initialize $n$ bags as in (3)
(see Figure 2).

$\scriptstyle{2n}$$\scriptstyle{1}$$\scriptstyle{B_{1}}$$\scriptstyle{2n-k+1}$$\scriptstyle{k}$$\scriptstyle{B_{k}}$$\scriptstyle{n+1}$$\scriptstyle{n}$$\scriptstyle{B_{n}}$
Figure 2: Bag initialization

Then, in each round $j$ of bag-filling, we keep adding goods in decreasing
value to the bag $B_{j}$ until some agent with no assigned bag values it at
least $1$. Then, we allocate it to an arbitrary such agent.

In the rest of this section, we prove the following theorem, showing the
correctness of the algorithm.

######  Theorem 3.

Given any ordered $4\lceil n/3\rceil$-normalized instance, Algorithm 1 returns
a $1$-out-of-$4\lceil n/3\rceil$ MMS allocation.

To do so, it suffices to prove that we never run out of goods in bag-filling.
Towards contradiction, assume that the algorithm stops before all agents
receive a bundle. Let $i$ be an agent with no bundle. Let $\hat{B}_{j}$ be the
$j$-th bundle after bag-filling.

######  Observation 1.

For all $j,k$ such that $j\leq k\leq n$, $v_{i}(\hat{B}_{j})\leq
1+v_{i}(2n-k+1)$.

###### Proof.

Let $g$ be the good with the largest index in $\hat{B}_{j}$. If $g=2n-j+1$,
$v_{i}(\hat{B}_{j}\setminus\\{g\\})=v_{i}(j)\leq 1$ by Proposition 2(1). If
$g>2n-j+1$, meaning that $g$ was added to $\hat{B}_{j}$ during bag-filling,
then $v_{i}(\hat{B}_{j}\setminus\\{g\\})<1$. Otherwise, $g$ would not be added
to $\hat{B}_{j}$. Therefore,

$\displaystyle v_{i}(\hat{B_{j}})$
$\displaystyle=v_{i}(\hat{B}_{j}\setminus\\{g\\})+v_{i}(g)$ $\displaystyle\leq
1+v_{i}(2n-k+1).$ ($v_{i}(\hat{B}_{j}\setminus\\{g\\})\leq 1$ and $g\geq
2n-k+1$)

∎

######  Observation 2.

For all $j,k$ such that $k\leq j\leq n$,
$v_{i}(\hat{B}_{j})\leq\max(1+v_{i}(2n-k+1),2v_{i}(k))$.

###### Proof.

First, assume $\hat{B}_{j}\neq B_{j}$ and $g$ be the last good added to
$\hat{B}_{j}$. We have $v_{i}(\hat{B}_{j}\setminus\\{g\\})<1$. Otherwise, $g$
would not be added to $\hat{B}_{j}$. Therefore,

$\displaystyle v_{i}(\hat{B_{j}})$
$\displaystyle=v_{i}(\hat{B}_{j}\setminus\\{g\\})+v_{i}(g)$
$\displaystyle<1+v_{i}(2n-k+1).$ ($v_{i}(\hat{B}_{j}\setminus\\{g\\})<1$ and
$g>2n-k+1$)

Now assume $\hat{B}_{j}=B_{j}$. We have

$\displaystyle v_{i}(\hat{B}_{j})$ $\displaystyle=v_{i}(B_{j})$
$\displaystyle=v_{i}(j)+v_{i}(2n-j+1)$ $\displaystyle\leq 2v_{i}(k).$
($2n-j+1>j\geq k$)

Hence, $v_{i}(\hat{B}_{j})\leq\max(1+v_{i}(2n-k+1),2v_{i}(k))$. ∎

######  Observation 3.

There exists a bag $B_{j}$, such that $v_{i}(B_{j})<1$.

###### Proof.

Otherwise, the algorithm would allocate the remaining bag with the smallest
index to agent $i$. ∎

Let $\ell^{*}$ be the smallest such that $v_{i}(B_{\ell^{*}+1})<1$. I.e.,
$B_{\ell^{*}+1}$ is the leftmost bag in Figure 2 with a value less than $1$ to
agent $i$. In Section 3.4, we reach a contradiction assuming
$v_{i}(2n-\ell^{*})<1/3$ and prove Theorem 4.

######  Theorem 4.

If Algorithm 1 does not allocate a bag to some agent $i$, then
$v_{i}(2n-\ell^{*})\geq 1/3$ where $\ell^{*}$ is the smallest index such that
$v_{i}(B_{\ell^{*}+1})<1$.

In Section 3.3, we reach a contradiction assuming $v_{i}(2n-\ell^{*})\geq 1/3$
and prove Theorem 5.

######  Theorem 5.

If Algorithm 1 does not allocate a bag to some agent $i$, then
$v_{i}(2n-\ell^{*})<1/3$ where $\ell^{*}$ is smallest such that
$v_{i}(B_{\ell^{*}+1})<1$.

By Theorems 4 and 5, agent $i$ who receives no bundle by the end of Algorithm
1 does not exist, and Theorem 3 follows.

###  3.3 $\mathbf{v_{i}(2n-\ell^{*})\geq 1/3}$

In this section we assume $v_{i}(2n-\ell^{*})=1/3+x$ for $x\geq 0$. We define
$A^{+}:=\\{B_{1},B_{2},\ldots,B_{\ell^{*}}\\}$; see Figure 3.

$\scriptstyle{A^{+}}$$\scriptstyle{2n}$$\scriptstyle{1}$$\scriptstyle{B_{1}}$$\scriptstyle{2n-\ell^{*}+1}$$\scriptstyle{\ell^{*}}$$\scriptstyle{B_{\ell^{*}}}$$\scriptstyle{\\{B_{\ell^{*}+1},\ldots,B_{s}\\}\subset
A^{1}\cup
A^{2}}$$\scriptstyle{2n-\ell^{*}}$$\scriptstyle{\ell^{*}+1}$$\scriptstyle{B_{\ell^{*}+1}}$$\scriptstyle{2n-s+1}$$\scriptstyle{s}$$\scriptstyle{B_{s}}$$\scriptstyle{\\{B_{s+1},\ldots,B_{n}\\}\subset
A^{2}}$$\scriptstyle{n+1}$$\scriptstyle{n}$$\scriptstyle{B_{n}}$

Figure 3: An illustration of which group each bag belongs to.

######  Observation 4.

For all $B_{j}\in A^{+}$, $\hat{B}_{j}=B_{j}$.

###### Proof.

For all $B_{j}\in A^{+}$, $v_{i}(B_{j})\geq 1$. Since $i$ did not receive any
bundle, $B_{j}$ must have been assigned to some other agent, and no good
needed to be added to $B_{j}$ in bag-filling since there is an agent (namely
$i$) with no bag who values $B_{j}$ at least $1$. ∎

######  Observation 5.

For all $j\geq 2n-\ell^{*}$, $v_{i}(j)<1/2$.

###### Proof.

Since $v_{i}(B_{\ell^{*}+1})=v_{i}(\ell^{*}+1)+v_{i}(2n-\ell^{*})<1$ and
$v_{i}(2n-\ell^{*})\leq v_{i}(\ell^{*}+1)$, $v_{i}(2n-\ell^{*})<1/2$. Also for
all $j\geq 2n-\ell^{*}$, $v_{i}(j)\leq v_{i}(2n-\ell^{*})<1/2$. ∎

######  Corollary 1 (of Observation 5).

$x<1/6$.

Let $s$ be the smallest such that either the algorithm stops at step $s+1$ or
$B_{s+1}$ gets more than one good in bag-filling.

######  Observation 6.

$s\geq\ell^{*}$.

###### Proof.

For all $j<\ell^{*}$, $v_{i}(B_{j+1})\geq 1$. Since $i$ did not receive any
bundle, $B_{j+1}$, must have been assigned to another agent. Therefore, the
algorithm does not stop at step $j+1$. Also, by Observation 4, $B_{j+1}$ gets
no good in bag-filling. ∎

Let $A^{1}$ be the set of bags in $\\{B_{\ell^{*}+1},\ldots,B_{s}\\}$ which
receive exactly one good in bag-filling. Formally,
$A^{1}=\\{B_{j}|\ell^{*}<j\leq s\text{ and }|\hat{B}_{j}|=3\\}$. Let
$A^{2}=\\{B_{1},B_{2},\ldots,B_{n}\\}\setminus(A^{+}\cup A^{1})$.

######  Lemma 4.

For all $B_{j}\in A^{2}$, $v_{i}(B_{j})<4/3-2x$.

###### Proof.

We have

$\displaystyle 1$ $\displaystyle>v_{i}(B_{\ell^{*}+1})$
$\displaystyle=v_{i}(\ell^{*}+1)+v_{i}(2n-\ell^{*})$
$\displaystyle=v_{i}(\ell^{*}+1)+\frac{1}{3}+x.$

Hence, $v_{i}(\ell^{*}+1)<2/3-x$. Also, for $B_{j}\in A^{2}$, we have

$\displaystyle v_{i}(B_{j})$ $\displaystyle=v_{i}(j)+v_{i}(2n-j+1)$
$\displaystyle\leq 2v_{i}(\ell^{*}+1)$ ($2n-j+1>j\geq\ell^{*}+1$ since
$B_{j}\in A^{2}$) $\displaystyle<\frac{4}{3}-2x.$

So if $\hat{B}_{j}=B_{j}$, the inequality holds. Now assume $\hat{B}_{j}\neq
B_{j}$. This implies that $j\geq s+1$ and the algorithm did not stop at step
$j$ before adding a good to $B_{j}$. Therefore it did not stop at step $s+1$
before adding a good to $B_{s+1}$ either. Let $g$ be the first good added to
$B_{s+1}$. Since $B_{s+1}$ requires more than one good,

$\displaystyle 1$ $\displaystyle>v_{i}(B_{s+1}\cup\\{g\\})$
$\displaystyle=v_{i}(s+1)+v_{i}(n-s)+v_{i}(g)$ $\displaystyle\geq
2v_{i}(2n-\ell^{*})+v_{i}(g)$ ($s+1<n-s\leq 2n-\ell^{*}$)
$\displaystyle=\frac{2}{3}+2x+v_{i}(g).$

Therefore, $v_{i}(g)<1/3-2x$. Now let $h$ be the last good added to bag
$B_{j}$. We have

$\displaystyle v_{i}(\hat{B}_{j})$
$\displaystyle=v_{i}(\hat{B}_{j}\setminus\\{h\\})+v_{i}(h)$
$\displaystyle<1+v_{i}(g)$ ($v_{i}(\hat{B}_{j}\setminus\\{h\\})<1$ and
$v_{i}(h)\leq v_{i}(g)$) $\displaystyle<\frac{4}{3}-2x.$

∎

######  Lemma 5.

For all $B_{j}\in A^{+}\cup A^{1}$, $v_{i}(\hat{B}_{j})\leq 4/3+x$.

###### Proof.

First assume $B_{j}\in A^{+}$. We have $j\leq\ell^{*}$. Also,

$\displaystyle v_{i}(\hat{B}_{j})$ $\displaystyle=v_{i}(B_{j})$
($\hat{B}_{j}=B_{j}$) $\displaystyle=v_{i}(j)+v_{i}(2n-j+1)$
$\displaystyle\leq 1+v_{i}(2n-\ell^{*})$ ($v_{i}(j)\leq 1$ and
$2n-j+1>2n-\ell^{*}$) $\displaystyle=\frac{4}{3}+x.$

Now assume $B_{j}\in A^{1}$. Let $g$ be the good added to bag $B_{j}$ in bag-
filling. We have,

$\displaystyle v_{i}(\hat{B}_{j})$ $\displaystyle=v_{i}(B_{j})+v_{i}(g)$
$\displaystyle<1+v_{i}(2n-\ell^{*})$ ($v_{i}(B_{j})<1$ and $v_{i}(g)\leq
v_{i}(2n+1)\leq v_{i}(2n-\ell^{*})$) $\displaystyle=\frac{4}{3}+x.$

∎

Let $|A^{1}|=2n/3+\ell$. Then
$|A^{2}|=n-\ell^{*}-(2n/3+\ell)=n/3-(\ell+\ell^{*})$. If $\ell+\ell^{*}\leq
0$, then $|A^{2}|\geq n/3$ and hence there are at least $n/3$ bags with value
less than $4/3-2x$ (by Lemma 4) and at most $2n/3$ bags with value at most
$4/3+x$ (by Lemma 5). Hence,

$v_{i}(M)<\frac{n}{3}(\frac{4}{3}-2x)+\frac{2n}{3}(\frac{4}{3}+x)=\frac{4n}{3},$

which is a contradiction since $v_{i}(M)=4n/3$. So assume $\ell+\ell^{*}>0$.

Limit the goods in a $1$-out-of-$4n/3$ MMS partition
$P^{i}=(P^{i}_{1},\dots,P^{i}_{4n/3})$ of agent $i$ to
$\\{1,\ldots,8n/3+\ell\\}$ and let $Q$ be the set of bags in $P^{i}$
containing goods $\\{1,\ldots,\ell^{*}\\}$. Formally,
$Q=\\{P_{j}^{i}\cap\\{1,\ldots,8n/3+\ell\\}:|P_{j}^{i}\cap\\{1,\ldots,\ell^{*}\\}|\geq
1\\}$. Let $t$ be the number of bags of size $1$ in $Q$.

$\scriptstyle{2n}$$\scriptstyle{1}$$\scriptstyle{B_{1}}$..$\scriptstyle{B_{2\ell+t+2\ell^{*}-2n/3}}$$\scriptstyle{2n-t}$$\scriptstyle{t+1}$$\scriptstyle{B_{t+1}}$$\scriptstyle{2n-\ell^{*}+1}$$\scriptstyle{\ell^{*}}$$\scriptstyle{B_{\ell^{*}}}$$\scriptstyle{2n-\ell^{*}}$$\scriptstyle{\ell^{*}+1}$$\scriptstyle{2n+1}$$\scriptstyle{B_{\ell^{*}+1}}$$2n-s+1$$\scriptstyle{s}$$\scriptstyle{\frac{8n}{3}+\ell}$$\scriptstyle{B_{s}}$$\scriptstyle{n+1}$$\scriptstyle{n}$$\scriptstyle{B_{n}}$

Figure 4: The first $2\ell+t+2\ell^{*}-2n/3$ goods are marked with red, and
the goods considered in Lemma 6 are marked with blue.

######  Lemma 6.

Let $t$ be the number of bags of size $1$ in $Q=\\{P_{j}^{i}\cap\\{1,\ldots
8n/3+\ell\\}:|P_{j}^{i}\cap\\{1,\ldots\ell^{*}\\}|\geq 1\\}$. Then,

$\displaystyle v_{i}($
$\displaystyle\\{8n/3-2\ell-t-2\ell^{*}+1,\ldots,8n/3+\ell\\}$
$\displaystyle\cup\\{t+1,\ldots,\ell^{*}\\}$
$\displaystyle\cup\\{2n-\ell^{*}+1,\ldots,2n-t\\})\leq 2\ell^{*}+\ell-t.$

The goods considered in Lemma 6 are marked with blue in Figure 4. First, we
prove that the goods mentioned in Lemma 6 are distinct. To that end, it
suffices to prove that $8n/3-2\ell-t-2\ell^{*}+1>2n-t$. It follows from the
fact that $2n/3+\ell+\ell^{*}\leq n$. Before proving Lemma 6, let us show how
to obtain a contradiction assuming this lemma holds. Note that since there are
$n/3-\ell-\ell^{*}$ bags with value less than $4/3-2x$ (namely the bags in
$A^{2}$), it suffices to prove that there exists $3(\ell+\ell^{*})$ other bags
with total value $4(\ell+\ell^{*})$. Since the remaining
$2n/3-2\ell-2\ell^{*}$ bags are of value at most $4/3+x$ (by Lemma 5), we get

$\displaystyle
v_{i}(M)<(\frac{n}{3}-\ell-\ell^{*})(\frac{4}{3}-2x)+(\frac{2n}{3}-2\ell-2\ell^{*})(\frac{4}{3}+x)+4(\ell+\ell^{*})=\frac{4n}{3}$
(4)

which is a contradiction since $v_{i}(M)=4n/3$.

Now consider
$B=\\{\hat{B}_{1},\ldots,\hat{B}_{2\ell+t+2\ell^{*}-2n/3},\hat{B}_{t+1},\ldots,\hat{B}_{\ell^{*}}\\}\cup\hat{A}^{1}$
where $\hat{A}^{1}$ is the set of bags in $A^{1}$ after bag-filling. $B$
consists of $3(\ell+\ell^{*})$ bags. Now we prove that
$v_{i}(\bigcup_{B_{j}\in B}B_{j})\leq 4(\ell+\ell^{*})$. We have

$\displaystyle v_{i}(\bigcup_{\hat{B}_{j}\in B}\hat{B}_{j})\leq v_{i}($
$\displaystyle\bigcup_{B_{j}\in A^{1}}B_{j})$
$\displaystyle+v_{i}({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\\{}$
$\displaystyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1,\ldots,2\ell+t+2\ell^{*}-2n/3\\}})$
$\displaystyle+v_{i}({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\\{}$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}8n/3-2\ell-t-2\ell^{*}+1,\ldots,8n/3+\ell\\}}$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\cup\\{t+1,\ldots,\ell^{*}\\}}$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\cup\\{2n-\ell^{*}+1,\ldots,2n-t\\}}).$

We bound the value of the goods marked with different colors in different
inequalities.

######  Observation 7.

For all $B_{j}\in A^{1}$, $v_{i}(B_{j})<1$.

Since $|A^{1}|=2n/3+\ell$,

$\displaystyle v_{i}(\bigcup_{B_{j}\in A^{1}}B_{j})<2n/3+\ell.$

Also, since all goods are of value at most $1$ to agent $i$,

$\displaystyle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}v_{i}(\\{1,\ldots,2\ell+t+2\ell^{*}-2n/3\\})\leq
2\ell+t+2\ell^{*}-2n/3}.$

By Lemma 6,

$\displaystyle v_{i}($
$\displaystyle\\{8n/3-2\ell-t-2\ell^{*}+1,\ldots,8n/3+\ell\\}$
$\displaystyle\cup\\{t+1,\ldots,\ell^{*}\\}$
$\displaystyle\cup\\{2n-\ell^{*}+1,\ldots,2n-t\\})\leq 2\ell^{*}+\ell-t.$

By adding all the inequalities, we get

$\displaystyle v_{i}(\bigcup_{\hat{B}_{j}\in B}\hat{B}_{j})\leq
4(\ell+\ell^{*}).$

Hence, Inequality (4) holds, which is a contradiction. So the case of
$v_{i}(2n-\ell^{*})\geq 1/3$ cannot arise. See 5

In the rest of this section, we prove Lemma 6.

####  3.3.1 Proof of Lemma 6

To prove Lemma 6, we partition the goods considered in this lemma into two
parts. These parts are colored red and blue in Figure 5. We bound the value of
red goods in Lemma 9, i.e.,

$\sum_{2n-\ell^{*}<j\leq 2n-t}v_{i}(j)+\sum_{8n/3-2\ell-t-2\ell^{*}<j\leq
8n/3-2\ell-2t-\ell^{*}}v_{i}(j)<\ell^{*}-t,$

and the value of the blue goods in Lemma 10, i.e.,

$\sum_{t<j\leq\ell^{*}}v_{i}(j)+\sum_{8n/3-2\ell-2t-\ell^{*}<j\leq
8n/3+\ell}v_{i}(j)\leq\ell^{*}+\ell.$

Thereafter, we have

$\displaystyle v_{i}($
$\displaystyle\\{8n/3-2\ell-t-2\ell^{*}+1,\ldots,8n/3+\ell\\}$
$\displaystyle\cup\\{t+1,\ldots,\ell^{*}\\}$
$\displaystyle\cup\\{2n-\ell^{*}+1,\ldots,2n-t\\})$
$\displaystyle={\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\sum_{2n-\ell^{*}<j\leq
2n-t}v_{i}(j)+\sum_{8n/3-2\ell-t-2\ell^{*}<j\leq
8n/3-2\ell-2t-\ell^{*}}v_{i}(j)}$
$\displaystyle+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\sum_{t<j\leq\ell^{*}}v_{i}(j)+\sum_{8n/3-2\ell-2t-\ell^{*}<j\leq
8n/3+\ell}v_{i}(j)}$ $\displaystyle<(\ell^{*}-t)+(\ell^{*}+\ell)$ (Lemma 9 and
10) $\displaystyle=2\ell^{*}+\ell-t,$

and Lemma 6 follows.

It suffices to prove Lemmas 9 and 10. In the rest of this section, we prove
these two lemmas.

$\scriptstyle{2n}$$\scriptstyle{1}$$\scriptstyle{B_{1}}$$\scriptstyle{\frac{8n}{3}-2\ell}$$\scriptstyle{-2t-\ell^{*}}$$\scriptstyle{2\ell+2t+\ell^{*}}$$\scriptstyle{-\frac{2n}{3}+1}$$\scriptstyle{B_{2\ell+2t+\ell^{*}-\frac{2n}{3}+1}}$$\scriptstyle{\frac{8n}{3}-2\ell-t}$$\scriptstyle{-2\ell^{*}+1}$$\scriptstyle{2\ell+t+2\ell^{*}}$$\scriptstyle{-\frac{2n}{3}}$$\scriptstyle{B_{2\ell+t+2\ell^{*}-\frac{2n}{3}}}$$\scriptstyle{2n-t}$$\scriptstyle{t+1}$$\scriptstyle{B_{t+1}}$$\scriptstyle{2n-\ell^{*}}$$\scriptstyle{\ell^{*}+1}$$\scriptstyle{2n+1}$$\scriptstyle{B_{\ell^{*}+1}}$$2n-s+1$$\scriptstyle{s}$$\scriptstyle{\frac{8n}{3}+\ell}$$\scriptstyle{B_{s}}$

Figure 5: The goods considered in in Lemma 9 are marked with red and the goods
in Lemma 10 are marked with blue.

Limit the goods in a $1$-out-of-$4n/3$ MMS partition of agent $i$ to
$\\{1,\ldots,8n/3+\ell\\}$ and let $R$ be the set of the resulting bags.
Formally, for all $j\in[4n/3]$, $R_{j}=P_{j}^{i}\cap\\{1,\ldots,8n/3+\ell\\}$
and $R=\\{R_{1},\ldots,R_{4n/3}\\}$. Without loss of generality, assume
$|R_{1}|\geq|R_{2}|\geq\ldots\geq|R_{4n/3}|$. Let $t$ be the number of bags of
size $1$ in $R$.

######  Lemma 7.

If there exist $t$ bags of size at most $1$ in $R$, then

$\sum_{1\leq j\leq t+\ell}|R_{j}|\geq 3(t+\ell).$

###### Proof.

Since $R_{j}$’s are sorted in decreasing order of their size,

$\displaystyle\sum_{1\leq j\leq t+\ell}|R_{j}|\geq(t+\ell)|R_{t+\ell}|.$

Hence, if $|R_{t+\ell}|\geq 3$, then $\sum_{1\leq j\leq t+\ell}|R_{j}|\geq
3(t+\ell).$ So assume $|R_{t+\ell}|\leq 2$.

$\displaystyle\frac{8n}{3}+\ell$ $\displaystyle=\sum_{1\leq j\leq
4n/3}|R_{j}|$ $\displaystyle=\sum_{1\leq j\leq
t+\ell}|R_{j}|+\sum_{t+\ell<j\leq 4n/3-t}|R_{j}|+\sum_{4n/3-t<j\leq
4n/3}|R_{j}|$ $\displaystyle\leq\sum_{1\leq j\leq
t+\ell}|R_{j}|+(\frac{4n}{3}-2t-\ell)|R_{t+\ell}|+t$
$\displaystyle\leq\sum_{1\leq j\leq t+\ell}|R_{j}|+2(\frac{4n}{3}-2t-\ell)+t$

Therefore,

$\sum_{j\in[t+\ell]}|R_{j}|\geq 3(\ell+t).$

∎

######  Lemma 8.

$\ell+\ell^{*}+t\leq 4n/3$.

###### Proof.

We have $\ell^{*}+2n/3+\ell\leq s\leq n$. See Figure 4 for intuition.
Therefore, $\ell^{*}+\ell\leq n/3$. Also, $t\leq\ell^{*}\leq n$. Hence
$\ell+\ell^{*}+t\leq 4n/3$. ∎

######  Lemma 9.

$\sum_{2n-\ell^{*}<j\leq 2n-t}v_{i}(j)+\sum_{8n/3-2\ell-t-2\ell^{*}<j\leq
8n/3-2\ell-2t-\ell^{*}}v_{i}(j)<\ell^{*}-t.$

###### Proof.

Let
$B^{\prime}=\\{2n-\ell^{*}+1,\ldots,2n-t\\}\cup\\{8n/3-2\ell-t-2\ell^{*}+1,\ldots,8n/3-2\ell-2t-\ell^{*}\\}$.
$|B^{\prime}|=2(\ell^{*}-t)$ and by Observation 5 for all goods $g\in
B^{\prime}$, $v_{i}(g)<1/2$. Therefore, $v_{i}(B^{\prime})<\ell^{*}-t$. ∎

######  Lemma 10.

$\sum_{t<j\leq\ell^{*}}v_{i}(j)+\sum_{8n/3-2\ell-2t-\ell^{*}<j\leq
8n/3+\ell}v_{i}(j)\leq\ell^{*}+\ell.$

###### Proof.

Recall that $\\{R_{1},\ldots,R_{4n/3}\\}$ is the set of bags in the $1$-out-
of-$4n/3$ MMS partition of agent $i$ after removing goods
$\\{8n/3+\ell+1,\ldots,m\\}$. Moreover, we know exactly $t$ of these bags have
size $1$. If there is a bag $R_{j}=\\{g\\}$ for $g>t$, there must be a good
$g^{\prime}\in[t]$ such that $g^{\prime}\in R_{j^{\prime}}$ and
$|R_{j^{\prime}}|>1$. Swap the goods $g$ and $g^{\prime}$ between $R_{j}$ and
$R_{j^{\prime}}$ as long as such good $g$ exists. Note that
$v_{i}(R_{j^{\prime}})$ can only decrease and
$v_{i}(R_{j})=v_{i}(g^{\prime})\leq 1$. Therefore, in the end of this process
for all $j\in[4n/3]$, $v_{i}(R_{j})\leq 1$ and we can assume bags containing
goods $1,\ldots,t$ are of size $1$ and bags containing goods
$t+1,\ldots,\ell^{*}$ are of a size more than $1$. Recall that
$|R_{1}|\geq\ldots\geq|R_{4n/3}|$. Let $T_{j}$ be the bag that contains good
$j$.

Consider the bags
$B=\\{R_{1},\ldots,R_{t+\ell}\\}\cup\\{T_{t+1},\ldots,T_{\ell^{*}}\\}$. If
$|B|<\ell^{*}+\ell$, keep adding a bag with the largest number of goods to $B$
until there are exactly $\ell^{*}+\ell$ bags in $B$. First we show that $B$
contains at least $3\ell+2\ell^{*}+t$ goods. Namely,

$\sum_{S\in B}|S|\geq 3\ell+2\ell^{*}+t.$

By Lemma 7, $\sum_{1\leq j\leq t+\ell}|R_{j}|\geq 3(t+\ell)$. If all the
remaining $\ell^{*}-t$ bags in $B\setminus\\{R_{1},\ldots,R_{t+\ell}\\}$ are
of size $2$, then $\sum_{S\in B}|S|\geq
3(t+\ell)+2(\ell^{*}-t)=3\ell+2\ell^{*}+t$. Otherwise, there is a bag in $B$
of size at most $1$; hence, all bags outside $B$ are also of size at most $1$.
So we have

$\displaystyle\frac{8n}{3}+\ell$ $\displaystyle=\sum_{S\in B}|S|+\sum_{S\notin
B}|S|$ $\displaystyle\leq\sum_{S\in B}|S|+(\frac{4n}{3}-\ell^{*}-\ell).$

Therefore,

$\displaystyle\sum_{S\in B}|S|$ $\displaystyle\geq 4n/3+2\ell+\ell^{*}$
$\displaystyle\geq 3\ell+2\ell^{*}+t.$ (Lemma 8)

Note that the goods $\\{t+1,\ldots,\ell^{*}\\}$ are contained in $B$ and
moreover, $B$ contains at least
$3\ell+2\ell^{*}+t-(\ell^{*}-t)=3\ell+2t+\ell^{*}$ other goods. Therefore,

$\displaystyle\ell^{*}+\ell$ $\displaystyle\geq\sum_{S\in B}v_{i}(S)$
$\displaystyle\geq\sum_{t<j\leq\ell^{*}}v_{i}(j)+\sum_{8n/3-2\ell-2t-\ell^{*}<j\leq
8n/3+\ell}v_{i}(j).$

The last inequality follows because we used the $3\ell+2t+\ell^{*}$ lowest
valued goods in $[8n/3+\ell]$. ∎

###  3.4 $\mathbf{v_{i}(2n-\ell^{*})<1/3}$

Let $r^{*}$ be largest such that $v_{i}(B_{r^{*}})<1$. That is, $B_{r*}$ is
the rightmost bag in Figure 2 with a value less than $1$ to agent $i$.

######  Lemma 11.

If $v_{i}(2n-r^{*}+1)\leq 1/3$, then $r^{*}<2n/3$.

###### Proof.

Since $1>v_{i}(B_{r^{*}})=v_{i}(r^{*})+v_{i}(2n-r^{*}+1)$, we have
$v_{i}(r^{*})<2/3+x$. By Observation 1, for all $j\leq r^{*}$,
$v_{i}(\hat{B}_{j})\leq 4/3-x$. Also, by Observation 2, for all $j>r^{*}$,
$v_{i}(\hat{B}_{j})<4/3+2x$. Hence, we have

$\displaystyle\frac{4n}{3}$ $\displaystyle=v_{i}(M)$
$\displaystyle=\sum_{j\leq
r^{*}}v_{i}(\hat{B}_{j})+\sum_{j>r^{*}}v_{i}(\hat{B}_{j})$
$\displaystyle<r^{*}(\frac{4}{3}-x)+(n-r^{*})(\frac{4}{3}+2x)$
$\displaystyle=\frac{4n}{3}+x(2n-3r^{*}).$

Therefore, $r^{*}<2n/3$. ∎

######  Lemma 12.

$v_{i}(2n-r^{*}+1)>1/3$.

###### Proof.

Towards contradiction, assume $v_{i}(2n-r^{*}+1)=1/3-x$ for $x\geq 0$. By
Lemma 11, $r^{*}<2n/3$.

######  Claim 1.

$\sum_{j>r^{*}}v_{i}(\hat{B}_{j})<\frac{10n}{9}-r^{*}+\frac{2nx}{3}$.

_Proof._ Note that by the definition of $r^{*}$, for all $j>r^{*}$,
$\hat{B}_{j}=B_{j}$. By Lemma 3,
$v_{i}(\\{2n/3+r^{*}+1,\ldots,2n-r^{*}\\})\leq 2n/3-r^{*}$. Also since
$v_{i}(r^{*})<2/3+x$,
$v_{i}(\\{r^{*}+1,\ldots,2n/3+r^{*}\\})\leq\frac{2n}{3}(\frac{2}{3}+x)$. In
total, we get

$\displaystyle\sum_{j>r^{*}}v_{i}(\hat{B}_{j})$
$\displaystyle=\sum_{j>r^{*}}v_{i}(B_{j})$
$\displaystyle=v_{i}(\\{r^{*}+1,\ldots,2n/3+r^{*}\\})+v_{i}(\\{2n/3+r^{*}+1,\ldots,2n-r^{*}\\})$
$\displaystyle<\frac{2n}{3}(\frac{2}{3}+x)+\frac{2n}{3}-r^{*}$
$\displaystyle=\frac{10n}{9}-r^{*}+\frac{2nx}{3}.$

Therefore, Claim 1 holds. $\blacksquare$

We have

$\displaystyle\frac{4n}{3}$ $\displaystyle=v_{i}(M)$
$\displaystyle=\sum_{j\leq
r^{*}}v_{i}(\hat{B}_{j})+\sum_{j>r^{*}}v_{i}(\hat{B}_{j})$
$\displaystyle<r^{*}(\frac{4}{3}-x)+\frac{10n}{9}-r^{*}+\frac{2nx}{3}$
(Observation 1 and Claim 1)
$\displaystyle=r^{*}(\frac{1}{3}-x)+\frac{10n}{9}+\frac{2nx}{3}.$

Thus,

$\displaystyle\frac{2n}{9}$
$\displaystyle<r^{*}(\frac{1}{3}-x)+\frac{2n}{3}(x)$
$\displaystyle\leq\frac{2n}{3}\cdot\frac{1}{3},$ ($r^{*}\leq 2n/3$ by Lemma
11)

which is a contradiction. Hence, $v_{i}(2n-r^{*}+1)>1/3$. ∎

Recall that $\ell^{*}$ be the smallest such that $v_{i}(B_{\ell^{*}+1})<1$,
i.e., $B_{\ell^{*}+1}$ is the leftmost bag in Figure 2 with value less than
$1$ to agent $i$. Let $\ell$ be largest such that $v_{i}(B_{\ell})<1$ and
$v_{i}(2n-\ell+1)\leq 1/3$. Since $v_{i}(B_{\ell^{*}+1})<1$ and
$v_{i}(2n-\ell^{*})<1/3$, such an index exists and $\ell\geq\ell^{*}+1$. Also,
let $r$ be smallest such that $v_{i}(B_{r+1})<1$ and $v_{i}(2n-r)\geq 1/3$.
Again, since $v_{i}(B_{r^{*}})<1$ and $v_{i}(2n-r^{*}+1)>1/3$, such an index
exists. We set $x:=1/3-v_{i}(2n-\ell+1)$ and $y:=v_{i}(2n-r)-1/3$. See Figure
6.

######  Observation 8.

$x<1/3$.

###### Proof.

Towards a contradiction, assume $x=1/3$. Therefore, $v_{i}(2n-\ell+1)=0$. Let
$k<2n-\ell+1$ be the number of goods with a value larger than $0$ to agent
$i$. Consider $(P^{i}_{1}\cap[k],\ldots,P^{i}_{4n/3}\cap[k])$. There are at
least $\ell$ many indices $j$ such that, $|P^{i}_{j}\cap[k]|=1$. Since
$\mathcal{I}$ is $4n/3$-normalized, $v_{i}(1)=\ldots=v_{i}(\ell)=1$ which is a
contradiction with $v_{i}(B_{\ell^{*}+1})<1$. ∎

######  Observation 9.

$y<1/6$.

###### Proof.

We have $1/3+y=v_{i}(2n-r)\leq v_{i}(B_{r})/2<1/2$. Thus, $y<1/6$. ∎

$v_{i}(\hat{B}_{j})\leq 4/3-x$by Corollary
2$v_{i}(\hat{B}_{j})\leq\max(4/3-x,4/3-2y)$by Corollary 3$1\leq
v_{i}(\hat{B}_{j})<1+x+y$by Observation
10$\scriptstyle{2n}$$\scriptstyle{1}$$\scriptstyle{B_{1}}$$\scriptstyle{2n-\ell+1}$$\scriptstyle{\ell}$$\scriptstyle{B_{\ell}}$$\scriptstyle{2n-r}$$\scriptstyle{r+1}$$\scriptstyle{B_{r+1}}$$\scriptstyle{n+1}$$\scriptstyle{n}$$\scriptstyle{B_{n}}$

Figure 6: $v_{i}(2n-\ell+1)=1/3-x$ and $v_{i}(2n-r)=1/3+y$.

######  Corollary 2 (of Observation 1).

For all $j\leq\ell$, $v_{i}(\hat{B}_{j})\leq 4/3-x$.

######  Corollary 3 (of Observation 2).

For all $j>r$, $v_{i}(\hat{B}_{j})\leq\max(4/3-x,4/3-2y)$.

######  Observation 10.

For all $\ell<j\leq r$, $1\leq v_{i}(\hat{B}_{j})<1+x+y$.

###### Proof.

Note that by definition of $\ell$ and $r$, for all $\ell<j\leq r$,
$v_{i}(B_{j})\geq 1$. Therefore, $\hat{B}_{j}=B_{j}$. Also,

$\displaystyle v_{i}(B_{j})$ $\displaystyle=v_{i}(j)+v_{i}(2n-j+1)$
$\displaystyle\leq v_{i}(\ell)+v_{i}(2n-r)$ ($\ell<j$ and $2n-r<2n-j+1$)
$\displaystyle<(\frac{2}{3}+x)+(\frac{1}{3}+y)$ ($v_{i}(B_{\ell})<1$ and
$v_{i}(B_{r+1})<1$) $\displaystyle=1+x+y.$

∎

######  Lemma 13.

$r-\ell>2n/3$.

###### Proof.

If $x+y\leq 1/3$, then by Corollaries 2 and 3 and Observation 10, for all
$t\in[n]$ we have $v_{i}(\hat{B}_{t})\leq 4/3$ and for at least one bag this
value is less than $1$ by Observation 3. Therefore, $v_{i}(M)<4n/3$, which is
a contradiction. Thus, $x+y>1/3$. We have

$\displaystyle\frac{4n}{3}$ $\displaystyle=v_{i}(M)$
$\displaystyle=\sum_{j\leq\ell}v_{i}(\hat{B}_{j})+\sum_{\ell<j\leq
r}v_{i}(\hat{B}_{j})+\sum_{j>r}v_{i}(\hat{B}_{j})$
$\displaystyle\leq\ell(\frac{4}{3}-x)+(r-\ell)(1+x+y)+(n-r)\max(\frac{4}{3}-x,\frac{4}{3}-2y)$
$\displaystyle\leq(r-\ell)(1+x+y)+(n-r+\ell)\max(\frac{4}{3}-x,\frac{4}{3}-2y)$
(Corollaries 2 and 3 and Observation 10)
$\displaystyle=\frac{4n}{3}+(r-\ell)(x+y-\frac{1}{3})-(n-r+\ell)\min(x,2y).$

Therefore, $(r-\ell)(x+y-1/3)\geq(n-r+\ell)\min(x,2y)$. By Observation 8,
$x<1/3$ and thus, we have $x+y-1/3<y$. Also, since $y<1/6$ (by Observation 9),
we have $x+y-1/3<x-1/6<x/2$. Thus, $x+y-1/3<\min(x,2y)/2$. Hence,
$r-\ell>2(n-r+\ell)$ and therefore, $r-\ell>2n/3$. ∎

Let $r-\ell=2n/3+s$. Recall that $P^{i}=(P^{i}_{1},\ldots,P^{i}_{4n/3})$ is an
$(4n/3)$-MMS partition of $M$ for agent $i$. Since $i$ is fixed, we use
$P=(P_{1},\ldots,P_{4n/3})$ instead for ease of notation. For all
$j\in[4n/3]$, let $g_{j}$ be good with the smallest index (and hence the
largest value) in $P_{j}$. Without loss of generality, assume
$g_{1}<g_{2}<\ldots<g_{4n/3}$. Observe that
$\\{1,\dots,r\\}\subseteq\cup_{k\in[r]}P_{k}$. Let $S^{\prime}$ be the set of
goods in $\\{r+1,\ldots,2n-\ell\\}$ that appear in the first $r$ bags in $P$.
Formally, $S^{\prime}=\\{g\in\\{r+1,\ldots,2n-\ell\\}\mid
g\in\cup_{j\in[r]}P_{j}\\}$. Let $s^{\prime}:=\min(|S^{\prime}|,s)$.

$\scriptstyle{2n}$$\scriptstyle{1}$$\scriptstyle{B_{1}}$$\scriptstyle{2n-\ell}$$\scriptstyle{\ell+1}$$\scriptstyle{B_{\ell+1}}$$\scriptstyle{2n-\ell-3s}$$\scriptstyle{+2s^{\prime}+1}$$\scriptstyle{\ell+3s-2s^{\prime}}$$\scriptstyle{B_{\ell+3s-2s^{\prime}}}$$\scriptstyle{2n-r+s^{\prime}}$$\scriptstyle{r-s^{\prime}+1}$$\scriptstyle{B_{r-s^{\prime}+1}}$$\scriptstyle{2n-r+1}$$\scriptstyle{r}$$\scriptstyle{B_{r}}$$\scriptstyle{n+1}$$\scriptstyle{n}$$\scriptstyle{B_{n}}$

Figure 7: The goods considered in Lemma 14 are marked with blue.

######  Lemma 14.

$v_{i}(\\{r-s^{\prime}+1,\ldots,r\\}\cup\\{2n-\ell-3s+2s^{\prime}+1,\ldots,2n-\ell\\})\leq
s$.

The goods considered in Lemma 14 are marked with blue in Figure 7. Before
proving Lemma 14, let us assume it holds and reach a contradiction. Since
$v_{i}(\ell)<1-v_{i}(2n-\ell+1)=2/3+x$, we have

$\displaystyle v_{i}(\\{\ell+1,\ldots,r-s^{\prime}\\})$
$\displaystyle<(\frac{2n}{3}+s-s^{\prime})(\frac{2}{3}+x).$ (5)

Also, since $v_{i}(2n-r+1)=1/3+y$,

$\displaystyle v_{i}(\\{2n-r+1,\ldots,2n-\ell-3s+2s^{\prime}\\})$
$\displaystyle\leq(\frac{2n}{3}-2s+2s^{\prime})(\frac{1}{3}+y).$ (6)

Therefore,

$\displaystyle\sum_{\ell<j\leq r}v_{i}(\hat{B}_{j})$
$\displaystyle=\sum_{\ell<j\leq r}v_{i}(B_{j})$
$\displaystyle=v_{i}(\\{\ell+1,\ldots,r\\}\cup\\{2n-r+1,\ldots,2n-\ell\\})$
$\displaystyle=v_{i}(\\{\ell+1,\ldots,r-s^{\prime}\\})$
$\displaystyle\indent+v_{i}(\\{r-s^{\prime}+1,\ldots,r\\}\cup\\{2n-\ell-3s+2s^{\prime}+1,\ldots,2n-\ell\\})$
$\displaystyle\indent+v_{i}(\\{2n-r+1,\ldots,2n-\ell-3s+2s^{\prime}\\})$
$\displaystyle<(\frac{2n}{3}+s-s^{\prime})(\frac{2}{3}+x)+s+(\frac{2n}{3}-2s+2s^{\prime})(\frac{1}{3}+y)$
(Inequalities (5) and (6) and Lemma 14)
$\displaystyle=\frac{2n}{3}(1+x+y)+(s-s^{\prime})(x-2y)+s.$

Thus,

$\displaystyle\frac{4n}{3}$ $\displaystyle=v_{i}(M)$
$\displaystyle=\sum_{j\leq\ell}v_{i}(\hat{B}_{j})+\sum_{\ell<j\leq
r}v_{i}(\hat{B}_{j})+\sum_{j>r}v_{i}(\hat{B}_{j})$
$\displaystyle<(\ell+n-r)\max(\frac{4}{3}-x,\frac{4}{3}-2y)+\frac{2n}{3}(1+x+y)+(s-s^{\prime})(x-2y)+s$
(Corollaries 2 and 3)
$\displaystyle=(\frac{n}{3}-s)\max(\frac{4}{3}-x,\frac{4}{3}-2y)+\frac{2n}{3}(1+x+y)+(s-s^{\prime})(x-2y)+s.$

If $x\leq 2y$, then by replacing $\max(4/3-x,4/3-2y)$ with $4/3-x$ in the
above inequality, we get

$\displaystyle\frac{4n}{3}$
$\displaystyle<(\frac{n}{3}-s)(\frac{4}{3}-x)+\frac{2n}{3}(1+x+y)+(s-s^{\prime})(x-2y)+s$
$\displaystyle\leq\frac{n}{3}(\frac{4}{3}-x)+\frac{2n}{3}(1+x+y)+(s-s^{\prime})(x-2y)$
($4/3-x\geq 1$) $\displaystyle\leq\frac{n}{3}(\frac{10}{3}+x+2y)$
($(s-s^{\prime})(x-2y)\leq 0$) $\displaystyle<\frac{4n}{3},$ ($x\leq 1/3$ and
$y<1/6$)

which is a contradiction. If $2y<x$, by replacing $\max(4/3-x,4/3-2y)$ with
$4/3-2y$, we get

$\displaystyle\frac{4n}{3}$
$\displaystyle<(\frac{n}{3}-s)(\frac{4}{3}-2y)+\frac{2n}{3}(1+x+y)+(s-s^{\prime})(x-2y)+s$
$\displaystyle=\frac{n}{3}(\frac{10}{3}+2x)-s(\frac{1}{3}-x)-s^{\prime}(x-2y)$
$\displaystyle\leq\frac{n}{3}(\frac{10}{3}+2x)$ ($x\leq 1/3$ and $x>2y$)
$\displaystyle\leq\frac{4n}{3},$ ($x\leq 1/3$)

which is again a contradiction. Therefore, it is not possible that
$v_{i}(2n-\ell^{*})<1/3$. Thus, Theorem 4 follows. See 4

It only remains to prove Lemma 14. The main idea is as follows. Recall that
$s^{\prime}=\min(|S^{\prime}|,s)$. We consider two cases for $s^{\prime}$. If
$s^{\prime}=s$, then in order to prove Lemma 14, we must prove

$v_{i}(\\{r-s^{\prime}+1,\ldots,r\\}\cup\\{2n-\ell-s^{\prime}+1,\ldots,2n-\ell\\})\leq
s^{\prime},$

which is what we do in Claim 3. In case $s^{\prime}=|S^{\prime}|$, we prove

$v_{i}(\\{r-s^{\prime}+1,\ldots,r\\})+v_{i}(S^{\prime})\leq s^{\prime}$

in Claim 4 and

$v_{i}(\\{2n-\ell-3s+2s^{\prime}+1,\ldots,2n-\ell\\})-v_{i}(S^{\prime})\leq
s-s^{\prime}$

in Claim 5. Adding the two sides of the inequalities implies Lemma 14. We
prove this lemma in Section 3.4.1.

####  3.4.1 Proof of Lemma 14

See 14 Note that $\\{1,\ldots,r\\}\cup S^{\prime}\subseteq P_{1}\cup\ldots\cup
P_{r}$. For $j\in[r]$, let $Q_{j}=P_{j}\cap(\\{1,\ldots,r\\}\cup S^{\prime})$.
We begin with proving the following claim.

######  Claim 2.

There are $s^{\prime}$ many sets like $Q_{j_{1}},\ldots,Q_{j_{s^{\prime}}}$
such that $|\cup_{k\in[s^{\prime}]}Q_{j_{k}}|\geq 2s^{\prime}$ and
$|\cup_{k\in[s^{\prime}]}Q_{j_{k}}\cap\\{1,\ldots,r\\}|\geq s^{\prime}$.

###### Proof.

If $s^{\prime}=0$, the claim trivially holds. Thus, assume $s^{\prime}\geq 1$.
By induction, we prove that for any $t\leq s^{\prime}$, there are $t$ many
sets like $Q_{j_{1}},\ldots,Q_{j_{t}}$ such that
$|\cup_{k\in[t]}Q_{j_{k}}|\geq 2t$ and
$|\cup_{k\in[t]}Q_{j_{k}}\cap\\{1,\ldots,r\\}|\geq t$.

##### Induction basis: $t=1$.

If there exists $Q_{k}$ such that $|Q_{k}\cap\\{1,\ldots,r\\}|\geq 2$, let
$j_{1}=k$. Otherwise, for all $k\in[r]$, we have
$|Q_{k}\cap\\{1,\ldots,r\\}|=1$. Since $s^{\prime}\geq 1$, there must be an
index $k$ such that $|Q_{k}\cap S^{\prime}|\geq 1$. Let $j_{1}=k$.

##### Induction assumption:

There are $t$ many sets like $Q_{j_{1}},\ldots,Q_{j_{t}}$ such that
$|\cup_{k\in[t]}Q_{j_{k}}|\geq 2t$ and
$|\cup_{k\in[t]}Q_{j_{k}}\cap\\{1,\ldots,r\\}|\geq t$.

Now for $t+1\leq s^{\prime}$, we prove that there are $t+1$ many sets like
$Q_{j_{1}},\ldots,Q_{j_{t+1}}$ such that $|\cup_{k\in[t+1]}Q_{j_{k}}|\geq
2t+2$ and $|\cup_{k\in[t+1]}Q_{j_{k}}\cap\\{1,\ldots,r\\}|\geq t+1$.

##### Case 1: $|\cup_{k\in[t]}Q_{j_{k}}|\geq 2t+2$:

If $|\cup_{k\in[t]}Q_{j_{k}}\cap\\{1,\ldots,r\\}|\geq t+1$, set $j_{t+1}=k$
for an arbitrary $k\in[r]\setminus\\{j_{1},\ldots,j_{t}\\}$. Otherwise, set
$j_{t+1}=k$ for an index $k\in[r]\setminus\\{j_{1},\ldots,j_{t}\\}$ such that
$|Q_{k}\cap\\{1,\dots,r\\}|\geq 1$.

##### Case 2: $|\cup_{k\in[t]}Q_{j_{k}}|=2t+1$:

If there exists $k\in[r]\setminus\\{j_{1},\ldots,j_{t}\\}$, such that
$|Q_{k}\cap[r]|\geq 1$, set $j_{t+1}=k$. Otherwise, set $j_{t+1}=k$ for any
$k\in[r]\setminus\\{j_{1},\ldots,j_{t}\\}$ such that $|Q_{k}|\geq 1$. Since
$|\cup_{j\in[r]}Q_{j}|\geq r+s^{\prime}>2t+1$, such $k$ exists.

##### Case 3. $|\cup_{k\in[t]}Q_{j_{k}}|=2t$ and
$|\cup_{k\in[t]}Q_{j_{k}}\cap\\{1,\ldots,r\\}|\geq t+1$:

$|\cup_{k\in[r]\setminus\\{j_{1},\ldots,j_{t}\\}}Q_{j_{k}}|\geq
r+s^{\prime}-2t>r-t$. Therefore, by pigeonhole principle, there exists an
index $k\in[r]\setminus\\{j_{1},\ldots,j_{t}\\}$ such that $|Q_{k}|\geq 2$.
Set $j_{t+1}=k$.

##### Case 4. $|\cup_{k\in[t]}Q_{j_{k}}|=2t$ and
$|\cup_{k\in[t]}Q_{j_{k}}\cap\\{1,\ldots,r\\}|=t$:

If there exists $k\in[r]\setminus\\{j_{1},\ldots,j_{t}\\}$, such that
$|Q_{k}\cap[r]|\geq 2$, set $j_{t+1}=k$. Otherwise, for all
$k\in[r]\setminus\\{j_{1},\ldots,j_{t}\\}$, $|Q_{k}\cap[r]|=1$ since
$|\cup_{k\in[t]}Q_{j_{k}}\cap\\{1,\ldots,r\\}|=t$ and
$|\cup_{k\in[r]}Q_{j_{k}}\cap\\{1,\ldots,r\\}|=r$. Set $j_{t+1}=k$ for any
$k\in[r]\setminus\\{j_{1},\ldots,j_{t}\\}$, such that $|Q_{k}\cap
S^{\prime}|\geq 1$. Since $|\cup_{j\in[r]}Q_{j}\cap S^{\prime}|\geq
s^{\prime}>t$, such $k$ exists. ∎ Now we prove Claim 3.

######  Claim 3.

$v_{i}(\\{r-s^{\prime}+1,\ldots,r\\}\cup\\{2n-\ell-s^{\prime}+1,\ldots,2n-\ell\\})\leq
s^{\prime}$.

###### Proof.

Let $Q^{1}$ be the set of $s^{\prime}$ most valuable goods in
$\cup_{k\in[s^{\prime}]}Q_{j_{k}}$ and let $Q^{2}$ be the set of $s^{\prime}$
least valuable goods in $\cup_{k\in[s^{\prime}]}Q_{j_{k}}$. Since
$|\cup_{k\in[s^{\prime}]}Q_{j_{k}}|\geq 2s^{\prime}$, $Q^{1}\cap
Q^{2}=\emptyset$. Also,
$|\cup_{k\in[s^{\prime}]}Q_{j_{k}}\cap\\{1,\ldots,r\\}|\geq s^{\prime}$. Thus,
$v_{i}(Q^{1})\geq v_{i}(\\{r-s^{\prime}+1,\ldots,r\\})$. Moreover,
$v_{i}(Q^{2})\geq v_{i}(\\{2n-\ell-s^{\prime}+1,\ldots,2n-\ell\\})$. Hence,

$\displaystyle s^{\prime}$
$\displaystyle=\sum_{k\in[s^{\prime}]}v_{i}(P_{j_{k}})$
$\displaystyle\geq\sum_{k\in[s^{\prime}]}v_{i}(Q_{j_{k}})$ $\displaystyle\geq
v_{i}(\\{r-s^{\prime}+1,\ldots,r\\}\cup\\{2n-\ell-s^{\prime}+1,\ldots,2n-\ell\\}).$

∎

Note that in case $s^{\prime}=s$, Claim 3 implies Lemma 14. Therefore, from
now on, we assume $s^{\prime}=|S^{\prime}|<s$.

######  Claim 4.

$v_{i}(\\{r-s^{\prime}+1,\ldots,r\\})+v_{i}(S^{\prime})\leq s^{\prime}$.

###### Proof.

The proof is similar to the proof of Claim 3. Let $Q^{1}$ be the set of
$s^{\prime}$ most valuable goods in $\cup_{k\in[s^{\prime}]}Q_{j_{k}}$ and let
$Q^{2}$ be the set of $s^{\prime}$ least valuable goods in
$\cup_{k\in[s^{\prime}]}Q_{j_{k}}$. Since
$|\cup_{k\in[s^{\prime}]}Q_{j_{k}}|\geq 2s^{\prime}$, $Q^{1}\cap
Q^{2}=\emptyset$. Also,
$|\cup_{k\in[s^{\prime}]}Q_{j_{k}}\cap\\{1,\ldots,r\\}|\geq s^{\prime}$. Thus,
$v_{i}(Q^{1})\geq v_{i}(\\{r-s^{\prime}+1,\ldots,r\\})$. Moreover,
$v_{i}(Q^{2})\geq v_{i}(S^{\prime})$ since $s^{\prime}=|S^{\prime}|$. Hence,

$\displaystyle s^{\prime}$
$\displaystyle=\sum_{k\in[s^{\prime}]}v_{i}(P_{j_{k}})$
$\displaystyle\geq\sum_{k\in[s^{\prime}]}v_{i}(Q_{j_{k}})$ $\displaystyle\geq
v_{i}(\\{r-s^{\prime}+1,\ldots,r\\}\cup S^{\prime})$
$\displaystyle=v_{i}(\\{r-s^{\prime}+1,\ldots,r\\})+v_{i}(S^{\prime}).$

∎

######  Claim 5.

$v_{i}(\\{2n-\ell-3s+2s^{\prime}+1,\ldots,2n-\ell\\})-v_{i}(S^{\prime})\leq
s-s^{\prime}.$

###### Proof.

Note that by definition of $S^{\prime}$, the $2n-\ell-
r-s^{\prime}=8n/3-2r+s-s^{\prime}$ goods in $\\{r+1,\ldots,2n-\ell\\}\setminus
S^{\prime}$ are in $P_{r+1}\cup\ldots\cup P_{4n/3}$. Now for $j\in[4n/3-r]$,
let $R_{j}=P_{j+r}\cap\\{r+1,\ldots,2n-\ell\\}\setminus S^{\prime}$. Assume
$|R_{j_{1}}|\geq\ldots\geq|R_{j_{4n/3-r}}|$. We prove

$\displaystyle\sum_{k\leq s-s^{\prime}}|R_{j_{k}}|\geq 3(s-s^{\prime}).$ (7)

If $|R_{j_{s-s^{\prime}+1}}|\geq 3$, Inequality (7) holds. Otherwise, we have

$\displaystyle\frac{8n}{3}-2r+s-s^{\prime}$
$\displaystyle=\sum_{k\in[4n/3-r]}|R_{j_{k}}|$ $\displaystyle=\sum_{k\leq
s-s^{\prime}}|R_{j_{k}}|+\sum_{s-s^{\prime}<k\leq 4n/3-r}|R_{j_{k}}|$
$\displaystyle\leq\sum_{k\leq
s-s^{\prime}}|R_{j_{k}}|+2(\frac{4n}{3}-r-s+s^{\prime}).$ ($|R_{j_{k}}|\leq 2$
for $k>s-s^{\prime}$)

Thus, $\sum_{k\in[s-s^{\prime}]}|R_{j_{k}}|\geq 3(s-s^{\prime})$. We have

$\displaystyle s-s^{\prime}$
$\displaystyle=\sum_{k\in[s-s^{\prime}]}v_{i}(P_{j_{k}+r})$
$\displaystyle\geq\sum_{k\in[s-s^{\prime}]}v_{i}(R_{j_{k}})$
$\displaystyle\geq
v_{i}(\\{2n-\ell-3s+2s^{\prime}+1,\ldots,2n-\ell\\})-v_{i}(S^{\prime}).$
($\lvert\cup_{k\in[s-s^{\prime}]}R_{j_{k}}\rvert\geq 3(s-s^{\prime})$ and
$\lvert S^{\prime}\rvert=s^{\prime}$)

∎

Claims 4 and 5 imply Lemma 14.

##### Recap:

To show that a $1$-out-of-$(4n/3)$ MMS allocation exists, it suffices to prove
that we never run out of goods for bag-filling in Algorithm 1. Towards
contradiction, we assumed that the algorithm stops before agent $i$ receives a
bundle. By Observation 3, a bag with a value less than $1$ for agent $i$
exists. Let $\ell^{*}$ be the smallest such that $v_{i}(B_{\ell^{*}+1})<1$. In
Section 3.4, we reached a contradiction assuming $v_{i}(2n-\ell^{*})<1/3$ and
proved Theorem 4. In Section 3.3, we reached a contradiction assuming
$v_{i}(2n-\ell^{*})\geq 1/3$ and proved Theorem 5. Therefore, no such agent
$i$ exists, and all agents receive a bag by the end of Algorithm 1. Theorem 3
follows.

###  3.5 Tight Example

We now show that Algorithm 1’s guarantees are almost tight, i.e., it cannot
give us better than 1-out-of-$\lfloor(4n+1)/3\rfloor$ MMS. Note that $\lceil
4n/3\rceil=\lfloor(4n+2)/3\rfloor$ for all $n\in\mathbb{N}$.

Specifically, we show a fair division instance where Algorithm 1’s output is
not 1-out-of-$\lfloor(4n-2)/3\rfloor$ MMS, even when agents have identical
valuations. This instance is similar to the tight example in [AGST23], where
they show that a natural class of algorithms (containing Algorithm 1) cannot
guarantee a better multiplicative approximation than
$(\frac{3}{4}+\frac{3}{8n-4})$-MMS.

######  Example 1.

Consider a fair division instance with $n$ agents, where $n\geq 2$. Let
$d:=\lfloor(4n-2)/3\rfloor=n+\lfloor(n-2)/3\rfloor$. There are
$m:=2n+1+3(d-n)\leq 3n-1$ goods. All agents have the same valuation function
$u$, where

$u(j):=\begin{cases}\displaystyle\frac{2}{3}-\frac{\lceil
j/2\rceil}{3n}&\textrm{ if }1\leq j\leq 2n\\\ 1/3&\textrm{ if }2n<j\leq
m\end{cases}.$

Figure 8 shows that when we run Algorithm 1 on Example 1 with $n=5$, it does
not output a 1-out-of-$d$ MMS allocation. We formally prove this for all $n$:
in Lemma 15, we show that Example 1 is ordered and normalized, and in Lemma
16, we show that Algorithm 1’s output on Example 1 gives someone a bundle of
value less than 1. This proves that Algorithm 1 does not output a 1-out-of-$d$
MMS allocation on Example 1.

$\nicefrac{{9}}{{15}}$$\nicefrac{{9}}{{15}}$$\nicefrac{{8}}{{15}}$$\nicefrac{{8}}{{15}}$$\nicefrac{{7}}{{15}}$$\nicefrac{{7}}{{15}}$$\nicefrac{{6}}{{15}}$$\nicefrac{{6}}{{15}}$$\nicefrac{{5}}{{15}}$$\nicefrac{{5}}{{15}}$$\nicefrac{{5}}{{15}}$$\nicefrac{{5}}{{15}}$$\nicefrac{{5}}{{15}}$$\nicefrac{{5}}{{15}}$$1$$2$$3$$4$$5$
(a) Algorithm 1’s output.

$\nicefrac{{9}}{{15}}$$\nicefrac{{9}}{{15}}$$\nicefrac{{8}}{{15}}$$\nicefrac{{8}}{{15}}$$\nicefrac{{7}}{{15}}$$\nicefrac{{7}}{{15}}$$\nicefrac{{6}}{{15}}$$\nicefrac{{6}}{{15}}$$\nicefrac{{5}}{{15}}$$\nicefrac{{5}}{{15}}$$\nicefrac{{5}}{{15}}$$\nicefrac{{5}}{{15}}$$\nicefrac{{5}}{{15}}$$\nicefrac{{5}}{{15}}$$1$$2$$3$$4$$5$$6$
(b) 1-out-of-$d$ MMS partition.

Figure 8: For Example 1 with $n=5$ (and $d=\lfloor(4n-2)/3\rfloor=6$),
Algorithm 1 outputs an allocation containing a bundle of value $14/15$, but
the 1-out-of-$d$ MMS is 1. (Each cell represents a good, and each column
represents a bundle.)

######  Lemma 15.

Example 1 is ordered and $d$-normalized.

###### Proof.

$u$ is ordered since $u(2n)=u(2n+1)=1/3$.

Define $M:=(M_{1},\ldots,M_{d})$ as

$M_{i}:=\begin{cases}\\{i,2n-1-i\\}&\textrm{ if }1\leq i\leq n-1\\\
\\{i+n-1,2d+n-i,2d-n+i+1\\}&\textrm{ if }n\leq i\leq d\end{cases}.$

To show that $u$ is normalized, we show that $u(M_{i})=1$ for all $i\in[d]$.
For $i\in[n-1]$, we have

$\displaystyle u(M_{i})$
$\displaystyle=u(i)+u(2n-1-i)=\frac{4}{3}-\frac{\lceil
i/2\rceil+\lceil(2n-1-i)/2\rceil}{3n}$ $\displaystyle=1-\frac{\lceil
i/2\rceil+\lceil-(i+1)/2\rceil}{3n}=1.$

For $i\in[d]\setminus[n-1]$ and $g\in M_{i}$, we have $g\geq 2n-1$. Since
$u(j)=1/3$ for all $j\geq 2n-1$, we get that $u(M_{i})=1$ for
$i\in[d]\setminus[n-1]$. ∎

######  Lemma 16.

Let $A:=(A_{1},\ldots,A_{n})$ be Algorithm 1’s output on Example 1. Then
$u(A_{n})=1-1/(3n)$.

###### Proof.

For $i\in[n]$, let $B_{i}:=\\{i,2n+1-i\\}$ be the initial bag. Then

$\displaystyle u(B_{i})$
$\displaystyle=u(i)+u(2n+1-i)=\frac{4}{3}-\frac{\lceil
i/2\rceil+\lceil(2n+1-i)/2\rceil}{3n}$
$\displaystyle=\frac{4}{3}-\frac{(n+1)+\lceil
i/2\rceil+\lceil-(i+1)/2\rceil}{3n}=1-\frac{1}{3n}.$

Since $m-2n\leq n-1$ goods are left after bag initialization, and each good
has value $1/3$, the first $m-2n$ bags get 1 good each during bag filling, and
the remaining bags do not get any goods. ∎

##  4 MMS with Agent Priority Ranking

We give an algorithm for approximate MMS allocations in the priority ranking
setting. We assume without loss of generality that the input is $n$-normalized
and ordered (see Definitions 2 and 1).

Our algorithm first performs a few _reduction_ operations (phase 1) and then
does bag filling (phase 2). This approach is very similar to that of [GT21].
We call our algorithm $\operatorname{\mathtt{RBF}}$ (abbreviates ‘Reductions
and Bag Filling’) and formally describe it in Algorithm 2. We assume that the
input to $\operatorname{\mathtt{RBF}}$ is a pair $(\mathcal{I},T)$, where
$\mathcal{I}:=([n],[m],\mathcal{V})$ is an $n$-normalized fair division
instance such that $v_{i}(1)\geq v_{i}(2)\geq\ldots\geq v_{i}(m)$ for all
$i\in[n]$, and $T:=[\tau_{1},\ldots,\tau_{n}]$ is a sequence of thresholds
such that $1\geq\tau_{1}\geq\ldots\geq\tau_{n}>0$. We say that an agent $i$
_likes_ a set $S$ of goods if $v_{i}(S)\geq\tau_{i}$. We want to show that for
a reasonable choice of $T$, $\operatorname{\mathtt{RBF}}$ gives each agent a
bundle that they like.

For a set $S\subseteq\mathbb{Z}_{\geq 1}$ and an index $j\in[|S|]$, let
$\operatorname{\\#}(S,j)$ be the $j^{\mathrm{th}}$ smallest number in $S$
(called the $j^{\mathrm{th}}$ order statistic of $S$). For a finite set
$J\subset\mathbb{Z}_{\geq 1}$, let
$\operatorname{\\#}(S,J):=\\{\operatorname{\\#}(S,j):j\in J\textrm{ and
}j\leq|S|\\}$.

The first phase of the algorithm proceeds in multiple rounds. In each round,
we pick a set $S$ of goods and give it to an agent $i$. The goods $S$ and
agent $i$ are then removed from consideration in subsequent rounds. This
operation is called a _reduction_. Specifically, let $N$ and $M$ be the set of
remaining agents and goods, respectively, at the beginning of a round. Let
$S_{1}:=\operatorname{\\#}(M,1)$,
$S_{2}:=\operatorname{\\#}(M,\\{|N|,|N|+1\\})$,
$S_{3}:=\operatorname{\\#}(M,\\{2|N|-1,2|N|,2|N|+1\\})$, and
$S_{4}:=\operatorname{\\#}(M,\\{1,2|N|+1\\})$. Then we find the smallest $k$
such that some agent likes $S_{k}$, and the smallest $i$ such that $i$ likes
$S_{k}$. Then we give $S_{k}$ to agent $i$. If no such $k$ exists, then phase
1 ends.

Algorithm 2 $\operatorname{\mathtt{RBF}}(\mathcal{I},T)$:
Input: Ordered and $n$-normalized instance $\mathcal{I}=([n],[m],\mathcal{V})$
and agent thresholds $T:=[\tau_{1},\ldots,\tau_{n}]$.
Output: (Partial) allocation $A=(A_{1},\ldots,A_{n})$.

1:$N=[n]$

2:$M=[m]$

3:while $|N|>0$ and $|M|>0$ do

4: Let $S_{1}:=\operatorname{\\#}(M,1)$.

5: Let $S_{2}:=\operatorname{\\#}(M,\\{|N|,|N|+1\\})$.

6: Let $S_{3}:=\operatorname{\\#}(M,\\{2|N|-1,2|N|,2|N|+1\\})$.

7: Let $S_{4}:=\operatorname{\\#}(M,\\{1,2|N|+1\\})$.

8: Find the (lexicographically) smallest pair $(k,i)\in[4]\times N$ such that
$v_{i}(S_{k})\geq\tau_{i}$. Let $k$ and $i$ be $\mathtt{null}$ if no such pair
exists. // this event is called a type-$k$ reduction.

9: if $i$ is not $\mathtt{null}$ then

10: Give $S_{k}$ to agent $i$. Set $N=N\setminus\\{i\\}$ and $M=M\setminus
S_{k}$.

11: else

12: break

13: end if

14:end while

15:// $|M|\geq 2|N|$ now (see Lemma 19).

16:$\operatorname{\hyperref@@ii[algo:bagFill]{\operatorname{\texttt{bagFill}}}}((N,M,\mathcal{V}),T)$

Then in phase 2, we perform bag filling (Algorithm 3) on the remaining
instance. We create $|N|$ bags, where in the $i^{\mathrm{th}}$ bag, we add the
$i^{\mathrm{th}}$ and $(2n-i+1)^{\mathrm{th}}$ most valuable goods (so the
first $2|N|$ goods are in bags). Then we repeatedly do the following till all
agents receive a bag: Find the smallest $i$ such that agent $i$ likes some
bag, and give that bag to $i$. If no such $i$ exists (i.e., no agent likes any
bag), add the most valuable remaining good to an arbitrary bag.

Algorithm 3 $\operatorname{\texttt{bagFill}}(\mathcal{I},T)$
Input: Ordered instance $\mathcal{I}=([n],[m],\mathcal{V})$ with $m\geq 2n$,
and agent thresholds $T:=[\tau_{1},\ldots,\tau_{n}]$.
Output: (Partial) allocation $A=(A_{1},\ldots,A_{n})$.

1:for $i\in[n]$ do

2: $B_{i}=\\{i,2n+1-i\\}$.

3: $A_{i}=\emptyset$.

4:end for

5:$U_{G}=[m]\setminus[2n]$ // unassigned goods

6:$U_{A}=[n]$ // unsatisfied agents

7:$U_{B}=[n]$ // unassigned bags

8:while $U_{A}\neq\emptyset$ do // loop invariant: $|U_{A}|=|U_{B}|$

9: Let $i$ be the smallest in $U_{A}$ such that for some $k\in U_{B}$, we have
$v_{i}(B_{k})\geq\tau_{i}$. Let $i=\mathtt{null}$ otherwise.

10: if $i$ is not $\mathtt{null}$ then

11: // assign the $k^{\mathrm{th}}$ bag to agent $i$:

12: $A_{i}=B_{k}$

13: $U_{A}=U_{A}\setminus\\{i\\}$

14: $U_{B}=U_{B}\setminus\\{k\\}$

15: else if $U_{G}\neq\emptyset$ then

16: $g$ = most valuable good in $U_{G}$

17: $k$ = arbitrary bag in $U_{B}$

18: // assign $g$ to the $k^{\mathrm{th}}$ bag:

19: $B_{k}=B_{k}\cup\\{g\\}$.

20: $U_{G}=U_{G}\setminus\\{g\\}$

21: else

22: error: we ran out of goods.

23: Allocate the bags in $U_{B}$ to agents in $U_{A}$ arbitrarily.

24: return $(A_{1},\ldots,A_{n})$.

25: // agents $U_{A}$ are not satisfied with their bags.

26: end if

27:end while

28:return $(A_{1},\ldots,A_{n})$

Our algorithm ($\operatorname{\mathtt{RBF}}$) is the same as that of [GT21],
with a few minor differences:

  1. 1.

We assume the input to be $n$-normalized, whereas they do not.

  2. 2.

In both phases 1 and 2, we assume that when multiple agents like a bundle, we
give it to the smallest-numbered agent, whereas they break ties arbitrarily.

  3. 3.

They use the same thresholds for all agents, i.e., $\tau_{1}=\ldots=\tau_{n}$.

The idea behind reductions is to shrink the set of agents to consider: we want
to give each agent a bundle that they like, and since each agent selected for
a reduction obtains a bundle that she likes, we only need to worry about the
remaining agents. Reductions also shrink the set of goods, though, and it is
therefore necessary to argue that the set of remaining goods is enough to
satisfy the remaining agents, i.e., we are not giving away too many goods
during reductions.

[GT21] showed this using the idea of _valid reductions_ : a reduction is
called _valid_ if it preserves the MMS values of the remaining agents.
Formally, they showed that if $\tau_{j}\leq 3/4$ for all $j$, and if a
reduction involves giving $S_{k}$ to agent $i$, then for all $j\in
N\setminus\\{i\\}$, we have $\text{MMS}_{j}^{|N|-1}(M\setminus
S_{k})\geq\text{MMS}_{j}^{|N|}(M)$. Hence, if the initial MMS value of each
agent is 1 (which happens if we start with an $n$-normalized instance), then
the MMS value of each remaining agent after phase 1 is at least 1. Since
[GT21] aim to find $3/4$-MMS allocations, they assume without loss of
generality that the input instance is irreducible, i.e., no reductions are
possible. They show that irreducible instances have nice properties, which
they exploit to show that $\operatorname{\texttt{bagFill}}$ outputs a
$3/4$-MMS allocation when its input is irreducible.

Unfortunately, reductions in $\operatorname{\mathtt{RBF}}$ are not valid,
i.e., they can decrease the MMS value of the remaining agents. Specifically,
when $\tau_{j}>3/4$ for an agent $j$, then it can happen that
$\text{MMS}^{n-1}_{j}(M\setminus S_{4})<\text{MMS}^{n}_{j}(M)$. Moreover, even
for fair division instances where reductions are valid (e.g., no type-4
reductions take place), it is unclear how to exploit the validity of
reductions in our analysis. This is because reductions can change the priority
rank of agents, e.g., the $(n/2)^{\mathrm{th}}$ most important agent in the
original instance may end up becoming the least important in the reduced
instance if $n/2$ reductions take place. Hence, we need to use other
techniques.

###  4.1 Analysis of $\operatorname{\mathtt{RBF}}$

We now show that when the thresholds are not too high,
$\operatorname{\mathtt{RBF}}$ outputs an allocation where each agent $i$ gets
a bundle of value at least $\tau_{i}$.

######  Lemma 17 (follows from [GT21]).

Let $A$ be the allocation output by
$\operatorname{\mathtt{RBF}}(\mathcal{I},T)$. For all $i\in[n]$, if
$\tau_{i}=\frac{3}{4}+\frac{1}{12n}$, then $v_{i}(A_{i})\geq\tau_{i}$.

Suppose $p$ reductions happen during $\operatorname{\mathtt{RBF}}$, where the
$j^{\mathrm{th}}$ reduction is a type-$r_{j}$ reduction. Call
$R:=(r_{1},\ldots,r_{p})$ the _reduction sequence_. To analyze
$\operatorname{\mathtt{RBF}}$, we must understand the structure of $R$.

######  Lemma 18.

The reduction sequence $R$ for $\operatorname{\mathtt{RBF}}$ is captured by
the following regular expression: $(1^{*}2^{*}4^{*})(32^{*}4^{*})^{*}$.
Equivalently, if $n_{3}$ type-3 reductions happened in
$\operatorname{\mathtt{RBF}}$, then we can partition $R$ into $n_{3}+1$
contiguous sub-lists $(R_{0},\ldots,R_{n_{3}})$, such that all of the
following hold:

  1. 1.

$R_{0}$ is a sequence of zero or more 1s, followed by zero or more 2s,
followed by zero or more 4s. ($R_{0}$ can be empty.)

  2. 2.

For $i\in[n_{3}]$, the first element in $R_{i}$ is 3, followed by zero or more
2s, followed by zero or more 4s.

###### Proof.

All type-1 reductions happen together in the beginning. This is because a
different kind of reduction can only happen if a type-1 reduction is not
possible. If a type-1 reduction is not possible, then for each good $g$ and
each remaining agent $i$, $v_{i}(g)<\tau_{i}$. Hence, a type-1 reduction will
never happen in the future.

Call $R_{i}$ the $i^{\mathrm{th}}$ _phase_ of $\operatorname{\mathtt{RBF}}$.
Within each phase, all type-2 reductions happen before all type-4 reductions.
This is because a type-4 reduction happens only if a type-2 reduction is not
possible. After a type-4 reduction, the value of $S_{2}$ remains the same, so
a type-2 reduction will never occur again in the same phase. ∎

######  Lemma 19.

In $\operatorname{\mathtt{RBF}}$, after all type-1 reductions have happened,
we have $|M|\geq 2|N|$ throughout the execution of the algorithm.

###### Proof.

Let $\mathcal{I}:=([n],[m],\mathcal{V})$ be the initial fair division instance
(the input to $\operatorname{\mathtt{RBF}}$).

By Lemma 18, all type-1 reductions happen before all other reductions. Suppose
$k$ type-1 valid reductions happened. Immediately after that, $|M|=m-k$ and
$|N|=n-k$. If $|M|<2|N|$, then $m<2n-k$. For any agent $i\in[n]$, consider her
partition $P:=(P_{1},\ldots,P_{n})$ for $\mathcal{I}$. Since $m<2n-k$, at
least $k+1$ singleton bundles in $P$ exist. Since $\mathcal{I}$ is normalized,
the goods in those singleton bundles have a value of $1$ for $i$. But at least
$k+1$ type-1 reductions should have happened, which is a contradiction. Hence,
immediately after type-1 reductions, we have $|M|\geq 2|N|$.

Type-3 and type-4 reductions only happen when $|M|\geq 2|N|+1$, so they
preserve the invariant $|M|\geq 2|N|$. ∎

######  Lemma 20.

In $\operatorname{\mathtt{RBF}}$, after all reductions have happened, let
$M_{f}$ and $N_{f}$ be the set of remaining goods and remaining agents,
respectively. (By Lemma 19, $|M_{f}|\geq 2|N_{f}|$.) Then for any good $g$ in
a type-$k$ reduction bundle, we have

  1. 1.

$g>\operatorname{\\#}(M_{f},|N_{f}|)$ if $k=2$.

  2. 2.

$g>\operatorname{\\#}(M_{f},2|N_{f}|)$ if $k=3$.

###### Proof.

Suppose $p$ reductions happen during $\operatorname{\mathtt{RBF}}$. For any
$i\in[p]$, let $S_{i}$ be the $i^{\mathrm{th}}$ reduction bundle and let
$k_{i}$ be the type of the $i^{\mathrm{th}}$ reduction. Let $M_{i}$ and
$N_{i}$ be the set of remaining goods and remaining agents, respectively,
after $i$ reductions have happened. (Hence, $(N_{0},M_{0},\mathcal{V})$ is the
original instance.)

Define proposition $P(i)$ as: For any $j\in[i]$ and any $g\in S_{i}$,
$g>\operatorname{\\#}(M_{i},|N_{i}|)$ if $k=2$ and
$g>\operatorname{\\#}(M_{i},2|N_{i}|)$ if $k=3$.

We prove $P(i)$ for all $i\in\\{0\\}\cup[p]$ using induction: The base case
$i=0$ is trivial since no reductions have happened. Now for $i\in[p]$, we want
to prove $P(i-1)\implies P(i)$.

Case 1: $k_{i}=1$:
By Lemma 18, no type-2 or type-3 reductions happened among the first $i$
reductions. Hence, $P(i)$ holds trivially.

For the remaining cases, $\operatorname{\\#}(M_{i},|N_{i}|)$ and
$\operatorname{\\#}(M_{i},2|N_{i}|)$ are well-defined because of Lemma 19.

Case 2: $k_{i}=2$:
Then $S_{i}=\operatorname{\\#}(M_{i-1},\\{|N_{i-1}|,|N_{i-1}|+1\\})$,
$\operatorname{\\#}(M_{i},|N_{i}|)=\operatorname{\\#}(M_{i-1},|N_{i-1}|-1)$,
and
$\operatorname{\\#}(M_{i},2|N_{i}|)=\operatorname{\\#}(M_{i-1},2|N_{i-1}|)$.
Hence, $P(i)$ holds.

Case 3: $k_{i}=3$:
Then
$S_{i}=\operatorname{\\#}(M_{i-1},\\{2|N_{i-1}|-1,2|N_{i-1}|,2|N_{i-1}|+1\\})$,
$\operatorname{\\#}(M_{i},|N_{i}|)=\operatorname{\\#}(M_{i-1},|N_{i-1}|-1)$,
and
$\operatorname{\\#}(M_{i},2|N_{i}|)=\operatorname{\\#}(M_{i-1},2|N_{i-1}|-2)$.
Hence, $P(i)$ holds.

Case 4: $k_{i}=4$:
Then $S_{i}=\operatorname{\\#}(M_{i-1},\\{1,2|N_{i-1}|+1\\})$,
$\operatorname{\\#}(M_{i},2|N_{i}|)=\operatorname{\\#}(M_{i-1},2|N_{i-1}|-1)$,
and $\operatorname{\\#}(M_{i},|N_{i}|)=\operatorname{\\#}(M_{i-1},|N_{i-1}|)$.
Hence, $P(i)$ holds.

By mathematical induction, we get that $P(p)$ holds. ∎

######  Lemma 21 (Lemma 6 in [AGST23]).

In an ordered and normalized fair division instance, for all $i,k\in[n]$, if
$v_{i}(\\{k,2n+1-k\\})>1$, then $v_{i}(2n+1-k)\leq 1/3$ and $v_{i}(k)>2/3$.

######  Lemma 22.

Let $A$ be the allocation output by
$\operatorname{\mathtt{RBF}}(\mathcal{I},T)$. For all $i\in[n]$, if
$\tau_{i}=2n/(2n+i-1)$, then $v_{i}(A_{i})\geq\tau_{i}$.

###### Proof.

Suppose for some $i\in[n]$, we have $\tau_{i}=2n/(2n+i-1)$ and
$v_{i}(A_{i})<\tau_{i}$. We will try to upper-bound the total value agent $i$
has for all the bundles. To do this, we associate a _charge_ $c(A_{j})$ with
each bundle $A_{j}$ for $j\in[n]$ such that all of these properties hold:

  1. 1.

The total charge of all bundles equals the total value of all bundles.

  2. 2.

The charge of each bundle is less than $3\tau_{i}/2$.

  3. 3.

If a bundle has value less than $\tau_{i}$ to agent $i$, then it is charged
less than $\tau_{i}$.

The total number of reductions that happen is at most $n-1$ (otherwise, $i$
would have gotten a bundle in some reduction). In the instance after all
reductions have happened, let $M_{f}$ and $N_{f}$ be the set of remaining
goods and remaining agents, respectively. Let
$z^{\prime}:=v_{i}(\operatorname{\\#}(M_{f},|N_{f}|))$ and
$z:=v_{i}(\operatorname{\\#}(M_{f},|N_{f}|+1))$. Then $z^{\prime}+z<\tau_{i}$
and $z^{\prime}\geq z$, so $z<\tau_{i}/2$.

We now upper-bound the charge of each bundle in $A$. To do this we consider
three cases.

Case 1: type-1 and type-4 reduction bundles:
Let $S$ be a type-$k$ reduction bundle, for $k\in\\{1,4\\}$. Let
$c(S):=v_{i}(S)$. Let $M$ and $N$ be the set of remaining goods and remaining
agents immediately before the reduction. Then $|N|\geq 2$, since at most $n-1$
valid reductions happen.

  1. 1.

$k=1$: then $v_{i}(S)\leq v_{i}(1)\leq 1$, since the instance is normalized.

  2. 2.

$k=4$: then a type-3 reduction was not possible. Hence,
$v_{i}(S)=v_{i}(\operatorname{\\#}(M,\\{1,2|N|+1\\}))<\tau_{i}+\tau_{i}/3=4\tau_{i}/3$.

Case 2: type-2 and type-3 reduction bundles:
By Lemma 18, we can partition the sequence of reduction events into sub-lists
$(R_{0},R_{1},\ldots,R_{n_{3}})$. Let $S$ be a type-2 reduction bundle in
$R_{0}$. Then $S=\\{j,2n+1-j\\}$ for some $j$. If $v_{i}(S)>1$, then by Lemma
21, we get that $v_{i}(2n+1-j)\leq 1/3$. Also, $v_{i}(j)<\tau_{i}$, since no
type-1 reduction was possible. Hence, $v_{i}(S)<\tau_{i}+1/3$ if $v_{i}(S)>1$.
Since $\tau_{i}=2n/(2n+i-1)\geq 2n/(3n-1)>2/3$, we get $1<3\tau_{i}/2$ and
$\tau_{i}+1/3<3\tau_{i}/2$. Hence, $v_{i}(S)<3\tau_{i}/2$. Let
$c_{i}(S):=v_{i}(S)$.

Consider the sub-list $R_{t}$ for some $t>0$. In the instance immediately
before the first reduction in $R_{t}$, let $M^{\prime}$ and $N^{\prime}$ be
the set of remaining goods and agents, respectively. Let $S_{j}$ be the
$j^{\mathrm{th}}$ type-2 reduction bundle in $R_{t}$, and let $T$ be the
type-3 reduction bundle in $R_{t}$.

  1. 1.

By Lemma 20,
$\operatorname{\\#}(M^{\prime},2|N^{\prime}|-1)>\operatorname{\\#}(M_{f},2|N_{f}|)$.
Hence, $v_{i}(T)\leq 3z<3\tau_{i}/2$.

  2. 2.

$S_{1}=\operatorname{\\#}(M^{\prime},\\{|N^{\prime}|-1,|N^{\prime}|\\})$. By
Lemma 20,
$\operatorname{\\#}(M^{\prime},|N^{\prime}|-1)>\operatorname{\\#}(M_{f},|N_{f}|)$.
Hence, $v_{i}(S_{1})\leq 2z^{\prime}<2(\tau_{i}-z)$.

  3. 3.

For $j\geq 2$, we have
$S_{j}=\operatorname{\\#}(M^{\prime},\\{|N^{\prime}|-j,|N^{\prime}|+(j-1)\\})$.
A type-2 reduction was not possible at the beginning of $R_{t}$, so
$v_{i}(\operatorname{\\#}(M^{\prime},|N^{\prime}|+1))<\tau_{i}/2$. Hence,
$v_{i}(S_{j})<3\tau_{i}/2$. Let $c(S_{j}):=v_{i}(S_{j})$.

If no type-2 reduction happened in $R_{t}$, let $c(T):=v_{i}(T)$.

Now, suppose at least one type-2 reduction happened in $R_{t}$. Let
$\zeta:=v_{i}(T)+v_{i}(S_{1})<3z+2(\tau_{i}-z)<5\tau_{i}/2$. Define $c(T)$ and
$c(S_{1})$ as follows:

$(c(T),c(S_{1}))=\begin{cases}(\frac{3}{5}\zeta,\frac{2}{5}\zeta)&\textrm{ if
}v_{i}(T)>\frac{3}{5}\zeta\\\ (\frac{2}{5}\zeta,\frac{3}{5}\zeta)&\textrm{ if
}v_{i}(S_{1})>\frac{3}{5}\zeta\\\ (v_{i}(T),v_{i}(S_{1}))&\textrm{
otherwise}\end{cases}.$

Let $x:=\max(c(T),c(S_{1}))$ and $y:=\min(c(T),c(S_{1}))$. Then
$x\leq\frac{3}{5}\zeta<3\tau_{i}/2$. Furthermore, if $v_{i}(S_{1})<\tau_{i}$,
then $c(S_{1})<\tau_{i}$. This is because if $c(S_{1})\neq v_{i}(S_{1})$, then
$c(S_{1})=\frac{2}{5}\zeta<\tau_{i}$. Similarly, $v_{i}(T)<\tau_{i}\implies
c(T)<\tau_{i}$.

Case 3: bag filling bundles:
For a bag filling bundle, its initial value is less than
$\tau_{i}+z<3\tau_{i}/2$. If it received some goods during bag filling, then
its value to $i$ before the last good was added is less than $\tau_{i}$. Since
no type-3 reduction is possible, each good added to a bag has a value less
than $\tau_{i}/3$ to agent $i$. Hence, the bag’s value is less than
$4\tau_{i}/3$ to agent $i$. Charge a bag equal to its value.

Now, we combine all the cases. There are $n$ bundles in the allocation. Since
agent $i$ did not get a bundle of value $\geq\tau_{i}$, and she has higher
priority than $n-i$ other agents, we get that each such bundle has value less
than $\tau_{i}$ to agent $i$, and hence has charge less than $\tau_{i}$. The
remaining $i-1$ agents get a bundle of charge less than $3\tau_{i}/2$. Hence,

$n=\sum_{j=1}^{n}v_{i}(A_{j})=\sum_{j=1}^{n}c(A_{j})<(i-1)(3\tau_{i}/2)+(n-i+1)\tau_{i}=(\tau_{i}/2)(2n+i-1).$

Therefore, $\tau_{i}>2n/(2n+i-1)$. This is a contradiction. Hence, if
$\tau_{i}=2n/(2n+i-1)$, then $v_{i}(A_{i})\geq\tau_{i}$. ∎

######  Theorem 6.

Let $\mathcal{I}$ be a fair division instance and
$T:=(\tau_{1},\ldots,\tau_{n})$ where for all $i\in[n]$,

$\tau_{i}:=\max\left(\frac{2n}{2n+i-1},\frac{3}{4}+\frac{1}{12n}\right).$

Let $A$ be the allocation output by
$\operatorname{\mathtt{RBF}}(\mathcal{I},T)$. Then $A$ is a $T$-MMS
allocation, i.e., for all $i\in[n]$, we have $v_{i}(A_{i})\geq\tau_{i}$.

###### Proof.

Follows from Lemmas 22 and 17. ∎

###  4.2 Best-of-Both-Worlds Fairness

In the best-of-both-worlds setting, the aim is to output a distribution
(ideally of small support) over allocations that is both ex-ante fair and ex-
post fair. We first show what guarantees we can get for any algorithm by
assigning priority ranks randomly.

######  Lemma 23.

Let $T:=(\tau_{1},\ldots,\tau_{n})$ be a list of thresholds and let
$\mathcal{A}$ be an algorithm that outputs a $T$-MMS allocation for every fair
division instance having $n$ agents. For $k\in[n]$, let $A^{(k)}$ be the
allocation output by algorithm $\mathcal{A}$ when agent $i$ has priority rank

$\begin{cases}i+k-1&\textrm{ if }i+k-1\leq n\\\ i+k-1-n&\textrm{
otherwise}\end{cases}.$

If we sample $k$ uniformly randomly from $[n]$, then $A^{(k)}$ is ex-post
$\tau_{n}$-MMS and ex-ante $(\frac{1}{n}\sum_{i=1}^{n}\tau_{i})$-MMS.

###### Proof.

For each agent $i$, her priority rank is distributed uniformly over $[n]$. ∎

Note that in Lemma 23, if $\mathcal{A}$ is deterministic, then instead of
outputting just a random allocation, we can output the entire distribution by
finding $A^{(k)}$ for all $k\in[n]$. This is useful if the agents want to
verify that the distribution is indeed ex-ante fair.

We now show that by randomizing priority ranks as in Lemma 23 and picking
thresholds as in Theorem 6, $\operatorname{\mathtt{RBF}}$ is ex-post
$(\frac{3}{4}+\frac{1}{12n})$-MMS and ex-ante $(0.82536+\frac{1}{36n})$-MMS.

######  Lemma 24.

For all $n\geq 1$, we get

$\gamma:=\frac{1}{n}\sum_{i=1}^{n}\max\left(\frac{2n}{2n+i-1},\frac{3}{4}+\frac{1}{12n}\right)\geq
2\ln\left(\frac{4}{3}\right)+\frac{1}{4}+\frac{1}{36n}.$

###### Proof.

(Proof deferred to Section B.3). ∎

######  Theorem 7.

Let $\mathcal{I}$ be a fair division instance having $n$ agents,
$T:=(\tau_{1},\ldots,\tau_{n})$, and
$\tau_{i}:=\max\big{(}\frac{2n}{2n+i-1},\allowbreak\frac{3}{4}+\frac{1}{12n}\big{)}$
for all $i\in[n]$. Sample $k$ uniformly randomly from $[n]$, and let agent
$i$’s priority rank be $i+k-1$ if $i+k-1\leq n$ and $i+k-1-n$ otherwise. Then
the allocation output by $\operatorname{\mathtt{RBF}}(\mathcal{I},T)$ is ex-
post $(\frac{3}{4}+\frac{1}{12n})$-MMS and ex-ante $\beta$-MMS, where
$\beta:=2\ln\left(\frac{4}{3}\right)+\frac{1}{4}+\frac{1}{36n}\approx
0.82536+\frac{1}{36n}$.

###### Proof.

Follows from Theorems 6, 23 and 24. ∎

###  4.3 Upper-Bounds on Thresholds

We show that if $\operatorname{\mathtt{RBF}}(\mathcal{I},T)$’s output is
$T$-MMS for every fair division instance $\mathcal{I}$ with $n$ agents, where
$T:=(\tau_{1},\ldots,\tau_{n})$ is a list of thresholds and $\tau_{n}>0$, then
$\tau_{i}$ must be at most $3n/(3n+i-2)$ for all $i\in\\{3,\ldots,n\\}$. We
also show how this limits the best ex-ante fairness achievable by
$\operatorname{\mathtt{RBF}}(\mathcal{I},T)$.

In particular, by setting $i=n$, we get that $\tau_{n}\leq 3n/(4n-2)$, i.e.,
$\operatorname{\mathtt{RBF}}$’s output cannot be better than $3n/(4n-2)$-MMS,
which was also proved in Section 5 of [AGST23]. Hence, we generalize their
tight example to the setting with agent priority ranks.

Let $n\geq 3$. For $i\in\\{3,\ldots,n\\}$, let $\delta_{i}:=1/(3n+i-2)$,
$\alpha_{i}:=3n\delta_{i}$, and $u_{i}:\mathbb{Z}_{>0}\to\mathbb{R}_{\geq 0}$,
where

$u_{i}(j):=\begin{cases}(2n-\lceil j/2\rceil)\delta_{i}&\textrm{ if }j\leq
2n\\\ n\delta_{i}&\textrm{ if }2n<j<2n+i\\\ 0&\textrm{ if }j\geq
2n+i\end{cases}.$

######  Observation 11.

$3/4<\alpha_{n}<\ldots<\alpha_{3}<1$.

######  Lemma 25.

For $i\in\\{3,\ldots,n\\}$, $u_{i}$ satisfies all of these properties:

  1. 1.

$u_{i}$ is ordered and normalized.

  2. 2.

$\max(u_{i}(\\{1\\}),u_{i}(\\{n,n+1\\}),u_{i}(\\{2n-1,2n,2n+1\\}),u_{i}(\\{1,2n+1\\}))\leq\alpha_{i}$.

  3. 3.

For each $j\in[n]$, we have $u_{i}(\\{j,2n+1-j\\})\leq\alpha_{i}$ and
$u_{i}(\\{j,2n+1-j,2n+i-1\\})\geq 1$.

###### Proof.

$u_{i}(2n)=n\delta_{i}=u_{i}(2n+1)>0$, so $u_{i}$ is ordered.

Let $k:=n-i+1$. Let $M:=(M_{1},\ldots,M_{n})$ where

$M_{j}:=\begin{cases}\\{j,2k+1-j\\}&\textrm{ if }1\leq j\leq k\\\
\\{k+j,2n+3k+1-j,2n+j-k\\}&\textrm{ if }k+1\leq j\leq n\end{cases}.$

Then we can verify that $u_{i}(M_{j})=1$ for all $j\in[n]$.

$u_{i}(\\{1,2n+1\\})=u_{i}(\\{n,n+1\\})=(3n-1)\delta_{i}\leq\alpha_{i}$.
$u_{i}(\\{2n-1,2n,2n+1\\})=3n\delta_{i}=\alpha_{i}$.

$u_{i}(\\{j,2n+1-j\\})=(3n-1)\delta_{i}\leq\alpha_{i}$.
$u_{i}(\\{j,2n+1-j,2n+i-1\\})=(4n-1)\delta_{i}\geq 1$. ∎

For any $\varepsilon\in(0,1)$ such that $1/\varepsilon\in\mathbb{Z}_{>0}$,
define valuation function $w_{\varepsilon}:[n/\varepsilon]\to\mathbb{R}_{\geq
0}$ as $w_{\varepsilon}(j)=\varepsilon$ for all $j$. Note that
$w_{\varepsilon}$ is ordered and normalized.

######  Theorem 8.

Let $T:=(\tau_{1},\ldots,\tau_{n})$, where $\tau_{n}>0$. If
$\operatorname{\mathtt{RBF}}(\mathcal{I},T)$ outputs a $T$-MMS allocation for
every fair division instance $\mathcal{I}$ with $n$ agents, then
$\tau_{i}\leq\alpha_{i}$ for all $i\in\\{3,\ldots,n\\}$, where
$\alpha_{i}:=3n/(3n+i-2)$.

###### Proof.

Assume without loss of generality that each agent $i$ has priority rank $i$.
Suppose $\operatorname{\mathtt{RBF}}(\mathcal{I},T)$ outputs a $T$-MMS
allocation for every fair division instance $\mathcal{I}$ with $n$ agents, but
$\tau_{i}>\alpha_{i}$ for some $i\in\\{3,\ldots,n\\}$.

Pick $\varepsilon\in(0,\tau_{n}/3)$ such that
$1/\varepsilon\in\mathbb{Z}_{>0}$. Consider a fair division instance
$([n],[n/\varepsilon],v)$, where $v_{1}=\ldots=v_{i}=u_{i}$ and
$v_{i+1}=\ldots=v_{n}=w_{\varepsilon}$. By Lemma 25.2, no reduction events
take place during $\operatorname{\mathtt{RBF}}$. Hence,
$\operatorname{\mathtt{RBF}}$ simply delegates everything to
$\operatorname{\texttt{bagFill}}$.

By Lemma 25.3, all bags initially have value at most $\alpha_{i}$ for the
first $i$ agents, and value $2\varepsilon$ for the remaining agents. Since
$\alpha_{i}<\tau_{i}$ and $2\varepsilon<\tau_{n}$, no agent wants any bag
initially.

For the first $i$ agents, only goods in $[2n+i-1]$ have positive value. Since
$\operatorname{\mathtt{RBF}}$ outputs a $T$-MMS allocation, each agent in
$[i]$ receives a bag with at least one good from $[2n+i-1]\setminus[2n]$. But
this is impossible since there are only $i-1$ goods in
$[2n+i-1]\setminus[2n]$. This is a contradiction. Hence,
$\tau_{i}\leq\alpha_{i}$. ∎

Our approach in Section 4.2 to get best-of-both-worlds fairness is via Lemma
23, i.e., we first find a list $T:=(\tau_{1},\ldots,\tau_{n})$ of thresholds
such that $\operatorname{\mathtt{RBF}}(\mathcal{I},T)$ outputs a $T$-MMS
allocation for every fair division instance $\mathcal{I}$ with $n$ agents, and
then we run $\operatorname{\mathtt{RBF}}$ with random priority ranks. Then we
get ex-post $\tau_{n}$-MMS and ex-ante
$\frac{1}{n}(\sum_{i=1}^{n}\tau_{i})$-MMS. We now show the limitations of this
approach.

By Theorem 8, if we want any ex-post MMS guarantee for the output of Algorithm
2, the best ex-ante MMS guarantee we can get is

$\frac{1}{n}\left(2+\sum_{i=3}^{n}\frac{3n}{3n+i-2}\right).$

We now show an upper-bound on this quantity.

######  Lemma 26.

For all $n\geq 2$,

$\frac{1}{n}\left(2+\sum_{i=3}^{n}\frac{3n}{3n+i-2}\right)\leq
3\ln\left(\frac{4}{3}\right)+\frac{1}{2n}\approx 0.86305+\frac{1}{2n}.$

###### Proof.

(Proof deferred to Section B.3). ∎

######  Theorem 9.

If we fix the number of agents to $n$, the ex-ante MMS guarantee obtainable
from $\operatorname{\mathtt{RBF}}$ by picking priority ranks randomly (as in
Lemma 23) is not better than $\beta$-MMS, where
$\beta:=3\ln(\frac{4}{3})+\frac{1}{2n}\approx 0.86305+\frac{1}{2n}$, and the
ex-post MMS guarantee is not better than $\gamma$-MMS, where
$\gamma:=3n/(4n-2)=\frac{3}{4}+\frac{3}{8n-4}$.

###### Proof.

Follows from Theorems 8, 23 and 26. ∎

## References

  * [AAGW15] Martin Aleksandrov, Haris Aziz, Serge Gaspers, and Toby Walsh.  Online fair division: Analysing a food bank problem.  In IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 2540–2546. AAAI Press, 2015.  URL: http://ijcai.org/Abstract/15/360.
  * [ABCM17] Georgios Amanatidis, Georgios Birmpas, George Christodoulou, and Evangelos Markakis.  Truthful allocation mechanisms without payments: Characterization and implications on fairness.  In Proc. 18th Conf. Economics and Computation (EC), pages 545–562, 2017.
  * [ABM16] Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis.  On truthful mechanisms for maximin share allocations.  In Subbarao Kambhampati, editor, Proc. 25th Intl. Joint Conf. Artif. Intell. (IJCAI), pages 31–37, 2016.
  * [AFSV23] Haris Aziz, Rupert Freeman, Nisarg Shah, and Rohit Vaish.  Best of both worlds: Ex ante and ex post fairness in resource allocation.  Operations Research, 2023.  doi:10.1287/opre.2022.2432.
  * [AG24] Hannaneh Akrami and Jugal Garg.  Breaking the $3/4$ barrier for approximate maximin share.  In Symposium on Discrete Algorithms (SODA), pages 74–91. ACM-SIAM, 2024.  doi:10.1137/1.9781611977912.4.
  * [AGST23] Hannaneh Akrami, Jugal Garg, Eklavya Sharma, and Setareh Taki.  Simplification and improvement of MMS approximation.  In Proc. 32nd Intl. Joint Conf. Artif. Intell. (IJCAI), 2023.
  * [AHSH19] Elad Aigner-Horev and Erel Segal-Halevi.  Envy-free matchings in bipartite graphs and their applications to fair division.  Inf. Sci., 587:164–187, 2019.
  * [ALW19] Haris Aziz, Bo Li, and Xiaowei Wu.  Strategyproof and approximately maxmin fair share allocation of chores.  In International Joint Conference on Artificial Intelligence, pages 60–66, 2019.  doi:10.24963/ijcai.2019/9.
  * [AM16] Haris Aziz and Simon Mackenzie.  A discrete and bounded envy-free cake cutting protocol for any number of agents.  In Proc. 57th Symp. Foundations of Computer Science (FOCS), pages 416–427, 2016.
  * [AMNS17] Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi.  Approximation algorithms for computing maximin share allocations.  ACM Transactions on Algorithms (TALG), 13(4):1–28, 2017.  doi:10.1145/3147173.
  * [ARSW17] Haris Aziz, Gerhard Rauchecker, Guido Schryen, and Toby Walsh.  Algorithms for max-min share fair allocation of indivisible chores.  In Proc. 31st Conf. Artif. Intell. (AAAI), page 335–341, 2017.
  * [ASMS23] Hannaneh Akrami, Masoud Seddighin, Kurt Mehlhorn, and Golnoosh Shahkarami.  Randomized and deterministic maximin-share approximations for fractionally subadditive valuations.  CoRR, abs/2308.14545, 2023.
  * [BB18] Arpita Biswas and Siddharth Barman.  Fair division under cardinality constraints.  In Proc. 27th Intl. Joint Conf. Artif. Intell. (IJCAI), pages 91–97, 2018.
  * [BBMN18] Siddharth Barman, Arpita Biswas, Sanath Kumar Krishna Murthy, and Yadati Narahari.  Groupwise maximin fair allocation of indivisible goods.  In Proc. 32nd Conf. Artif. Intell. (AAAI), pages 917–924, 2018.
  * [BEF21] Moshe Babaioff, Tomer Ezra, and Uriel Feige.  Fair-share allocations for agents with arbitrary entitlements.  In Proc. 22nd Conf. Economics and Computation (EC), pages 127–127, 2021.
  * [BEF22] Moshe Babaioff, Tomer Ezra, and Uriel Feige.  On best-of-both-worlds fair-share allocations.  In International Conference on Web and Internet Economics, pages 237–255. Springer, 2022.
  * [BF22] Moshe Babaioff and Uriel Feige.  Fair shares: Feasibility, domination and incentives.  In Proc. 23rd Conf. Economics and Computation (EC), page 435, 2022.
  * [BGJ+19] Siddharth Barman, Ganesh Ghalme, Shweta Jain, Pooja Kulkarni, and Shivika Narang.  Fair division of indivisible goods among strategic agents.  In International Conference on Autonomous Agents and Multi-Agent Systems, page 1811–1813, 2019.  URL: https://www.ifaamas.org/Proceedings/aamas2019/pdfs/p1811.pdf.
  * [BILS22] Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, and Warut Suksompong.  The price of connectivity in fair division.  SIAM Journal on Discrete Mathematics, 36(2):1156–1186, 2022.  doi:10.1137/20M1388310.
  * [BK20] Siddharth Barman and Sanath Kumar Krishnamurthy.  Approximation algorithms for maximin fair division.  ACM Transactions on Economics and Computation (TEAC), 8(1):1–28, 2020.  doi:10.1145/3381525.
  * [BL16] Sylvain Bouveret and Michel Lemaître.  Characterizing conflicts in fair division of indivisible goods using a scale of criteria.  Auton. Agents Multi Agent Syst., 30(2):259–290, 2016.
  * [BM23] Anna Bogomolnaia and Hervé Moulin.  Guarantees in fair division: General or monotone preferences.  Math. Oper. Res., 48(1), 2023.
  * [BNT21] Moshe Babaioff, Noam Nisan, and Inbal Talgam-Cohen.  Competitive equilibrium with indivisible goods and generic budgets.  Math. Oper. Res., 46(1):382–403, 2021.
  * [Bud11] Eric Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  J. Political Economy, 119(6):1061–1103, 2011.
  * [CKMS21] Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa.  A little charity guarantees almost envy-freeness.  SIAM Journal on Computing, 50(4):1336–1358, 2021.  doi:10.1137/20M1359134.
  * [ESHS20] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong.  Mind the gap: Cake cutting with separation.  Artif. Intell., 313:103783, 2020.
  * [ESHS21a] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong.  Graphical cake cutting via maximin share.  In Proc. 30th Intl. Joint Conf. Artif. Intell. (IJCAI), 2021.
  * [ESHS21b] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong.  Keep your distance: Land division with separation.  In Proc. 30th Intl. Joint Conf. Artif. Intell. (IJCAI), 2021.
  * [FGH+19] Alireza Farhadi, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Sebastien Lahaie, David Pennock, Masoud Seddighin, Saeed Seddighin, and Hadi Yami.  Fair allocation of indivisible goods to asymmetric agents.  Journal of Artificial Intelligence Research, 64:1–20, 2019.  doi:10.1613/jair.1.11291.
  * [FMNP23] Michal Feldman, Simon Mauras, Vishnu V. Narayan, and Tomasz Ponitka.  Breaking the envy cycle: Best-of-both-worlds guarantees for subadditive valuations.  CoRR, abs/2304.03706, 2023.  arXiv:2304.03706, doi:10.48550/arXiv.2304.03706.
  * [FN22] Uriel Feige and Alexey Norkin.  Improved maximin fair allocation of indivisible items to three agents, 2022.  doi:10.48550/ARXIV.2205.05363.
  * [Fol67] Duncan K Foley.  Resource allocation and the public sector.  Yale Economic Essays, 7(1):45–98, 1967.
  * [FST21] Uriel Feige, Ariel Sapir, and Laliv Tauber.  A tight negative example for MMS fair allocations.  In Proc. 17th Conf. Web and Internet Economics (WINE), pages 355–372, 2021.
  * [FSV20] Rupert Freeman, Nisarg Shah, and Rohit Vaish.  Best of both worlds: Ex-ante and ex-post fairness in resource allocation.  In Proceedings of the 21st ACM Conference on Economics and Computation, pages 21–22, 2020.
  * [GGD20] Vael Gates, Thomas L. Griffiths, and Anca D. Dragan.  How to be helpful to multiple people at once.  Cognitive Science, 44, 2020.
  * [GHS+18] Mohammad Ghodsi, MohammadTaghi HajiAghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami.  Fair allocation of indivisible goods: Improvements and generalizations.  In Proc. 19th Conf. Economics and Computation (EC), pages 539–556, 2018.
  * [GM19] Laurent Gourvès and Jérôme Monnot.  On maximin share allocations in matroids.  Theoretical Computer Science, 754:50–64, 2019.  doi:10.1016/j.tcs.2018.05.018.
  * [GMT18] Jugal Garg, Peter McGlaughlin, and Setareh Taki.  Approximating maximin share allocations.  In Symposium on Simplicity in Algorithms (SOSA 2019), volume 69, pages 20:1–20:11, 2018.  doi:10.4230/OASIcs.SOSA.2019.20.
  * [GT21] Jugal Garg and Setareh Taki.  An improved approximation algorithm for maximin shares.  Artificial Intelligence, page 103547, 2021.
  * [HL21] Xin Huang and Pinyan Lu.  An algorithmic framework for approximating maximin share allocation of chores.  In Proc. 22nd Conf. Economics and Computation (EC), pages 630–631, 2021.
  * [HS21] Hadi Hosseini and Andrew Searns.  Guaranteeing maximin shares: Some agents left behind.  In Proc. 30th Intl. Joint Conf. Artif. Intell. (IJCAI), pages 238–244, 2021.
  * [HSH23] Xin Huang and Erel Segal-Halevi.  A reduction from chores allocation to job scheduling.  In Proc. 24th Conf. Economics and Computation (EC), 2023.
  * [HSSH21] Hadi Hosseini, Andrew Searns, and Erel Segal-Halevi.  Ordinal maximin share approximation for goods.  J. Artif. Intell. Res., 74, 2021.
  * [HSSH22] Hadi Hosseini, Andrew Searns, and Erel Segal-Halevi.  Ordinal maximin share approximation for chores.  ArXiv, abs/2201.07424, 2022.
  * [KPW16] David Kurokawa, Ariel D Procaccia, and Junxing Wang.  When can the maximin share guarantee be guaranteed?  In Proc. 30th Conf. Artif. Intell. (AAAI), pages 523–529, 2016.
  * [KPW18] David Kurokawa, Ariel D. Procaccia, and Junxing Wang.  Fair enough: Guaranteeing approximate maximin shares.  J. ACM, 65(2):8:1–8:27, 2018.
  * [LV21] Zhentao Li and Adrian Vetta.  The fair division of hereditary set systems.  ACM Transactions on Economics and Computation (TEAC), 9(2):1–19, 2021.  doi:10.1145/3434410.
  * [PW14] Ariel D Procaccia and Junxing Wang.  Fair enough: Guaranteeing approximate maximin shares.  In Proc. 15th Conf. Economics and Computation (EC), pages 675–692, 2014.
  * [SH17] Erel Segal-Halevi.  Competitive equilibrium for almost all incomes.  In Adaptive Agents and Multi-Agent Systems, 2017.
  * [SH19] Erel Segal-Halevi.  The maximin share dominance relation.  ArXiv, abs/1912.08763, 2019.
  * [Ste48] Hugo Steinhaus.  The problem of fair division.  Econometrica, 16:101–104, 1948.
  * [TL20] Miroslaw Truszczynski and Zbigniew Lonc.  Maximin share allocations on cycles.  Journal of Artificial Intelligence Research, 69:613–655, 2020.  doi:10.1613/jair.1.11702.
  * [Var74] Hal Varian.  Equity, envy and efficiency.  J. Econom. Theory, 29(2):217–244, 1974.
  * [Woe97] Gerhard J Woeginger.  A polynomial-time approximation scheme for maximizing the minimum machine completion time.  Oper. Res. Lett., 20(4):149–154, 1997.

##  Appendix A Missing Proofs of Section 2

See 2

###### Proof.

Let $\mathcal{I}=(N,M,V)$ be an arbitrary instance. We create a $d$-normalized
ordered instance $\mathcal{I}^{\prime\prime}=(N,M,V^{\prime\prime})$ such that
from any $1$-out-of-$d$ MMS allocation for $\mathcal{I}^{\prime\prime}$, one
can obtain a $1$-out-of-$d$ MMS allocation for the original instance
$\mathcal{I}$.

First of all, we can ignore all agents $i$ with $\text{MMS}^{d}_{i}=0$ since
no good needs to be allocated to them. Recall that for all $i\in N$,
$P^{i}=(P^{i}_{1},\ldots,P^{i}_{d})$ is a $d$-MMS partition of agent $i$. For
all $i\in N$ and $g\in M$, we define
$v^{\prime}_{i,g}=v_{i}(g)/v_{i}(P^{i}_{j})$ where $j$ is such that $g\in
P^{i}_{j}$. Now for all $i\in N$, let
$v^{\prime}_{i}:2^{M}\rightarrow\mathbb{R}_{\geq 0}$ be defined as an additive
function such that $v^{\prime}_{i}(S)=\sum_{g\in S}v^{\prime}_{i,g}$. Note
that $v^{\prime}_{i,g}\leq v_{i}(g)/\text{MMS}^{d}_{i}(M)$ for all $g\in M$
and thus,

$\displaystyle v_{i}(S)\geq v^{\prime}_{i}(S)\cdot\text{MMS}^{d}_{i}(M).$ (8)

Since $v^{\prime}_{i}(P^{i}_{j})=1$ for all $i\in N$ and $j\in[d]$,
$\mathcal{I}^{\prime}=(N,M,V^{\prime})$ is a $d$-normalized instance. If a
$1$-out-of-$d$ MMS allocation exists for $\mathcal{I}$, let $X$ be one such
allocation. By Inequality (8), $v_{i}(X_{i})\geq
v^{\prime}_{i}(X_{i})\cdot\text{MMS}^{d}_{i}(M)\geq\text{MMS}^{d}_{i}(M)$.
Thus, every allocation that is $1$-out-of-$d$ MMS for $\mathcal{I}^{\prime}$
is $1$-out-of-$d$ MMS for $\mathcal{I}$ as well. For all agents $i$ and
$g\in[m]$, let $v^{\prime\prime}_{i,g}$ be the $g$-th number in the multiset
of $\\{v_{i}(1),\ldots,v_{i}(m)\\}$. Let
$v^{\prime\prime}_{i}:2^{M}\rightarrow\mathbb{R}_{\geq 0}$ be defined as an
additive function such that $v^{\prime\prime}_{i}(S)=\sum_{g\in
S}v^{\prime\prime}_{i,g}$. Let
$\mathcal{I^{\prime\prime}}=(N,M,V^{\prime\prime})$. Note that
$\mathcal{I}^{\prime\prime}$ is ordered and $d$-normalized. Barman and
Krishnamurthy [BK20] proved that for any allocation $X$ in
$\mathcal{I^{\prime\prime}}$, there exists and allocation $Y$ in
$\mathcal{I^{\prime}}$ such that $v^{\prime}_{i}(Y_{i})\geq
v^{\prime\prime}_{i}(X_{i})$. Therefore, from any $1$-out-of-$d$ MMS
allocation in $\mathcal{I}^{\prime\prime}$, one can obtain a $1$-out-of-$d$
MMS allocation in $\mathcal{I^{\prime}}$ and as already shown before, it gives
a $1$-out-of-$d$ MMS allocation for $\mathcal{I}$. ∎

##  Appendix B Limitations of Oblivious Analysis

We start by showing an attempt to improve the upper bounds of Section 4.3.
Although our attempt does not succeed, it reveals a shortcoming of existing
techniques (including ours) to analyze bag-filling algorithms. We formally
characterize this using a concept called _obliviousness_ , and study the
limitations of oblivious techniques.

###  B.1 Attempt to get a Hard Example

Consider a fair division instance $\mathcal{I}:=([n],[m],v)$ with $n:=6$
agents, where each agent $i$ has priority rank $i$. We will analyze
$\operatorname{\mathtt{RBF}}$ from the perspective of agent 4. Section 4.3
says that $\tau_{4}$ should be at most $0.9$ for $\operatorname{\mathtt{RBF}}$
to always succeed. We will try to improve this to $\tau_{4}\leq
5/6=0.8\overline{3}$. According to agent 4, say the first 3 goods have value
$5/6$, the next 9 goods of value $1/3$, and the remaining $3t$ goods have
value $\varepsilon:=1/6t$, for some $t\in\mathbb{Z}_{\geq 3}$.

$\mathcal{I}$ is ordered and normalized according to agent 4: 3 of her MMS
bundles have 3 goods of value $1/3$ each, and each of the remaining bundles
has one good of value $5/6$ and $t$ goods of value $1/6t$.

Suppose $\tau_{4}>5/6+2\varepsilon$. Then agent 4 does not want any bundle
during reduction, since $v_{1}(1)\leq
v_{1}(\\{1,2n+1\\})=5/6+\varepsilon<\tau_{4}$,
$v_{1}(\\{n,n+1\\})=2/3<\tau_{4}$, and
$v_{1}(\\{2n-1,2n+1,2n+1\\})=2/3+\varepsilon<\tau_{4}$. Suppose the other
agents also do not want any of the above bundles. Hence, no reduction events
happen during $\operatorname{\mathtt{RBF}}$, and
$\operatorname{\texttt{bagFill}}$ starts.

According to agent 4, the first 3 bags have value $5/6+1/3=7/6$ each. Suppose
the first 3 agents also want these bags. Since they have a smaller priority
rank, these bags go to the first 3 agents. Agent 4 does not like any of the
remaining bags, since they have value $2/3$. Suppose agents 5 and 6 also do
not like these bags. Hence, we start adding goods to these bags. Since all
goods in $[m]\setminus[2n]$ have value $\varepsilon$ to agent 4, agent 4 would
want a bag only if at least $t+3$ goods are added to it. Suppose agents 5 and
6 like a bag iff it gets at least $t+2$ goods from $[m]\setminus[2n]$. Since
there are only $3t$ goods of value $\varepsilon$, agent 4 does not get a bag
of value $\geq\tau_{4}$.

At first glance, this seems to prove that $\operatorname{\mathtt{RBF}}$ cannot
give agent 4 more than $5/6$-MMS. But there is a catch: we have not mentioned
what the valuations and thresholds of the other agents are. Are there
valuations and thresholds for which $\operatorname{\mathtt{RBF}}$ behaves as
above?

When all agents have the same valuation function as agent 4, and agents 5 and
6 have thresholds in the range $(5/6+\varepsilon,5/6+2\varepsilon]$, then
$\operatorname{\mathtt{RBF}}$ indeed behaves as described above. However, this
threshold range is unreasonable since Section 4.3 says that $\tau_{6}\leq
9/11<5/6$ for $\operatorname{\mathtt{RBF}}$ to succeed. Are there (ordered and
normalized) valuations and reasonable thresholds for the agents such that
$\operatorname{\mathtt{RBF}}$ behaves as described above? We could not resolve
this question.

###  B.2 Obliviousness

Let us think of fair division algorithms as interactive protocols, where the
algorithm repeatedly makes value queries to agents, i.e., it finds out
$v_{i}(S)$ for some agent $i$ and some set $S$ of goods, instead of just
querying the value of each good for each agent upfront.
$\operatorname{\mathtt{RBF}}$ can be interpreted in this way: during the
reduction phase, it queries $v_{i}(S)$ for
$S\in\\{\\{1\\},\\{n,n+1\\},\\{2n-1,2n,2n+1\\},\\{1,2n+1\\}\\}$, and during
the bag-filling phase, it repeatedly queries the value of some bag.

Let $\mathcal{A}$ be an algorithm for fair division, let $i^{*}$ be an agent,
and let $T:=(\tau_{1},\ldots,\tau_{n})$ be a list of thresholds. Generally,
when we analyze $\mathcal{A}$, we ask the following question: Does
$\mathcal{A}$’s output give each agent $i$ at least $\tau_{i}$ times her MMS,
given that all agents answer value queries truthfully?

An _oblivious analysis_ of $\mathcal{A}$, on the other hand, asks the
following question: For each $i\in[n]$, does $\mathcal{A}$’s output give agent
$i$ at least $\tau_{i}$ times her MMS if agent $i$ answers value queries
truthfully and all other agents are free to answer value queries non-
truthfully? Note that in an oblivious analysis, the other agents’ responses
are not required to be consistent with any (additive, ordered, normalized)
valuation function. Also, we do not assume that the other agents are rational,
i.e., they may answer value queries arbitrarily, even if it hurts them.

In the oblivious setting, we wish to show that an agent $i$ can secure a
certain fraction of her MMS for any possible responses of the other agents.
This is a worst-case analysis, so imagine that the other $n-1$ agents are
controlled by an adversary (who knows $i$’s valuation function) whose sole
motive is to reduce the value of $i$’s bundle. Furthermore, the oblivious
setting is more demanding than a non-oblivious one, i.e., if $i$ is guaranteed
$\alpha$ times her MMS in the oblivious setting, then she also gets $\alpha$
times her MMS in the non-oblivious setting.

The analysis of bag-filling algorithms in the literature [AGST23, GT21, AG24,
GMT18], and our analysis in Section 4, work in the oblivious setting. In fact,
it is unclear how to _not_ do an oblivious analysis. In this sense,
obliviousness is a hard-to-bypass barrier towards the design of approximate
MMS algorithms.

Furthermore, we can get tighter upper bounds on thresholds in the oblivious
setting. E.g., Section B.1 shows that for 6 agents, we need $\tau_{4}\leq 5/6$
for $\operatorname{\mathtt{RBF}}$ to succeed in the oblivious setting. We now
generalize this example to an arbitrary number of agents.

######  Theorem 10.

Let $T:=(\tau_{1},\ldots,\tau_{n})$ be a list of thresholds, where $n\geq 2$.
If $\operatorname{\mathtt{RBF}}(\cdot,T)$ always outputs a $T$-MMS allocation
in the oblivious setting, then for each $i\in[n]$, we have

$\tau_{i}\leq\max\left(\frac{5}{6},1-\frac{i-1}{3n}\right).$

###### Proof.

Let $k_{1},k_{2}\in[n]$ such that $k_{1}+k_{2}<i$ and $2k_{1}+k_{2}\leq n$.
Let $\alpha:=1-k_{1}/3(n-k_{2})$. Let $t\in\mathbb{Z}_{\geq 3}$ and
$\varepsilon:=1/3t(n-k_{2})$. Then $\alpha\in[5/6,1-\varepsilon)$. Pick an
arbitrary agent $i$. Assume without loss of generality that $i\geq 2$
(otherwise theorem is trivially true). According to agent $i$, let there be
$k_{1}+k_{2}$ goods of value $\alpha$, $2n-k_{1}-2k_{2}$ goods of value $1/3$,
and $(n-k_{1}-k_{2})^{2}t$ goods of value $\varepsilon$. Let
$\tau_{i}>\alpha+2\varepsilon$.

The instance is normalized for agent $i$, since the MMS partition is as
follows:

  1. 1.

$k_{1}$ bundles: one good of value $\alpha$ and $k_{1}t$ goods of value
$\varepsilon$.

  2. 2.

$k_{2}$ bundles: one good of value $\alpha$ and one good of value $1-\alpha$.

  3. 3.

$k_{1}$ bundles: 3 goods of value $1/3$.

  4. 4.

$n-2k_{1}-k_{2}$ bundles: 2 goods of value $1/3$ and $1/3\varepsilon$ goods of
value $\varepsilon$.

Suppose no reduction events happen during $\operatorname{\mathtt{RBF}}$. This
is possible because $v_{i}(\\{n,n+1\\})=2/3<\tau_{i}$,
$v_{i}(\\{2n-1,2n,2n+1\\})\leq 2/3+\varepsilon<\tau_{i}$, and
$v_{i}(\\{1,2n+1\\})=\alpha+\varepsilon<\tau_{i}$.

Suppose $\operatorname{\mathtt{RBF}}$ gives away $k_{1}+k_{2}$ bags having a
good of value $\alpha$ and a good of value $1/3$ or $1-\alpha$ to the first
$k_{1}+k_{2}$ agents. All the remaining bags initially have 2 goods of value
$1/3$. Suppose each of them receives at most $(n-k_{1}-k_{2})t+2$ goods of
value $\varepsilon$. Then each of those bags has value at most
$\alpha+2\varepsilon$. Hence, agent $i$ will not get a bag of value
$\geq\tau_{i}$.

Hence, if $\tau_{i}>\alpha$, then for some large enough $t$,
$\operatorname{\mathtt{RBF}}$ cannot give a bag of value $\geq\tau_{i}$ to
agent $i$. If $i\leq n/2+1$, then set $k_{1}=i-1$ and $k_{2}=0$ to get
$\tau_{i}\leq 1-(i-1)/3n$. Otherwise, set $k_{1}=\lfloor n/2\rfloor$ and
$k_{2}=n-2k_{1}$ to get $\tau_{i}\leq 5/6$. Hence,

$\tau_{i}\leq\max\left(\frac{5}{6},1-\frac{i-1}{3n}\right).\qed$

Our approach in Section 4.2 to get best-of-both-worlds fairness is by running
$\operatorname{\mathtt{RBF}}$ with random priority ranks (as in Lemma 23). If
$\operatorname{\mathtt{RBF}}$ is $T$-MMS, this gives us ex-post $\tau_{n}$-MMS
and ex-ante $\frac{1}{n}(\sum_{i=1}^{n}\tau_{i})$-MMS. In the oblivious
setting, by Theorems 8 and 10, the best ex-ante MMS guarantee we can get is

$\frac{1}{n}\sum_{i=1}^{n}\min\left(\frac{3n}{3n+i-2},\max\left(\frac{5}{6},1-\frac{i-1}{3n}\right)\right).$

We now show an upper-bound on this quantity.

######  Lemma 27.

For all $n\geq 1$,

$\frac{1}{n}\sum_{i=1}^{n}\min\left(\frac{3n}{3n+i-2},\max\left(\frac{5}{6},1-\frac{i-1}{3n}\right)\right)\leq\frac{13}{24}+3\ln\left(\frac{10}{9}\right)+\frac{1}{3n}.$

###### Proof.

(Proof deferred to Section B.3). ∎

######  Theorem 11.

If we fix the number of agents to $n$, the ex-ante MMS guarantee obtainable
from $\operatorname{\mathtt{RBF}}$ in the oblivious setting by picking
priority ranks randomly (as in Lemma 23) is not better than $\beta$-MMS, where
$\beta:=\frac{13}{24}+3\ln\left(\frac{10}{9}\right)+\frac{1}{3n}\approx
0.8578+\frac{1}{3n}$, and the ex-post MMS guarantee is not better than
$\gamma$-MMS, where $\gamma:=3n/(4n-2)=\frac{3}{4}+\frac{3}{8n-4}$.

###### Proof.

Follows from Theorems 8, 10, 23 and 26. ∎

###  B.3 Bounding Sums using Integrals

######  Lemma 28.

Let $f:[a,b]\to\mathbb{R}_{\geq 0}$ be a non-increasing function and let $F$
be its antiderivative. Then

$f(b)+\int_{a}^{b}f(x)dx\leq\sum_{i=a}^{b}f(i)\leq f(a)+\int_{a}^{b}f(x)dx.$

See 24

###### Proof.

Define $f:[0,n-1]\to\mathbb{R}_{\geq 0}$ as

$f(x):=\max\left(\frac{2n}{2n+x},\,\frac{3}{4}+\frac{1}{12n}\right).$

Let $\beta:=2n(3n-1)/(9n+1)$. Then

$\frac{2n}{2n+x}\geq\frac{3}{4}+\frac{1}{12n}\iff x\leq\beta.$

Hence,

$f(x):=\begin{cases}\displaystyle\frac{2n}{2n+x}&\textrm{ if
}x\in[0,\beta)\\\\[10.00002pt] \displaystyle\frac{3}{4}+\frac{1}{12n}&\textrm{
if }x\in(\beta,n-1]\end{cases}.$

Therefore,

$\displaystyle\gamma$
$\displaystyle=\frac{1}{n}\sum_{i=0}^{n-1}f(i)\geq\frac{1}{n}\left(\frac{3}{4}+\frac{1}{12n}+\int_{0}^{n-1}\\!\\!\\!\\!\\!\\!f(x)dx\right)$
(by Lemma 28)
$\displaystyle=\frac{1}{n}\left(2n\ln\left(\frac{2n+\beta}{2n}\right)+\left(\frac{3}{4}+\frac{1}{12n}\right)(n-\beta)\right)$
$\displaystyle=2\ln\left(\frac{4}{3}\right)+\frac{1}{4}+\frac{1}{4n}-2\ln\left(1+\frac{1}{9n}\right)$
$\displaystyle\geq
2\ln\left(\frac{4}{3}\right)+\frac{1}{4}+\frac{1}{4n}-\frac{2}{9n}$ (since
$\ln(1+x)\leq x$ for all $x>-1$)
$\displaystyle=2\ln\left(\frac{4}{3}\right)+\frac{1}{4}+\frac{1}{36n}.\qed$

See 26

###### Proof.

$\displaystyle\frac{1}{n}\left(2+\sum_{i=3}^{n}\frac{3n}{3n+i-2}\right)=\frac{1}{n}\left(1+\sum_{i=0}^{n-2}\frac{3n}{3n+i}\right)$
$\displaystyle\leq\frac{1}{n}\left(2+3n\int_{0}^{n-2}\frac{dx}{3n+x}\right)$
(by Lemma 28)
$\displaystyle=\frac{2}{n}+3\ln\left(\frac{4}{3}\right)+3\ln\left(1-\frac{1}{2n}\right)$
$\displaystyle\leq\frac{2}{n}+3\ln\left(\frac{4}{3}\right)-\frac{3}{2n}$
(since $\ln(1-x)\leq-x$ for all $x<1$)
$\displaystyle=3\ln\left(\frac{4}{3}\right)+\frac{1}{2n}.\qed$

See 27

###### Proof.

Define $f:[0,n-1]\to\mathbb{R}_{\geq 0}$ as

$f(x):=\min\left(\frac{3n}{3n+x-1},\max\left(\frac{5}{6},1-\frac{x}{3n}\right)\right).$

Then for $x\geq 0$,

$\frac{3n}{3n+x-1}-\left(1-\frac{x}{3n}\right)=\frac{x(x-1)+3n}{3n(3n+i-2)}>0.$
$\frac{5}{6}\geq 1-\frac{x}{3n}\iff x\geq\frac{n}{2}.$
$\frac{5}{6}\leq\frac{3n}{3n+x-1}\iff x\leq\frac{3n}{5}+1.$

Hence,

$f(x)=\begin{cases}1-x/3n&\textrm{ if }x\in[0,n/2]\\\ 5/6&\textrm{ if
}x\in\big{(}\frac{n}{2},\frac{3n}{5}+1\big{]}\\\
\displaystyle\frac{3n}{3n+x-1}&\textrm{ if
}x\in\big{(}\frac{3n}{5}+1,n-1\big{]}\end{cases}.$

Therefore,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}f(i-1)\leq\frac{1}{n}\left(f(0)+\int_{0}^{n-1}f(x)dx\right)$
(by Lemma 28)
$\displaystyle=\frac{1}{n}\left(1+\int_{0}^{\frac{n}{2}}\left(1-\frac{x}{3n}\right)dx+\int_{\frac{n}{2}}^{\frac{3n}{5}+1}\frac{5}{6}dx+\int_{\frac{3n}{5}+1}^{n-1}\frac{3n}{3n+x-1}dx\right)$
$\displaystyle=\frac{1}{n}\left(\frac{11}{6}+\frac{13}{24}n+3n\ln\left(\frac{10}{9}\left(1-\frac{1}{2n}\right)\right)\right)$
$\displaystyle\leq\frac{13}{24}+3\ln\left(\frac{10}{9}\right)+\frac{1}{3n}.$
(since $\ln(1-x)\leq-x$ for all $x<1$)

∎