# The Submodular Santa Claus Problem
in the Restricted Assignment Case111This research was supported by the Swiss
National Science Foundation project 200021-184656 “Randomness in Problem
Instances and Randomized Algorithms.”

Etienne Bamas222EPFL, Switzerland<EMAIL_ADDRESS>Paritosh Garg333EPFL,
Switzerland<EMAIL_ADDRESS>Lars Rohwedder444EPFL, Switzerland,
<EMAIL_ADDRESS>
###### Abstract

The submodular Santa Claus problem was introduced in a seminal work by
Goemans, Harvey, Iwata, and Mirrokni (SODA’09) as an application of their
structural result. In the mentioned problem $n$ unsplittable resources have to
be assigned to $m$ players, each with a monotone submodular utility function
$f_{i}$. The goal is to maximize $\min_{i}f_{i}(S_{i})$ where
$S_{1},\dotsc,S_{m}$ is a partition of the resources. The result by Goemans et
al. implies a polynomial time $O(n^{1/2+\varepsilon})$-approximation
algorithm.

Since then progress on this problem was limited to the linear case, that is,
all $f_{i}$ are linear functions. In particular, a line of research has shown
that there is a polynomial time constant approximation algorithm for linear
valuation functions in the restricted assignment case. This is the special
case where each player is given a set of desired resources $\Gamma_{i}$ and
the individual valuation functions are defined as
$f_{i}(S)=f(S\cap\Gamma_{i})$ for a global linear function $f$. This can also
be interpreted as maximizing $\min_{i}f(S_{i})$ with additional assignment
restrictions, i.e., resources can only be assigned to certain players.

In this paper we make comparable progress for the submodular variant. Namely,
if $f$ is a monotone submodular function, we can in polynomial time compute an
$O(\log\log(n))$-approximate solution.

##  1 Introduction

In the Santa Claus problem (sometimes referred to as Max-Min Fair Allocation)
we are given a set of $n$ players $P$ and a set of $m$ indivisible resources
$R$. In its full generality, each player $i\in P$ has a utility function
$f_{i}:2^{R}\mapsto\mathbb{R}_{\geq 0}$, where $f_{i}(S)$ measures the
happiness of player $i$ if he is assigned the resource set $S$. The goal is to
find a partition of the resources that maximizes the happiness of the least
happy player. Formally, we want to find a partition $\\{S_{i}\\}_{i\in P}$ of
the resources that maximizes

$\min_{i\in P}f_{i}(S_{i}).$

Most of the recent literature on this problem focuses on cases where $f_{i}$
is a linear function for all players $i$. If we assume all valuation functions
are linear, the best approximation algorithm known for this problem, designed
by Chakrabarty, Chuzhoy, and Khanna [4], has an approximation rate of
$n^{\epsilon}$ and runs in time $n^{O(1/\epsilon)}$ for
$\epsilon\in\Omega(\log\log(n)/\log(n))$. On the negative side, it is only
known that computing a $(2-\delta)$-approximation is NP-hard [12]. Apart from
this there has been significant attention on the so-called _restricted
assignment case_. Here the utility functions are defined by one linear
function $f$ and a set of resources $\Gamma_{i}$ for each player $i$.
Intuitively, player $i$ is interested in the resources $\Gamma_{i}$, whereas
the other resources are worthless for him. The individual utility functions
are then implicitly defined by $f_{i}(S)=f(S\cap\Gamma_{i})$. In a seminal
work Bansal and Srividenko [3] provide a
$O(\log\log(m)/\log\log\log(m))$-approximation algorithm for this case. This
was improved by Feige [8] to an $O(1)$-approximation. Further progress on the
constant or the running time was made since then, see e.g. [2, 7, 6, 5, 10, 1,
15].

Let us now move to the non-linear case. Indeed, the problem becomes hopelessly
difficult without any restrictions on the utility functions. Consider the
following reduction from set packing. There are sets of resources
$\\{S_{1},\dotsc,S_{k}\\}$ and all utility functions are equal and defined by
$f_{i}(S)=1$ if $S_{j}\subseteq S$ for some $j$ and $f_{i}(S)=0$ otherwise.
Deciding whether there are $m$ disjoint sets in $S_{1},\dotsc,S_{k}$ (a
classical NP-hard problem) is equivalent to deciding whether the optimum of
the Santa Claus problem is non-zero. In particular, obtaining any bounded
approximation ratio for Santa Claus in this case is NP-hard.

Two naturally arising properties of utility functions are monotonicity and
submodularity, see for example the related submodular welfare problem [11, 17]
where the goal is to maximize $\sum_{i}f_{i}(S_{i})$. A function $f$ is
monotone, if $f(S)\leq f(T)$ for all $S\subseteq T$. It is submodular, if
$f(S\cup\\{a\\})-f(S)\geq f(T\cup\\{a\\})-f(T)$ for all $S\subseteq T$ and
$a\notin T$. The latter is also known as the _diminishing returns_ property in
economics. A standard assumption on monotone submodular functions (used
throughout this work) is that the value on the empty set is zero, i.e.,
$f(\emptyset)=0$. Goemans, Harvey, Iwata, and Mirrokni [9] first considered
the Santa Claus problem with monotone submodular utility functions as an
application of their fundamental result on submodular functions. Together with
the algorithm of [4] it implies an $O(n^{1/2+\epsilon})$-approximation in time
$O(n^{1/\epsilon})$.

In this paper we investigate the restricted assignment case with a monotone
submodular utility function. That is, all utility functions are defined by
$f_{i}(S)=f(S\cap\Gamma_{i})$, where $f$ is a monotone submodular function and
$\Gamma_{i}$ is a subset of resources for each players $i$. Before our work,
the state-of-the-art for this problem was the
$O(n^{1/2+\epsilon})$-approximation algorithm mentioned above, since none of
the previous results for the restricted assignment case with a linear utility
function apply when the utility function becomes monotone submodular.

###  1.1 Overview of results and techniques

Our main result is an approximation algorithm for the submodular Santa Claus
problem in the restricted assignment case.

######  Theorem 1.

There is a randomized polynomial time $O(\log\log(n))$-approximation algorithm
for the restricted assignment case with a monotone submodular utility
function.

Our way to this result is organised as follows. In Section 2, we first reduce
our problem to a hypergraph matching problem (see next paragraph for a formal
definition). We then solve this problem using Lovasz Local Lemma (LLL) in
Section 3. In [3] the authors also reduce to a hypergraph matching problem
which they then solve using LLL, although both parts are substantially
simpler. The higher generality of our utility functions is reflected in the
more general hypergraph matching problem. Namely, our problem is precisely the
weighted variant of the (unweighted) problem in [3]. We will elaborate later
in this section why the previous techniques do not easily extend to the
weighted variant.

#### The hypergraph matching problem.

After the reduction in Section 2 we arrive at the following problem. There is
a hypergraph $\mathcal{H}=(P\cup R,\mathcal{C})$ with hyperedges $\mathcal{C}$
over the vertices $P$ and $R$. We write $m=|P|$ and $n=|R|$. We will refer to
hyperedges as configurations, the vertices in $P$ as players and $R$ as
resources555We note that these do not have to be the same players and
resources as in the Santa Claus problem we reduced from, but $n$ and $m$ do
not increase.. Moreover, a hypergraph is said to be regular if all vertices in
$P$ and $R$ have the same degree, that is, they are contained in the same
number of configurations.

The hypergraph may contain multiple copies of the same configuration. Each
configuration $C\in\mathcal{C}$ contains exactly one vertex in $P$, that is,
$|C\cap P|=1$. Additionally, for each configuration $C\in\mathcal{C}$ the
resources $j\in C$ have weights $w_{j,C}\geq 0$. We emphasize that the same
resource $j$ can be given different weights in two different configurations,
that is, we may have $w_{j,C}\neq w_{j,C^{\prime}}$ for two different
configurations $C,C^{\prime}$.

We require to select for each player $i\in P$ one configuration $C$ that
contains $i$. For each configuration $C$ that was selected we require to
assign a subset of the resources in $C$ which has a total weight of at least
$(1/\alpha)\cdot\sum_{j\in C}w_{j,C}$ to the player in $C$. A resource can
only be assigned to one player. We call such a solution an $\alpha$-relaxed
perfect matching. One seeks to minimize $\alpha$.

We show that every regular hypergraph has an $\alpha$-relaxed perfect matching
for some $\alpha=O(\log\log(n))$ assuming that
$w_{j,C}\leq(1/\alpha)\cdot\sum_{j^{\prime}\in C}w_{j^{\prime},C}$ for all
$j,C$, that is, all weights are small compared to the total weight of the
configuration. Moreover, we can find such a matching in randomized polynomial
time. In the reduction we use this result to round a certain LP relaxation and
$\alpha$ essentially translates to the approximation rate. This result
generalizes that of Bansal and Srividenko on hypergraph matching in the
following way. They proved the same result for unit weights and uniform
hyperedges, that is, $w_{j,C}=1$ for all $j,C$ and all hyperedges have the
same number of resources666In fact they get a slightly better ratio of
$\alpha=O(\log\log(m)/\log\log\log(m))$.. In the next paragraph we briefly go
over the techniques to prove our result for the hypergraph matching problem.

#### Our techniques.

Already the extension from uniform to non-uniform hypergraphs (assuming unit
weights) is highly non-trivial and captures the core difficulty of our result.
Indeed, we show with a (perhaps surprising) reduction, that we can reduce our
weighted hypergraph matching problem to the unweighted (but non-uniform)
version by introducing some bounded dependencies between the choices of the
different players. For sake of brevity we therefore focus in this section on
the unweighted non-uniform variant, that is, we need to assign to each player
a configuration $C$ and at least $|C|/\alpha$ resources in $C$. We show that
for any regular hypergraph there exists such a matching for
$\alpha=O(\log\log(n))$ assuming that all configurations contain at least
$\alpha$ resources and we can find it in randomized polynomial time. Without
the assumption of uniformity the problem becomes significantly more
challenging. To see this, we lay out the techniques of Bansal and Srividenko
that allowed them to solve the problem in the uniform case. We note that for
$\alpha=O(\log(n))$ the statement is easy to prove: We select for each player
$i$ one of the configurations containing $i$ uniformly at random. Then by
standard concentration bounds each resource is contained in at most
$O(\log(n))$ of the selected configurations with high probability. This
implies that there is a fractional assignment of resources to configurations
such that each of the selected configurations $C$ receives
$\lfloor|C|/O(\log(n))\rfloor$ of the resources in $C$. By integrality of the
bipartite matching polytope, there is also an integral assignment with this
property.

To improve to $\alpha=O(\log\log(n))$ in the uniform case, Bansal and
Srividenko proceed as follows. Let $k$ be the size of each configuration.
First they reduce the degree of each player and resource to $O(\log(n))$ using
the argument above, but taking $O(\log(n))$ configurations for each player.
Then they sample uniformly at random $O(n\log(n)/k)$ resources and drop all
others. This is sensible, because they manage to prove the (perhaps
surprising) fact that an $\alpha$-relaxed perfect matching with respect to the
smaller set of resources is still an $O(\alpha)$-relaxed perfect matching with
respect to all resources with high probability (when assigning the dropped
resources to the selected configurations appropriately). Indeed, the smaller
instance is easier to solve: With high probability all configurations have
size $O(\log(n))$ and this greatly reduces the dependencies between the bad
events of the random experiment above (the event that a resource is contained
in too many selected configurations). This allows them to apply Lovász Local
Lemma (LLL) in order to show that with positive probability the experiment
succeeds for $\alpha=O(\log\log(n))$.

It is not obvious how to extend this approach to non-uniform hypergraphs:
Sampling a fixed fraction of the resources will either make the small
configurations empty—which makes it impossible to retain guarantees for the
original instance—or it leaves the big configurations big—which fails to
reduce the dependencies enough to apply LLL. Hence it requires new
sophisticated ideas for non-uniform hypergraphs, which we describe next.

Suppose we are able to find a set $\mathcal{K}\subseteq\mathcal{C}$ of
configurations (one for each player) such that for each $K\in\mathcal{K}$ the
sum of intersections $|K\cap K^{\prime}|$ with smaller configurations
$K^{\prime}\in\mathcal{K}$ is very small, say at most $|K|/2$. Then it is easy
to derive a $2$-relaxed perfect matching: We iterate over all
$K\in\mathcal{K}$ from large to small and reassign all resources to $K$
(possibly stealing them from the configuration that previously had them). In
this process every configuration gets stolen at most $|K|/2$ of its resources,
in particular, it keeps the other half. However, it is non-trivial to obtain a
property like the one mentioned above. If we take a random configuration for
each player, the dependencies of the intersections are too complex. To avoid
this we invoke an advanced variant of the sampling approach where we construct
not only one set of resources, but a hierarchy of resource sets
$R_{0}\supseteq\cdots\supseteq R_{d}$ by repeatedly dropping a fraction of
resources from the previous set. We then formulate bad events based on the
intersections of a configuration $C$ with smaller configurations $C^{\prime}$,
but we write it only considering a resource set $R_{k}$ of convenient
granularity (chosen based on the size of $C^{\prime}$). In this way we
formulate a number of bad events using various sets $R_{k}$. This succeeds in
reducing the dependencies enough to apply LLL. Unfortunately, even with this
new way of defining bad events, the guarantee that for each $K\in\mathcal{K}$
the sum of intersections $|K\cap K^{\prime}|$ with smaller configurations
$K^{\prime}\in\mathcal{K}$ is at most $|K|/2$ is still too much to ask. We can
only prove some weaker property which makes it more difficult to reconstruct a
good solution from it. The reconstruction still starts from the biggest
configurations and iterates to finish by including the smallest configurations
but it requires a delicate induction where at each step, both the resource set
expands and some new small configurations that were not considered before come
into play.

#### Additional implications of non-uniform hypergraph matchings to the Santa
Claus problem.

We believe this hypergraph matching problem is interesting in its own right.
Our last contribution is to show that finding good matchings in unweighted
hypergraphs with fewer assumptions than ours would have important applications
for the Santa Claus problem with linear utility functions. We recall that
here, each player $i$ has its own utility function $f_{i}$ that can be any
linear function. In this case, the best approximation algorithm is due to
Chakrabarty, Chuzhoy, and Khanna [4] who gave a
$O(n^{\epsilon})$-approximation running in time $O(n^{1/\epsilon})$. In
particular, no sub-polynomial approximation running in polynomial time is
known. Consider as before $\mathcal{H}=(P\cup R,\mathcal{C})$ a non-uniform
hypergraph with unit weights ($w_{j,C}=1$ for all $j,C$ such that $j\in C$).
Finding the smallest $\alpha$ (or an approximation of it) such that there
exists an $\alpha$-relaxed perfect matching in $\mathcal{H}$ is already a very
non-trivial question to solve in polynomial time.

We show, via a reduction, that a $c$-approximation for this problem would
yield a $O((c\log^{*}(n))^{2})$-approximation for the Santa Claus problem with
arbitrary linear utility functions. In particular, any sub-polynomial
approximation for this problem would significantly improve the state-of-the-
art777We mention that our result on relaxed matchings in Section 3 does not
imply an $O(\log\log(n))$-approximation for this problem since we make
additional assumptions on the regularity of the hypergraph or the size of
hyperedges.. All the details of this last result can be found in Section 4.

#### A remark on local search techniques.

We focus here on an extension of the LLL technique of Bansal and Srividenko.
However, another technique proved itself very successful for the Santa Claus
problem in the restricted assignment case with a linear utility function. This
is a local search technique discovered by Asadpour, Feige, and Saberi [1] who
used it to give a non-constructive proof that the integrality gap of the
configuration LP of Bansal and Srividenko is at most $4$. One can wonder if
this technique could also be extended to the submodular case as we did with
LLL. Unfortunately, this seems problematic as the local search arguments
heavily rely on amortizing different volumes of configurations (i.e., the sum
of their resources’ weights or the number of resources in the unweighted
case). Amortizing the volumes of configurations works well, if each
configuration has the same volume, which is the case for the problem derived
from linear valuation functions, but not the one derived from submodular
functions. If the volumes differ then these amortization arguments break and
the authors of this paper believe this is a fundamental problem for
generalizing those arguments.

