# Fair Allocation with Interval Scheduling Constraints††thanks: The authors
thanks Warut Suksompong for reading a draft of this paper and for helpful
discussions.

Bo Li
<EMAIL_ADDRESS>
Department of Computing
The Hong Kong Polytechnic University
Hong Kong, China
Minming Li
<EMAIL_ADDRESS>
Department of Computer Science
City University of Hong Kong
Hong Kong, China

Ruilong Zhang
<EMAIL_ADDRESS>
Department of Computer Science
City University of Hong Kong
Hong Kong, China

###### Abstract

We study a fair resource scheduling problem, where a set of interval jobs are
to be allocated to heterogeneous machines controlled by agents. Each job is
associated with release time, deadline and processing time such that it can be
processed if its complete processing period is between its release time and
deadline. The machines gain possibly different utilities by processing
different jobs, and all jobs assigned to the same machine should be processed
without overlap. We consider two widely studied solution concepts, namely,
maximin share fairness and envy-freeness. For both criteria, we discuss the
extent to which fair allocations exist and present constant approximation
algorithms for various settings.

##  1 Introduction

With the rapid progress of AI technologies, AI algorithms are widely deployed
in many societal settings and used to assist human decision-making such as the
distribution of job and education opportunities. To motivate our study, let us
consider a problem faced by the Students Affairs Office (SAO). An SAO clerk is
assigning multiple part-time jobs to the students who submitted job
applications. Each part-time job occupies a consecutive time period within a
possibly flexible interval. For example, a one-hour math tutorial needs to be
given between 8:00am and 11:00am on June 26th. A feasible assignment requires
that the jobs assigned to an applicant can be scheduled without mutual
overlap. The students are heterogeneous, i.e., different students may hold
different job preferences. It is important that the students are treated
equally in terms of getting job opportunities, and thus the clerk’s task is to
make the assignment fair.

The SAO problem falls under the umbrella of the research on job scheduling,
which has been studied in numerous fields, including operations research
Gentner et al. (2004), machine learning Paleja et al. (2020), parallel
computing Drozdowski (2009), cloud computing Al-Arasi and Saif (2020), etc.
Following the convention of job scheduling research, each part-time job, or
job for short, is associated with release time, deadline, and processing time.
The students are modeled as machines, who have different utility gains for
completing jobs. Traditionally, the objective of designing scheduling
algorithms is solely focused on efficiency or profit. However, motivated by
various real-world AI driven deployments where the data points of the
algorithms are real human beings who should be treated unbiasedly, addressing
the individual fairness becomes important. Accordingly, the past several years
has seen considerable efforts in developing fair AI algorithms Chierichetti et
al. (2017), where combinatorial structures are incorporated into the design,
such as vertex cover Rahmattalabi et al. (2019), facility location Chen et al.
(2019) and knapsack Amanatidis et al. (2020).

It is noted that people have different criteria on evaluating fairness, and in
this work, we consider two of the most widely accepted definitions. The first
is motivated by the max-min objective, i.e., maximizing the worst-case
utility, which has received observable attention for various learning
scenarios Rahmattalabi et al. (2019). However, for heterogeneous agents,
optimizing the worst case is not enough, as different people have different
perspectives and may not agree on the output. Accordingly, one popular
research agenda is centered around computing an assignment such that everyone
believes that it (approximately) maximizes the worst case utility. Budish
(2010). The second one is envy-freeness (EF), which has been very widely
studied in social sciences and economics. Informally, an assignment is called
EF if everyone believes she has obtained the best resource compared with any
other agent’s assignment. We note that, due to the scheduling-feasible
constraint, some jobs may not be allocated. Thus EF alone is not able to
satisfy the agents as keeping all resources unallocated does not incur any
envy among them, but the agents envy the charity where unallocated/disregarded
items are assumed to be donated to a "charity". To resolve this issue, in this
work, we want to understand how we can compute allocations that are
simultaneously EF and Pareto efficient (PO), where an allocation is called PO
if there does not exist another allocation that makes nobody worse off but
somebody strictly better off.

Recently, Chiarelli et al. (2020) and Hummel and Hetland (2021) studied the
fair allocation of conflicting items, where the items are connected via
graphs. An edge between two items means they are in conflict and should be
allocated to different agents. However, in our model, since we allow the time
intervals to be flexible, the conflict among items cannot be described as the
edges in a graph. For example, two one-hour tutorials between 9:00am and
11:00am can be feasibly scheduled, but three such tutorials are not feasible
any more.

###  1.1 Main Results

We study the fair interval scheduling problem (FISP), where fairness is
captured by MMS and EF. For each of them, we design approximation algorithms
to compute MMS or EF1 schedules.

Maximin Share. Informally, a machine’s MMS is defined to be its optimal worst-
case utility in an imaginary experiment: it partitions the items into $m$
bundles but was the last to select one, where $m$ is the number of agents. It
is noted that as the machines are heterogeneous, they may not have the same
MMS value. Our task is to investigate the extent to which everyone agrees on
the final allocation. A job assignment is called $\alpha$-approximate MMS fair
if every machine’s utility is no less than $\alpha$ fraction of its MMS value.
Our main result in this part is an algorithmic framework which ensures a
$1/3$-approximate MMS schedule, and thus improves the best known approximation
of $1/5$ which is proved for a broader class of valuation functions – XOS
Ghodsi et al. (2018). Interestingly, in the independent and parallel work
Hummel and Hetland (2021), the authors also show the existence of
$1/3$-approximate MMS for graphically conflicting items. With XOS valuation
oracles, Ghodsi et al. (2018) also designed a polynomial-time algorithm to
compute a $0.125$-approximate MMS allocation. As a comparison, by slightly
modifying our algorithm, it returns a $0.24$-approximate MMS allocation in
polynomial time, without any oracle assumptions. When all jobs are rigid and
utilities are identical, i.e., processing time = deadline - release time, our
problem degenerates to finding a partition of an interval graph such that the
minimum weight of the independent set for each subgraph is maximized.
Recently, a pseudo-polynomial-time algorithm is given in Chiarelli et al.
(2020) for a constant number of agents. In this sense, we generalize this
problem to flexible jobs and design approximation algorithms for an arbitrary
number of agents.

Main Result 1. For an arbitrary FISP instance, there exists a
$1/3$-approximate MMS schedule, and a $(0.24-\epsilon)$-approximate MMS
schedule can be found in polynomial time, for any constant $\epsilon>0$.

EF1+PO. EF is actually a demanding fairness notion, in the sense that any
approximation of EF is not compatible with PO. Instead, initiated by Lipton et
al. (2004), most research is focused on its relaxation, envy-freeness up to
one item (EF1), which means the envy between two agents may exist but will
disappear if some item is removed. Unfortunately, EF1 and PO are still not
compatible even if all jobs are rigid and agents have unary valuations.
However, the good news is, if all jobs have unit processing time, an EF1 and
PO schedule is guaranteed to exist and can be found in polynomial time. This
result continues to hold when agent valuations are weighted but identical,
i.e., the jobs have different values. It is shown in Biswas and Barman (2018)
that under laminar matroid constraint an EF1 and PO allocation exists when
agents have identical utilities, but the efficient algorithm is not given. We
improve this result in two perspectives. First, our feasibility constraints,
even for unit jobs, do not necessary correspond to laminar matroid. Second,
our algorithm runs in polynomial time.

Main Result 2. No algorithm can return an EF1 and PO schedule for all FISP
instances, even if all jobs are rigid and valuations are unary. When all jobs
have unit processing time and valuations are (weighted) identical, an EF1 and
PO schedule can be computed in polynomial time.

Although exact EF1 and PO are not compatible, we prove that for an arbitrary
FISP instance, there always exists a $1/4$-approximate EF1 and PO schedule,
which coincides with Wu et al. (2021). In the setting of Wu et al. (2021),
each job has a value and a weight but there is no release time, processing
time and deadline. Every agent has a budget and every subset of jobs that the
total weight does not exceed the agent’s budget can be assigned to the agent.
If all jobs have unit processing time, a $1/2$-approximate EF1 and PO schedule
exists. To prove this result, we consider Nash social welfare – the geometric
mean of all machines’ utilities. We show that a Nash social welfare maximizing
schedule satisfies the desired approximation ratio. This result is in contrast
to the corresponding one in Caragiannis et al. (2016), which shows that
without any feasibility constraints, such an allocation is EF1 and PO. We also
show that both approximations are tight.

Main Result 3. For any FISP instance, the schedule maximizing Nash social
welfare is PO and $1/4$-approximate EF1. If all jobs have unit processing
time, it is $1/2$-approximate EF1.

##### EF1+IO

By the above results, we observe that PO is too demanding to measure
efficiency in our model. One milder requirement is individual optimality (IO).
Intuitively, an allocation is called IO if every agent gets the best feasible
subset of jobs from the union of her current jobs and unscheduled jobs. We
show that EF1 is still not compatible with IO in the general case. But for
unary valuations, we obtain positive results and design polynomial time
algorithms for (1) computing an EF1 and IO schedule for rigid jobs, and (2)
computing an EF1 and 1/2-approximate IO schedule for flexible jobs. To prove
these results, we utilize two classic algorithms Earliest Deadline First and
Round-Robin.

###  1.2 Related Works

Since computing feasible job sets to maximize the total weight is NP-hard
Garey and Johnson (1979), various approximation algorithms have been proposed
Bar-Noy et al. (2001); Berman and DasGupta (2000); Chuzhoy et al. (2006), and
the best known approximation ratio is $0.644$ Im et al. (2020). For rigid
instances, the problem is polynomial-time solvable Schrijver (1999). Recently,
scheduling has been studied from the perspective of machine learning,
including developing learning algorithms to empirically solve NP-hard
scheduling problem Zhang et al. (2020); Paleja et al. (2020), and predicting
uncertain data in order to optimize the performance in the online setting
Purohit et al. (2018). Fairness has been concerned in the scheduling community
in the past decades Ajtai et al. (1998); Baruah and Lin (1998); Baruah (1995).
Most of these works aim at finding a fair schedule for the jobs, such as
balancing the waiting and completion time Bilò et al. (2016); Im and Moseley
(2020).

MMS allocation for indivisible resources has been widely studied since Budish
(2010). Unfortunately, it is shown in Kurokawa et al. (2018); Ghodsi et al.
(2018); Feige et al. (2021) that an exact MMS fair allocation may not exist.
Thereafter, a string of approximation algorithms for various valuation types
are proposed, such as additive Garg and Taki (2020), submodular Barman and
Krishnamurthy (2020); Ghodsi et al. (2018), XOS and subadditive Ghodsi et al.
(2018). Regarding EF1, in the unconstrained setting, an allocation that is
both EF1 and PO is guaranteed to exist Caragiannis et al. (2016); Barman et
al. (2018). However, when there are constraints, such as cardinality and
knapsack, the general compatibility is still open Biswas and Barman (2018);
Biswas and Barman (2019); Dror et al. (2020); Wu et al. (2021).

##  2 Preliminaries

###  2.1 Fair Interval Scheduling Problem

In a fair interval scheduling problem (FISP), we are given a job-machine
system, which is denoted by tuple $(J,A,\mathbf{u}_{A})$.
$J=\set{j_{1},\cdots,j_{n}}$ represents a set of $n$ jobs (also called
resources or items) and $A=\set{a_{1},\cdots,a_{m}}$ is a set of $m\geqslant
2$ machines controlled by agents. In this work, machines and agents are used
interchangeably. We consider discrete time, and for $t\in\mathbb{N}_{+}$, let
$[t,t+1)$ denote the $t$-th time slot. Each $j_{i}\in J$ is associated with
release time $r_{i}\in\mathbb{N}_{+}$, deadline $d_{i}\in\mathbb{N}_{+}$, and
processing time $p_{j}\in\mathbb{N}_{+}$ such that $p_{i}\leqslant
d_{i}-r_{i}+1$. The $[r_{i},d_{i}]$ is called a job interval, which can also
be viewed as a set of consecutive time slots,
$\set{r_{i},r_{i}+1,\cdots,d_{i}}$. Job $j_{i}$ can be processed successfully
if it is offered $p_{i}$ consecutive time slots within $[r_{i},d_{i}]$. Each
machine can process at most one job at each time slot and a set of jobs
$J^{\prime}\subseteq J$ is called feasible if all jobs in $J^{\prime}$ can be
processed without overlap on a single machine. For a job $j_{k}\in J$, agent
$a_{i}\in A$ gains utility $u_{i}(\set{j_{k}})\geqslant 0$ if $j_{k}$ is
successfully processed by $a_{i}$. We slightly abuse the notation and assume
that $u_{i}(j_{k})=u_{i}(\set{j_{k}})$. We use $u_{i}$ to denote $a_{i}$’s
utility function, and define $\mathbf{u}_{A}=(u_{i})_{i\in A}$. For a feasible
set of jobs $S$, the agent’s utility is additive, i.e.,
$u_{i}(S)=\sum_{j_{k}\in S}u_{i}(j_{k})$. For an arbitrary set of jobs that
may not be feasible, the agent’s utility is the maximum she can obtain by
processing a feasible subset, i.e.,

$u_{i}(S)=\max_{S^{\prime}\subseteq S:\text{ $S^{\prime}$ is
feasible}}\sum_{j_{k}\in S^{\prime}}u_{i}(j_{k}).$

It is noted that $u_{i}(\cdot)$’s are not additive for infeasible set of jobs
and the computation of its value is NP-hard Garey and Johnson (1979). In
appendix A, we show that they are actually XOS, which is a special type of
subadditive functions. We call these $u_{i}(\cdot)$’s interval scheduling (IS)
functions.

A schedule or allocation $\mathbf{X}=(X_{1},\cdots,X_{m})$ is defined as an
ordered partial partition of $J$, where $X_{i}$ is the jobs assigned to agent
$a_{i}$, such that $X_{i}\cap X_{j}=\emptyset$ for $i\neq j$ and
$X_{1}\cup\cdots\cup X_{m}\subseteq J$. Let
$X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}$ denote all unscheduled jobs, which is
regarded as the donation to a charity. A schedule $\mathbf{X}$ is called
feasible if $X_{i}$ is feasible for all $a_{i}\in A$, i.e., all jobs in
$X_{i}$ can be successfully processed by $a_{i}$. Note that since jobs in
$X_{0}$ are not scheduled, $X_{0}$ is not necessarily feasible. Observe that
any infeasible schedule $\mathbf{X}$ is equivalent to a feasible schedule
$\mathbf{X}^{\prime}$ by setting each $X^{\prime}_{i}$ to be the feasible
subset of $X_{i}$ that maximizes $a_{i}$’s utility and
$X^{\prime}_{0}=J\setminus\bigcup_{i\in[m]}X_{i}^{\prime}$. We call an
instance rigid if $p_{i}=d_{i}-r_{i}+1$, for all $j_{i}\in J$, i.e., the jobs
need to occupy the entire job intervals. For rigid instances, the feasibility
constraints can be described via interval graphs and the computation of
$u_{i}(S)$ for any $S\subseteq J$ can be done in polynomial time Kleinberg and
Tardos (2006).

As we will discuss the approximation algorithms and the existences of
MMS/EF1/PO/IO schedules in different settings, we introduce the following
notations to simplify the description of different settings.

Regarding agents’ utilities, FISP contains three cases, from the most special
to the most general:

  * •

Unweighted: $u_{i}(j_{k})=1$ for all $a_{i}\in A,j_{k}\in J$, i.e., agents
have unary utility for jobs.

  * •

Identical: $u_{i}(j_{k})=u_{r}(j_{k})$ for all $a_{i},a_{r}\in A,j_{k}\in J$,
i.e., all agents have the same utility for the same job.

  * •

Non-identical: $u_{i}(j_{k})\geqslant 0$ without any restrictions.

Regarding jobs, there are three cases:

  * •

Unit: $p_{i}=1$, for all $j_{i}\in J$, i.e., all jobs have unit processing
time.

  * •

Rigid: $r_{i}+p_{i}-1=d_{i}$, for all $j_{i}\in J$, i.e., the jobs need to
occupy the entire time intervals between their release times and deadlines.

  * •

Flexible: $r_{i}+p_{i}-1\leqslant d_{i}$, for all $j_{i}\in J$.

Note that unit jobs may not be rigid and rigid jobs may not be unit either. In
the remainder of the paper, we use notation FISP with $\langle$utility type,
job type$\rangle$ to denote a certain case of the general FISP, e.g., FISP
with $\langle$unweighted, unit$\rangle$ represents the case where the
processing time of each job is 1 and each agent has unweighted utility
function.

###  2.2 Solution Concepts

We first define the maximin value for any utility function $u$, item set $S$
and the number of agents $k$. Let $\mathcal{F}(S,k)$ be the set of all
$k$-partial-partitions of $S$ and

$\mathsf{MMS}^{u}(S,k)=\max_{(S_{1},\cdots,S_{k})\in\mathcal{F}(S,k)}\min_{i\in[k]}u(X_{i}).$

For any FISP instance $(J,A,\mathbf{u}_{A})$ with $m=|A|$, agent $a_{i}\in
A$’s maximin share (MMS) is given by

$\mathsf{MMS}_{i}(J,m)=\mathsf{MMS}^{u_{i}}(J,m).$

When the parameters are clear in the context, we write
$\mathsf{MMS}_{i}=\mathsf{MMS}_{i}(J,m)$ for simplicity. If a schedule
$\mathbf{X}$ achieves $\mathsf{MMS}_{i}$, i.e.,
$\min_{k\in[m]}u_{i}(X_{k})=\mathsf{MMS}_{i}$, it is called an MMS schedule
for $a_{i}$.

######  Definition 1 ($\alpha$-MMS Schedule).

For $0<\alpha\leqslant 1$, a schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$ is
called $\alpha$-approximate MMS ($\alpha$-MMS) if
$u_{i}(X_{i})\geqslant\alpha\cdot\mathsf{MMS}_{i}$. When $\alpha=1$,
$\mathbf{X}$ is called an MMS schedule.

We next introduce envy freeness (EF). An EF schedule
$\mathbf{X}=(X_{1},\cdots,X_{m})$ requires everybody’s utility to be no less
than her utility for any other agent’s bundle, i.e., $u_{i}(X_{i})\geqslant
u_{i}(X_{k})$ for any $a_{i},a_{k}\in A$. Since EF is over demanding for
indivisible items, following the convention of fair division literature, in
this work, we mainly consider EF1.

######  Definition 2 ($\alpha$-EF1 Schedule).

For $0<\alpha\leqslant 1$, a schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$ is
called $\alpha$-approximate envy-free up to one item ($\alpha$-EF1) if for any
two agents $a_{i},a_{k}\in A$,

$u_{i}(X_{i})\geqslant\alpha\cdot u_{i}(X_{k}\setminus\\{j\\})\text{ for some
$j\in X_{k}$}.$

When $\alpha=1$, $\mathbf{X}$ is called an EF1 schedule.

We observe that an empty schedule is trivially EF and EF1, i.e., $X_{0}=J$ and
$X_{i}=\emptyset$ for all $a_{i}\in A$. However, this is a highly inefficient
schedule, and thus we also want the schedule to be Pareto optimal.

######  Definition 3 (PO schedule).

A schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$ is called Pareto Optimal (PO) if
there does not exist an alternative schedule
$\mathbf{X}^{\prime}=(X_{1}^{\prime},\cdots,X_{m}^{\prime})$ such that
$u_{i}(X_{i}^{\prime})\geqslant u_{i}(X_{i})$ for all $a_{i}\in A$, and
$u_{k}(X_{k}^{\prime})>u_{k}(X_{k})$ for some $a_{k}\in A$.

