# Budget-feasible Maximum Nash Social Welfare Allocation is Almost Envy-free

Xiaowei Wu1 Bo Li2 Jiarui Gan3
1IOTSC, University of Macau
2Department of Computing, The Hong Kong Polytechnic University
3Max Planck Institute for Software Systems
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The Nash social welfare (NSW) is a well-known social welfare measurement that
balances individual utilities and the overall efficiency. In the context of
fair allocation of indivisible goods, it has been shown by Caragiannis et al.
(EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up
to one good (EF1). In this paper, we are interested in the fairness of the NSW
in a budget-feasible allocation problem, in which each item has a cost that
will be incurred to the agent it is allocated to, and each agent has a budget
constraint on the total cost of items she receives. We show that a budget-
feasible allocation that maximizes the NSW achieves a $1/4$-approximation of
EF1 and the approximation ratio is tight. The approximation ratio improves
gracefully when the items have small costs compared with the agents’ budgets;
it converges to $1/2$ when the budget-cost ratio approaches infinity.

##  1 Introduction

Fairness and efficiency are two of the primary considerations in public
economics. Yet, these two objectives are often unaligned and even conflict
with each other. The Nash social welfare (NSW) — proposed by Nash as a
solution for bargaining problems [21, 16] — is a well-known social welfare
function that balances individual utilities and the overall efficiency. In
more details, the NSW of a solution $\mathbf{x}$ is defined as the product of
the agents’ values $v_{i}(\mathbf{x})$ provided by this solution. As noted in
[4], it can be viewed as a special case of a family of functions known as
generalized (power) means:

$\textstyle
M_{p}(\mathbf{x})=\left(\frac{1}{n}\sum_{i}v_{i}(\mathbf{x})^{p}\right)^{1/p}.$

When $p=1$, $M_{p}(\mathbf{x})$ defines the utilitarian social welfare, i.e.,
the average of all agents’ values; and when $p\to-\infty$, $M_{p}(\mathbf{x})$
defines the egalitarian social welfare, i.e., the minimum value received by an
agent. The NSW corresponds to exactly the limit of $M_{p}(\mathbf{x})$ when
$p\to 0$, i.e., $\left(\prod_{i\in N}v_{i}(\mathbf{x})\right)^{1/n}$. Thus, it
serves a middle ground between the two other cases. A Max-NSW allocation,
i.e., an allocation that maximizes the NSW, naturally leads to balanced values
among the agents while it also nudges the overall efficiency towards the
maximum.

In the context of fair allocation of indivisible goods, it has been shown by
Caragiannis et al. [6, 7] that a Max-NSW allocation is envy-free up to one
good (EF1); namely, it ensures that every agent does not envy the bundle of
any other agent by more than one item. The fairness of the NSW has since
attracted much attention from the fair allocation community.

###  1.1 Our Results

In this paper, we study the fairness of the NSW in a budget-feasible
allocation problem. In this problem, every item $j$ has a cost of $c_{j}$ that
will be incurred to the agent it is allocated to, and every agent $i$ has a
budget $B_{i}>0$ that can be used to pay for the additive cost of the bundle
$S$ of items she receives, i.e., $c(S)=\sum_{j\in S}c_{j}\leq B_{i}$. An
allocation $(X_{1},\cdots,X_{n})$ is a collection of disjoint subsets of
items, whereby $X_{i}$ is the bundle of items allocated to agent $i$, yielding
value $v_{i}(X_{i})$ for this agent. An allocation is budget-feasible if
$c(X_{i})\leq B_{i}$ for all $i$, i.e., every agent can afford the cost
incurred by this allocation. Accordingly, a Max-NSW feasible allocation is
equivalent to the solution to the following problem.

$\displaystyle\max_{(X_{1},\cdots,X_{n})}$ $\displaystyle\quad\prod_{i\in
N}v_{i}(X_{i})$ subject to $\displaystyle\quad(X_{1},\cdots,X_{n})\text{ \em
is budget-feasible.}$

Note that since allocations are subject to budget constraints, it is not
always possible to allocate all items. The unallocated items are assumed to be
allocated to a charity who has unlimited budget. Indeed, it is not hard to see
that a Max-NSW allocation is Pareto-optimal (PO), i.e., we cannot hope to
further improve some agent’s utility without hurting the other agents. This
immediately implies that no agent has any incentive to exchange her bundle
with any subset of unallocated items that fits within her budget. An
interesting question is whether the agents would wish to exchange their
bundles with the other agents.

To answer this question, we adapt the classic EF (envy-free) notion to the
budget-feasible setting. In our EF notion, an agent $i$ envies another agent
$j$ if there is a subset of items allocated to agent $j$ that costs at most
$B_{i}$ and gives agent $i$ a strictly higher value. The EF1 notion can be
defined similarly: agent $i$ envies agent $j$ for more than one item if there
is a subset of $X_{j}$ that costs at most $B_{i}$ and gives $i$ a strictly
higher value even after removing the most valuable item from this subset. An
allocation is said to be EF (resp., EF1) if no agent envies any other agent
(resp., for more than one item). We show that, unlike the setting without
budget constraints, a Max-NSW allocation is no longer always EF1. However, it
remains a good approximation of EF1. Our main contributions are summarized by
the following two results, where we call an allocation $\alpha$-EF1 is it
achieves an $\alpha$ approximation of EF1, for $\alpha\in[0,1]$.

Main Result 1. A Max-NSW allocation is $\frac{1}{4}$-EF1 and PO.

We also show that the approximation ratio we proved cannot be improved.
Specifically, we construct an instance for which a Max-NSW allocation is
exactly $1/4$-EF1. We observe that this instance requires some items to have
very high costs compared with the agents’ budgets, i.e., the budget-cost ratio
is $\kappa=\min_{i,j}\frac{B_{i}}{c_{j}}=1$. This motivates our study of the
large budget case where $\kappa$ is large. Interestingly, we find that the
approximation guarantee improves gracefully with $\kappa$ and eventually
converges to ${1}/{2}$ when $\kappa$ goes to infinity.

Main Result 2. A Max-NSW allocation is
$\left(\frac{1}{2}-\frac{5}{\kappa^{1/4}}\right)$-EF1.

Note that instances with large budget are also a typical setting of the bin
packing problem that has received considerable interests in the literature
[15, 13, 20, 17]. We remark that when $\kappa$ goes to infinity our model does
not degenerate to the one without budget constraints, because the number of
items can be infinity as well. This is why the approximation ratio does not
converge to $1$ as in the setting without budget constraints.

#### Technical Novelty.

We remark that deriving the above results requires techniques very different
from those employed in previous work. The approach of Caragiannis et al. [6,
7] for proving the EF1-ness of Max-NSW allocation is by contradiction: if a
Max-NSW allocation were not EF1, then by reallocating some items, the NSW
could be improved. In our setting, such reallocations need to conform to the
budget constraints. We may need to discard some items when reallocating items
to an agent. Thus, applying the same argument requires a larger difference
between the agents’ values. Indeed, this is why the Max-NSW allocation is only
approximately EF1 in our setting, instead of being exactly EF1.

Our analysis for the second main result is more challenging. We observe that
if the items are divisible, then any Max-NSW allocation must be $1/2$-EF1. To
convert the analysis to the indivisible case, we show that in the divisible
analysis at most a constant number of items are fractionally allocated. Then
it suffices to give a rounding scheme for a small number of fractional items.
A main challenge arises when we have to deal with fractional items with large
values. We resolve this issue by using a fine-tuned classification of items
into heavy and light ones and applying different analyses depending on the
class the majority of the items belong to.

###  1.2 Related Work

There is a large literature on fair division and NSW. Due to space limit, we
only discuss the most related previous work. The pioneering work of
Caragiannis et al. [6, 7] triggered a series of follow-up interests in the
fairness of the NSW. It is shown in [3] that with matriod constraints a Max-
NSW allocation is always EF1 if the agents have identical valuations. More
recently, Amanatidis et al. [1] proved that a Max-NSW allocation guarantees
envy-freeness up to any item (EFX) if there are at most two possible values
for the goods. The fairness of NSW has also been studied in the setting when
the goods are public [11, 14]. Furthermore, the algorithm in [2] showed that
there is an allocation that is simultaneously $1/1.45$-approximate Max-NSW,
Pareto optimal, and $(1-\epsilon)$-approximate EF1. Similarly, the algorithm
in [19] computes an allocation that is $1/2$-approximate Max-NSW, proportional
up to one item, $1/(2n)$-approximate maximin share fair, and Pareto optimal
and can be found in polynomial time. No previous work has considered the
setting with budget constraints to the best of our knowledge.

Our work is conceptually related to a line of work on fair division that
involves a charity in the models. In our budget-feasible setting, unallocated
items are assumed to be donated to a charity. The concept of charity has also
been used to simplify analysis of EFX allocations as was in [6, 7].
Caragiannis et al. also showed that there is an EFX allocation on a subset of
items that is a $1/2$-approximation of Max-NSW over the original set of items
[5]. Similarly, Chaudhury et al. [8] proved that by donating no more than $n$
items, there is an EFX allocation for the remaining items and no agent envies
the charity.

The complexity of computing a Max-NSW allocation has been studied for various
types of valuation functions [24, 12]. The problem is APX-hard for additive
valuation functions [22, 18]. There has been some effort towards designing
efficient algorithms to compute approximate Max-NSW allocations [23, 10, 9].
The state-of-the-art approximation ratio of NSW is $1.45$ by [2].

##  2 Preliminaries

In our model, a set $M$ of $m$ goods will be allocated to a set $N$ of $n$
agents. Every item $j\in M$ has a cost $c_{j}\geq 0$ and every agent $i\in N$
has a budget $B_{i}\geq 0$. Each agent $i$ has an additive valuation function
$v_{i}:2^{M}\rightarrow\mathbb{R}^{+}\cup\\{0\\}$ on the subsets of items.
Equivalently, we can express the valuation function $v_{i}$ as a vector
$v_{i}=(v_{i1},\cdots,v_{im})$, where $v_{ij}\in\mathbb{R}^{+}\cup\\{0\\}$
denotes agent $i$’s value for item $j$. Upon receiving a subset $S\subseteq M$
of items, an agent $i$ obtains an additive value $v_{i}(S)=\sum_{j\in
S}v_{ij}$; in addition, the allocation incurs an additive cost
$c(S)=\sum_{j\in S}c_{j}$ to agent $i$, which needs to be paid using her
budget. We assume that the values for the items and the cost of the allocation
are not mutually convertible. For example, the cost may represent the size of
the items and the budget represents the capacity of her knapsack, which cannot
be converted from the items’ values.

An allocation $\mathbf{X}=(X_{0},X_{1},\cdots,X_{n})$ is a partition of the
item set $M$ into $n+1$ bundles, where $X_{i}\subseteq M$ is the bundle of
items allocated to agent $i$ for each $i\in N$ and $X_{0}$ is the set of
unallocated item (recall that due to the budget constraints, we cannot
guarantee $\bigcup_{i=1}^{n}X_{i}=M$). The unallocated items can be thought of
as a donation to a special agent $0$, i.e., a charity, who has an unbounded
budget and value $0$ for every item (in the sense that she does not envy any
other agents no matter what they get). An allocation $\mathbf{X}$ is _budget-
feasible_ if $c(X_{i})\leq B_{i}$, for all $i\in N$.

In the remainder of this paper, we require every allocation to be feasible.
When we write “an allocation” we mean “a feasible allocation” unless otherwise
stated. For convenience, for a set $X$ and an element $j$, we will write
$X\cup\\{j\\}$ as $X+j$ and $X\setminus\\{j\\}$ as $X-j$ throughout the paper.

######  Definition 2.1 (Max-NSW)

An allocation $\mathbf{X^{*}}$ is a Max-NSW allocation if it maximizes the
Nash social welfare, i.e., $\prod_{i\in N}v_{i}(X_{i}^{*})\geq\prod_{i\in
N}v_{i}(X_{i})$ for any allocation $\mathbf{X}$.

In the budget-feasible setting, an agent cannot hope to take a bundle that
costs more than her budget. We adapt the EF notion accordingly and define it
as follows.

######  Definition 2.2 (EF)

For any $\alpha\in[0,1]$, an allocation $\mathbf{X}$ is $\alpha$-approximate
envy-free ($\alpha$-EF) if for any two agents $i,j\in N$ and any $S\subseteq
X_{j}$ with $c(S)\leq B_{i}$, it holds that

$v_{i}(X_{i})\geq\alpha\cdot v_{i}(S).$

When $\alpha=1$, $\mathbf{X}$ is also said to be EF.

This definition is consistent with the standard EF notion when every agent’s
budget is $c(M)$. Since the items are indivisible, (approximate) EF is hard to
achieve. One of the most widely studied relaxed notion is envy-free up to one
item.

######  Definition 2.3 (EF1)

For any $\alpha\in[0,1]$, an allocation $\mathbf{X}$ is $\alpha$-approximate
envy-free up to one item ($\alpha$-EF1) if for any two agents $i,j\in N$ and
any $S\subseteq X_{j}$ with $c(S)\leq B_{i}$, there exists $j\in S$ such that

$v_{i}(X_{i})\geq\alpha\cdot v_{i}(S-j).$

When $\alpha=1$, $\mathbf{X}$ is also said to be EF1.

Trivially, an allocation $\mathbf{X}=(M,\emptyset,\dots,\emptyset)$ (i.e.,
allocating all items to the charity) is already EF and EF1. Apparently, such
an allocation is not efficient for the agents by any reasonable measurement of
efficiency. Therefore, we consider Pareto optimality as a criterion for
efficiency.

######  Definition 2.4 (PO)

An allocation $\mathbf{X}$ is Pareto optimal (PO) if there exists no
allocation $\mathbf{X}^{\prime}$ such that $v_{i}(X^{\prime}_{i})\geq
v_{i}(X_{i})$ for all $i\in N$ and $v_{j}(X^{\prime}_{j})>v_{j}(X_{j})$ for
some $j\in N$.

Note that in a PO allocation $\mathbf{X}$ no agent $i$ can improve her value
by exchanging items with the charity (subject to budget constraint), i.e., for
any $S\subseteq X_{i}\cup X_{0}$ such that $c(S)\leq B_{i}$, it holds that
$v_{i}(X_{i})\geq v_{i}(S)$.

##  3 Max-NSW Allocation is $\frac{1}{4}$-EF1 and PO

In this section, we present our first main result, which is stated in the
theorem below.

###### Theorem 3.1

A Max-NSW allocation $\mathbf{X^{*}}$ is $\frac{1}{4}$-EF1 and PO.

Before presenting the proof, we remark that the ${1}/{4}$ approximation ratio
is tight, even when agents have identical valuation and budget. We present an
instance for which a Max-NSW allocation is not $c$-EF1, for any constant
$c>{1}/{4}$.

###### Example 3.2

Let $\epsilon>0$ be arbitrarily close to $0$. Consider the instance with two
agents who have the identical valuation $v$ and budget $B=1$. Let there be
$1+\frac{1}{\epsilon}$ items, where $v_{1}=1+\epsilon$, $c_{1}=1$,
$v_{j}=4\epsilon$, and $c_{j}=\epsilon$ for all
$j\in\\{2,3,\ldots,1+\frac{1}{\epsilon}\\}$. It can be verified that the
allocation $\mathbf{X}^{*}$ with $X_{1}^{*}=\\{1\\}$ and
$X_{2}^{*}=\\{2,\ldots,1+\frac{1}{\epsilon}\\}$ maximizes the NSW with
$v(X_{1}^{*})\cdot v(X_{2}^{*})=4(1+\epsilon)$. However, $\mathbf{X}^{*}$ is
not $c$-EF1, for any $c>\frac{1}{4}$, because
$v(X_{1}^{*})=\frac{1-\epsilon^{2}}{4}\cdot v(X_{2}^{*}-j)$ for all $j\in
X_{2}^{*}$.

$j$ | 1 | 2 | $\ldots$ | $1+\frac{1}{\epsilon}$
---|---|---|---|---
$v_{j}$ | $1+\epsilon$ | $4\epsilon$ | $\ldots$ | $4\epsilon$
$c_{j}$ | 1 | $\epsilon$ | $\ldots$ | $\epsilon$

Next we proceed to the proof of Theorem 3.1.

Proof of Theorem 3.1:  It is trivial to see that $\mathbf{X^{*}}$ is PO
because if there is another allocation that increases one agent’s value
without decreasing any other agent’s value, it must also increase the NSW,
which contradicts the maximum of NSW under $\mathbf{X^{*}}$. In what follows,
we prove that $\mathbf{X^{*}}$ is $\frac{1}{4}$-EF1 by contradiction. Suppose
that a Max-NSW allocation $\mathbf{X^{*}}$ is not $\frac{1}{4}$-EF1, we show
that there exists another allocation $\mathbf{X^{\prime}}$ with a strictly
larger NSW, which is a contradiction with $\mathbf{X^{*}}$ being a Max-NSW
allocation.

By assumption, there exist two agents, say $1$ and $2$, such that agent $1$
finds a set $T\subseteq X_{2}$ such that $c(T)\leq B_{1}$ and

$\displaystyle v_{1}(T-j)>4\cdot v_{1}(X_{1}),\qquad\text{ for all }j\in T.$
(1)

For ease of description, we rename the items in $T$ as $\\{1,2,\cdots,t\\}$
such that $v_{2j}\leq v_{2,j+1}$ for any $1\leq j<t$. Let $T_{1}=\\{j\in
T-t:j\text{ is odd}\\}$ and $T_{2}=\\{j\in T-t:j\text{ is even}\\}$. Note that
we have either

$v_{2}(T_{1})\leq v_{2}(T_{2})\leq v_{2}(T_{1}+t)\quad\text{ or }\quad
v_{2}(T_{2})\leq v_{2}(T_{1})\leq v_{2}(T_{2}+t).$

In other words, under the valuation of agent $2$, if we assign item $t$ to the
bundle with smaller value, then the resulting bundle has value at least that
of the other bundle.

Now we can construct a new allocation $\mathbf{X}^{\prime}$, where

  * •

$X^{\prime}_{i}=X_{i}$ for all $i\geq 3$,

  * •

$X^{\prime}_{1}=T_{l}$, where
$l\in\arg\max_{\ell\in\\{1,2\\}}v_{1}(T_{\ell})$,

  * •

$X^{\prime}_{2}=X_{2}\setminus T_{l}$, and

  * •

$X^{\prime}_{0}=X_{0}\cup X_{1}$.

In other words, we first remove all the items originally allocated to agent
$1$. Then we pick the bundle agent $1$ prefers in $\\{T_{1},T_{2}\\}$, and
move items in this bundle from $X_{2}$ to $X_{1}$. Note that under the
valuation of agent $2$, the items agent $2$ loses have total value at most
$\frac{1}{2}\cdot v_{2}(T)$. In addition, $\mathbf{X}^{\prime}$ is a feasible
allocation as $c(T_{l})\leq c(T)\leq B_{1}$ and $c(X_{2}\setminus T_{l})\leq
c(X_{2})\leq B_{2}$. By Equation (1), we then have

$v_{1}(X^{\prime}_{1})\geq\frac{1}{2}\cdot v_{1}(T-j)>2\cdot v_{1}(X_{1}).$

Moreover,

$v_{2}(X^{\prime}_{2})=v_{2}(X_{2})-v_{2}(T_{l})\geq\frac{1}{2}\cdot
v_{2}(X_{2}).$

Since $v_{i}(X^{\prime}_{i})=v_{i}(X_{i})$ for all $i\geq 3$, it follows that

$\prod_{i\in N}v_{i}(X^{\prime}_{i})>\prod_{i\in N}v_{i}(X_{i}),$

which contradicts the fact that $\mathbf{X^{*}}$ is Max-NSW.

#### Remark.

While we assume that the valuation functions are additive, our result holds
with sub-additive valuation functions as well. We provide the details in the
Appendix A.

##  4 Improved Ratios with Large Budgets

We have shown that in general, the $1/4$ approximation ratio can not be
improved. However, one observation is that in the tight instance we presented
(Example 3.2), the budgets are such that $B_{1}=B_{2}=1=\max_{j\in M}c_{j}$.
In other words, an agent’s budget may be exhausted by allocating only one item
to her. Interestingly, we find that when this is not the case, the
approximation ratio can be improved.

###  4.1 Warm-up Analysis

As a warm up, we show that if it takes at least two item to exhaust the budget
of any agent, then the approximation ratio can be slightly improved to
$\frac{3}{11}\approx 0.273$.

###### Lemma 4.1

Suppose $B_{i}\geq 2\cdot c_{j}$ for all $i\in N$ and $j\in M$. Then a Max-NSW
allocation $\mathbf{X^{*}}$ is $\frac{3}{11}$-EF1.

Proof:  Suppose for the sake of contradiction that a Max-NSW allocation
$\mathbf{X^{*}}$ is not $\frac{3}{11}$-EF1. Without loss of generality, let
agents $1$ and $2$ be the two agents that block $\mathbf{X}^{*}$ from being
$\frac{3}{11}$-EF1. In other words, there exists $T\subseteq X_{2}$ with
$c(T)\leq B_{1}$ such that for any $j\in T$, we have

$v_{1}(T-j)>\frac{11}{3}\cdot v_{1}(X_{1}).$

We use a similar approach to the proof of Theorem 3.1 and partition $T$ into
three subsets $T_{1}$, $T_{2}$, and $\\{t\\}$ such that

$v_{2}(T_{1})\leq v_{2}(T_{2})\leq v_{2}(T_{1}\cup\\{t\\}).$

#### Case 1.

If there exists $l\in\\{1,2\\}$ such that $v_{1}(T_{l})>2\cdot v_{1}(X_{1})$,
we construct a new allocation $\mathbf{X}^{\prime}$ with
$X^{\prime}_{i}=X_{i}$ for all $i\geq 3$, $X^{\prime}_{1}=T_{l}$,
$X^{\prime}_{2}=X_{2}\setminus T_{l}$, and $X^{\prime}_{0}=X_{0}\cup X_{1}$.
By this construction, we have that $v_{1}(X^{\prime}_{1})>2\cdot v_{1}(X_{1})$
and $v_{2}(X^{\prime}_{2})\leq\frac{1}{2}\cdot v_{2}(X_{2})$; thus,

$\prod_{i\in N}v_{i}(X^{\prime}_{i})>\prod_{i\in N}v_{i}(X_{i}),$

which contradicts the fact that $\mathbf{X^{*}}$ is a Max-NSW allocation.

#### Case 2.

Otherwise, we have $\max\\{v_{1}(T_{1}),v_{1}(T_{2})\\}\leq 2\cdot
v_{1}(X_{1})$. Since

$v_{1}(T_{1})+v_{1}(T_{2})=v_{1}(T_{1}\cup T_{2})>\frac{11}{3}\cdot
v_{1}(X_{1}),$

we have

$\min\\{v_{1}(T_{1}),v_{1}(T_{2})\\}>\frac{5}{3}\cdot v_{1}(X_{1}).$

Pick an arbitrary $l\in\arg\min_{\ell\in\\{1,2\\}}c(T_{\ell})$. Since
$c(T_{1})+c(T_{2})\leq B_{1}$, we have $c(T_{l})\leq\frac{1}{2}\cdot B_{1}$.

We construct a new allocation by allocating all the items in $T_{l}$ to agent
$1$, along with a sufficiently valuable portion of items in $X_{1}$. To ensure
that the budget feasibility, we need the following result.

###### Claim 4.1

There exists $\hat{X}_{1}\subseteq X_{1}$ such that
$c(\hat{X}_{1})\leq\frac{1}{2}\cdot B_{1}$ and
$v_{1}(\hat{X}_{1})\geq\frac{1}{3}\cdot v_{1}(X_{1})$.

Proof:  If $c(X_{1})\leq\frac{1}{2}\cdot B_{1}$, we can let
$\hat{X}_{1}=X_{1}$. Note that under this case,
$v_{1}(\hat{X}_{1})=v_{1}(X_{1})$.

Now suppose $c(X_{1})>\frac{1}{2}\cdot B_{1}$. We create a set $T$ and let it
be an empty set initially. Then we add into $T$ items in $X_{1}$ one at a time
until $c(T)>\frac{1}{2}\cdot B_{1}$. Let $j$ be the last item added into $T$.
We have

$c(T)>\frac{1}{2}\cdot B_{1}\text{ and }c(T-j)\leq\frac{1}{2}\cdot B_{1}.$

Consider the partition of $X_{1}$ into three sets: $T-j$, $\\{j\\}$ and
$X_{1}\setminus T$. Note that all three sets have cost at most
$\frac{1}{2}\cdot B_{1}$. Let $\hat{X}_{1}$ be the set with maximum value
(under $v_{1}$) among $T-j$, $\\{j\\}$ and $X_{1}\setminus T$. Obviously, we
have $v_{1}(\hat{X}_{1})\geq\frac{1}{3}\cdot v_{1}(X_{1})$.

By the above claim, we can now construct a new allocation
$\mathbf{X}^{\prime}$ with $X^{\prime}_{i}=X_{i}$ for all $i\geq 3$,
$X^{\prime}_{1}=T_{l}\cup\hat{X}_{1}$, $X^{\prime}_{2}=X_{2}\setminus T_{l}$,
and $X^{\prime}_{0}=X_{0}\cup(X_{1}\setminus\hat{X}_{1})$. This allocation is
feasible since

$c(X^{\prime}_{1})=c(T_{l})+c(\hat{X}_{1})\leq\frac{B_{1}}{2}+\frac{B_{1}}{2}=B_{1}.$

By construction, we have that

$\displaystyle v_{1}(X^{\prime}_{1})=$ $\displaystyle
v_{1}(T_{l})+v_{1}(\hat{X}_{1})>\frac{5}{3}\cdot v_{1}(X_{1})+\frac{1}{3}\cdot
v_{1}(X_{1})=2\cdot v_{1}(X_{1}),$

and $v_{2}(X^{\prime}_{2})\geq\frac{1}{2}\cdot v_{2}(X_{2})$. Therefore

$\prod_{i\in N}v_{i}(X^{\prime}_{i})>\prod_{i\in N}v_{i}(X_{i}),$

which is a contradiction.

As we can see from the analysis, the improvement in the approximation ratio
comes mainly from the fact that when reallocating items in $T_{l}$ from
$X_{2}$ to $X_{1}$, we are able to keep a constant fraction of the items in
$X_{1}$ (as in Claim 4.1).

It is natural to expect that if we are able to obtain an even finer dissection
of $X_{1}$, we should be able to improve the approximation ratio even further.
Indeed, this is the case. We show that when all items are very small compared
with the budgets, the approximation ratio approaches $1/2$. While the idea is
clear, as we will show in the following section, to accomplish the analysis is
a highly non-trivial task.

###  4.2 Large Budget Case

Let $\kappa=\min_{i\in N,j\in M}\frac{B_{i}}{c_{j}}$. Without loss of
generality, assume that $\kappa$ is an integer; otherwise, we round $\kappa$
down to the nearest integer. In other words, it takes at least $\kappa$ items
to exhaust the budget of any agent.

###### Theorem 4.2

The Max-NSW allocation $\mathbf{X^{*}}$ is
$\left(\frac{1}{2}-\frac{5}{\kappa^{1/4}}\right)$-EF1, where
$\kappa=\min_{i\in N,j\in M}\frac{B_{i}}{c_{j}}$.

Observe that when $\kappa\rightarrow\infty$ then the approximation ratio (with
respect to EF1) approaches $1/2$.

Before we present the proof of Theorem 4.2, we first show that the $1/2$
approximation ratio is tight. In particular, we give an example with
arbitrarily large $\kappa$, for which a Max-NSW allocation is
$(\frac{1}{2}+O(\frac{1}{\kappa}))$-EF1.

###### Example 4.3

Let there be two agents $\\{1,2\\}$ with $B_{1}=B_{2}=\kappa$. Let there be
$2\kappa$ items $M=M_{1}\cup M_{2}$ with cost $1$, where
$M_{1}=\\{1,2,\ldots,\kappa\\}$ and
$M_{2}=\\{\kappa+1,\kappa+2,\ldots,2\kappa\\}$. Let the valuations be
$v_{1j}=1$ for all $j\in M_{1}$; $v_{1j}=2$ for all $j\in M_{2}$; $v_{2j}=0$
for all $j\in M_{1}$; $v_{2j}=2$ for all $j\in M_{2}$ (see below).

$j$ | 1 | $\ldots$ | $\kappa$ | $\kappa+1$ | $\ldots$ | $2\kappa$
---|---|---|---|---|---|---
$v_{1j}$ | 1 | $\ldots$ | 1 | 2 | $\ldots$ | 2
$v_{2j}$ | 0 | $\ldots$ | 0 | 2 | $\ldots$ | 2

Suppose that $x\leq\kappa$ items in $M_{2}$ are allocated to agent $2$ in a
Max-NSW allocation, then it is optimal to allocate the remaining $\kappa-x$
items in $M_{2}$ together with $x$ items in $M_{1}$ to agent $1$. The NSW is
thus given by

$v_{1}(X_{1})\cdot v_{2}(X_{2})=(2\kappa-x)\cdot 2x,$

which is maximized when $x=\kappa$. That is, $X_{1}=M_{1}$ and $X_{2}=M_{2}$.
Since for any $j\in X_{2}$,

$v_{1}(X_{2}-j)=2(\kappa-1)=\frac{2(\kappa-1)}{\kappa}\cdot v_{1}(X_{1}),$

the Max-NSW allocation is $\frac{\kappa}{2\kappa-1}$-EF1, and the
approximation ratio approaches $\frac{1}{2}$ when $\kappa\rightarrow\infty$.

###  4.3 Proof of Theorem 4.2

Next we prove Theorem 4.2. For ease of notation we let $k=\kappa^{1/4}$. Note
that it suffices to consider the case when $k>20$, as otherwise the theorem
follows from Theorem 3.1.

######  Definition 4.4 (Density)

Let the density of item $j\in M$ under the valuation of agent $i$ as
$\rho_{ij}=\frac{v_{ij}}{c_{j}}$.

We first prove the following lemma, which will be useful in the analysis.

###### Lemma 4.5

Given two sets of items $X$ and $Y$, both have cost at most $B$, and a
valuation function $v$, there exists a subset of items $Z\subseteq X\cup Y$
with $c(Z)\leq B$ and

$v(Z)\geq\left(1-\frac{c(Y)}{B}-\frac{1}{k^{4}}\right)\cdot v(X)+v(Y).$

Proof:  We prove by constructing the subset $Z$ satisfying the claimed
properties. In particular, we compute a subset $X^{\prime}\subseteq X$ with
$c(X^{\prime})\leq B-c(Y)$, and

$v(X^{\prime})\geq\left(1-\frac{c(Y)}{B}-\frac{1}{k^{4}}\right)\cdot v(X).$

Then the lemma follows immediately by setting $Z=X^{\prime}\cup Y$.

To ease the analysis, we assume without loss of generality that $c(X)=B$. If
$c(X)<B$ then imagine that we include into $X$ many items with $0$ value and
arbitrarily small cost until $c(X)=B$, which does not increase the value of
$X$. We construct $X^{\prime}$ by repeatedly removing an item in $X$ with the
smallest density (under valuation function $v$), until $c(X^{\prime})\leq
B-c(Y)$. Since each item has cost at most $\frac{B}{k^{4}}$ by definition of
$k$, the total cost of items removed in this procedure is at most
$c(Y)+\frac{B}{k^{4}}$. Since the items removed are among those with the
smallest density, their average density is at most the overall density of
items in $X$; the total value of items removed is at most

$\left(c(Y)+\frac{B}{k^{4}}\right)\cdot\frac{v(X)}{c(X)}=\left(\frac{c(Y)}{B}+\frac{1}{k^{4}}\right)\cdot
v(X),$

Thus we have

$\displaystyle
v(Z)=v(X^{\prime})+v(Y)\geq\left(1-\frac{c(Y)}{B}-\frac{1}{k^{4}}\right)\cdot
v(X)+v(Y),$

as claimed.

As before, we prove by contradiction, and assume the allocation is not
$(\frac{1}{2}-\frac{5}{k})$-EF1, say, between agents $1$ and $2$. We show that
this assumption leads to contradictions.

Let $T\subseteq X_{2}$ with $c(T)\leq B_{1}$ such that

$\displaystyle v_{1}(T-j^{*})>$
$\displaystyle\left(\frac{1}{2}-\frac{5}{k}\right)^{-1}\cdot
v_{1}(X_{1})=\left(2+\frac{20}{k-10}\right)\cdot v_{1}(X_{1}),$ (2)

where $j^{*}=\arg\max_{j\in T}v_{2j}$ is the item in $T$ with the maximum
value under the valuation of agent $2$.

Let $\hat{T}=T-j^{*}$. For each item $j\in\hat{T}$, we refer to
$v_{2j}/v_{2}(\hat{T})$ as the _contribution_ of item $j$ to set $\hat{T}$
under valuation of agent $2$. The total contribution of items in $\hat{T}$ is
$1$. Depending on the contributions of items, we partition $\hat{T}$ into a
set $T_{h}$ of _heavy items_ and a set $T_{l}$ of _light items_ :

$\displaystyle
T_{h}:=\left\\{j\in\hat{T}:\frac{v_{2j}}{v_{2}(\hat{T})}\geq\frac{1}{k^{3}}\right\\},\quad\text{
and }\quad T_{l}:=\hat{T}\setminus T_{h}.$

We first show that under the valuation of agent $1$, the contribution of heavy
items must be small.

###### Claim 4.2

For all $j\in T_{h}$, we have
$\frac{v_{1j}}{v_{1}(\hat{T})}<\frac{1}{2}\cdot\frac{v_{2j}}{v_{2}(\hat{T})}$.

Proof:  Suppose for the sake of contradiction that there exists $j\in T_{h}$
such that

$\frac{v_{1j}}{v_{1}(\hat{T})}\geq\frac{1}{2}\cdot\frac{v_{2j}}{v_{2}(\hat{T})}.$

We show that there exists an allocation (by reallocating item $j$) that
achieves a strictly larger NSW, which is a contradiction. Let
$c=\frac{v_{2}(\hat{T})}{v_{2j}}$. By definition of heavy item, we have $c\leq
k^{3}$. Consider the allocation obtained by moving item $j$ from $\hat{T_{h}}$
to $X_{1}$. Since $v_{2j}\leq v_{2j^{*}}$, we have

$\displaystyle v_{2}(X^{\prime}_{2})=$
$\displaystyle\left(1-\frac{v_{2j}}{v_{2}(X_{2})}\right)\cdot
v_{2}(X_{2})\geq\left(1-\frac{v_{2j}}{v_{2}(\hat{T})+v_{2j^{*}}}\right)\cdot
v_{2}(X_{2})\geq\left(1-\frac{1}{c+1}\right)\cdot v_{2}(X_{2}).$

Note that including $j$ into $X_{1}$ may result in a violation of the budget
constraint of agent $1$. To resolve this issue, we use Lemma 4.5 with
$B=B_{1}$, $v=v_{1}$, $X=X_{1}$ and $Y=\\{j\\}$, and let $X^{\prime}_{1}=Z$
(as specified in Lemma 4.5). Since item $j$ has cost
$c_{j}\leq\frac{B_{1}}{k^{4}}$, we have

$v_{1}(X^{\prime}_{1})\geq\left(1-\frac{2}{k^{4}}\right)\cdot
v_{1}(X_{1})+v_{1j}.$

Recall that by assumption of the proof we have

$v_{1j}\geq\frac{1}{2}\cdot
v_{1}(\hat{T})\cdot\frac{v_{2j}}{v_{2}(\hat{T})}=\frac{1}{2c}\cdot
v_{1}(\hat{T}).$

By inequality (2), we have

$\displaystyle v_{1}(X^{\prime}_{1})\geq$
$\displaystyle\left(1-\frac{2}{k^{4}}+\frac{1}{2c}\cdot\left(2+\frac{20}{k-10}\right)\right)\cdot
v_{1}(X_{1})$ $\displaystyle=$
$\displaystyle\left(1+\frac{1}{c}+\frac{10}{c(k-10)}-\frac{2}{k^{4}}\right)\cdot
v_{1}(X_{1})$ $\displaystyle>$ $\displaystyle\frac{c+1}{c}\cdot v_{1}(X_{1}),$

where the last inequality holds since $c\leq k^{3}$.

Hence, we have $v_{1}(X^{\prime}_{1})\cdot
v_{2}(X^{\prime}_{2})>v_{1}(X_{1})\cdot v_{2}(X_{2})$ and

$\prod_{i\in N}v_{i}(X^{\prime}_{i})>\prod_{i\in N}v_{i}(X_{i}),$

which is a contradiction.

Let $f=\frac{v_{2}(T_{l})}{v_{2}(\hat{T})}$ be the total contribution of light
items to $\hat{T}$. By the above claim we have

$\frac{v_{1}(T_{l})}{v_{1}(\hat{T})}=1-\frac{v_{1}(T_{h})}{v_{1}(\hat{T})}>1-\frac{1}{2}\cdot\frac{v_{2}(T_{h})}{v_{2}(\hat{T})}=\frac{1}{2}+\frac{f}{2}.$

In other words, under the valuation of agent $1$, the light items have a
larger total contribution to $\hat{T}$.

Next, we prove the following lemma. Roughly speaking, we can partition the
light items into $k$ sets with about the same cost and value.

###### Lemma 4.6

We can partition $T_{l}$ into $k$ sets such that each set $Y$ satisfies

$v_{2}(Y)\leq\left(\frac{f}{k}+\frac{4}{k^{3}}\right)\cdot
v_{2}(\hat{T}),\;c(Y)\leq\left(\frac{1}{k}+\frac{4}{k^{4}}\right)\cdot B_{1}.$

For continuity of presentation, we defer the proof of the above lemma to the
end of this section.

We partition $T_{l}$ into $k$ sets as specified in Lemma 4.6, then pick the
one most valuable to agent $1$ out of the $k$ sets, and reassign it to agent
$1$. Let $Y$ be the set chosen. Note that $Y$ satisfies

$\displaystyle v_{1}(Y)\geq\frac{1}{k}\cdot v_{1}(T_{l})\geq$
$\displaystyle\frac{1}{k}\left(\frac{1}{2}+\frac{f}{2}\right)\cdot
v_{1}(\hat{T})\geq\frac{1}{k}\left(\frac{1}{2}+\frac{f}{2}\right)\left(2+\frac{20}{k-10}\right)\cdot
v_{1}(X_{1}).$

After losing set $Y$, the remaining value of agent $2$ is

$\displaystyle
v_{2}(X^{\prime}_{2})=v_{2}(X_{2})-v_{2}(Y)\geq\left(1-\frac{f}{k}-\frac{4}{k^{3}}\right)\cdot
v_{2}(X_{2}),$ (3)

where the inequality holds by Lemma 4.6. After acquiring set $Y$, agent $1$
has the set of items $X^{\prime}_{1}=X_{1}\cup Y$, which might have a larger
cost than $B_{1}$. Similarly, we use Lemma 4.5, with $B=B_{1}$, $v=v_{1}$ and
$X=X_{1}$. Let $X^{\prime}_{1}=Z$ be the set specified in Lemma 4.6.

As a result, the bundle agent $1$ receives has value

$\displaystyle v_{1}(X^{\prime}_{1})$
$\displaystyle\geq\left(1-(\frac{1}{k}+\frac{5}{k^{4}})+\frac{1}{k}(\frac{1}{2}+\frac{f}{2})(2+\frac{20}{k-10})\right)\cdot
v_{1}(X_{1})$
$\displaystyle=\left(1+\frac{f}{k}+\frac{10(1+f)}{k(k-10)}-\frac{5}{k^{4}}\right)\cdot
v_{1}(X_{1})>\left(1+\frac{f}{k}+\frac{9}{k^{2}}\right)\cdot v_{1}(X_{1}),$
(4)

where in the last inequality we use $f\geq 0$ and $k\geq 20$.

Combining inequalities (4) and (3), we have

$\displaystyle\frac{v_{1}(X^{\prime}_{1})v_{2}(X^{\prime}_{2})}{v_{1}(X_{1})v_{2}(X_{2})}$
$\displaystyle>\left(1-\frac{f}{k}-\frac{4}{k^{3}}\right)\cdot\left(1+\frac{f}{k}+\frac{9}{k^{2}}\right)$
$\displaystyle=\left(1-(\frac{f}{k}+\frac{4}{k^{3}})^{2}+(\frac{9}{k^{2}}-\frac{4}{k^{3}})(1-\frac{f}{k}-\frac{4}{k^{3}})\right)$
$\displaystyle\geq\left(1-(\frac{f}{k}+\frac{4}{k^{3}})^{2}+\frac{5}{k^{2}}\right)>1.$

It follows that

$\prod_{i\in N}v_{i}(X^{\prime}_{i})>\prod_{i\in N}v_{i}(X_{i}),$

which is a contradiction.

###  4.4 Proof of Lemma 4.6

Proof of Lemma 4.6:  Let $S=c(T_{l})$ be the total cost of items in $T_{l}$.
Recall that $S\leq B_{1}$. We first show that we can partition the set $T_{l}$
_fractionally_ into $k$ sets $Y_{1},Y_{2},\ldots,Y_{k}$ with equal cost and
value. That is, for all $i\in[k]$, we have

$c(Y_{i})=\frac{1}{k}\cdot S\text{ and }v_{2}(Y_{i})=\frac{1}{k}\cdot
v_{2}(T_{l}).$ (5)

In general, obtaining such fractional partitioning is easy because we can
simply assign each $Y_{i}$ a $\frac{1}{k}$ fraction of every item in $T_{l}$.
However, this would result in too many fractional items. The key to our
analysis is to show that we can fractionally and evenly partition $T_{l}$ such
that each $Y_{i}$ contains at most $4$ fractional items. Given such a
fractional partitioning $(Y_{1},Y_{2},\ldots,Y_{k})$ of $T_{l}$, we round the
fractional items arbitrarily, e.g., assign the fractional item to the set
$Y_{i}$ containing it with the smallest $i$. Hence we obtain an integral
partition $(Y^{\prime}_{1},Y^{\prime}_{2},\ldots,Y^{\prime}_{k})$ of $T_{l}$.
Moreover, since each set $Y_{i}$ contains at most $4$ fractional items and
each (integral) item has cost at most $\frac{B_{1}}{k^{4}}$, we have

$\displaystyle c(Y^{\prime}_{i})\leq$ $\displaystyle
c(Y_{i})+4\cdot\frac{B_{1}}{k^{4}}=\frac{1}{k}\cdot S+\frac{4}{k^{4}}\cdot
B_{1}\leq\left(\frac{1}{k}+\frac{4}{k^{4}}\right)\cdot B_{1}.$

By definition of light items, each $j\in T_{l}$ has value
$v_{2j}<\frac{1}{k^{3}}\cdot v_{2}(\hat{T})$. Recall that $v_{2}(T_{l})=f\cdot
v_{2}(\hat{T})$, we have

$\displaystyle v_{2}(Y^{\prime}_{i})\leq$ $\displaystyle
v_{2}(Y_{i})+\frac{4}{k^{3}}\cdot v_{2}(\hat{T})=\frac{1}{k}\cdot
v_{2}(T_{l})+\frac{4}{k^{3}}\cdot
v_{2}(\hat{T})=\left(\frac{f}{k}+\frac{4}{k^{4}}\right)\cdot v_{2}(\hat{T}).$

Hence both conditions are satisfied. It remains to compute the sets
$Y_{1},Y_{2},\ldots,Y_{k}$.

We first introduce some notation for fractional sets. Each fractional item set
$F$ can be represented by a vector $\mathbf{y}\in[0,1]^{|T_{l}|}$, where
$\mathbf{y}=(y_{1},\ldots,y_{|T_{l}|})$ and $y_{j}\in[0,1]$ represents the
fraction of item $j\in T_{l}$ that is included in $F$. The cost of $F$ is
denoted by $c(F)=\sum_{j\in T_{l}}y_{j}$.

Given $T_{l}$ and $b\leq S=c(T_{l})$, a fractional item set $T_{l}[0,b]$ is
defined as follows. We initialize $T_{l}[0,b]$ to an empty set, and then
repeatedly include into this set a densest item from $T\setminus T_{l}[0,b]$
(under the valuation of agent $2$), until the cost of $T_{l}[0,b]$ will exceed
$b$ if we include the next such item, say item $j$, into $T_{l}[0,b]$; we then
include into $T_{l}[0,b]$ only a fraction of $j$ that will make
$c(T_{l}[0,b])=b$ (see Figure 1).

Figure 1: Illustrating example of $T_{l}[0,b]$, where each item is represented
as a rectangle with the height being its density and width being its cost. The
items are listed in descending order of their densities.

Equivalently, we describe the fractional item set $T_{l}[0,b]$ as a vector
$\mathbf{y}\in[0,1]^{T_{l}}$, where for each $j\in T_{l}$,

$y_{j}=\min\left\\{1,\
\frac{1}{c_{j}}\cdot\max\Big{\\{}0,b-\sum_{j^{\prime}:\rho_{2j^{\prime}}>\rho_{2j}}c_{j^{\prime}}\Big{\\}}\right\\}.$

Similarly, for each $0\leq a\leq b\leq S$ we define $T_{l}(a,b]$ to be the
fractional item set obtained by letting

$T_{l}(a,b]:=T_{l}[0,b]\setminus T_{l}[0,a].$

Next we construct the sets $Y_{1},Y_{2},\ldots,Y_{k}$. To construct $Y_{1}$,
we use a parameter $b_{1}\in[0,\frac{S}{k}]$ and let

$Y_{1}=T_{l}[0,b_{1}]\cup T_{l}\left(\frac{k-1}{k}\cdot S+b_{1},S\right].$ (6)

Note that for any $b_{1}\in[0,\frac{S}{k}]$, we have $c(Y_{1})=\frac{S}{k}$,
whereas the value $v_{2}(Y_{1})$ increases (weakly) with $b_{1}$. For
$b_{1}=0$, $Y_{1}=T_{l}\left(\frac{k-1}{k}\cdot S,S\right]$ contains the
fractional items in $T_{l}$ with the smallest densities; for
$b_{1}=\frac{S}{k}$, $Y_{1}=T_{l}\left[0,\frac{S}{k}\right]$ contains the
fractional items in $T_{l}$ with the largest densities. Hence, there exists a
value $b_{1}\in[0,\frac{S}{k}]$ which makes $v_{2}(Y_{1})=\frac{1}{k}\cdot
v_{2}(T_{l})$. We fix $b_{1}$ to this value and let $Y_{1}$ be the
corresponding set defined by Equation (6). Next we construct $Y_{2}$.

Note that after fixing $Y_{1}$, the remaining fractional item set is
$T_{l}\left(b_{1},\frac{k-1}{k}\cdot S+b_{1}\right]$, which has cost
$\frac{k-1}{k}\cdot S$ and value

$v_{2}(T_{l})-v_{2}(Y)=\frac{k-1}{k}\cdot v_{2}(T_{l}).$

In other words, the remaining items have average density exactly the same as
$\rho_{2}(T_{l})=\frac{v_{2}(T_{l})}{c(T_{l})}$. Thus we can construct $Y_{2}$
the same way we constructed $Y_{1}$: for $b_{2}\in[b_{1},\frac{S}{k}+b_{1}]$,
let

$Y_{2}=T_{l}(b_{1},b_{2}]\cup T_{l}\left(\frac{k-2}{k}\cdot
S+b_{2},\frac{k-1}{k}\cdot S+b_{1}\right].$

Similarly, for any $b_{2}$ we have $c(Y_{2})=\frac{S}{k}$, and the value
$v_{2}(Y_{2})$ increases with $b_{2}$. We can find a value for $b_{2}$ that
makes $v_{2}(Y_{2})=\frac{1}{k}\cdot v_{2}(T_{l})$ and let $Y_{2}$ be the
corresponding set defined by Equation (6).

Figure 2: Partitioning $T_{l}$ into disjoint fractional item sets: an example
with $k=3$.

By repeating the above procedure, we can construct the subsequent sets
$Y_{3},\dots,Y_{k}$ and obtain $k$ fractional sets with the equal cost and
value (see Figure 2). Note that each fractional set $Y_{i}$ contains at most
four fractional items, one for each interval boundary in Equation (6). Hence,
the sets $Y_{1},\ldots,Y_{k}$ satisfy the claimed properties.

##  5 Discussion and Future Directions

We showed that in the presence of budget constraints a Max-NSW allocation may
not be EF1 but achieves a constant approximation of EF1. The tight
approximation ratio is $1/4$ and in the case of large budgets, the ratio
improves with the budget-cost ratio and converges to $1/2$ when this ratio
goes to infinity. Our results complement previous work that focused on the
setting without budget constraint.

There are several directions for future work. First, our results actually
imply that in a budget-feasible setting, a $1/4$-EF1 allocation always exists
and is compatible with Pareto optimality, but it is not known whether an exact
EF1 allocation always exists or not and this appears to be a non-trivial
problem. Second, the computation of maximum NSW in our setting is an
interesting question which we did not study in this paper. Indeed, an APX-
hardness for the complexity of this problem can be readily established since
the setting without budget can be seen as a special case of our setting (where
every agent has budget $c(M)$). Thus, an natural task is to design efficient
approximation algorithms. Theorem 3.1 can be extended to show that an
$\alpha$-approximation of the Max-NSW is also $\frac{\alpha}{4}$-EF1. Hence an
approximation algorithm for Max-NSW would also compute an approximate EF1
allocation. However, in the large budget case, an $\alpha$-approximation of
the Max-NSW is not necessarily
$\alpha\cdot\left(\frac{1}{2}-\frac{5}{\kappa^{1/4}}\right)$-EF1 due to the
following example.

###### Example 5.1

Fix an arbitrarily large integer $\kappa$. Suppose there are two agents with
capacity $B_{1}=B_{2}=\kappa$, and $2\kappa$ items of size $1$. Let the first
$\kappa$ items $M_{1}=\\{1,2,\ldots,\kappa\\}$ have value $1$ and the
remaining $\kappa$ items $M_{2}=\\{\kappa+1,\kappa+2,\ldots,2\kappa\\}$ have
value $0.2$. Obviously the optimal Nash social welfare is $0.36\kappa^{2}$.
Now consider the allocation $\mathbf{X}=(M_{1},M_{2})$. The Nash social
welfare is $0.2\kappa^{2}$, which implies an approximation ratio $\alpha>0.5$.
However, the allocation is not $c$-EF1 for any
$c>\frac{1}{5}+\frac{1}{5(\kappa-1)}$.

Finally, while we focus on EF in this paper, it would also be interesting to
consider other fairness notions such as proportionality and maximin share
fairness and study whether a Max-NSW allocation provides any fairness
guarantee under these notions.

## Acknowledgement

The authors thank Edith Elkind, Georgios Birmpas, Warut Suksompong, and
Alexandros Voudouris for helpful discussions at the early stage of this work.

## References

  * [1] G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris.  Maximum nash welfare and other stories about EFX.  In IJCAI, pages 24–30. ijcai.org, 2020.
  * [2] S. Barman, S. K. Krishnamurthy, and R. Vaish.  Finding fair and efficient allocations.  In EC, pages 557–574. ACM, 2018.
  * [3] A. Biswas and S. Barman.  Fair division under cardinality constraints.  In IJCAI, pages 91–97. ijcai.org, 2018.
  * [4] S. Brânzei, V. Gkatzelis, and R. Mehta.  Nash social welfare approximation for strategic agents.  In EC, pages 611–628. ACM, 2017.
  * [5] I. Caragiannis, N. Gravin, and X. Huang.  Envy-freeness up to any item with high nash welfare: The virtue of donating items.  In EC, pages 527–545. ACM, 2019.
  * [6] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang.  The unreasonable fairness of maximum nash welfare.  In EC, pages 305–322. ACM, 2016.
  * [7] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang.  The unreasonable fairness of maximum nash welfare.  ACM Trans. Economics and Comput., 7(3):12:1–12:32, 2019.
  * [8] B. R. Chaudhury, T. Kavitha, K. Mehlhorn, and A. Sgouritsa.  A little charity guarantees almost envy-freeness.  In SODA, pages 2658–2672. SIAM, 2020.
  * [9] R. Cole, N. R. Devanur, V. Gkatzelis, K. Jain, T. Mai, V. V. Vazirani, and S. Yazdanbod.  Convex program duality, fisher markets, and nash social welfare.  In EC, pages 459–460. ACM, 2017.
  * [10] R. Cole and V. Gkatzelis.  Approximating the nash social welfare with indivisible items.  In STOC, pages 371–380. ACM, 2015.
  * [11] V. Conitzer, R. Freeman, and N. Shah.  Fair public decision making.  In EC, pages 629–646. ACM, 2017.
  * [12] A. Darmann and J. Schauer.  Maximizing nash product social welfare in allocating indivisible goods.  Eur. J. Oper. Res., 247(2):548–559, 2015.
  * [13] N. R. Devanur, K. Jain, B. Sivan, and C. A. Wilkens.  Near optimal online algorithms and fast approximation algorithms for resource allocation problems.  In EC, pages 29–38. ACM, 2011.
  * [14] B. Fain, K. Munagala, and N. Shah.  Fair allocation of indivisible public goods.  In EC, pages 575–592. ACM, 2018.
  * [15] J. Feldman, M. Henzinger, N. Korula, V. S. Mirrokni, and C. Stein.  Online stochastic packing applied to display ad allocation.  In ESA (1), volume 6346 of Lecture Notes in Computer Science, pages 182–194. Springer, 2010.
  * [16] M. Kaneko and K. Nakamura.  The nash social welfare function.  Econometrica: Journal of the Econometric Society, pages 423–435, 1979.
  * [17] T. Kesselheim, K. Radke, A. Tönnis, and B. Vöcking.  Primal beats dual on online packing lps in the random-order model.  In STOC, pages 303–312. ACM, 2014.
  * [18] E. Lee.  Apx-hardness of maximizing nash social welfare with indivisible items.  Inf. Process. Lett., 122:17–20, 2017.
  * [19] P. McGlaughlin and J. Garg.  Improving nash social welfare approximations.  J. Artif. Intell. Res., 68:225–245, 2020.
  * [20] M. Molinaro and R. Ravi.  Geometry of online packing linear programs.  In ICALP (1), volume 7391 of Lecture Notes in Computer Science, pages 701–713. Springer, 2012.
  * [21] J. F. Nash Jr.  The bargaining problem.  Econometrica: Journal of the econometric society, pages 155–162, 1950.
  * [22] N. Nguyen, T. T. Nguyen, M. Roos, and J. Rothe.  Computational complexity and approximability of social welfare optimization in multiagent resource allocation.  Auton. Agents Multi Agent Syst., 28(2):256–289, 2014.
  * [23] T. T. Nguyen and J. Rothe.  Minimizing envy and maximizing average nash social welfare in the allocation of indivisible goods.  Discret. Appl. Math., 179:54–68, 2014.
  * [24] S. Ramezani and U. Endriss.  Nash social welfare in multiagent resource allocation.  In AMEC/TADA, volume 59 of Lecture Notes in Business Information Processing, pages 117–131. Springer, 2009.

##  Appendix A Sub-additive Evaluation Functions

While we assume that the valuation functions are additive throughout this
paper, Theorem 3.1 can be extended to sub-additive valuation functions as
well. A valuation function $v:2^{M}\rightarrow\mathbb{R}^{+}\cup\\{0\\}$ is
sub-additive if for any disjoint sets $S,T\subseteq M$, we have

$v(S)+v(T)\geq v(S\cup T).$

######  Theorem A.1 (Sub-additive Valuations)

When all agents have sub-additive valuation functions, a Max-NSW allocation
$\mathbf{X^{*}}$ is $\frac{1}{4}$-EF1 and PO.

Proof:  The proof is almost identical to that of Theorem 3.1, and the only
difference is here we provide a more general way to partition $T$ into
$T_{1}$, $T_{2}$ and $\\{t\\}$ such that for some $i\in\\{1,2\\}$,

$\displaystyle v_{2}(T_{i})\leq v_{2}(T_{3-i})\leq v_{2}(T_{i}+t).$ (7)

Let $T^{\prime}_{1}$ and $T^{\prime}_{2}$ be the two sets returned by
Algorithm 1 on inputs $T$ and $v_{2}$. Then we have
$v_{2}(T^{\prime}_{1})>v_{2}(T^{\prime}_{2})$. Moreover, for any $t\in
T^{\prime}_{1}$, it holds that $v_{2}(T^{\prime}_{1}-t)\leq
v_{2}(T^{\prime}_{2}+t)$. Let $t$ be an arbitrary item in $T^{\prime}_{1}$;
let $T_{1}=T^{\prime}_{1}-t$, and $T^{\prime}_{2}=T_{2}$. Then $T_{1}$,
$T_{2}$ and $\\{t\\}$ satisfy (7).

1 Input: A set of items $T$ and a sub-additive valuation $v$.

2Initialize: $T_{1}=T$ and $T_{2}=\emptyset$.

3 while  _there exists $e\in T_{1}$ such that $v(T_{1}-e)>v(T_{2}+e)$_ do

4 $T_{1}=T_{1}-e$ and $T_{2}=T_{2}+e$.

5

Output: A partition of $T=(T_{1},T_{2})$.

Algorithm 1 Partioning $T$.


# How Lightweight Can a Vision Transformer Be

Jen Hong Tan
Data Science and Artificial Intelligence Lab (DSAIL)
Health Services Research Unit
Singapore General Hospital

###### Abstract

In this paper, we explore a strategy that uses Mixture-of-Experts (MoE) to
streamline, rather than augment, vision transformers. Each expert in an MoE
layer is a SwiGLU feedforward network, where $\mathbf{V}$ and $\mathbf{W_{2}}$
are shared across the layer. No complex attention or convolutional mechanisms
are employed. Depth-wise scaling is applied to progressively reduce the size
of the hidden layer and the number of experts is increased in stages. Grouped
query attention is used. We studied the proposed approach with and without
pre-training on small datasets and investigated whether transfer learning
works at this scale. We found that the architecture is competitive even at a
size of 0.67M parameters.

##  1 Introduction

In real-world applications of computer vision, such as edge intelligence,
small and performant models are still preferred to overcome computational
challenges [1]. Vision Transformers (ViTs) [2] have achieved remarkable
results, but their performance drops significantly when the model size and
dataset are small [3]. Consequently, there are studies investigating
lightweight vision transformers that perform well on mid-size datasets. Almost
all of these studies either use new types of attention blocks [4, 5] or
integrate convolutional mechanisms [6] into their architectures.

On the other hand, Tan [7] has shown that by employing Masked Auto-Encoder
(MAE) [8] as a pre-training strategy, it is possible to get ViT to learn
effectively from small datasets. In that work, the ViT consists of 12
transformer encoder layers, each containing a multi-head attention component
and a feedforward network. The feedforward network consists of two linear
layers: the first expands the output to twice, rather than four times, the
embedding size, and the second reduces the output back to the embedding size.
To further lighten the model, reducing the expanded output size in the middle
of the feedforward network can help, but excessive reduction can negatively
affect model performance.

With these considerations in mind, we designed an architecture that uses
Mixture-of-Experts (MoE) [9] to streamline vision transformers. In our
architecture, each expert in a MoE layer is formed by a SwiGLU [10]
feedforward network. By design, SwiGLU is heavier in terms of parameters
compared to a typical multi-layer perceptron. However, with several experts in
a MoE layer, we are able to make the hidden size in SwiGLU smaller than the
embedding size without negatively affecting model performance. Furthermore, we
share 2 out of the 3 linear transformations in each SwiGLU across the layer.
This helps to significantly lower the parameter count while maintaining the
strength of MoE. Beyond that, to further reduce the number of parameters, we
progressively increase the number of experts in the MoE in stages, while
linearly reducing the hidden size by depth, borrowing the idea from depth-wise
scaling [11]. Lastly, we use grouped query attention [12] to keep the
parameter count low. Source code will be provided in near future.

##  2 Method

Our proposed approach consists of two parts: mLiT and mmLiT. mLiT is a
mixture-of-experts based Lightweight vision Transformer, and mmLiT is a mLiT
pre-trained and fine-tuned using masked auto-encoder pretraining strategy.

###  2.1 mLiT

Similar to the original ViT [2], we start by dividing each image into non-
overlapping patches. Each of these patches is linearly transformed into a set
of embeddings, augmented by learnable positional embeddings. The processed
embeddings go through a series of MoE-based transformer encoder layers. Figure
1 shows the overall structure of our transformer encoder layer .

Figure 1: The structure of an MoE based transformer encoder layer. Each expert
is a SwiGLU feedforward network. $b$ stands for batch size, $n$ for the number
of embeddings and $m$ for embedding size. In this layer there are $t$ number
of experts Figure 2: The working of MoE assuming the input is a vector. In
this example, expert 1 and expert 3 receive the input as directed by the
gating network

####  2.1.1 Grouped Query Attention (GQA)

Grouped query attention divides query heads into $G$ groups, with each group
sharing a single key head and value head. For instance, GQA-1, with a single
group, is equivalent to multi-query attention (MQA); while GQA-$H$, with
groups equal to the number of heads ($H$), is equivalent to multi-head
attention (MHA). An intermediate number of groups results in a model that is
higher quality than MQA but faster than MHA [12], providing a favorable trade-
off between performance and memory bandwidth.

####  2.1.2 Mixture of Experts (MoE)

A single Mixture-of-Experts layer comprises $t$ number of expert networks
$E_{1},E_{2},\cdots,E_{t}$, with a gating network $G$ that directs each input
vector/embedding to the relevant expert(s) in the layer. For each vector or
embedding, the output of $G$ is a sparse $t$-dimensional vector. Figure 2
shows an overview of the working of MoE when the input is a vector.

Let’s denote a vector/embedding by $x$, the output of the $i$-th expert by
$E_{i}(x)$, and the $i$-th component of the output of the gating network
$G(x)$ by $G(x)_{i}$. The output $y$ of the MoE is given by:

$y=\sum_{i=1}^{t}G(x)_{i}E_{i}(x)\vspace{0.8em}$ (1)

As the output $G(x)$ is sparse, in MoE, no computation is performed on the
$j$-th expert when $G(x)_{j}=0$. In many applications, however, the input to
the layer is generally of shape $(b,n,m)$, where $b$, $n$, and $m$ denote
batch size, the number of embeddings and the embedding size, respectively.
Therefore, it is common to reshape the input tensor into 2D [13] before the
MoE layer. Figure 3 shows the workflow of the actual implementation of MoE.

Figure 3: The actual implementation of MoE. Unlike the case when the input is
just a vector, when $b\cdot n$ embeddings go into the layer, almost all the
expert networks will receive some embeddings sent by the dispatcher

Noisy Top-K Gating Network. We follow the proposal by Shazeer et. al. [9] that
adds sparsity and noise to a softmax gating mechanism. Assume a reshaped input
tensor $\mathbf{x}$ with a shape $(b\cdot n,m)$ and two trainable weight
matrices $\mathbf{W}_{g}$ and $\mathbf{W}_{noise}$ , both of shape $(m,t)$,
where $t$ is the total number of experts in the layer and $k$ is the number of
expert(s) to be selected. The output of the gating network is given by

$G(\mathbf{x})=\mathrm{Softmax}_{k}\left(H(\mathbf{x})\right)$ (2)

where

$H(\mathbf{x})=\mathbf{x}\mathbf{W}_{g}+\mathrm{randn\\_like({\mathbf{x}\mathbf{W}_{g}}})\odot\mathrm{Softplus}\left(\mathbf{x}\mathbf{W}_{noise}\right)\vspace{0.8em}$
(3)

$\odot$ denotes the element-wise product. $\mathrm{randn\\_like}$ generates a
tensor filled with random numbers from a normal distribution with mean 0 and
variance 1, and the shape of the tensor is equal to the shape of the output
from $\mathbf{x}\mathbf{W}_{g}$. $\mathrm{Softmax}_{k}$ applies softmax (row-
wise) only on the top $k$ elements, with the rest set to 0 in the output. The
equation below illustrates how $\mathrm{Softmax}_{k}$ works when $k$ is 2 and
$t$ (the number of experts) is 4:

$\mathrm{Softmax}_{k}\left(\left[\begin{array}[]{rrrr}4.4742&-5.6365&6.8226&0.9960\\\
3.5298&2.3049&1.2113&-1.3946\\\ -2.2414&0.3925&1.6676&-1.9253\\\
\end{array}\right]\right)=\begin{bmatrix}0.0872&0.0000&0.9128&0.0000\\\
0.7729&0.2271&0.0000&0.0000\\\ 0.0000&0.2184&0.7816&0.0000\\\
\end{bmatrix}\vspace{0.8em}$ (4)

Losses for MoE. To encourage all experts to have equal importance, two loss
functions are introduced: load balancing loss and importance loss. To
calculate load balancing loss, we first determine the following probability by

$P(\mathbf{x})=\Phi\left(\frac{\mathbf{x}\mathbf{W}_{g}-\Psi(H(\mathbf{x}))}{\mathrm{Softplus}(\mathbf{x}\mathbf{W}_{noise})}\right)\vspace{0.8em}$
(5)

where $\Phi$ is the cumulative distribution function of a standard normal
distribution. To calculate the output of $\Psi$, we let $\mathbf{H}$ denote
the output of $H(\mathbf{x})$, which has a shape of $(b\cdot n,t)$, with each
element in $\mathbf{H}$ denoted by $h_{r,c}$ . Furthermore, we let
$\mathbf{H}_{r}$ denote a row by index $r$ in $\mathbf{H}$. Similarly,
$\psi_{r,c}$ denotes each element in the output of $\Psi(H(\mathbf{x}))$. If
we let $l^{k}_{r}$ and $l^{k+1}_{r}$ denote the $k^{th}$ and $k+1^{th}$
largest values respectively for a row $r$ in $\mathbf{H}$,
$l^{k}_{r}>l^{k+1}_{r}$, then

$\psi_{r,c}=\left\\{\begin{array}[]{ll}l^{k+1}_{r}\mbox{ in
}\mathbf{H}_{r}&\mbox{ if }h_{r,c}\geq l^{k}_{r}\\\ l^{k}_{r}\mbox{ in
}\mathbf{H}_{r}&\mbox{ if }h_{r,c}<l^{k}_{r}\\\ \end{array}\right.$ (6)

where $k$ is the amount of expert(s) to be selected in the layer. As an
example, assume we have

$\mathbf{H}=\left[\begin{array}[]{rrrr}4.4742&-5.6365&6.8226&0.9960\\\
3.5298&2.3049&1.2113&-1.3946\\\ -2.2414&0.3925&1.6676&-1.9253\\\
\end{array}\right]\vspace{0.8em}$ (7)

and $k$ is 2, then for each row in $\mathbf{H}$ (with row index starting from
0), we have

$\begin{array}[]{crr}\hline\cr\mbox{row}&k^{th}\mbox{ largest}&k+1^{th}\mbox{
largest}\\\ \hline\cr 0&4.4742&0.9960\\\ 1&2.3049&1.2113\\\
2&0.3925&-1.9253\\\ \hline\cr\end{array}\vspace{1em}$ (8)

The output of $\Psi$ is

$\Psi(\mathbf{H})=\left[\begin{array}[]{rrrr}0.9960&4.4742&0.9960&4.4742\\\
1.2113&1.2113&2.3049&2.3049\\\ 0.3925&-1.9253&-1.9253&0.3925\\\
\end{array}\right]\vspace{0.8em}$ (9)

Lastly, with the probability calculated, the load balancing loss is given by:

$L_{load}(\mathbf{x})=w_{load}\times\mathrm{CV}\left(\mathrm{sum}_{0}(P(\mathbf{x}))\right)\vspace{0.8em}$
(10)

where $w_{load}$ is a hand-tuned scaling factor, $\mathrm{CV}$ is the function
to calculate coefficient of variation for the input, and $\mathrm{sum}_{0}$
performs column-wise summation on $P(\mathbf{x})$.To determine importance
loss, we simply do

$L_{importance}=w_{importance}\times\mathrm{sum}_{0}(G(\mathbf{x}))\vspace{0.8em}$
(11)

and the total loss is

$L=L_{importance}+L_{load}\vspace{0.8em}$ (12)

In our implementation, we set $w_{importance}=w_{load}=1\times 10^{-2}$.

SwiGLU. Each expert in a MoE layer is a SwiGLU FeedForward Network (FFN).
Assume we have a tensor $\mathbf{x}$ of shape $(n,m)$, where $n$ is the number
of embeddings and $m$ is the embedding size, we define $\mathbf{W},\mathbf{V}$
and $\mathbf{W_{2}}$ of shape $(m,d_{h})$, $(m,d_{h})$ and $(d_{h},m)$
respectively. $d_{h}$ is the hidden size. The output of the network is given
by:

$\mathrm{FFN_{SwiGLU}}(\mathbf{x})=\left(\mathrm{silu}\left(\mathbf{xW}\right)\odot\left(\mathbf{xV}\right)\right)\mathbf{W}_{2}\vspace{0.8em}$
(13)

Biases are omitted in the above for $\mathbf{W},\mathbf{V}$ and
$\mathbf{W_{2}}$. $\mathrm{silu}$ is the swish function:

$\mathrm{silu}(x)=x*\sigma(x)\vspace{0.8em}$ (14)

where $\sigma(x)$ is the logistic sigmoid. Dropout is applied on the output of
SwiGLU FFN.

In mLiT, $\mathbf{V}$ and $\mathbf{W_{2}}$ and their corresponding biases in
each expert are shared in a MoE layer.

####  2.1.3 Depth-wise Scaling

Our vision transformer does not have a fixed hidden size $d_{h}$ across the
transformer encoder layers. Instead, the hidden size is linearly reduced from
the first layer to the last layer. Let $d^{\mathrm{first}}_{h}$ and
$d^{\mathrm{last}}_{h}$ denote the hidden size of the first and the last layer
respectively, the hidden size of any layer is given by

$l^{i}_{h}=\left\lfloor\frac{(L_{E}-1)-i}{L_{E}-1}\left(d^{\mathrm{first}}_{h}-d^{\mathrm{last}}_{h}\right)\right\rfloor+d^{\mathrm{last}}_{h}$
(15)

where $L_{E}$ is the total number of the transformer encoder layers,
$\lfloor\cdot\rfloor$ is floor operator, and $i$ is a layer index starting
from 0.

Furthermore, the number of experts in mLiT is increased at different stages,
specifically from 3 to 5 after every 3, 4, or 5 layers, depending on the model
size. See Figure 4 for more detail.

Figure 4: The overall architecture of mLiT. The linear transformation and
positional embeddings before the first layer are not included in the
illustration. $b$ stands for batch size, $n$ for the number of embeddings and
$m$ for embedding size. The input and the output embedding size of each SwiGLU
FFN expert are equal to the embedding size $m$. The model in this figure has 9
MoE based transformer encoder layers, with the number of experts increased by
1 at layer 3 and layer 6. $d^{\mathrm{first}}_{h}$ and $d^{\mathrm{last}}_{h}$
are 81 and 27, respectively. The hidden size at each layer is calculated using
Equation 15.

###  2.2 mmLiT

In mmLiT, we apply masked auto-encoder on mLiT. We follow strictly the process
outlined in [7], which is based on the original MAE paper [8]. The masking
ratio is set to 0.75. However, unlike in [7], we did not incorporate a
separable learnable positional embeddings at the decoder’s input (See Figure
5). Similar to [7], we compute the loss of the auto-encoder as a sum of the
loss on masked patches and an additional, discounted loss on unmasked patches.
The total loss is given by

$\mathrm{Loss}=\mathrm{MSE}_{\mathrm{masked}}+\alpha\cdot\mathrm{MSE}_{\mathrm{unmasked}}+\beta\cdot
L$ (16)

where $\alpha$ denotes the discounting factor, $\beta$ is the loss coefficient
for MoE. $L$ is calculated from Equation 12.

Figure 5: The architecture of mmLiT. $b$, $m$ and $p$ stand for batch size,
embedding size and patch size, respectively. $n_{E}$ and $n_{D}$ are the
number of embeddings/patches at the encoder and decoder respectively.
$n_{E}+n_{D}=n$. $L_{E}$ is the total number of MoE transformer encoder layers
at encoder; $L_{D}$ is the total number the layers at decoder.

##  3 Experimental Setup

We investigate the performance of mLiT and mmLiT at three different sizes: S,
XS and XXS. Table 1 shows the details of the encoder of each model, and Table
2 for decoder. For mmLiT, we perform self-supervised pre-training on the
Cifar100 [14] training datasets and fine-tune on Cifar100, Cifar10[14],
Flowers102 [15] and Svhn [16]. Additionally, we conduct supervised learning
(without any pre-training) on the aforementioned four datasets.

The input image to the models has a size of 36 x 36, slightly larger than the
original 32 x 32 dimensions of these datasets (except Flowers102, which is
much larger and varied) . This results in each image being divided into 144
patches, given the patch size of 3 x 3. Similar to [7], an auxiliary dummy
patch is added to each image during both the pre-training and fine-tuning
phases. This dummy patch, which contains zero values for all elements, is
appended as the 145th patch for classification purposes.

Table 1: Configurations for various sizes of mLiT Configuration | S | XS | XXS
---|---|---|---
Embedding size | 144 | 128 | 108
No. of layers ($L_{E}$) | 15 | 12 | 9
Hidden size | 72-144 | 32-96 | 27-81
No. of Attn. heads | 8 | 8 | 6
No. of Attn. groups | 4 | 4 | 3
No. of experts | 3-5 | 3-5 | 3-5
k | 2 | 2 | 2
No. of stages | 3 | 3 | 3
No. of parameters | 2.36M | 1.21M | 0.66M
Dropout rate @ SwiGLU | 0.1 | 0.1 | 0.1
Table 2: Configurations for decoder in mmLiT Configuration |  S,XS,XXS
---|---
Embedding size | 108
No. of layers ($L_{D}$) | 4
Hidden size | 72
No. of Attn. heads | 6
No. of Attn. groups | 3
No. of experts | 3
k | 2
No. of parameters | 0.34M
Dropout rate @ SwiGLU | 0.1

All linear layers within the MoE based transformer encoder layers include
bias. However, we exclude bias from other linear projection layers in both the
encoder and decoder. For initializing weights and biases across all layer
types, we rely on the default methods provided by Pytorch. The same applies to
our approach to layer normalization [17], where we use Pytorch’s default
setup.

###  3.1 Pre-training

mmLiT-S, mmLiT-XS, and mmLiT-XXS were pre-trained on Cifar100 for 4000, 6000
and 8000 epochs, respectively. We employed the AdamW optimizer [18] with a
weight decay set at 0.05. The initial 5% of the total epochs were designated
for warm-up [19]. We followed this with a cosine decay schedule [20] for the
learning rate and adhered to the linear learning rate scaling rule with a base
learning rate of $3e-4$ [19, 8]:

$\mathrm{lr}=\mathrm{base\\_lr}\times\mathrm{batch\\_size}/256$ (17)

See Table 3 for more details.

Table 3: Parameters and configuration for pre-training Configuration | Value
---|---
Optimizer | AdamW
Weight decay | 0.05
Base learning rate | $3\times 10^{-4}$
Learning rate schedule | Cosine decay
Warm-up epochs | 200 (S), 300 (XS), 400 (XXS)
Batch size | 840 (S), 1280 (XS, XXS)
Horizontal flipping | $p=0.5$
Random resized cropping | $[0.6,1]$
Color normalization | $\mathrm{mean}=0.5,\mathrm{std}=0.5$
Discounting factor ($\alpha$) | 0.1
MoE loss coefficient ($\beta$) | 0.5

###  3.2 Fine-tuning

For each pre-trained model, we conducted two sets of fine-tuning experiments.
First, we fine-tuned the models pre-trained on Cifar100 for Cifar100
classification over 300 epochs. Second, we evaluated the transfer learning
capabilities of the models by fine-tuning each one on Cifar100, Cifar10,
Flowers102, and SVHN for 100 epochs. Table 4 shows the configuration for the
first set of fine-tuning, and Table 5 shows the deviations in configurations
with respect to Table 4 for the second set of fine-tuning.

Additionally, we evaluated the performance of various sizes of mLiT models
(trained from scratch with only supervised learning). Table 6 shows the
deviations in configurations for supervised learning on mLiT on the four
datasets. We adhere to the linear learning rate scaling rule (Eq. 16) for all
fine-tunings and supervised learning. All pre-trainings and fine-tunings were
done using mixed precision (torch.float16).

Table 4: Hyperparameters for the first set of fine-tuning Hyperparameter | Value
---|---
Optimizer | AdamW
Weight decay | 0.05
Base learning rate | $5\times 10^{-3}$
Learning rate schedule | Cosine decay
Layer-wise decay | 0.9
Total epochs | 300
Warm-up epochs | 20
Batch size | 448
Horizontal flipping | $p=0.5$
Random resized cropping | $[0.8,1]$
AutoAugment | Policy for Cifar10
Color normalization | $\mathrm{mean}=0.5,\mathrm{std}=0.5$
Table 5: Hyperparameters deviations for the second set of fine-tuning. The learning rate is in $10^{-3}$. Hyperparameter | Flowers102 | Svhn | Cifar10 | Cifar100
---|---|---|---|---
Batch size | 16 | 256 | 256 | 128
Learning rate | 10 | 2.5 | 2.5 | 5
Layer-wise decay | 0.9 | 0.9 | 0.8 | 0.9
Warm-up epoch | 10 | 10 | 5 | 5
AutoAugment policy | Cifar10 | Svhn | Cifar10 | Cifar10
Table 6: Hyperparameters deviations for supervised learning on mLiT across four datasets. The learning rate is in $10^{-3}$. Hyperparameter | Flowers102 | Svhn | Cifar10 | Cifar100
---|---|---|---|---
Batch size | 16 | 256 | 256 | 128
Learning rate | 10 | 1 | 1 | 2
Layer-wise decay | 1 | 1 | 1 | 1
Warm-up epoch | 10 | 10 | 5 | 5
AutoAugment policy | Cifar10 | Svhn | Cifar10 | Cifar10

##  4 Result

###  4.1 On Pre-Training

Figure 6 presents the pre-training losses for various sizes of mmLiT. The
reductions in training losses exhibit approximately a log-linear relationship
when plotted on logarithmic scales for both the x-axis (epochs) and y-axis
(loss values). This indicates an exponential decrease in losses across epochs.

mmLiT-S exhibited the lowest loss, reaching 0.020404 at epoch 4000. mmLiT-XS
and mmLiT-XXS achieved losses of 0.021051 and 0.021514 at epochs 6000 and
8000, respectively. The pre-training of mmLiT-S was notably stable, as
evidenced by the minimal variability in its training loss. In contrast, the
training losses for mmLiT-XS and mmLiT-XXS showed greater variability and more
frequent, pronounced spikes, particularly noticeable after epoch 1000.

Figure 6: Pre-training losses for mmLiT-S,mmLiT-XS, and mmLiT-XXS. The pre-
training of mmLiT-S was the most stable, with minimal variability. This can be
observed by the thickness of the curves.

###  4.2 On Fine-Tuning

Table 7 compares the performances of models with similar sizes, all trained or
fine-tuned over 300 epochs. mmLiT-S achieves an accuracy nearly 1% higher than
Mae-ViT-C100, despite having only two-thirds the parameters. mmLiT-XS, which
is one-third the size of Mae-ViT-C100, exhibits a performance only 1.5% lower.
More interestingly, mmLiT-XXS, with just 18% of the parameters of Mae-
ViT-C100, remains competitive, trailing by only 3.3% in accuracy. Furthermore,
mmLiT-XXS slightly outperforms ResNet56, even though ResNet56 has 18% more
parameters.

Table 8 illustrates the transfer learning capabilities of the models pre-
trained only on Cifar100, with reference to the results reported from [21]. It
can be seen that mmLiT is competitive even at a scale of 0.67M parameters,
where ViT-T+SSAT is almost 9 times larger, and the rests are at least 30 times
larger than mmLiT-XXS. Furthermore, with the exception of CVT-13, which has
convolutions in the architecture, mLiT always performs better than vanilla ViT
and Swin-T even at the smallest scale on Cifar100, Cifar10 and Svhn.
Flowers102 is a fine-grained classification dataset, so it is no surprise that
mLiT is not competitive at an image size of 36 x 36.

Table 7: Comparison of Top-1 validation accuracy Model | Cifar100 | # Params
---|---|---
Convolutional Networks (Designed for CIFAR)
ResNet56 [22] | 74.81% | 0.85 M
ResNet110[22] | 76.63% | 1.73 M
Vision Transformers[23]
ViT-12/16 | 57.97% | 85.63 M
ViT-Lite-7/16 | 52.87% | 3.89 M
ViT-Lite-7/8 | 67.27% | 3.74 M
ViT-Lite-7/4 | 73.94% | 3.72 M
Compact Vision Transformers[23]
CVT-7/8 | 70.11% | 3.74 M
CVT-7/4 | 76.49% | 3.72 M
Compact Convolutional Transformers[23]
CCT-2/3 $\times$ 2 | 66.93% | 0.28 M
CCT-7/3 $\times$ 2 | 77.72% | 3.85 M
MAE Vision Transformers [7]
Mae-ViT-C100 | 78.27% | 3.64 M
Current work on mmLiT
mmLiT-S | 79.15% | 2.38M
mmLiT-XS | 76.70% | 1.22M
mmLiT-XXS | 74.95% | 0.67M
Table 8: Top-1 classification accuracy (in percentage) of various models on Cifar100, Cifar10, Svhn, and Flowers102. All models were trained for 100 epochs. For mmLiT and mLiT, all images were resized to 36 x 36, including Flowers-102. For the other models, the image size was set to 32 x 32 for Cifar100, Cifar10, and Svhn, and 224 x 224 for Flowers102. Model |  # Param. (M) | Cifar100 | Cifar10 | Svhn | Flowers102
---|---|---|---|---|---
Vanila variants of ViT [21]
ViT-T [24] | $5.4$ | 55.11 | 79.47 | 92.04 | 45.51
ViT-S [24] | $21.4$ | 54.08 | 79.93 | 94.45 | 56.17
CVT-13 [25] | $20.0$ | 73.50 | 89.02 | 91.47 | 54.29
Swin-T [26] | $29.0$ | 53.28 | 59.47 | 71.60 | 34.51
ResNet-50 [22, 21] | $25.6$ | 72.80 | 91.78 | 96.45 | 46.92
mLiT (no pre-training)
mLiT-S | $2.38$ | 60.58 | 84.03 | 96.01 | 34.41
mLiT-XS | $1.22$ | 57.93 | 82.74 | 95.43 | 35.41
mLiT-XXS | $0.67$ | 56.98 | 80.78 | 94.97 | 35.34
Variants of ViT augmented by Masked Autoencoders [21]
ViT-T+SSAT | $5.8$ | 69.64 | 91.65 | 97.52 | 57.20
ViT-S+SSAT | $21.8$ | 73.37 | 94.05 | 97.87 | 61.15
CVT-13+SSAT | $20.3$ | 75.16 | 95.93 | 97.00 | 68.82
Swin-T+SSAT | $29.3$ | 60.68 | 83.12 | 85.83 | 54.72
mmLiT (pre-trained on Cifar100 )
mmLiT-S | $2.38$ | 78.18 | 94.62 | 97.39 | 59.59
mmLiT-XS | $1.22$ | 75.91 | 94.01 | 97.26 | 57.46
mmLiT-XXS | $0.67$ | 73.42 | 92.21 | 97.32 | 48.59

##  5 Discussion

The results from Table 8 show that ViT can learn better with streamlined MoE
at a much smaller scale. In our current proposal, $\mathbf{V}$ and
$\mathbf{W_{2}}$ are shared across an MoE layer. The main consideration behind
this arrangement is the non-linear $\mathrm{silu}$ applied on $\mathbf{xW}$.
Nevertheless, we have also explored two other possible sharing arrangements on
mmLiT-S (see Table 9), revealing that retaining $\mathbf{W}$ gives a slight
advantage.

Table 9: Investigation into various ways of sharing linear transformations in SwiGLU across MoE layer Items shared | Acc. @ Cifar100
---|---
$\mathbf{V}$, $\mathbf{W_{2}}$ | 79.15
$\mathbf{V}$, $\mathbf{W}$ | 78.34
$\mathbf{W}$, $\mathbf{W_{2}}$ | 78.87

In our design, we have progressively reduced the hidden size and increased the
number of experts at several stages. This arrangement is inspired by
convolutional neural networks [27], where the size of the feature maps is
reduced successively across layers, and the number of feature maps increases
as the network gets deeper. We found that with the arrangement of MoE, a
reduction in hidden size leads to little deterioration in performance if the
reduction is not significant at the early layers and not more than 75% in the
last layers. Further experiments are required in future to confirm this.

When we performed fine-tuning on the four datasets, we started by applying the
fine-tuning setup we used for Cifar100 to the other three datasets. But
overfitting at an early stage became a consistent issue, and because of that,
we had to modify the setup to accommodate each dataset. We encountered similar
problem when we tried to perform supervised learning with mLiT from scratch.
Therefore, we reported setups in Table 4 and Table 5 for clarity. It is worth
nothing that we did not perform a thorough search on the configurations; we
simply adjusted the hyperparameters to avoid overfitting during training.
Furthermore, unlike in [21], we did not use advanced augmentation techniques
in all our fine-tunings.

During pre-training of mmLiT, we used different amount of epochs for the
different sizes of models. From Figure 6, it is clear that more epochs should
have been allocated for mmLiT-XS and mmLiT-XXS from the perspective of loss.
However one of the downsides of masked autoencoders is the unclear
relationship between the loss of a model and its subsequent performance in
downstream tasks. In our experience, we have seen cases where further pre-
training for a few hundreds epochs at a later stage leads to similar or poorer
performance in classification. This might be a specific issue when the dataset
is small. Despite the above, we believe that with such datasets, further pre-
training of thousands of epochs should lead to a better model.

In this study, we found that mLiT pre-trained on only 50,000 images can serve
as a sort of foundation model [28] even at the smallest size. On both Cifar10
and Flowers102, models pre-trained on Cifar100 improve by at least 10%. On
Cifar10, mmLiT-XXS can reach 90% accuracy in less 40 epochs. On Svhn, the
improvements are modest. This is partly because mLiT is already performing
well without pre-training. It is also possibly due to the lack of similar
images in Cifar100. We believe a model pre-trained on a slightly larger and a
more diverse dataset can perform competitively on various simpler tasks at
these tiny scales.

In literature, it is common to integrate convolutional layers [29, 23] or
employ a convolutional ’teacher’ [24] for imparting inductive bias. It seems
the use of streamlined MoE can help alleviate the lack of inductive bias.
However, as demonstrated in [7, 21], with a masked auto-encoder setup, the
problem of inductive bias can be overcome.

##  6 Conclusion

In this paper, we demonstrated the potential of streamlined MoE architecture
to create very lightweight vision transformers. By sharing parameters across
MoE layers and adopting depth-wise scaling, we achieved a balance between
model complexity and performance. Furthermore, our findings suggest that pre-
training on a slightly larger and more diverse dataset could enhance the
model’s versatility and efficacy across various tasks. The streamlined MoE
approach appears promising in mitigating the lack of inductive bias,
particularly when used in conjunction with masked autoencoder setups.

## References

  * [1] Di Liu, Hao Kong, Xiangzhong Luo, Weichen Liu, and Ravi Subramaniam.  Bringing ai to edge: From deep learning’s perspective.  Neurocomputing, 485:297–320, 2022.
  * [2] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [3] J. Zheng, L. Yang, Y. Li, K. Yang, Z. Wang, and J. Zhou.  Lightweight vision transformer with spatial and channel enhanced self-attention.  In 2023 IEEE/CVF International Conference on Computer Vision Workshops (ICCVW), pages 1484–1488, Los Alamitos, CA, USA, oct 2023. IEEE Computer Society.
  * [4] Junting Pan, Adrian Bulat, Fuwen Tan, Xiatian Zhu, Lukasz Dudziak, Hongsheng Li, Georgios Tzimiropoulos, and Brais Martinez.  Edgevits: Competing light-weight cnns on mobile devices with vision transformers.  In European Conference on Computer Vision, 2022.
  * [5] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao.  Pyramid vision transformer: A versatile backbone for dense prediction without convolutions.  In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pages 548–558, 2021.
  * [6] Sachin Mehta and Mohammad Rastegari.  Mobilevit: Light-weight, general-purpose, and mobile-friendly vision transformer.  In International Conference on Learning Representations, 2022.
  * [7] Jen Hong Tan.  Pre-training of lightweight vision transformers on small datasets with minimally scaled images, 2024.
  * [8] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked autoencoders are scalable vision learners.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 16000–16009, 2022.
  * [9] Noam Shazeer, *Azalia Mirhoseini, *Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean.  Outrageously large neural networks: The sparsely-gated mixture-of-experts layer.  In International Conference on Learning Representations, 2017.
  * [10] Noam Shazeer.  Glu variants improve transformer, 2020.
  * [11] Sachin Mehta, Marjan Ghazvininejad, Srinivasan Iyer, Luke Zettlemoyer, and Hannaneh Hajishirzi.  Delight: Deep and light-weight transformer.  In International Conference on Learning Representations, 2021.
  * [12] Joshua Ainslie, James Lee-Thorp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai.  Gqa: Training generalized multi-query transformer models from multi-head checkpoints.  arXiv preprint arXiv:2305.13245, 2023.
  * [13] David Rau.  Sparsely-gated mixture-of-experts pytorch implementation, 2019.
  * [14] Alex Krizhevsky and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  Technical Report 0, University of Toronto, Toronto, Ontario, 2009.
  * [15] Maria-Elena Nilsback and Andrew Zisserman.  Automated flower classification over a large number of classes.  In Indian Conference on Computer Vision, Graphics and Image Processing, Dec 2008.
  * [16] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng.  Reading digits in natural images with unsupervised feature learning.  In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011.
  * [17] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton.  Layer normalization, 2016.
  * [18] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In International Conference on Learning Representations, 2019.
  * [19] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He.  Accurate, large minibatch sgd: Training imagenet in 1 hour, 2018.
  * [20] Ilya Loshchilov and Frank Hutter.  SGDR: Stochastic gradient descent with warm restarts.  In International Conference on Learning Representations, 2017.
  * [21] Srijan Das, Tanmay Jain, Dominick Reilly, Pranav Balaji, Soumyajit Karmakar, Shyam Marjit, Xiang Li, Abhijit Das, and Michael Ryoo.  Limited data, unlimited potential: A study on vits augmented by masked autoencoders.  2024 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), 2024.
  * [22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [23] Ali Hassani, Steven Walton, Nikhil Shah, Abulikemu Abuduweili, Jiachen Li, and Humphrey Shi.  Escaping the big data paradigm with compact transformers.  arXiv preprint arXiv:2104.05704, 2021.
  * [24] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  In International conference on machine learning, pages 10347–10357. PMLR, 2021.
  * [25] Haiping Wu, Bin Xiao, Noel Codella, Mengchen Liu, Xiyang Dai, Lu Yuan, and Lei Zhang.  Cvt: Introducing convolutions to vision transformers.  In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pages 22–31, 2021.
  * [26] Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pages 9992–10002, Los Alamitos, CA, USA, oct 2021. IEEE Computer Society.
  * [27] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25, 2012.
  * [28] Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, S. Buch, Dallas Card, Rodrigo Castellon, Niladri S. Chatterji, Annie S. Chen, Kathleen A. Creel, Jared Davis, Dora Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren E. Gillespie, Karan Goel, Noah D. Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas F. Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, O. Khattab, Pang Wei Koh, Mark S. Krass, Ranjay Krishna, Rohith Kuditipudi, Ananya Kumar, Faisal Ladhak, Mina Lee, Tony Lee, Jure Leskovec, Isabelle Levent, Xiang Lisa Li, Xuechen Li, Tengyu Ma, Ali Malik, Christopher D. Manning, Suvir P. Mirchandani, Eric Mitchell, Zanele Munyikwa, Suraj Nair, Avanika Narayan, Deepak Narayanan, Benjamin Newman, Allen Nie, Juan Carlos Niebles, Hamed Nilforoshan, J. F. Nyarko, Giray Ogut, Laurel Orr, Isabel Papadimitriou, Joon Sung Park, Chris Piech, Eva Portelance, Christopher Potts, Aditi Raghunathan, Robert Reich, Hongyu Ren, Frieda Rong, Yusuf H. Roohani, Camilo Ruiz, Jack Ryan, Christopher R’e, Dorsa Sadigh, Shiori Sagawa, Keshav Santhanam, Andy Shih, Krishna Parasuram Srinivasan, Alex Tamkin, Rohan Taori, Armin W. Thomas, Florian Tramèr, Rose E. Wang, William Wang, Bohan Wu, Jiajun Wu, Yuhuai Wu, Sang Michael Xie, Michihiro Yasunaga, Jiaxuan You, Matei A. Zaharia, Michael Zhang, Tianyi Zhang, Xikun Zhang, Yuhui Zhang, Lucia Zheng, Kaitlyn Zhou, and Percy Liang.  On the opportunities and risks of foundation models.  ArXiv, 2021.
  * [29] Benjamin Graham, Alaaeldin El-Nouby, Hugo Touvron, Pierre Stock, Armand Joulin, Hervé Jégou, and Matthijs Douze.  Levit: a vision transformer in convnet’s clothing for faster inference.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 12259–12269, 2021.