##  2 Reduction to hypergraph matching problem

In this section we give a reduction of the restricted submodular Santa Claus
problem to the hypergraph matching problem. As a starting point we solve the
configuration LP, a linear programming relaxation of our problem. The LP is
constructed using a parameter $T$ which denotes the value of its solution. The
goal is to find the maximal $T$ such that the LP is feasible. In the LP we
have a variable $x_{i,C}$ for every player $i\in P$ and every configuration
$C\in\mathcal{C}(i,T)$. The configurations $\mathcal{C}(i,T)$ are defined as
the sets of resources $C\subseteq\Gamma_{i}$ such that $f(C)\geq T$. We
require every player $i\in P$ to have at least one configuration and every
resource $j\in R$ to be contained in at most one configuration.

$\displaystyle\sum_{C\in\mathcal{C}(i,T)}$ $\displaystyle x_{i,C}\geq
1\quad\text{ for all }i\in P$ $\displaystyle\sum_{i\in
P}\sum_{C\in\mathcal{C}(i,T):j\in C}$ $\displaystyle x_{i,C}\leq 1\quad\text{
for all }j\in R$ $\displaystyle x_{i,C}\geq 0\quad\text{ for all }i\in
P,C\in\mathcal{C}(i,T)$

Since this linear program has exponentially many variables, we cannot directly
solve it in polynomial time. We will give a polynomial time constant
approximation for it via its dual. This is similar to the linear variant in
[3], but requires some more work. In their case they can reduce the problem to
one where the separation problem of the dual can be solved in polynomial time.
In our case even the separation problem can only be approximated.
Nevertheless, this is sufficient to approximate the linear program in
polynomial time.

######  Theorem 2.

The configuration LP of the restricted submodular Santa Claus problem can be
approximated within a factor of $(1-1/e)/2$ in polynomial time.

We defer the proof of this theorem to Appendix B. Given a solution $x^{*}$ of
the configuration LP we want to arrive at the hypergraph matching problem from
the introduction such that an $\alpha$-relaxed perfect matching of that
problem corresponds to an $O(\alpha)$-approximate solution of the restricted
submodular Santa Claus problem. Let $T^{*}$ denote the value of the solution
$x^{*}$. We will define a resource $j\in R$ as _fat_ if

$f(\\{j\\})\geq\frac{T^{*}}{100\alpha}.$

Resources that are not fat are called _thin_. We call a configuration
$C\in\mathcal{C}(i,T)$ thin, if it contains only thin resources and denote by
$\mathcal{C}_{t}(i,T)\subseteq\mathcal{C}(i,T)$ the set of thin
configurations. Intuitively in order to obtain an $O(\alpha)$-approximate
solution, it suffices to give each player $i$ either one fat resource
$j\in\Gamma_{i}$ or a thin configuration
$C\in\mathcal{C}_{t}(i,T^{*}/O(\alpha))$. For our next step towards the
hypergraph problem we use a technique borrowed from Bansal and Srividenko [3].
This technique allows us to simplify the structure of the problem
significantly using the solution of the configuration LP. Namely, one can find
a partition of the players into clusters such that we only need to cover one
player from each cluster with thin resources. All other players can then be
covered by fat resources. Informally speaking, the following lemma is proved
by sampling configurations randomly according to a distribution derived in a
non-trivial way from the configuration LP.

######  Lemma 3.

Let $\ell\geq 12\log(n)$. Given a solution of value $T^{*}$ for the
configuration LP in randomized polynomial time we can find a partition of the
players into clusters $K_{1}\cup\cdots\cup K_{k}\cup Q=P$ and multisets of
configurations $\mathcal{C}_{h}\subseteq\bigcup_{i\in
K_{h}}\mathcal{C}_{T}(i,T^{*}/5)$, $h=1,\dotsc,k$, such that

  1. 1.

$|\mathcal{C}_{h}|=\ell$ for all $h=1,\dotsc,k$ and

  2. 2.

Each small resource appears in at most $\ell$ configurations of
$\bigcup_{h}\mathcal{C}_{h}$.

  3. 3.

given any $i_{1}\in K_{1},i_{2}\in K_{2},\dotsc,i_{k}\in K_{k}$ there is a
matching of fat resources to players $P\setminus\\{i_{1},\dotsc,i_{k}\\}$ such
that each of these players $i$ gets a unique fat resource $j\in\Gamma_{i}$.

The role of the players $Q$ in the lemma above is that each one of them gets a
fat resource for certain. The proof follows closely that in [3]. For
completeness we include it in Appendix B. We are now ready to define the
hypergraph matching instance. The vertices of our hypergraph are the clusters
$K_{1},\dotsc,K_{k}$ and the thin resources. Let
$\mathcal{C}_{1},\dotsc,\mathcal{C}_{k}$ be the multisets of configurations as
in Lemma 3. For each $K_{h}$ and $C\in\mathcal{C}_{h}$ there is a hyperedge
containing $K_{h}$ and all resources in $C$. Let
$\\{j_{1},\dotsc,j_{\ell}\\}=C$ ordered arbitrarily, but consistently. Then we
define the weights as normalized marginal gains of resources if they are taken
in this order, that is,

$w_{j_{i},C}=\frac{5}{T^{*}}f(\\{j_{i}\\}\mid\\{j_{1},\dotsc,j_{i-1}\\})=\frac{5}{T^{*}}(f(\\{j_{1},\dotsc,j_{i-1},j_{i}\\})-f(\\{j_{1},\dotsc,j_{i-1}\\})).$

This implies that $\sum_{j\in C}w_{j,C}\geq 5f(C)/T^{*}\geq 1$ for each
$C\in\mathcal{C}_{h}$, $h=1,\dotsc,k$.

######  Lemma 4.

Given an $\alpha$-relaxed perfect matching to the instance as described by the
reduction, one can find in polynomial time an $O(\alpha)$-approximation to the
instance of restricted submodular Santa Claus.

###### Proof.

The $\alpha$-relaxed perfect matching implies that cluster $K_{h}$ gets some
small resources $C^{\prime}$ where $C^{\prime}\subseteq C$ for some
$C\in\mathcal{C}_{h}$ and $\sum_{j\in C^{\prime}}w_{j,C}\geq 1/\alpha$. By
submodularity we have that $f(C^{\prime})\geq T^{*}/(5\alpha)$. Therefore we
can satisfy one player in each cluster using thin resources and by Lemma 23
all others using fat resources. ∎

The proof above is the most critical place in the paper where we make use of
the submodularity of the valuation function $f$. We note that since all
resources considered are thin resources we have, by submodularity of $f$, the
assumption that

$w_{j,C}\leq\frac{5}{T^{*}}f(\\{j\\})\leq\frac{5}{T^{*}}\frac{T^{*}}{100\alpha}\leq\frac{5}{100\alpha}\sum_{j\in
C}w_{j,C}$

for all $j,C$ such that $j\in C$. This means that the weights are all small
enough, as promised in introduction. From now on, we will assume that
$\sum_{j\in C}w_{j,C}=1$ for all configurations $C$. This is w.l.o.g. since we
can just rescale the weights inside each configuration. This does not hurt the
property that all weights are small enough.

###  2.1 Reduction to unweighted hypergraph matching

Before proceeding to the solution of this hypergraph matching problem, we
first give a reduction to an unweighted variant of the problem. We will then
solve this unweighted variant in the next section. First, we note that we can
assume that all the weights $w_{j,C}$ are powers of $2$ by standard rounding
arguments. This only loses a constant factor in the approximation rate.
Second, we can assume that inside each configuration $C$, each resource has a
weight that is at least a $1/(2n)$. Formally, we can assume that

$\min_{j\in C}w_{j,C}\geq 1/(2n)$

for all $C\in\mathcal{C}$. If this is not the case for some $C\in\mathcal{C}$,
simply delete from $C$ all the resources that have a weight less than
$1/(2n)$. By doing this, the total weight of $C$ is only decreased by a factor
$1/2$ since it looses in total at most a weight of

$n\cdot\frac{1}{2n}=\frac{1}{2}.$

(Recall that we rescaled the weights so that $\sum_{j\in C}w_{j,C}=1$).

Hence after these two operations, an $\alpha$-relaxed perfect matching in the
new hypergraph is still an $O(\alpha)$-relaxed perfect matching in the
original hypergraph. From there we reduce to an unweighted variant of the
matching problem. Note that each configuration contains resources of at most
$\log(n)$ different possible weights (powers of $2$ from $1/(2n)$ to
$1/\alpha$). We create the following new unweighted hypergraph
$\mathcal{H}^{\prime}=(P^{\prime}\cup R,\mathcal{C}^{\prime})$. The resource
set $R$ remains unchanged. For each player $i\in P$, we create $\log(n)$
players, which later correspond each to a distinct weight. We will say that
the players obtained from duplicating the original player form a group. For
every configuration $C$ containing player $i$ in the hypergraph $\mathcal{H}$,
we add a set $\mathcal{S}_{C}=\\{C_{1},\ldots,C_{s},\ldots,C_{\log(n)}\\}$ of
configurations in $\mathcal{H}^{\prime}$. $C_{s}$ contains player $i_{s}$ and
all resources that are given a weight $2^{-(s+1)}$ in $C$. In this new
hypergraph, the resources are not weighted. Note that if the hypergraph
$\mathcal{H}$ is regular then $\mathcal{H}^{\prime}$ is regular as well.

Additionally, for a group of player and a set of $\log(n)$ configurations (one
for each player in the group), we say that this set of configurations is
consistent if all the configurations selected are obtained from the same
configuration in the original hypergraph $\mathcal{H}$ (i.e. the selected
configurations all belong to $\mathcal{S}_{C}$ for some $C$ in $\mathcal{H}$).

Formally, we focus of the following problem. Given the regular hypergraph
$\mathcal{H}^{\prime}$, we want to select, for each group of $\log(n)$
players, a consistent set of configurations
$C_{1},\ldots,C_{s},\ldots,C_{\log(n)}$ and assign to each player $i_{s}$ a
subset of the resources in the corresponding configuration $C_{s}$ so that
$i_{s}$ is assigned at least $\left\lfloor|C_{s}|/\alpha\right\rfloor$
resources. No resource can be assigned to more than one player. We refer to
this assignment as a consistent $\alpha$-relaxed perfect matching. Note that
in the case where $|C_{s}|$ is small (e.g. of constant size) we are not
required to assign any resource to player $i_{s}$.

######  Lemma 5.

A consistent $\alpha$-relaxed matching in $\mathcal{H}^{\prime}$ induces a
$O(\alpha)$-relaxed matching in $\mathcal{H}$.

###### Proof.

Let us consider a group of $\log(n)$ players
$i_{1},\ldots,i_{s},\ldots,i_{\log(n)}$ in $\mathcal{H}^{\prime}$
corresponding to a player $i$ in $\mathcal{H}$. These players are assigned a
consistent set of configurations $C_{1},\ldots,C_{s},\ldots,C_{\log(n)}$ that
correspond to a partition of a configuration in $\mathcal{H}$. Moreover, each
player $i_{s}$ is assigned $\left\lfloor|C_{s}|/\alpha\right\rfloor$ resources
from $C_{s}$. We have two cases. If $|C_{s}|\geq\alpha$ then we have that
$i_{s}$ is assigned at least

$\left\lfloor|C_{s}|/\alpha\right\rfloor\geq|C_{s}|/(2\alpha)$

resources from $C_{s}$. On the other hand, if
$\left\lfloor|C_{s}|/\alpha\right\rfloor=0$ then the player $i_{s}$ might not
be assigned anything. However, we claim that that the configurations $C_{s}$
of cardinality less than $\alpha$ can represent at most a $1/5$ fraction of
the total weight of the configuration $C$ in the original weighted hypergraph.
To see this note that the total weight they represent is upper bounded by

$\alpha\left(\sum_{k=\log(100\alpha/5)}^{\infty}\frac{1}{2^{k}}\right)=\alpha\left(\frac{5}{100\alpha}\sum_{k=0}^{\infty}\frac{1}{2^{k}}\right)\leq\frac{10}{100}=\frac{1}{10}\sum_{j\in
C}w_{j,C}.$

Hence, the consistent $\alpha$-relaxed matching in $\mathcal{H}^{\prime}$
induces in a straightforward way a matching in $\mathcal{H}$ where every
player gets at least a fraction $1/(2\alpha)\cdot(1-1/10)\geq 1/(3\alpha)$ of
the total weight of the appropriate configuration. This means that the
consistent $\alpha$-relaxed perfect matching in $\mathcal{H}^{\prime}$ is
indeed a $(3\alpha)$-relaxed perfect matching in $\mathcal{H}$. ∎

##  3 Matchings in regular hypergraphs

In this section we solve the hypergraph matching problem we arrived to in the
previous section. For convenience, we give a self contained definition of the
problem before formulating and proving our result.

#### Input:

We are given $\mathcal{H}=(P\cup R,\mathcal{C})$ a hypergraph with hyperedges
$\mathcal{C}$ over the vertices $P$ (players) and $R$ (resources) with $m=|P|$
and $n=|R|$. As in previous sections, we will refer to hyperedges as
configurations. Each configuration $C\in\mathcal{C}$ contains exactly one
vertex in $P$, that is, $|C\cap P|=1$. The set of players is partitioned into
groups of size at most $\log(n)$, we will use $A$ to denote a group. These
groups are disjoint and contain all players. Finally there exists an integer
$\ell$ such that for each group $A$ there are $\ell$ consistent sets of
configurations. A consistent set of configurations for a group $A$ is a set of
$|A|$ configurations such that all players in the group appear in exactly one
of these configurations. We will denote by $\mathcal{S}_{A}$ such a set and
for a player $i\in A$, we will denote by $\mathcal{S}_{A}^{(i)}$ the unique
configuration in $\mathcal{S}_{A}$ containing $i$. Finally, no resource
appears in more than $\ell$ configurations. We say that the hypergraph is
regular (although some resources may appear in less than $\ell$
configurations).

#### Output:

We wish to select a matching that covers all players in $P$. More precisely,
for each group $A$ we want to select a consistent set of configurations
(denoted by $\\{\mathcal{S}_{A}^{(i)}\\}_{i\in A}$). Then for each player
$i\in A$, we wish to assign a subset of the resources in
$\mathcal{S}_{A}^{(i)}$ to the player $i$ such that:

  1. 1.

No resource is assigned to more than one player in total.

  2. 2.

For any group $A$ and any player $i\in A$, player $i$ is assigned at least

$\left\lfloor\frac{\mathcal{S}_{A}^{(i)}}{\alpha}\right\rfloor$

resources from $\mathcal{S}_{A}^{(i)}$.

We call this a consistent $\alpha$-relaxed perfect matching. Our goal in this
section will be to prove the following theorem.

######  Theorem 6.

Let $\mathcal{H}=(P\cup R,\mathcal{C})$ be a regular (non-uniform) hypergraph
where the set of players is partitioned into groups of size at most $\log(n)$.
Then we can, in randomized polynomial time, compute a consistent
$\alpha$-relaxed perfect matching for $\alpha=O(\log\log(n))$.

We note that Theorem 6 together with the reduction from the previous section
will prove our main result (Theorem 1) stated in introduction.

###  3.1 Overview and notations

To prove Theorem 6, we introduce the following notations. Let
$\ell\in\mathbb{N}$ be the regularity parameter as described in the problem
input (i.e. each group has $\ell$ consistent sets and each resource appears in
no more than $\ell$ configurations). As we proved in Lemma 3 we can assume
with standard sampling arguments that $\ell=300.000\log^{3}(n)$ at a constant
loss. If this is not the case because we might want to solve the hypergraph
matching problem by itself (i.e. not obtained by the reduction in Section 2),
the proof of Lemma 3 can be repeated in a very similar way here.