We note that any approximation of EF is not compatible with PO, even in the
very simple setting with two machines and a single job. In the following, we
introduce another efficiency criterion, individual optimality (IO), which is
weaker than PO and study the compatibility between EF1 and IO.

######  Definition 4 ($\alpha$-IO schedule).

A feasible schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$ with
$X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}$ is called $\alpha$-approximate
individual optimal ($\alpha$-IO) if $u_{i}(X_{i})\geqslant\alpha\cdot
u_{i}(X_{0}\cup X_{i})$ for all $a_{i}\in A$, where $\alpha\in(0,1]$ and when
$\alpha=1$, $\mathbf{X}$ is called IO schedule.

It is not hard to see that a PO schedule is also IO, but not vice versa. To
show the existences and approximation of EF1/PO/IO, we sometimes use the
schedule which maximizes the Nash social welfare.

######  Definition 5 (MaxNSW Schedule).

A feasible schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$ is called MaxNSW
schedule if and only if

$\mathbf{X}\in\operatorname*{arg\,max}_{\mathbf{X}^{\prime}\in\mathcal{F}}\prod_{i=1}^{m}u_{i}(X_{i}^{\prime})$

where $\mathcal{F}$ is the set of all feasible schedules and
$\mathbf{X}^{\prime}=(X_{1}^{\prime},\cdots,X_{m}^{\prime})$.

Note that in the standard definition of Nash social welfare maximizing
schedule, $\mathbf{X}$ was supposed to be a member of
$\operatorname*{arg\,max}_{\mathbf{X}^{\prime}\in\mathcal{F}}\bigg{(}\prod_{i=1}^{m}u_{i}(X_{i}^{\prime})\bigg{)}^{\frac{1}{m}}$.
Here, we ignore the power of $\frac{1}{m}$ to simplify the formula.

##  3 Approximately MMS Scheduling

Before introducing our algorithmic framework, we first recall the best known
existential and computation results for MMS scheduling problems.

######  Observation 1 (Ghodsi et al. (2018)).

For an arbitrary FISP instance, there exists a 1/5-MMS schedule and a 1/8-MMS
schedule can be computed in polynomial time, given XOS function oracle.

###  3.1 Algorithmic Framework

In this section, we present our algorithmic framework and prove that it
ensures a $1/3$-MMS schedule. The algorithm has two parameters, a threshold
vector $(\gamma_{1},\cdots,\gamma_{m})$ with $\gamma_{i}\geqslant 0$ and a
$\beta$-approximation algorithm for IS functions, where
$0\leqslant\beta\leqslant 1$. In this section, we set
$\gamma_{i}=\mathsf{MMS}_{i}$ for each $a_{i}\in A$. We can pretend that
$\beta=1$ to understand the existential result easily. Note that the
computations of each $\mathsf{MMS}_{i}$ and exact value for IS functions are
NP-hard, and in section 3.2, we show how to gradually adjust the parameters to
make it run in polynomial time. The high-level idea of the algorithm is to
repeatedly fill a bag with unscheduled jobs (which may not be feasible) until
some agent values it for no less than a threshold and takes away the bag. Then
this agent reserves her best feasible subset of the bag, and returns the
remaining jobs to the algorithm. By carefully designing the thresholds, we
show that everybody can obtain at least $\frac{\beta}{\beta+2}$ of her MMS.

####  3.1.1 Pre-processing

As we will see, the above bag-filling algorithm works well only if the jobs
are small, i.e., $u_{i}(j_{k})\leqslant\frac{\beta}{\beta+2}\cdot\gamma_{i}$
for all $a_{i}\in A$ and $j_{k}\in J$. We first introduce the following
property, which is used to deal with large jobs. Intuitively, lemma 1 implies
that after allocating an arbitrary job to an arbitrary agent, the remaining
agents’ MMS values in the reduced sub-instance do not decrease. A similar
result for additive valuations is proved in Amanatidis et al. (2017).

######  Lemma 1.

For any instance $\mathcal{I}=(J,A,\mathbf{u}_{A})$ with $|A|=m$, the
following inequality holds for any $a_{i}\in A$ and any $j_{k}\in J$,

$\mathsf{MMS}_{i}(J\setminus\set{j_{k}},m-1)\geqslant\mathsf{MMS}_{i}(J,m).$

###### Proof.

Let $\mathcal{I}=(J,A,\mathbf{u}_{A})$ be an arbitrary instance of FISP with
$J=\set{j_{1},\cdots,j_{m}}$ and $|A|=m$. To show that
$\mathsf{MMS}_{i}(J\setminus\set{j_{k}},m-1)\geqslant\mathsf{MMS}_{i}(J,m)$
holds for any $j_{k}\in J,a_{i}\in A$, we consider an arbitrary agent $a_{i}$.
Let $\mathbf{X}=(X_{1},X_{2},\cdots,X_{m})$ be a feasible schedule for
$a_{i}$, i.e., $\min_{X_{r}\in\mathbf{X}}u_{i}(X_{r})=\mathsf{MMS}_{i}$.
Consider an arbitrary job $j_{k}$, assume that $j_{k}\in X_{l}$. Then remove
job set $X_{l}$ from $\mathsf{MMS}_{i}$ schedule. This generates a new
schedule, denoted by
$\mathbf{X}^{\prime}=\set{X_{1}^{\prime},X_{2}^{\prime},\cdots,X_{m-1}^{\prime}}$.
It is easy to see that $\mathbf{X}^{\prime}$ is a feasible schedule to the
instance with $m-1$ agents and the job set $J\setminus\set{J_{k}}$. This
implies that
$\mathsf{MMS}_{i}(J\setminus\set{j_{k}},m-1)\geqslant\min_{X_{r}^{\prime}\in\mathbf{X}^{\prime}}u_{i}(X_{r}^{\prime})$.
Note that
$\min_{X_{r}^{\prime}\in\mathbf{X}^{\prime}}u_{i}(X_{r}^{\prime})\geqslant\mathsf{MMS}_{i}(J,m)$.
Therefore, we have

$\mathsf{MMS}_{i}(J\setminus\set{j_{k}},m-1)\geqslant\min_{X_{r}^{\prime}\in\mathbf{X}^{\prime}}u_{i}(X_{r}^{\prime})\geqslant\mathsf{MMS}_{i}(J,m).$

In the case where $j_{k}\notin\bigcup_{r\in[m]}X_{r}$, we remove an arbitrary
job set from $\mathbf{X}$ and the above analysis still works. ∎

We use lemma 1 to design algorithm 1 which repeatedly allocates a large job to
some agent and removes them from the instance until there is no large job.

Algorithm 1 . Matching Procedure

0: Arbitrary FISP instance $\mathcal{I}=(J,A,\mathbf{u}_{A})$; Thresholds
$(\gamma_{1},\cdots,\gamma_{m})$.

0: (1) Sub-instance
$\mathcal{I}^{\prime}=(J^{\prime},A^{\prime},\mathbf{u}_{A^{\prime}})$ such
that $u_{i}(j_{k})\leqslant\frac{\beta}{\beta+2}\cdot\gamma_{i}$ for all
$a_{i}\in A^{\prime}$ and $j_{k}\in J^{\prime}$; (2) Partial Schedule
$(X_{r})_{a_{r}\in A\setminus A^{\prime}}$.

1: Initialize $A^{\prime}=A$ and $J^{\prime}=J$.

2: while there is an agent $a_{i}\in A^{\prime}$ and a job $j_{k}\in
J^{\prime}$ with $u_{i}(j_{k})>\frac{\beta}{\beta+2}\cdot\gamma_{i}$ do

3: Set $X_{i}=\set{j_{k}}$, $A^{\prime}=A^{\prime}\setminus\set{a_{i}}$, and
$J^{\prime}=J^{\prime}\setminus\set{j_{k}}$.

4: end while

By lemma 1, it is straightforward to have the following lemma.

######  Lemma 2.

For any instance $\mathcal{I}=(J,A,\mathbf{u}_{A})$ with
$(\gamma_{1},\cdots,\gamma_{m})$, the partial schedule $(X_{r})_{a_{r}\in
A\setminus A^{\prime}}$ and the reduced instance
$\mathcal{I}^{\prime}=(J^{\prime},A^{\prime},\mathbf{u}_{A^{\prime}})$
returned by algorithm 1 satisfy
$u_{r}(X_{r})\geqslant\frac{\beta}{\beta+2}\cdot\gamma_{r}$ for all $a_{r}\in
A\setminus A^{\prime}$ and
$\mathsf{MMS}_{i}(J^{\prime},|A^{\prime}|)\geqslant\mathsf{MMS}_{i}(J,|A|)$
for all $a_{i}\in A^{\prime}$.

####  3.1.2 Bag-Filling Procedure

Let $\mathcal{I}=(J,A,\mathbf{u}_{A})$ be an instance such that $|A|=m$ and
$u_{i}(j_{k})\leqslant\frac{\beta}{\beta+2}\cdot\gamma_{i}$ for all $a_{i}\in
A$ and $j_{k}\in J$. We show the Bag-Filling Procedure in algorithm 2, with
parameters $(\gamma_{1},\cdots,\gamma_{m})$ and $\beta$-approximation
algorithm for IS functions. For each $a_{i}\in A$, we use
$u^{\prime}_{i}:2^{J}\to\mathbb{R}_{+}$ to denote the approximate utility, and
thus $u^{\prime}_{i}(S)\geqslant\beta\cdot u_{i}(S)$ for any $S\subseteq J$.
Intuitively, it keeps a bag $B$ and repeatedly adds an unscheduled job into it
until some agent $a_{i}$ first values this bag (under the approximate utility
function $u^{\prime}_{i}$) for at least
$\frac{\beta}{\beta+2}\cdot\gamma_{i}$. If there are more than one such
agents, arbitrarily select one of them. Then $a_{i}$ gets assigned a feasible
subset $X_{i}\subseteq B$ with $\sum_{j_{l}\in
X_{i}}u_{i}(j_{l})=u_{i}^{\prime}(B)$, and returns $B\setminus X_{i}$ to the
algorithm. This step is crucial, otherwise the other remaining agents may not
obtain enough jobs. It is obvious that if agent $a_{i}$ gets assigned a bag,
then her true utility satisfies

$u_{i}(X_{i})=\sum_{j_{l}\in
X_{i}}u_{i}(j_{l})=u^{\prime}_{i}(X_{i})\geqslant\frac{\beta}{\beta+2}\cdot\gamma_{i}.$

The major technical difficulty of our algorithm is to prove that everyone can
obtain a bag.

Algorithm 2 . BagFilling Procedure

0: An FISP instance $\mathcal{I}=(J,A,\mathbf{u}_{A})$ such that
$u_{i}(j_{k})\leqslant\frac{\beta}{\beta+2}\cdot\gamma_{i}$ for all $a_{i}\in
A$ and $j_{k}\in J$; $\beta$-approximation algorithm for IS functions;
Thresholds $(\gamma_{1},\cdots,\gamma_{m})$.

0: $\frac{\beta}{\beta+2}$-MMS schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$.

1: Initialize $A^{\prime}=A,J^{\prime}=J$, and obtain approximate utility
functions $u^{\prime}_{i}$ for all $a_{i}\in A$.

2: while $A^{\prime}\neq\emptyset$ and $J^{\prime}\neq\emptyset$ do

3: Set $B=\emptyset$.

4: while $u^{\prime}_{i}(B)<\frac{\beta}{\beta+2}\cdot\gamma_{i}$ for all
$a_{i}\in A^{\prime}$ and $J^{\prime}\neq\emptyset$ do

5: Let $j_{k}$ be an arbitrary job in $J^{\prime}$. Set $B=B\cup\set{j_{k}}$
and $J^{\prime}=J^{\prime}\setminus\set{j_{k}}$.

6: end while

7: Let $a_{i}$ be an arbitrary agent such that
$u^{\prime}_{i}(B)\geqslant\frac{\beta}{\beta+2}\cdot\gamma_{i}$.

8: Let $X_{i}\subseteq B$ be a feasible subset such that $\sum_{j_{l}\in
X_{i}}u_{i}(j_{l})=u^{\prime}_{i}(B)$.

9: Set $J^{\prime}=J^{\prime}\cup(B\setminus X_{i})$ and
$A^{\prime}=A^{\prime}\setminus\set{a_{i}}$.

10: end while

######  Lemma 3.

Setting $\gamma_{i}=\mathsf{MMS}_{i}$ for all $a_{i}\in A$, algorithm 2
returns a $\frac{\beta}{\beta+2}$-MMS schedule.

###### Proof.

As we have discussed, it suffices to prove that at the beginning of any round
of the outer while loop, there are sufficiently many remaining jobs in
$J^{\prime}$ for every remaining agent in $A^{\prime}$, i.e.,

$\displaystyle
u_{i}^{\prime}(J^{\prime})\geqslant\frac{\beta}{\beta+2}\gamma_{i},\text{ for
any $a_{i}\in A^{\prime}$}.$

To prove the above inequality, in the following, we actually prove a stronger
argument.

######  Claim 1.

For any $a_{i}\in A^{\prime}$, let
$\mathbf{X}^{\prime}=(X^{\prime}_{1},\cdots,X^{\prime}_{m})$ be a feasible MMS
schedule for $a_{i}$. Then there exists $k\in[m]$, such that
$u_{i}(X_{k}^{\prime}\cap
J^{\prime})\geqslant\frac{1}{\beta+2}\cdot\gamma_{i}$.

Given 1 and the $\beta$-approximation of $u^{\prime}_{i}$,
$u^{\prime}_{i}(X_{k}^{\prime}\cap
J^{\prime})\geqslant\frac{\beta}{\beta+2}\cdot\gamma_{i}$ and thus the lemma
holds. We prove by contradiction and assume 1 does not hold for agent $a_{i}$.
Since $\mathbf{X}^{\prime}=(X^{\prime}_{1},\cdots,X^{\prime}_{m})$ is a
feasible MMS schedule for $a_{i}$,
$u_{i}(X^{\prime}_{k})\geqslant\mathsf{MMS}_{i}=\gamma_{i}$ for all $k\in[m]$
and thus

$\displaystyle\sum_{k\in[m]}u_{i}(X^{\prime}_{k})\geqslant m\cdot\gamma_{i}.$
(1)

Denote by $(X_{r})_{a_{r}\in A\setminus A^{\prime}}$ the assignments that are
allocated to $A\setminus A^{\prime}$ in previous rounds by algorithm 2, and
for each $a_{r}$, let $j_{l_{r}}$ be the last item added to the bag $B$. Note
that $j_{l_{r}}\in X_{r}$ otherwise $a_{r}$ will stop the inner while loop
(Step 4) before $j_{l_{r}}$ was added. Moreover, since $a_{i}$ did not break
the while loop either,
$u^{\prime}_{i}(X_{r}\setminus\set{j_{l_{r}}})<\frac{\beta}{\beta+2}\cdot\gamma_{i}$.
Thus
$u_{i}(X_{r}\setminus\set{j_{l_{r}}})\leqslant\frac{1}{\beta+2}\cdot\gamma_{i}$
as $u^{\prime}_{i}$ is $\beta$-approximation of $u_{i}$. By the assumption
that all jobs are small, i.e.,
$u_{i}(j_{l_{r}})\leqslant\frac{\beta}{\beta+2}\cdot\gamma_{i}$, we have the
following

$\displaystyle
u_{i}(X_{r})=u_{i}(X_{r}\setminus\set{j_{l_{r}}})+u_{i}(j_{l_{r}})<\frac{\beta+1}{\beta+2}\cdot\gamma_{i}.$
(2)

If $u_{i}(X_{k}^{\prime}\cap J^{\prime})<\frac{1}{\beta+2}\cdot\gamma_{i}$ for
all $k\in[m]$, then

$\displaystyle\sum_{k\in[m]}u_{i}(X_{k}^{\prime})$
$\displaystyle=\sum_{k\in[m]}\left(u_{i}(X_{k}^{\prime}\cap
J^{\prime})+\sum_{a_{r}\in A\setminus A^{\prime}}u_{i}(X_{k}^{\prime}\cap
X_{r})\right)$ $\displaystyle=\sum_{k\in[m]}u_{i}(X_{k}^{\prime}\cap
J^{\prime})+\sum_{a_{r}\in A\setminus
A^{\prime}}\sum_{k\in[m]}u_{i}(X_{k}^{\prime}\cap X_{r})$
$\displaystyle\leqslant\sum_{k\in[m]}u_{i}(X_{k}^{\prime}\cap
J^{\prime})+\sum_{a_{r}\in A\setminus A^{\prime}}u_{i}(X_{r})$
$\displaystyle<m\cdot\frac{1}{\beta+2}\cdot\gamma_{i}+(m-|A^{\prime}|)\cdot\frac{\beta+1}{\beta+2}\cdot\gamma_{i}<m\cdot\gamma_{i},$

where the first inequality is because the $X^{\prime}_{k}$’s are disjoint and
the second inequality is because of equation 2. Thus we obtain a contradiction
with equation 1. ∎

####  3.1.3 Main Existential Theorem

Combining lemma 2 and lemma 3, it is not hard to prove the main existential
result.

Algorithm 3 . Main Algorithm: Matching-BagFilling

0: An arbitrary FISP instance $\mathcal{I}=(J,A,\mathbf{u}_{A})$;
$\beta$-approximation algorithm for IS functions; Thresholds
$(\gamma_{1},\cdots,\gamma_{m})$.

0: $\frac{\beta}{\beta+2}$-MMS schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$.

1: Run algorithm 1 on $\mathcal{I}$ with $(\gamma_{1},\cdots,\gamma_{m})$.
Obtain $\mathcal{I}^{\prime}=(J^{\prime},A^{\prime},\mathbf{u}_{A^{\prime}})$
and $(X_{r})_{a_{r}\in A\setminus A^{\prime}}$.

2: Run algorithm 2 on $\mathcal{I}^{\prime}$ with
$(\gamma_{1},\cdots,\gamma_{m})$ and the $\beta$-approximation algorithm.
Obtain $(X_{i})_{a_{i}\in A^{\prime}}$.

######  Theorem 1.

algorithm 3 with the optimal algorithm for IS functions (i.e., $\beta=1$) and
$\gamma_{i}=\mathsf{MMS}_{i}$ for all $a_{i}\in A$ returns a 1/3-MMS schedule
for arbitrary FISP instance.

Interestingly, in the independent and parallel work Hummel and Hetland (2021),
via a similar bag-filling algorithm, the authors prove the existence of
$1/3$-approximate MMS allocations under the context of graphically conflicting
items. However, the two models in our work and theirs are not compatible in
general.

###  3.2 Polynomial-time Implementation

Note that, in general, algorithm 3 is not efficient, because if P $\neq$ NP,
the computation of exact values for IS functions and MMS values cannot be done
in polynomial time. For the special case when jobs are rigid or unit, IS
functions can be computed in polynomial time. If the number of machines is
constant, MMS values for rigid jobs can be computed in pseudo-polynomial time
Chiarelli et al. (2020). Thus, in this section, we deal with the general case.
Of course, for IS functions, we can directly use the $\beta$-approximation
algorithms, and the best-known approximation ratio is 0.644 Im et al. (2020).
Regarding the MMS barrier, instead of using their approximate values, we
utilize a combinatorial trick similar with one used in Barman and
Krishnamurthy (2020) such that without knowing their values, we can still
execute our algorithm.

First, an important corollary of lemma 2 and lemma 3 is that if
$\gamma_{i}\leqslant\mathsf{MMS}_{i}$ for some $a_{i}$, no matter what values
are set for $\gamma_{j}$, $j\neq i$, algorithm 3 always assigns a bag to
$a_{i}$ such that $u_{i}(X_{i})\geqslant\frac{\beta}{\beta+2}\gamma_{i}$.

