# A General Framework for Learning-Augmented Online Allocation††thanks: An
extended abstract of this paper will appear in the Proceedings of the 50th
EATCS International Colloquium on Automata, Languages and Programming (ICALP
2023). IC was supported in part by ISF grant 1737/21. DP was supported in part
by NSF grants CCF-1750140 (CAREER Award) and CCF-1955703.

Ilan Reuven Cohen Faculty of Engineering, Bar-Ilan University, Israel. ilan-
<EMAIL_ADDRESS>Debmalya Panigrahi  Department of Computer Science,
Duke University, Durham, NC, USA<EMAIL_ADDRESS>
###### Abstract

Online allocation is a broad class of problems where items arriving online
have to be allocated to agents who have a fixed utility/cost for each assigned
item so to maximize/minimize some objective. This framework captures a broad
range of fundamental problems such as the Santa Claus problem (maximizing
minimum utility), Nash welfare maximization (maximizing geometric mean of
utilities), makespan minimization (minimizing maximum cost), minimization of
$\ell_{p}$-norms, and so on. We focus on divisible items (i.e., fractional
allocations) in this paper. Even for divisible items, these problems are
characterized by strong super-constant lower bounds in the classical worst-
case online model.

In this paper, we study online allocations in the learning-augmented setting,
i.e., where the algorithm has access to some additional (machine-learned)
information about the problem instance. We introduce a general algorithmic
framework for learning-augmented online allocation that produces nearly
optimal solutions for this broad range of maximization and minimization
objectives using only a single learned parameter for every agent. As
corollaries of our general framework, we improve prior results of Lattanzi et
al. (SODA 2020) and Li and Xian (ICML 2021) for learning-augmented makespan
minimization, and obtain the first learning-augmented nearly-optimal
algorithms for the other objectives such as Santa Claus, Nash welfare,
$\ell_{p}$-minimization, etc. We also give tight bounds on the resilience of
our algorithms to errors in the learned parameters, and study the learnability
of these parameters.

##  1 Introduction

Recent research has focused on obtaining learning-augmented algorithms for
many online problems to overcome pessimistic lower bounds in competitive
analysis. In this paper, we consider the online allocation framework in the
learning-augmented setting. In this framework, a set of (divisible) items have
to be allocated online among a set of agents, where each agent has a non-
negative utility/cost for each item. This framework captures a broad range of
classic problems depending on the objective one seeks to optimize. In load
balancing (also called makespan minimization), the goal is to minimize the
maximum (MinMax) cost of any agent. A more general goal is to minimize the
$\ell_{p}$-norm of the cost vector defined on the agents, for some $p\geq 1$.
Both makespan minimization (which is $\ell_{\infty}$-minimization) and
$\ell_{p}$-minimization are classic problems in scheduling theory and have
been extensively studied in competitive analysis. In a different vein, the
online allocation framework also applies to maximization problems, where the
allocation of an item obtains some utility for the receiving agent. This
includes the famous Santa Claus problem, where the goal is to maximize the
minimum (MaxMin) utility of any agent, or the maximization of Nash welfare
which is defined as the geometric mean of the agents’ utilities. These
maximization objectives have also been been extensively studied, particularly
because of their connection to fairness in allocations.

Learning-Augmented Online Allocation. In this paper, we consider the online
allocation framework in the learning-augmented setting. Typically, online
allocation problems are characterized by strong super-constant lower bounds in
competitive analysis, e.g., $\Omega(\log m)$ for load balancing [AzarNR95],
$\Omega(p)$ for $\ell_{p}$-minimization [AwerbuchAGKKV95] and $\Omega(m)$ for
both Santa Claus (folklore) and Nash welfare [BanerjeeGGJ22]. A natural
question, then, is whether some additional (machine-learned) information about
the problem instance (we call these learned parameters) can help overcome
these lower bounds and obtain a near-optimal solution. In this paper, we
answer this question in the affirmative. In particular, we give a simple,
unified framework for obtaining near-optimal (fractional) allocations using a
single learned parameter for every agent. Our result holds for both
maximization and minimization problems, and applies to all objective functions
that satisfy two mild technical conditions that we define below. Indeed, the
most interesting aspect of our techniques and results is this generality:
prior work for online allocation problems, both in competitive analysis and
beyond worst-case algorithms, has typically been specific to the objective at
hand, and the techniques for maximization and minimization objectives bear no
similarity. In contrast, our techniques surprisingly handles not only a broad
range of objectives but applies both to maximization and minimization problems
simultaneously. We hope that the generality of our methods will cast a new
light on what is one of the most important classes of problems in
combinatorial optimization.

Before proceeding further, we define the two technical conditions that the
objective function of the online allocation problem needs to satisfy for our
results to apply. Let $f:\mathbb{R}_{>0}^{m}\rightarrow\mathbb{R}_{>0}$ be the
objective function defined on the vector of costs/utilities of the agents.
Then, the conditions are:

  * •

Monotonicity: $f$ is said to be monotone if the following holds: for any
$\ell,\ell^{\prime}\in\mathbb{R}_{>0}^{m}$ such that
$\ell_{i}\geq\ell^{\prime}_{i}$ for all $i\in[m]$, we have $f(\ell)\geq
f(\ell^{\prime})$.

  * •

Homogeneity: $f$ is said to be homogeneous if the following holds: for any
$\ell,\ell^{\prime}\in\mathbb{R}_{>0}^{m}$ such that
$\ell^{\prime}_{i}=\alpha\cdot\ell_{i}$ for all $i\in[m]$, then we have
$f(\ell^{\prime})=\alpha\cdot f(\ell)$.

We say an objective function is well-behaved if it is both monotone and
homogeneous. All online allocation objectives studied previously that we are
aware of are well-behaved, including the examples given above.

###  1.1 Our Results

We now state our main result below:

######  Theorem 1.1 (Informal).

Fix any $\epsilon>0$. For any online allocation problem with a well-behaved
objective, there is an algorithm that achieves a competitive ratio of
$1-\epsilon$ for maximization problems or $1+\epsilon$ for minimization
problems using a single learned parameter for every agent.

We remark that the role of $\epsilon$ in the above theorem is to ensure that
the learned parameter vector is of bounded precision.

Comparison to Prior Work. Lattanzi et al. [LattanziLMV20] were the first to
consider online allocation in a learning-augmented setting. They considered a
special case of the load balancing problem called restricted assignment, and
showed the surprising result that a single (learned) parameter for each agent
is sufficient to bypass the lower bound and obtain a nearly optimal
(fractional) allocation. This result was further generalized by Li and Xian
[LiX21] to the full generality of the load balancing problem, but instead of a
single parameter, they now required two parameters for every agent. At a high
level, their algorithm first uses one set of parameters to restrict the set of
agents who can receive an item, and then solves the resulting restricted
assignment problem using the second set of parameters. A a corollary of
Theorem 1.1, we improve this result by obtaining a near-optimal solution using
a single learned parameter for every agent. In both these papers, as well as
in our paper, the (fractional) allocation uses _proportional allocation_. In
the setting of online optimization, proportional allocations were used earlier
by Agrawal et al. [agrawal2018proportional] for the (weighted) $b$-matching
problem. As in our paper, they also gave an iterative algorithm for computing
the parameters of the allocation. However, because the two problems are
structurally very different (e.g., matching is a packing problem while our
allocation problems are covering problems), the iterative algorithm in the
Agrawal et al. paper is different from ours. To the best of our knowledge, our
results for the other problems, namely Santa Claus, Nash welfare maximization,
$\ell_{p}$-norm minimization, and other objectives that can be defined in the
online allocation framework are the first results in learning-augmented
algorithms for these problems.

We now state our additional results.

Resilience to Prediction Error. A key desiderata of learning-augmented online
algorithms is resilience to errors in the learned parameters. In other words,
one desires that the competitive ratio of the algorithm should gracefully
degrade when the learned parameters used in the algorithm deviate from their
optimal values. For well-behaved objectives for both minimization and
maximization problems, we give an error-resilient algorithm whose competitive
ratio degrades gracefully with prediction error:

######  Theorem 1.2 (Informal).

For any online allocation problem with a well-behaved objective, there is an
(learning-augmented) algorithm that achieves a competitive ratio of
$O(\alpha)$ when the learned parameter input to the algorithm is within a
multiplicative factor of $\alpha$ of the optimal learned parameter for every
agent. This holds for both minimization and maximization objectives.

The above theorem is asymptotically tight for the MaxMin objective. But,
interestingly, for the MinMax objective we can do better:

######  Theorem 1.3 (Informal).

For the load balancing problem (MinMax objective), there is an (learning-
augmented) algorithm that achieves a competitive ratio of $O(\log\alpha)$ when
the learned parameter input to the algorithm is within a multiplicative factor
of $\alpha$ of the optimal learned parameter for every agent. Moreover, the
dependence $O(\log\alpha)$ in the above statement is asymptotically tight.

An analogous statement was previously known only in the special case of
restricted assignment [LattanziLMV20].

######  Remark 1.4.

We use a multiplicative measure of error $\alpha$ similar to [LattanziLMV20].
For both MinMax and MaxMin objectives, we may assume w.l.o.g. that $\alpha\leq
m$. This is because by standard techniques, it is possible to achieve
$O(\min(\alpha,m))$ and $O(\log\min(\alpha,m))$ competitiveness for the MaxMin
and MinMax objectives respectively. We also show that our bounds are
asymptotically tight as a function of $\alpha$, in addition to matching
existing lower bounds for the two problems as a function of $m$.

Learnability of Parameters. We also study the learnability of the parameters
used in our algorithm. Following [LiX21] and [LavastidaMRX21a], we adopt the
PAC framework. We assume that each item is drawn independently (but not
necessarily identically) from a distribution, and show a bound on the sample
complexity of approximately learning the parameter vector under this setting.
For the MaxMin and MinMax objectives, we show the following:

######  Theorem 1.5 (Informal).

Fix any $\epsilon>0$. For the online allocation problem with MaxMin or MinMax
objectives, the sample complexity of learning a parameter vector that gives a
$1-\epsilon$ (for MaxMin) or $1+\epsilon$ (for MinMax) approximation is
$O(\frac{m}{\log m}\cdot\log\frac{m}{\epsilon})$.

We note that a similar result was previously known for the MinMax objective
(Li and Xian [LiX21]). We also generalize this result to all well-behaved
objectives subject to a technical condition of superadditivity for
maximization or subadditivity for minimization. All the objectives described
earlier in the introduction satisfy these conditions.

##### Our Techniques

Our learning-augmented online algorithms for both minimization and
maximization objectives follow from a single, unified algorithmic framework
that we develop in this paper. This is quite surprising because in the worst-
case setting, the online algorithms for the different objectives do not share
any similarity (indeed have different competitive ratios), particularly
between maximization and minimization problems. First, let us first consider
the MinMax and MaxMin objectives. To use common terminology across these
problems, let us call the cost/utility of an item $j$ to an agent $i$ the
weight of item $j$ for agent $i$ and denote it $p_{i,j}$. Our common
algorithmic framework uses proportional allocation according to the learned
parameters of the agents. Let $w_{i}$ denote the parameter for agent $i$.
Normally, proportional allocation would entail that we allocate a fraction
$x_{i,j}$ of item $j$ to agent $i$ where
$x_{i,j}=\frac{w_{i}p_{i,j}}{\sum_{i^{\prime}}w_{i^{\prime}}p_{{i^{\prime}},j}}$.
But, this is clearly not adequate, since it would produce the same allocation
for both the MaxMin and MinMax objectives. Specifically, if $p_{i,j}$ is large
for a pair $i,j$, then $x_{i,j}$ should be large for the MaxMin objective and
small for the MinMax objective respectively. To implement this intuition, we
exponentiate the weight $p_{i,j}$ by a fixed value $\alpha$ that depends on
the objective (i.e., is different for MaxMin and MinMax) and then allocate
using fractions
$x_{i,j}=\frac{w_{i}p_{i,j}^{\alpha}}{\sum_{i^{\prime}}w_{i^{\prime}}p_{{i^{\prime}},j}^{\alpha}}$.
We call this an exponentiated proportional allocation (or EP-allocation in
short), and call $\alpha$ the exponentiation constant.

Let us fix any value of $\alpha$. It is clear that for both the MinMax and
MaxMin objectives, an optimal allocation has uniform cumulative fractional
weights (called load) across all agents. (Note that otherwise, an
infinitesimal fraction of an item can be repeatedly moved from the most loaded
to the least loaded agent to eventually improve the competitive ratio.)
Following this intuition, we define a canonical allocation as one that sets
learned parameters on the agents in a way that equalizes the loads on all
agents. We show that the canonical allocation always exists and is unique.
Indeed, this is true not only for all EP-allocation algorithms, but for a much
broader class of proportional allocation schemes that we called generalized
proportional allocations (or GP-allocations). In the latter class, we allow
any transformation of the weights $p_{i,j}$ before applying proportional
allocation. Thus, EP-allocations represent the subclass of GP-allocations
where the transformation is exponentiation by the fixed value $\alpha$. We
also give a simple iterative (Sinkhorn-like) algorithm for computing the
optimal learned parameters, and establish its convergence properties, for GP-
allocations. GP-allocations give an even larger palette of proportional
allocation schemes to choose from than EP-allocations, and we hope it will be
useful in future work for problem settings that are not covered in this paper
(e.g., non-linear utilities).

Finally, we need to set the value of $\alpha$ specifically for the MinMax and
MaxMin objectives. Intuitively, it is clear that we need to set $\alpha$ to a
large positive value for the MaxMin objective and a large negative value for
the MinMax objective. Indeed, we show that in the limit of
$\alpha\rightarrow\infty$ and $\alpha\rightarrow-\infty$, the canonical
allocation defined above recovers optimal allocations for the MaxMin and
MinMax objectives respectively. We also show a monotonicity property of the
optimal objective (with the value of $\alpha$) that can be used to set
$\alpha$ to a finite value (function of $\epsilon$) and obtain a $1-\epsilon$
(resp., $1+\epsilon$) approximation for the MaxMin (resp., MinMax) objective,
for any $\epsilon>0$.

Now that we have described the EP-allocation scheme for obtaining nearly
optimal algorithms for the MinMax and MaxMin objectives, we generalize to all
well-behaved objective functions. This is quite simple. The main advantage of
the MinMax and MaxMin objectives that is not shared by other objectives is the
property that the optimal solution has uniform load across all agents. Now,
suppose for a maximization objective, the load of agent $i$ in an optimal
solution is $s_{i}$ (we call this the scaling parameter for agent $i$). For
now, suppose these values $s_{i}$ are also provided offline as a second set of
parameters. Then, we can first scale the weights $p_{i,j}$ using these
parameters to obtain a new instance $q_{i,j}=\frac{p_{i,j}}{s_{i}}$. Clearly,
the optimal solution for the original instance has uniform load across all
agents for the transformed instance. Indeed, by the monotonicity of the
maximization objective, this solution for the transformed instance is also
optimal for the MaxMin objective. Using the above analysis for the MaxMin
objective, we can now claim that there exist learned parameters $w_{i}$ for
$i\in[m]$ such that setting
$x_{i,j}=\frac{w_{i}q_{i,j}^{\alpha}}{\sum_{i^{\prime}}w_{i^{\prime}}q_{{i^{\prime}},j}^{\alpha}}$
gives an optimal solution to the original instance of the problem. Now, note
that

$x_{i,j}=\frac{w_{i}q_{i,j}^{\alpha}}{\sum_{i^{\prime}}w_{i^{\prime}}q_{{i^{\prime}},j}^{\alpha}}=\frac{(w_{i}/s_{i}^{\alpha})p_{i,j}^{\alpha}}{\sum_{i^{\prime}}(w_{i^{\prime}}/s_{i^{\prime}}^{\alpha})p_{{i^{\prime}},j}^{\alpha}}=\frac{w^{\prime}_{i}p_{i,j}^{\alpha}}{\sum_{i^{\prime}}w^{\prime}_{i^{\prime}}p_{{i^{\prime}},j}^{\alpha}}\text{
for }w^{\prime}_{i}=w_{i}/s_{i}^{\alpha}.$

It follows that by using learned parameters $w^{\prime}_{i}$ in an EP-
allocation on the original instance, we can obtain an optimal solution for the
original maximization objective. (The case for a minimization objective is
identical to the above argument, with the MaxMin objective being replaced by
the MinMax objective.) Finally, using the homogeneity of the objective
function, we can also set $\alpha$ to a finite value (function of $\epsilon$)
and obtain a $1-\epsilon$ (resp., $1+\epsilon$) approximation for the
maximization (resp., minimization) objective, for any $\epsilon>0$.

###  1.2 Related Work

Learning-augmented online algorithms were pioneered by the work of Lykouris
and Vassilvikskii [LykourisV21] for the caching problem, and has become a very
popular research area in the last few years. The basic idea of this framework
is to augment an online algorithm with (machine-learned) predictions about the
future, which helps overcome pessimistic worst case lower bounds in
competitive analysis. Many online allocation problems have been considered in
this framework in scheduling [PurohitSK18, AzarLT21, AzarLT22, BamasMRS20,
ImKQP21, Mitzenmacher20], online matching [AntoniadisGKK20, ChenI21,
KumarPSSV19], ad delivery [MahdianNS12, LavastidaMRX21b], etc. The reader is
referred to the survey by Mitzenmacher and Vassilvitskii [MitzenmacherV20,
MitzenmacherV22] for further examples of online learning-augmented algorithms.
The papers specifically related to our work are those of Lattanzi et al.
[LattanziLMV20] and Li and Xian [LiX21] that we described above, and that of
Lavastida et al. [LavastidaMRX21a] that focuses on the learnability of the
parameters for the same problem. As mentioned earlier, Agrawal et al.
[agrawal2018proportional] used the proportional allocation framework earlier
for the online (weighted) $b$-matching problem, and gave an iterative
algorithm for computing the parameters of the allocation.

We now give a brief summary of online allocation in the worst-case model. For
minimization problems, two classic objectives are makespan (i.e.,
$\ell_{\infty}$ norm) and $\ell_{p}$ norm minimization for $p>1$. The former
was studied in several works (e.g., [AzarNR95, AspnesAFPW97]), eventually
leading to an asymptotically tight bound of $\Theta(\log m)$. This was later
generalized to arbitrary $\ell_{p}$ norms, and a tight bound of $\Theta(p)$
was obtained for this case [AwerbuchAGKKV95, Caragiannis08]. For maximization
objectives, there are $\Omega(m)$ lower bounds for many natural objectives
such as MaxMin (see, e.g., [HajiaghayiKPS22]) and Nash welfare
[BanerjeeGGJ22]. Some recent work has focused on overcoming these lower bounds
using additional information such as monopolist values for the agents
[BanerjeeGGJ22, BarmanKM22]. While this improves the competitive ratio to sub-
linear in $m$, lower bounds continue to rule out near-optimal solutions (or
even constant factor approximations) that we seek in this paper.

Organization. For most of the paper, we only consider the MinMax and MaxMin
objectives. We establish the notation in Section 2 and give an overview of the
results. Then, we prove these results by showing properties of GP-allocations
in Section 3 and of EP-allocations in Section 4. Next, we give noise resilient
algorithms in Section 5 and discuss learnability of the parameters in Section
6. Finally, in Section 7, we extend our results to all well-behaved objective
functions via simple reductions to the MaxMin and MinMax objectives.

##  2 Preliminaries and Results

###  2.1 Problem Definition

We have $n$ (divisible) items that arrive online and have to be (fractionally)
allocated to $m$ agents. The weight of item $j\in[n]$ for agent $i\in[m]$ is
denoted $p_{i,j}$ and is revealed when item $j$ arrives. We denote the weight
matrix

$P=\begin{bmatrix}p_{1,1}&\ldots&p_{1,n}\\\ \vdots&\ddots&\vdots\\\
p_{m,1}&\ldots&p_{m,n}\\\ \end{bmatrix}\text{ where all $p_{i,j}>0$ for all
$i\in[m],j\in[n]$}.$

A feasible allocation is given by an assignment matrix

$X=\begin{bmatrix}x_{1,1}&\ldots&x_{1,n}\\\ \vdots&\ddots&\vdots\\\
x_{m,1}&\ldots&x_{m,n}\\\ \end{bmatrix}\text{ where }x_{i,j}\in[0,1]\text{ for
all }i\in[m],j\in[n]\text{ and }\sum_{i=1}^{m}x_{i,j}=1\text{ for all
}j\in[n].$