For a configuration $C$, its size will be defined as $|C\cap R|$ (i.e. its
cardinality over the resource set). For each player $i$, we denote by
$\mathcal{C}_{i}$ the set of configurations that contain $i$. We now group the
configurations in $\mathcal{C}_{i}$ by size: We denote by
$\mathcal{C}_{i}^{(0)}$ the configurations of size in $[0,\ell^{4})$ and for
$k\geq 1$ we write $\mathcal{C}_{i}^{(k)}$ for the configurations of size in
$[\ell^{k+3},\ell^{k+4})$. Moreover, define
$\mathcal{C}^{(k)}=\bigcup_{i}\mathcal{C}_{i}^{(k)}$ and $\mathcal{C}^{(\geq
k)}=\bigcup_{h\geq k}\mathcal{C}^{(h)}$. Let $d$ be the smallest number such
that $\mathcal{C}^{(\geq d)}$ is empty. Note that $d\leq\log(n)/\log(\ell)$.

Now consider the following random process.

######  Random Experiment 7.

We construct a nested sequence of resource sets $R=R_{0}\supseteq
R_{1}\supseteq\ldots\supseteq R_{d}$ as follows. Each $R_{k}$ is obtained from
$R_{k-1}$ by deleting every resource in $R_{k-1}$ independently with
probability $(\ell-1)/\ell$.

In expectation only a $1/\ell$ fraction of resources in $R_{k-1}$ survives in
$R_{k}$. Also notice that for $C\in\mathcal{C}^{(k)}$ we have that
$\mathbb{E}[|R_{k}\cap C|]=\mathrm{poly}(\ell)$.

The proof of Theorem 6 is organized as follows. In Section 3.2, we give some
properties of the resource sets constructed by Random Experiment 7 that hold
with high probability. Then in Section 3.3, we show that we can find a single
consistent set of configurations for each group of players such that for each
configuration selected, its intersection with smaller selected configurations
is bounded if we restrict the resource set to an appropriate $R_{k}$.
Restricting the resource set is important to bound the dependencies of bad
events in order to apply Lovasz Local Lemma. Finally in Section 3.4, we
demonstrate how these configurations allows us to reconstruct a consistent
$\alpha$-relaxed perfect matching for an appropriate assignment of resources
to configurations.

###  3.2 Properties of resource sets

In this subsection, we give a precise statement of the key properties that we
need from Random Experiment 7. The first two lemmas have a straight-forward
proof. The last one is a generalization of an argument used by Bansal and
Srividenko [3]. Since the proof is more technical and tedious, we also defer
it to Appendix C along with the proof of the first two statements.

We start with the first property which bounds the size of the configurations
when restricted to some $R_{k}$. This property is useful to reduce the
dependencies while applying LLL later.

######  Lemma 8.

Consider Random Experiment 7 with $\ell\geq 300.000\log^{3}(n)$. For any
$k\geq 0$ and any $C\in\mathcal{C}^{(\geq k)}$ we have

$\frac{1}{2}\ell^{-k}|C|\leq|R_{k}\cap C|\leq\frac{3}{2}\ell^{-k}|C|$

with probability at least $1-1/n^{10}$.

The next property expresses that for any configuration the sum of
intersections with configurations of a particular size does not deviate much
from its expectation. In particular, for any configuration $C$, the sum of
it’s intersections with other configurations is at most $|C|\ell$ as each
resource is in atmost $\ell$ configurations. By the lemma stated below, we
recover this up to a multiplicative constant factor when we consider the
appropriately weighted sum of the intersection of $C$ with other
configurations $C^{\prime}$ of smaller sizes where each configuration
$C^{\prime}\in\mathcal{C}^{(k)}$ is restricted to the resource set $R_{k}$.

######  Lemma 9.

Consider Random Experiment 7 with $\ell\geq 300.000\log^{3}(n)$. For any
$k\geq 0$ and any $C\in\mathcal{C}^{(\geq k)}$ we have

$\sum_{C^{\prime}\in\mathcal{C}^{(k)}}|C^{\prime}\cap C\cap
R_{k}|\leq\frac{10}{\ell^{k}}\left(|C|+\sum_{C^{\prime}\in\mathcal{C}^{(k)}}|C^{\prime}\cap
C|\right)$

with probability at least $1-1/n^{10}$.

We now define the notion of _good_ solutions which is helpful in stating our
last property. Let $\mathcal{F}$ be a set of configurations,
$\alpha:\mathcal{F}\rightarrow\mathbb{N}$, $\gamma\in\mathbb{N}$, and
$R^{\prime}\subseteq R$. We say that an assignment of $R^{\prime}$ to
$\mathcal{F}$ is $(\alpha,\gamma)$-good if every configuration
$C\in\mathcal{F}$ receives at least $\alpha(C)$ resources of $C\cap
R^{\prime}$ and if no resource in $R^{\prime}$ is assigned more than $\gamma$
times in total.

Below we obtain that given a $(\alpha,\gamma)$-good solution with respect to
resource set $R_{k+1}$, one can construct an almost
$(\ell\cdot\alpha,\gamma)$-good solution with respect to the bigger resource
set $R_{k}$. Informally, starting from a good solution with respect to the
final resource set and iteratively applying this lemma would give us a good
solution with respect to our complete set of resources.

######  Lemma 10.

Consider Random Experiment 7 with $\ell\geq 300.000\log^{3}(n)$. Fix $k\geq
0$. Conditioned on the event that the bounds in Lemma 8 hold for $k$, then
with probability at least $1-1/n^{10}$ the following holds for all
$\mathcal{F}\subseteq\mathcal{C}^{(\geq k+1)}$,
$\alpha:\mathcal{F}\rightarrow\mathbb{N}$, and $\gamma\in\mathbb{N}$ such that
$\ell^{3}/1000\leq\alpha(C)\leq n$ for all $C\in\mathcal{F}$ and
$\gamma\in\\{1,\dotsc,\ell\\}$: If there is a $(\alpha,\gamma)$-good
assignment of $R_{k+1}$ to $\mathcal{F}$, then there is a
$(\alpha^{\prime},\gamma)$-good assignment of $R_{k}$ to $\mathcal{F}$ where

$\alpha^{\prime}(C)\geq\ell\left(1-\frac{1}{\log(n)}\right)\alpha(C)$

for all $C\in\mathcal{F}$. Moreover, this assignment can be found in
polynomial time.

Given the lemmata above, by a simple union bound one gets that all the
properties of resource sets hold.

###  3.3 Selection of configurations

In this subsection, we give a random process that selects one consistent set
of configurations for each group of players such that the intersection of the
selected configurations with smaller configurations is bounded when considered
on appropriate sets $R_{k}$. We will denote $\mathcal{S}_{A}$ the selected
consistent set for group $A$ and for ease of notation we will denote
$K_{i}=\mathcal{S}_{A}^{(i)}$ the selected configuration for player $i\in A$.
For any integer $k$, we write $\mathcal{K}^{(k)}_{i}=\\{K_{i}\\}$ if
$K_{i}\in\mathcal{C}^{(k)}_{i}$ and $\mathcal{K}^{(k)}_{i}=\emptyset$
otherwise. As for the configuration set, we will also denote
$\mathcal{K}^{(k)}=\bigcup_{i}\mathcal{K}^{(k)}_{i}$ and
$\mathcal{K}=\bigcup_{k}\mathcal{K}^{(k)}$. The following lemma describes what
are the properties we want to have while selecting the configurations. For
better clarity we also recall what the properties of the sets
$R_{0},\dotsc,R_{d}$ that we need are. These hold with high probability by the
lemmata of the previous section.

######  Lemma 11.

Let $R=R_{0}\supseteq\dotsc\supseteq R_{d}$ be sets of fewer and fewer
resources. Assume that for each $k$ and $C\in\mathcal{C}_{i}^{(k)}$ we have

$1/2\cdot\ell^{k-h}\leq|C\cap R_{h}|\leq
3/2\cdot\ell^{-h}|C|<3/2\cdot\ell^{k-h+4}$

for all $h=0,\dotsc,k$. Then there exists a selection of one consistent set
$\mathcal{S}_{A}$ for each group $A$ such for all $k=0,\dotsc,d$,
$C\in\mathcal{C}^{(k)}$ and $j=0,\dotsc,k$ then we have

$\sum_{j\leq h\leq k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h}|K\cap C\cap
R_{h}|\leq\frac{1}{\ell}\sum_{j\leq h\leq
k}\sum_{C^{\prime}\in\mathcal{C}^{(h)}}\ell^{h}|C^{\prime}\cap C\cap
R_{h}|+1000\frac{d+\ell}{\ell}\log(\ell)|C|.$

Moreover, this selection of consistent sets can be found in polynomial time.

Before we prove this lemma, we give an intuition of the statement. Consider
the sets $R_{1},\dotsc,R_{d}$ constructed as in Random Experiment 7. Then for
$C^{\prime}\in\mathcal{C}^{(h)}$ we have $\mathbb{E}[\ell^{h}|C^{\prime}\cap
C\cap R_{h}|]=|C^{\prime}\cap C|$. Hence

$\sum_{h\leq k}\sum_{K\in\mathcal{K}^{(h)}}|K\cap C|=\mathbb{E}[\sum_{h\leq
k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h}|K\cap C\cap R_{h}|]$

Similarly for the right-hand side we have

$\mathbb{E}[\frac{1}{\ell}\sum_{j\leq h\leq
k}\sum_{C^{\prime}\in\mathcal{C}^{(h)}}\ell^{h}|C^{\prime}\cap C\cap
R_{h}|+O(\frac{d+\ell}{\ell}\log(\ell)|C|)]\\\
=\frac{1}{\ell}\underbrace{\sum_{j\leq h\leq
k}\sum_{C^{\prime}\in\mathcal{C}^{(h)}}|C^{\prime}\cap
C|}_{\leq\ell|C|}+O\left(\frac{d+\ell}{\ell}\log(\ell)|C|\right)=O\left(\frac{d+\ell}{\ell}\log(\ell)|C|\right).$

Hence the lemma says that each resource in $C$ is roughly covered
$O((d+\ell)/\ell\cdot\log(\ell))$ times by smaller configurations.

We now proceed to prove the lemma by performing the following random
experiment and by Lovasz Local Lemma show that there is a positive probability
of success.

######  Random Experiment 12.

For each group $A$, select one consistent set $\mathcal{S}_{A}$ uniformly at
random. Then for each player $i\in A$ set
$K_{i}=\mathcal{\mathcal{S}}_{A}^{(i)}$.

For all $h=0,\dotsc,d$ and $i\in P$ we define the random variable

$X^{(h)}_{i,C}=\sum_{K\in\mathcal{K}^{(h)}_{i}}|K\cap C\cap
R_{h}|\leq\min\\{3/2\cdot\ell^{4},|C\cap R_{h}|\\}.$

Let $X^{(h)}_{C}=\sum_{i=1}^{m}X^{(h)}_{i,C}$. Then

$\mathbb{E}[X^{(h)}_{C}]\leq\frac{1}{\ell}\sum_{C^{\prime}\in\mathcal{C}^{(h)}}|C^{\prime}\cap
C\cap R_{h}|\leq|C\cap R_{h}|.$

We define a set of bad events. As we will show later, if none of them occur,
the properties from the premise hold. For each $k$, $C\in\mathcal{C}^{(k)}$,
and $h\leq k$ let $B_{C}^{(h)}$ be the event that

$X_{C}^{(h)}\geq\begin{cases}\mathbb{E}[X_{C}^{(h)}]+63|C\cap
R_{h}|\log(\ell)&\text{ if $k-5\leq h\leq k$},\\\
\mathbb{E}[X_{C}^{(h)}]+135|C\cap R_{h}|\log(\ell)\cdot\ell^{-1}&\text{ if
$h\leq k-6$}.\end{cases}$

There is an intuitive reason as to why we define these two different bad
events. In the case $h\leq k-6$, we are counting how many times $C$ is
intersected by configurations that are much smaller than $C$. Hence the size
of this intersection can be written as a sum of independent random variables
of value at most $O(\ell^{4})$ which is much smaller than the total size of
the configuration $|C\cap R_{h}|$. Since the random variables are in a much
smaller range, Chernoff bounds give much better concentration guarantees and
we can afford a very small deviation from the expectation. In the other case,
we do not have this property hence we need a bigger deviation to maintain a
sufficiently low probability of failure. However, this does not hurt the
statement of Lemma 11 since we sum this bigger deviation only a constant
number of times. With this intuition in mind, we claim the following.

######  Claim 13.

For each $k$, $C\in\mathcal{C}^{(k)}$, and $h\leq k$ we have

$\mathbb{P}[B_{C}^{(h)}]\leq\exp\left(-2\frac{|C\cap
R_{h}|}{\ell^{9}}-18\log(\ell)\right).$

###### Proof.

Consider first the case that $h\geq k-5$. By a Chernoff bound (see Proposition
22) with

$\delta=63\frac{|C\cap R_{h}|\log(\ell)}{\mathbb{E}[X_{C}^{(h)}]}\geq 1$

we get

$\mathbb{P}[B_{C}^{(h)}]\leq\exp\bigg{(}-\frac{\delta\mathbb{E}[X^{(h)}_{C}]}{3|C\cap
R_{h}|}\bigg{)}\leq\exp(-21\log(\ell)))\leq\exp\bigg{(}-2\underbrace{\frac{|C\cap
R_{h}|}{\ell^{9}}}_{\leq 3/2}-18\log(\ell)\bigg{)}.$

Now consider $h\leq k-6$. We apply again a Chernoff bound with

$\delta=135\frac{|C\cap
R_{h}|\log(\ell)}{\ell\mathbb{E}[X_{C}^{(h)}]}\geq\frac{1}{\ell}.$

This implies

$\mathbb{P}[B_{C}^{(h)}]\leq\exp\left(-\frac{\min\\{\delta,\delta^{2}\\}\mathbb{E}[X^{(h)}_{C}]}{3\cdot
3/2\cdot\ell^{4}}\right)\leq\exp\left(-30\frac{|C\cap
R_{h}|\log(\ell)}{\ell^{6}}\right)\\\ \leq\exp\left(-2\frac{|C\cap
R_{h}|}{\ell^{9}}-18\log(\ell)\right).\qed$

######  Proposition 14 (Lovasz Local Lemma (LLL)).

Let $B_{1},\dotsc,B_{t}$ be bad events, and let
$G=(\\{B_{1},\dotsc,B_{t}\\},E)$ be a dependency graph for them, in which for
every $i$, event $B_{i}$ is mutually independent of all events $B_{j}$ for
which $(B_{i},B_{j})\notin E$. Let $x_{i}$ for $1\leq i\leq t$ be such that
$0<x(B_{i})<1$ and $\mathbb{P}[B_{i}]\leq x(B_{i})\prod_{(B_{i},B_{j})\in
E}(1-x(B_{j}))$. Then with positive probability no event $B_{i}$ holds.

Let $k\in\\{0,\dotsc,d\\}$, $C\in\mathcal{C}^{(k)}$ and $h\leq k$. For event
$B_{C}^{(h)}$ we set

$x(B_{C}^{(h)})=\exp(-|C\cap R_{h}|/\ell^{9}-18\log(\ell)).$

We now analyze the dependencies of $B_{C}^{(h)}$. The event depends only on
random variables $\mathcal{S}_{A}$ for groups $A$ that contain at least one
player $i$ that has a configuration in $\mathcal{C}^{(h)}_{i}$ which overlaps
with $C\cap R_{h}$. The number of such configurations (in particular, of such
groups) is at most $\ell|C\cap R_{h}|$ since the hypergraph is regular.

In each of these groups, we count at most $\log(n)$ players, each having
$\ell$ configurations hence in total at most $\ell\cdot\log(n)$
configurations.

Each configuration $C^{\prime}\in\mathcal{C}^{(h^{\prime})}$ can only
influence those events $B^{(h^{\prime})}_{C^{\prime\prime}}$ where
$C^{\prime}\cap C^{\prime\prime}\cap R_{h^{\prime}}\neq\emptyset$. Since
$|C^{\prime}\cap R_{h^{\prime}}|\leq 3/2\cdot\ell^{4}$ and since each resource
appears in at most $\ell$ configurations, we see that each configuration can
influence at most $3/2\cdot\ell^{5}$ events.