######  Lemma 4.

For any $a_{i}$, if $\gamma_{i}\leqslant\mathsf{MMS}_{i}$, algorithm 3 ensures
that $u_{i}(X_{i})\geqslant\frac{\beta}{\beta+2}\gamma_{i}$, regardless of
$\gamma_{-i}$.

We prove lemma 4 in appendix B. Now, we are ready to introduce the trick.
First, we set each $\gamma_{i}$ to be sufficiently large such that
$\gamma_{i}\geqslant\mathsf{MMS}_{i}$ for all $a_{i}$. Then we run algorithm
3. If we found some agent $a_{i}$ with
$u_{i}(X_{i})<\frac{\beta}{\beta+2}\gamma_{i}$, it means $\gamma_{i}$ is
higher than $\mathsf{MMS}_{i}$ and we can decrease $\gamma_{i}$ by
$0<1-\epsilon<1$ fraction and keep the other MMS values unchanged. We repeat
the above procedure until everyone is satisfied
$u_{i}(X_{i})\geqslant\frac{\beta}{\beta+2}\gamma_{i}$. By lemma 4, it must be
that $\gamma_{i}\geqslant(1-\epsilon)\mathsf{MMS}_{i}$ for all $a_{i}$. We
summarize this in algorithm 4, and it is straightforward to have the following
theorem.

Algorithm 4 . Efficient Implementation: Matching-BagFilling

0: An arbitrary FISP instance $\mathcal{I}=(J,A,\mathbf{u}_{A})$;
$\beta$-approximation polynomial-time algorithm for IS functions; Thresholds
$(\gamma_{1}=\frac{u_{1}^{\prime}(J)}{\beta},\cdots,\gamma_{m}=\frac{u_{m}^{\prime}(J)}{\beta})$;
$0<\epsilon<1$.

0: $\frac{\beta}{(\beta+2)}(1-\epsilon)$-MMS schedule
$\mathbf{X}=(X_{1},\cdots,X_{m})$.

1: Run algorithm 3 on $\mathcal{I}$ with $(\gamma_{1},\cdots,\gamma_{m})$.
Obtain $\mathbf{X}=(X_{1},\cdots,X_{m})$.

2: while there exist $a_{i}\in A$ such that
$u^{\prime}_{i}(X_{i})<\frac{\beta}{\beta+2}\gamma_{i}$ do

3: Set $\gamma_{i}=(1-\epsilon)\gamma_{i}$.

4: Run algorithm 3 on $\mathcal{I}$ with $(\gamma_{1},\cdots,\gamma_{m})$ and
update $\mathbf{X}=(X_{1},\cdots,X_{m})$.

5: end while

######  Theorem 2.

For any $0<\epsilon<1$, algorithm 4 returns a
$\frac{\beta}{\beta+2}(1-\epsilon)$-MMS schedule for arbitrary FISP instance
with an $\beta$-approximation algorithm for IS functions. The running time is
polynomial with $|J|$, $|A|$ and $1/\epsilon$. Particularly, using the
0.64-approximation algorithm in Im et al. (2020), we have
$0.24(1-\epsilon)$-approximation polynomial-time algorithm.

##  4 Approximately EF1 and PO Scheduling

In this section, we investigate the extent to which there is a schedule that
is both EF1 and PO. We first show that EF1 and PO are not compatible even if
jobs are rigid and valuations are unary, i.e., $u_{i}(j_{k})=1$ for all
$a_{i}\in A$ and $j_{k}\in J$. That is no algorithm can return an EF1 and PO
schedule for all instances. Fortunately, if the jobs have unit processing
time, an EF1 and PO schedule exists and can be computed in polynomial time.
This result continues to hold if the agents have weighted but identical
utilities, i.e., $u_{i}(j_{k})=u_{r}(j_{k})$ for any job $j_{k}$ and any two
agents $a_{i}$ and $a_{r}$. We sometimes ignore the subscript and use
$u(\cdot)$ to denote the identical valuation.

###  4.1 Incompatibility of EF1 and PO

######  Lemma 5.

EF1 and PO are not compatible for FISP with $\langle$unweighted,
rigid$\rangle$, i.e., no algorithm can return a feasible schedule that is
simultaneously EF1 and PO for all FISP with $\langle$unweighted,
rigid$\rangle$ instances.

###### Proof.

To prove lemma 5, we show that any PO schedule must not be an EF1 schedule for
the instance in figure 1. We consider an arbitrary PO schedule, denoted by
$\mathbf{X}=(X_{1},\cdots,X_{m})$ and let
$X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}$. We claim that $\mathbf{X}$ must
satisfy the following two properties:

  1. 1.

$\exists i\in[m]$ such that $X_{i}=J_{1}$;

  2. 2.

$X_{0}=\emptyset$.

We first prove that there exists an $i\in[m]$ such that $X_{i}=J_{1}$.
Suppose, towards to the contradiction, that there is no $i\in[m]$ such that
$X_{i}=J_{1}$. Note that there must exist $i\in[m]$ such that $X_{i}\cap
J_{1}\neq\emptyset$ otherwise $\mathbf{X}$ is not a PO schedule. Now we
consider the job set $X_{l}$ such that $X_{l}\cap J_{1}\neq\emptyset$. In the
case where no job set except $X_{l}$ in $\mathbf{X}$ contains jobs in $J_{1}$,
we can construct another feasible schedule
$\mathbf{X}^{\prime}=\mathbf{X}\cup\set{J_{1}}\setminus X_{l}$. It is easy to
see that $u_{i}(X_{i}^{\prime})\geqslant u_{i}(X_{i})$ for all $a_{i}\in A$
and $u_{l}(J_{1})>u_{l}(X_{l})$ for agent $a_{l}$. This implies that
$\mathbf{X}$ is not a PO schedule. In the case where there exist another one
or two subsets $X_{r},X_{p}\in\mathbf{X}$ such that $X_{r},X_{p}\cap
J_{1}\neq\emptyset$. Since there are only three jobs in $J_{1}$, there are at
most three job sets in $\mathbf{X}$ that contains some job in $J_{1}$. Without
loss of generality, we assume that both $X_{r}$ and $X_{p}$ exist. Since every
job in $J_{2}$ overlaps with every job in $J_{1}$, we have
$X_{l},X_{r},X_{p}\cap J_{2}=\emptyset$. Therefore,
$|X_{l}|=|X_{r}|=|X_{p}|=1$. Since there are $m-1$ long jobs and every job set
in $\mathbf{X}\setminus(X_{l}\cup X_{r}\cup X_{p})$ contains only one job in
$J_{2}$, $X_{0}$ contains two jobs from $J_{2}$. Now we can construct another
feasible schedule $\mathbf{X}^{\prime}=(X_{1}^{\prime},\cdots,X_{m}^{\prime})$
in following way: move all jobs in $X_{r}\cup X_{p}$ to $X_{l}$; assign one of
two jobs in $X_{0}$ to $X_{r}$ and another one to $X_{p}$; keep the remaining
job sets same as the corresponding one in $\mathbf{X}$. It is easy to see that
$u_{i}(X_{i}^{\prime})\geqslant u_{i}(X_{i})$ for all $a_{i}\in A$ and
$u_{l}(X_{l}^{\prime})=u_{l}(J_{1})>u_{l}(X_{l})$. This implies that
$\mathbf{X}$ is not a PO schedule.

Figure 1: Instance for lemma 5. There are $|A|=m$ agents and $|J|=m+2$ jobs
with $m\geqslant 2$. Job set $J$ can be partitioned as $J_{1}\cup J_{2}$,
where $J_{1}=\set{j_{1},j_{2},j_{3}}$ and
$J_{2}=\set{j_{4},j_{5},\cdots,j_{m+2}}$. Each job $J_{1}$ has unit processing
time and each job $J_{2}$ has processing time 5. All jobs are rigid such that
$j_{i}\in J_{1}$ needs to occupy the entire time slot $2i-1$, where
$i\in\set{1,2,3}$. And $j\in J_{2}$ occupies the entire time period from 1 to
5.

Therefore, we can assume that there must exist an $i\in[m]$ such that
$X_{i}=J_{1}$. Without loss of generality, we assume that $X_{1}=J_{1}$. Now
we show that the second property holds. Since $|J_{2}|=m-1$,
$X_{0}\neq\emptyset$ implies that there must exist a job set
$X_{l}\in\mathbf{X}$ such that $X_{l}=\emptyset$. This would imply that
$\mathbf{X}$ is not a PO schedule. Since $\mathbf{X}$ holds the above two
properties, we assume that every remaining agent in $A\setminus\set{a_{1}}$
will receive exactly one job in $J_{2}$. Without loss of generality, we assume
that $X_{i}=\set{j_{i+2}}$. Therefore, we have
$\mathbf{X}=(X_{1},\cdots,X_{m})$, where
$X_{1}=J_{1},X_{2}=\set{j_{4}},\cdots,X_{m}=\set{j_{m+2}}$. Since
$u_{i}(X_{1}\setminus\set{j})=2>u_{i}(X_{i})=1,\forall a_{i}\in
A\setminus\set{a_{1}},\forall j\in X_{1}$, $\mathbf{X}$ is not an EF1
schedule. ∎

###  4.2 Compatibility of EF1 and PO

######  Theorem 3.

Given an arbitrary instance of FISP with $\langle$identical, unit$\rangle$,
algorithm 5 returns a schedule that is simultaneously EF1 and PO in polynomial
time.

Algorithm 5 . $m$-Matching + Inner-Greedy

0: An FISP instance $\mathcal{I}=(J,A,\mathbf{u}_{A})$, where all jobs have
unit processing time and all agents have identical valuation.

0: EF1 and PO schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$.

1: Construct graph $G(J\cup T,E)$, and compute a maximum weighted $m$-matching
$\mathcal{M}^{*}$.

2: Define $J_{t}=\set{j\in J\mid(j,t)\in\mathcal{M}^{*}}$ for each $t\in T$.

3: Set $X_{1}=X_{2}=\cdots=X_{m}=\emptyset$.

4: for $p=1$ to $|T|$ do

5: if $J_{p}\neq\emptyset$ then

6: Sort $A$ in non-decreasing order of $u_{i}(X_{i})$’s, and $J_{p}$ in non-
increasing order of $u(j_{k})$’s.

7: for $i=1$ to $|J_{p}|$ do

8: Set $X_{i}=X_{i}\cup\set{j_{i}}$.

9: end for

10: end if

11: end for

Before give the proof of theorem 3, we first give the definition of the
condensed instance which is used to improve the running time.

Given an arbitrary instance of FISP with $\langle$identical, unit$\rangle$,
denoted by $I$, for each job $j_{i}\in J$, let $\mathcal{T}_{i}$ be the set of
time slots included in the job interval of $j_{i}$, i.e.,
$\mathcal{T}_{i}=\set{r_{i},r_{i}+1,\cdots,d_{i}}$. Let $\mathcal{T}$ be the
set of condensed time slots (definition 6). We construct another instance,
denoted by $I^{\prime}$, by condensing $T_{i}$, i.e., for every job in $J$,
$T_{i}=T_{i}\cap T$. We show that these two instances are equivalent (lemma
6). Let $J^{\prime}$ be the set of jobs in the instance $I^{\prime}$.

######  Definition 6.

Let $T$ be the condensed time slots set.

$T=\bigcup_{1\leqslant l\leqslant n}\set{d_{l}-n+1,d_{l}-n+2,\cdots,d_{l}}$

where $d_{l}$ is the deadline of job $j_{l}$.

To prove lemma 7, it suffices to prove the following lemma.

######  Lemma 6.

Let $\hat{J}\subseteq J$ be an arbitrary subset of jobs in the instance $I$.
Let $\hat{J}^{\prime}\subseteq J^{\prime}$ be the corresponding jobs in the
instance $I^{\prime}$. Then, $\hat{J}$ is a feasible job set if and only if
$\hat{J}^{\prime}$ is a feasible job set.

###### Proof.

($\Leftarrow$) This direction is straightforward.

($\Rightarrow$) To prove this direction, we define a job block as a maximal
set of consecutive jobs such that they are scheduled after each other. Since
$\hat{J}$ is a feasible job set, there is a feasible schedule for all jobs in
$\hat{J}$. We start from the first job $j_{l}\in\hat{J}$ which is scheduled in
time slot $t_{l}$ such that $t_{l}\notin T$, we show that we can always shift
this job block to the right. Time slot $t_{l}\notin T$ implies that $t_{r}$ is
in a distance more that $n$ from any elements in deadline set
$D=\bigcup_{j_{q}\in J}\set{d_{q}}$. We can shift the job block $j_{l}$ to the
right. An example is shown in figure 2. We show that we can always shift
$j_{l}$ to the right until:

  * •

Either job $j_{l}$ is scheduled in a time slot in $T$.

  * •

Or the job block starting from $j_{l}$ reaches another scheduled job and form
a bigger job block.

Figure 2: Illustration of lemma 6. Initially, job $j_{l}$ is scheduled in the
time slot $t_{r}$ which is not in $T$. The job block starting from $j_{l}$
only includes two jobs: $j_{l}$ and $j_{o}$. We can always shift job $j_{l}$
to the right until $j_{l}$ is scheduled in a time slot in $T$. Or the leftmost
time slot in $T$ is occupied by a certain job $j_{r}$. The job block starting
from $j_{r}$ contains three jobs: $j_{r}$, $j_{h}$ and $j_{f}$. We can still
shift the merged job block, which contains $j_{l},j_{o},j_{r},j_{h},j_{f}$, to
the right, since the distance between time slot $t_{r}$ and any deadline in
$D$ exceeds $n$.

If job $j_{l}$ is scheduled in a time slot in $T$, then the lemma follows. If
the job block starting from $j_{l}$ reaches another scheduled job and form a
bigger job block, we keep shifting the bigger job block to the right unit
$j_{l}$ is scheduled in a time slot $t_{l}^{\prime}\in T$. Note that no job
would miss its deadline, since the distance between $t_{l}^{\prime}$ and any
deadline in $D$ exceeds $n$ which implies that there is enough time slots to
schedule all jobs in the current job block. ∎

######  Lemma 7.

For an arbitrary instance of FISP with $\langle$identical, unit$\rangle$, if
there is a polynomial-time algorithm that returns an EF1 and PO schedule for
all condensed instances, there also exists one for non-condensed instances.

Figure 3: An example of the bipartite graph $G(J\cup T,E)$ and a corresponding
maximum $m$-matching, where
$J=\set{j_{1},\cdots,j_{6}},A=\set{a_{1},a_{2}},T=\set{t_{1},t_{2},t_{3}}$.
Assume all jobs have identical utility to the agents. The job intervals are
$T_{1}=T_{2}=T_{3}=T_{5}=T_{6}=\set{t_{1},t_{2}}$, and
$T_{4}=\set{t_{1},t_{2},t_{3}}$. A possible maximum weighted $m$-matching
$\mathcal{M}^{*}$ is shown one the right, according to which the jobs are
partitioned as
$J_{1}=\set{j_{1},j_{2}},J_{2}=\set{j_{3},j_{6}},J_{3}=\set{j_{4}}$. Then,
$X_{0}=J\setminus(J_{1}\cup J_{2}\cup J_{3})=\set{j_{5}}$.

Arbitrarily fix a maximum weighted $m$-matching $\mathcal{M}^{*}$. For any
$t\in T$, let $J_{t}$ be the set of jobs which are matched with time slot $t$,
i.e., $J_{t}=\set{j\in J\mid(j,t)\in\mathcal{M}^{*}}.$ Note that the $J_{t}$’s
are mutually disjoint. Therefore we can refer $t$ as the type of jobs in
$J_{t}$. An example can be found in figure 3 (a). The key idea of algorithm 5
is to first use the above procedure to find the job set with the maximum total
weight that can be processed and classify jobs into different types, and then
greedily assign each type of jobs to the agents. The jobs that are not matched
by $\mathcal{M}^{*}$, i.e., $J\setminus(\bigcup_{t\in T}J_{t})$, are kept
unallocated and will be assigned to charity.

Let $\mathbf{X}=(X_{1},\cdots,X_{m})$ be the schedule returned by algorithm 5
and let $X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}$. Note that although the
agents have identical utilities, we sometimes use $u_{i}$ for agent $a_{i}\in
A$ to make the comparison clear.

######  Lemma 8.

For any $a_{i},a_{k}\in A$, $u_{i}(X_{i})\geqslant
u_{i}(X_{k}\setminus\set{j_{l}})\text{ for some $j_{l}\in X_{k}$.}$

###### Proof.

We prove the lemma by induction. Let $X_{i}^{p}$ be the set of jobs assigned
to agent $a_{i}$ after the $p$-th round of algorithm 5, and
$\mathbf{X}^{p}=(X_{1}^{p},\cdots,X_{m}^{p})$.

Base Case. When $p=1$, each agent gets at most one job as $|J_{t}|\leqslant m$
for all $t\in T$, and thus $\mathbf{X}^{1}$ is EF1.

Induction Hypothesis. For any $p>1$, after the $p$-th round of algorithm 5,
suppose lemma 8 holds, i.e., for any $a_{i},a_{k}\in A$, there exists a job,
denoted by $j_{h}$, in $X_{i}^{p}$ such that $u_{k}(X_{k}^{p})\geqslant
u_{k}(X_{i}^{p}\setminus\set{j_{h}}).$

Now we consider the $(p+1)$-th round. Arbitrarily fix two agents
$a_{i},a_{k}\in A$ and without loss of generality assume
$u_{i}(X_{i}^{p})\geqslant u_{k}(X_{k}^{p})$. In the following we prove that
after this round, $a_{i}$ and $a_{k}$ continue not to envy each other for more
than one item. Note that, in the $(p+1)$-th round, $a_{k}$ chooses a job from
$J_{p+1}$ before $a_{i}$.

Suppose that $j_{\hat{k}}$ is assigned to $a_{k}$ while $j_{\hat{i}}$ is
assigned to $a_{i}$ in the $(p+1)$-th round. Therefore, we have
$X_{k}^{p+1}=X_{k}^{p}\cup\set{j_{\hat{k}}}$ and
$X_{i}^{p+1}=X_{i}^{p}\cup\set{j_{\hat{i}}}$. Since $|J_{p+1}|\leqslant m$,
$\set{j_{\hat{k}}}$ and $\set{j_{\hat{i}}}$ may be empty, in which case, we
assume that $u(j_{\hat{k}})=u(j_{\hat{i}})=0$. Since $a_{k}$ chooses the job
before $a_{i}$ and all jobs in $J_{p+1}$ are sorted in non-increasing order,
$u(j_{\hat{k}})\geqslant u(j_{\hat{i}})$ always holds no matter whether
$\set{j_{\hat{k}}}$ is empty or not.

Regarding agent $a_{i}$, as $u_{i}(X_{i}^{p})\geqslant u_{k}(X_{k}^{p})$, we
have

$u_{i}(X_{i}^{p+1})\geqslant u_{i}(X_{i}^{p})\geqslant
u_{i}(X_{k}^{p})=u_{i}(X_{k}^{p+1}\setminus\set{j_{\hat{k}}}).$

Regarding agent $a_{k}$, because $u_{k}(j_{\hat{k}})\geqslant
u_{k}(j_{\hat{i}})$ and $u_{i}(X_{i}^{p})\geqslant
u_{i}(X_{k}^{p}\setminus\set{j_{h}})$ (induction hypothesis),