Note that every item has to be fully allocated among all the agents. We use
$\mathcal{X}$ to denote the set of feasible solutions. The total weight of an
agent $i$ corresponding to an allocation $X$ (we call this the load of $i$) is
given by

$\ell_{i}(P,X)=\sum_{j\in[n]}x_{i,j}\cdot p_{i,j},$

and the vector of loads of all the agents is denoted $\bm{\ell}(P,X)$.

The load balancing problem is now defined as

$\min_{X\in\mathcal{X}}\Big{\\{}T:\ell_{i}(P,X)\leq T\text{ for all
}i\in[m]\Big{\\}},$

while the Santa Claus problem is defined as

$\max_{X\in\mathcal{X}}\Big{\\{}T:\ell_{i}(P,X)\geq T\text{ for all
}i\in[m]\Big{\\}}.$

###  2.2 Exponentiated and Generalized Proportional Allocations

Our algorithmic framework is simple: when allocating item $j$, we first
exponentiate the weights $p_{i,j}$ to $p_{i,j}^{\alpha}$ for some fixed
$\alpha$ (called the exponentiation constant) that only depends on the
objective being optimized. Next, we perform proportional allocation weighted
by the learned parameters $w_{i}$ for agents $i\in[m]$:

$x_{i,j}=\frac{p_{i,j}^{\alpha}\cdot
w_{i}}{\displaystyle\sum_{i^{\prime}\in[m]}p_{i^{\prime},j}^{\alpha}\cdot
w_{i^{\prime}}}.$

We call this an exponentiated proportional allocation or EP-allocation in
short.

Our main theorem is the following:

######  Theorem 2.1.

For the load balancing and Santa Claus problems, there are EP-allocations that
achieve a competitive ratio of $1+\epsilon$ and $1-\epsilon$ respectively, for
any $\epsilon>0$.

The Canonical Allocation. In order to define an EP-allocation and establish
Theorem 2.1, we need to specify two things: the vector of learned parameters
$\mathbf{w}\in\mathbb{R}_{>0}^{m}$ and the exponentiation constant $\alpha$.
First, we focus on the learned parameters. For any fixed $\alpha$ and a weight
matrix $P$, we use learned parameters $\mathbf{w}\in\mathbb{R}_{>0}^{m}$ that
result in equal load for every agent. We call this the canonical allocation.
The corresponding learned parameters and the load of every agent are
respectively called the canonical parameters (denoted $\mathbf{w}^{*}$) and
the canonical load (denoted $\ell^{*}$).

Apriori, it is not clear that a canonical allocation should even exist, and
even if it does, that it is unique. Interestingly, we show this existence and
uniqueness not just from EP-allocations but for the much broader class of
proportional allocations where any function
$f:\mathbb{R}_{>0}\rightarrow\mathbb{R}_{>0}$ (called the transformation
function) can be used to transform the weights rather than just an exponential
function. I.e.,

$x_{i,j}=\frac{f(p_{i,j})\cdot
w_{i}}{\displaystyle\sum_{i^{\prime}\in[m]}f(p_{i^{\prime},j})\cdot
w_{i^{\prime}}}.$

We call this a generalized proportional allocation or GP-allocation in short.

We show the following theorem for GP-allocations:

######  Theorem 2.2.

For any weight matrix $P\in\mathbb{R}_{>0}^{m\times n}$ and any transformation
function $f:\mathbb{R}_{>0}\rightarrow\mathbb{R}_{>0}$, the canonical load for
a GP-allocation exists and is unique. Moreover, it is attained by a unique (up
to scaling) set of canonical parameters.

We prove Theorem 2.2 algorithmically by giving a simple iterative (offline)
algorithm that converges to the set of canonical parameters (see Algorithm 1).
We will show later that the canonical allocations produced by appropriately
setting the value of the exponentiation constant $\alpha$ are respectively
optimal (fractional) solutions for the Santa Claus and the load balancing
problems. Therefore, an interesting consequence of the iterative convergence
of this algorithm to the canonical allocation is that it gives a simple
alternative offline algorithm for computing an optimal fractional solution for
these two problems. To the best of our knowledge, this was not explicitly
known before our work.

An interesting direction for future research would be to explore other natural
classes of transformation functions, other than the exponential functions
considered in this paper. Since Theorem 2.2 holds for any transformation
function, they also admit a canonical allocation, and it is conceivable that
such canonical allocations would optimize objective functions other than the
MinMax and MaxMin functions considered here. For example, one natural open
problem is following: are there a transformation functions whose canonical
allocations correspond to maximizing Nash Social Welfare or minimizing
$p$-norms of loads?

Monotonicity and Convergence of EP-allocations. Now that we have defined the
learned parameters in Theorem 2.1 as the corresponding canonical parameters,
we are left to define the values of the exponentiation constant $\alpha$ for
the MaxMin and MinMax problems respectively. We show two key properties of
canonical loads of EP-allocations. First, we show that the canonical load is
monotone nondecreasing with the value of $\alpha$. This immediately suggests
that we should choose the largest possible value of $\alpha$ for the MaxMin
problem since it is a maximization problem, and the smallest possible value of
$\alpha$ for the MinMax problem since it is a minimization problem. Indeed,
the second property that we show is that in the limit of
$\alpha\rightarrow\infty$, the canonical load converges to the optimal
objective for the Santa Claus problem (we denote this optimal value
$\ell^{\textbf{SNT}}$) and in the limit of $\alpha\rightarrow-\infty$, the
canonical load converges to the optimal objective for the load balancing
problem (we denote this optimal value $\ell^{\textbf{MKS}}$).

For a fixed $\alpha$, let $X(P,\alpha,\mathbf{w})$ denote the assignment
matrix and $\bm{\ell}(P,\alpha,\mathbf{w})$ the load vector for a learned
parameter vector $\mathbf{w}$. Let $\bm{\ell}^{*}(P,\alpha)$ denote the
corresponding canonical load. We show the following properties of canonical
EP-allocations:

######  Theorem 2.3.

For any weight matrix $P\in\mathbb{R}_{>0}^{m\times n}$, the following
properties hold for canonical EP-allocations:

  * •

The monotonicity property: For $\alpha_{1},\alpha_{2}\in\mathbb{R}$ such that
$\alpha_{1}\geq\alpha_{2}$, we have
$\ell^{*}(P,\alpha_{1})\geq\ell^{*}(P,\alpha_{2})$.

  * •

The convergence property:
$\displaystyle\lim_{\alpha\rightarrow\infty}\ell^{*}(P,\alpha)=\ell^{\textbf{SNT}}(P)$
and
$\displaystyle\lim_{\alpha\rightarrow-\infty}\ell^{*}(P,\alpha)=\ell^{\textbf{MKS}}(P)$.

Clearly, Theorem 2.3 implies Theorem 2.1 as a corollary when $\alpha$ is set
sufficiently large for the Santa Claus problem and sufficiently small for the
load balancing problem.

In the rest of the paper, we will prove Theorem 2.2 and Theorem 2.3.

##  3 Canonical Properties of Generalized Proportional Allocations

In this section, we prove Theorem 2.2. For notational convenience, we define a
transformation matrix $G\in\mathbb{R}_{>0}^{m\times n}$ where
$G(i,j)=f(p_{i,j})$ for the transformation function $f$. Using this notation,
we denote by $x_{i,j}(G,\mathbf{w})$ the fractional allocation of item $j$ to
agent $i$, and by $\ell_{i}(P,G,\mathbf{w})$ the load of agent $i$ (we use
$\bm{\ell}(P,G,\mathbf{w})$ to denote the vector of agent loads) under the GP-
allocation corresponding to the transformation matrix $G$ and learned
parameters $\mathbf{w}$.

We say two sets of learned parameters $\mathbf{w},\mathbf{w}^{\prime}$ are
equivalent (denoted $\mathbf{w}\equiv\mathbf{w}^{\prime}$) if there exists
some constant $c>0$ such that $w^{\prime}_{i}=c\cdot w_{i}$ for every agent
$i\in[m]$. The following is a simple observation from the GP-allocation scheme
that two equivalent sets of learned parameters produce the same allocation:

######  Observation 3.1.

For any $G\in\mathbb{R}_{>0}^{m\times n}$, if
$\mathbf{w}\equiv\mathbf{w}^{\prime}\in\mathbb{R}_{>0}^{m}$, then
$x_{i,j}(G,\mathbf{w})=x_{i,j}(G,\mathbf{w}^{\prime})$ for all $i,j$.

We also note that GP-allocations are monotone in the sense that if one agent’s
parameter decreases while the rest increase, then the allocation on this agent
decreases as well.

######  Observation 3.2.

Consider any $G\in\mathbb{R}_{>0}^{m\times n}$ and any nonzero vector
$\bm{\epsilon}\in\mathbb{R}_{\geq 0}^{m}$ such that $-w_{k}<\epsilon_{k}\leq
0$ for some $k\in[m]$ and $\epsilon_{i}\geq 0$ for all $i\neq k$. Then,
$x_{k,j}(G,\mathbf{w}^{\prime})<x_{k,j}(G,\mathbf{w})$ for all $j\in[n]$,
where $\mathbf{w}^{\prime}=\mathbf{w}+\bm{\epsilon}$ and
$\mathbf{w}^{\prime}\not=\mathbf{w}$.

Our first nontrivial property is that the load vector uniquely determines the
learned parameters up to equivalence of the parameters.

######  Lemma 3.3.

For any $P,G\in\mathbb{R}_{>0}^{m\times n}$,
$\ell_{i}(P,G,\mathbf{w})=\ell_{i}(P,G,\mathbf{w}^{\prime})$ for all $i\in[m]$
if and only if $\mathbf{w}\equiv\mathbf{w}^{\prime}$.

###### Proof.

In one direction, if $\mathbf{w}\equiv\mathbf{w}^{\prime}$, the loads are
identical because the allocations are identical (by Observation 3.1).

We now show the lemma in the opposite direction. Let
$k=\arg\min_{i}\frac{w_{i}}{w^{\prime}_{i}}$ and
$c=\frac{w_{k}}{w^{\prime}_{k}}$. Let us define
$\hat{\mathbf{w}}=c\cdot\mathbf{w}^{\prime}$. Then, $\hat{w}_{k}=w_{k}$, and
$\hat{w}_{i^{\prime}}=\left(\min_{i}\frac{w_{i}}{w^{\prime}_{i}}\right)\cdot
w^{\prime}_{i^{\prime}}\leq\ w_{i^{\prime}}$ for all $i^{\prime}\not=k$. Now,
if $\mathbf{w}$ and $\mathbf{w}^{\prime}$ are not equivalent, then there
exists some $i^{\prime}\in[m]$ such that
$\hat{w}_{i^{\prime}}<w_{i^{\prime}}$. Therefore, by Observation 3.2,
$x_{k,j}(G,\hat{\mathbf{w}})>x_{k,j}(G,\mathbf{w})$ for all $j\in[n]$. But, by
Observation 3.1, $x_{k,j}(G,\hat{\mathbf{w}})=x_{k,j}(G,\mathbf{w}^{\prime})$
for all $j\in[n]$. Thus,
$x_{k,j}(G,\mathbf{w}^{\prime})>x_{k,j}(G,\mathbf{w})$ for all $j\in[n]$,
which contradicts
$\ell_{k}(P,G,\mathbf{w}^{\prime})=\ell_{k}(P,G,\mathbf{w})$. ∎

Similarly, we show that if the canonical load exists (i.e., a load vector
where all loads are identical), it must be unique.

######  Lemma 3.4.

For any $P,G\in\mathbb{R}_{>0}^{m\times n}$, if there exist
$\mathbf{w},\mathbf{w}^{\prime}\in\mathbb{R}_{>0}^{m}$ such that
$\ell_{i}(P,G,\mathbf{w})=\ell$ and
$\ell_{i}(P,G,\mathbf{w}^{\prime})=\ell^{\prime}$ for all $i\in[m]$, then
$\ell=\ell^{\prime}$.

###### Proof.

Assume for the purpose of contradiction that there exist
$\mathbf{w},\mathbf{w}^{\prime}\in\mathbb{R}_{>0}^{m}$ such that for all
$i\in[m]$, $\ell_{i}(P,G,\mathbf{w})=\ell$ and
$\ell_{i}(P,G,\mathbf{w}^{\prime})=\ell^{\prime}$ but $\ell>\ell^{\prime}$.
Let $k=\arg\min_{i}\frac{w_{i}}{w^{\prime}_{i}}$ and
$c=\frac{w_{k}}{w^{\prime}_{k}}$, and let
$\hat{\mathbf{w}}=c\cdot\mathbf{w}^{\prime}$. We have

$\ell^{\prime}=\ell_{k}(P,G,\mathbf{w}^{\prime})=\ell_{k}(P,G,\hat{\mathbf{w}})\geq\ell_{k}(P,G,\mathbf{w})=\ell,\text{which
is a contradiction.}$

Here, the second equality is by Observation 3.1, and the inequality is by
Observation 3.2, since $\hat{w}_{k}=w_{k}$, and $\hat{w}_{i}\leq w_{i}$ for
$i\in[m]$. ∎

###  3.1 Convergence of Algorithm 1

The rest of this section focuses on showing the existence of a canonical
allocation for GP-allocations. We do so by showing convergence of the
following simple iterative algorithm (Algorithm 1):

  * •

Initialize: $\mathbf{w}^{(0)}\leftarrow\mathbf{1}^{m}$

Iteration $r$:

  * •

Compute $\bm{\ell}^{(r)}$ as
$\ell^{(r)}_{i}\leftarrow\ell_{i}(P,G,\mathbf{w}^{(r)})$, for all $i\in[m]$,
where $\ell_{i}(P,G,\mathbf{w}^{(r)})$ is the load of agent $i$ under the GP-
allocation with transformation matrix $G$ and learned parameters
$\mathbf{w}^{(r)}$.

  * 0.1•

Set $\mathbf{w}^{(r+1)}$ as
$w^{(r+1)}_{i}\leftarrow\frac{w^{(r)}_{i}}{\ell^{(r)}_{i}}\cdot\gamma^{(r)}$,
for all $i\in[m]$.

Here, $\gamma^{(r)}\in\mathbb{R}_{>0}$ is a scaling factor whose value does
not affect the load (by Observation 3.1). But, by using, e.g.,
$\gamma^{(r)}=\ell^{(r)}_{1}$, we can ensure that the algorithm terminates
with a single set of learned parameters instead of repeatedly finding
equivalent sets of parameters after it has converged.

Algorithm 1 The iterative algorithm showing the existence of a canonical
allocation for GP-allocations.

Note that Algorithm 1 ensures that if the loads of all agents are uniform at
any stage, then the iterative process has converged and the algorithm
terminates. So, it remains to show that for any
$P,G\in\mathbb{R}_{>0}^{m\times n}$, this iterative process reaches a set of
parameters $\mathbf{w}^{*}\in\mathbb{R}_{>0}^{m}$ such that
$\ell_{i}(P,G,\mathbf{w}^{*})=\ell_{i^{\prime}}(P,G,\mathbf{w}^{*})$ for all
$i,i^{\prime}\in[m]$.

Our proof has two parts. The first part shows that the maximum and minimum
loads are (weakly) monotone over the course of the iterative process. For
this, we focus on a single iteration. For a vector
$\bm{\ell}\in\mathbb{R}_{>0}^{m}$, let $\ell_{\max}=\max_{i\in[m]}\ell_{i}$
and $\ell_{\min}=\min_{i\in[m]}\ell_{i}$ be the maximum and minimum
coordinates of $\bm{\ell}$. We will show that if $\ell_{\max}^{(r)}$ and
$\ell_{\min}^{(r)}$ are not equal at the beginning of an iteration, then
$\ell_{\max}^{(r)}$ can only decrease (or stay unchanged) and
$\ell_{\min}^{(r)}$ can only increase (or stay unchanged) in a single
iteration.

######  Lemma 3.5.

Consider any $P,G\in\mathbb{R}_{>0}^{m\times n}$, $\gamma>0$. Let
$\mathbf{w},\mathbf{w}^{\prime},\bm{\ell},\bm{\ell}^{\prime}\in\mathbb{R}_{>0}^{m}$
such that $\ell_{i}=\ell_{i}(P,G,\mathbf{w})$,
$\ell^{\prime}_{i}=\ell_{i}(P,G,\mathbf{w}^{\prime})$ and
$w^{\prime}_{i}=\frac{w_{i}}{\ell_{i}}\cdot\gamma$ and let
$\tilde{p}_{i}=\sum_{j}p_{i,j}$. Then, we have
$\ell_{i}^{\prime}\geq\nicefrac{{\ell_{\min}}}{{\left(1-\frac{\ell_{i}-\ell_{\min}}{\tilde{p}_{i}}\right)}}$
and
$\ell_{i}^{\prime}\leq\nicefrac{{\ell_{\max}}}{{\left(1+\frac{\ell_{\max}-\ell_{i}}{\tilde{p}_{i}}\right)}}$

In the second part, we show that the ratio
$\frac{\ell_{\max}^{(r)}}{\ell_{\min}^{(r)}}$ is strictly decreasing after a
finite number of iterations. The proof of this stronger property requires the
per-iteration weak monotonicity property that we establish in the first part
of the proof.

######  Lemma 3.6.

Let $P,G\in\mathbb{R}_{>0}^{m\times n}$ be given fixed matrices. Fix an
iteration $r$ in Algorithm 1 where $\ell_{\max}^{(r)}>\ell_{\min}^{(r)}$. Let
$\ell_{\max}^{(r)}\geq(1+\epsilon)\cdot\ell_{\min}^{(r)}$ for some
$\epsilon\in(0,1]$. Then, in the next iteration, we have
$\ell_{\min}^{(r+1)}\geq(1+c\cdot\epsilon)\cdot\ell_{\min}^{(r)}$ for some
constant $c>0$ that only depends on $P$ and $G$.

Using Lemma 3.5 and Lemma 3.6, we complete the proof of Theorem 2.2.

###### Proof of Theorem 2.2.

We are given fixed matrices $P,G\in\mathbb{R}_{>0}^{m\times n}$. Let
$\ell_{\max}^{(r)},\ell_{\min}^{(r)}$ denote the maximum and the minimum load
respectively in iteration $r$ of Algorithm 1. Let $c>0$ be the constant (that
depends only on $P,G$) in Lemma 3.6.

For a non-negative integer $a$, let $r_{a}$ be defined recursively as follows:

$r_{a}=r_{a-1}+\left\lceil\frac{\log(1+2^{-a+1})}{\log{(1+c\cdot
2^{-a})}}\right\rceil+1,\text{ where
}r_{0}=\left\lceil\frac{\log\left(\nicefrac{{\ell_{\max}^{(0)}}}{{\ell_{\min}^{(0)}}}\right)}{\log{(1+c)}}\right\rceil+1.$

We will show for any $a$, in any iteration $r\geq r_{a}$, we have
$\nicefrac{{\ell_{\max}^{(r)}}}{{\ell_{\min}^{(r)}}}\leq 1+2^{-a}$. First, we
prove it for $a=0$. If there exists some $r\leq r_{0}$ such that
$\nicefrac{{\ell_{\max}^{(r)}}}{{\ell_{\min}^{(r)}}}\leq 2$, then this also
holds for $r\geq r_{0}$ by Lemma 3.5. Otherwise, for all $r\leq r_{0}$ we have
$\nicefrac{{\ell_{\max}^{(r)}}}{{\ell_{\min}^{(r)}}}>2$. Then, using Lemma 3.6
with $\epsilon=1$, we get
$\ell_{\min}^{(r+1)}\geq(1+c)\cdot\ell_{\min}^{(r)}$. Therefore,
$\ell_{\min}^{(r_{0})}\geq(1+c)^{r_{0}}\cdot\ell_{\min}^{(0)}>\ell_{\max}^{(0)}$
by our choice of $r_{0}$. This contradicts Lemma 3.5, thereby showing that
$\nicefrac{{\ell_{\max}^{(r)}}}{{\ell_{\min}^{(r)}}}\leq 2$ for any $r\geq
r_{0}$.