Putting everything together, we see that the bad event $B_{C}^{(h)}$ is
independent of all but at most

$(\ell|C\cap
R_{h}|)\cdot(\ell\cdot\log(n))\cdot(3/2\cdot\ell^{5})=3/2\cdot\ell^{7}\cdot\log(n)|C\cap
R_{h}|\leq|C\cap R_{h}|\ell^{8}$

other bad events.

We can now verify the condition for Proposition 14 by calculating

$\displaystyle x(B_{C}^{(h)})$
$\displaystyle\prod_{(B_{C}^{(h)},B_{C^{\prime}}^{(h^{\prime})})\in
E}(1-x(B_{C^{\prime}}^{(h^{\prime})}))$ $\displaystyle\geq\exp(-|C\cap
R_{h}|/\ell^{9}-18\log(\ell))\cdot(1-\ell^{-18})^{|C\cap R_{h}|\ell^{8}}$
$\displaystyle\geq\exp(-|C\cap R_{h}|/\ell^{9}-18\log(\ell))\cdot\exp(-|C\cap
R_{h}|/\ell^{9})$ $\displaystyle\geq\exp(-2|C\cap
R_{h}|/\ell^{9}-18\log(\ell))\geq\mathbb{P}[B^{(h)}_{C}].$

By LLL we have that with positive probability none of the bad events happen.
Let $k\in\\{0,\dotsc,d\\}$ and $C\in\mathcal{C}^{(k)}$. Then for $k-5\leq
h\leq k$ we have

$\ell^{h}X^{(h)}_{C}\leq\ell^{h}\mathbb{E}[X_{C}^{(h)}]+63\ell^{h}|C\cap
R_{h}|\log(\ell)\leq\ell^{h}\mathbb{E}[X_{C}^{(h)}]+95|C|\log(\ell).$

Moreover, for $h\leq k-6$ it holds that

$\ell^{h}X^{(h)}_{C}\leq\ell^{h}\mathbb{E}[X_{C}^{(h)}]+135\ell^{h-1}|C\cap
R_{h}|\log(\ell)\leq\ell^{h}\mathbb{E}[X_{C}^{(h)}]+203|C|\log(\ell)\cdot\ell^{-1}.$

We conclude that, for any $0\leq j\leq k$,

$\displaystyle\sum_{j\leq h\leq k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h}|K\cap
C\cap R_{h}|$ $\displaystyle\leq\sum_{j\leq h\leq
k}\ell^{h}\mathbb{E}[X^{(h)}_{C}]+1000\frac{(k-j+1)+\ell}{\ell}|C|\log(\ell)$
$\displaystyle\leq\frac{1}{\ell}\sum_{j\leq h\leq
k}\ell^{h}\sum_{C^{\prime}\in\mathcal{C}^{(h)}}|C^{\prime}\cap C\cap
R_{h}|+1000\frac{d+\ell}{\ell}|C|\log(\ell).$

This proves Lemma 11.

######  Remark 15.

Since there are at most $\mathrm{poly}(n,m,\ell)$ bad events and each bad
event $B$ has $\frac{x(B)}{1-x(B)}\leq 1/2$ (because $x(B)\leq\ell^{-18}$),
the constructive variant of LLL by Moser and Tardos [13] can be applied to
find a selection of configurations such that no bad events occur in randomized
polynomial time.

###  3.4 Assignment of resources to configurations

In this subsection, we show how all the previously established properties
allow us to find, in polynomial time, a good assignment of resources to the
configurations $\mathcal{K}$ chosen as in the previous subsection. We will
denote as in the previous subsection $\mathcal{K}_{i}^{(k)}=\\{K_{i}\\}$ if
$K_{i}\in\mathcal{C}_{i}^{(k)}$ and $\mathcal{K}_{i}^{(k)}=\emptyset$
otherwise. We also define $\mathcal{K}^{(k)}=\bigcup_{i}\mathcal{K}_{i}^{(k)}$
and $\mathcal{K}^{(\geq k)}=\bigcup_{h\geq k}\mathcal{K}^{(k)}$. Finally we
define the parameter

$\gamma=100.000\frac{d+\ell}{\ell}\log(\ell),$

which will define how many times each resource can be assigned to
configurations in an intermediate solution. Note that
$d\leq\log(n)/\log(\ell)$. By our choice of $\ell=300.000\log^{3}(n)$, we have
that $\gamma\leq 310.000\log\log(n)$. Lemma 11 implies the following bound.
For sake of brevity, the proof is deferred to Appendix D.

######  Claim 16.

For any $k\geq 0$, any $0\leq j\leq k$, and any $C\in\mathcal{K}^{(k)}$

$\sum_{j\leq h\leq k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h}|K\cap C\cap
R_{h}|\leq 2000\frac{d+\ell}{\ell}\log(\ell)|C|$

The main technical part of this section is the following lemma that is proved
by induction.

######  Lemma 17.

For any $j\geq 0$, there exists an assignment of resources of $R_{j}$ to
configurations in $\mathcal{K}^{(\geq j)}$ such that no resource is taken more
than $\gamma$ times and each configuration $C\in\mathcal{K}^{(k)}$ ($k\geq j$)
receives at least

$\left(1-\frac{1}{\log(n)}\right)^{2(k-j)}\ell^{k-j}|C\cap
R_{k}|-\frac{3}{\gamma}\sum_{j\leq h\leq
k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h-j}|K\cap C\cap R_{h}|$

resources from $R_{k}$.

Before proceeding to the proof, we first give intuition of why this is what we
want to prove. Note that the term $\ell^{k-j}|C\cap R_{k}|$ is roughly equal
to $\ell^{-j}|C|$ by the properties of the resource sets (precisely Lemma 8).
The second term

$\sum_{j\leq h\leq k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h-j}|K\cap C\cap
R_{h}|$

can be shown to be

$O\left(\ell^{-j}\frac{d+\ell}{\ell}\log(\ell)|C|\right)=O(\ell^{-j}\log\log(n)|C|)$

by Claim 16. Hence by choosing $\gamma$ to be $\Theta(\log\log(n))$ we get
that the bound in Lemma 17 will be $\Theta(\ell^{-j}|C|)$. At the end of the
induction, we have $j=0$ which indeed implies that we have an assignment in
which configurations receive

$\Theta(\ell^{-0}|C|)=\Theta(|C|)$

resources and such that each resource is assigned to at most $O(\log\log(n))$
configurations.

###### Proof.

We start from the biggest configurations and then iteratively reconstruct a
good solution for smaller and smaller configurations. Recall $d$ is the
smallest integer such that $\mathcal{K}^{(\geq d)}$ is empty. Our base case
for these configurations in $\mathcal{K}^{(\geq d)}$ is vacuously satisfied.

Now assume that we have a solution at level $j$, i.e. an assignment of
resources to configurations in $\mathcal{K}^{(\geq j)}$ such that no resource
is taken more than $\gamma$ times and each configuration
$C\in\mathcal{K}^{(k)}$ such that $k\geq j$ receives at least

$\left(1-\frac{1}{\log(n)}\right)^{2(k-j)}\ell^{k-j}|C\cap
R_{k}|-\frac{3}{\gamma}\sum_{j\leq h\leq
k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h-j}|K\cap C\cap R_{h}|$

resources from $R_{j}$. We show that this implies a solution at level $j-1$ in
the following way. First by Lemma 10, this implies an assignment of resources
of $R_{j-1}$ to configurations in $\mathcal{K}^{(\geq j)}$ such that each
$C\in\mathcal{K}^{(k)}$ receives at least

$\displaystyle\left(1-\frac{1}{\log(n)}\right)\ell\left(\ell^{k-j}\left(1-\frac{1}{\log(n)}\right)^{2(k-j)}|C\cap
R_{k}|-\frac{3}{\gamma}\sum_{j\leq h\leq
k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h-j}|K\cap C\cap R_{h}|\right)$
$\displaystyle=\left(1-\frac{1}{\log(n)}\right)^{2(k-(j-1))-1}\ell^{k-(j-1)}|C\cap
R_{k}|-\frac{3}{\gamma}\left(1-\frac{1}{\log(n)}\right)\sum_{j\leq h\leq
k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h-(j-1)}|K\cap C\cap R_{h}|$
$\displaystyle\geq\left(1-\frac{1}{\log(n)}\right)^{2(k-(j-1))-1}\ell^{k-(j-1)}|C\cap
R_{k}|-\frac{3}{\gamma}\sum_{j\leq h\leq
k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h-(j-1)}|K\cap C\cap R_{h}|$

resources and no resource of $R_{j-1}$ is taken more than $\gamma$ times. Note
that we can apply Lemma 10 since we have by Claim 16 and Lemma 8

$\displaystyle\left(1-\frac{1}{\log(n)}\right)^{2(k-j)}\ell^{k-j}|C\cap
R_{k}|-\frac{3}{\gamma}\sum_{j\leq h\leq
k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h-j}|K\cap C\cap R_{h}|$
$\displaystyle\geq\frac{\ell^{k-j}}{e^{2}}|C\cap
R_{k}|-\frac{3}{\gamma}2000\ell^{-j}\frac{d+\ell}{\ell}\log(\ell)|C|$
$\displaystyle\geq\ell^{-j}|C|\left(\frac{1}{2e^{2}}-\frac{6000}{\gamma}\frac{d+\ell}{\ell}\log(\ell)\right)$
$\displaystyle\geq\frac{\ell^{-j}|C|}{3e^{2}}>\frac{\ell^{3}}{1000}$

Now consider configurations in $\mathcal{K}^{(j-1)}$ and proceed for them as
follows. Give to each $C\in\mathcal{K}^{(j-1)}$ all the resources in $C\cap
R_{j-1}$ except all the resources that appear in more than $\gamma$
configurations in $\mathcal{K}^{(j-1)}$. Since each deleted resource is
counted at least $\gamma$ times in the sum
$\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap R_{j-1}|$, we have that each
configuration $C$ in $\mathcal{K}^{(j-1)}$ receives at least

$|C\cap R_{j-1}|-\frac{1}{\gamma}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap
R_{j-1}|$

resources and no resource is taken more than $\gamma$ times by configurations
in $\mathcal{K}^{(j-1)}$. Notice that now every resource is taken no more than
$\gamma$ times by configurations in $\mathcal{K}^{(\geq j)}$ and no more than
$\gamma$ times by configurations in $\mathcal{K}^{(j-1)}$ which in total can
sum up to $2\gamma$ times.

Therefore to finish the proof consider an resource $i\in R_{j-1}$. This
resource is taken $b_{i}$ times by configurations in $\mathcal{K}^{(\geq j)}$
and $a_{i}$ times by configurations in $\mathcal{K}^{(j-1)}$. If
$a_{i}+b_{i}\leq\gamma$, nothing needs to be done. Otherwise, denote by $O$
the set of problematic resources (i.e. resources $i$ such that
$a_{i}+b_{i}>\gamma$). For every $i\in O$, select uniformly at random
$a_{i}+b_{i}-\gamma$ configurations in $\mathcal{K}^{(\geq j)}$ that currently
contain resource $i$ and delete the resource from these configurations. When
this happens, each configuration in $C\in\mathcal{K}^{(\geq j)}$ that contains
$i$ has a probability of $(a_{i}+b_{i}-\gamma)/b_{i}$ to be selected to loose
this resource. Hence the expected number of resources that $C$ looses with
such a process is

$\mu=\sum_{i\in O\cap C}\frac{a_{i}+b_{i}-\gamma}{b_{i}}$

It is not difficult to prove the following claim. However, for better clarity
we defer its proof to appendix D.

######  Claim 18.

For any $C\in\mathcal{K}^{(\geq j)}$,

$\frac{1}{\gamma^{2}}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap R_{j-1}\cap
O|\leq\mu\leq\frac{2}{\gamma}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap
R_{j-1}\cap O|$

Assume then that $\mu\leq\frac{|C\cap R_{k}|}{10^{12}\log^{3}(n)}$. Note that
$C$ cannot loose more than $\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap
R_{j-1}\cap O|$ resources in any case. Therefore, by assumption on $\mu$, and
since

$\mu\geq\frac{1}{\gamma^{2}}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap
R_{j-1}\cap O|\ ,$

we have that

$\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap R_{j-1}\cap
O|\leq\frac{\gamma^{2}}{10^{12}\log^{3}(n)}|C\cap
R_{k}|\leq\frac{10^{11}\log^{2}\log(n)}{10^{12}\log^{3}(n)}|C\cap
R_{k}|\leq\frac{1}{\log(n)}|C\cap R_{k}|\ .$

Therefore $C$ looses at most $|C\cap R_{k}|/\log(n)$ resources. Otherwise we
have that

$\mu>\frac{|C\cap
R_{k}|}{10^{12}\log^{2}(n)}\geq\frac{\ell^{3}}{10^{12}\log^{3}(n)}\geq
200\log(n)$

by Lemma 8. Hence noting $X$ the number of deleted resources in $C$ we have
that

$\mathbb{P}\left(X\geq\frac{3}{2}\mu\right)\leq\exp\left(-\frac{\mu}{12}\right)\leq\frac{1}{n^{10}}.$

With high probability no configuration looses more than

$\frac{3}{2}\mu\leq\frac{3}{\gamma}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap
R_{j-1}\cap O|\leq\frac{3}{\gamma}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap
R_{j-1}|$

resources. Hence each configuration $C\in\mathcal{K}^{(\geq j)}$ ends with at
least

$\displaystyle\left(1-\frac{1}{\log(n)}\right)^{2(k-(j-1))-1}\ell^{k-(j-1)}|C\cap
R_{k}|-\frac{3}{\gamma}\sum_{j\leq h\leq
k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h-(j-1)}|K\cap C\cap R_{h}|$
$\displaystyle-\frac{1}{\log(n)}\left(1-\frac{1}{\log(n)}\right)^{2(k-(j-1))-1}\ell^{k-(j-1)}|C\cap
R_{k}|-\frac{3}{\gamma}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap R_{j-1}|$
$\displaystyle\geq\left(1-\frac{1}{\log(n)}\right)^{2(k-(j-1))}\ell^{k-(j-1)}|C\cap
R_{k}|-\frac{3}{\gamma}\sum_{j-1\leq h\leq
k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h-(j-1)}|K\cap C\cap R_{h}|$

resources which concludes the proof. ∎

######  Corollary 19.

There exists an assignment of resources $R$ to $\mathcal{K}$ such that each
configuration $C\in\mathcal{K}$ receives at least
$\left\lfloor|C|/(100\gamma)\right\rfloor$ resources. Moreover, this
assignment can be found in polynomial time.

###### Proof.

Lemma 17 for $k=0$ and Claim 16 together imply that we can assign at least

$\frac{|C|}{2e^{2}}-\frac{6000}{100.000}|C|\geq\frac{|C|}{100}$

resources to every $C\in\mathcal{K}$ such that no resource in $R$ is assigned
more than $\gamma$ times. In particular, we can fractionally assign at least
$|C|/(100\gamma)$ resources to each $C\in\mathcal{K}$ such that no resource is
assigned more than once. By integrality of the bipartite matching polytope,
the corollary follows. ∎

##  4 Further connections between hypergraph matching and Santa Claus

In Section 3 we essentially prove that every regular (non-uniform) hypergraph
has an $\alpha$-relaxed perfect matching for some $\alpha=O(\log\log(n))$,
assuming that all hyperedges contain at least $\alpha$ resources. This means
that we give a sufficient condition for a hypergraph to have a good relaxed
matching. A natural optimization problem that arises from this is the
following: Given any unweighted hypergraph, which is not necessarily regular
nor all hyperedges necessarily contain many resources, what is the minimum
$\alpha$ such that there exists an $\alpha$-relaxed perfect matching in this
hypergraph?

In this section, we investigate the relationship between this problem and the
Santa Claus problem with linear utility functions. Formally, the two problems
considered are precisely the following.

#### Matching in general hypergraphs.