$u_{k}(X_{k}^{p+1})=u_{k}(X_{k}^{p})+u_{k}(j_{\hat{k}})\geqslant
u_{k}(X_{i}^{p}\setminus\set{j_{h}})+u_{k}(j_{\hat{i}})=u_{k}(X_{i}^{p+1}\setminus\set{j_{h}}).$

Thus, after the $(p+1)$-th round, $a_{i}$ and $a_{k}$ continue not to envy
each other for more than one item. By induction, lemma 8 holds. ∎

###### Proof of theorem 3.

Since schedule $\mathbf{X}$ returned by algorithm 5 maximizes social welfare
$\sum_{a_{i}\in A}u_{i}(X_{i})$, $\mathbf{X}$ must be PO. According to lemma
8, $\mathbf{X}$ is EF1. For time complexity, we have already discussed that
computing a maximum $m$-matching can be done in polynomial time. Further, as
allocating jobs by types only needs to sort jobs or agents, which can also be
done in polynomial time, we finished the proof. ∎

We note that algorithm 5 fails to return an EF1 and PO schedule if the agents’
utilities are not identical. Actually, the existence of EF1 and PO schedule
for this case is left open in Biswas and Barman (2018); Dror et al. (2020); Wu
et al. (2021) even when the scheduling constraints degenerate to cardinality
constraints.

######  Remark 1.

We noted that the proof of lemma 8 only uses the ranking of jobs’ weight.
Therefore, algorithm 5 is able to return to a feasible schedule that is
simultaneously EF1 and PO in the setting where agents value jobs in the same
order but the concrete jobs’ weight are not known by the algorithm.

###  4.3 Approximate EF1 and PO

Although EF1 and PO are only compatible in special cases, in this section we
show that approximate EF1 and PO can be always satisfied. In the following, we
show that Nash social welfare maximizing schedule satisfies the desired
properties.

######  Theorem 4.

Given an arbitrary instance of general FISP, any schedule that maximizes the
Nash social welfare is a 1/4-EF1 and PO schedule.

The proof of theorem 4 is essentially in the same spirit with the
corresponding one in Wu et al. (2021), and we include the proof for
completeness in appendix C. Although we show that the proof in theorem 4 is
tight in the appendix, when the jobs are unit we can improve the approximation
ratio to 1/2.

######  Theorem 5.

Given an arbitrary instance of FISP with $\langle$non-identical,
unit$\rangle$, a MaxNSW schedule is a 1/2-EF1 and PO schedule.

###### Proof.

We show that a feasible schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$ that
maximizes Nash social welfare is simultaneously 1/2-EF1 and PO. Since any
MaxNSW schedule must be a PO schedule, we only prove that $\mathbf{X}$ is a
1/2-EF1 schedule Hence, we only show that $\mathbf{X}$ is an 1/2-EF1 schedule,
i.e., $\forall i,k\in[m],u_{i}(X_{i})\geqslant\frac{1}{2}\cdot
u_{i}(X_{k}\setminus\set{j}),\exists j\in X_{k}$.

We prove by contradiction and assume that there exists $i,k\in[m]$ such that
$u_{i}(X_{i})<\frac{1}{2}\cdot u_{i}(X_{k}\setminus\set{j}),\forall j\in
X_{k}$. Then, we have

$\displaystyle u_{i}(X_{i})+u_{i}(j)<u_{i}(X_{k})-u_{i}(X_{i}),\forall j\in
X_{k}.$ (3)

Since $X_{i},X_{k}$ are feasible job set, there is a maximum weighted matching
in $G(X_{i}\cup T,E_{i}),G(X_{k}\cup T,E_{k})$ with size $|X_{i}|,|X_{k}|$,
respectively. Let $M_{i},M_{k}$ be the maximum weighted matching in
$G(X_{i}\cup T,E_{i}),G(X_{k}\cup T,E_{k})$, respectively. An example can be
found in figure 4.

Figure 4: Illustration for $M_{i},M_{k}$. In the above example, we have
$X_{i}=\set{j_{1}^{i},j_{2}^{i},j_{3}^{i}}$,
$X_{k}=\set{j_{1}^{k},j_{2}^{k},j_{3}^{k}}$ and
$T=\set{t_{1},t_{2},t_{3},t_{4}}$. We have matching $M_{i}=\set{\langle
j_{1}^{i},t_{1}^{i}\rangle,\langle j_{2}^{i},t_{2}^{i}\rangle,\langle
j_{3}^{i},t_{4}^{i}\rangle}$ and $M_{k}=\set{\langle
j_{1}^{k},t_{2}^{k}\rangle,\langle j_{2}^{k},t_{3}^{k}\rangle,\langle
j_{3}^{k},t_{4}^{k}\rangle}$. Moreover, we have
$M_{i}(J)=X_{i},M_{i}(T)=\set{t_{1},t_{2},t_{4}}$ and
$M_{k}(J)=X_{k},M_{k}(T)=\set{t_{2},t_{3},t_{4}}$.

For every time slot $t_{l}\in M_{i}(T)\cup M_{k}(T)$, we find the pair
$\langle j^{i},t_{l}^{i}\rangle\in M_{i},\langle j^{k},t_{l}^{k}\rangle\in
M_{k}$. Note that there may exist some time slot $t_{l}$ such that $t_{l}$ is
only matched in $M_{i}$ or $M_{k}$, e.g., time slot $t_{1},t_{3}$ in the
example shown in figure 4. In this case, we add a dummy pair to $M_{k}$ or
$M_{i}$, e.g., in the example shown in figure 4, $M_{i}=M_{i}\cup\set{\langle
j_{o},t_{3}^{i}\rangle},M_{k}=M_{k}\cup\set{\langle j_{o},t_{1}^{k}\rangle}$
and let $u_{i}(j_{o})=u_{k}(j_{o})=0,\forall i\in[m]$. For every time slot
$t_{l}\in M_{i}(T)\cup M_{k}(T)$, we find the pair $\langle
j^{i},t_{l}^{i}\rangle\in M_{i},(j^{k},t_{l}^{k})\in M_{k}$ and define the big
pair $[\langle j^{i},t_{l}^{i}\rangle,\langle j^{k},t_{l}^{k}\rangle]$ as
$(j^{i},j^{k})$ for convenience. For each pair $(j^{i},j^{k})$, we define
$|(j^{i},j^{k})|$ as its value, where

$|(j^{i},j^{k})|=\frac{u_{i}(j^{k})-u_{i}(j^{i})}{u_{k}(j^{k})-u_{k}(j^{i})}.$

Note that there may exist two pairs: $\langle j^{i},t_{l}^{i}\rangle\in
M_{i},\langle j^{k},t_{l}^{k}\rangle\in M_{k}$ such that
$u_{i}(j^{k})-u_{i}(j^{i})=0$ and $u_{k}(j^{k})-u_{k}(j^{i})=0$. In this case,
we have

$|(j^{i},j^{k})|=\begin{cases}0,\text{ if
}&u_{i}(j^{k})-u_{i}(j^{i})=0,u_{k}(j^{k})-u_{k}(j^{i})\neq 0;\\\
\infty,\text{ if }&u_{i}(j^{k})-u_{i}(j^{i})\neq
0,u_{k}(j^{k})-u_{k}(j^{i})=0.\end{cases}$

Let $\mathcal{P}_{+},\mathcal{P}_{-}$ be the set of all $(j^{i},j^{k})$ such
that $u_{i}(j^{k})-u_{i}(j^{i})>0$ and $u_{i}(j^{k})-u_{i}(j^{i})\leqslant 0$,
respectively. We consider an arbitrary pair $(j^{i}_{+},j^{k}_{+})$ in
$\mathcal{P}_{+}$, i.e., $u_{i}(j^{k}_{+})-u_{i}(j^{i}_{+})>0$. Note that
$u_{k}(j^{k}_{+})-u_{k}(j^{i}_{+0})$ holds; otherwise, we can construct a new
feasible schedule by swapping job $j^{i}_{+}$ and $j^{k}_{+}$ will have larger
Nash Social Welfare. This would imply that $\mathbf{X}$ does not maximize the
Nash Social Welfare. Let $X_{i}^{+},X_{k}^{+}$ be the set of jobs in
$X_{i},X_{k}$ that are covered by some pair in $\mathcal{P}_{+}$,
respectively, i.e., $X_{i}^{+}=\set{j^{i}\in
X_{i}}{\exists(j^{i},j^{k})\in\mathcal{P}_{+}}$ and $X_{k}^{+}=\set{j^{k}\in
X_{k}}{\exists(j^{i},j^{k})\in\mathcal{P}_{+}}$. Notations
$X_{i}^{-},X_{k}^{-}$ are defined in similar ways. Note that

$u_{i}(X_{k})-u_{i}(X_{i})=\bigg{(}u_{i}(X_{k}^{+})-u_{i}(X_{i}^{+})\bigg{)}+\bigg{(}u_{i}(X_{k}^{-})-u_{i}(X_{i}^{-})\bigg{)}.$

Since $u_{i}(X_{k}^{-})-u_{i}(X_{i}^{-})\leqslant 0$, we have

$u_{i}(X_{k})-u_{i}(X_{i})\leqslant u_{i}(X_{k}^{+})-u_{i}(X_{i}^{+}).$ (4)

Then, we have:

$\frac{u_{i}(X_{k}^{+})-u_{i}(X_{i}^{+})}{u_{k}(X_{k}^{+})}\geqslant\frac{u_{i}(X_{k}^{+})-u_{i}(X_{i}^{+})}{u_{k}(X_{k})}\geqslant\frac{u_{i}(X_{k})-u_{i}(X_{i})}{u_{k}(X_{k})},$
(5)

where the first inequality is due to $u_{i}(X_{k}^{+})-u_{i}(X_{i}^{+})>0$ and
$u_{k}(X_{k})\geqslant u_{k}(X_{k}^{+})$, the last inequality is due to
equation 4. Now, we define $(g^{i},g^{k})$ as:

$(g^{i},g^{k})=\operatorname*{arg\,max}_{(j^{i},j^{k})\in\mathcal{P}_{+}}\bigg{\\{}|(j^{i},j^{k})|\bigg{\\}}.$

Note that $\mathcal{P}_{+}\neq\emptyset$, i.e., there must exist a pair
$(j^{i}_{+},j^{k}_{+})$ such that $u_{i}(j^{k}_{+})-u_{i}(j^{i}_{+})>0$
because of $u_{i}(X_{k})>u_{i}(X_{i})$. Since every pair $(j^{i},j^{k})$ in
$\mathcal{P}_{+}$ has property $u_{i}(j^{k})-u_{i}(j^{i})>0$ and
$u_{k}(j^{k})-u_{i}(j^{i})>0$, we have:

$\frac{u_{i}(g^{k})-u_{i}(g^{i})}{u_{k}(g^{k})-u_{k}(g^{i})}\geqslant\frac{u_{i}(X_{k}^{+})-u_{i}(X_{i}^{+})}{u_{k}(X_{k}^{+})-u_{k}(X_{i}^{+})}\geqslant\frac{u_{i}(X_{k}^{+})-u_{i}(X_{i}^{+})}{u_{k}(X_{k}^{+})},$
(6)

where the last inequality is due to $u_{i}(X_{k}^{+})-u_{i}(X_{i}^{+})>0$ and
$u_{k}(X_{i}^{+})\geqslant 0$. By combining equation 5 and equation 6, we have

$\frac{u_{i}(g^{k})-u_{i}(g^{i})}{u_{k}(g^{k})-u_{k}(g^{i})}\geqslant\frac{u_{i}(X_{k})-u_{i}(X_{i})}{u_{k}(X_{k})}>\frac{u_{i}(X_{i})+u_{i}(g^{k})}{u_{k}(X_{k})},$
(7)

where the last inequality is due to equation 3.

Since $u_{i}(g^{k})-u_{i}(g^{i})>0$ and $(u_{k}(g^{k})-u_{k}(g^{i})>0$, we
have:

$\bigg{(}u_{i}(g^{k})-u_{i}(g^{i})\bigg{)}\cdot
u_{k}(X_{k})>\bigg{(}u_{k}(g^{k})-u_{k}(g^{i})\bigg{)}\cdot\bigg{(}u_{i}(X_{i})+u_{i}(g^{k})\bigg{)}.$
(8)

Holding equation 8 on our hand, we are ready to prove that $\mathbf{X}$ does
not maximize the Nash social welfare. Now, we construct another feasible
schedule, denoted by
$\mathbf{X}^{\prime}=(X_{1}^{\prime},\cdots,X_{m}^{\prime})$. We construct
$\mathbf{X}^{\prime}$ by swapping the job $g^{i}$ with $g^{k}$, i.e.,
$X_{o}^{\prime}=X_{o},\forall o\in[m]\text{ and }o\neq i,k$,
$X_{i}^{\prime}=X_{i}\cup\set{g^{k}}\setminus\set{g^{i}}$ and
$X_{k}^{\prime}=X_{k}\cup\set{g^{i}}\setminus\set{g^{k}}$. Note that all job
sets in $\mathbf{X}^{\prime}$ except $X_{i}^{\prime},X_{k}^{\prime}$ are the
same as the corresponding job sets in $\mathbf{X}$. Observe that if we can
show that
$u_{i}(X_{i}^{\prime})u_{k}(X_{k}^{\prime})>u_{i}(X_{i})u_{k}(X_{k})$, then it
implies that $\mathbf{X}$ does not maximize the Nash social welfare. Note that

$\displaystyle u_{i}(X_{i}^{\prime})$
$\displaystyle=u_{i}(X_{i})+u_{i}(g^{k})-u_{i}(g^{i});$ $\displaystyle
u_{k}(X_{k}^{\prime})$ $\displaystyle=u_{k}(X_{k})+u_{k}(g^{i})-u_{k}(g^{k}).$

We define $\Gamma$ as follows for convenience:

$\Gamma=\bigg{(}u_{i}(g^{k})-u_{i}(g^{i})\bigg{)}\cdot
u_{k}(X_{k})-\bigg{(}u_{k}(g^{k})-u_{k}(g^{i})\bigg{)}\cdot\bigg{(}u_{i}(X_{i})+u_{i}(g^{k})\bigg{)},$

where $\Gamma>0$ because of equation 8. Then, we have

$u_{i}(X_{i}^{\prime})u_{k}(X_{k}^{\prime})-u_{i}(X_{i})u_{k}(X_{k})=\Gamma+\bigg{(}u_{k}(g^{k})-u_{k}(g^{i})\bigg{)}\cdot
u_{i}(g^{i}).$

Since $u_{k}(g^{k})-u_{k}(g^{i})>0$ and $\Gamma>0$, we have
$u_{i}(X_{i}^{\prime})u_{k}(X_{k}^{\prime})-u_{i}(X_{i})u_{k}(X_{k})>0$. Hence
$\mathbf{X}$ does not maximize the Nash social welfare which contradicts our
assumption. Therefore, $\forall
i,k\in[m],u_{i}(X_{i})\geqslant\frac{1}{2}\cdot(X_{k}\setminus\set{j}),\exists
j\in X_{k}$. ∎

In the following, we show that our proof of theorem 5 is tight.

######  Lemma 9.

The schedule which maximizes the Nash social welfare can only guarantee
1/2-EF1 and PO for FISP with $\langle$non-identical,unit$\rangle$.

###### Proof.

To prove lemma 9, we give an instance for which a schedule that maximizes the
Nash social welfare is an 1/2-EF1 schedule.

We consider the job set $J=\set{j_{1},\cdots,j_{n},j_{n+1},\cdots,j_{2n}}$
which contains $2n$ jobs. All jobs have the same release time $1$ and deadline
$n$. Moreover, all jobs have unit processing time. The agent set
$A=\set{a_{1},a_{2}}$ contains two agents. The utilities matrix is as follows:

$\begin{array}[]{c|ccccccc}&j_{1}&j_{2}&\cdots&j_{n}&j_{n+1}&\cdots&j_{2n}\\\
\hline\cr a_{1}&2&2&\cdots&2&1&\cdots&1\\\ a_{2}&1&1&\cdots&1&0&\cdots&0\\\
\end{array}$

To find the schedule that maximizes the Nash social welfare, we consider an
arbitrary schedule $\mathbf{X}=(X_{1},X_{2})$ and assume that
$X_{0}=J\setminus(X_{1}\cup X_{2})$. We define
$J_{1}=\set{j_{1},\cdots,j_{n}}$ and $J_{2}=\set{j_{n+1},\cdots,j_{2n}}$.
Observe that $X_{0}=\emptyset$ otherwise $\mathbf{X}$ does not maximize the
value of $u_{1}(X_{1})\cdot u_{2}(X_{2})$. We assume that $x$ jobs in $J_{1}$
are assigned to $a_{1}$ and $y$ jobs in $J_{2}$ are assigned to $a_{2}$, where
$0\leqslant x,y\leqslant n$. Then, we have

$f(x,y)=u_{1}(X_{1})\cdot u_{2}(X_{2})=(2x+y)\cdot(n-x).$

To find the maximum value of $f(x,y)$ under the constraints $0\leqslant
x,y\leqslant n$, we compute partial derivative.

$\begin{cases}\frac{\partial f(x,y)}{\partial x}=2n-4x-y=0\vspace{0.2cm}\\\
\frac{\partial f(x,y)}{\partial y}=n-x=0\end{cases}$

The solution to the above two equations is $(n,-2n)$. Since the point
$(n,-2n)$ is not in $\set{(x,y)}{0\leqslant x,y\leqslant n}$, the maximum
value will be taken at a certain vertex. We can find that the maximum value
will be taken at the point $(x,y)=(0,n)$ by computing the value of
$f(0,0),f(0,n),f(n,0),f(n,n)$.

Hence, we found the schedule $\mathbf{X}=(X_{1},X_{2})$ maximizes the Nash
social welfare, where $X_{1}=J_{2},X_{2}=J_{1}$. Then, we have
$u_{1}(X_{1})=2n$ and $u_{1}(X_{1}\setminus\set{j})=2(n-1),\forall j\in
X_{1}$. Then, we have

$\lim_{n\to+\infty}\frac{u_{1}(X_{1})}{u_{1}(X_{1}\setminus\set{j})}=\frac{n}{2(n-1)}=\frac{1}{2}.$

∎

##  5 EF1 and IO Scheduling

lemma 5 shows that PO is very demanding since even if agents have unweighted
utilities, EF1 and PO are not compatible. Accordingly, in this section, we
will consider the weaker efficiency criterion – Individual Optimality. As we
will see, although EF1 and IO are still not compatible for weighted utilities,
they are when agents have unweighted utilities.

###  5.1 An Impossibility Result

We first show that EF1 and IO are not compatible even for FISP with
$\langle$identical, rigid$\rangle$, i.e., given an arbitrary instance of FISP
with $\langle$identical, rigid$\rangle$, there is no algorithm can always find
a feasible schedule that is simultaneously EF1 and IO (lemma 10).

######  Lemma 10.

EF1 and IO are not compatible even for FISP with $\langle$identical,
rigid$\rangle$.

###### Proof.

To prove lemma 10, it suffices to consider the instance in figure 5, and prove
the following two claims.

######  Claim 2.

For any IO schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$,
$X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}=\emptyset$.

We prove this claim by contradiction. If $X_{0}\cap J_{1}\neq\emptyset$, as
$|J_{2}|=m-1$, there will be at least one agent, without loss of generality
say $a_{1}$, for whom $X_{1}\cap J_{2}=\emptyset$. Note that by the design of
the instance, $X_{1}\cup(X_{0}\cap J_{1})$ is feasible, and thus by allocating
$X_{0}\cap J_{1}$ to $a_{1}$, $a_{1}$’s utility strictly increases.