Now, we show the inductive case. Assume the inductive hypothesis that
$\nicefrac{{\ell_{\max}^{(r_{a-1})}}}{{\ell_{\min}^{(r_{a-1})}}}\leq
1+2^{-(a-1)}$. We will prove that
$\nicefrac{{\ell_{\max}^{(r_{a})}}}{{\ell_{\min}^{(r_{a})}}}\leq 1+2^{-(a)}$.
The proof is similar to the base case of $a=0$. If there exists some $r\leq
r_{a}$ such that $\nicefrac{{\ell_{\max}^{(r)}}}{{\ell_{\min}^{(r)}}}\leq
1+2^{-a}$, then this inequality also holds for any $r\geq r_{a}$ by Lemma 3.5.
Otherwise, for all $r\leq r_{a}$ we have
$\nicefrac{{\ell_{\max}^{(r)}}}{{\ell_{\min}^{(r)}}}>1+2^{-a}$. Then, for all
$r_{a-1}\leq r\leq r_{a}$, using Lemma 3.6 with $\epsilon=2^{-a}$, we have
$\ell_{\min}^{(r+1)}\geq(1+c\cdot 2^{-a})\cdot\ell_{\min}^{(r)}$. Therefore,
$\ell_{\min}^{(r_{a})}\geq(1+c\cdot
2^{-a})^{r_{a}-r_{a-1}}\cdot\ell_{\min}^{(r_{a-1})}$. By our choice of
$r_{a}$, this implies
$\ell_{\min}^{(r_{a})}>(1+2^{-(a-1)})\cdot\ell_{\min}^{(r_{a-1})}$. By the
induction hypothesis, this implies
$\ell_{\min}^{(r_{a})}>\ell_{\max}^{(r_{a-1})}$. But, this implies
$\ell_{\max}^{(r_{a})}>\ell_{\max}^{(r_{a-1})}$, which contradicts Lemma 3.5.
Therefore,

$\lim_{r\rightarrow\infty}\nicefrac{{\ell_{\max}^{(r)}}}{{\ell_{\min}^{(r)}}}=1,$

and $\ell^{*}(P,G)=\displaystyle\lim_{r\rightarrow\infty}\ell_{\max}^{(r)}$.
Moreover, by Lemma 3.4 this value is uniquely defined and attained by a unique
(up to scaling) set of learned parameters.

∎

###  3.2 Weak Monotonicity of the Maximum and Minimum Loads in Algorithm 1:
Proof of Lemma 3.5

For ease of description, we assume that $G$ and $\mathbf{w}$ are normalized in
the following sense:

$\mathbf{w}=\mathbf{1}^{m}\text{ and }\sum_{j}g_{i,j}=1.$

This transformation is local to the current iteration, and only for the
purpose of this proof. First, we explain why this change of notation is
w.l.o.g. Suppose $\hat{G},{\bf\hat{w}}$ represent the actual transformation
matrix and learned parameters respectively. Now, we define $G$ as follows:

$g_{i,j}=\frac{\hat{g}_{i,j}\cdot\hat{w}_{i}}{\sum_{i^{\prime}\in[m]}\hat{g}_{i^{\prime},j}\cdot\hat{w}_{i^{\prime}}},$

and our new learned parameters is given by $\mathbf{1}^{m}$.

Note that the fractional allocation remains unchanged, i.e.,
$x_{i,j}(\hat{G},\hat{w})=x_{i,j}(G,\mathbf{1}^{m})=g_{i,j}$, and therefore
the loads are also unchanged:
$\ell_{i}=\ell_{i}(P,\hat{G},\hat{\mathbf{w}})=\ell_{i}(P,G,\mathbf{1}^{m})=\sum_{j\in[n]}g_{i,j}\cdot
p_{i,j}$. Assume w.l.o.g. (by Observation 3.1) that $\gamma=\ell_{1}$, so
$\hat{w}^{\prime}_{i}=\frac{\hat{w}_{i}}{\ell_{i}}\cdot\ell_{1}$. In the
normalized notation, the new parameters are
$w^{\prime}_{i}=\frac{\ell_{1}}{\ell_{i}}$. Again, the allocation is unchanged
whether we use the original notation or the normalized one:

$x_{i,j}(\hat{G},{\bf\hat{w}}^{\prime})=x_{i,j}(G,\mathbf{w}^{\prime})=\frac{g_{i,j}\cdot
w^{\prime}_{i}}{\sum_{i^{\prime}\in[m]}g_{i^{\prime},j}\cdot
w^{\prime}_{i^{\prime}}},$

and we have,
$\ell^{\prime}_{i}=\ell_{i}(P,\hat{G},\hat{\mathbf{w}^{\prime}})=\ell_{i}(P,G,\mathbf{w}^{\prime})$.

The case of Two Agents. First, we consider the case of two agents here, i.e.,
$m=2$. Later, we will show the reduction from general $m$ to $m=2$.

We have

$\displaystyle\ell_{1}=\sum_{j}g_{1,j}\cdot p_{1,j}\qquad\text{ and
}\qquad\ell_{2}=\sum_{j}g_{2,j}\cdot p_{2,j},$

and the parameter for the second agent after the update is given by:
$w^{\prime}_{2}=\frac{\ell_{1}}{\ell_{2}}$ (note that $w^{\prime}_{1}=1)$.

Accordingly, the loads after the update are given by:

$\displaystyle\ell^{\prime}_{1}=\sum_{j}p_{1,j}\cdot\frac{g_{1,j}}{g_{1,j}+w^{\prime}_{2}\cdot
g_{2,j}}\qquad\text{ and
}\qquad\ell^{\prime}_{2}=\sum_{j}p_{2,j}\cdot\frac{w^{\prime}_{2}\cdot
g_{2,j}}{g_{1,j}+w^{\prime}_{2}\cdot g_{2,j}}.$

Assume w.l.o.g that $\ell_{1}<\ell_{2}$. First, note that, from monotonicity
(Observation 3.2) we have:

$\ell^{\prime}_{2}\leq\ell_{2}=\nicefrac{{\ell_{\max}}}{{\left(1+\frac{\ell_{\max}-\ell_{2}}{\tilde{p}_{1}}\right)}}.$

Next, we have to show that

$\ell^{\prime}_{1}\leq\nicefrac{{\ell_{\max}}}{{\left(1+\frac{\ell_{\max}-\ell_{1}}{\tilde{p}_{1}}\right)}}=\nicefrac{{\ell_{2}}}{{\left(1+\frac{\ell_{2}-\ell_{1}}{\tilde{p}_{1}}\right)}}.$
(1)

The proof of the lower bound on $\ell^{\prime}_{1}$ is similar and is omitted
for brevity.

We use the following standard inequality:

######  Fact 3.7 (Milne’s Inequality [milne1925note]).

For any $a,b\in\mathbb{R}^{n}$, we have

$\displaystyle\sum_{j\in[n]}\frac{a_{j}\cdot
b_{j}}{a_{j}+b_{j}}\quad\leq\quad\frac{\displaystyle\sum_{j\in[n]}a_{j}\cdot\displaystyle\sum_{j\in[n]}b_{j}}{\displaystyle\sum_{j\in[n]}{(a_{j}+b_{j})}}.$

In using this inequality, we set for any $j\in[n]$,

$a_{j}=p_{1,j}\text{ and
}b_{j}=p_{1,j}\cdot\left(\frac{f_{j}}{w^{\prime}_{2}}-1\right)\text{ where
}f_{j}=g_{1,j}+w^{\prime}_{2}\cdot
g_{2,j}=g_{1,j}+w^{\prime}_{2}\cdot(1-g_{1,j}).$

First, we calculate each term in Milne’s inequality separately:

$\displaystyle\displaystyle\sum_{j\in[n]}\frac{a_{j}\cdot b_{j}}{a_{j}+b_{j}}$
$\displaystyle=\displaystyle\sum_{j\in[n]}p_{1,j}\cdot\frac{f_{j}-w^{\prime}_{2}}{f_{j}}=\displaystyle\sum_{j\in[n]}p_{1,j}\cdot\frac{g_{1,j}+w^{\prime}_{2}\cdot
g_{2,j}-w^{\prime}_{2}}{f_{j}}=\displaystyle\sum_{j\in[n]}p_{1,j}\cdot\frac{g_{1,j}-w^{\prime}_{2}\cdot(1-g_{2,j})}{f_{j}}$
$\displaystyle=\displaystyle\sum_{j\in[n]}p_{1,j}\cdot\frac{g_{1,j}-w^{\prime}_{2}\cdot
g_{1,j}}{f_{j}}=\displaystyle\sum_{j\in[n]}p_{1,j}\cdot
g_{1,j}\cdot\frac{1-w^{\prime}_{2}}{f_{j}}=\ell^{\prime}_{1}\cdot(1-w^{\prime}_{2}).$
$\displaystyle\displaystyle\sum_{j\in[n]}a_{j}$ $\displaystyle=\tilde{p}_{1}.$
$\displaystyle\displaystyle\sum_{j\in[n]}b_{j}$
$\displaystyle=\displaystyle\sum_{j\in[n]}p_{1,j}\cdot
g_{1,j}\cdot\left(\frac{1}{w^{\prime}_{2}}-1\right)=\frac{\ell_{1}}{w^{\prime}_{2}}-\ell_{1}=\ell_{2}-\ell_{1}=\ell_{2}\cdot(1-w^{\prime}_{2}).$

Using 3.7, we get

$\ell^{\prime}_{1}\cdot(1-w^{\prime}_{2})\leq\frac{\tilde{p}_{1}\cdot\ell_{2}}{\ell_{2}-\ell_{1}+\tilde{p}_{1}}\cdot(1-w^{\prime}_{2})$

By our assumption that $\ell_{1}<\ell_{2}$, and therefore $w^{\prime}_{2}<1$.
We now get Equation 1 by rearranging terms. This completes the proof for the
lemma for the case of two agents.

General case of More than Two Agents. For more than two agents, we again only
show the upper bound; the lower bound follows similarly. We also focus on
agent $1$ which is w.l.o.g. by symmetry. Therefore, we have to show that:

$\ell_{1}^{\prime}\leq\frac{\ell_{\max}}{1+\frac{\ell_{\max}-\ell_{1}}{\tilde{p}_{1}}}.$
(2)

To show this inequality, we use a two-step transformation to an instance with
two agents. In the first step, we change the weight matrix by increasing the
weights of jobs for agents other than agent $1$ so that the loads of all
agents except $1$ becomes $\ell_{\max}$. We argue below that this is w.l.o.g.
In the second step, we transform the instance to two agents, where we
“combine” all the other $m-1$ agents (except agent $1$) to a single row in the
matrices $P$ and $G$ (this represents the second agent in the transformed
instance). Again, we show that we can do this in a way that establishing the
upper bounds on $\ell^{\prime}_{1}$ after the transformation implies Equation
2. Finally, we use Equation 1 to conclude the proof.

First transformation: We assume $G,\mathbf{w}$ are normalized as earlier.
Recall that in this case, we have $\mathbf{w}=\mathbf{1}^{m}$. Consider the
instance $\hat{P},\hat{G}$, where
$\hat{p}_{i,j}=p_{i,j}\cdot\frac{\ell_{\max}}{\ell_{i}}$ and
$\hat{p}_{i,1}=p_{i,1}$, and $\hat{G}=G$. Let the corresponding load in the
transformed instance be denoted
$\hat{\bm{\ell}}=\bm{\ell}(\hat{P},\hat{G},\mathbf{1}^{m})$. By definition,
$\ell_{1}=\hat{\ell}_{1}$, and $\ell_{\max}=\hat{\ell}_{\max}$.

Let, $\hat{w}_{i}=\ell_{1}/\hat{\ell}_{i}$ for all $i\in[m]$. Note that we
have $\hat{w}_{1}=w^{\prime}_{1}=1$ and
$\hat{w}_{i}=\ell_{1}/\ell_{\max}\leq\ell_{1}/\hat{\ell}_{i}=w^{\prime}_{i}$
for $i\geq 2$. By Observation 3.2, we have
$\ell^{\prime}_{1}=\ell_{1}(P,G,\mathbf{w}^{\prime})\leq\ell_{1}(P,G,\hat{\mathbf{w}}^{\prime})=\ell_{1}(\hat{P},\hat{G},\hat{\mathbf{w}}^{\prime})$.
Thus, it suffices to show Equation 2 on the transformed instance.

Second transformation: Now, define
$\tilde{P},\tilde{G}\in\mathbb{R}_{>0}^{2\times n}$ as follows:

$\displaystyle\tilde{g}_{1,j}$ $\displaystyle=$
$\displaystyle\hat{g}_{1,j}\quad=\quad g_{1,j}$ $\displaystyle\tilde{g}_{2,j}$
$\displaystyle=$ $\displaystyle 1-g_{1,j}$ $\displaystyle\tilde{p}_{1,j}$
$\displaystyle=$ $\displaystyle{p}_{1,j}$ $\displaystyle\tilde{p}_{2,j}$
$\displaystyle=$ $\displaystyle\frac{\sum_{i=2}^{m}\hat{p}_{i,j}\cdot
g_{i,j}}{(m-1)\cdot(1-g_{1,i})}.$

Before the update, we update
$\ell_{1}(\hat{P},\hat{G},\mathbf{1}^{m})=\ell_{1}(\tilde{P},\tilde{G},\mathbf{1}^{2})$
since we did not modify the rows in $P$ and $G$ corresponding to agent $1$.
Second, we have

$\ell_{2}(\tilde{P},\tilde{G},\mathbf{1}^{2})=\sum_{j}\tilde{p}_{2,j}\cdot\tilde{g}_{2,j}=\frac{\sum_{i=2}^{m}\hat{p}_{i,j}\cdot
g_{i,j}}{(m-1)\cdot(1-g_{1,i})}\cdot\tilde{g}_{2,j}=\frac{(m-1)\cdot\ell_{\max}}{(m-1)}=\ell_{\max}$

For $\tilde{\mathbf{w}}$ such that, $\tilde{w}^{\prime}_{1}=1$ and
$\tilde{w}^{\prime}_{2}=\hat{\ell}_{1}/\ell_{\max}$, we have

$x_{1,j}(\tilde{G},\tilde{w}^{\prime})=\frac{\tilde{g}_{1,j}}{\tilde{g}_{1,j}+\hat{\ell}_{1}/\ell_{\max}\cdot\tilde{g}_{2,j}}=\frac{g_{1,j}}{g_{1,j}+\hat{\ell}_{1}/\ell_{\max}\cdot\sum_{i=2}^{m}g_{i,j}}=x_{1,j}(\hat{G},\hat{w}^{\prime}).$

Therefore,
$\ell_{1}(\hat{P},\hat{G},\hat{w}^{\prime})=\ell_{1}(\tilde{P},\tilde{G},\tilde{w}^{\prime})$.
Finally, by the case of two agents (Equation 1), we have

$\ell_{1}(\tilde{P},\tilde{G},\tilde{w}^{\prime})\leq\frac{\ell_{\max}}{1+\frac{\ell_{\max}-\ell_{1}}{\tilde{p}_{1}}}$

and therefore

$\ell_{1}(P,G,w^{\prime})\leq\ell_{1}(\hat{P},\hat{G},\hat{w}^{\prime})=\ell_{1}(\tilde{P},\tilde{G},\tilde{w}^{\prime})\leq\frac{\ell_{\max}}{1+\frac{\ell_{\max}-\ell_{1}}{\tilde{p}_{1}}},$

as required.

###  3.3 Strict Monotonicity of the Ratio of the Maximum to Minimum Loads in
Algorithm 1

We will need the following observation, which relates the assignment vectors
for two different parameter vectors. We will use this later to relate the
assignment vectors for an agent before and after a single iteration of
Algorithm 1.

######  Observation 3.8.

Fix any $G\in\mathbb{R}_{>0}^{m\times n}$. Consider two parameter vectors
$\mathbf{w}$ and $\mathbf{w}^{\prime}$ where we denote their coordinate-wise
ratio as $\tau_{i}=\frac{w^{\prime}_{i}}{w_{i}}$ for all $i\in[m]$. Let
$y_{i,j}=x_{i,j}(G,\mathbf{w})$ and $z_{i,j}=x_{i,j}(G,\mathbf{w}^{\prime})$
be the fractional allocations corresponding to the parameter vector
$\mathbf{w},\mathbf{w}^{\prime}$ respectively. Then we have

$z_{i,j}=\frac{\tau_{i}\cdot
y_{i,j}}{\sum_{i^{\prime}\in[m]}\tau_{i^{\prime}}\cdot y_{i^{\prime},j}},$

and

$\frac{y_{i,j}}{z_{i,j}}={\sum_{i^{\prime}\in[m]}\frac{\tau_{i^{\prime}}}{\tau_{i}}\cdot
y_{i^{\prime},j}},$

Next, we show that for fixed matrices $P$ and $G$, the assignment variable
$x_{i,j}$ is at least some fixed value.

######  Lemma 3.9.

Let $P,G\in\mathbb{R}_{>0}^{m\times n}$ be given fixed matrices. Then, for any
iteration $r$ of Algorithm 1 and the corresponding parameter vector
$\mathbf{w}^{(r)}$, we have $x_{i,j}(G,\mathbf{w}^{(r)})\geq x_{\min}$ for
some fixed $x_{\min}>0$ that depends only on $P$ and $G$.

###### Proof.

First, we show that for every iteration $r$ in Algorithm 1, and for any two
agents $i^{\prime},i\in[m]$, the ratio of their respective parameters
$\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}$ is bounded by a term that only
depends on the matrices $P$ and $G$. To obtain this bound, we define two terms
that depend only on the matrices $P$ and $G$. The first term, denoted
$\alpha$, is the ratio of the maximum to minimum load at the beginning of
Algorithm 1, i.e., $\alpha=\frac{\ell_{\max}^{(0)}}{\ell_{\min}^{(0)}}$. The
second term, denoted $\rho_{i,i^{\prime}}$, is specific to the agents
$i,i^{\prime}$ and is defined as
$\rho_{i,i^{\prime}}=\max_{j\in[n]}\biggl{\\{}\frac{p_{i,j}}{p_{i^{\prime},j}}\cdot\frac{g_{i,j}}{g_{i^{\prime},j}}\biggl{\\}}$.
Our goal is to show that for every iteration $r$ of Algorithm 1, we have
$\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}\leq\alpha\cdot\max(\rho_{i,i^{\prime}},1)$.

We show this bound in two steps. First, we show that the ratio
$\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}$ cannot increase by a factor greater
than $\alpha$ in any iteration. Next, we show that if this ratio
$\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}$ exceeds $\rho_{i,i^{\prime}}$ in
any iteration, then it must decrease in the next iteration. Further, observe
that the initial value of this ratio
$\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}$ is 1 for every pair of agents
$i,i^{\prime}\in[m]$ since $w^{(0)}_{i}=1$ for all agents $i\in[m]$. Putting
these together, we can then claim that
$\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}\leq\alpha\cdot\max(\rho_{i,i^{\prime}},1)$
for all iterations $r$ and for any two agents $i,i^{\prime}\in[m]$.

We first prove that $\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}$ cannot increase
by a factor greater than $\alpha$ in any iteration. We have the following:

$\displaystyle\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}$
$\displaystyle=\frac{\ell_{i}^{(r-1)}}{\ell_{i^{\prime}}^{(r-1)}}\cdot\frac{w^{(r-1)}_{i^{\prime}}}{w^{(r-1)}_{i}}\quad$
(by the definition of Algorithm 1)
$\displaystyle\leq\frac{\ell_{\max}^{(r-1)}}{\ell_{\min}^{(r-1)}}\cdot\frac{w^{(r-1)}_{i^{\prime}}}{w^{(r-1)}_{i}}\quad$
(by the definition of $\ell_{\max}$ and $\ell_{\min}$)
$\displaystyle\leq\frac{\ell_{\max}^{(0)}}{\ell_{\min}^{(0)}}\cdot\frac{w^{(r-1)}_{i^{\prime}}}{w^{(r-1)}_{i}}\quad$
(by Lemma 3.5)
$\displaystyle=\alpha\cdot\frac{w^{(r-1)}_{i^{\prime}}}{w^{(r-1)}_{i}}\quad$
$\displaystyle\quad\text{(by the definition of $\alpha$)}.$