Consider a (non-uniform) hypergraph $\mathcal{H}=(P\cup R,\mathcal{C})$ with
unit weights, that is, $w_{j,C}=1$ for all $j,C$ such that $j\in C$. The
problem is to find the minimum $\alpha$ such that $\mathcal{H}$ has an
$\alpha$-relaxed perfect matching (and output such a matching).

#### The Santa Claus with linear utility functions.

In this case, each player $i$ has an arbitrary linear utility function
$f_{i}$. We note that there is no relationship assumed between the utility
functions of different players. The goal is to assign resources to players to
maximize the minimum utility among players. As mentioned in introduction, the
best approximation algorithm for this problem is an
$O(n^{\epsilon})$-approximation running in time $O(n^{1/\epsilon})$.

We show by a straightforward reduction that a $c$-approximation for the Santa
Claus problem immediately implies a $c$-approximation for the matching
problem. Interestingly, there is also a close connection in the opposite
direction.

######  Theorem 20.

A $c$-approximation algorithm to the hypergraph matching problem in general
hypergraphs yields an $O((c\log^{*}(n))^{2})$-approximation algorithm to the
Santa Claus problem.

We mention that we implicitly refer to polynomial time algorithms even when
not specified. All the proofs of this section are deferred to Appendix E. We
also mention that Theorem 20 implies that any sub-polynomial approximation to
the matching problem would be a significant improvement of the state-of-the-
art for Santa Claus with arbitrary linear utility functions.

#### Remark.

Since hypergraphs considered here might be non-regular and some hyperedges
might contain very few resources, our result in Section 3 does not imply any
approximation for the optimization problem considered here. Our reduction in
this section makes a crucial use of small hyperedges containing only one
resource. This shows that handling the small hyperedges is one of the core
difficulties in this case.

##  5 Conclusion

We investigated the submodular Santa Claus in the restricted assignment case
and gave a $O(\log\log(n))$-approximation for this problem. This represents a
significant generalization of the results for the linear case. The
submodularity of the utility function introduced new obstacles compared to the
linear case. These difficulties are captured by the fact that we need to solve
a new matching problem in non-uniform hypergraphs that generalizes the case of
uniform hypergraphs which has been already studied in the context of the
restricted Santa Claus problem with a linear utility function. Under the
assumption that the hypergraph is regular and all edges are sufficiently
large, we proved that there is always a $\alpha$-relaxed perfect matching for
$\alpha=O(\log\log(n))$. This result generalizes the work of Bansal and
Srividenko [3]. It remains an intriguing question whether one can get
$\alpha=O(1)$ as it is possible in the uniform case. One idea (similar to
Feige’s proof in the uniform case [8]) would be to view our proof as a
sparsification theorem and to apply it several times. Given a set of
hyperedges such that every player has $\ell$ hyperedges and every resource
appears in no more than $\ell$ hyperedges, one would like to select
$\textrm{polylog}(\ell)$ hyperedges for each player such that all resources
appear in no more than $\textrm{polylog}(\ell)$ of the selected hyperedges. It
is not difficult to see than our proof actually achieves this when
$\ell=\textrm{polylog}(n)$. However, repeating this after the first step seems
to require new ideas since our bound on the number of times each resource is
taken is $\Omega\left(\frac{d+\ell}{\ell}\log(\ell)\right)$ where $\ell$ is
the current sparsity and $d$ the number of configuration sizes. For the first
step, we conveniently have that $d=O(\log(n))=O(\ell)$ but after the first
sparsification, it may not be true.

We also provided a reduction from the Santa Claus with arbitrary linear
utility functions to the hypergraph matching problem in general hypergraphs.
This shows that finding the smallest $\alpha$ such that a hypergraph has an
$\alpha$-relaxed perfect matching (or approximating it) is a very non-trivial
problem (even within a sub-polynomial factor). Another interesting question is
to improve the $O(\log^{*}(n))^{2}$ factor in the reduction to a constant.

##  6 Acknowledgements

The authors wish to thank Ola Svensson for helpful discussions on the problem.

## References

  * AFS [12] Arash Asadpour, Uriel Feige, and Amin Saberi.  Santa claus meets hypergraph matchings.  ACM Trans. Algorithms, 8(3), July 2012.
  * AKS [17] Chidambaram Annamalai, Christos Kalaitzis, and Ola Svensson.  Combinatorial algorithm for restricted max-min fair allocation.  ACM Trans. Algorithms, 13(3):37:1–37:28, 2017.
  * BS [06] Nikhil Bansal and Maxim Sviridenko.  The santa claus problem.  In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’06, page 31–40, New York, NY, USA, 2006. Association for Computing Machinery.
  * CCK [09] Deeparnab Chakrabarty, Julia Chuzhoy, and Sanjeev Khanna.  On allocating goods to maximize fairness.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 107–116. IEEE Computer Society, 2009.
  * CM [18] Siu-Wing Cheng and Yuchen Mao.  Restricted max-min fair allocation.  In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 37:1–37:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * CM [19] Siu-Wing Cheng and Yuchen Mao.  Restricted max-min allocation: Approximation and integrality gap.  In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 38:1–38:13, 2019.
  * DRZ [20] Sami Davies, Thomas Rothvoss, and Yihao Zhang.  A tale of santa claus, hypergraphs and matroids.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2748–2757, 2020.
  * Fei [08] Uriel Feige.  On allocations that maximize fairness.  In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, page 287–293, USA, 2008. Society for Industrial and Applied Mathematics.
  * GHIM [09] Michel X Goemans, Nicholas JA Harvey, Satoru Iwata, and Vahab Mirrokni.  Approximating submodular functions everywhere.  In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 535–544. SIAM, 2009.
  * JR [20] Klaus Jansen and Lars Rohwedder.  A note on the integrality gap of the configuration lp for restricted santa claus.  Information Processing Letters, 164:106025, 2020.
  * LLN [06] Benny Lehmann, Daniel Lehmann, and Noam Nisan.  Combinatorial auctions with decreasing marginal utilities.  Games Econ. Behav., 55(2):270–296, 2006.
  * LST [87] J. K. Lenstra, D. B. Shmoys, and E. Tardos.  Approximation algorithms for scheduling unrelated parallel machines.  In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pages 217–224, 1987.
  * MT [10] Robin A Moser and Gábor Tardos.  A constructive proof of the general lovász local lemma.  Journal of the ACM (JACM), 57(2):1–15, 2010.
  * MU [17] Michael Mitzenmacher and Eli Upfal.  Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis.  Cambridge university press, 2017.
  * PS [12] Lukas Polacek and Ola Svensson.  Quasi-polynomial local search for restricted max-min fair allocation.  In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming, pages 726–737, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
  * Svi [04] Maxim Sviridenko.  A note on maximizing a submodular set function subject to a knapsack constraint.  Oper. Res. Lett., 32(1):41–43, 2004.
  * Von [08] Jan Vondrák.  Optimal approximation for the submodular welfare problem in the value oracle model.  In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 67–74. ACM, 2008.

##  Appendix A Concentration bounds

######  Proposition 21 (Chernoff bounds (see e.g. [14])).

Let $X=\sum_{i}X_{i}$ be a sum of independent random variables such that each
$X_{i}$ can take values in a range $[0,1]$. Define $\mu=\mathbb{E}(X)$. We
then have the following bounds

$\mathbb{P}\left(X\geq(1+\delta)\mathbb{E}(X)\right)\leq\exp\left(-\frac{\min\\{\delta,\delta^{2}\\}\mu}{3}\right)$

for any $\delta>0$.

$\mathbb{P}\left(X\leq(1-\delta)\mathbb{E}(X)\right)\leq\exp\left(-\frac{\delta^{2}\mu}{2}\right)$

for any $0<\delta<1$.

The following proposition follows immediately from Proposition 21 by apply it
with $X^{\prime}=X/a$.

######  Proposition 22.

Let $X=\sum_{i}X_{i}$ be a sum of independent random variables such that each
$X_{i}$ can take values in a range $[0,a]$ for some $a>0$. Define
$\mu=\mathbb{E}(X)$. We then have the following bounds

$\mathbb{P}\left(X\geq(1+\delta)\mathbb{E}(X)\right)\leq\exp\left(-\frac{\min\\{\delta,\delta^{2}\\}\mu}{3a}\right)$

for any $\delta>0$.

$\mathbb{P}\left(X\leq(1-\delta)\mathbb{E}(X)\right)\leq\exp\left(-\frac{\delta^{2}\mu}{2a}\right)$

for any $0<\delta<1$.

##  Appendix B Omitted proofs from Section 2

###  B.1 Solving the configuration LP

The goal of this section is to prove Theorem 2. We consider the dual of the
configuration LP (after adding an artificial minimization direction $\min
0^{T}x$).

$\displaystyle\max\sum_{i\in P}y_{i}$ $\displaystyle-\sum_{j\in R}z_{j}$
$\displaystyle\sum_{j\in C}z_{j}$ $\displaystyle\geq y_{i}\quad\text{ for all
}i\in P,C\in\mathcal{C}(i,T)$ $\displaystyle y_{j},z_{i}$ $\displaystyle\geq
0$

Observe that the optimum of the dual is either $0$ obtained by $y_{i}=0$ and
$z_{j}=0$ for all $i,j$ or it is unbounded: If it has any solution with
$\sum_{i\in P}y_{i}-\sum_{j\in R}z_{j}>0$, the variables can be scaled by an
arbitrary common factor to obtain any objective value. If it is unbounded,
this can therefore be certified by providing a feasible solution $y,z$ with

$\sum_{i\in P}y_{i}-\sum_{j\in R}z_{j}\geq 1.$ ($*$)

We approximate the dual in the variant with constraint $(*)$ instead of a
maximization direction using the ellipsoid method. The separation problem of
the dual is as follows. Given $z_{j}$, $y_{i}$ find a player $i$ and set $C$
with $g(C\cap\Gamma_{i})\geq T$ such that $\sum_{j\in C}z_{j}<y_{i}$.

To this end, consider the related problem of maximizing a monotone submodular
function subject to knapsack constraints. In this problem we are given a
monotone submodular function $g$ over a ground set $E$ and the goal is to
maximize $g(E^{\prime})$ over all $E^{\prime}\subseteq E$ with $\sum_{j\in
E^{\prime}}a_{j}\leq b$. Here $a_{j}\geq 0$ is a weight associated with $j\in
E$ and $b$ is a capacity. For this problem Srividenko gave a polynomial time
$(1-1/e)$-approximation algorithm [16]. It is not hard to see that this can be
used to give a constant approximation for the variation where strict
inequality is required in the knapsack constraint: Assume w.l.o.g. that
$0<a_{j}<b$ for all $j$. Then run Srivideko’s algorithm to find a set
$E^{\prime}$ with $\sum_{j\in E^{\prime}}a_{j}\leq b$. Notice that
$g(E^{\prime})$ is at least $(1-1/e)\mathrm{OPT}$, also when $\mathrm{OPT}$ is
the optimal value with respect to strict inequality. If $E^{\prime}$ contains
only one element then equality in the knapsack constraint cannot hold and we
are done. Otherwise, split $E^{\prime}$ into two arbitrary non-empty parts
$E^{\prime\prime}$ and $E^{\prime\prime\prime}$. It follows that $\sum_{j\in
E^{\prime\prime}}a_{j}<b$ and $\sum_{j\in E^{\prime\prime\prime}}a_{j}<b$.
Moreover, either $g(E^{\prime\prime})\geq g(E^{\prime})/2$ or
$g(E^{\prime\prime})\geq g(E^{\prime})/2$. Hence, this method yields a
$c$-approximation for $c=(1-1/e)/2$. We now demonstrate how to use this to
find a $c$-approximation to the configuration LP.

Let $\mathrm{OPT}$ be the optimum of the configuration LP. It suffices to
solve the problem of finding for a given $T$ either a solution of value $cT$
or deciding that $T>\mathrm{OPT}$. This can then be embedded into a standard
dual approximation framework. We run the ellipsoid method on the dual of the
configuration LP with objective value $cT$ and constraint $(*)$. This means we
have to solve the separation problem. Let $z,y$ be the variables at some
state. We first check whether $(*)$ is satisfied, that is $\sum_{i\in
P}y_{i}-\sum_{j\in R}z_{j}\geq 1$. If not, we return this inequality as a
separating hyperplane. Hence, assume $(*)$ is satisfied and our goal is to
find a violated constraint of the form $\sum_{j\in C}z_{j}<y_{i}$ for some
$i\in P$ and $C\in\mathcal{C}(i,T)$. For each player $i$ we maximize $f$ over
all $S\subseteq\Gamma_{i}$ with $\sum_{j\in S}z_{j}<y_{i}$. We use the variant
of Srividenko’s algorithm described above to obtain a $c$-approximation for
each player. If for one player $i$ the resulting set $S$ satisfies $f(S)\geq
cT$, then we have found a separating hyperplane to provide to the ellipsoid
method. Otherwise, we know that $f(S)<T$ for all players $i$ and
$S\subseteq\Gamma_{i}$ with $\sum_{j\in S}z_{j}<y_{i}$. In other words, for
all players $i$ and all $C\in\mathcal{C}(i,T)$ it holds that $\sum_{j\in
C}z_{j}\geq y_{i}$, i.e., $z,y$ is feasible for objective value $T$ and hence
$\mathrm{OPT}>T$. If the ellipsoid method terminates without concluding that
$\mathrm{OPT}>T$, we can derive a feasible primal solution with objective
value $cT$: The configurations constructed for separating hyperplanes suffice
to prove that the dual is bounded. These configurations can only be
polynomially many by the polynomial running time of the ellipsoid method.
Hence, when restricting the primal to these configurations it must remain
feasible. To obtain the primal solution we now only need to solve a polynomial
size linear program. This concludes the proof of Theorem 2.

###  B.2 Clusters

This section is devoted to prove Lemma 3. The arguments are similar to those
used in [3].

######  Lemma 23.

Let $x^{*}$ be a solution to the configuration LP of value $T^{*}$. Then
$x^{*}$ can be transformed into some $x^{\prime}_{i,C}\geq 0$ for $i\in P$,
$C\in\mathcal{C}_{t}(i,T^{*})$ which satisfies the following. There is a
partition of the players into clusters $K_{1}\cup\cdots\cup K_{k}\cup Q=P$
that satisfy the following.

  1. 1.

any thin resource $j$ is fractionally assigned at most once, that is,

$\sum_{i\in P}\sum_{C\in\mathcal{C}_{t}(i,T^{*}):j\in C}x^{\prime}_{i,C}\leq
1$

We say that the congestion on item $j$ is at most 1.

  2. 2.

every cluster $K_{j}$ gets at least $1/2$ thin configurations in $x^{\prime}$,
that is,

$\sum_{i\in K_{j}}\sum_{C\in\mathcal{C}_{t}(i,T^{*})}x^{\prime}_{i,C}\geq
1/2;$

  3. 3.

given any $i_{1}\in K_{1},i_{2}\in K_{2},\dotsc,i_{k}\in K_{k}$ there is a
matching of fat resources to players $P\setminus\\{i_{1},\dotsc,i_{k}\\}$ such
that each of these players $i$ gets a unique fat resource $j\in\Gamma_{i}$.

The role of the set of players $Q$ in the lemma above is that each of them
gets one fat resource for certain.

###### Proof.