If $X_{0}\cap J_{2}\neq\emptyset$, as $|J_{2}|=m-1$, there will be at least
two agents, without loss of generality say $a_{1}$ and $a_{2}$, for whom
$X_{1}\cap J_{2}=\emptyset$ and $X_{2}\cap J_{2}=\emptyset$. Furthermore, as
$|J_{1}|=4$ one of them gets at most two jobs in $J_{1}$. Again without loss
of generality assume this is agent $a_{1}$. Accordingly,
$u_{1}(X_{1})\leqslant 4$ and by exchanging $X_{1}$ with one job in $X_{0}\cap
J_{2}$, $a_{1}$’s utility strictly increases.

######  Claim 3.

For any EF1 schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$,
$X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}\neq\emptyset$.

We note that the only possible and feasible schedule $\mathbf{X}$ such that
$X_{0}=\emptyset$ is that some agent, say $a_{1}$, gets entire $J_{1}$ and
every other agent gets one job in $J_{2}$. Then to prove this claim, it
suffices to prove $\mathbf{X}$ cannot be EF1. It is not hard to check that
under $\mathbf{X}$, for any agent $a_{i}$ with $i\geqslant 2$ and any job
$j\in X_{1}$,

$u_{i}(X_{i})=6-\epsilon<u_{i}(X_{1}\setminus\\{j\\})=6.$

That is all $a_{i}$ envies $a_{1}$ for more than one item.

Combing the above two claims, we complete the proof of lemma 10. ∎

Figure 5: Instance for lemma 10. There are $|A|=m$ agents and $|J|=m+3$ jobs
with $m\geqslant 2$. Job set $J$ can be partitioned as $J_{1}\cup J_{2}$ with
$J_{1}=\set{j_{1},j_{2},j_{3},j_{4}}$ and $J_{2}=\set{j_{5},\cdots,j_{m+3}}$.
Each job in $J_{1}$ has unit processing time with weight $2$ and each job in
$J_{2}$ has processing time 7 with weight $6-\epsilon$. All jobs are rigid
such that $j_{i}\in J_{1}$ needs to occupy the entire time slot $2i-1$, and
$j\in J_{2}$ occupies the entire time period from 1 to 7.

###  5.2 A Polynomial-time Algorithm for FISP with $\langle$unweighted,
rigid$\rangle$

In the following, we design a polynomial-time algorithm to compute a schedule
that is EF1 and IO for any instance of FISP with $\langle$unweighted,
rigid$\rangle$.

######  Theorem 6.

Given an arbitrary instance of FISP with $\langle$unweighted, rigid$\rangle$,
algorithm 6 returns a feasible schedule that is simultaneously EF1 and IO in
polynomial time.

Algorithm 6 . Earliest Deadline First + Round-Robin

0: Agent set $A$ and job set $J$.

0: EF1 schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$

1: Sort all jobs by their deadline in non-decreasing order.

2: $X_{1}=X_{2}=\cdots=X_{m}=\emptyset$.

3: $i=1,k=1$. // The index.

4: for all $j_{k}\in J$ do

5: if $X_{i}\cup\set{j_{k}}$ is a feasible job set then

6: $X_{i}=X_{i}\cup\set{j_{k}}$.

7: $J=J\setminus\set{j_{k}}$.

8: $i=(i+1)\mod m$.

9: else

10: $i=i\mod m$.

11: end if

12: end for

13: $X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}$.

Let $\mathbf{X}=(X_{1},\cdots,X_{m})$ be the schedule returned by algorithm 6
and let $X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}$. Suppose that all agents
receive a job at every round of first $L$ rounds of algorithm 6, i.e., in the
$(L+1)$-th round, $\exists i\in[m]$ such that $a_{i}$ receives nothing. Note
that $L\leqslant n$, where $n$ is the number of jobs. Let
$j_{i}^{l},1\leqslant i\leqslant m,1\leqslant l\leqslant L,$ be the job
assigned to agent $a_{i}$ in the $l$-th round of algorithm 6. Let
$r_{i}^{l},d_{i}^{l}$ be the release time and deadline of job $j_{i}^{l}$. Let
$X_{i}^{l}$ be the job set that is assigned to agent $a_{i}$ after the $l$-th
round of algorithm 6.

######  Lemma 11.

$d_{1}^{l}\leqslant d_{2}^{l}\leqslant\cdots\leqslant d_{m}^{l},\forall
l\in[L]$.

###### Proof.

We consider two agents $a_{i},a_{k}$ such that $1\leqslant i<k\leqslant m$.
Note that $j_{i}^{l},j_{k}^{l}$ must exist since, in the first $L$ rounds, all
agents receive a job. We prove by induction.

##### Base case and induction hypothesis.

In the base case where $l=1$, it is strainghtforward to see that
$d_{i}^{1}\leqslant d_{k}^{1}$, otherwise $j_{k}^{1}$ will be assigned to
agent $a_{i}$ in the first round of algorithm 6. Now, we have induction
hypothesis $d_{i}^{l}\leqslant d_{k}^{l}$.

We need to prove $d_{i}^{l+1}\leqslant d_{k}^{l+1}$. We prove by contradiction
and assume that $d_{i}^{l+1}>d_{k}^{l+1}$. Since agent $a_{i}$ chooses
$j_{i}^{l+1}$ instead of $j_{k}^{l+1}$ in the $(l+1)$-th round, we know that
$X_{i}^{l}\cup\set{j_{k}^{l+1}}$ is a not feasible job set which implies that
$r_{k}^{l+1}\leqslant d_{i}^{l}$. By induction hypothesis, we have
$r_{k}^{l+1}\leqslant d_{i}^{l}\leqslant d_{k}^{l}$. This implies that
$X_{k}^{l}\cup\set{j_{k}^{l+1}}$ is not a feasible job set. This contradicts
our assumption. Thus, $d_{i}^{l+1}\leqslant d_{k}^{l+1}$. ∎

######  Lemma 12.

$d_{m}^{l}\leqslant d_{1}^{l+1},\forall l\in[L-1]$. Moreover,
$d_{m}^{L}\leqslant d_{1}^{L+1}$ if $j_{1}^{L+1}$ exists.

###### Proof.

Let $a_{i},a_{k}$ be two agents such that $1\leqslant i<k\leqslant m$. We
assume that $j_{1}^{L+1}$ exists and prove that the lemma holds for all
$l\in[L]$. We prove by contradiction.

In the base case where $l=1$, it is not hard to see that $d_{m}^{l}\leqslant
d_{1}^{2}$; otherwise $a_{m}$ will choose $j_{1}^{2}$ in the first round. Now,
we have induction hypothesis $d_{m}^{l-1}\leqslant d_{1}^{l}$.

Suppose, towards to a contradiction, that there exist $l\in[L]$ such that
$d_{m}^{l}>d_{1}^{l+1}$. In the $l$-th round, agent $a_{m}$ selects
$j_{m}^{l}$ instead of $j_{1}^{l+1}$ because
$X_{m}^{l-1}\cup\set{j_{1}^{l+1}}$ is not a feasible job set; otherwise
$a_{m}$ will select $j_{1}^{l+1}$. Since $X_{m}^{l-1}\cup\set{j_{1}^{l+1}}$ is
not a feasible job set, we have $r_{1}^{l+1}\leqslant d_{m}^{l-1}$. By
induction hypothesis, we have $d_{m}^{l-1}\leqslant d_{1}^{l}$. Therefore, we
have $r_{1}^{l+1}\leqslant d_{1}^{l}$ which implies that
$X_{1}^{l}\cup\set{j_{1}^{l+1}}$ is not a feasible job set. This contradicts
our assumption. ∎

######  Lemma 13.

$|X_{i}|-|X_{k}|\in\set{-1,0,1},\forall i,k\in[m]$.

###### Proof.

We consider the $(L+1)$-th round of algorithm 6 in which $\exists f\in[m]$
such that $a_{f}$ receives nothing in this round. Let $J_{f}^{L}$ be the set
of remaining jobs in $J$ after $a_{f}$ chooses in the $(L+1)$-th round. We
consider the agent $a_{k}$ such that $1\leqslant f\leqslant k<m$. Since
$a_{f}$ receives nothing, we have $r_{j}\leqslant d_{f}^{L},\forall j\in
J_{f}^{L}$. According to lemma 11, we have $d_{f}^{L}\leqslant d_{k}^{L}$.
Then, we have $r_{j}\leqslant d_{f}^{L}\leqslant d_{k}^{L},\forall j\in
J_{f}^{L}$ which implies that agent $a_{k}$ also receives nothing in this
round. Therefore, $a_{m}$ must receive nothing in the $(L+1)$-th round because
there exist an agent that does not receive job in the $(L+1)$-th round. Let
$J_{m}^{L}$ be the remaining jobs in $J$ before $a_{m}$ chooses in the
$(L+1)$-th round. Since $a_{m}$ receives nothing in the $(L+1)$-th round, we
have $r_{j}\leqslant d_{m}^{L},\forall j\in J_{m}^{L}$. According to lemma 12,
we have $d_{m}^{L}\leqslant d_{1}^{L+1}$ if $j_{1}^{L+1}$ exists. Therefore,
we have $r_{j}\leqslant d_{1}^{L+1},\forall j\in J_{m}^{L}$. Thus, $a_{1}$
will receive nothing in the $(L+2)$-th round. Now, we consider an arbitrary
agent $a_{h},1\leqslant h\leqslant m$, it is strainghtforward to see that if
$a_{h}$ receives nothing in $(L+1)$-th round, then $a_{h}$ will receive
nothing in any $L^{\prime}$-th round, where $L+1<L^{\prime}$. Note that, in
the $(L+1)$-th round, there may exist many agents that receive nothing.
Without loss of generality, we assume that $a_{f}$ is the agent with the
smallest index who receives nothing in the $(L+1)$-th round. Therefore, we
have

$|X_{i}|=\begin{cases}L,&\forall f\leqslant i\leqslant m;\\\ L+1,&\forall
1\leqslant i<f.\end{cases}$

Thus, we have $|X_{i}|-|X_{k}|\in\set{-1,0,1},\forall i,k\in[m]$. ∎

######  Lemma 14.

$u_{i}(X_{i})\geqslant u_{i}(X_{0}\cup X_{i}),\forall i\in[m]$.

We will use the optimal argument for classical interval scheduling to prove
lemma 14. We restate the problem and optimal argument for completeness.

In classical interval scheduling, we are given a set of intervals
$\mathcal{I}=\set{I_{1},I_{2},\cdots,I_{n}}$. Each interval is associated with
a release time and a deadline. A set of intervals $\mathcal{I}^{\prime}$ is
called a compatible set if and only if, for every two intervals
$I_{k},I_{h}\in\mathcal{I}^{\prime}$, $I_{k},I_{h}$ do not intersect. The goad
is to find the compatible set with the maximum size. This problem can be
easily solved by Earlier Deadline First (EDF) Kleinberg and Tardos (2006).

###### Proof.

We consider an arbitrary agent $a_{i}$. We prove by constructing an instance
of classical interval scheduling problem. Let $\mathcal{I}=X_{0}\cup X_{i}$.
Let $\mathsf{ALGE}$ be the interval set selected by EDF algorithm. Observe
that if we can prove that $\mathsf{ALGE}=X_{i}$, then it implies that
$u_{i}(X_{i})\geqslant u_{i}(X_{0}\cup X_{i})$ since $\mathsf{ALGE}$ is the
optimal solution. Suppose that
$\mathsf{ALGE}=\set{j_{1}^{\prime},j_{2}^{\prime},\cdots,j_{h}^{\prime}}$ and
assume that the interval is added to $\mathsf{ALGE}$ by EDF algorithm in this
order. Suppose that $X_{i}=\set{j_{1},j_{2},\cdots,j_{k}}$ and assume that the
job is added to $X_{i}$ by algorithm 6 in this order. Note that
$|X_{i}|\leqslant|\mathsf{ALGE}|$ since $\mathsf{ALGE}$ is the compatible set
with the maximum size.

We prove by comparison. Assume that $\mathsf{ALGE}$ and $X_{i}$ become
different from the $R$-th element, i.e., $j_{l}=j_{l}^{\prime},\forall
l\in[R-1]$ and $j_{R}\neq j_{R}^{\prime}$. This implies that $j_{R}^{\prime}$
instead of $j_{R}$ is the job with the smallest deadline in $X_{0}\cup
X_{i}\setminus\set{j_{1},\cdots,j_{R-1}}$ to make
$\set{j_{1},\cdots,j_{R-1}}\cup\set{j_{R}^{\prime}}$ be compatible. Note that
both $\set{j_{1},\cdots,j_{R-1}}\cup\set{j_{R}^{\prime}}$ and
$\set{j_{1},\cdots,j_{R-1}}\cup\set{j_{R}}$ are feasible. Since
$j_{R}^{\prime}$ is left to charity, there is no agent takes it away.
Therefore, algorithm 6 will assign $j_{R}^{\prime}$ instead of $j_{R}$ to
$a_{i}$. Hence, we proved $X_{i}\subseteq\mathsf{ALGE}$. It is easy to see
that there is no interval $j_{u}^{\prime}\in\mathsf{ALGE}$ such that
$j_{u}^{\prime}\notin X_{i}$ which implies that $X_{i}=\mathsf{ALGE}$. ∎

Now, we are ready to prove theorem 6.

###### Proof of theorem 6.

According to lemma 13, we know that the feasible schedule $\mathbf{X}$
returned by algorithm 6 is an EF1 schedule. According to lemma 14,
$\mathbf{X}$ is also an IO schedule. Hence, algorithm 6 returns a feasible
schedule that is simultaneously EF1 and IO.

Now, we prove the running time. Line 1 requires running time $O(n\log n)$,
where $n$ is the number of jobs. Line 4-13 requires running time $O(n)$.
Hence, the running time of algorithm 6 can be bounded by $O(n\log n)$. ∎

Now, we show an instance that algorithm 6 returns a schedule that is not PO
schedule. See figure 6. By applying algorithm 6 to the instance in figure 6,
let $\mathbf{X}$ be the returned schedule. Then, we have
$\mathbf{X}=(X_{1},X_{2})$, where
$X_{1}=\set{j_{1},j_{4}},X_{2}=\set{j_{2},j_{5}}$ and
$X_{0}=\set{j_{3},j_{6}}$. But a possible PO schedule is
$\mathbf{X}^{\prime}=(X_{1}^{\prime},X_{2}^{\prime})$, where
$X_{1}^{\prime}=\set{j_{1},j_{4},j_{5}},X_{2}^{\prime}=\set{j_{2},j_{6}}$ and
$X_{0}^{\prime}=\set{j_{3}}$.

Figure 6: Instance for which algorithm 6 fails to return a PO schedule. In the
above instance, we have
$J=\set{j_{1},j_{2},j_{3},j_{4},j_{5},j_{6}},A=\set{a_{1},a_{2}}$. The job
windows are
$T_{1}=\set{1,2},T_{2}=\set{3,4},T_{3}=\set{2,3,4,5,6},T_{4}=\set{6,7,8},T_{5}=\set{10,11},T_{6}=\set{8,9,10,11,12}$,
respectively.

###  5.3 A polynomial time algorithm for FISP with $\langle$unweighted,
flexible$\rangle$

Note that algorithm 6 can be modified to run on instances of FISP with
$\langle$unweighted, flexible$\rangle$. But this modified algorithm fails to
return an IO schedule. This is not surprising as it has been proved in Garey
and Johnson (1979) that even with a single machine, finding an IO schedule is
NP-hard. Fortunately, the modified algorithm still runs in polynomial time and
always returns a schedule that is EF1 and 1/2-IO.

Before giving the round-robin algorithm, we first re-state the following
classical scheduling problem.

##### Scheduling to find the maximum compatible job set

We are given a job set $J$ which contains $n$ jobs, i.e.,
$J=\set{j_{1},j_{2},\cdots,j_{n}}$, with each job regraded as a tuple, i.e.,
$j_{i}=(r_{i},p_{i},d_{i}),i\in[n],1\leqslant p_{i}\leqslant d_{i}-r_{i}+1,$
where $r_{i},p_{i},d_{i}$ are the release time, processing time and deadline,
respectively. There is one machine which is used to process jobs. A subset
$J^{\prime}$ of jobs is called compatible job set if and only if all jobs in
$J^{\prime}$ can be finished without preemption before their deadlines. The
objective is to find a compatible job set with the maximum size.

The above scheduling problem is the optimization version of the scheduling
problem SEQUENCING WITH RELEASE TIMES AND DEADLINES, which is strongly NP-
complete Garey and Johnson (1979). In Bar-Noy et al. (2001), they give an
$\frac{(m+1)^{m}}{(m+1)^{m}-m^{m}}$-approximation algorithm for $m$ identical
machines case. In particular, the approximation ratio is $2$ when $m=1$. We
restate the greedy algorithm for completeness (algorithm 7).

Algorithm 7 . 2-approximation for scheduling problem on single machine.

1: $\mathsf{ALGC}=\emptyset$.

2: $J^{*}=J$.

3: $D=0$.

4: while $J^{*}\neq\emptyset$ do

5: $J^{*}=\emptyset$. // reset $J^{*}$.

6: for every job $j\in J$ do

7: if $d_{j}\leqslant\max\\{D,r_{j}\\}+p_{j}$ then

8: $J^{*}=J^{*}\cup\set{j}$.

9: end if

10: end for

11: $j^{*}=\operatorname*{arg\,min}\limits_{j\in
J^{*}}\\{\max\\{D,r_{j}\\}+p_{j}\\}$.

12: Schedule job $j^{*}$ at time slot $\max\\{D,r_{j}\\}$.

13: $D=\max\\{D,r_{j^{*}}\\}+p_{j^{*}}$.

14: $\mathsf{ALGC}=\mathsf{ALGC}\cup\set{j^{*}}$.

15: end while

######  Theorem 7.

A schedule that is simultaneously EF1 and 1/2-IO exists and can be found in
polynomial time for all instance of FISP $\langle$unweighted,
flexible$\rangle$.

Now, we are ready to give the algorithm (algorithm 8) for instance of FISP
$\langle$unweighted, flexible$\rangle$.

Algorithm 8 . Round-Robin for FISP $\langle$unweighted, flexible$\rangle$

0: Agent set $A$ and job set $J$.

0: EF1 schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$.

1: $X_{1}=\cdots=X_{m}=\emptyset$.

2: $J^{*}_{1}=\cdots=J^{*}_{m}=J$.

3: $D_{1}=\cdots=D_{m}=0$.

4: $i=1$. // The index.

5: while there is a $J^{*}_{i}\neq\emptyset$ do

6: for all $a_{i}\in A$ do

7: $J_{i}^{*}=\emptyset$. // reset $J_{i}^{*}$.

8: for every job $j\in J$ do

9: if $d_{j}\leqslant\max\\{D_{i},r_{j}\\}+p_{j}$ then

10: $J^{*}_{i}=J^{*}_{i}\cup\set{j}$.

11: end if

12: end for

13: $j^{*}_{i}=\operatorname*{arg\,min}\limits_{j\in
J^{*}_{i}}\\{\max\\{D_{i},r_{j}\\}+p_{j}\\}$.

14: $X_{i}=X_{i}\cup\set{j^{*}_{i}}$.

15: Schedule job $j^{*}_{i}$ at $\max\\{D_{i},r_{j}\\}$.

16: $D_{i}=\max\\{D_{i},r_{j^{*}_{i}}\\}+p_{j^{*}_{i}}$.

17: $J=J\setminus\set{j^{*}_{i}}$.

18: end for

19: end while

20: $X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}$.