Next, we prove that if
$\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}>\rho_{i,i^{\prime}}$ in any
iteration $r$, then the ratio must decrease in the next iteration, i.e.,
$\frac{w^{(r+1)}_{i^{\prime}}}{w^{(r+1)}_{i}}<\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}$.
Note that if $\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}>\rho_{i,i^{\prime}}$,
this implies that

$\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}>\frac{p_{i,j}}{p_{i^{\prime},j}}\cdot\frac{g_{i,j}}{g_{i^{\prime},j}}\quad\text{
for every item }j\in[n],$ (3)

since
$\rho_{i,i^{\prime}}=\max_{j\in[n]}\biggl{\\{}\frac{p_{i,j}}{p_{i^{\prime},j}}\cdot\frac{g_{i,j}}{g_{i^{\prime},j}}\biggl{\\}}$.
Now, by the rules of proportional allocation, we have for every item
$j\in[n]$:

$\frac{x^{(r)}_{i^{\prime},j}}{x^{(r)}_{i,j}}=\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}\cdot\frac{g_{i^{\prime},j}}{g_{i,j}}>\left(\frac{p_{i,j}}{p_{i^{\prime},j}}\cdot\frac{g_{i,j}}{g_{i^{\prime},j}}\right)\cdot\frac{g_{i^{\prime},j}}{g_{i,j}}=\frac{p_{i,j}}{p_{i^{\prime},j}}\quad\text{(the
inequality is from \lx@cref{creftypecap~refnum}{eq:cond})}.$

Then, the loads of the agents $i,i^{\prime}$ in iteration $r$ of Algorithm 1
satisfy

$\ell^{(r)}_{i}=\sum_{j\in[n]}x^{(r)}_{i,j}\cdot
p_{i,j}<\sum_{j\in[n]}x^{(r)}_{i^{\prime},j}\cdot
p_{i^{\prime},j}=\ell^{(r)}_{i^{\prime}}.$

Then,

$\frac{w^{(r+1)}_{i^{\prime}}}{w^{(r+1)}_{i}}=\frac{\ell_{i}^{(r)}}{\ell_{i^{\prime}}^{(r)}}\cdot\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}<\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}.$

We have now shown
$\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}\leq\alpha\cdot\max(\rho_{i,i^{\prime}},1)$
for all iterations $r$ and for any two agents $i,i^{\prime}\in[m]$. In other
words, $\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}\leq\tau$, where we define
$\tau:=\alpha\cdot\max\biggl{(}\max_{i,i^{\prime}}\rho_{i,i^{\prime}},1\bigg{)}$.

Now, recall that

$x^{(r)}_{i,j}=\frac{w^{(r)}_{i}\cdot
g_{i,j}}{\sum_{i^{\prime}}w^{(r)}_{i^{\prime}}\cdot
g_{i^{\prime},j}}=\frac{g_{i,j}}{g_{i,j}+\sum_{i^{\prime}\not=i}\left(\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}\right)\cdot
g_{i^{\prime},j}}\geq\frac{g_{i,j}}{g_{i,j}+\sum_{i^{\prime}\not=i}\tau\cdot
g_{i^{\prime},j}},\text{ since
}\frac{w^{(r)}_{i^{\prime}}}{w^{(r)}_{i}}\leq\tau.$

To complete the proof, we define
$x_{\min}=\min_{i,j}\frac{g_{i,j}}{g_{i,j}+\sum_{i^{\prime}\not=i}\tau\cdot
g_{i^{\prime},j}}$. Note that $x_{\min}$ only depends on $P$ and $G$ as
required by the lemma. ∎

We are now ready to show the strict monotonicity property. Note that since
$\ell_{\max}^{(r+1)}\leq\ell_{\max}^{(r)}$ by the weak monotonicity property
(Lemma 3.5), it suffices to show that $\ell_{\min}^{(r+1)}-\ell_{\min}^{(r)}$
is sufficiently large so that the ratio
$\nicefrac{{\ell_{\max}}}{{\ell_{\min}}}$ converges to 1. We bound the
increase in $\ell_{\min}$ in the next lemma, and then show the convergence in
the proof of Theorem 2.2.

###### Proof of Lemma 3.6.

We will prove that the minimum load $\ell_{\min}$ will strictly increase in
the next iteration; specifically that
$\ell_{\min}^{(r+1)}\geq(1+c\cdot\epsilon)\cdot\ell_{\min}^{(r)}$, for some
constant $c>0$ that only depends on $P$ and $G$.

Let $\delta=x_{\min}\cdot\big{(}1-\frac{1}{1+{\epsilon}}\big{)}$, where
$x_{\min}$ is as defined in Lemma 3.9. We divide the agents into two sets: the
light agents
$S_{s}=\left\\{i\in[m]:\ell^{(r)}_{i}\leq(1+\delta)\cdot\ell_{\min}^{(r)}\right\\}$
and the heavy agents
$S_{t}=\left\\{i\in[m]:\ell^{(r)}_{i}>(1+\delta)\cdot\ell_{\min}^{(r)}\right\\}$.
The bulk of our proof bounds the increase in the load of every light agent
$i\in S_{s}$. For every heavy agent $i\in S_{t}$, we use Lemma 3.5 to show
that its load in iteration $r+1$ is sufficiently large. Putting these together
yields the lemma.

First, let us consider a light agent $i\in S_{s}$. For each item $j\in[n]$,
define $y_{i,j}=x_{i,j}(G,\mathbf{w}^{(r)})$ and
$z_{i,j}=x_{i,j}(G,\mathbf{w}^{(r+1)})$. First, we show that for each item
$j\in[n]$,

$z_{i,j}-y_{i,j}\geq x_{\min}^{2}\cdot\delta.$ (4)

For any agent $i\in[m]$, let $\tau_{i}=\frac{w_{i}^{(r+1)}}{w_{i}^{(r)}}$.
Then, we have:

$\displaystyle\frac{y_{i,j}}{z_{i,j}}$ $\displaystyle=$
$\displaystyle\frac{\sum_{i^{\prime}\in[m]}\tau_{i^{\prime}}\cdot
y_{i^{\prime},j}}{\tau_{i}}\qquad\text{(By
\lx@cref{creftypecap~refnum}{obv:xval})}$ $\displaystyle=$
$\displaystyle\sum_{i^{\prime}\in[m]}\frac{w_{i^{\prime}}^{(r+1)}}{w_{i^{\prime}}^{(r)}}\cdot\frac{w_{i}^{(r)}}{w_{i}^{(r+1)}}\cdot
y_{i^{\prime},j}=\displaystyle\sum_{i^{\prime}\in[m]}\frac{\ell^{(r)}_{i}}{\ell^{(r)}_{i^{\prime}}}\cdot
y_{i^{\prime},j}\qquad\text{(By the definition of
\lx@cref{creftypecap~refnum}{alg:iterative})}.$

Now, let $k$ be an agent with maximum load in iteration $r$, i.e,
$k\in\arg\max_{i}\ell^{(r)}_{i}$. We rewrite the above equation as:

$\displaystyle\frac{y_{i,j}}{z_{i,j}}$ $\displaystyle=$ $\displaystyle
y_{i,j}+y_{k,j}\cdot\frac{\ell_{i}^{(r)}}{\ell_{\max}^{(r)}}+\sum_{i^{\prime}\in[m]\setminus\\{i,k\\}}\frac{\ell^{(r)}_{i}}{\ell^{(r)}_{i^{\prime}}}\cdot
y_{i^{\prime},j}$ $\displaystyle\leq$ $\displaystyle
y_{i,j}+y_{k,j}\cdot\frac{\ell_{i}^{(r)}}{\ell_{\max}^{(r)}}+\frac{\ell^{(r)}_{i}}{\ell_{\min}^{(r)}}\cdot\sum_{i^{\prime}\in[m]\setminus\\{i,k\\}}y_{i^{\prime},j}\quad\text{(since
$\ell^{(r)}_{i^{\prime}}\geq\ell_{\min}^{(r)}$ for all $i^{\prime}\in[m]$)}$
$\displaystyle\leq$ $\displaystyle 1\cdot
y_{i,j}+\frac{\ell_{i}^{(r)}}{\ell_{\max}^{(r)}}\cdot
y_{k,j}+\frac{\ell^{(r)}_{i}}{\ell_{\min}^{(r)}}\cdot\left(\sum_{i^{\prime}\in[m]\setminus\\{i,k\\}}y_{i^{\prime},j}\right).$

Now, note that
$\sum_{i}y_{i,j}=y_{i,j}+y_{k,j}+\sum_{i^{\prime}\in[m]\setminus\\{i,k\\}}y_{i^{\prime},j}=1$,
i.e., the RHS of the above inequality is a convex combination of
$1,\frac{\ell_{i}^{(r)}}{\ell_{\max}^{(r)}}$, and
$\frac{\ell^{(r)}_{i}}{\ell_{\min}^{(r)}}$. Now, since
$\frac{\ell_{i}^{(r)}}{\ell_{\max}^{(r)}}\leq
1\leq\frac{\ell^{(r)}_{i}}{\ell_{\min}^{(r)}}$, this expression is maximized
when $y_{i,j}$ and $y_{k,j}$ are minimized. By Lemma 3.9, we know
$y_{i,j},y_{k,j}\geq x_{\min}$. Hence, we can write

$\displaystyle\frac{y_{i,j}}{z_{i,j}}$ $\displaystyle\leq
x_{\min}+x_{\min}\cdot\frac{\ell_{i}^{(r)}}{\ell_{\max}^{(r)}}+(1-2\cdot
x_{\min})\cdot\frac{\ell_{i}^{(r)}}{\ell_{\min}^{(r)}}$ $\displaystyle\leq
x_{\min}+x_{\min}\cdot\frac{1+\delta}{1+\epsilon}+(1-2\cdot
x_{\min})\cdot(1+\delta)$ (since $i\in S_{s}$,
$\ell^{(r)}_{i}\leq(1+\delta)\cdot\ell_{\min}^{(r)}$, and by definition of
$\epsilon$, $\ell_{\max}^{(r)}\geq(1+\epsilon)\cdot\ell_{\min}^{(r)}$)
$\displaystyle=x_{\min}+\frac{x_{\min}}{1+\epsilon}+\frac{x_{\min}\cdot\delta}{1+\epsilon}+1+\delta-2\cdot
x_{\min}-2\cdot x_{\min}\cdot\delta$ $\displaystyle\leq
x_{\min}+\frac{x_{\min}}{1+\epsilon}+x_{\min}\cdot\delta+1+\delta-2\cdot
x_{\min}-2\cdot x_{\min}\cdot\delta\qquad\qquad\text{(Since $\epsilon>0$)}$
$\displaystyle=1-x_{\min}\cdot\delta+\delta-
x_{\min}\cdot(1-\nicefrac{{1}}{{1+\epsilon}})$
$\displaystyle=1-x_{\min}\cdot\delta.\qquad\qquad\text{(By the definition of
$\delta$ )}$

Therefore, for any $i\in S_{s}$ and for any $j\in[n]$,

$\frac{z_{i,j}}{y_{i,j}}\geq\frac{1}{1-x_{\min}\cdot\delta}\geq
1+x_{\min}\cdot\delta.$

Note that $y_{i,j}\geq x_{\min}$ by Lemma 3.9. Hence, $z_{i,j}-y_{i,j}\geq
x_{\min}^{2}\cdot\delta$. This establishes Equation 4.

Now, recall that $\tilde{p}_{i}=\sum_{j}p_{i,j}$ for all $i\in[m]$. Now, let
$\tilde{p}_{\min}=\displaystyle\min_{i\in[n]}\tilde{p}_{i}$. We have

$\ell_{i}^{(r+1)}=\ell_{i}^{(r)}+\sum_{j\in[n]}(z_{i,j}-y_{i,j})\cdot
p_{i,j}\geq\ell_{\min}^{(r)}+\delta\cdot
x_{\min}^{2}\cdot\tilde{p}_{\min}\quad\text{(by
\lx@cref{creftypecap~refnum}{eq:diff})}.$

Now, let $c_{3}=x_{\min}^{2}\cdot\frac{\tilde{p}_{\min}}{\ell_{\max}^{(0)}}$.
By Lemma 3.5, we have $c_{3}\leq
x_{\min}^{2}\cdot\frac{\tilde{p}_{\min}}{\ell_{\max}^{(r)}}$, and therefore,
$c_{3}\leq x_{\min}^{2}\cdot\frac{\tilde{p}_{\min}}{\ell_{\min}^{(r)}}$ since
$\ell_{\min}^{(r)}\leq\ell_{\max}^{(r)}$. Therefore, we can write the above
inequality as:

$\ell_{i}^{(r+1)}\geq\ell_{\min}^{(r)}+\delta\cdot
x_{\min}^{2}\cdot\tilde{p}_{\min}\geq(1+c_{3}\cdot\delta)\cdot\ell_{\min}^{(r)}\quad\text{for
all light agents }i\in S_{s}.$

Note that $c_{3}$ depends only on $P$ and $G$.

Finally, we consider heavy agents. Let
$c_{4}=\ell_{\min}^{(0)}\cdot\min_{i\in[m]}\frac{1}{\tilde{p}_{i}}\leq\ell_{\min}^{(r)}\cdot\min_{i\in[m]}\frac{1}{\tilde{p}_{i}}$
by Lemma 3.5. For all $i\in S_{t}$, we have

$\displaystyle\ell_{i}^{(r+1)}$ $\displaystyle\geq$
$\displaystyle\frac{\ell_{\min}^{(r)}}{\left(1-\frac{\ell^{(r)}_{i}-\ell_{\min}^{(r)}}{\tilde{p}_{i}}\right)}\qquad\text{(by
\lx@cref{creftypecap~refnum}{lem:notincreasing})}$ $\displaystyle\geq$
$\displaystyle\ell_{\min}^{(r)}\cdot{\left(1+\frac{\ell^{(r)}_{i}-\ell_{\min}^{(r)}}{\tilde{p}_{i}}\right)}\qquad\text{}$
$\displaystyle\geq$
$\displaystyle\ell_{\min}^{(r)}\cdot\left(1+\ell_{\min}^{(r)}\cdot\frac{\delta}{\tilde{p}_{i}}\right)\qquad\text{(since
$i\in S_{t}$)}$ $\displaystyle\geq$
$\displaystyle\ell_{\min}^{(r)}\cdot(1+c_{4}\cdot\delta).$

Thus, we have established that for all agents $i\in[m]$, we have

$\ell_{i}^{(r+1)}\geq(1+\min(c_{3},c_{4})\cdot\delta))\cdot\ell_{\min}^{(r)}.$

Now, $\delta=\frac{\epsilon}{1+\epsilon}\cdot
x_{\min}\geq(\nicefrac{{\epsilon}}{{2}})\cdot x_{\min}$ since
$\epsilon\in(0,1]$. Let us define
$c=\min(c_{3},c_{4})\cdot(\nicefrac{{x_{\min}}}{{2}})$. Therefore, we get that
for all agents $i\in[m]$, it holds that

$\ell_{i}^{(r+1)}\geq(1+c\cdot\epsilon)\cdot\ell_{\min}^{(r)},\text{ as
desired}.$

∎

##  4 Monotonicity and Convergence of Exponentiated Proportional Allocations

In this section, we prove the monotonicity and convergence of EP-allocations
(Theorem 2.3).

First, we establish monotonicity of EP-allocations (first part of Theorem
2.3). We compare two EP-allocations with arbitrary learned parameters but
different exponential constants. We show that with a larger exponent, at least
one agent’s load will be higher, regardless of the parameters used.

######  Lemma 4.1.

Fix a weight matrix $P\in\mathbb{R}_{>0}^{m\times n}$. Let
$\alpha,{{\alpha^{\prime}}}\in\mathbb{R}$ such that
$\alpha>{\alpha^{\prime}}$. Now, for any two sets of learned parameters
$\mathbf{w}_{\alpha},\mathbf{w}_{\alpha^{\prime}}\in\mathbb{R}_{>0}^{m}$,
there exists an agent $k\in[m]$ such that

$\ell_{k}(P,\alpha,\mathbf{w}_{\alpha})\geq\ell_{k}(P,{\alpha^{\prime}},\mathbf{w}_{\alpha^{\prime}}).$

###### Proof.

Let $\Delta$ denote the vector of differences of loads of the machines in the
two allocations, namely
$\Delta_{i}=\ell_{i}(P,\alpha,\mathbf{w}_{\alpha})-\ell_{i}(P,{\alpha^{\prime}},\mathbf{w}_{\alpha^{\prime}})$.
Our goal is to show that $\Delta$ has at least one nonnegative coordinate.

To show this, we define a vector in the positive orthant
$\mathbf{c}\in\mathbb{R}_{>0}^{m}$ as follows:

$c_{i}=\left(\frac{w_{\alpha,i}}{w_{{\alpha^{\prime}},i}}\right)^{\frac{1}{\rho}},\text{
where }\rho=\alpha-{\alpha^{\prime}}>0$

and show that this vector $\bf c$ has a nonnegative inner product with the
vector $\Delta$. Note that this suffices since the inner product of a vector
with all positive coordinates and one with all negative coordinates cannot be
nonnegative. In other words, we want to show the following:

$\sum_{i\in[m]}c_{i}\cdot(\ell_{i}(P,\alpha,w_{\alpha})-\ell_{i}(P,{\alpha^{\prime}},w_{\alpha^{\prime}}))\geq
0.$ (5)

Let us denote the fractional allocation of an item $j$ in the two cases by
$x_{i,j}$ and $x^{\prime}_{i,j}$ respectively. Then, Equation 5 can be
rewritten as

$\sum_{i\in[m]}c_{i}\cdot\sum_{j\in[n]}p_{i,j}\cdot(x_{i,j}-x^{\prime}_{i,j})\geq
0.$

Changing the order of the two summations, we rewrite further as

$\sum_{j\in[n]}\left(\sum_{i\in[m]}c_{i}\cdot
p_{i,j}\cdot(x_{i,j}-x^{\prime}_{i,j})\right)\geq 0.$

We will prove this inequality separately for each item $j\in[n]$. Namely, we
will show that

$\sum_{i\in[m]}c_{i}\cdot p_{i,j}\cdot(x_{i,j}-x^{\prime}_{i,j})\geq 0,\text{
for every }j\in[n].$ (6)

Fix an item $j$. Since the item is fixed, we will drop $j$ from the notation
and define $\mathbf{u}\in\mathbb{R}^{m}$ as

$u_{i}=p_{i}\cdot(x_{i}-x^{\prime}_{i}).$

So, we need to show that

${\bf c}\cdot\mathbf{u}\geq 0,\text{ i.e., }\sum_{i\in[m]}c_{i}\cdot u_{i}\geq
0.$ (7)

We have

$\displaystyle\sum_{i}c_{i}\cdot u_{i}$ $\displaystyle=$
$\displaystyle\sum_{i}{c_{i}\cdot p_{i}\cdot\left(\frac{p_{i}^{\alpha}\cdot
w_{\alpha,i}}{\sum_{i^{\prime}}p_{i^{\prime}}^{\alpha}\cdot
w_{\alpha,i^{\prime}}}-\frac{p_{i}^{\alpha^{\prime}}\cdot
w_{{\alpha^{\prime}},i}}{\sum_{i^{\prime}}p_{i^{\prime}}^{\alpha^{\prime}}\cdot
w_{{\alpha^{\prime}},i^{\prime}}}\right)}$ $\displaystyle=$
$\displaystyle\frac{1}{T}\cdot\sum_{i}{c_{i}\cdot
p_{i}\cdot\left({p_{i}^{\alpha}\cdot
w_{\alpha,i}\cdot\left(\sum_{i^{\prime}}p_{i^{\prime}}^{\alpha^{\prime}}\cdot
w_{{\alpha^{\prime}},i^{\prime}}\right)-p_{i}^{\alpha^{\prime}}\cdot
w_{{\alpha^{\prime}},i}\cdot\left(\sum_{i^{\prime}}p_{i^{\prime}}^{\alpha}\cdot
w_{\alpha,i^{\prime}}\right)}\right)}$ $\displaystyle\qquad\text{ where
}T=\left(\sum_{i^{\prime}}p_{i^{\prime}}^{\alpha^{\prime}}\cdot
w_{{\alpha^{\prime}},i^{\prime}}\right)\cdot\left(\sum_{i^{\prime}}p_{i^{\prime}}^{\alpha}\cdot
w_{\alpha,i^{\prime}}\right).$