We first transform the solution $x^{*}$ as follows. For every configuration
$C$ (for player $i$) that contains at least one fat resource and such that
$x^{*}_{i,C}>0$, we select arbitrarily one of these fat resources $j$ and we
set $x^{*}_{i,\\{j\\}}=x^{*}_{i,C}$ and then we set $x^{*}_{i,C}=0$. It is
clear that this does not increase the congestion on resources and now every
configuration that has non-zero value is either a thin configuration or a
singleton containing one fat resource. Therefore we can consider the bipartite
graph $G$ formed between the players and the fat resources where there is an
edge between player $i$ and fat resource $j$ if the corresponding
configuration $C=\\{j\\}$ is of non zero value (i.e. $x^{*}_{i,C}>0$). The
value of such an edge will be exactly the value $x^{*}_{i,C}$. We now make G
acyclic by doing the following operation until there exists no cycle anymore.
Pick any cycle (which must have even length since the graph is bipartite) and
increase the coordinate of $x^{*}$ corresponding to every other edge in the
cycle by a small constant. Decrease the value corresponding to the remaining
edges of the cycle by the same constant. This ensures that fat resources are
still (fractionally) taken at most once and that the players still have one
unit of configurations fractionally assigned to them. We continue this until
one of the edge value becomes 0 or 1. If an edge becomes 0, delete that edge
and if it becomes 1, assign the corresponding resource to the corresponding
player forever. Then delete the player and the resource from the graph and add
the player to the cluster $Q$. By construction, every added player to $Q$ is
assigned a unique fat resource. Notice that when we stop, each remaining
player still has at least 1 unit of configurations assigned to him and every
fat resource is still (fractionally) taken at most once. Hence we get a new
assignment vector where the assignments of fat resources to players form a
forest. We also note that the congestion on thin resources did not increase
during this process (it actually only decreased either when we replace fat
configurations by a singleton and when players are put into the set $Q$ and
deleted from the instance). We show below how to get the clusters for any tree
in the forest.

  1. 1.

If the tree consists of a single player, then it trivially forms its own
cluster. By feasibility of the original solution $x^{*}$, condition 2 of the
lemma holds.

  2. 2.

If there is a fat resource that has degree 1, assign it to its player, add the
player to $Q$ and delete both the player and resource. Continue this until
every resource has a degree of at least 2. This step adds players to cluster
$Q$. By construction, every added player is assigned a unique fat resource.

  3. 3.

While there is a resource of degree at least 3, we perform the following
operation. Root the tree containing such a resource at an arbitrary player.
Consider a resource $j$ of degree at least 3 such that the subtree rooted at
this resource contains only resources of degree 2. Because this resource must
have at least 2 children in the tree $i_{1},i_{2},\ldots$ (which are players)
and because

$\sum_{i\in P}\sum_{C:j\in C}x^{*}_{i,C}\leq 1,$

it must be that one of the children (say $i_{1}$) satisfies
$x^{*}_{i_{1},\\{j\\}}\leq 1/2$. We then delete the edge $(j,i_{1})$ in the
tree and set $x^{*}_{i_{1},\\{j\\}}$ to 0.

  4. 4.

Every resource now has degree exactly 2. We form a cluster for each tree in
the forest. The cluster will contain the players and fat resources in the
tree. We note that in every tree, only the player at the root lost at most
$1/2$ unit of a fat resource by the previous step in the construction. By the
degree property of resources and because the graph contains no cycle, it must
be that in each cluster $K$ we have $|R(K)|=|P(K)|-1$ where $|R(K)|$ is the
number of resources in the cluster and $|P(K)|$ the number of players. Because
each resource is assigned at most once, and because only one player in the
cluster lost at most $1/2$ unit of a fat resource, it must be that the
cumulative amount of thin configurations assigned to players in $K$ is at
least

$|P(K)|-|R(K)|-1/2=1/2.$

This gives the second property of the lemma. For the third property, notice
that for any choice of player $i\in K$, we can root the tree corresponding to
the cluster $K$ at the player $i$ and assign all the fat resources in $K$ to
their only child in the tree (they all have degree 2). This gives the third
property of the lemma.

As each of these steps individually maintained maintained a congestion of at
most $1$ on every thin resource, we indeed get a new solution $x^{\prime}$ and
the associated clusters with the required properties.

∎

Lemma 23 implies that for each cluster we need to cover only one player with a
thin configuration. Then the remaining players can be covered with fat
resources. We will now replace $x^{\prime}$ by a solution $x^{\prime\prime}$
which takes slightly worse configurations $\mathcal{C}_{t}(i,T^{*}/5)$, but
satisfies (2) in Lemma 23 with $2$ instead of $1/2$. This can be achieved by
splitting each configuration $C\in\mathcal{C}_{t}(i,T^{*})$ in $4$ disjoint
parts $C_{1},C_{2},C_{3},C_{4}\in\mathcal{C}_{t}(i,T^{*}/5)$. Let
$C_{1}\subseteq C$ with $f(C_{1})\geq T^{*}/5$ minimal in the sense that
$f(C_{1}\setminus\\{j\\})<T^{*}/5$ for all $j\in C_{1}$. Let $j_{1}\in C_{1}$.
By submodularity and because $j_{1}$ is thin it holds that

$f(C\setminus C_{1})\geq f(C)-f(C_{1}\setminus\\{j_{1}\\})-f(\\{j_{1}\\})\geq
4T^{*}/5-T^{*}/100.$

Hence, in the same way we can select $C_{2}\subseteq C\setminus C_{1}$,
$C_{3}\subseteq C\setminus(C_{1}\cup C_{2})$ and $C_{4}\subseteq
C\setminus(C_{1}\cup C_{2}\cup C_{3})$. We now augment $x^{\prime}$ to
$x^{\prime\prime}$ by initializing $x^{\prime\prime}$ with $0$ and then for
each $i$ and $C\in\mathcal{C}(i,T^{*})$ increasing
$x^{\prime\prime}_{i,C_{1}}$, $x^{\prime\prime}_{i,C_{2}}$,
$x^{\prime\prime}_{i,C_{3}}$, and $x^{\prime\prime}_{i,C_{4}}$ by
$x^{\prime}_{i,C}$. Here $C_{1},C_{2},C_{3},C_{4}\in\mathcal{C}(i,T^{*}/5)$
are the configurations derived from $C$ by splitting it as described above.

Finally, we sample for each cluster some $\ell\geq 12\log(n)$ many
configurations with the distribution of $x^{\prime\prime}$ to obtain the
statement of Lemma 3 which we restate for convenience.

######  Lemma 3.

(restated) Let $\ell\geq 12\log(n)$. Given a solution of value $T^{*}$ for the
configuration LP in randomized polynomial time we can find a partition of the
players into clusters $K_{1}\cup\cdots\cup K_{k}\cup Q=P$ and multisets of
configurations $\mathcal{C}_{h}\subseteq\bigcup_{i\in
K_{h}}\mathcal{C}_{T}(i,T^{*}/5)$, $h=1,\dotsc,k$, such that

  1. 1.

$|\mathcal{C}_{h}|=\ell$ for all $h=1,\dotsc,k$ and

  2. 2.

Each small resource appears in at most $\ell$ configurations of
$\bigcup_{h}\mathcal{C}_{h}$.

  3. 3.

given any $i_{1}\in K_{1},i_{2}\in K_{2},\dotsc,i_{k}\in K_{k}$ there is a
matching of fat resources to players $P\setminus\\{i_{1},\dotsc,i_{k}\\}$ such
that each of these players $i$ gets a unique fat resource $j\in\Gamma_{i}$.

###### Proof.

We start with the clusters obtained with Lemma 23 and the solution
$x^{\prime\prime}$ described above. Recall that

$\sum_{i\in K_{h}}\sum_{C\in C_{t}(i,T^{*}/5)}x^{\prime\prime}_{i,C}\geq 2$

for each cluster $K_{h}$. We assume w.l.o.g. that equality holds by reducing
some variables $x^{\prime\prime}_{i,C}$. Clearly then each resource is still
contained in at most one configuration in total.

For each cluster $K_{h}$, we sample a configuration that contains a player in
this cluster according to the probability distribution given by the values
$\\{x^{\prime\prime}_{i,C}/2\\}_{i\in K_{h},C\in\mathcal{C}_{t}(i,T^{*}/5)}$.
By the assumption of equality stated above this indeed defines a probability
distribution. We repeat this process $\ell$ times. We first note that for one
iteration, each resource is in expectation contained in

$\sum_{i\in P}\sum_{C\in\mathcal{C}(i,T^{*}/5):j\in
C}x^{\prime\prime}_{i,C}/2\leq 1/2$

selected configurations. Hence in expectation all the resource are contained
in $\ell/2$ selected configurations after $\ell$ iterations. By a standard
Chernoff bound (see Proposition 21), we have that with probability at most

$\exp\left(-\ell/6\right)\leq 1/n^{2}$

a resource is contained in more than $\ell$ configurations. By a union bound,
it holds that all resources are contained in at most $\ell$ selected
configurations with high probability. ∎

##  Appendix C Omitted proofs from Section 3.2

######  Lemma 8.

(restated) Consider Random Experiment 7 with $\ell\geq 300.000\log^{3}(n)$.
For any $k\geq 0$ and any $C\in\mathcal{C}^{(\geq k)}$ we have

$\frac{1}{2}\ell^{-k}|C|\leq|R_{k}\cap C|\leq\frac{3}{2}\ell^{-k}|C|$

with probability at least $1-1/n^{10}$.

###### Proof.

The lemma trivially holds for $k=0$. For $k>0$, by assumption
$C\in\mathcal{C}^{(\geq k)}$ hence $|C|\geq\ell^{k+3}$. Since each resource of
$R=R_{0}$ survives in $R_{k}$ with probability $\ell^{-k}$ we clearly have
that in expectation

$\mathbb{E}(|R_{k}\cap C|)=\ell^{-k}|C|$

Hence the random variable $X=|R_{k}\cap C|$ is a sum of independent variables
of value either $0$ or $1$ and such that $\mathbb{E}(X)\geq\ell^{3}$. By a
standard Chernoff bound (see Proposition 22), we get

$\mathbb{P}\left(X\notin\left[\frac{\mathbb{E}(X)}{2},\frac{3\mathbb{E}(X)}{2}\right]\right)\leq
2\exp\left(-\frac{\mathbb{E}(X)}{12}\right)\leq
2\exp\left(-\frac{300.000\log^{3}(n)}{12}\right)\leq\frac{1}{n^{10}}$

since by assumption $\ell\geq 300.000\log^{3}(n)$. ∎

######  Lemma 9.

(restated) Consider Random Experiment 7 with $\ell\geq 300.000\log^{3}(n)$.
For any $k\geq 0$ and any $C\in\mathcal{C}^{(\geq k)}$ we have

$\sum_{C^{\prime}\in\mathcal{C}^{(k)}}|C^{\prime}\cap C\cap
R_{k}|\leq\frac{10}{\ell^{k}}\left(|C|+\sum_{C^{\prime}\in\mathcal{C}^{(k)}}|C^{\prime}\cap
C|\right)$

with probability at least $1-1/n^{10}$.

###### Proof.

The expected value of the random variable
$X=\sum_{C^{\prime}\in\mathcal{C}^{(k)}}|C^{\prime}\cap C\cap R_{k}|$ is

$\mathbb{E}(X)=\frac{1}{\ell^{k}}\sum_{C^{\prime}\in\mathcal{C}^{(k)}}|C^{\prime}\cap
C|.$

Since each resource is in at most $\ell$ configurations, $X$ is a sum of
independent random variables that take value in a range $[0,\ell]$. Then by a
standard Chernoff bound (see Proposition 22), we get

$\mathbb{P}\left(X\geq
10\left(\frac{|C|}{\ell^{k}}+\mathbb{E}(X)\right)\right)\leq\exp\left(-\frac{3|C|}{\ell^{k+1}}\right)\leq\frac{1}{n^{10}},$

since by assumption, $|C|\geq\ell^{k+3}$ and $\ell\geq 300.000\log^{3}(n)$.

∎

We finish by the proof of the last property. As mentioned in the main body of
the paper, this statement is a generalization of some ideas that already
appeared in [3]. However, in [3], the situation is simpler since they need to
sample down the resource set only once (i.e. there are only two sets
$R_{1}\subseteq R$ and not a full hierarchy of resource sets $R_{d}\subseteq
R_{d-1}\subseteq\cdots\subseteq R_{1}\subseteq R$). Given the resource set
$R_{1}$, they want to select configurations and give to each selected
configuration $K$ all of its resource set $|K\cap R_{1}|$ so that no resource
is assigned too many times. In our case the situation is also more complex
than that since at every step the selected configurations receive only a
fraction of their current resource set. Nevertheless, we extend the ideas of
Bansal and Srividenko to our more general setting. We recall the main
statement before proceeding to its proof.

######  Lemma 10.

(restated) Consider Random Experiment 7 with $\ell\geq 300.000\log^{3}(n)$.
Fix $k\geq 0$. Conditioned on the event that the bounds in Lemma 8 hold for
$k$, then with probability at least $1-1/n^{10}$ the following holds for all
$\mathcal{F}\subseteq\mathcal{C}^{(\geq k+1)}$,
$\alpha:\mathcal{F}\rightarrow\mathbb{N}$, and $\gamma\in\mathbb{N}$ such that
$\ell^{3}/1000\leq\alpha(C)\leq n$ for all $C\in\mathcal{F}$ and
$\gamma\in\\{1,\dotsc,\ell\\}$: If there is a $(\alpha,\gamma)$-good
assignment of $R_{k+1}$ to $\mathcal{F}$, then there is a
$(\alpha^{\prime},\gamma)$-good assignment of $R_{k}$ to $\mathcal{F}$ where

$\alpha^{\prime}(C)\geq\ell\left(1-\frac{1}{\log(n)}\right)\alpha(C)$ (1)

for all $C\in\mathcal{F}$. Moreover, this assignment can be found in
polynomial time.

We first provide the definitions of a flow network that allows us to state a
clean condition whether a good assignment of resources exists or not. We then
provide the high probability statements that imply the lemma.

For any subset of configurations $\mathcal{F}\subseteq\mathcal{C}^{(\geq
k+1)}$, resource set $R_{k}$, $\alpha:\mathcal{F}\rightarrow\mathbb{N}$, and
any integer $\gamma$, consider the following directed network (denoted by
$\mathcal{N}(\mathcal{F},R_{k},\alpha,\gamma)$). Create a vertex for each
configuration in $\mathcal{F}$ as well as a vertex for each resource. Add a
source $s$ and sink $t$. Then add a directed arc from $s$ to the vertex
$C\in\mathcal{F}$ with capacity $\alpha(C)$. For every pair of a configuration
$C$ and a resource $i$ such that $i\in C$ add a directed arc from $C$ to $i$
with capacity $1$. Finally, add a directed arc from every resource to the sink
of capacity $\gamma$. See Figure 1 for an illustration.

Figure 1: The directed network and an $s$-$t$ cut

We denote by

$\textrm{maxflow}\left(\mathcal{N}(\mathcal{F},R_{k},\alpha,\gamma)\right)$

the value of the maximum $s$-$t$ flow in
$\mathcal{N}(\mathcal{F},R_{k},\alpha,\gamma)$.

Before delving into the technical lemmas, we provide a brief road map for the
proof. First, we argue that for any subset of configurations, in the two
networks induced on this subset and the consecutive resource sets (which are
$R_{k}$ and $R_{k+1}$), the value of the maximum flow differs by approximately
a factor $\ell$ (this is Lemma 25 stated below). Then by a union bound over
all possible subsets of configurations, we say that the above argument
consecutively holds with good probability. This helps us conclude that a good
assignment of the resource set $R_{k+1}$ implies that there is a good
assignment of the resource set $R_{k}$. Notice that if one does not have the
above argument with respect to all subsets of configurations at once, it is
not necessary that a good assignment of resources must exist. In particular,
we need Lemma 24 to show that if on all subsets of configurations the maximum
flow is multiplied by approximately $\ell$ when we expand the resource set
from $R_{k+1}$ to $R_{k}$, then an $(\alpha,\gamma)$-good assignment of
$R_{k+1}$ implies an $(\alpha^{\prime},\gamma)$-good assignment of $R_{k}$,
where $\alpha^{\prime}$ is almost equal to $\ell\alpha$.

######  Lemma 24.

Let $\mathcal{F}$ be a set of configurations, $R^{\prime}\subseteq R$,
$\alpha:\mathcal{F}\rightarrow\mathbb{N}$ a set of resources,
$\gamma\in\mathbb{N}$, and $\epsilon\geq 0$. Define

$\alpha^{\prime}(C)=\lfloor(1-\epsilon)\alpha(C)\rfloor.$

There is an $(\alpha^{\prime},\gamma)$-good assignment of $R^{\prime}$ to
$\mathcal{F}$ if and only if for every
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$, the maximum flow in the network
$\mathcal{N}(\mathcal{F}^{\prime},R^{\prime},\alpha,\gamma)$ is of value at
least $\sum_{C\in\mathcal{F}^{\prime}}\alpha^{\prime}(C)$. Moreover, this
assignment can be found in polynomial time.