Let $\mathbf{X}=(X_{1},\cdots,X_{m})$ be the schedule returned by algorithm 8
and $X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}$. We first show that $\mathbf{X}$
is an 1/2-IO schedule and then prove that $\mathbf{X}$ is an EF1 schedule.

######  Lemma 15.

$u_{i}(X_{i})\geqslant\frac{1}{2}\cdot u_{i}(X_{i}\cup X_{0}),\forall a_{i}\in
A$.

###### Proof.

We consider an arbitrary agent $a_{i}\in A$ and the job set $X_{i}\cup X_{0}$.
Let $\mathsf{ALGC}$ be the set of jobs selected from $X_{0}\cup X_{i}$ by
algorithm 7. Let $\mathsf{OPTC}$ be the set of jobs selected by the optimal
algorithm. Since algorithm 7 is a $2$-approximation algorithm, we have
$|\mathsf{ALGC}|\geqslant\frac{1}{2}\cdot|\mathsf{OPTC}|$. Observe that if we
can prove that $\mathsf{ALGC}=X_{i}$, then we have
$u_{i}(X_{i})\geqslant\frac{1}{2}\cdot u_{i}(X_{i}\cup X_{0})$ since
$\mathsf{ALGC}$ has the size at least half of the optimal solution. Let
$\mathsf{ALGC}=\set{j_{1},j_{2},\cdots,j_{k}}$ and assume that the jobs are
added to the solution by algorithm 7 in this order. Let
$X_{i}=\set{j_{1}^{\prime},j_{2}^{\prime},\cdots,j_{r}^{\prime}}$ and assume
that the jobs are added to $X_{i}$ by algorithm 8 in this order. We prove by
comparison. Assume that $\mathsf{ALGC}$ and $X_{i}$ become different from the
$R$-th element, i.e., $j_{l}=j_{l}^{\prime},\forall l\in[R-1]$ and $j_{R}\neq
j_{R}^{\prime}$. Assume that the completion time of $j_{R-1}$ is $D_{R-1}$.
Then, we have

$j_{R}^{\prime}\neq j_{R}=\operatorname*{arg\,min}_{j\in
J_{R}^{*}}\\{\max\\{D_{R-1},r_{j}\\}+p_{j}\\},$

where $J_{R}^{*}\subseteq\mathcal{J}_{r}=X_{0}\cup
X_{i}\setminus\set{j_{1},\cdots,j_{R}}$ is a set of jobs which can be feasibly
scheduled after $j_{R}$, i.e.,

$J_{R}^{*}=\set{j\in\mathcal{J}_{r}}{\max\\{D_{R-1},r_{j}\\}+p_{j}\leqslant
d_{j}}.$

Note that $j_{R}^{\prime}\in J_{R}^{*}$. Since $j_{R}^{\prime}$ instead of
$j_{R}$ is assigned to agent $a_{i}$ in a certain round, we know that $j_{R}$
must be assigned to a certain agent before agent $a_{i}$ chooses, i.e.,
$j_{R}\in X_{k},\exists k\in[m]$. This contradicts our assumption since
$j_{R}\in X_{0}$.

∎

Let $J^{l}_{i}$ be the job set $J^{*}_{i}$ for agent $a_{i}\in A$ in the
$l$-th round, where $1\leqslant i\leqslant m$ and $1\leqslant l\leqslant L$.
Suppose that in first $L$-th rounds of algorithm 8,
$J^{*}_{i}\neq\emptyset,\forall i\in[m]$, i.e., in the $(L+1)$-th round,
$\exists i\in[m]$ such that $J^{*}_{i}=\emptyset$. Let $D_{i}^{l}$ be the
parameter $D_{i}$ in algorithm 8 for agent $a_{i}\in A$ at the end of the
$l$-th round, where $1\leqslant i\leqslant m$ and $1\leqslant l\leqslant L$.

######  Lemma 16.

$D_{1}^{l}\leqslant D_{2}^{l}\leqslant\cdots\leqslant D_{m}^{l},\forall
l\in[L]$. Moreover, we have $D_{m}^{l}\leqslant D_{1}^{l+1},\forall
l\in[L-1]$, and $D_{m}^{L}\leqslant D_{1}^{L+1}$ if
$J_{1}^{L+1}\neq\emptyset$.

###### Proof.

We first prove $D_{1}^{l}\leqslant D_{2}^{l}\leqslant\cdots\leqslant
D_{m}^{l},\forall l\in[L]$. Let $a_{k},a_{h}\in A$ be two agents, where
$1\leqslant k<h\leqslant n$. We only need to prove $D_{k}^{l}\leqslant
D_{h}^{l},\forall l\in[L]$. We prove by induction. In the base case where
$l=1$, $D_{k}^{1}\leqslant D_{h}^{1}$ obviously holds since agent $a_{k}$
chooses the job before $a_{h}$. Now, we have induction hypothesis
$D_{k}^{l}\leqslant D_{h}^{l}$ and we need to prove $D_{k}^{l+1}\leqslant
D_{h}^{l+1}$. We prove by contradiction and assume that
$D_{k}^{l+1}>D_{h}^{l+1}$. Let $j_{k}^{l+1},j_{h}^{l+1}$ be the jobs that are
selected by agent $a_{k},a_{h}$ in the $(l+1)$-round of algorithm 8,
respectively. Hence, we have

$\displaystyle D_{k}^{l+1}$
$\displaystyle=\max\\{D_{k}^{l},r_{j_{k}^{l+1}}\\}+p_{j_{k}^{l+1}},$
$\displaystyle D_{h}^{l+1}$
$\displaystyle=\max\\{D_{h}^{l},r_{j_{h}^{l+1}}\\}+p_{j_{h}^{l+1}}.$

By induction hypothesis $D_{k}^{l}\leqslant D_{h}^{l}$, we have

$\max\\{D_{k}^{l},r_{j_{h}^{l+1}}\\}+p_{j_{h}^{l+1}}\leqslant\max\\{D_{h}^{l},r_{j_{h}^{l+1}}\\}+p_{j_{h}^{l+1}}\leqslant
d_{j_{h}^{l+1}}.$

This implies that $j_{h}^{l+1}\in J_{k}^{l+1}$. Since

$\max\\{D_{k}^{l},r_{j_{h}^{l+1}}\\}+p_{j_{h}^{l+1}}\leqslant
D_{h}^{l+1}<D_{k}^{l+1},$

we have

$\max\\{D_{k}^{l},r_{j_{h}^{l+1}}\\}+p_{j_{h}^{l+1}}<\max\\{D_{k}^{l},r_{j_{k}^{l+1}}\\}+p_{j_{k}^{l+1}}.$

This implies that $j_{h}^{l+1}$ instead of $j_{k}^{l+1}$ will be chosen by
agent $a_{k}$ in the $(l+1)$-th round of algorithm 8. This contradicts our
assumption.

We assume that $J_{1}^{L+1}\neq\emptyset$ and prove that $D_{m}^{l}\leqslant
D_{1}^{l+1},\forall l\in[L]$. We prove $D_{m}^{l}\leqslant D_{1}^{l+1}$ holds
for any $1\leqslant l\leqslant L$. Note that $D_{r}^{0}=0,\forall r\in[m]$. We
prove by induction. In the base case where $l=1$, if $D_{m}^{1}>D_{1}^{2}$,
$a_{m}$ will choose $j_{1}^{2}$ instead of $j_{m}^{1}$ in the first round.
Now, we have induction hypothesis $D_{m}^{l}\leqslant D_{1}^{l+1}$ and we need
to prove that $D_{m}^{l+1}\leqslant D_{1}^{l+2}$ holds. We prove by
contradiction and assume that $D_{m}^{l+1}>D_{1}^{l+2}$. Let
$j_{m}^{l+1},j_{1}^{l+2}$ be the jobs that are selected by agent $a_{m},a_{1}$
in the $(l+1),(l+2)$-th round of algorithm 8, respectively. Note that in the
case where $l=L-1$, there always exists a job $j_{m}^{l+2}$ since
$\set{j_{m}^{L+1}}\neq\emptyset$. Hence, we have

$\displaystyle D_{m}^{l+1}$
$\displaystyle=\max\\{D_{m}^{l},r_{j_{m}^{l+1}}\\}+p_{j_{m}^{l+1}},$
$\displaystyle D_{1}^{l+2}$
$\displaystyle=\max\\{D_{1}^{l+1},r_{j_{1}^{l+2}}\\}+p_{j_{1}^{l+2}}.$

By induction hypothesis $D_{m}^{l}\leqslant D_{1}^{l+1}$, we have

$\max\\{D_{m}^{l},r_{j_{1}^{l+2}}\\}+p_{j_{1}^{l+2}}\leqslant\max\\{D_{1}^{l+1},r_{j_{1}^{l+2}}\\}+p_{j_{1}^{l+2}}\leqslant
d_{j_{1}^{l+2}}.$

This implies that $j_{1}^{l+2}\in J_{m}^{l+1}$. Since

$\max\\{D_{m}^{l},r_{j_{1}^{l+2}}\\}+p_{j_{1}^{l+2}}\leqslant
D_{1}^{l+2}<D_{m}^{l+1},$

we have

$\max\\{D_{m}^{l},r_{j_{1}^{l+2}}\\}+p_{j_{1}^{l+2}}<\max\\{D_{m}^{l},r_{j_{m}^{l+1}}\\}+p_{j_{m}^{l+1}}.$

This implies that $j_{1}^{l+2}$ instead of $j_{m}^{l+1}$ will be chosen by
agent $a_{m}$ in the $(l+1)$-th round of algorithm 8. This contradicts our
assumption. ∎

######  Lemma 17.

$J_{1}^{l}\supseteq J_{2}^{l}\supseteq\cdots\supseteq J_{m}^{l},\forall
l\in[L+1]$. Moreover, we have $J_{m}^{l}\supseteq J_{1}^{l+1},l\in[L]$.

###### Proof.

We first prove that $J_{1}^{l}\supseteq J_{2}^{l}\supseteq\cdots\supseteq
J_{m}^{l},\forall l\in[L]$. Let $a_{k},a_{h}\in A$ be two agents, where
$1\leqslant k<h\leqslant n$. We only need to prove $J^{l}_{k}\supseteq
J^{l}_{h}$. To prove $J^{l}_{h}\subseteq J^{l}_{k}$, we consider an arbitrary
job $j\in J^{l}_{h}$ and show that $j\in J^{l}_{k}$. Note that
$J_{k}^{l},J_{h}^{l}\neq\emptyset,\forall l\in[L]$. Let
$\mathcal{J}^{k}_{s},\mathcal{J}^{h}_{s}$ be the set of jobs that are already
assigned to the agents before agent $a_{k}$ and $a_{h}$ select, respectively.
Note that $\mathcal{J}^{k}_{s}\subseteq\mathcal{J}^{h}_{s}$. According to
algorithm 8, we have

$\displaystyle J^{l}_{k}$
$\displaystyle=\set{j\in(J\setminus\mathcal{J}_{s}^{k})}{d_{j}\leqslant\max\\{D^{l-1}_{k},r_{j}\\}+p_{j}},$
$\displaystyle J^{l}_{h}$
$\displaystyle=\set{j\in(J\setminus\mathcal{J}_{s}^{h})}{d_{j}\leqslant\max\\{D^{l-1}_{h},r_{j}\\}+p_{j}}.$

Since $\mathcal{J}^{k}_{s}\subseteq\mathcal{J}^{h}_{s}$, we have
$J\setminus\mathcal{J}_{s}^{k}\supseteq J\setminus\mathcal{J}_{s}^{h}$. Now we
consider an arbitrary job $j\in J_{h}^{l}$ and show that $j$ is also a member
of $J_{k}^{l}$. Since $j\in(J\setminus\mathcal{J}_{s}^{h})$ and
$J\setminus\mathcal{J}_{s}^{k}\supseteq J\setminus\mathcal{J}_{s}^{h}$, we
have $j\in(J\setminus\mathcal{J}_{s}^{k})$. Since $j\in J_{h}^{l}$, we have

$d_{j}\leqslant\max\\{D_{h}^{l-1},r_{j}\\}+p_{j}.$

According to lemma 16, $D_{h}^{l-1}\geqslant D_{k}^{l-1}$, we have

$d_{j}\leqslant\max\\{D_{k}^{l-1},r_{j}\\}+p_{j},$

which implies that $j\in J_{k}^{l}$. Now we consider the case where $l=L+1$.
Note that in the $(L+1)$-th round of algorithm 8, $\exists i\in[m]$ such that
$J_{i}^{L+1}=\emptyset$. Now we prove that $J_{k}^{L+1}\supseteq J_{h}^{L+1}$.
If $J_{h}^{L+1}=\emptyset$, then we are done. Hence, we assume that
$J_{h}^{L+1}\neq\emptyset$. By a similar argument, a job $j\in J_{h}^{L+1}$
has the property $d_{j}\leqslant\max\\{D_{h}^{L},r_{j}\\}+p_{j}$. Then we have
$d_{j}\leqslant\max\\{D_{k}^{L},r_{j}\\}+p_{j}$ holds since
$D_{k}^{L}\leqslant D_{h}^{L}$. Then we have $j\in J_{k}^{L+1}$.

Now, we prove that $J_{m}^{l}\supseteq J_{1}^{l+1},\forall l\in[L]$. Note that
it is possible that $J_{1}^{L+1}=\emptyset$. In this case $J_{m}^{L}\supseteq
J_{1}^{L+1}$ trivially holds. Hence, we assume that
$J_{1}^{L+1}\neq\emptyset$. To prove $J_{m}^{l}\supseteq J_{1}^{l+1}$, we
consider an arbitrary job $j\in J_{1}^{l+1}$ and show that $j\in J_{m}^{l}$.
Let $\mathcal{J}^{m}_{s},\mathcal{J}^{1}_{s}$ be the set of jobs that are
already assigned to the agents before agent $a_{m}$ and $a_{1}$ select in the
$l,(l+1)$-th round of algorithm 8, respectively. Note that
$\mathcal{J}^{m}_{s}\subseteq\mathcal{J}^{1}_{s}$. According to algorithm 8,
we have

$\displaystyle J_{m}^{l}$
$\displaystyle=\set{j\in(J\setminus\mathcal{J}^{m}_{s})}{d_{j}\leqslant\max\\{D_{m}^{l-1},r_{j}\\}+p_{j}},$
$\displaystyle J_{1}^{l+1}$
$\displaystyle=\set{j\in(J\setminus\mathcal{J}^{1}_{s})}{d_{j}\leqslant\max\\{D_{1}^{l},r_{j}\\}+p_{j}}.$

Since $\mathcal{J}^{m}_{s}\subseteq\mathcal{J}^{1}_{s}$, we have
$J\setminus\mathcal{J}^{m}_{s}\supseteq J\setminus\mathcal{J}^{1}_{s}$. Now we
consider an arbitrary job $j\in J_{1}^{l+1}$ and show that $j\in J_{m}^{l}$.
Since $j\in J_{1}^{l+1}$, we have

$d_{j}\leqslant\max\\{D_{1}^{l},r_{j}\\}+p_{j}.$

According to lemma 16, we have $D_{m}^{l-1}\leqslant D_{1}^{l}$. Then, we have

$\max\\{D_{1}^{l},r_{j}\\}+p_{j}\geqslant\max\\{D_{m}^{l-1},r_{j}\\}+p_{j}.$

Hence, we have $d_{j}\leqslant\max\\{D_{m}^{l-1},r_{j}\\}+p_{j}$ which implies
that $j\in J_{m}^{l}$. ∎

######  Lemma 18.

$|X_{i}|-|X_{k}|\in\set{-1,0,1},\forall i,k\in[m]$.

###### Proof.

We consider the $(L+1)$-th round of algorithm 8 in which there exists an agent
$a_{i}\in A$ such that $a_{i}$ does not choose any jobs for the first time.
Note that there may exist many agents that do not choose any job for the first
time in $(L+1)$-th round. We assume that $a_{f}$ is the first agent that
chooses nothing in the $(L+1)$-th round. Since $a_{f}$ chooses nothing, we
have $J_{f}^{L+1}=\emptyset$. According to lemma 17, we have
$J_{i}^{L+1}=\emptyset,\forall f\leqslant i\leqslant n$. Moreover, we have
$J_{i}^{L^{\prime}}=\emptyset,\forall i\in[m]$ and $L+1<L^{\prime}$.
Therefore, we have

$|X_{i}|=\begin{cases}L,&\forall f\leqslant i\leqslant m;\\\ L+1,&\forall
1\leqslant i<f.\end{cases}$

This implies that lemma 18 holds. ∎

Now we are ready to prove theorem 7.

###### Proof of theorem 7.

According to lemma 18 and lemma 15, we know that algorithm 8 will return a
feasible schedule that is simultaneously EF1 and 1/2-IO.

Now we bound the running time. According to lemma 18 and lemma 15, we know
that line 5-20 will be run at most $\lceil\frac{n}{m}\rceil$ times, where $n$
is the number of jobs and $m$ is the number of agents. In each while loop,
line 6-18 will be run at most $m$ times. In each for loop, line 8-12 will be
run at most $n$ times and the running time of line 13 can be bounded by
$O(n)$. Hence, we have the running time of algorithm 8
$O(\lceil\frac{n}{m}\rceil\cdot m\cdot(n^{2}+n))=O(mn^{3})$. ∎

##  6 Experiment

We now empirically test the performance of algorithm 4 when jobs are rigid,
comparing it against a simple Round-Robin algorithm. In this simple Round-
Robin algorithm, all jobs are sorted by their deadlines in non-decreasing
order. Then every agent picks a job in round-robin manner. Finally, every
agent computes the compatible intervals with the maximum weight and all the
remaining jobs will be assigned to charity. The formal description can be
found in algorithm 9 with $J^{\prime}=J$ and $A^{\prime}=A$. For the
experiments, we have implemented both algorithm 4 and the above round-robin
algorithm.

Algorithm 9 . Round-Robin (RR)

0: Agent set $A^{\prime}$ and job set $J^{\prime}$.

0: EF1 schedule $\mathbf{X}=(X_{1},\cdots,X_{|A^{\prime}|})$

1: Sort all jobs by their deadline in non-decreasing order.

2: $X_{1}=X_{2}=\cdots=X_{|A^{\prime}|}=\emptyset$.

3: $i=1,k=1$. // The index.

4: for all $j_{k}\in J^{\prime}$ do

5: for all $a_{i}\in A^{\prime}$ do

6: if $k\mod|A^{\prime}|=i$ then

7: $X_{i}=X_{i}\cup\set{j_{k}}$.

8: end if

9: end for

10: end for

11: $i=1$. // Reset the index

12: for all $X_{i}$ do

13: Let $X_{i}^{\prime}\subseteq X_{i}$ be the compatible job set with the
maximum weight for agent $a_{i}$.

14: $X_{i}=X_{i}^{\prime}$.

15: end for

16: $X_{0}=J\setminus\bigcup_{i\in[|A^{\prime}|]}X_{i}$.

We run our experiments on three job sets with different sizes: 100 (figure 1
(a)), 500 (figure 1 (b)) and 1000 (figure 1 (c)). The release time and
deadline of each job is uniformly randomly sampled from the interval [0,50].
For each job set, we further set up three subgroups according to the agents’
utility of every job: (i) the utility gain is sampled uniformly randomly from
[1,20]; (ii) the utility gain follows Poisson Distribution with means 50;
(iii) the utility gain follows Normal Distribution with means 25 and variance
10. For each subgroup, we further set up three subsubgroups according to the
size of agent set: 5, 10 and 15.