Now, on the right hand side of the above equation, we replace $\alpha$ by
$\alpha^{\prime}+\rho$ and $w_{\alpha,i}$ by $w_{\alpha^{\prime},i}\cdot
c_{i}^{\rho}$ for every $i\in[m]$. This gives us:

$\displaystyle\sum_{i}c_{i}\cdot u_{i}=$
$\displaystyle\frac{1}{T}\sum_{i}{c_{i}\cdot
p_{i}\left({p_{i}^{\alpha^{\prime}}\cdot p_{i}^{\rho}\cdot
w_{{\alpha^{\prime}},i}\cdot
c_{i}^{\rho}\left(\sum_{i^{\prime}}p_{i^{\prime}}^{\alpha^{\prime}}\cdot
w_{{\alpha^{\prime}},i^{\prime}}\right)-p_{i}^{\alpha^{\prime}}\cdot
w_{{\alpha^{\prime}},i}\left(\sum_{i^{\prime}}p_{i^{\prime}}^{\alpha^{\prime}}\cdot
p_{i^{\prime}}^{\rho}\cdot w_{{\alpha^{\prime}},i^{\prime}}\cdot
c_{i^{\prime}}^{\rho}\right)}\right)}$
$\displaystyle=\frac{1}{T}\sum_{i}{b_{i}\left({a_{i}\cdot
b_{i}^{\rho}\left(\sum_{i^{\prime}}a_{i^{\prime}}\right)-a_{i}\left(\sum_{i^{\prime}}a_{i^{\prime}}\cdot
b_{i^{\prime}}^{\rho}\right)}\right)},$ $\displaystyle\qquad\text{ where
}a_{i}=w_{{\alpha^{\prime}},i}\cdot p_{i}^{\alpha^{\prime}}\text{ and
}b_{i}=p_{i}\cdot c_{i}.$

Rearranging the summations on the two terms on the right hand side, we get

$\sum_{i}c_{i}\cdot
u_{i}=\frac{1}{T}\cdot\left(\sum_{i^{\prime}}a_{i^{\prime}}\right)\cdot\sum_{i}{a_{i}\cdot
b_{i}^{\rho+1}}-\frac{1}{T}\cdot\left(\sum_{i^{\prime}}a_{i^{\prime}}\cdot
b_{i^{\prime}}^{\rho}\right)\cdot\sum_{i}{a_{i}\cdot b_{i}}$

Now, let $z_{i}=a_{i}^{1/2}$, and $y_{i}=a_{i}^{1/2}\cdot b_{i}^{\rho/2+1/2}$,
and $\theta=\frac{|\rho-1|}{\rho+1}$. Then, we have

$\displaystyle T\cdot\sum_{i}c_{i}\cdot u_{i}$ $\displaystyle=$
$\displaystyle\left(\sum_{i^{\prime}}a_{i^{\prime}}\right)\cdot\left(\sum_{i}{a_{i}\cdot
b_{i}^{\rho+1}}\right)-\left(\sum_{i^{\prime}}a_{i^{\prime}}\cdot
b_{i^{\prime}}^{\rho}\right)\cdot\left(\sum_{i}{a_{i}\cdot b_{i}}\right)$
$\displaystyle=$
$\displaystyle\left(\sum_{i^{\prime}}z_{i^{\prime}}^{2}\right)\cdot\left(\sum_{i}{y_{i}^{2}}\right)-\left(\sum_{i^{\prime}}z_{i^{\prime}}^{1+\theta}\cdot
y_{i^{\prime}}^{1-\theta}\right)\cdot\left(\sum_{i}{z_{i}^{1-\theta}\cdot
y_{i}^{1+\theta}}\right).$

In the last equation, the first term follows directly from
$a_{i^{\prime}}=z_{i^{\prime}}^{2}$ and $a_{i}\cdot b_{i}^{\rho+1}=y_{i}^{2}$.
The second term is more complicated. There are two cases. If $\rho\leq 1$,
then $a_{i^{\prime}}\cdot b_{i^{\prime}}^{\rho}=z_{i^{\prime}}^{1+\theta}\cdot
y_{i^{\prime}}^{1-\theta}$ and $a_{i}\cdot b_{i}=z_{i}^{1-\theta}\cdot
y_{i}^{1+\theta}$ but if $\rho>1$, then the roles get reversed and we get
$a_{i^{\prime}}\cdot b_{i^{\prime}}^{\rho}=z_{i^{\prime}}^{1-\theta}\cdot
y_{i^{\prime}}^{1+\theta}$ and $a_{i}\cdot b_{i}=z_{i}^{1+\theta}\cdot
y_{i}^{1-\theta}$.

Now, note that $T\geq 0$. So, to establish $\sum_{i}c_{i}\cdot u_{i}\geq 0$,
it suffices to show that the right hard side of the equation is nonnegative.
We do so by employing Callebaut’s inequality which we state below:

######  Fact 4.2 (Callebaut’s Inequality [callebaut1965generalization]).

For any $y,z\in\mathbb{R}^{n}$ and $\theta\leq 1$, we have

$\left(\sum_{i^{\prime}}z_{i^{\prime}}^{2}\right)\cdot\left(\sum_{i}{y_{i}^{2}}\right)\geq\left(\sum_{i^{\prime}}z_{i^{\prime}}^{1+\theta}\cdot
y_{i^{\prime}}^{1-\theta}\right)\cdot\left(\sum_{i}{z_{i}^{1-\theta}\cdot
y_{i}^{1+\theta}}\right)$

Note that we can apply Callebaut’s inequality because $\rho\geq 0$ implies
that $\theta\leq 1$. This completes the proof of the lemma.

∎

######  Lemma 4.3.

Given any weight matrix $P\in\mathbb{R}_{>0}^{m\times n}$ and any constant
$\epsilon>0$,

  1. (a)

there exists an $\alpha$ (think of $\alpha$ as a sufficiently large negative
number) and a corresponding set of parameters $\mathbf{w}_{\alpha}$ such that
$\ell_{i}(P,\alpha,w_{\alpha})\leq(1+\epsilon)\cdot\ell^{\textbf{MKS}}(P)$ for
all $i\in[m]$.

  2. (b)

there exists an $\alpha^{\prime}$ (think of $\alpha^{\prime}$ as a
sufficiently large positive number) and a corresponding set of parameters
$\mathbf{w}_{\alpha^{\prime}}$ such that
$\ell_{i}(P,\alpha^{\prime},w_{\alpha^{\prime}})\geq(1-\epsilon)\cdot\ell^{\textbf{SNT}}(P)$
for all $i\in[m]$.

Using Lemma 4.3, we complete the proof of Theorem 2.3.

###### Proof of Theorem 2.3.

First by Lemma 3.3, there exists $\mathbf{w}^{*}_{\alpha}$ and
$\mathbf{w}^{*}_{\alpha^{\prime}}$, such that, for all $i\in[m]$,
$\ell_{i}(P,\alpha,\mathbf{w}^{*}_{\alpha})=\ell^{*}(P,\alpha)$ and
$\ell_{i}(P,{\alpha^{\prime}},\mathbf{w}^{*}_{\alpha^{\prime}})=\ell^{*}(P,{\alpha^{\prime}})$.
Now, if $\ell^{*}(P,\alpha)<\ell^{*}(P,{\alpha^{\prime}})$, it would
contradict Lemma 4.1. And combining Lemma 4.1 and Lemma 4.3, we completed the
proof the second part of Theorem 2.3.

∎

###  4.1 Proof of Lemma 4.3

We will only prove property (a) in Lemma 4.3 for the MinMax problem. Property
(b) for the MaxMin problem has a symmetric proof which is omitted for brevity.

Properties of an optimal Solution for the MinMax problem. First, we establish
some properties of an optimal solution. First, we prove the following simple
property:

######  Lemma 4.4.

Given a weight matrix $P$, the load of every agent $i\in[m]$ in any optimal
allocation must be exactly equal to the objective value
$\ell^{\textbf{MKS}}(P)$.

###### Proof.

If not and there is some agent $k$ with a strictly lower load, then we can
remove an infinitesimally small allocation of items from every other agent and
assign it to agent $k$ to reduce the objective of the overall allocation. ∎

Now, given a weight matrix $P\in\mathbb{R}_{>0}^{m}$ and an optimal solution
$x^{*}$ for the MinMax objective, we define an auxiliary directed graph
$G_{x^{*}}(V,E)$ as follows:

  * •

The set of vertices $V=[m]\cup\\{0\\}$, i.e., the agents and a special vertex
labeled $0$.

  * •

The set of edges $E=([m]\times[m])\cup(\\{0\\}\times[m])$, i.e., all edges
between (ordered) pairs of vertices representing the agents (including self
loops) and edges from the special vertex to all the vertices representing the
agents. Note that the set of vertices and edges does not depend on $x^{*}$.

  * •

We now define a cost function on the edges that does depend on $x^{*}$. Edges
in $[m]\times[m]$ have the following costs:

$c_{i,k}=\ln\left(\min_{j\in[n]}\left\\{\frac{p_{k,j}}{p_{i,j}}\;\bigg{|}\;x^{*}_{i,j}>0\right\\}\right).$

In other words, the cost of an edge $(i,k)$ is the logarithm of the minimum
ratio of the weight of an item for $k$ to that for $i$ among those items that
have a non-zero allocation to agent $i$ in $x^{*}$. In addition, all edges
incident on the special vertex have cost $0$, i.e., $c_{0,k}=0$ for all
$k\in[m]$.

Next, we will show that this graph $G_{x^{*}}$ does not contain a negative
cycle, i.e. a cycle whose edge costs sum to a negative value.

######  Lemma 4.5.

Given a processing matrix $P$ and an optimal solution $x^{*}$ resulting in an
objective value of $\ell^{\textbf{MKS}}(P)$ for the MinMax problem, the
auxiliary graph $G_{x^{*}}$ does not contain a negative cycle.

###### Proof.

Suppose not, and let $i_{1},\dots,i_{k},i_{k+1}(=i_{1})$ be a negative cycle
in $G_{x^{*}}$. Now, let $j_{1},\dots j_{k}$ be the items that determine the
edges costs in this cycle, i.e.
$j_{r}=\arg\min_{j\in[n]}\left\\{\frac{p_{i_{r+1},j}}{p_{i_{r},j}}\;\big{|}\;x^{*}_{i_{r},j}>0\right\\}$.
We have:

$\sum_{r=1}^{k}c_{i_{r},i_{r+1}}=\sum_{r=1}^{k}\ln\left(\frac{p_{i_{r+1},j_{r}}}{p_{i_{r},j_{r}}}\right)=\ln\left(\prod_{r=1}^{k}\frac{p_{i_{r+1},j_{r}}}{p_{i_{r},j_{r}}}\right)<0$
(8)

Now, define an alternate allocation $x^{\prime}$ where
$x^{\prime}_{i_{r},j_{r}}=x^{*}_{i_{r},j_{r}}-\epsilon_{r}$,
$x^{\prime}_{i_{r+1},j_{r}}=x^{*}_{i_{r+1},j_{r}}+\epsilon_{r}$, and
$x^{\prime}_{i,j}=x^{*}_{i,j}$ for all other $i,j$ pairs. Set
$\epsilon_{r+1}=\epsilon_{r}\cdot\frac{p_{i_{r+1},j_{r}}}{p_{i_{r+1},j_{r+1}}}$
with $\epsilon_{1}>0$ being chosen small enough such that $x^{\prime}$ is a
feasible solution (i.e., none of the allocations is negative in $x^{\prime}$).
Note that $x^{*}_{i_{r},j_{r}}>0$ and therefore $x^{*}_{i_{r+1},j_{r}}<1$
which implies that such an $\epsilon_{1}$ exists.

Now, for $r\in[k-1]$ we have
$\ell^{\prime}_{i_{r+1}}-\ell^{*}_{i_{r+1}}=\epsilon_{r}\cdot
p_{i_{r+1},j_{r}}-\epsilon_{r+1}\cdot p_{i_{r+1},j_{r+1}}=0$. This leaves us
to compare the load of $i_{1}$ in the two allocations. We have

$\ell^{\prime}_{i_{1}}-\ell^{*}_{i_{1}}=\epsilon_{k}\cdot
p_{i_{1},j_{k}}-\epsilon_{1}\cdot p_{i_{1},j_{1}}=\epsilon_{1}\cdot
p_{i_{1},j_{1}}\cdot\left(\frac{p_{i_{1},j_{k}}}{p_{i_{1},j_{1}}}\cdot\prod_{r=1}^{k-1}\frac{p_{j_{r},i_{r+1}}}{p_{j_{r+1},i_{r+1}}}-1\right)=\epsilon_{1}\cdot
p_{i_{1},j_{1}}\cdot\left(\prod_{r=1}^{k}\frac{p_{i_{r+1,j_{r}}}}{p_{i_{r},j_{r}}}-1\right)<0,$

where the last inequality is by (8).

This means that the load of an agent can be decreased while keeping all other
agents at the same load. But, by Lemma 4.4, all agents must have equal load
before this modification since we started with an optimal allocation. This
means that after the modification, there is an optimal solution (note that the
maximum load has not increased) where the load of agent $i_{1}$ is lower than
the optimal objective $\ell^{\textbf{MKS}}(P)$. This contradicts Lemma 4.4 and
therefore completes the proof of this lemma. ∎

For any agent $i\in[m]$, Lemma 4.5 allows us to define $c^{*}_{i}$ as the
minimum cost of a path from vertex $0$ to vertex $i$ in the auxiliary graph
$G_{x^{*}}$. We now define a ratio vector $\mathbf{u}\in\mathbb{R}_{>0}^{m}$,
where $u_{i}=e^{c^{*}_{i}}$. Our next goal is to show that in the solution
$x^{*}$, the set of agents $S_{j}$ that an item $j\in[n]$ is allocated to
(i.e., $x^{*}_{i,j}>0$ if and only if $i\in S_{j}$) is given by
$S_{j}=\operatorname{argmin}_{i\in[m]}\left(\frac{p_{i,j}}{u_{i}}\right)$.

######  Lemma 4.6.

Given a weight matrix $P$ and an optimal solution $x^{*}$ resulting in
$\ell^{\textbf{MKS}}(P)$ load, we have that any $i\in[m]$, $j\in[n]$, if there
exists some agent $k\in[m]$ such that
$\frac{p_{k,j}}{u_{k}}<\frac{p_{i,j}}{u_{i}}$, then $x^{*}_{i,j}=0$.

###### Proof.

Suppose not. Then, by definition the cost of edge $(i,k)$ in the auxiliary
graph $G_{x^{*}}$ satisfies

$c_{i,k}\leq\ln\left(\frac{p_{k,j}}{p_{i,j}}\right)<\ln(u_{k})-\ln(u_{i})$

while

$c^{*}_{k}\leq
c^{*}_{i}+c_{i,k}<\ln(u_{i})+\ln(u_{k})-\ln(u_{i})=\ln(u_{k})=c^{*}_{k},$

which is a contradiction. ∎

The following is an immediate corollary:

######  Corollary 4.7.

For any item $j\in[n]$ and agent $i\in[m]$ such that $x^{*}_{i,j}>0$, it must
be that $i\in S_{j}$ where
$S_{j}=\arg\min\left\\{i\in[m]:\frac{p_{i,j}}{u_{i}}\right\\}$.

Transforming to a restricted related instance. We now introduce a special
category of instances of the allocation problem that we call restricted
related instances. Such an instance is characterized by a weight vector
$\mathbf{p}\in\mathbb{R}_{>0}^{n}$ defined on the items, a speed vector
$\mathbf{v}\in\mathbb{R}_{>0}^{m}$ defined on the agents, and a binary matrix
$E\in\\{0,1\\}^{m\times n}$ called the admissibility matrix. Then, the weight
$p_{i,j}$ of item $j\in[n]$ for agent $i\in[m]$ is given by the following:

$p_{i,j}=\begin{cases}\frac{p_{j}}{v_{i}}&\text{ if }E_{i,j}=1\\\
\infty&\text{ if }E_{i,j}=0.\end{cases}$

Corollary 4.7 allows us to convert any (general) weight matrix
$P\in\mathbb{R}_{>0}^{m\times n}$ to a restricted related instance while
preserving the value of $\ell^{\textbf{MKS}}(P)$. Let
$P^{\prime}\in\mathbb{R}_{>0}^{m\times n}$ be the weight matrix for the
restricted related instance that we construct. Then, we require that the
weights for agent-item pairs $i\in[n],j\in[m]$ such that $x^{*}_{i,j}>0$ are
preserved, while those for the remaining agent-item pairs are made infinite.
Clearly, the optimal assignment $x^{*}$ continues to have the same objective
value $\ell^{\textbf{MKS}}$ after this transformation.

To see why these weights form a restricted related instance, we define the
following:

  * •

a weight vector $\hat{\mathbf{p}}\in\mathbb{R}_{>0}^{n}$ where
$\hat{p}_{j}=\frac{p_{i,j}}{u_{i}}$ for any $i\in S_{j}$. (Note that by
Corollary 4.7, we get the same value of $\hat{p}_{j}$ no matter which agent
$i\in S_{j}$ is chosen.)

  * •

a speed vector $\hat{\mathbf{v}}\in\mathbb{R}_{>0}^{m}$ where
$\hat{v}_{i}=\frac{1}{u_{i}}$. (Note that this implies that the weight of an
item $j\in[n]$ for an agent $i\in S_{j}$ remains unchanged at $p_{i,j}$.)

  * •

an admissibility matrix $\hat{E}\in\\{0,1\\}^{m\times n}$ where
$\hat{E}_{i,j}=1$ if $i\in S_{j}$ and $0$ if $i\notin S_{j}$.

By Corollary 4.7, the solution $x^{*}$ is also feasible for the restricted
related instance $(\hat{\mathbf{p}},\hat{\mathbf{v}},\hat{E})$ and has the
same load for every agent $i\in[m]$ since

$\ell_{i}(P,x^{*})=\sum_{j}x^{*}_{i,j}\cdot p_{i,j}=\sum_{j:i\in
S_{j}}x^{*}_{i,j}\cdot p_{i,j}=\sum_{j:S_{j}\ni
i}x^{*}_{i,j}\cdot(\hat{p}_{j}\cdot{u_{i}})=\ell_{i}(P^{\prime},x^{*}),$

where $P^{\prime}$ is the weight matrix of the corresponding restricted
related instance.

We now invoke Sinkhorn’s theorem (see e.g. [rothblum1989scalings]) which
states the following:

######  Theorem 4.8 (Sinkhorn’s Theorem).

For any matrix $Z\in\mathbb{R}^{m\times n}$ and vectors ${\bf
c}\in\mathbb{R}^{n}$ and ${\bf r}\in\mathbb{R}^{m}$, if there is some matrix
$Y$ with the properties that (a) the column and row sums of $Y$ are equal to
$\bf c$ and $\bf r$ respectively and (b) $Y_{i,j}>0$ only if $Z_{i,j}>0$, then
there exist diagonal matrices $A\in\mathbb{R}^{m\times m}$ and
$B\in\mathbb{R}^{n\times n}$ such that the column and row sums of $A\cdot
Z\cdot B$ are $\bf c$ and $\bf r$ respectively.

To apply Theorem 4.8, we set $Z$ to the admissibility matrix $\hat{E}$ and the
vectors $\bf c$ and $\bf r$ respectively to the vectors
$\ell^{\textbf{MKS}}\cdot\hat{{\bf v}}$ and $\hat{{\bf p}}$. Now, the matrix
$Y$ required in the condition for Theorem 4.8 is given by
$Y_{i,j}=\hat{p}_{j}\cdot x^{*}_{i,j}$. Note that $Y_{i,j}>0$ only if $i\in
S_{j}$, which in turn implies $\hat{E}_{i,j}=Z_{i,j}=1$. We therefore apply
Theorem 4.8 and obtain diagonal matrices $A\in\mathbb{R}^{m\times m}$ and
$B\in\mathbb{R}^{n\times n}$. Finally, we set the vector of parameters
$\mathbf{w}$ to $w_{i}=A_{i,i}$ to derive the following corollary:

######  Corollary 4.9.