###### Proof.

First assume there is such an $(\alpha^{\prime},\gamma)$-good assignment. Then
send a flow of $\alpha^{\prime}(C)$ from $s$ to each $C\in\mathcal{F}$. If
resource $i$ is assigned to $C$, send a flow of $1$ from $C$ to $i$. Finally
ensure that flow is preserved at every vertex corresponding to a resource by
sending the correct amount of flow to $t$. Since no resource is taken more
than $\gamma$ times, this flow is feasible.

We prove the other direction by contradiction. Denote by $\mathcal{N}$ the
network $\mathcal{N}(\mathcal{F},R^{\prime},\alpha^{\prime},\gamma)$. If there
is no good assignment satisfying the condition of the lemma then the maximum
flow in $\mathcal{N}$ must be strictly less than
$\sum_{C\in\mathcal{F}}\alpha^{\prime}(C)$ (otherwise consider the maximum
flow, which can be taken to be integral, and give to every configuration $C$
all the resources to which they send a flow of $1$). Then by the max-flow min-
cut theorem, there exists an $s$-$t$ cut $S$ that has value strictly less than
$\sum_{C\in\mathcal{F}}\alpha^{\prime}(C)$. Let $\mathcal{C}^{\prime}$ be the
set of configurations on the side of the source in $S$. Notice that
$\mathcal{C}^{\prime}$ cannot be empty by assumption on the value of the cut.

Consider the induced network
$\mathcal{N}(\mathcal{C}^{\prime},R^{\prime},\alpha^{\prime},\gamma)$ and the
cut $S$ in it. It has a value strictly lower than
$\sum_{C\in\mathcal{C}^{\prime}}\alpha^{\prime}(C)$. This, in turn implies
that the cut $S$ in
$\mathcal{N}(\mathcal{C}^{\prime},R^{\prime},\alpha,\gamma)$ has a value
strictly lower than $\sum_{C\in\mathcal{C}^{\prime}}\alpha^{\prime}(C)$, since
this cut does not contain any edge from the source $s$ to some configuration.
Hence the maximum flow in
$\mathcal{N}(\mathcal{C}^{\prime},R^{\prime},\alpha,\gamma)$ has a value
strictly less than $\sum_{C\in\mathcal{C}^{\prime}}\alpha^{\prime}(C)$, a
contradiction to the assumption in the premise. ∎

######  Lemma 25.

Let $\mathcal{F}\subseteq\mathcal{C}^{\geq(k+1)}$,
$\alpha:\mathcal{F}\rightarrow\mathbb{N}$ such that
$\ell^{3}/1000\leq\alpha(C)\leq n$ for all $C\in\mathcal{F}$, and
$1\leq\gamma\leq\ell$. Denote by $\mathcal{N}$ the network
$\mathcal{N}(\mathcal{F},R_{k},\ell\cdot\alpha,\gamma)$ and by
$\tilde{\mathcal{N}}$ the network
$\mathcal{N}(\mathcal{F},R_{k+1},\alpha,\gamma)$. Then

$\mathrm{maxflow}\left(\mathcal{N}\right)\geq\frac{\ell}{1+0.5/\log(n)}\mathrm{maxflow}\left(\tilde{\mathcal{N}}\right)$

with probability at least $1-1/(n\ell)^{20|\mathcal{F}|}$.

###### Proof.

We use the max-flow min-cut theorem that asserts that the value of the maximum
flow in a network is equal to the value of the minimum $s$-$t$ cut in the
network. Consider a minimum cut $S$ of network $\mathcal{N}$ with $s\in S$ and
$t\notin S$. Denote by $c(S)$ the value of the cut. We will argue that with
high probability this cut induces a cut of value at most
$c(S)/\ell\cdot(1+0.5/\log(n))$ in the network $\tilde{\mathcal{N}}$. This
directly implies the lemma.

Denote by $\mathcal{C}^{\prime}$ the set of configurations of $\mathcal{F}$
that are in $S$, i.e., on the source side of the cut, and
$\mathcal{C}^{\prime\prime}=\mathcal{F}\setminus\mathcal{C}^{\prime}$.
Similarly consider $R^{\prime}$ the set of resources in the $s$ side of the
cut and $R^{\prime\prime}=R_{k}\setminus R^{\prime}$. With a similar notation,
we denote $\tilde{R}^{\prime}=R^{\prime}\cap R_{k+1}$ the set of resources of
$R^{\prime}$ surviving in $R_{k+1}$; and
$\tilde{R}^{\prime\prime}=R^{\prime\prime}\cap R_{k+1}$. Finally, denote by
$\tilde{S}$ the cut in $\tilde{\mathcal{N}}$ obtained by removing resources of
$R^{\prime}$ that do not survive in $R_{k+1}$ from $S$, i.e.,
$\tilde{S}=\\{s\\}\cup\mathcal{C}^{\prime}\cup R^{\prime}$. The value of the
cut $S$ of $\mathcal{N}$ is

$c(S)=\sum_{C\in\mathcal{C}^{\prime\prime}}\ell\cdot\alpha(C)+e(\mathcal{C}^{\prime},R^{\prime\prime})+\gamma|R^{\prime}|$

where $e(X,Y)$ denotes the number of edges from $X$ to $Y$. The value of the
cut $\tilde{S}$ in $\tilde{\mathcal{N}}$ is

$c(\tilde{S})=\sum_{C\in\mathcal{C}^{\prime\prime}}\alpha(C)+e(\mathcal{C}^{\prime},\tilde{R}^{\prime\prime})+\gamma|\tilde{R}^{\prime}|$

We claim the following properties.

######  Claim 26.

For every $C\in\mathcal{F}$, the outdegree of the vertex corresponding to $C$
in $\mathcal{N}$ is at least $\ell^{4}/2$.

Since $C\in\mathcal{C}^{(\geq k+1)}$ and by Lemma 8, we clearly have that
$|C\cap R_{k}|\geq\ell^{4}/2$.

######  Claim 27.

It holds that

$c(S)\geq\frac{|\mathcal{F}|\ell^{3}}{1000}.$

We have by assumption on $\alpha(C)$

$c(S)=\sum_{C\in\mathcal{C}^{\prime\prime}}\ell\cdot\alpha(C)+e(\mathcal{C}^{\prime},R^{\prime\prime})+\gamma|R^{\prime}|\geq\sum_{C\in\mathcal{C}^{\prime\prime}}\frac{\ell^{3}}{1000}+e(\mathcal{C}^{\prime},R^{\prime\prime})+\gamma|R^{\prime}|\\\
\geq\frac{|\mathcal{C}^{\prime\prime}|\ell^{3}}{1000}+e(\mathcal{C}^{\prime},R^{\prime\prime})+\gamma|R^{\prime}|$

Now consider the case where
$e(\mathcal{C}^{\prime},R^{\prime\prime})\leq|\mathcal{C}^{\prime}|\ell^{3}/1000$.
Since each vertex in $\mathcal{C}^{\prime}$ has outdegree at least
$\ell^{4}/2$ in the network $\mathcal{N}$ (by Claim 26) it must be that
$e(\mathcal{C}^{\prime},R^{\prime})\geq|\mathcal{C}^{\prime}|\ell^{4}/2-|\mathcal{C}^{\prime}|\ell^{3}/1000>|\mathcal{C}^{\prime}|\ell^{4}/3$.
Using that each vertex in $R^{\prime}$ has indegree at most $\ell$ (each
resource is in at most $\ell$ configurations), this implies
$|R^{\prime}|\geq|\mathcal{C}^{\prime}|\ell^{3}/3$. Since $\gamma\geq 1$ we
have in all cases that
$e(\mathcal{C}^{\prime},R^{\prime\prime})+\gamma|R^{\prime}|\geq|\mathcal{C}^{\prime}|\ell^{3}/1000$.
Hence

$c(S)\geq\frac{|\mathcal{C}^{\prime\prime}|\ell^{3}}{1000}+\frac{|\mathcal{C}^{\prime}|\ell^{3}}{1000}=\frac{|\mathcal{F}|\ell^{3}}{1000}.$

This proves Claim 27. We can now finish the proof of the lemma. Denote by $X$
the value of the random variable
$e(\mathcal{C}^{\prime},\tilde{R^{\prime\prime}})+\gamma|\tilde{R^{\prime}}|$.
We have that

$\mathbb{E}[X]=\frac{1}{\ell}(e(\mathcal{C}^{\prime},R^{\prime\prime})+\gamma|R^{\prime}|).$

Moreover, $X$ can be written as a sum of independent variables in the range
$[0,\ell]$ since each vertex is in at most $\ell$ configurations and
$\gamma\leq\ell$ by assumption. By a Chernoff bound (see Proposition 22) with

$\delta=\frac{0.5c(S)}{\log(n)\cdot(c(S)-\sum_{C\in\mathcal{C}^{\prime\prime}}\alpha(C))}\geq\frac{0.5}{\log(n)}$

we have that

$\mathbb{P}\left(X\geq\mathbb{E}(X)+\frac{0.5c(S)}{\ell\log(n)}\right)\leq\exp\left(-\frac{\min\\{\delta,\delta^{2}\\}\mathbb{E}(X)}{3\ell}\right)\\\
\leq\exp\left(-\frac{c(S)}{12\ell^{2}\log^{2}(n)}\right)\leq\exp\left(-\frac{|\mathcal{F}|\ell^{3}}{12.000\ell^{2}\log^{2}(n)}\right)\leq\frac{1}{(n\ell)^{20|\mathcal{F}|}},$

where the third inequality comes from Claim 27 and the last one from the
assumption that $\ell\geq 300.000\log^{3}(n)$. Hence with probability at least
$1-1/(n\ell)^{20|\mathcal{F}|}$, we have that

$c(\tilde{S})=\sum_{C\in\mathcal{C}^{\prime\prime}}\alpha(C)+e(\mathcal{C}^{\prime},\tilde{R}^{\prime\prime})+\gamma|\tilde{R}^{\prime}|\leq\frac{1}{\ell}c(S)+\frac{0.5}{\ell\log(n)}c(S).\qed$

We are now ready to prove Lemma 10. Note that Lemma 25 holds with probability
at least $1-1/(n\ell)^{20|\mathcal{F}|}$. Given the resource set $R_{k}$ and a
cardinality $s=|\mathcal{F}|$ there are $O((n\ell)^{2s})$ ways of defining a
network satisfying the conditions from Lemma 25 ($(m\ell)^{s}\leq(n\ell)^{s}$
choices of $\mathcal{F}$, $n^{s}$ choices for $\alpha$ and $\ell$ choices for
$\gamma$). By a union bound, we can assume that the properties of Lemma 25
hold for every possible network with probability at least $1-1/n^{10}$. Assume
now there is a $(\alpha,\gamma)$-good assignment of $R_{k+1}$ to some family
$\mathcal{F}$. Then by Lemma 24 the
$\mathrm{maxflow}(\mathcal{N}(\mathcal{F}^{\prime},R_{k+1},\alpha,\gamma))$ is
exactly $\sum_{C\in\mathcal{F}^{\prime}}\alpha(C)$ for any
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$. By Lemma 25, this implies that
$\mathrm{maxflow}(\mathcal{N}(\mathcal{F}^{\prime},R_{k},\ell\cdot\alpha,\gamma))$
is at least $\ell/(1+0.5/\log(n))\sum_{C\in\mathcal{F}^{\prime}}\alpha(C)$. By
Lemma 24, this implies a $(\alpha^{\prime},\gamma)$-good assignment from
$R_{k}$ to $\mathcal{F}$, where

$\alpha^{\prime}(C)=\lfloor\ell/(1+0.5/\log(n))\rfloor\alpha(C)\geq\ell/(1+1/\log(n))\alpha(C)\geq\ell(1-1/\log(n))\alpha(C).$

##  Appendix D Omitted proofs from Section 3.4

######  Claim 16.

(restated) For any $k\geq 0$, any $0\leq j\leq k$, and any
$C\in\mathcal{K}^{(k)}$

$\sum_{j\leq h\leq k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h}|K\cap C\cap
R_{h}|\leq 2000\frac{d+\ell}{\ell}\log(\ell)|C|.$

###### Proof of Claim 16.

By Lemma 11 we have that

$\sum_{j\leq h\leq k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h}|K\cap C\cap
R_{h}|\leq\frac{1}{\ell}\sum_{j\leq h\leq
k}\sum_{C^{\prime}\in\mathcal{C}^{(h)}}\ell^{h}|C^{\prime}\cap C\cap
R_{h}|+1000\frac{d+\ell}{\ell}\log(\ell)|C|.$

Furthermore, by Lemma 9, we get

$\sum_{C^{\prime}\in\mathcal{C}^{(h)}}\ell^{h}|C^{\prime}\cap C\cap
R_{h}|\leq\ell^{h}\frac{10}{\ell^{h}}\left(|C|+\sum_{C^{\prime}\in\mathcal{C}^{(h)}}|C^{\prime}\cap
C|\right).$

Finally note that each resource appears in at most $\ell$ configurations,
hence

$\sum_{j\leq h\leq k}\sum_{C^{\prime}\in\mathcal{C}^{(h)}}|C^{\prime}\cap
C|\leq\ell|C|.$

Putting everything together we conclude

$\displaystyle\sum_{j\leq h\leq k}\sum_{K\in\mathcal{K}^{(h)}}\ell^{h}|K\cap
C\cap R_{h}|$ $\displaystyle\leq\frac{1}{\ell}\sum_{j\leq h\leq
k}\sum_{C^{\prime}\in\mathcal{C}^{(h)}}\ell^{h}|C^{\prime}\cap C\cap
R_{h}|+1000\frac{d+\ell}{\ell}\log(\ell)|C|$
$\displaystyle\leq\frac{1}{\ell}\sum_{j\leq h\leq
k}10\left(|C|+\sum_{C^{\prime}\in\mathcal{C}^{(h)}}|C^{\prime}\cap
C|\right)+1000\frac{d+\ell}{\ell}\log(\ell)|C|$
$\displaystyle\leq\frac{k-j}{\ell}10|C|+10|C|+1000\frac{d+\ell}{\ell}\log(\ell)|C|$
$\displaystyle\leq 20|C|+1000\frac{d+\ell}{\ell}\log(\ell)|C|$
$\displaystyle\leq 2000\frac{d+\ell}{\ell}\log(\ell)|C|.\qed$

######  Claim 18.

(restated) For any $C\in\mathcal{K}^{(\geq j)}$,

$\frac{1}{\gamma^{2}}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap R_{j-1}\cap
O|\leq\mu\leq\frac{2}{\gamma}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap
R_{j-1}\cap O|.$

###### Proof of Claim 18.

Note that we can write

$\mu=\sum_{i\in O\cap C}\frac{a_{i}+b_{i}-\gamma}{b_{i}}\leq\max_{i\in O\cap
C}\left\\{\frac{a_{i}+b_{i}-\gamma}{a_{i}b_{i}}\right\\}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap
C\cap R_{j-1}\cap O|.$

The reason for this is that each resource $i$ accounts for an expected loss of
$(a_{i}+b_{i}-\gamma)/b_{i}$ while it is counted $a_{i}$ times in the sum

$\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap R_{j-1}\cap O|.$

Similarly,

$\mu=\sum_{i\in O\cap C}\frac{a_{i}+b_{i}-\gamma}{b_{i}}\geq\min_{i\in O\cap
C}\left\\{\frac{a_{i}+b_{i}-\gamma}{a_{i}b_{i}}\right\\}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap
C\cap R_{j-1}\cap O|.$

Note that by assumption we have that $a_{i}+b_{i}>\gamma$. This implies that
either $a_{i}$ or $b_{i}$ is greater than $\gamma/2$. Assume w.l.o.g. that
$a_{i}\geq\gamma/2$. Since by assumption $a_{i}\leq\gamma$ we have that