In total, our experiment contains $3\times 3\times 3$ groups. For each group,
we run algorithm 4 and Round-Robin algorithm on 1000 different instances.
Noted that algorithm 4 does not have a good performance when the number of
jobs is much larger than the number of agents, e.g., the groups with 5 agents
(U.1, P.1, N.1) in figure 1. The reason algorithm 4 performances
unsatisfactorily is that algorithm 4 stops at the threshold while there are a
lot of remaining jobs. To fix this problem, we add the Round-Robin procedure
at the end of algorithm 4, i.e., if there exist some unallocated jobs at the
end of algorithm 4, we run Round-Robin algorithm on the remaining job set.
Finally, every agent computes the maximum compatible job set from the union of
the job set returned by algorithm 4 and Round-Robin algorithm. The formal
description can be found in algorithm 10. Let BAG+ be the updated version of
algorithm 4 and BAG be the original one. With the help of the Round-Robin
procedure, the performance of algorithm 4 is better than the Round-Robin
algorithm in all groups. Note that BAG+ does not have better theoretical
performance than BAG. We give a hard instance to prove above argument in the
appendix.

Algorithm 10 . Matching-BagFilling + Round-Robin (BAG+)

0: Agent set $A$ and job set $J$.

0: EF1 schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$

1: Run algorithm 4.

2: Let $\mathbf{X}=(X_{1},\cdots,X_{m})$ be the schedule returned by algorithm
4.

3: Let $X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}$.

4: if $X_{0}\neq\emptyset$ then

5: Run algorithm 9 with job set $X_{0}$ and agent set $A$.

6: Let $\mathbf{X}^{\prime}=(X_{1}^{\prime},\cdots,X_{m}^{\prime})$ be the
schedule returned by algorithm 9.

7: end if

8: $i=1$. // The index.

9: for all $X_{i}$ do

10: Let $X_{i}^{\prime\prime}\subseteq(X_{i}\cup X_{i}^{\prime})$ be the
compatible job set with the maximum weight for agent $a_{i}$.

11: $X_{i}=X_{i}^{\prime\prime}$.

12: end for

13: $X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}$.

(a) Groups with $|J|=100$.

(b) Groups with $|J|=500$.

(c) Groups with $|J|=1000$.

Figure 1: The results of the evaluation of algorithm 4, algorithm 10 and
algorithm 9 on different settings. Every subfigure represents the groups with
same job set size. Every notation in x-axis represents a setting. Notations
"U.", "P.", "N.", represent the utility gain follows the Uniform, Poisson,
Normal Distribution, respectively. Notations "1", "2", "3", represent the
number of agents is 5, 10, 15, respectively. The top and bottom point of every
solid red interval represent the maximum and minimum value of BAG+/RR among
all the agents, where BAG+/RR is the ratio of total gain that the agents
receive when we run BAG+ and RR algorithm. The top and bottom point of every
dot-dashed green interval represent the maximum and minimum value of BAG/RR
among all the agents, where BAG/RR is the ratio of total gain that the agents
receive when we run BAG and RR algorithm.

According to figure 1, it is not hard to see that algorithm 4 is not able to
achieve a good performance when the number of jobs is much larger than the
number of agents. When the size of the job set is 100, algorithm 4 performs
worse than Round-Robin only in the setting where the agent set is 5 (see
figure 1 (a), only U.1, P.1, N.1’s green interval is behind 1.0). When we
increase the number of jobs to 500, the situation that algorithm 4 is worse
than Round-Robin begins to appear at $|A|=10$ (see figure 1 (b), part of green
interval of U.2 begins to appear behind 1.0). When we further increase the
number of jobs to 1000, algorithm 4 performs better than Round-Robin only in
the setting where there are 15 agents (see figure 1 (c), only U.3, P.3, N.3’s
green interval is above 1.0).

The reason is that algorithm 4 stops at the case where every agent gets the
threshold but there are a lot of remaining jobs. We can fix this issue by
adding an extra round-robin procedure to allocate the remaining jobs, and thus
yield BAG+ algorithm. According to figure 1, we can find that the performance
of BAG+ is better than Round-Robin in all settings as all red intervals are
above 1.0. Thus, BAG+ algorithm can achieve a good performance in practices
and guarantee the approximation in the worst case.

##  7 Conclusion and Future Directions

In this work, we studied the fair scheduling problem for time-dependent
resources, and designed constant approximation algorithms for MMS, EF1&PO and
EF1&IO schedules. There are many open problems and future directions. An
immediate direction is to improve our approximation ratios and investigate the
limit of approximation algorithms for different settings. It is also
interesting to impose other efficiency criteria on EF1 schedules, such as
computing an EF1 schedule that maximizes social welfare. In this work, we have
assumed the jobs are resources that bring utility to agents, and leave the
case when jobs are chores for future study. Finally, it is of both theoretical
interest and practical importance to consider the online setting when jobs
arrive dynamically and the strategic setting when agents’ valuations are
private information.

## References

  * Ajtai et al. [1998] Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, and Orli Waarts.  Fairness in scheduling.  J. Algorithms, 29(2):306–357, 1998.
  * Al-Arasi and Saif [2020] Rasha A. Al-Arasi and Anwar Saif.  Task scheduling in cloud computing based on metaheuristic techniques: A review paper.  EAI Endorsed Trans. Cloud Syst., 6(17):e4, 2020.
  * Amanatidis et al. [2017] Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi.  Approximation algorithms for computing maximin share allocations.  ACM Trans. Algorithms, 13(4):52:1–52:28, 2017.
  * Amanatidis et al. [2020] Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser.  Fast adaptive non-monotone submodular maximization subject to a knapsack constraint.  In NeurIPS, 2020.
  * Bar-Noy et al. [2001] Amotz Bar-Noy, Sudipto Guha, Joseph Naor, and Baruch Schieber.  Approximating the throughput of multiple machines in real-time scheduling.  SIAM J. Comput., 31(2):331–352, 2001.
  * Barman and Krishnamurthy [2020] Siddharth Barman and Sanath Kumar Krishnamurthy.  Approximation algorithms for maximin fair division.  ACM Trans. Economics and Comput., 8(1):5:1–5:28, 2020.
  * Barman et al. [2018] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Finding fair and efficient allocations.  In EC, pages 557–574. ACM, 2018.
  * Baruah and Lin [1998] Sanjoy K. Baruah and Shun-Shii Lin.  Pfair scheduling of generalized pinwheel task systems.  IEEE Trans. Computers, 47(7):812–816, 1998.
  * Baruah [1995] Sanjoy K. Baruah.  Fairness in periodic real-time scheduling.  In RTSS, pages 200–209. IEEE Computer Society, 1995.
  * Berman and DasGupta [2000] Piotr Berman and Bhaskar DasGupta.  Multi-phase algorithms for throughput maximization for real-time scheduling.  J. Comb. Optim., 4(3):307–323, 2000.
  * Bilò et al. [2016] Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli.  The price of envy-freeness in machine scheduling.  Theor. Comput. Sci., 613:65–78, 2016.
  * Biswas and Barman [2018] Arpita Biswas and Siddharth Barman.  Fair division under cardinality constraints.  In IJCAI, pages 91–97. ijcai.org, 2018.
  * Biswas and Barman [2019] Arpita Biswas and Siddharth Barman.  Matroid constrained fair allocation problem.  In AAAI, pages 9921–9922. AAAI Press, 2019.
  * Budish [2010] Eric Budish.  The combinatorial assignment problem: approximate competitive equilibrium from equal incomes.  In BQGT, page 74:1. ACM, 2010.
  * Caragiannis et al. [2016] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang.  The unreasonable fairness of maximum nash welfare.  In EC, pages 305–322. ACM, 2016.
  * Chen et al. [2019] Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala.  Proportionally fair clustering.  In ICML, volume 97 of Proceedings of Machine Learning Research, pages 1032–1041. PMLR, 2019.
  * Chiarelli et al. [2020] Nina Chiarelli, Matjaz Krnc, Martin Milanic, Ulrich Pferschy, Nevena Pivac, and Joachim Schauer.  Fair packing of independent sets.  In IWOCA, volume 12126 of Lecture Notes in Computer Science, pages 154–165. Springer, 2020.
  * Chierichetti et al. [2017] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii.  Fair clustering through fairlets.  In NIPS, pages 5029–5037, 2017.
  * Chuzhoy et al. [2006] Julia Chuzhoy, Rafail Ostrovsky, and Yuval Rabani.  Approximation algorithms for the job interval selection problem and related scheduling problems.  Math. Oper. Res., 31(4):730–738, 2006.
  * Dror et al. [2020] Amitay Dror, Michal Feldman, and Erel Segal-Halevi.  On fair division under heterogeneous matroid constraints.  CoRR, abs/2010.07280, 2020.
  * Drozdowski [2009] Maciej Drozdowski.  Scheduling for Parallel Processing.  Computer Communications and Networks. Springer, 2009.
  * Feige et al. [2021] Uriel Feige, Ariel Sapir, and Laliv Tauber.  A tight negative example for MMS fair allocations.  CoRR, abs/2104.04977, 2021.
  * Garey and Johnson [1979] M. R. Garey and David S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
  * Garg and Taki [2020] Jugal Garg and Setareh Taki.  An improved approximation algorithm for maximin shares.  In EC, pages 379–380. ACM, 2020.
  * Gentner et al. [2004] Karsten Gentner, Klaus Neumann, Christoph Schwindt, and Norbert Trautmann.  Batch production scheduling in the process industries.  In Handbook of Scheduling. Chapman and Hall/CRC, 2004.
  * Ghodsi et al. [2018] Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami.  Fair allocation of indivisible goods: Improvements and generalizations.  In EC, pages 539–556. ACM, 2018.
  * Hummel and Hetland [2021] Halvard Hummel and Magnus Lie Hetland.  Fair allocation of conflicting items.  CoRR, abs/2104.06280, 2021.
  * Im and Moseley [2020] Sungjin Im and Benjamin Moseley.  Fair scheduling via iterative quasi-uniform sampling.  SIAM J. Comput., 49(3):658–680, 2020.
  * Im et al. [2020] Sungjin Im, Shi Li, and Benjamin Moseley.  Breaking 1 - 1/e barrier for nonpreemptive throughput maximization.  SIAM J. Discret. Math., 34(3):1649–1669, 2020.
  * Kleinberg and Tardos [2006] Jon M. Kleinberg and Éva Tardos.  Algorithm design.  Addison-Wesley, 2006.
  * Kurokawa et al. [2018] David Kurokawa, Ariel D. Procaccia, and Junxing Wang.  Fair enough: Guaranteeing approximate maximin shares.  J. ACM, 65(2):8:1–8:27, 2018.
  * Lipton et al. [2004] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi.  On approximately fair allocations of indivisible goods.  In EC, pages 125–131. ACM, 2004.
  * Paleja et al. [2020] Rohan R. Paleja, Andrew Silva, Letian Chen, and Matthew C. Gombolay.  Interpretable and personalized apprenticeship scheduling: Learning interpretable scheduling policies from heterogeneous user demonstrations.  In NeurIPS, 2020.
  * Purohit et al. [2018] Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ML predictions.  In NeurIPS, pages 9684–9693, 2018.
  * Rahmattalabi et al. [2019] Aida Rahmattalabi, Phebe Vayanos, Anthony Fulginiti, Eric Rice, Bryan Wilder, Amulya Yadav, and Milind Tambe.  Exploring algorithmic fairness in robust graph covering problems.  In NeurIPS, pages 15750–15761, 2019.
  * Schrijver [1999] Alexander Schrijver.  Theory of linear and integer programming.  Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1999.
  * Wu et al. [2021] Xiaowei Wu, Bo Li, and Jiarui Gan.  Budget-feasible maximum nash social welfare allocation is almost envy-free.  In IJCAI. ijcai.org, 2021.
  * Zhang et al. [2020] Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Chi Xu.  Learning to dispatch for job shop scheduling via deep reinforcement learning.  In NeurIPS, 2020.

## Appendix

##  Appendix A Missing Materials in section 2

A set function $f:2^{V}\to\mathbb{R}$ defined on $V$ is called fractionally
subadditive (XOS) if there is a finite set of additive functions
$\set{f_{1},\cdots,f_{w}}$ such that $f(S)=\max_{1\leqslant i\leqslant
m}f_{i}(S)$ for any $S\subseteq V$.

######  Lemma 19.

IS functions are XOS.

###### Proof.

Let $u$ be an IS function defined on job set $J=\set{j_{1},\cdots,j_{n}}$ with
individual utility $(v_{1}=u(j_{1}),\cdots,v_{n}=u(j_{n}))$. To show $u$ is
XOS, it suffices to define a finite set of additive functions on $J$. For each
feasible job set $T\subseteq J$, define additive function $f_{T}$ such that
$f_{T}(j_{i})=v_{i}$ if $j_{i}\in T$ and $f_{T}(j_{i})=0$ otherwise.
Therefore, for any $S\subseteq T$,

$u(S)=\max_{T\subseteq S:T\text{ is feasible}}\sum_{j_{i}\in
T}v_{i}=\max_{T\subseteq S:T\text{ is feasible}}f_{T}(T)=\max_{T\subseteq
S:T\text{ is feasible}}f_{T}(S)=\max_{T\text{ is feasible}}f_{T}(S),$

where the last equality is because any subset of a feasible job set is also
feasible. Thus $u$ is XOS. ∎

##  Appendix B Missing Materials for MMS Scheduling in section 3

Lemma 4 (restate). For any $a_{i}$, if $\gamma_{i}\leqslant\mathsf{MMS}_{i}$,
algorithm 3 ensures that
$u_{i}(X_{i})\geqslant\frac{\beta}{\beta+2}\gamma_{i}$, regardless of
$\gamma_{-i}$.

###### Proof of Lemma 4.

Note that the algorithm only ensures that agent $a_{i}$ with
$\gamma_{i}\leqslant\mathsf{MMS}_{i}$ can obtain a bag but not everyone. This
is natural as if for some $a_{j}\neq a_{i}$ and $\gamma_{j}$ is super large
compared with $\mathsf{MMS}_{j}$, $a_{j}$ will never stop the algorithm and
get a bag.

Recall that we can assume that there is no large job in the instance, i.e.,
$u_{i}(j_{k})\leqslant\frac{\beta}{\beta+2}\cdot\gamma_{i}$, where
$0\leqslant\beta\leqslant 1$. Observe that if agent $a_{i}$ gets assigned a
bag, then her true utility satisfies:

$u_{i}(X_{i})=\sum_{j_{l}\in
X_{i}}u_{i}(j_{l})=u_{i}^{\prime}(X_{i})\geqslant\frac{\beta}{\beta+2}\gamma_{i}.$

The above inequality also holds no matter whether
$\gamma_{i}\leqslant\mathsf{MMS}_{i}$ or not. Similar as the proof of lemma 3,
the core is to prove that $a_{i}$ can be guaranteed to obtain a bag as long as
$\gamma_{i}\leqslant\mathsf{MMS}_{i}$. We consider the $R$-th round of the
outer while loop of algorithm 4 (line 2-5) in which the value of $\gamma_{i}$
is decreased below $\mathsf{MMS}_{i}$. In the $R$-th round of algorithm 4
(line 2-5), we assume that the order of the agents that break the while loop
of algorithm 2 (line 4-10) is $\set{a_{1},\cdots,a_{i-1},a_{i},\cdots}$. It
suffices to prove that at the beginning of the $i$-th while loop of algorithm
2 (line 4-10), there are sufficiently many remaining jobs in $J^{\prime}$ for
the agent $a_{i}$, i.e.,

$u_{i}^{\prime}(J^{\prime})\geqslant\frac{\beta}{\beta+2}\cdot\gamma_{i},\forall
a_{i}\in A^{\prime}.$

Similar as the proof of lemma 3, we prove the following stronger claim. Given
4 and the $\beta$-approximation of $u_{i}^{\prime}$, we have
$u_{i}^{\prime}(X_{k}^{\prime}\cap
J^{\prime})\geqslant\frac{\beta}{\beta+2}\cdot\gamma_{i}$ Therefore lemma 4
holds. ∎

######  Claim 4.

For any $a_{i}\in A^{\prime}$ with $\gamma_{i}\leqslant\mathsf{MMS}_{i}$, let
$\mathbf{X}^{\prime}=\set{X_{1}^{\prime},\cdots,X_{m}^{\prime}}$ be a feasible
MMS schedule for $a_{i}$. Then, there exists $k\in[m]$ such that
$u_{i}(X_{k}^{\prime}\cap
J^{\prime})\geqslant\frac{1}{\beta+2}\cdot\gamma_{i}$, where
$\gamma_{i}\leqslant\mathsf{MMS}_{i}$.

###### Proof.

We consider an arbitrary agent $a_{i}$. Since
$\mathbf{X}^{\prime}=(X_{1}^{\prime},X_{2}^{\prime},\cdots,X_{m}^{\prime})$ is
a feasible MMS schedule for $a_{i}$, we have
$u_{i}(X_{k}^{\prime})\geqslant\mathsf{MMS}_{i}\geqslant\gamma_{i},\forall
k\in[m]$ and therefore

$\sum_{k=1}^{m}u_{i}(X_{k}^{\prime})\geqslant m\cdot\mathsf{MMS}_{i}\geqslant
m\cdot\gamma_{i}.$ (9)

Same as the proof of lemma 3, the key idea of the proof is to show that agent
$a_{i}$ values the bundles that are taken by the agents before $a_{i}$ less
than $\frac{\beta+1}{\beta+2}\cdot\gamma_{i}$, i.e.,

$u_{i}(X_{r})<\frac{\beta+1}{\beta+2}\cdot\gamma_{i},\forall r\in[i-1].$ (10)

We consider an arbitrary bundle that is taken by agent $a_{r},r\in[i-1]$ and
assume that job $j_{r}$ is the last job added to the Bag. Since $a_{i}$ did
not break the while loop, we have
$u_{i}^{\prime}(X_{r}\setminus\set{j_{r}})<\frac{\beta}{\beta+2}\cdot\gamma_{i}$.
This implies that
$u_{i}(X_{r}\setminus\set{j_{r}})\leqslant\frac{1}{\beta+2}\cdot\gamma_{i}$.
Since all jobs are small, i.e.,
$u_{i}(j_{r})\leqslant\frac{\beta}{\beta+2}\cdot\gamma_{i}$, we have

$u_{i}(X_{r})=u_{i}(X_{r}\setminus\set{j_{r}})+u_{i}(j_{r})<\frac{\beta+1}{\beta+2}\cdot\gamma_{i}.$

Therefore, equation 10 holds. To help understand the following proof, an
example is shown in figure 2. Every rectangle in figure 2 represents a job in
$J$. The area of every rectangle $j_{l}$ in figure 2 represents the value of
$u_{i}(j_{l})$. The non-white rectangles represent the jobs that are assigned
to some agents in $\set{a_{1},\cdots,a_{i-1}}$. According to equation 10, the
total area of non-white rectangles in figure 2 is at most
$\frac{(\beta+1)(i-1)}{\beta+2}\gamma_{i}$, i.e.,
$\sum_{r=1}^{i-1}u_{i}(X_{r})<\frac{(\beta+1)(i-1)}{\beta+2}\gamma_{i}$.
According to equation 9, the total area of rectangles in figure 2 is at least
$m\gamma_{i}$. Therefore, the total area of white rectangles in
$\set{X_{1}^{\prime},\cdots,X_{m}^{\prime}}$ is at least
$m\gamma_{i}-\frac{(\beta+1)(i-1)}{\beta+2}\gamma_{i}$, i.e.,

$\sum_{r=1}^{m}u_{i}(X_{r}^{\prime}\setminus\bigcup_{l\in[i-1]}X_{l})>m\gamma_{i}-\frac{(\beta+1)(i-1)}{\beta+2}\gamma_{i}\geqslant\frac{m+\beta+1}{\beta+2}\gamma_{i},$
(11)