There exists a vector of parameters $\mathbf{w}\in\mathbb{R}_{>0}^{m}$ such
that the following allocation

$\hat{x}_{i,j}=\begin{cases}\frac{w_{i}}{\sum_{i^{\prime}\in
S_{j}}w_{i^{\prime}}}&\text{ if }i\in S_{j}\\\ 0&\text{ otherwise
}\end{cases}$

achieves the optimal MinMax objective $\ell^{\textbf{MKS}}$.

We are now ready to finish the proof of Lemma 4.3.

###### Proof of Lemma 4.3.

Suppose we are given a weight matrix $P\in\mathbb{R}_{>0}^{m\times n}$. By
Corollary 4.7 and Corollary 4.9, there exists a vector of parameters
$\mathbf{w}$ for the corresponding restricted related instance defined by the
ratio vector $\mathbf{u}$ with the following property: the proportional
assignment with these parameters produces an optimal solution $\hat{x}$. Now,
for a fixed $\alpha$, let us define
$\hat{w}_{\alpha,i}=\frac{w_{i}}{u_{i}^{\alpha}}$. Then, it is sufficient to
show that

$\lim_{\alpha\rightarrow-\infty}\frac{\hat{w}_{\alpha,i}\cdot
p_{i,j}^{\alpha}}{\sum_{i^{\prime}}\hat{w}_{\alpha,i^{\prime}}\cdot
p_{i^{\prime},j}^{\alpha}}=\hat{x}_{i,j}.$

We know

$\frac{\hat{w}_{\alpha,i}\cdot p_{i,j}^{\alpha}}{\hat{w}_{\alpha,k}\cdot
p_{k,j}^{\alpha}}=\frac{w_{i}\cdot
p_{i,j}^{\alpha}/{u_{i}}^{\alpha}}{w_{k}\cdot
p_{k,j}^{\alpha}/{u_{k}}^{\alpha}}=\frac{w_{i}}{w_{k}}\cdot\left(\frac{{u_{k}}\cdot
p_{i,j}}{{u_{i}}\cdot p_{k,j}}\right)^{\alpha}.$

Now, fix an item $j$ and an agent $k\in S_{j}$. We have the following two
cases for any agent $i\in[m]$:

$\displaystyle\frac{\hat{w}_{\alpha,i}\cdot
p_{i,j}^{\alpha}}{\hat{w}_{\alpha,k}\cdot p_{k,j}^{\alpha}}$ $\displaystyle=$
$\displaystyle\frac{w_{i}}{w_{k}}\quad\text{ if }i\in S_{j},\text{ and }$
$\displaystyle\displaystyle\lim_{\alpha\rightarrow-\infty}\frac{\hat{w}_{\alpha,i}\cdot
p_{i,j}^{\alpha}}{\hat{w}_{\alpha,k}\cdot p_{k,j}^{\alpha}}$ $\displaystyle=$
$\displaystyle 0\quad\text{ if }i\notin S_{j}.$

Therefore, there exists an $\alpha^{*}$ such that
$\ell_{i}(P,\alpha^{*},w_{\alpha^{*}})\leq\ell^{\textbf{MKS}}(P)+\epsilon$ for
all agents $i\in[m]$. By the monotonicity property on values of $\alpha$
(first part of Theorem 2.3), for any ${\alpha^{\prime}}<\alpha^{*}$, the value
of $\ell^{*}(P,{\alpha^{\prime}})$ is at most
$\ell^{\textbf{MKS}}(P)+\epsilon$ as required.

∎

##  5 Noise Resilience: Handling Predictions with Error

In this section, we show the noise resilience of our algorithms, namely that
we can handle errors in the learned parameters. First, we will show that for
both objectives (MaxMin and MinMax), an $\eta$-approximate set of learned
parameters yields an online algorithm with a competitive ratio of at least/at
most $\eta$. Second, for the MinMax objective, we show that it is possible to
improve the competitive ratio further in the following sense: using a set of
learned parameters with a multiplicative error of $\eta$ with respect to the
optimal parameters, we can obtain a $O(\log\eta)$-competitive algorithm. (This
was previously shown by Lattanzi et al. [LattanziLMV20] but only for the
special case of restricted assignment.) We also rule out a similar guarantee
for the MaxMin objective, i.e., we show that using $\eta$-approximate learned
parameters, an algorithm cannot hope to obtain a competitive ratio better than
$\eta/c$ for some constant $c$. Finally, we show that noise-resilient bounds
can be obtained not just for the MinMax and MaxMin objectives but also for any
homogeneous monotone minimization or maximization objective function.

Formally, a weight vector $\mathbf{w}$ is $\eta$-approximate with respect to a
weight vector to $\mathbf{w}^{*}$, if for any two agents $i,i^{\prime}\in[m]$,
$\frac{w_{i^{\prime}}}{w_{i}}\leq\eta\cdot\frac{w^{*}_{i^{\prime}}}{w^{*}_{i}}$.
First, we show a basic noise resilience property that holds for both the
MinMax and MaxMin objectives:

######  Lemma 5.1.

Fix a weight matrix $P\in\mathbb{R}_{>0}^{m\times n}$ and a transformation
matrix $G\in\mathbb{R}_{>0}^{m\times n}$. For any two parameter vectors
$\mathbf{w}^{*},\mathbf{w}\in\mathbb{R}_{>0}^{m}$, such that $\mathbf{w}$ is
$\eta$-approximate to $\mathbf{w}^{*}$, we have that for any agent $k$:

$\frac{\ell_{k}(P,G,\mathbf{w}^{*})}{\eta}\leq\ell_{k}(P,G,\mathbf{w})\leq\eta\cdot\ell_{k}(P,G,\mathbf{w}^{*}).$

###### Proof.

Let $y_{i,j}=x_{i,j}(G,\mathbf{w}^{*})$ and $z_{i,j}=x_{i,j}(G,\mathbf{w})$ be
the respective fractional allocations under proportional allocation using the
transformation matrix $G$. For an agent $i$, let $\tau_{i}=w_{i}/w^{*}_{i}$.
Then for any two agents $i,k$, we have that
$1/\eta\leq\tau_{k}/\tau_{i}\leq\eta$. By Observation 3.8 , we have:
$\frac{y_{i,j}}{z_{i,j}}=\sum_{i^{\prime}\in[m]}\frac{\tau_{i^{\prime}}}{\tau_{i}}\cdot
y_{i^{\prime},j}.$ Therefore,

$\frac{y_{i,j}}{z_{i,j}}=\sum_{i^{\prime}\in[m]}\frac{\tau_{i^{\prime}}}{\tau_{i}}\cdot
y_{i^{\prime},j}\geq\sum_{i^{\prime}\in[m]}\frac{1}{\eta}\cdot
y_{i^{\prime},j}=\frac{1}{\eta}\cdot\sum_{i^{\prime}\in[m]}y_{i^{\prime},j}=\frac{1}{\eta},\text{
and}$
$\frac{y_{i,j}}{z_{i,j}}=\sum_{i^{\prime}\in[m]}\frac{\tau_{i^{\prime}}}{\tau_{i}}\cdot
y_{i^{\prime},j}\leq\sum_{i^{\prime}\in[m]}{\eta}\cdot
y_{i^{\prime},j}={\eta}\cdot\sum_{i^{\prime}\in[m]}y_{i^{\prime},j}=\eta.$

Hence, $y_{i,j}/\eta\leq z_{i,j}\leq y_{i,j}\cdot\eta$. Finally, the lemma
hold by summing over all items. ∎

The next theorem follows immediately by using a proportional allocation
according to the parameter vector $\tilde{\mathbf{w}}$:

######  Theorem 5.2.

Fix any $P,G\in\mathbb{R}_{>0}^{m\times n}$. Let $\mathbf{w}$ be a learned
parameter vector that gives a solution of value $\gamma$ for the MaxMin
(resp., MinMax) objective using proportional allocation. Let
$\tilde{\mathbf{w}}$ be $\eta$-approximate to $\mathbf{w}$ for some $\eta>1$.
Then, there exists an online algorithm that given $\tilde{\mathbf{w}}$
generates a solution with value at least $\Omega(\gamma/\eta)$ (resp., at most
$O(\eta\gamma)$).

In particular, if $\mathbf{w}$ is the optimal learned parameter vector in the
above theorem and $\tilde{\mathbf{w}}$ is an $\eta$-approximation to it, then
we obtain a competitive ratio of $\Omega(1/\eta)$.

The rest of this section focuses on the MinMax objective for which we can
obtain an improved bound. In the next lemma, we establish an upper bound on
the load, using Lemma 5.1 and monotonicity.

######  Lemma 5.3.

Fix a weight matrix $P\in\mathbb{R}_{>0}^{m\times n}$ and a transformation
matrix $G\in\mathbb{R}_{>0}^{m\times n}$. For any two parameter vectors
$\mathbf{w}^{*},\mathbf{w}\in\mathbb{R}_{>0}^{m}$ such that there exists an
agent $k\in[m]$ for which $w^{*}_{k}/2\leq w_{k}\leq w^{*}_{k}$ and for all
other agents $i\not=k$, we have $w_{i}\geq w^{*}_{i}/2$, then the following
holds: $\ell_{k}(P,G,\mathbf{w})\leq 2\cdot\ell_{k}(P,G,\mathbf{w}^{*}).$

###### Proof.

Define $\mathbf{w}^{\prime}$ where $w^{\prime}_{k}=w^{*}_{k}$ (i.e., the
maximum in its allowed range) and $w^{\prime}_{i}=w^{*}_{i}/2$ for all $i\neq
k$ (i.e., the minimum in their allowed ranges). Now, by monotonicity
(Observation 3.2), we have $x_{k,j}(G,\mathbf{w})\leq
x_{k,j}(G,\mathbf{w}^{\prime})$, and therefore,
$\ell_{k}(P,G,\mathbf{w})\leq\ell_{k}(P,G,\mathbf{w}^{\prime})$. Note that for
$\mathbf{w}^{\prime}$, for any two agents $i_{1},i_{2}$,
$\frac{w_{i_{1}}}{w_{i_{2}}}\leq 2\cdot\frac{w^{*}_{i_{1}}}{w^{*}_{i_{2}}}$.
Therefore, by Lemma 5.1, we have $\ell_{k}(P,G,\mathbf{w}^{\prime})\leq
2\cdot\ell_{k}(P,G,\mathbf{w}^{*})$. By combining the two inequalities, we
have $\ell_{k}(P,G,\mathbf{w})\leq\ell_{k}(P,G,\mathbf{w}^{\prime})\leq
2\cdot\ell_{k}(P,G,\mathbf{w}^{*})$, as required. ∎

  * •

Let $\hat{\mathbf{w}}$ a prediction vector and $T$ is the offline optimal
objective for the MinMax problem.

  * •

Initialize: $\ell_{i}\leftarrow 0$ and $\tilde{w}_{i}\leftarrow\hat{w}_{i}$,
for all $i\in[m]$

For each item $j$:

  * •

Compute
$x_{i,j}=\frac{f(p_{i,j})\cdot\tilde{w}_{i}}{\displaystyle\sum_{i^{\prime}\in[m]}f(p_{i^{\prime},j})\cdot\tilde{w}_{i^{\prime}}}$

  * •

$\ell_{i}\leftarrow\ell_{i}+p_{i.j}\cdot x_{i,j}$, for all $i\in[m]$

  * •

If exists $i\in[m]$, s.t. $\ell_{i}>2\cdot T$

Set $\ell_{i}\leftarrow 0$

Update $\tilde{w}_{i}\leftarrow\tilde{w}_{i}/2$

Algorithm 2 The online algorithm with predictions.

Let us denote the predicted learned parameter vector that is given offline to
the MinMax algorithm by $\hat{\mathbf{w}}$. We also assume that the algorithm
knows the optimal objective value $T$. By scaling, we assume w.l.o.g that
$\tilde{\mathbf{w}}$ is coordinate-wise larger than the optimal learned
parameter vector $\mathbf{w}$. The algorithm uses a learned parameter vector
$\hat{\mathbf{w}}$ that is iteratively refined, starting with
$\hat{\mathbf{w}}=\tilde{\mathbf{w}}$ (see Algorithm 2). In each iteration,
the current parameter vector $\hat{\mathbf{w}}$ is used to determine the
assignment using proportional allocation until an agent’s load in the current
phase exceeds $2T$. If this happens for any agent $i$, then the algorithm
halves the value of $\hat{w}_{i}$, starts a new phase for agent $i$, and
continues doing proportional allocation with the updated learned parameter
vector $\hat{\mathbf{w}}$.

######  Theorem 5.4.

Fix any $P,G\in\mathbb{R}_{>0}^{m\times n}$. Let $\mathbf{w}$ be a learned
parameter vector that gives a fractional solution with maximum load $T$ using
proportional allocation. Let $\tilde{\mathbf{w}}$ be an $\eta$-approximate
prediction for $\mathbf{w}$. Then there exists an online algorithm that given
$\tilde{\mathbf{w}}$ generates a fractional assignment of items to agents with
maximum load at most $O(T\log\eta)$.

###### Proof.

By the algorithm’s definition, an agent’s total load is at most $2T$ times the
number of phases for the agent. We show that for any agent $i$, the parameter
$\tilde{w}_{i}$ is always at least $w_{i}/2$. This immediately implies that
the number of phases for machine $i$ is $O(\log\eta)$, which in turn
establishes the theorem.

Suppose, for contradiction, in some phase for agent $k$, we have
$\tilde{w}_{k}<w_{k}/2$. Moreover, assume w.l.o.g. that agent $k$ is the first
agent for which this happens. Clearly, by the algorithm definition, there is a
preceding phase for agent $k$ when $\tilde{w}_{k}<w_{k}$. Note that, in this
entire preceding phase, we have $w_{k}>\tilde{w}_{k}\geq w_{k}/2$, and for all
$i\neq k$, $\tilde{w}_{i}\geq w_{i}/2$ (by our assumption that $k$ is the
first agent to have a violation). However, by Lemma 5.3, the load of agent $k$
in the preceding phase would be at most $2T$. This contradicts the fact that
the algorithm started a new phase for agent $k$ when its load exceeded $2T$ in
the preceding phase. ∎

We now show that the bounds obtained above for the MaxMin and MinMax
objectives are asymptotically tight.

######  Lemma 5.5.

There exists an instance $P$ and learned parameter vectors
$\mathbf{w},\mathbf{w}^{*}$, where $\mathbf{w}$ is $\tau$-approximate with
respect to $\mathbf{w}^{*}$, such that using proportional allocation with
$\mathbf{w}^{*}$ obtains a MaxMin objective of $\Omega(\tau)$, while even when
$\mathbf{w}$ is known offline, any online algorithm achieves a MaxMin
objective of $O(1)$.

###### Proof.

Our construction is in the restricted assignment setting. To define
$\mathbf{w}$, set $w_{i}=1$ for all $i\in m$. The first batch has $m$ items,
where $p_{i,j}=1$ for all $i,j\in[m]$. Clearly, in any assignment of these
items, there exists an agent $k$ such that their load at the end of the first
batch is at most $1$. The second batch consists of $(m-1)\cdot m$ items such
that for $j\in\\{m+1,\ldots,(m-1)\cdot m\\}$, we have $p_{i,j}=1$ for $i\neq
k$ and $p_{k,j}=0$. Clearly, the load of agent $k$ at the end of the second
batch remains unchanged at $\leq 1$, which means the MaxMin objective is also
$\leq 1$. (This can also be extended to randomized algorithms but choosing $k$
uniformly at random in the second batch, and using Yao’s minmax principle.)

Now, define $\mathbf{w}^{*}$ as $w^{*}_{i}=1$ for $i\neq k$ and
$w^{*}_{k}=\tau$. Then, for $m\geq\tau\geq 1$, using $\mathbf{w}^{*}$ gives a
proportional allocation with a MaxMin objective of $\Omega(\tau)$. ∎

######  Lemma 5.6.

There exists an instance $P$ and learned parameter vectors
$\mathbf{w},\mathbf{w}^{*}$, where $\mathbf{w}$ is $\tau$-approximate with
respect to $\mathbf{w}^{*}$, such that using proportional allocation with
$\mathbf{w}^{*}$ obtains a MinMax objective of $O(1)$, while even even when
$\mathbf{w}$ is known offline, any online algorithm achieves a MinMax
objective of $\Omega(\log\tau)$.

###### Proof.

Our construction is in the restricted assignment setting and is essentially
equivalent to the $\Omega(\log m)$ lower bound for the MinMax problem in the
worst-case setting. To define $\mathbf{w}$, set $w_{i}=1$ for all $i\in m$.
The example consists of $m=2^{k}$ agents and $n=m-1$ items. The first batch
comprises $m/2$ items, each of which has a weight of $1$ for a disjoint pair
of agents, and $\infty$ for the remaining agents. The second batch comprises
$m/4$ items, each of which has a weight of $1$ for a disjoint pair of agents,
and $\infty$ for the remaining agents. Crucially, for every pair of agents
with finite weight for an item in the first batch, one must have load at least
$\nicefrac{{1}}{{2}}$ after the first batch; this agent has finite weight for
one of the items in the second batch and the other agent has infinite weights
for all items in the second batch (and all batches henceforth). We continue in
this manner, pruning the number of items by a factor of $2$ in every step and
ensuring that the agents that have finite weight for any item in the $t$th
batch must have a total load of at least $\frac{t-1}{2}$ from the previous
$t-1$ batches. Clearly, the MinMax objective at the end of the algorithm is
$\Omega(\log m)$. (This is true even if we allow randomized algorithms by
uniformly randomizing the choice of agent to retain in any batch, and using
Yao’s minmax principle.)

Now, set $\tau=m$ and define $\mathbf{w}^{*}$ as follows:
$w^{*}_{k}=2^{-a_{k}}$, where $a_{k}$ is the number of items that have a
finite weight for agent $k$. A proportional allocation using these learned
parameters achieves a makespan of at most $2$. ∎

##  6 Learnability of the Parameters