$\frac{a_{i}+b_{i}-\gamma}{a_{i}b_{i}}\leq\frac{b_{i}}{a_{i}b_{i}}=\frac{1}{a_{i}}\leq\frac{2}{\gamma}.$

In the same manner, since $a_{i}+b_{i}>\gamma$ and that
$a_{i},b_{i}\leq\gamma$, we can write

$\frac{a_{i}+b_{i}-\gamma}{a_{i}b_{i}}\geq\frac{1}{a_{i}b_{i}}\geq\frac{1}{\gamma^{2}}.$

We therefore get the following bounds

$\frac{1}{\gamma^{2}}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap R_{j-1}\cap
O|\leq\mu\leq\frac{2}{\gamma}\sum_{K\in\mathcal{K}^{(j-1)}}|K\cap C\cap
R_{j-1}\cap O|,$

which is what we wanted to prove. ∎

##  Appendix E Omitted proofs from Section 4

###  E.1 From matchings to Santa Claus

The idea in this reduction is to replace each player by a set of players, one
for each of the $t$ configuration containing him. These players will share
together $t-1$ large new resources, but to satisfy all, one of them has to get
other resources, which are the original resources in the corresponding
configuration.

Players.

For every vertex $v\in P$, and every hyperedge $C\in\mathcal{C}$ that $v$
belongs to, we create a player $p_{v,C}$ in the Santa Claus instance.

Resources.

For every vertex $u\in R$, create a resource $r_{u}$ in the Santa Claus
instance. For any vertex $v\in P$ such that it belongs to $t$ edges in
$\mathcal{C}$, create $t-1$ resources $r_{v,1},r_{v,2},\ldots,r_{v,t-1}$.

Values.

For any resource $r_{u}$ for some $u\in R$ and any player $p_{v,C}$ for some
$C\in\mathcal{C}$, the resource has a value $\frac{1}{|C|-1}$ if $u\in C$,
otherwise it has value $0$. Any resource $r_{v,i}$ for some $v\in P$ and
$i\in\mathbb{N}$, has value $1$ for any player $p_{v,C}$ for some
$C\in\mathcal{C}$ and $0$ to all other players.

It is easy to see that given an $\alpha$-relaxed matching in the original
instance, one can construct an $\alpha$-approximate solution for the Santa
Claus instance.

For the other direction, notice that for each $v\in P$, there exists a player
$p_{v,C}$ for some $C\in\mathcal{C}$, such that it gets resources only of the
type $r_{u}$. One can simply assign the resource $u\in R$ to the player $v$
for any resource $r_{u}$ assigned to $p_{v,C}$.

###  E.2 From Santa Claus to matchings

This subsection is devoted to the proof of Theorem 20.

###### Proof.

We write $(\log)^{k}(n)=\underbrace{\log\cdots\log}_{\times k}(n)$ and
$(\log)^{0}(n)=n$.

#### Construction.

We describe how to construct a hypergraph matching instance from a Santa Claus
instance in four steps by reducing to the following more and more special
cases.

#### (1) Geometric grouping.

In this step, given arbitrary $v_{ij}$, we reduce it to an instance such that
$\mathrm{OPT}=1$ and for each $i,j$ we have $v_{ij}=2^{-k}$ for some integer
$k$ and $1/(2n)<v_{ij}\leq 1$. This step follows easily from guessing
$\mathrm{OPT}$, rounding down the sizes, and omitting all small elements in a
solution.

#### (2) Reduction to O(log*(n)) size ranges.

Next, we reduce to an instance such that for each player $i$ there is some
$k\leq\log^{*}(2n)$ such that for each resource $j$, $v_{ij}\in\\{0,1\\}$ or
$1/(\log)^{k}(2n)<v_{ij}\leq 1/(\log)^{k+1}(2n)$. We explain this step below.

Each player and resource is copied to the new instance. However, we will also
add auxiliary players and resources. Let $i$ be a player. In the optimal
solution there is some $0\leq k\leq\log^{*}(2n)$ such that the values of all
resources $j$ with $1/(\log)^{k}(2n)<v_{ij}\leq 1/(\log)^{k+1}(2n)$ assigned
to player $i$ sum up to at least $1/\log^{*}(2n)$. Hence, we create
$\log^{*}(2n)$ auxiliary players which correspond to each $k$ and each of
which share an resource with the original player that has value $1$ for both.
The original player needs to get one of these resources, which means one of
the auxiliary players needs to get a significant value from the resources with
$1/(\log)^{k}(2n)<v_{ij}\leq 1/(\log)^{k+1}(2n)$. This reduction loses a
factor of at most $\log^{*}(2n)$. Hence, $\mathrm{OPT}\geq 1/\log^{*}(2n)$.

#### (3) Reduction to 3 sizes.

We further reduce to an instance such that for each player $i$ there is some
value $v_{i}$ such that for each resource $j$, $v_{ij}\in\\{0,v_{i},1\\}$.

Let $i$ be some player who has only resources of value $v_{ij}\in\\{0,1\\}$ or
$1/(\log)^{k}(2n)<v_{ij}\leq 1/(\log)^{k+1}(2n)$ for some integer $k$. There
are at most $\log((\log)^{k}(2n))\leq(\log)^{k+1}(2n)$ distinct values of the
latter kind. The idea is to assign bundles of resources of value
$0.5/\left(\log^{*}(2n)(\log)^{k+1}(2n)\right)$ to the player $i$.

Fix a resource value $s$ such that $1/(\log)^{k}(2n)<s\leq
1/(\log)^{k+1}(2n)$. We denote by $R_{s}$ the set of resources $j$ such that
$v_{ij}=s$.

We define the integer

$b=\left\lceil\frac{0.5}{s\log^{*}(2n)(\log)^{k+1}(2n)}\right\rceil$

which is the number of resources of value $s$ that are needed to make a bundle
of total value at least $0.5/\left(\log^{*}(2n)(\log)^{k+1}(2n)\right)$. We
remark that if $s>0.5/\left(\log^{*}(2n)(\log)^{k+1}(2n)\right)$ we have
$b=1$. However, since $s\leq 1/(\log)^{k+1}(2n)$, the value of a bundle never
exceeds $1/(\log)^{k+1}(2n)$ in the instance of step (2).

Then we create

$\left\lfloor|R_{s}|/b\right\rfloor$

auxiliary players $i_{1},i_{2},\ldots$ and auxiliary resources
$j_{1},j_{2},\ldots$ (note that we create 0 player and resource if
$|R_{s}|<b$).

Each auxiliary player $i_{\ell}$ shares resource $j_{\ell}$ with player $i$.
This resource has value $2/\left(\log^{*}(2n)(\log)^{k+1}(2n)\right)$ for
player $i$ and value $1$ for player $i_{\ell}$. Then for all resources $j\in
R_{s}$, we set $v_{ij}=0$ and

$v_{i_{\ell}j}=\frac{1}{(\log^{*}(2n))^{2}b}$

for any auxiliary player $i_{\ell}$ that was created.

We see that we are now in the case where for each player $i$, there exists
some $v_{i}$ such that $v_{ij}\in\\{0,v_{i},1\\}$ for all resources $j$. We
claim the following.

######  Claim 28.

In the instance created at step (3), we have that $\mathrm{OPT}\geq
1/(\log^{*}(2n))^{2}$.

###### Proof.

To see this, take an assignment of resources to player that gives
$1/\log^{*}(2n)$ value to every player in the instance obtained at the end of
step (2). Define $R_{i}$ to be the set of resources assigned to player $i$ in
this solution. Either $R_{i}$ contains a resource of value $1$ or only
resources that are in a range $(1/(\log)^{k}(2n),1/(\log)^{k+1}(2n)]$ for some
integer $k$. In the first case, nothing needs to be done as the resource $j$
of value $1$ assigned to $i$ still satisfies $v_{ij}=1$ in the new instance.
Hence we assign $j$ to $i$ and all auxiliary players created for player $i$
get their auxiliary resource of value 1.

In the second case, fix a resource value $s$. Let $R_{i,s}$ be the set of
resources assigned to $i$ for which $v_{ij}=s$ and $b$ defined as before. We
select $\left\lfloor|R_{i,s}|/b\right\rfloor$ auxiliary players to receive $b$
resources from $R_{i,s}$ and player $i$ takes the corresponding auxiliary
resources. The remaining auxiliary players of the corresponding value take
their auxiliary resource.

Doing this, we ensure that all auxiliary players receive either a value of 1
(by taking the auxiliary resource) or $1/(\log^{*}(2n))^{2}$ by taking
resources assigned to $i$ in the instance of step (2). Moreover, we claim that
$i$ receives a total value of at least $1/(\log^{*}(2n))^{2}$. To see this, we
have $3$ cases depending on the value of $b$ and
$\left\lfloor|R_{i,s}|/b\right\rfloor$.

  * •

If $b=1$, then $\left\lfloor|R_{i,s}|/b\right\rfloor=|R_{i,s}|$. We note that
the value of a bundle of $b$ resources of size $s$ never exceeds
$1/(\log)^{k+1}(2n)$ in instance (2). Since each auxiliary resource represents
a value of $2/\left(\log^{*}(2n)(\log)^{k+1}(2n)\right)$ to player $i$ in
instance (3), it must be that player $i$ receives in instance (3) at least a
$2/\log^{*}(2n)$ fraction of the value he would receive in instance (2).

  * •

If $b>1$ and $\left\lfloor|R_{i,s}|/b\right\rfloor>0$. Then we have that
$\left\lfloor|R_{i,s}|/b\right\rfloor\geq|R_{i,s}|/(2b)$. Since in this case
we have $s<0.5/\left(\log^{*}(2n)(\log)^{k+1}(2n)\right)$ it must be that each
bundle of $b$ resources of size $s$ represents a total value of at most
$1/\left(\log^{*}(2n)(\log)^{k+1}(2n)\right)$. Since the value of auxiliary
resources is twice this value and because
$\left\lfloor|R_{i,s}|/b\right\rfloor\geq|R_{i,s}|/(2b)$ it must be that in
this case player $i$ receives in instance (3) at least the same value he would
receive in instance (2).

  * •

If $\left\lfloor|R_{i,s}|/b\right\rfloor=0$, then player $i$ receives $0$
value from resources of this value. However, when we combine all the values
$s$ for which $\left\lfloor|R_{i,s}|/b\right\rfloor=0$, it represents to
player $i$ in instance (2) a total value of at most

$0.5/\left(\log^{*}(2n)(\log)^{k+1}(2n)\right)\cdot(\log)^{k+1}(2n)=0.5/\log^{*}(2n)$

since there are at most $(\log)^{k+1}(2n)$ different resource values.

Putting everything together, we see that in the first two cases, player $i$
receives at least a $2/\log^{*}(2n)$ fraction of the value he would receive in
instance (2) and that he looses at total value of at most $0.5/\log^{*}(2n)$
in the third case. Since in instance (2) we have that $\mathrm{OPT}\geq
1/\log^{*}(2n)$ we see that in instance (3) player $i$ receives a value at
least

$(2/\log^{*}(2n))\cdot(1/\log^{*}(2n)-0.5/\log^{*}(2n))\geq
1/(\log^{*}(2n))^{2}.$

∎

Finally, we also claim that it is easy to reconstruct an approximate solution
to the instance obtained at step (1) from an approximate solution to the
instance at step (3).

######  Claim 29.

A $c$-approximate solution to the instance obtained at step (3) induces a
$O((c\log^{*}(2n))^{2})$-approximate solution to the instance obtained at step
(1).

###### Proof.

To see this, note that a $c$-approximate solution must give at least
$1/(c(\log^{*}(2n))^{2})$ value to every player since $\mathrm{OPT}\geq
1/(\log^{*}(2n))^{2}$ (by Claim 28). This means that each player $i$ either
takes a resource of value 1 which has also value 1 for him in the instance at
step (1) or he must take at total value of $1/(c(\log^{*}(2n))^{2})$ in
auxiliary resources and the corresponding auxiliary players must take bundles
of resources that represent a value of at least

$0.5/\left(c\log^{*}(2n)(\log)^{k+1}(2n)\right)$

for player $i$ in the instance at step (1). We simply assign all the resources
appearing in these bundles to the player $i$ in the instance of step (1).
Since the value of an auxiliary resource for player $i$ is
$2/\left(\log^{*}(2n)(\log)^{k+1}(2n)\right)$ it must be that player $i$ takes
at least

$\frac{1/(c(\log^{*}(2n))^{2})}{2/\left(\log^{*}(2n)(\log)^{k+1}(2n)\right)}=\frac{(\log)^{k+1}(2n)}{2c\log^{*}(2n)}$

auxiliary resources. Since each auxiliary resource brings a value of

$0.5/\left(c\log^{*}(2n)(\log)^{k+1}(2n)\right)$

to player $i$ (in the instance at step (1)) then player $i$ receives in total
a value of at least

$\frac{1}{(2c\log^{*}(2n))^{2}}$

in the instance of step (1). ∎

Before the last step, we rescale the instance appropriately to get
$\mathrm{OPT}=1$ (we keep the property that each player $i$ has 3 distinct
sizes 0,1 and $v_{i}$).

#### (4) Reduction to hypergraph matching.

For each player create a vertex in $P$ and for each resource create a vertex
in $R$. For each player add one hyperedge for each resource he values at $1$
(containing $i$ and this resource). Moreover, for every player $i$, add
$1/v_{i}$ new vertices to $P$ and the same number of new resources to $R$.
Pair these $1/v_{i}$ new vertices in $P$ and $R$ together (one from $R$ and
one from $P$) and for each pair add a hyperedge containing these two vertices
in the pair. Add another hyperedge for $i$ containing $i$ and all
corresponding $1/v_{i}$ new vertices in $R$. Finally, for each new vertex in
$P$ and each resource that $i$ values at $v_{i}$, add a hyperedge containing
them. See Figure 2 for an illustration: New resources and players are marked
as squares and hyperedges containing only 2 vertices are marked as simple
edges.

Figure 2: An example of the reduction to hypergraph matching for player $i$
with $v_{i}=1/2$.

We claim that there exists a $1$-relaxed perfect matching in this instance.
Since $\mathrm{OPT}=1$ there is an assignment of resources to players such
that every player gets a value $1$. If player $i$ takes one resource of value
$1$, give to player $i$ the corresponding hyperedge and the resource in it in
the hypergraph. All the new players get the new resource they are paired to.
If player $i$ takes $1/v_{i}$ resources of value $v_{i}$, give to player $i$
in the hypergraph all the $1/v_{i}$ new resources contained in the new
hyperedge. Then we give to each new player the hyperedge (and the resource in
it) corresponding to a resource that is assigned to $i$ in instance from step
(3). This is indeed a $1$-relaxed perfect matching.

#### Correctness.

In the reduction we arrive at step (3) for which we prove that a
$c$-approximate solution can be used to easily reconstruct a
$O((c\log^{*}(2n))^{2})$-approximate solution to the original instance (in
Claim 29). It remains to show that a $c$-relaxed perfect matching in the
instance (4) induces a $c$-approximate solution to step (3). To see this, note
that a $c$-relaxed perfect matching in the instance (4) either gives to player
$i$ the resource in one hyperedge corresponding to a resource of value $1$ to
player $i$ in instance (3). In that case we assign this resource to player $i$
in instance (3). Or it gives at least $1/(cv_{i})$ new resources to player
$i$. In this case, it must be that each new player paired to one of these
resources takes one resource of value $v_{i}$ in instance (3). We give these
resources to $i$ in instance (3). In this case $i$ receives a total value of
$v_{i}/(cv_{i})=1/c$ which ends the proof.

We finish by remarking that the size of our construction is indeed polynomial
in the size of the original instance. This is clear for step (1). In step (2),
only $O(\log^{*}(n))$ new players and items are created for each player in the
original instance. In step (3), for each player $i$ and each resource size
$v_{ij}$, at most a polynomial number of resources and players are created. As
for the last step, $O(1/v_{i})$ new resources and players are created for each
player $i$ which is also polynomial since $v_{i}=\Omega(1/n)$. The number of
hyperedges in the hypergraph is also clearly polynomial in the number of
vertices in our construction. ∎