where the last inequality is due to $i\leqslant m$.

Figure 2: Illustration of 4. The schedule is the feasible schedule
$\mathbf{X}^{\prime}$ which implies that job set $X_{r}^{\prime}$ is a
feasible for all $r\in[m]$. Every rectangle represents a job. The width of
rectangle $j_{l}$ is the value of $u_{i}(j_{l})$ while the height is 1. The
area of rectangle $j_{l}$ is also the value of $u_{i}(j_{l})$. The four agents
$a_{1},a_{2},a_{3},a_{4}\in\set{a_{1},\cdots,a_{i-1}}$. The non-white
rectangles represent the jobs that are assigned in some agents in
$\set{a_{1},\cdots,a_{i-1}}$ in schedule $\mathbf{X}$, e.g., the gray, blue,
green, pink rectangles are the jobs that are assigned to
$a_{1},a_{2},a_{3},a_{4}$, respectively. Recall that $\mathbf{X}$ is the
schedule returned by algorithm 2. The white rectangles are the jobs in
$J^{\prime}$. In 4, we show that there exist a $r\in[m]$ such that total area
of white rectangles in $X_{r}^{\prime}$ is at least
$\frac{1}{\beta+2}\gamma_{i}$.

According to equation 11, the total area of white rectangles is at least
$\frac{m+\beta+1}{\beta+2}\gamma_{i}$. There must exist an $r\in[m]$ such that
$u_{i}(X_{r}^{\prime}\cap
J^{\prime})\geqslant\frac{m+\beta+1}{m(\beta+2)}\gamma_{i}$. Therefore, 4
holds. ∎

##  Appendix C Missing Proof for EF1 and PO Scheduling in section 4

###  C.1 Proof of theorem 4

Theorem 4 (restate) Given an arbitrary instance of general FISP, any schedule
that maximizes the Nash social welfare is a 1/4-EF1 and PO schedule.

###### Proof of theorem 4.

Given an arbitrary instance of general FISP, let
$\mathbf{X}=(X_{1},\cdots,X_{m})$ be the MaxNSW schedule and let
$X_{0}=J\setminus\bigcup_{i\in[m]}X_{i}$. Since any MaxNSW schedule must be a
PO schedule, we only prove that $\mathbf{X}$ is a 1/4-EF1 schedule i.e.,
$\forall
i,k\in[m],u_{i}(X_{i})\geqslant\frac{1}{4}u_{i}(X_{k}\setminus\set{j_{p}}),\exists
j_{p}\in X_{k}$. Suppose, on the contrary, that there exists $i,k\in[m]$ such
that $u_{i}(X_{i})<\frac{1}{4}u_{i}(X_{k}\setminus\set{j_{p}}),\forall
j_{p}\in X_{k}$.

Now, we sort all jobs in $X_{k}$ in non-increasing order according to the
value of $u_{k}(j_{p}),j_{p}\in X_{k}$. Assume that
$X_{k}=\set{j_{1},j_{2},\cdots}$ after sorting. Without loss of generality, we
assume that $|X_{k}|$ is an odd number; otherwise, we add a dummy job $j_{o}$
to $X_{k}$ such that $u_{i}(j_{o}),\forall i\in[m]$. Now we partition
$X_{k}\setminus\set{j_{1}}$ into two subsets $X_{k}^{1},X_{k}^{2}$, where
$X_{k}^{1}=\set{j_{2},j_{4},j_{6},\cdots}$ and
$X_{k}^{2}=\set{j_{3},j_{5},j_{7},\cdots}$. Note that
$X_{k}=\set{j_{1}}\cup\set{X_{k}^{1}}\cup\set{X_{k}^{2}}$. Note that
$u_{k}(X_{k}^{1})\geqslant u_{k}(X_{k}^{2})$ and
$u_{k}(X_{k}^{2}\cup\set{j_{1}})\geqslant u_{k}(X_{k}^{1})$ since all jobs in
$X_{k}$ are sorted in non-increasing order. Since $u_{k}(X_{k}^{1})\geqslant
u_{k}(X_{k}^{2})$, we have $u_{k}(j_{1})+u_{k}(X_{k}^{1})\geqslant
u_{k}(X_{k}^{2})$. Therefore, we have

$u_{k}(X_{k}^{d}\cup\set{j_{1}})\geqslant\frac{1}{2}u_{k}(X_{k}),\forall
d\in\set{1,2}.$ (12)

Since $u_{i}(X_{i})<\frac{1}{4}u_{i}(X_{k}\setminus\set{j_{p}}),\forall
j_{p}\in X_{k}$, we have $u_{i}(X_{i})<\frac{1}{4}u_{i}(X_{k}^{1}\cup
X_{k}^{2})$. Since $X_{k}$ is a feasible job set, we have $u_{i}(X_{k}^{1}\cup
X_{k}^{2})=u_{i}(X_{k}^{1})+u_{i}(X_{k}^{2})$ which implies that either
$u_{i}(X_{k}^{1})\geqslant\frac{1}{2}u_{i}(X_{k}^{1}\cup X_{k}^{2})$ or
$u_{i}(X_{k}^{1})\geqslant\frac{1}{2}u_{i}(X_{k}^{1}\cup X_{k}^{2})$.
Therefore, we have

$u_{i}(X_{i})<\frac{1}{4}u_{i}(X_{k}^{1}\cup
X_{k}^{2})\leqslant\frac{1}{2}u_{i}(X_{k}^{d}),\exists d\in\set{1,2}.$ (13)

Now we construct a new schedule, denoted by
$\mathbf{X}^{\prime}=(X_{1}^{\prime},\cdots,X_{m}^{\prime})$, where
$X_{r}^{\prime}=X_{r},\forall r\in[m],r\neq i,k$. Let
$X_{0}^{\prime}=J\setminus\bigcup_{i\in[m]}X_{i}^{\prime}$. We discard all
jobs in $X_{i}$, i.e., $X_{0}^{\prime}=X_{0}\cup X_{i}$. If
$u_{i}(X_{k}^{1})\geqslant\frac{1}{2}u_{i}(X_{k}^{1}\cup X_{k}^{2})$, let
$X_{i}^{\prime}=X_{k}^{1}$ and $X_{k}^{\prime}=X_{k}^{2}\cup\set{j_{1}}$;
otherwise, let $X_{i}^{\prime}=X_{k}^{2}$ and
$X_{k}^{\prime}=X_{k}^{1}\cup\set{j_{1}}$. It is easy to see that
$\mathbf{X}^{\prime}$ is a feasible schedule. Note thar all job sets in
$\mathbf{X}^{\prime}$ except $X_{0}^{\prime},X_{i}^{\prime},X_{k}^{\prime}$
are the same as the corresponding job sets in $\mathbf{X}$. Observe that if we
can prove that
$u_{i}(X_{i}^{\prime})u_{k}(X_{k}^{\prime})>u_{i}(X_{i})u_{k}(X_{k})$, then
$\mathbf{X}$ is not a MaxNSW schedule which will contradict our assumption. In
the case where $u_{i}(X_{k}^{1})\geqslant\frac{1}{2}u_{i}(X_{k}^{1}\cup
X_{k}^{2})$, we have $X_{i}^{\prime}=X_{k}^{1}$. By equation 12, we have
$u_{k}(X_{k}^{\prime})=u_{k}(X_{k}^{2}\cup\set{j_{1}})\geqslant\frac{1}{2}u_{k}(X_{k})$.
By equation 13, we have
$u_{i}(X_{i}^{\prime})=u_{i}(X_{k}^{1})>{2}u_{i}(X_{i})$. In the case where
$u_{i}(X_{k}^{1})<\frac{1}{2}u_{i}(X_{k}^{1}\cup X_{k}^{2})$, we have
$X_{i}^{\prime}=X_{k}^{2}$. By equation 12, we have
$u_{k}(X_{k}^{\prime})=u_{k}(X_{k}^{1}\cup\set{j_{1}})\geqslant\frac{1}{2}u_{k}(X_{k})$.
By equation 13, we have
$u_{i}(X_{i}^{\prime})=u_{i}(X_{k}^{2})>{2}u_{i}(X_{i})$. By combining above
two cases, we have
$u_{i}(X_{i})u_{i}(X_{k})<u_{i}(X_{i}^{\prime})u_{k}(X_{k}^{\prime})$. ∎

###  C.2 The tight instance for theorem 4

######  Lemma 20.

Given an arbitrary instance of general FISP, a MaxNSW schedule can only
guarantee 1/4-EF1 and PO.

###### Proof.

To prove lemma 20, it is sufficient to give an instance such that MaxNSW
schedule is exactly 1/4-EF1 schedule and PO. In this instance, all jobs in job
set $J$ are rigid and $J$ can be partitioned into two sets $J_{L}$ and
$J_{S}$. There is only one job in $J_{L}$ which is very long and has weight
$1$. There are $\frac{4}{\epsilon}$ jobs in $J_{S}$ each of which has unit
length and weight $\epsilon$. Note that $\frac{4}{\epsilon}$ is assumed to be
an even integer number. All jobs in $J_{S}$ are disjoint and the job in
$J_{L}$ intersects with all jobs in $J_{S}$. The agent set $A$ contains only
two agents, i.e., $|A|=2$. The instance can be found in figure 3.

Figure 3: Tight example of MaxNSW schedule for general FISP.

Note that the total weight of jobs in $J_{S}$ is $4$. Let
$\mathbf{X}=(X_{1},X_{2})$ be the schedule, where $X_{1}=J_{L},X_{2}=J_{S}$.
let $\mathbf{X}^{\prime}=(X_{1}^{\prime},X_{2}^{\prime})$, where
$X_{1}^{\prime}=\set{j_{2},\cdots,j_{\frac{2}{\epsilon}+1}},X_{2}^{\prime}=J_{S}\setminus
X_{1}^{\prime}$, i.e., $J_{S}$ is partitioned into two subsets with equal
size. Note that $X_{0}^{\prime}=J_{L}$. It is not hard to see that
$\mathbf{X}^{\prime}$ is a MaxNSW schedule. And we have
$u_{1}(X_{1})u_{2}(X_{2})=4$, $u_{1}(X_{1}^{\prime})u_{2}(X_{2}^{\prime})=4$.
Therefore, $\mathbf{X}$ is a MaxNSW schedule. Note that
$u_{1}(X_{2}\setminus\set{j_{p}})=\frac{4-\epsilon}{\epsilon}\cdot\epsilon=4-\epsilon,\forall
j_{p}\in X_{2}$. Therefore, we have

$\lim_{\epsilon\to
0}\frac{1}{4}u_{1}(X_{2}\setminus\set{j_{p}})=1=u_{1}(X_{1}),\forall j_{p}\in
X_{1}.$

This implies that $\mathbf{X}$ is a 1/4-EF1 schedule. ∎

##  Appendix D Missing the Hard Instance in section 6

In the following, we present an instance such that even without the
preprocessing procedure and the last agent takes away all remaining jobs,
everyone obtains exactly $\frac{1}{3}\mathsf{MMS}_{i}+\epsilon$. Accordingly,
the instance proves that “Matching-BagFilling+ does not have better
theoretical performance than Matching-BagFilling” as claimed in section 6.

Consider the following instance with $|A|=m$ agents where $m$ is a
sufficiently large even number.

The job set $J$ can be classified into the following categories:

  * •

$J_{1}=\set{j_{1}^{1},j_{2}^{1},\cdots,j_{m}^{1}}$: There are $m$ rigid jobs
in $J_{1}$. Every job in $J_{1}$ has the same job interval $[1,2]$. For every
job in $J_{1}$, $a_{m}$ has the same utility gain $\frac{1}{3}+\frac{1}{m}$.
For every job in $J_{1}$, all agents in $A\setminus\set{a_{m}}$ have the same
utility gain $\frac{2}{3}+\frac{1}{m}$;

  * •

$J_{2}=\set{j_{1}^{2},j_{2}^{2},\cdots,j_{m-1}^{2}}$: There are $m-1$ rigid
jobs in $J_{2}$. Every job in $J_{2}$ has the same job interval
$[3,\frac{m}{2}+2]$. For every job in $J_{2}$, all agents in $A$ have the same
utility gain $\frac{1}{3}$;

  * •

$J_{3}=\set{j_{1}^{3},j_{2}^{3},\cdots,j_{m-1}^{3}}$: There are $m$ unit jobs
in $J_{3}$. Every job in $J_{3}$ has the same job interval $[3,m+2]$. For
every job in $J_{3}$, all agents in $A$ have the same utility gain
$\frac{1}{3m}$;

  * •

$J_{4}=\bigcup_{r\in[m]}J_{4}^{r}$: There are $m$ group rigid jobs in $J_{4}$.
Each group $J_{4}^{r},r\in[m],$ contains $m$ rigid jobs. Assume that
$J_{4}^{r}=\set{j_{r1}^{4},j_{r2}^{4},\cdots,j_{rm}^{4}},\forall r\in[m-1]$. A
job $j_{ri}^{4}\in J_{4}^{r},i\in[m]$ has the job interval $[m+3+i,m+4+i]$.
Assume that $J_{4}^{m}=\set{j_{m1}^{4},j_{m2}^{4},\cdots,j_{mm}^{4}}$. A job
$j_{mi}^{4}\in J_{3}^{m}$ has the job interval $[m+4+i,m+5+i]$. In total,
there are $m^{2}$ jobs in $J_{4}$. For every job in $J_{4}$, $a_{m}$ has the
same utility gain $\frac{1}{3m}$. For every job in $J_{4}$, all agents in
$A\setminus\set{a_{m}}$ have the same utility gain $0$.

Let us focus on $a_{m}$ first. The upper bound of $\mathsf{MMS}_{m}$ is:

$\frac{1}{m}\cdot\left((\frac{1}{3}+\frac{1}{m})\cdot
m+\frac{m-1}{3}+\frac{1}{3m}\cdot m+\frac{1}{3m}\cdot
m^{2}\right)=1+\frac{1}{m}.$

We consider the schedule $\mathbf{X}=(X_{1},\cdots,X_{m})$, where
$X_{i}=\set{j_{i}^{1},j_{i}^{2}}\cup J_{4}^{i},\forall i\in[m-1]$ and
$X_{m}=\set{j_{m}^{1}}\cup J_{3}\cup J_{4}^{m}$ (See figure 4). It is not hard
to see that $\mathbf{X}$ is a feasible schedule and
$\min_{i\in[m]}u_{m}(X_{i})=u_{m}(X_{m})=1+\frac{1}{m}$. Therefore,
$\mathbf{X}$ is a feasible schedule that obtains the value $1+\frac{1}{m}$
which is also the upper bound of $\mathsf{MMS}_{m}$. Thus,
$\mathsf{MMS}_{m}=1+\frac{1}{m}$. Hence, once $a_{m}$ values the bag greater
than or equal to $\frac{1}{3}+\frac{1}{3m}$, $a_{m}$ will take the bag away.

Figure 4: Illustration for the tight instance for algorithm 3. The above
schedule is $\mathbf{X}$ which is also the MMS schedule for agent $a_{m}$. The
red jobs are the remaining jobs at the end of the $(m-1)$-th round of
algorithm 3 with the specified job sequence described in the "The specified
job sequence" paragraph.

Now, we consider an arbitrary agent $a_{i}\in A\setminus\set{a_{m}}$. Since
all agents in $A\setminus\set{a_{m}}$ have utility gain 0 for all jobs in
$J_{4}$, we can ignore the job set $J_{4}$. Therefore, the upper bound of
$\mathsf{MMS}_{i},\forall i\in[m-1]$ is:

$\frac{1}{m}\left((\frac{2}{3}+\frac{1}{m})\cdot
m+(\frac{m-1}{3})+(\frac{1}{3m})\cdot m\right)=1+\frac{1}{m}.$

We consider the schedule
$\mathbf{X}^{\prime}=(X_{1}^{\prime},\cdots,X_{m}^{\prime})$, where
$X_{i}^{\prime}=\set{j_{i}^{1},j_{i}^{2}},\forall i\in[m-1]$ and
$X_{m}^{\prime}=\set{j_{m}^{1}}\cup J_{3}$. It is not hard to see that
$\mathbf{X}^{\prime}$ is a feasible schedule and
$u_{i}(X_{k}^{\prime})=u_{i}(X_{r}^{\prime})=1+\frac{1}{m},\forall
k,r\in[m],\forall i\in[m-1]$. Therefore, $\mathbf{X}^{\prime}$ is a feasible
schedule that obtains the value $1+\frac{1}{m}$ which is also an upper bound
of $\mathsf{MMS}_{i},\forall i\in[m-1]$. Thus,
$\mathsf{MMS}_{i}=1+\frac{1}{m},\forall i\in[m-1]$. Hence, once agent
$a_{i},\forall i\in[m-1],$ values the bag greater than or equal to
$\frac{1}{3}+\frac{1}{3m}$, $a_{i}$ will take the bag away.

##### The specified job sequence

Now, we consider the following job sequence. In the first round, algorithm 3
adds $J_{1}^{4}\setminus\set{j_{1(m-1)}^{4},j_{1m}^{4}}$ to the bag, and then
adds $j_{1}^{3},j_{m1}^{4}$ to the bag, and then adds $j_{1}^{2}$ to the bag,
i.e.,
$\mathsf{BAG}=\set{j_{11}^{4},j_{12}^{4},\cdots,j_{1(m-2)}^{4}}\cup\set{j_{1}^{3},j_{m1}^{4}}\cup\set{j_{1}^{2}}$.
It is not hard to see that $\mathsf{BAG}$ is a feasible job set and all agents
in $A\setminus\set{a_{m}}$ value the bag exactly $\frac{1}{3}+\frac{1}{3m}$.
Without loss of generality, we assume that $a_{1}$ takes the bag away at the
end of the first round. In the $l$-th round, $2\leqslant l\leqslant m-1$,
algorithm 3 first adds $J_{l}^{4}\setminus\set{j_{l(m-1)}^{4},j_{lm}^{4}}$,
and then adds $j_{l}^{3},j_{ml}^{4}$, and then adds $j_{l}^{2}$ to the bag.
Without loss of generality, we assume that $a_{l}$ takes the bag away at the
end of the $l$-th round, where $2\leqslant l\leqslant m-1$. Note that, at the
end of the $(m-1)$-th round, all agents in $A\setminus\set{a_{m}}$ obtain the
utility gain exactly $\frac{1}{3}+\frac{1}{3m}$.

It is not hard to see that, at the end of the $(m-1)$-th round,

$J^{\prime}=J_{1}\cup\set{j_{m}^{3}}\cup\set{j_{mm}^{4}}\cup\set{j_{1(m-1)}^{4},j_{1m}^{4}}\cup\set{j_{2(m-1)}^{4},j_{2m}^{4}}\cup\cdots\set{j_{(m-1)(m-1)}^{4},j_{(m-1)m}^{4}}.$

See the red jobs in figure 4. Thus,
$u_{m}(J^{\prime})=(\frac{1}{3}+\frac{1}{m})+\frac{1}{3m}+\frac{3}{3m}=\frac{1}{3}+\frac{7}{3m}$.

Therefore, everyone obtains exactly $\frac{1}{3}\mathsf{MMS}_{i}+\epsilon$ at
the end of algorithm 3. Moreover, it is not hard to see that if we run round-
robin procedure at the end of algorithm 3, the utility gains of all agents in
$A\setminus\set{a_{m}}$ will be increased but the utility gain of $a_{m}$ is
not able to be further improved. Thus, the above instance implies that “BAG+
does not have better theoretical performance than BAG”.