We consider the learning model introduced by [LavastidaMRX21a], and show that
under this model, the parameter vector $\mathbf{w}$ can be learned efficiently
from sampled instances. Specifically, we consider the following model: the
$j$th item (i.e., the values of $\mathbf{p}_{j}=(p_{i,j}:i\in[m])$ is
independently sampled from a (discrete) distribution $\mathcal{D}_{j}$. In
other words, the matrix $P$ of utilities is sampled from
$\mathcal{D}=\times_{j}\mathcal{D}_{j}$.

We set up the model for the MaxMin objective; the setup for the MinMax
objective is very similar and is omitted for brevity. Let
$T=\mathbb{E}_{P\sim\mathcal{D}}[\ell^{\textbf{SNT}}(P)]$ be the expected
value of the MaxMin objective in the optimal solution for an instance
$\ell^{\textbf{SNT}}(P)$ drawn from $\mathcal{D}$. Morally, we would like to
say that we can obtain a vector $\mathbf{w}$ that gives a nearly optimal
solution (in expectation) using proportional allocation (i.e., a MaxMin
objective of $(1-\epsilon)\cdot T$ in expectation for some error parameter
$\epsilon$) using a bounded (as a function of $\epsilon$) number of samples.
Similar to [LavastidaMRX21a], we need the following assumption:

Small Items Assumption: Conceptually, this assumption states that each
individual item has a small utility compared to the overall utility of any
agent in an optimal solution. Precisely, we need $p_{i,j}\leq\frac{T}{\zeta}$
for every $i\in[m],j\in[n]$ for some value $\zeta=\Theta\left(\frac{\log
m}{\epsilon^{2}}\right)$.

Our main theorem in this section for the MaxMin and MinMax objectives are:

######  Theorem 6.1.

Fix an $\epsilon>0$ for which the small items assumption holds. Then, there is
an (learning) algorithm that samples $O(\frac{m}{\log
m}\cdot\log\frac{m}{\epsilon})$ independent instances from $\mathcal{D}$ and
outputs (with high probability) a prediction vector $\mathbf{w}$ such that
using $\mathbf{w}$ in the proportional allocation scheme gives a MaxMin
objective of at least $(1-\Omega(\epsilon))\cdot T$ in expectation over
instances $P\sim\mathcal{D}$.

######  Theorem 6.2.

Fix an $\epsilon>0$ for which the small items assumption holds. Then, there is
an (learning) algorithm that samples $O(\frac{m}{\log
m}\cdot\log\frac{m}{\epsilon})$ independent instances from $\mathcal{D}$ and
outputs (with high probability) a prediction vector $\mathbf{w}$ such that
using $\mathbf{w}$ in the proportional allocation scheme gives a MinMax
objective of at most $(1+O(\epsilon))T$ in expectation over instances
$P\sim\mathcal{D}$.

Importantly, the description of the entries of $\mathbf{w}$ in Theorem 6.1 and
Theorem 6.2 are bounded. Specifically, let us define
$\textbf{NET}(m,\epsilon)\subseteq\mathbb{R}_{>0}^{m}$ as follows: (a) for the
MaxMin objective, $\mathbf{w}\in\textbf{NET}(m,\epsilon)$ if there exist
vectors $\mathbf{u},\mathbf{\delta}\in\mathbb{R}_{>0}^{m}$ such that
$w_{i}=\frac{\delta_{i}}{u_{i}^{\alpha}}$ and
$u_{i},\delta_{i}\in\left\\{\left(\frac{1}{1-\epsilon}\right)^{r}:r\in[K]\right\\}$
for some $K=O(\frac{m}{\epsilon}\log\frac{m}{\epsilon})$, and (b) for the
MinMax objective, $\mathbf{w}\in\textbf{NET}^{\prime}(m,\epsilon)$ if there
exist vectors $\mathbf{u},\mathbf{\delta}\in\mathbb{R}_{>0}^{m}$ such that
$w_{i}=\frac{\delta_{i}}{u_{i}^{\alpha}}$ and
$u_{i},\delta_{i}\in\left\\{(1+\epsilon)^{r}:r\in[K]\right\\}$ for some
$K=O(\frac{m}{\epsilon}\log\frac{m}{\epsilon})$. The vectors $\mathbf{w}$
produced by the learning algorithm in Theorem 6.1 and Theorem 6.2 will satisfy
$\mathbf{w}\in\textbf{NET}(m,\epsilon)$ and
$\mathbf{w}\in\textbf{NET}^{\prime}(m,\epsilon)$ in the respective cases.

Proof Idea for Theorem 6.1 and Theorem 6.2. Recall that in PAC theory, the
number of samples needed to learn a function from a family of $N$ functions is
about $O(\log N)$. Indeed, restricting $\mathbf{w}$ to be in the class
$\textbf{NET}(m,\epsilon)$ or $\textbf{NET}^{\prime}(m,\epsilon)$ serves this
role of limiting the hypothesis class to a finite, bounded set since
$|\textbf{NET}(m,\epsilon)|=|\textbf{NET}^{\prime}(m,\epsilon)|=K^{2m}$ where
$K=O(\frac{m}{\epsilon}\log\frac{m}{\epsilon})$. Using standard PAC theory,
this implies that using about $O(m\log K)=O(m\cdot\log\frac{m}{\epsilon})$
samples, we can learn the “best” vector in $\textbf{NET}(m,\epsilon)$ or
$\textbf{NET}^{\prime}(m,\epsilon)$ depending on whether we have the MaxMin or
MinMax objective. Our main technical work is to show that this “best” vector
produces an approximately optimal solution when used in proportional
allocation. We state this lemma next:

######  Lemma 6.3.

Fix any $P$. For the MaxMin objective, there exists a learned parameter vector
$\mathbf{w}\in\textbf{NET}(m,\epsilon)$ which when used in EP-allocation gives
a $1-\Omega(\epsilon)$ approximation. For the MaxMin objective, there exists a
learned parameter vector
$\mathbf{w}^{\prime}\in\textbf{NET}^{\prime}(m,\epsilon)$ which when used in
EP-allocation gives a $1+O(\epsilon)$ approximation.

###  6.1 Proof of Lemma 6.3

####  6.1.1 Preprocessing: Modification of $P$

We will not show Lemma 6.3 directly on an arbitrary matrix $P$. Instead, we
will first “preprocess” $P$ to establish some properties that will help us
show Lemma 6.3.

The first step performs discretization. For the MaxMin objective, we round
down each $p_{i,j}$ value to an integer power of $\frac{1}{1-\epsilon}$. This
changes the optimal MaxMin objective by at most $1-\epsilon$. Similarly, for
the MinMax objective, we round up each $p_{i,j}$ value to an integer power
$1+\epsilon$. This changes the optimal MinMax objective by at most a factor of
$1+\epsilon$.

In the second step, the goal is to ensure that the ratio between any two
entries $p_{i,j}$ and $p_{k,j}$ is bounded. For the MinMax objective, this is
simple: if $\frac{p_{i,j}}{p_{k,j}}>\frac{m}{\epsilon}$ for some $k\in[m]$,
then we set $p_{i,j}=\infty$, i.e., $x_{i,j}=0$. This transformation increases
the MinMax objective by at most a factor of $1+\epsilon$.

For the MaxMin objective, the second step is more complicated. We modify the
online allocation algorithm to assign an $\frac{\epsilon}{m}$ fraction of each
item to every agent. Since we still have a $1-\epsilon$ fraction of every item
left, this step changes the optimal MaxMin objective by at most a factor of
$1-\epsilon$. But, what does this allocation of $\epsilon$-fraction of each
item achieve? Let $a_{i}=\sum_{j\in[n]}p_{i,j}$ denote the monopolist value of
agent $i\in[m]$, i.e., the total utility if all items were assigned to agent
$i$. We assume that the values of $a_{i}$ for all $i\in[m]$ are known to the
algorithm – in fact, these values can also be learned to sufficient accuracy
but we ignore this additional learning step for simplicity and assume these
values are known. Now, note that $\ell^{\textbf{SNT}}\leq a_{\min}$ where
$a_{\min}$ is defined as $\min_{i\in[m]}a_{i}$. The allocation of $\epsilon$
fraction of every item ensures that every agent $i\in[m]$ with a large
monopolist value satisfying $a_{i}\geq\frac{m}{\epsilon}\cdot a_{\min}$ gets a
load of at least $\frac{\epsilon}{m}\cdot a_{i}\geq
a_{\min}\geq\ell^{\textbf{SNT}}$ just from this $\epsilon$-allocation.
Therefore, we ignore these agents in the rest of the analysis and assume
$a_{i}<\frac{m}{\epsilon}\cdot a_{\min}$ for every agent $i\in[m]$.

Now, fix any agent $i\in[m]$ and define $J_{i}$ to be the set of items
$j\in[m]$ for each of which there exists another agent $k(j)$ such that
$\frac{p_{k,j}}{p_{i,j}}>\frac{m^{3}}{\epsilon^{2}}$. Then, we set
$p_{i,j}=0$. This modification decreases the optimal MaxMin objective by a
factor of at most $1-\epsilon$ because:

$\sum_{j\in J_{i}}p_{i,j}\leq\frac{\sum_{j\in
J_{i}}p_{k(j),j}}{\frac{m^{3}}{\epsilon^{2}}}\leq\frac{\sum_{k}a_{k}}{\frac{m^{3}}{\epsilon^{2}}}\leq^{\rm(by~{}first~{}preprocessing~{}step)}\frac{m\cdot\frac{m}{\epsilon}\cdot
a_{\min}}{\frac{m^{3}}{\epsilon^{2}}}=\epsilon\cdot\frac{a_{\min}}{m}\leq\epsilon\cdot\ell^{\textbf{SNT}},$

where the last step follows from $\ell^{\textbf{SNT}}\geq\frac{a_{\min}}{m}$
by a uniform assignment.

So, in essence, we can assume for both the MinMax and MaxMin objectives, the
following holds for any item $j\in[n]$: if $x^{*}_{i,j},x^{*}_{k,j}\not=0$ in
an optimal solution $x^{*}$, then we can assume that
$\frac{p_{i,j}}{p_{k,j}}\leq\operatorname{poly}(m/\epsilon)$.

####  6.1.2 Proof of Lemma 6.3 for the MaxMin objective

We now prove Lemma 6.3 for the MaxMin objective. The proof for the MinMax
objective is similar, and we omit it for brevity.

Recall that to define any vector $\mathbf{w}\in\textbf{NET}(m,\epsilon)$, we
need to define two vectors $\mathbf{u}$ and $\delta$. We define these vectors
for the vector $\mathbf{w}$ in Lemma 6.3 separately in the next two
subsections. Note that Lemma 6.3 is existential; hence, we can use the optimal
solution, for instance, in the proof.

The vector $\mathbf{u}$. Given a preprocessed matrix $P\in\mathbb{R}_{>0}^{m}$
and an optimal solution $x^{*}$ for the MaxMin objective, we define an
auxiliary directed graph $G_{x^{*}}(V,E)$ as follows:

  * •

The set of vertices $V=[m]\cup\\{0\\}$, i.e., the agents and a special vertex
labeled $0$.

  * •

The set of edges $E=([m]\times[m])\cup(\\{0\\}\times[m])$, i.e., all edges
between (ordered) pairs of vertices representing the agents (including self
loops) and edges from the special vertex to all the vertices representing the
agents. Note that the set of vertices and edges does not depend on $x^{*}$.

  * •

We now define a cost function on the edges that does depend on $x^{*}$. Edges
in $[m]\times[m]$ have the following costs:

$c_{i,k}=\ln\left(\max_{j\in[n]}\left\\{\frac{p_{k,j}}{p_{i,j}}\;\bigg{|}\;x^{*}_{i,j}>0\right\\}\right).$

In other words, the cost of an edge $(i,k)$ is the logarithm of the maximum
ratio of the weight of an item for $k$ to that for $i$ among those items that
have a non-zero allocation to agent $i$ in $x^{*}$. In addition, all edges
incident on the special vertex have cost $0$, i.e., $c_{0,k}=0$ for all
$k\in[m]$.

Similar to Lemma 4.5, one can verify that $G_{x^{*}}$ does not contain a
negative cycle; if not, one can compute a different assignment in which the
load of some agent increases while keeping all other agents at the same load.

######  Lemma 6.4.

Given a processing matrix $P$ and an optimal solution $x^{*}$ resulting in an
objective value of $\ell^{\textbf{SNT}}(P)$ for the MaxMin problem, the
auxiliary graph $G_{x^{*}}$ does not contain a negative cycle.

For any agent $i\in[m]$, Lemma 6.4 allows us to define $c^{*}_{i}$ as the
minimum cost of a path from vertex $0$ to vertex $i$ in the auxiliary graph
$G_{x^{*}}$. We now define a ratio vector $\mathbf{u}\in\mathbb{R}_{>0}^{m}$,
where $u_{i}=e^{c^{*}_{i}}$. As in Lemma 4.6, one can show that:

######  Lemma 6.5.

Given a matrix $P$ and an optimal solution $x^{*}$ resulting in a MaxMin
objective of $\ell^{\textbf{SNT}}(P)$, we have that any $i\in[m]$, $j\in[n]$,
if there exists some agent $k\in[m]$ such that
$\frac{p_{k,j}}{u_{k}}>\frac{p_{i,j}}{u_{i}}$, then $x^{*}_{i,j}=0$.

We also note the following property of $\mathbf{u}$ that follows immediately
from the third preprocessing step:

######  Lemma 6.6.

Each coordinate of vector $\mathbf{u}$ is an integer power of
$\frac{1}{1-\epsilon}$.

Bounding the aspect ratio of the ratio vector. We show the following:

######  Lemma 6.7.

For any $i,k\in[m]$, the aspect ratio of the ratio vector $\mathbf{u}$ is
bounded as follows:

$\frac{u_{k}}{u_{i}}\leq\left(\frac{m^{3}}{\epsilon^{2}}\right)^{m}.$

###### Proof.

First, note that since there is a directed edge of zero cost from vertex $0$
to every the vertex for every agent $i\in[m]$, we have

$u_{i}\leq 1\text{ for all }i\in[m].$

Next, we bound the minimum value of $u_{i}$ for any agent $i$. Recall that by
preprocessing, we have the following: if $p_{i,j},p_{k,j}>0$, then
$\frac{p_{i,j}}{p_{k,j}}\leq\frac{\epsilon^{2}}{m^{3}}$ if $x^{*}_{i,j}>0$.
Therefore, $c_{i,k}\geq\ln\frac{\epsilon^{2}}{m^{3}}$ for all $i,k\in[m]$.
Since the shortest path contains at most $m$ edges, therefore $c^{*}_{i}\geq
m\cdot\ln\frac{\epsilon^{2}}{m^{3}}$, i.e.,

$u_{i}\geq\left(\frac{\epsilon^{2}}{m^{3}}\right)^{m}\text{ for all }i\in[m].$

We can now conclude the lemma from the upper and lower bounds on $u_{i}$ for
all $i\in[m]$. ∎

The vector $\delta$. We first define a restricted related instance of the
problems based on the value of $\mathbf{u}$. For any item $j\in[n]$, let
$\gamma_{j}=\displaystyle\max_{i}\frac{p_{i,j}}{u_{i}}$ and
$S_{j}=\arg\max_{i}\frac{p_{i,j}}{u_{i}}=\left\\{i\in[m]:\frac{p_{i,j}}{u_{i}}={\gamma_{j}}\right\\}$.
By Lemma 6.5, there exists an optimal solution $x^{*}$ such that $x_{i,j}=0$
if $i\notin S_{j}$.

Lemma 6.5 allows us to convert any general matrix $P$ to a restricted related
instance while preserving the value of $\ell^{\textbf{SNT}}(P)$.

We define the following:

  * •

an utility vector $\hat{\mathbf{p}}\in\mathbb{R}_{>0}^{n}$ where
$\hat{p}_{j}=\gamma_{j}$.

  * •

a speed vector $\hat{\mathbf{v}}\in\mathbb{R}_{>0}^{m}$ where
$\hat{v}_{i}=1/{u_{i}}$.

  * •

an admissibility matrix $\hat{E}\in\\{0,1\\}^{m\times n}$ where
$\hat{E}_{i,j}=1$ if and only if $i\in S_{j}$.

Note that by Lemma 6.5, $x^{*}$ is a feasible solution to this restricted
related instance, and produces the same load for every agent:

$\ell_{i}(x^{*},\hat{\mathbf{p}},\hat{v},\hat{E})=\sum_{j}x^{*}_{i,j}\cdot\frac{\hat{p}_{j}}{\hat{v}_{i}}=\sum_{j:x^{*}_{i,j}>0}x^{*}_{i,j}\gamma_{j}u_{i}=\sum_{j}x^{*}_{i,j}p_{i,j}\geq\ell^{\textbf{SNT}}(P).$

Conversely, let $\hat{x}$ be a solution to the restricted related instance. We
have:

$\ell_{i}(\hat{x},\hat{\mathbf{p}},\hat{v},\hat{E})=\sum_{j:S_{j}\ni
i}\hat{x}_{i,j}\cdot\frac{\hat{p}_{j}}{\hat{v}_{i}}=\sum_{j:S_{j}\ni
i}\hat{x}_{i,j}\gamma_{j}{u}_{i}=\sum_{j:S_{j}\ni
i}\hat{x}_{i,j}p_{i,j}=\ell_{i}(\hat{x},P).$

We now invoke Theorem 4.8, which yields:

######  Corollary 6.8.

There exists a vector of parameters $\delta\in\mathbb{R}_{>0}^{m}$ such that
the following allocation

$\hat{x}_{i,j}(\delta)=\begin{cases}\frac{\delta_{i}}{\sum_{i^{\prime}\in
S_{j}}\delta_{i^{\prime}}}&\text{ if }i\in S_{j}\\\ 0&\text{ otherwise
}\end{cases}$

for the restricted related instance achieves the optimal MaxMin objective
(denoted $\ell^{\textbf{SNT}}(\hat{\mathbf{p}},\hat{v},\hat{E})$).

Next, we approximate the vector $\delta$ in Corollary 6.8 with a vector
$\delta^{\prime}$ with a bounded aspect ratio, and show that this
approximation only loses a factor of $1-\epsilon$. In fact, we will show that
$\hat{x}_{i,j}(\delta^{\prime})\geq(1-\epsilon)\cdot\hat{x}_{i,j}(\delta)$.

We give an algorithm for computing $\delta^{\prime}$. Let $i_{1},\dots i_{m}$
be the ordered indices in increasing order of values of the coordinates of
$\delta$, i.e.,
$\delta_{i_{1}}\leq\delta_{i_{2}}\leq\ldots\leq\delta_{i_{m}}$. Initialize
$\delta^{\prime}_{i}=\delta_{i}$ for all $i\in[m]$. Next, we update the values
of $\delta^{\prime}$ iteratively using the following rule in each iteration:
for each $k\in[m-1]$ satisfying the condition
$\frac{\delta^{\prime}_{i_{k+1}}}{\delta^{\prime}_{i_{k}}}>\frac{m}{\epsilon}$,
we multiply $\delta^{\prime}_{i_{r}}$ by
$\frac{\delta^{\prime}_{i_{k}}}{\delta^{\prime}_{i_{k+1}}}\cdot\frac{m}{\epsilon}$
for every $r=\\{k+1,\dots,m\\}$. In effect, the ratio
$\frac{\delta^{\prime}_{i_{k+1}}}{\delta^{\prime}_{i_{k}}}$ becomes
$\frac{m}{\epsilon}$ and the ratios between all other pairs
$\frac{\delta^{\prime}_{i_{k^{\prime}+1}}}{\delta^{\prime}_{i_{k^{\prime}}}}$
for $k^{\prime}\not=k$ remains unchanged. (A similar trick also appears in
[LiX21].)

The following inequality holds for every item $j\in[m]$ and any agent $i\in
S_{j}$:

$\displaystyle\frac{\delta^{\prime}_{i}}{\sum_{k\in
S_{j}}\delta^{\prime}_{k}}\geq(1-\epsilon)\cdot\frac{\delta_{i}}{\sum_{k\in
S_{j}}\delta_{k}}$

By scaling, we assume that $\min_{i}\delta^{\prime}_{i}=1$. By our
construction we have:

$\delta^{\prime}_{i}\leq\left(\frac{m}{\epsilon}\right)^{m}\text{ for all
}i\in[m].$

Let $\tilde{\delta}$ be derived from $\delta^{\prime}_{i}$ by rounding up to
the nearest integer power of $\frac{1}{1-\epsilon}$. Then for $i\in S_{j}$, we
have $\tilde{x}_{i,j}\geq(1-\epsilon)x^{\prime}_{i,j}$. This completes the
definition of $\delta$.

The vector $\mathbf{w}$ in Lemma 6.3. Now, given such
$\mathbf{u},\tilde{\delta}$, for a fixed $\alpha$, we define the vector
$\mathbf{w}\in\textbf{NET}(m,\epsilon)$ in Lemma 6.3. Set
$w_{i}=\frac{\tilde{\delta}}{u_{i}^{\alpha}}$. Then, it is sufficient to show
that, for $i\in S_{j}$,

$x_{i,j}=\frac{w_{i}\cdot
p_{i,j}^{\alpha}}{\sum_{i^{\prime}}w_{i^{\prime}}\cdot
p_{i^{\prime},j}^{\alpha}}\geq(1-\epsilon)\cdot\tilde{x}_{i,j}$

We have

$\frac{w_{i}\cdot p_{i,j}^{\alpha}}{w_{k}\cdot
p_{k,j}^{\alpha}}=\frac{\tilde{\delta}_{i}\cdot
p_{i,j}^{\alpha}/{u_{i}}^{\alpha}}{\tilde{\delta}_{k}\cdot
p_{k,j}^{\alpha}/{u_{k}}^{\alpha}}=\frac{\tilde{\delta}_{i}}{\tilde{\delta}_{k}}\cdot\left(\frac{{u_{k}}\cdot
p_{i,j}}{{u_{i}}\cdot p_{k,j}}\right)^{\alpha}.$

Now, fix an item $j$ and an agent $i\in S_{j}$. We have the following two
cases for any agent $k\in[m]$ (we use
$\alpha=\frac{2m}{\epsilon}\cdot\log_{1-\epsilon}\frac{m}{\epsilon}$):

$\displaystyle\frac{w_{i}\cdot p_{i,j}^{\alpha}}{w_{k}\cdot p_{k,j}^{\alpha}}$
$\displaystyle=$
$\displaystyle\frac{\tilde{\delta}_{i}}{\tilde{\delta}_{k}}\quad\text{ if
}k\in S_{j}$ $\displaystyle\frac{w_{i}\cdot p_{i,j}^{\alpha}}{w_{k}\cdot
p_{k,j}^{\alpha}}$ $\displaystyle\leq$
$\displaystyle\frac{\tilde{\delta}_{i}}{\tilde{\delta}_{k}}\cdot(1-\epsilon)^{\alpha}\leq\left(\frac{m}{\epsilon}\right)^{m}(1-\epsilon)^{\alpha}\leq\frac{\epsilon}{m}\quad\text{
if }k\notin S_{j},$

where the first inequality is by our construction if $i\in S_{j}$ and $k\notin
S_{j}$ then $\left(\frac{{u_{k}}\cdot p_{i,j}}{{u_{i}}\cdot
p_{k,j}}\right)\leq 1-\epsilon$, the second inequality is since
$1\leq\tilde{\delta}_{i}\leq(\frac{m}{\epsilon})^{m}$, the third inequality is
by $\alpha$’s definition. Therefore,

$x_{i,j}=\frac{1}{\sum_{i^{\prime}}\frac{w_{i^{\prime}}\cdot
p_{i^{\prime},j}^{\alpha}}{w_{i}\cdot
p_{i,j}^{\alpha}}}\geq\frac{1}{1+\sum_{i^{\prime}\neq i,i\in
S_{j}}\frac{\tilde{\delta}_{i}}{\tilde{\delta}_{k}}+\sum_{i\notin
S_{j}}\frac{\epsilon}{m}}\geq\frac{1}{1+\sum_{i^{\prime}\neq i,i\in
S_{j}}\frac{\tilde{\delta}_{i}}{\tilde{\delta}_{k}}+\epsilon}\geq(1-\epsilon)\cdot\tilde{x}_{i,j}$

This completes the proof of Lemma 6.3.

The rest of the proof, i.e. from Lemma 6.3 to Theorem 6.1, uses standard PAC
theory and closely follows Li and Xian [LiX21]. We include it for completeness
in Section 6.2.

###  6.2 PAC Learning: From Lemma 6.3 to Theorem 6.1 for the MaxMin objective

Let us consider a combination of all instances in the support of the
distribution $\mathcal{D}$. For $L$ processing matrices
$P^{(1)},P^{(2)},\dots,P^{(L)}$. we define
$P^{\text{all}}=\bigoplus_{r=1}^{L}P^{(r)}$ to be the instance defined by the
$n\cdot L$ items. For every $\ell\in[L]$ and $j\in[n]$, we have an item
$j^{(\ell)}$ with utility vector $\mathbf{p}_{j}^{(\ell)}$.

The following observation is immediate (superadditivity):

######  Observation 6.9.

$\ell^{\textbf{SNT}}(P^{\text{all}})\geq\sum_{r=1}^{L}\ell^{\textbf{SNT}}(P^{(r)})$.

Using this observation, we can prove the following lemma, by considering the
combination of all instances in $\mathcal{D}$, scaled by their respective
probabilities.

######  Lemma 6.10.

There exists $\mathbf{w}\in\textbf{NET}(m,\epsilon)$, such that for every
$i\in[m]$, we have

$\displaystyle\mathbb{E}_{P\sim\mathcal{D}}[\ell_{i}(P,\mathbf{w})]\geq(1-\epsilon)\cdot
T.$

###### Proof.

Consider the instance $\mathbb{P}=\bigoplus\text{Pr}_{D}[P]\cdot P$ where
$\text{Pr}_{D}[P]$ is the probability mass of $P$ in $\mathcal{D}$, and
$\text{Pr}_{D}[P]\cdot P$ is the matrix $P$ multiplied by $\text{Pr}_{D}[P]$.
By Observation 6.9, we have

$\ell^{\textbf{SNT}}(\mathbb{P})\geq\sum_{P}\text{Pr}_{\mathcal{D}}[P]\ell^{\textbf{SNT}}(P)=\mathbb{E}_{P\sim
D}[\ell^{\textbf{SNT}}(P)]=T.$

We can apply Lemma 6.3 to the combined instance to show there exists
$\mathbf{w}^{*}\in\textbf{NET}(m,\epsilon)$ such that for every $i\in[m]$, we
have,

$\sum_{j}x_{i,j}(\mathbb{P},\mathbf{w}^{*})\cdot
p_{i,j}\geq(1-\epsilon)\ell^{\textbf{SNT}}(\mathbb{P})\geq(1-\epsilon)\cdot T$

where $j$ indexes over all items in $\mathbb{P}$. Notice that
$x_{i,j}(\mathbb{P},\mathbf{w}^{*})$ depends on the utility vector for item
$j$, which is part of the instance $P\in\mathcal{D}$ that $j$ belongs to.
Therefore, the left side of the above inequality is exactly

$\sum_{P}\sum_{j\in[n]}x_{i,j}(P,\mathbf{w}^{*})\cdot\text{Pr}_{\mathcal{D}}[P]\cdot
p_{i,j}=\mathbb{E}_{P\sim\mathcal{D}}\sum_{j\in[n]}x_{i,j}(P,\mathbf{w}^{*})p_{i,j}=\mathbb{E}_{P\sim\mathcal{D}}\sum_{j\in[n]}\ell_{i}(P,\mathbf{w}^{*}),$

as required. ∎

For any real numbers $A,B,\epsilon,C$, we use $A\approx_{\epsilon,C}B$ to
denote $|A-B|\leq\epsilon\cdot\max(B,C)$. The next lemma appears in [LiX21]:

######  Lemma 6.11 (Lemma D.6 in in [LiX21]).

For any $\mathbf{w}\in\textbf{NET}(m,\epsilon)$, with high probability over
$P\sim\mathcal{D}$, we have

$\forall
i\in[m]:\ell_{i}(P,\mathbf{w})\approx_{\epsilon,T}\mathbb{E}_{P^{\prime}\sim
D}\ell_{i}(P^{\prime},\mathbf{w}).$

The learning algorithm. We sample $H=O\left(\frac{m}{\log
m}\log\frac{m}{\epsilon}\right)$ instances $P_{1},P_{2},\dots,P_{H}$
independently and randomly form $\mathcal{D}$. We output
$\tilde{\mathbf{w}}\in\textbf{NET}(m,\epsilon)$ that maximizes
$\min_{i\in[m]}\frac{1}{H}\sum_{h=1}^{H}\ell_{i}(P_{h},\tilde{\mathbf{w}})$.

The next lemma also appears in [LiX21]:

######  Lemma 6.12 (Lemma D.7 in [LiX21]).

With probability at least $1-\frac{1}{K^{m}}$, for every
$\mathbf{w}\in\textbf{NET}(m,\epsilon)$ and for every $i\in[m]$, we have

$\frac{1}{H}\sum_{h=1}^{H}\ell_{i}(P_{h},\mathbf{w})\approx_{\epsilon,T}\mathbb{E}_{P\sim
D}\ell_{i}(P,\mathbf{w}).$

Now assume the event in Lemma 6.12 happens. Then by Lemma 6.10, there exists
some $\mathbf{w}\in\textbf{NET}(m,\epsilon)$ such that

$\min_{i\in[m]}\frac{1}{H}\sum_{h=1}^{H}\ell_{i}(P_{h},\mathbf{w})\geq(1-\epsilon)^{2}\cdot
T.$

In particular, since $\tilde{\mathbf{w}}$ maximizes
$\min_{i\in[m]}\frac{1}{H}\sum_{h=1}^{H}\ell_{i}(P_{h},\tilde{\mathbf{w}})$
for $\tilde{\mathbf{w}}\in\textbf{NET}(m,\epsilon)$, we can conclude that

$\min_{i\in[m]}\frac{1}{H}\sum_{h=1}^{H}\ell_{i}(P_{h},\tilde{\mathbf{w}})\geq(1-\epsilon)^{2}\cdot
T.$

Applying Lemma 6.12 again, we get

$\min_{i\in[m]}\mathbb{E}_{P\sim\mathcal{D}}\ell_{i}(P,\tilde{\mathbf{w}})\geq(1-\epsilon)^{3}\cdot
T.$

We now apply Lemma 6.11 to $\tilde{\mathbf{w}}$. We have that with high
probability over $P\sim\mathcal{D}$, for every $i\in[m]$ the following holds:

$\ell_{i}(P,\tilde{\mathbf{w}})\geq\mathbb{E}_{P^{\prime}\sim\mathcal{D}}\ell_{i}(P^{\prime},\tilde{\mathbf{w}})-\epsilon\cdot\max\\{T,\mathbb{E}_{P^{\prime}\sim\mathcal{D}}\ell_{i}(P^{\prime},\tilde{\mathbf{w}})\\}\geq(1-\epsilon)^{4}\cdot
T.$

Therefore,
$\ell^{\textbf{SNT}}(P,\tilde{\mathbf{w}})\geq(1-\Omega(\epsilon))\cdot T$.
This completes the proof of Theorem 6.1.

##  7 Generalization to Well-Behaved Objectives

We first generalize Theorem 2.1 to all well-behaved functions.

######  Theorem 7.1.

Fix any instance of an online allocation problem with divisible items where
the goal is to maximize or minimize a monotone homogeneous objective function.
Then, there exists an online algorithm and a learned parameter vector in
$\mathbb{R}_{>0}^{m}$ that achieves a competitive ratio of $1-\epsilon$ (for
maximization) or $1+\epsilon$ (for minimization).

###### Proof.

Fix an objection function $f$ and a matrix $P\in\mathbb{R}_{>0}^{m\times n}$.
Let $\ell^{f}_{i}$ denote the load of agent $i$ in an optimal solution for
objective function $f$. Also, let $x_{i,j}$ denote the fraction of item $j$
assigned to agent $i$ in this optimal solution. Now, consider the matrix
$\tilde{P}$, where $\tilde{p}_{i,j}=\frac{p_{i,j}}{\ell^{f}_{i}}$. By the
monotonicity property of $f$, the optimal objective value for $\tilde{P}$ is
$1$. Therefore, by Theorem 2.3, there exist $\alpha$ and $\tilde{\mathbf{w}}$,
such that using an EP-allocation, we get
$\ell^{*}(\tilde{P},\alpha,\tilde{\mathbf{w}})\geq 1-\epsilon$ for
maximization and $\ell^{*}(\tilde{P},\alpha,\tilde{\mathbf{w}})\leq
1+\epsilon$ for minimization. Let $x^{*}_{i,j}$ be the fraction of item $j$
assigned to agent $i$ in this approximate solution. By the definition of EP-
allocation, $x^{*}_{i,j}$ is proportional to
$\tilde{p}_{i,j}^{\alpha}\cdot\tilde{w}_{i}=\left(\frac{p_{i,j}}{\ell^{f}_{i}}\right)^{\alpha}\cdot\tilde{w}_{i}=p_{i,j}^{\alpha}\cdot\frac{\tilde{w}_{i}}{{(\ell^{f}_{i})}^{\alpha}}$.
Thus, if we define $\mathbf{w}$ such that
$w_{i}=\frac{\tilde{w}_{i}}{{(\ell^{f}_{i})}^{\alpha}}$, then the
corresponding EP-allocation gives a $(1-\epsilon)$-approximate solution for
maximization and $(1+\epsilon)$-approximate solution for minimization. ∎

###  7.1 Noise Resilience

Next, we consider noise resilience for well-behaved functions, i.e., we
generalize Theorem 5.2 to all well-behaved objective functions. This follows
immediately from Lemma 5.1 and the observation that if all loads are scaled by
$\eta$, then the objective value for a well-behaved objective is also scaled
by $\eta$. We state this generalized theorem below:

######  Theorem 7.2.

Fix any $P,G\in\mathbb{R}_{>0}^{m\times n}$ and any monotone, homogeneous
function $f$. Let $\mathbf{w}$ be a learned parameter vector that gives a
solution of objective value $\gamma$ using EP-allocation. Let
$\tilde{\mathbf{w}}$ be $\eta$-approximate to $\mathbf{w}$ for some $\eta>1$.
Then, the EP-allocation for $\tilde{\mathbf{w}}$ gives a solution with value
at least $\gamma/\eta$ for maximization and at most $\eta\gamma$ for
minimization.

###  7.2 Learnability

Finally, we consider learnability of parameters for well-behaved functions,
i.e., we generalize Theorem 6.1 and by assuming additional property of the
objective function:

  * •

For a maximization objective $f$, we need superadditivity:
$f(\sum_{r}\ell_{r})\geq\sum_{r}f(\ell_{r})$.

  * •

For a minimization objective $f$, we need subadditivity:
$f(\sum_{r}\ell_{r})\leq\sum_{r}f(\ell_{r})$.

######  Theorem 7.3.

Let $f$ be a well-behaved function. If $f$ is superadditive, the following
theorem holds for maximization of $f$, while if $f$ is subadditive, the
following theorem holds for minimization of $f$. Let $T$ be the expectation of
the maximum value of $f$ over instances sampled from $\mathcal{D}$. Fix an
$\epsilon>0$ for which the small items assumption holds. Then, there is an
(learning) algorithm that samples $O(\frac{m}{\log
m}\cdot\log\frac{m}{\epsilon})$ independent instances from $\mathcal{D}$ and
outputs (with high probability) a prediction vector $\mathbf{w}$ such that
using $\mathbf{w}$ in the EP-allocation gives a value of $f$ that is at least
$(1-\Omega(\epsilon))\cdot T$ for maximization and at most
$(1+O(\epsilon))\cdot T$ for minimization, in expectation over instances
$P\sim\mathcal{D}$.

###### Proof.

Fix a maximization objective function $f$ and distribution $\mathcal{D}$ (the
proof for a minimization objective is similar and omitted for brevity).
Consider the instance $\mathbb{P}=\bigoplus\text{Pr}_{D}[P]\cdot P$ where
$\text{Pr}_{D}[P]$ is the probability mass of $P$ in $\mathcal{D}$, and
$\text{Pr}_{D}[P]\cdot P$ is the matrix $P$ multiplied by $\text{Pr}_{D}[P]$.
By our superadditivity assumption, we have

$f(\ell^{f}(\mathbb{P}))\geq\sum_{P}\text{Pr}_{\mathcal{D}}[P]f(\ell^{f}(P))=\mathbb{E}_{P\sim
D}[f(\ell^{f}(P))]=T.$

Suppose we sample $H=O\left(\frac{m}{\log m}\log\frac{m}{\epsilon}\right)$
instances $P^{(1)},P^{(2)},\dots,P^{(H)}$ independently and randomly from
$\mathcal{D}$. Now, using the small items assumption, it is possible to
compute $\hat{\ell}^{f}_{i}$ which is a $(1+\epsilon)$ approximation to
$\ell^{f}_{i}(\mathbb{P})$ for all $i\in[m]$. Similar to the previous
construction, given a matrix $P$, we define $\tilde{P}$ as
$\tilde{p}_{i,j}=\frac{{P}_{i,j}}{\hat{\ell}^{f}_{i}}$. By the monotonicity
property of $f$, we have: $\mathbb{E}_{P\sim
D}[\ell^{\textbf{SNT}}(\tilde{P})]\geq 1-\epsilon$.

We output $\mathbf{w}^{*}\in\textbf{NET}(m,\epsilon)$ that maximizes
$\min_{i\in[m]}\frac{1}{H}\sum_{h=1}^{H}\ell_{i}(\tilde{P}_{h},\tilde{\mathbf{w}})$.
Then according to the proof of Theorem 6.1, for $P\sim D$, we have with high
probability for every $i\in[m]$:

$\ell_{i}(\tilde{P},\mathbf{w}^{*})\geq 1-\Omega(\epsilon).$

Let us now define $\mathbf{w}$ such that
$w_{i}=\frac{w^{*}_{i}}{({\hat{\ell}^{f}_{i})}^{\alpha}}$. Then, by the
homogeneity property, for a random $P\sim\mathcal{D}$, the objective function
$f$ corresponding to the assignment $x_{i,j}(P,\mathbf{w})$ is at least
$(1-\Omega(\epsilon))\cdot T$ with high probability. ∎

##  8 Conclusion and Future Directions

In this paper, we gave a unifying framework for designing near-optimal
algorithm for fractional allocation problems for essentially all well-studied
minimization and maximization objectives in the literature. The existence of
this overarching framework is rather surprising because the corresponding
worst-case problems exhibit a wide range of behavior in terms of the best
competitive ratio achievable, as well as the techniques required to achieve
those bounds. It would be interesting to gain further understanding of the
optimal learned parameters introduced in this paper. One natural conjecture is
that these are optimal dual variables for a suitably defined convex program
(for instance, such convex programs are known for restricted assignment and
$b$-matching [agrawal2018proportional]). Another interesting direction of
future work would be to explore other polytopes beyond the simple assignment
polytope considered in this paper, such as that corresponding to congestion
minimization problems.

## References

  * [AAF+97] James Aspnes, Yossi Azar, Amos Fiat, Serge A. Plotkin, and Orli Waarts.  On-line routing of virtual circuits with applications to load balancing and machine scheduling.  J. ACM, 44(3):486–504, 1997.
  * [AAG+95] Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming-Yang Kao, P. Krishnan, and Jeffrey Scott Vitter.  Load balancing in the l${}_{\mbox{p}}$ norm.  In 36th Annual Symposium on Foundations of Computer Science, pages 383–391. IEEE Computer Society, 1995.
  * [AGKK20] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev.  Secretary and online matching problems with machine learned advice.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020\.
  * [ALT21] Yossi Azar, Stefano Leonardi, and Noam Touitou.  Flow time scheduling with uncertain processing time.  In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1070–1080. ACM, 2021.
  * [ALT22] Yossi Azar, Stefano Leonardi, and Noam Touitou.  Distortion-oblivious algorithms for minimizing flow time.  In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 252–274. SIAM, 2022.
  * [ANR95] Yossi Azar, Joseph Naor, and Raphael Rom.  The competitiveness of on-line assignments.  J. Algorithms, 18(2):221–237, 1995.
  * [AZM18] Shipra Agrawal, Morteza Zadimoghaddam, and Vahab Mirrokni.  Proportional allocation: Simple, distributed, and diverse matching with high entropy.  In International Conference on Machine Learning, pages 99–108. PMLR, 2018.
  * [BGGJ22] Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin.  Online nash social welfare maximization with predictions.  In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 1–19. SIAM, 2022.
  * [BKM22] Siddharth Barman, Arindam Khan, and Arnab Maiti.  Universal and tight online algorithms for generalized-mean welfare.  In Thirty-Sixth AAAI Conference on Artificial Intelligence, pages 4793–4800. AAAI Press, 2022.
  * [BMRS20] Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson.  Learning augmented energy minimization via speed scaling.  In Advances in Neural Information Processing Systems 33, NeurIPS 2020, 2020.
  * [Cal65] DK Callebaut.  Generalization of the cauchy-schwarz inequality.  Journal of mathematical analysis and applications, 12(3):491–494, 1965.
  * [Car08] Ioannis Caragiannis.  Better bounds for online load balancing on unrelated machines.  In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pages 972–981. SIAM, 2008.
  * [CI21] Justin Y. Chen and Piotr Indyk.  Online bipartite matching with predicted degrees.  CoRR, 2021.
  * [HKPS22] MohammadTaghi Hajiaghayi, MohammadReza Khani, Debmalya Panigrahi, and Max Springer.  Online algorithms for the santa claus problem.  In Advances in Neural Information Processing Systems 35, NeurIPS 2022, 2022.
  * [IKQP21] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit.  Non-clairvoyant scheduling with predictions.  In SPAA ’21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021, pages 285–294. ACM, 2021.
  * [KPS+19] Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, and Erik Vee.  Semi-online bipartite matching.  In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, volume 124 of LIPIcs, pages 50:1–50:20. Schloss Dagstuhl \- Leibniz-Zentrum für Informatik, 2019.
  * [LLMV20] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Online scheduling via learned weights.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 1859–1877. SIAM, 2020.
  * [LMRX21a] Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu.  Learnable and instance-robust predictions for online matching, flows and load balancing.  In 29th Annual European Symposium on Algorithms, ESA 2021, volume 204 of LIPIcs, pages 59:1–59:17, 2021.
  * [LMRX21b] Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu.  Using predicted weights for ad delivery.  In Applied and Computational Discrete Algorithms, ACDA 2021, 2021\.