# A characterization of surfaces whose universal cover is the bidisk

Fabrizio Catanese, Marco Franciosi

(Date: March 25, 2008)

###### Abstract.

We show that the universal cover of a compact complex surface $X$ is the
bidisk $\mathbb{H}\times\mathbb{H}$, or $X$ is biholomorphic to
$\mathbb{P}^{1}\times\mathbb{P}^{1}$, if and only if $K_{X}^{2}>0$ and there
exists an invertible sheaf $\eta$ such that $\eta^{2}\cong\mathcal{O}_{X}$ and
$H^{0}(X,S^{2}\Omega^{1}_{X}(-K_{X})\otimes\eta)\neq 0$. The two cases are
distinguished by the second plurigenus, $P_{2}(X)\geq 2$ in the former case,
$P_{2}(X)=0$ in the latter. We also discuss related questions.

##  1\. Introduction

The beauty of the theory of algebraic curves is deeply related to the manifold
implications of the:

######  Theorem 1.1 (Uniformization theorem of Koebe and Poincaré).

A connected and simply connected complex curve $\tilde{C}$ is biholomorphic
to:

$\tilde{C}\cong\left\\{\begin{array}[]{ll}{\mathbb{P}}^{1}&\mbox{ if }\ g=0\\\
\mathbb{C}&\mbox{ if }\ g=1\\\ \mathbb{H}&\mbox{ if }\ g\geq 2\\\
\end{array}\right.$

($\mathbb{H}$ denotes as usual the Poincaré upper half-plane
$\mathbb{H}=\\{\tau\in\mathbb{C}:Im(\tau)>0\\}$, but we shall often refer to
it as the ‘disk’ since it is biholomorphic to $\\{z\in\mathbb{C}:||z||<1\\}$).

Hence a smooth (connected) compact complex curve $C$ of genus $g\geq 1$ admits
a uniformization in the strong sense (iii) of the following definition:

######  Definition 1.2.

A connected complex space $X$ of complex dimension $n$ admits a uniformization
if one of the following conditions hold:

  1. (i)

there is a connected open set $\Omega\subset\mathbb{C}^{n}$ and a surjective
holomorphic map $f\colon\Omega\rightarrow X$ (weak uniformization);

  2. (ii)

there is a connected open set $\Omega\subset\mathbb{C}^{n}$ and a properly
discontinuous group ${\Gamma}\subset Aut(\Omega)$ such that
$\Omega/{\Gamma}\cong X$ (Galois uniformization).

If $X$ is a complex manifold, there are two stronger properties:

  1. (iii)

there is a connected open set $\Omega\subset\mathbb{C}^{n}$ and a surjective
holomorphic submersion $f\colon\Omega\rightarrow X$ (étale uniformization);

  2. (iv)

there is a connected open set $\Omega\subset\mathbb{C}^{n}$ biholomorphic to
the universal cover of $X$ (strong uniformization).

Hence the universal cover of a compact complex curve is completely determined
by its genus; in particular $\tilde{C}\cong\mathbb{H}$ if and only if $g\geq
2$, i.e., “$C$ is of general type”, and we get then an isomorphism of
$\pi_{1}(C)$ with a Fuchsian group
${\Gamma}\subset\operatorname{Aut}(\mathbb{H})\cong\operatorname{PSL}(2,\mathbb{R})$.

In higher dimension the condition that the universal cover be biholomorphic to
a bounded domain $\Omega$ is quite exceptional; but still in the Galois étale
case, where $\Omega/{\Gamma}\cong X$ and ${\Gamma}$ acts freely with compact
quotient, we have, if $\Omega$ is bounded, that the complex manifold $X$ has
ample canonical bundle $K_{X}$ (see [Sieg73]), in particular it is a
projective manifold of general type.

Even more exceptional is the case where the universal cover is biholomorphic
to a bounded symmetric domain $\Omega$, or where there is Galois
uniformization (ii) of definition 1.2) with source a bounded symmetric domain,
and there is a vast literature on a characterization of these properties (cf.
[Yau77], [Yau88], [Yau93], [Bea00]).

The basic result in this direction is S.T. Yau’s uniformization theorem
(explained in [Yau88] and [Yau93]), and for which a very readable exposition
is contained in the first section of [V-Z05], enphasyzing the role of
polystability of the cotangent bundle for varieties of general type. One would
wish nevertheless for more precise characterizations of the various possible
cases.

For the sake of simplicity, we shall stick here to the case of smooth complex
surfaces, where the former problem boils down to two very specific questions.

Question. When is the universal cover of a compact complex surface $X$
biholomorphic to the two dimensional ball
${\mathbb{B}}_{2}:=\\{z\in\mathbb{C}^{2}:||z||<1\\}$, respectively to the
bidisk $\mathbb{H}\times\mathbb{H}$ ?

The first part of this question is fully answered by the well-known inequality
by Miyaoka and Yau (cf. [Miy77], [Yau77] [Miy82]). Setting, as usual, $K_{X}=$
the canonical divisor, $\chi(X):=\chi(\mathcal{O}_{X})$ the holomorphic Euler
characteristic and $P_{2}(X)=h^{0}(X,2K_{X})$ the second plurigenus of $X$, we
have the following characterization:

######  Theorem 1.3 (Miyaoka-Yau).

Let $X$ be a compact complex surface. Then $X\cong{\mathbb{B}}_{2}/\Gamma$
(with $\Gamma$ a cocompact discrete subgroup of
$\operatorname{Aut}({\mathbb{B}}_{2})$ acting freely on ${\mathbb{B}}_{2}$) if
and only if

  1. (1)

$K_{X}^{2}=9\chi(S)$;

  2. (2)

the second plurigenus $P_{2}(X)>0$.

The above well known characterization is obtained combining Miyaoka’s result
([Miy82]) that these two conditions imply the ampleness of $K_{X}$, with Yau’s
uniformization result ([Yau77]) which uses the existence of a Kähler Einstein
metric; quite remarkably, it is given purely in terms of certain numbers which
are either bimeromorphic or topological invariants.

In the case where $X=\mathbb{H}\times\mathbb{H}/\Gamma$, with $\Gamma$ a
discrete cocompact subgroup of
$\operatorname{Aut}(\mathbb{H}\times\mathbb{H})$ acting freely, one has
$K_{X}^{2}=8\chi(X)$.

But Moishezon and Teicher in [MT87] showed the existence of a simply connected
surface of general type (whence with $P_{2}(X)>0$) having
$K_{X}^{2}=8\chi(X)$, so that the above conditions are necessary, but not
sufficient. We observe however that (and our contribution here is a by-product
of our attempt to answer the latter question) it is still unknown if there
exists a surface of general type with $\chi(X)=1,K_{X}^{2}=8$ which is not
uniformized by $\mathbb{H}\times\mathbb{H}$.

The purpose of this note is to point out a precise characterization of compact
complex surfaces whose universal cover is the bidisk, and of the quadric
$\mathbb{P}^{1}\times\mathbb{P}^{1}$, discussing whether some hypotheses can
be dispensed with, and to pose an analogous question in higher dimension. Our
characterization, which is of course based on Yau’s results, relies on the
following crucial

######  Definition 1.4.

Let $X$ be a complex manifold of complex dimension $n$.

Then a special tensor is a non zero section $0\neq\omega\in
H^{0}(X,S^{n}\Omega^{1}_{X}(-K_{X}))$, while a semi special tensor is a non
zero section $0\neq\omega\in H^{0}(X,S^{n}\Omega^{1}_{X}(-K_{X})\otimes\eta)$,
where $\eta$ is an invertible sheaf such that $\eta^{2}\cong\mathcal{O}_{X}$.

We shall say that $X$ admits a unique semi special tensor if moreover
$dim(H^{0}(X,S^{n}\Omega^{1}_{X}(-K_{X})\otimes\eta))=1.$

In fact, the existence of such tensors is a fundamental property of manifolds
strongly uniformized by the polydisk as we are now going to see.

Recall that the group of automorphism of $\mathbb{H}^{n}$,
$\operatorname{Aut}(\mathbb{H}^{n})$, is the semidirect product of
$(\operatorname{Aut}(\mathbb{H}))^{n}$ with the symmetric group
${\mathfrak{S}}_{n}$, hence for every subgroup ${\Gamma}$ of
$\operatorname{Aut}(\mathbb{H}^{n})$ we have a diagram:

$\begin{array}[]{ccccccc}1\rightarrow&(\operatorname{Aut}(\mathbb{H}))^{n}&\rightarrow&\operatorname{Aut}(\mathbb{H}^{n})&\rightarrow{\mathfrak{S}}_{n}&\rightarrow
1\\\ &\bigcup&&\bigcup&\bigcup&\\\
1\rightarrow&\Gamma^{0}&\hookrightarrow&\Gamma&\rightarrow H&\rightarrow 1.\\\
\end{array}$

######  Proposition 1.5.

Let $X=\mathbb{H}^{n}/{\Gamma}$ be a compact complex manifold whose universal
covering is the polydisk $\mathbb{H}^{n}$: then $X$ admits a semi special
tensor and $K_{X}$ is ample, in particular $K_{X}^{n}>0$.

###### Proof.

In $\mathbb{H}^{n}$ take coordinates $\\{z_{1},\dots,z_{n}\\}$ and define

$\tilde{\omega}:=\frac{\operatorname{d}z_{1}\otimes\dots\otimes\operatorname{d}z_{n}}{\operatorname{d}z_{1}\wedge\dots\wedge\operatorname{d}z_{n}}.$

Observe that $\tilde{\omega}$ is clearly invariant for
$(\operatorname{Aut}(\mathbb{H}))^{n}$ and for the alternating subgroup. Let
$\eta$ be the 2-torsion invertible sheaf associated to the signature character
of ${\mathfrak{S}}_{n}$ restricted to $H$. Then clearly $\tilde{\omega}$
descends to a semi special tensor $\omega\in
H^{0}(X,S^{n}\Omega^{1}_{X}(-K_{X})\otimes\eta)$.

The other assertions are well known (cf. [Sieg73] and [K-M71]). ∎

######  Remark 1.6.

We observe that also $(\mathbb{P}^{1})^{n}$ admits the following special
tensor $\omega$, given on $\mathbb{C}^{n}\subset(\mathbb{P}^{1})^{n}$ by
$\omega:=\frac{\operatorname{d}z_{1}\otimes\dots\otimes\operatorname{d}z_{n}}{\operatorname{d}z_{1}\wedge\dots\wedge\operatorname{d}z_{n}}.$

In dimension two we have then the following

######  Theorem 1.7.

Let $X$ be a compact complex surface.

Then the following two conditions:

  1. (1)

$X$ admits a semi special tensor;

  2. (2)

$K_{X}^{2}>0$

hold if and only if either

  1. (i)

$X\cong\mathbb{P}^{1}\times\mathbb{P}^{1}$; or

  2. (ii)

$X\cong\mathbb{H}\times\mathbb{H}/\Gamma$ (where $\Gamma$ is a cocompact
discrete subgroup of $\operatorname{Aut}(\mathbb{H}\times\mathbb{H})$ acting
freely ).

In particular one has the following reformulation of a theorem of S.T. Yau
(theorem 2.5 of [Yau93], giving sufficient conditions for (ii) to hold).

######  Theorem 1.8.

(Yau) $X$ is strongly uniformized by the bidisk if and only if

  1. (1)

$X$ admits a semi special tensor;

  2. (2)

$K_{X}^{2}>0$;

  3. (3)

the second plurigenus $P_{2}(X)\geq 1$.

One can indeed be even more precise:

######  Theorem 1.9.

$X$ is strongly uniformized by the bidisk if and only if

  1. (1*)

$X$ admits a unique semi special tensor;

  2. (2)

$K_{X}^{2}>0$;

  3. (3*)

the second plurigenus $P_{2}(X)\geq 2$.

$X$ is biholomorphic to $\mathbb{P}^{1}\times\mathbb{P}^{1}$ if and only if
(1*), (2) hold and $P_{2}(X)=0.$

It is interesting to see that none of the above hypotheses can be dispensed
with.

######  Remark 1.10.

The following examples show the existence of surfaces which satisfy two of the
three conditions stated in Thm. 1.8, respectively in Thm. 1.9, but are not
uniformized by the bidisk

  1. (i)

$\mathbb{P}^{1}\times\mathbb{P}^{1}$ satisfies (1*) and (2);

  2. (ii)

A complex torus $X=\mathbb{C}^{2}/\Lambda$ satisfies (1)  and (3), but neither
(1*) nor (3*) (obviously, it does not satisfy (2));

  3. (iii)

$X=C_{1}\times C_{2}$ with $g(C_{1})=1$, $g(C_{2})=2$ satisfies (1*) and (3*),
but its universal cover is $\tilde{X}\cong\mathbb{C}\times\mathbb{H}$.

The most intriguing examples are provided by

######  Proposition 1.11.

There do exist properly elliptic surfaces $X$ satisfying

  * •

(1) $X$ admits a special tensor;

  * •

(3*) the second plurigenus $P_{2}(X)\geq 2$;

  * •

$q(X):=dim(H^{1}(\mathcal{O}_{X}))>0$;

  * •

$K_{X}^{2}=0$;

  * •

$X$ is not birational to a product.

We would like to pose then the following

Question. Let $X$ be a surface with $q(X)=0$ and satisfying (1*) and (3*): is
then $X$ strongly uniformized by the bidisk?

Concerning the above question, recall the following

######  Definition 1.12.

$\Gamma\subset\operatorname{Aut}(\mathbb{H}^{n})$ is said to be reducible if
there exists $\Gamma^{0}$ as above (i.e., such that
$\gamma(z_{1},...,z_{n})=(\gamma_{1}(z_{1}),...,\gamma_{n}(z_{n}))$ for every
$\gamma\in\Gamma^{0}$) and a decomposition
$\mathbb{H}^{n}=\mathbb{H}^{k}\times\mathbb{H}^{h}$ (with $h>0$) such that the
action of $\Gamma^{0}$ on $\mathbb{H}^{k}$ is discrete.

For $n=2$ there are then only two alternatives:

######  Remark 1.13.

Let $\Gamma\subset\operatorname{Aut}(\mathbb{H}^{2})$ be a discrete cocompact
subgroup acting freely and let $X=\mathbb{H}^{2}/\Gamma$. Then

  * •

$\Gamma$ is reducible if and only if $X$ is isogenous to a product of curves,
i.e., there is a finite group $G$ and two curves of genera at least 2 such
that $X\cong C_{1}\times C_{2}/G$. Both cases $q(X)\neq 0$, $q(X)=0$ can occur
here.

  * •

$\Gamma$ is irreducible and $q(X)=0$ ( this result holds in all dimensions and
is a well-known result of Matsushima [Ma62]).

Let us try to explain the main idea of our main result. In order to do this,
it is important to make the following

######  Remark 1.14.

A complex manifold $X$ admits a semi special tensor if and only if it has an
unramified cover $X^{\prime}$ of degree at most two which admits a special
tensor.

###### Proof.

Assume that we have an invertible sheaf $\eta$ such that
$\eta^{2}\cong\mathcal{O}_{X}$, $\eta\not\cong\mathcal{O}_{X}$. Take the
corresponding double connected étale covering $\pi:X^{\prime}\rightarrow X$
and observe that

$H^{0}(X^{\prime},S^{n}\Omega^{1}_{X^{\prime}}(-K_{X^{\prime}}))\cong
H^{0}(X,S^{n}\Omega^{1}_{X}(-K_{X}))\oplus
H^{0}(X,S^{n}\Omega^{1}_{X}(-K_{X})\otimes\eta).$

Whence, there is a special tensor on $X^{\prime}$ if and only if there is a
semi special tensor on $X$. ∎

In dimension $n=2$ things are easier, since the existence of a special tensor
$\omega$ is equivalent to the existence of a trace free endomorphism
$\epsilon$ of the tangent bundle of $X$.

Our proof of Theorem 1.7 consists essentially in finding a decomposition of
the tangent bundle $T_{X}$ as a direct sum of two line bundles $L_{1}$ and
$L_{2}$, which are the eigenbundles of an invertible endomorphism
$\epsilon\in\operatorname{End}(T_{X})$ (see §2 and §3 for details), and then
applying the results on surfaces with split tangent bundles as given in
[Bea00].

Since the results on manifolds with split tangent bundles hold in dimension
$n\geq 3$, one has a characterization of compact manifolds strongly
uniformized by the polydisk under a very strong condition on the semi special
tensor $\omega\in H^{0}(X,S^{n}\Omega^{1}_{X}(-K_{X})\otimes\eta)$, which
essentially corresponds to ask for the local splitting of $\omega$ as the
product of $n$ 1-forms which are linearly independent at each point. There
remains the problem of finding a simpler characterization.

##  2\. Preliminaries and remarks

Notation. $X$ denotes throughout a compact complex surface. We use standard
notation of algebraic geometry: $\Omega^{1}_{X}$ is the cotangent sheaf,
$T_{X}$ is the holomorphic tangent bundle (locally free sheaf), $c_{1}(X)$,
$c_{2}(X)$ are the Chern classes of $X$; $K_{X}$ is the canonical divisor, and
$P_{n}:=h^{0}(X,nK_{X})$ is called the $n$-th plurigenus, in particular for
$n=1$ we have the geometric genus of $X$ $p_{g}(X):=h^{0}(X,K_{X})$, while
$q:=h^{1}(X,\mathcal{O}_{X})$ is classically called the irregularity of $X$.
Finally, $\chi(X):=\chi(\mathcal{O}_{X})=1+p_{g}-q$ is the holomorphic Euler
characteristic.

With a slight abuse of notation, we do not distinguish between invertible
sheaves, line bundles and divisors, while the symbol $\equiv$ denotes linear
equivalence of divisors.

First of all let us recall a result of Beauville which characterizes compact
complex surfaces whose universal cover is a product of two complex curves (cf.
[Bea00, Thm. C]).

######  Theorem 2.1 (Beauville).

Let $X$ be a compact complex surface. The tangent bundle $T_{X}$ splits as a
direct sum of two line bundles if and only if either $X$ is a special Hopf
surface or the universal covering space of $X$ is a product $U\times V$ of two
complex curves and the group $\pi_{1}(X)$ acts diagonally on $U\times V$.

Given a direct sum decomposition of the cotangent bundle $\Omega^{1}_{X}\cong
L_{1}\oplus L_{2}$, Beauville shows that $(L_{1})^{2}=(L_{2})^{2}=0$ (cf.
[Bea00, 4.1, 4.2]) hence

$K_{X}\equiv L_{1}+L_{2}\hskip 28.45274ptc_{1}(X)^{2}=2\cdot(L_{1}\cdot
L_{2})=2\cdot c_{2}(X)$

The last equality corresponds to $K_{X}^{2}=8\chi(X)$.

Let us now consider the bundle $\operatorname{End}(T_{X})$ of endomorphisms of
the tangent bundle. We can write
$\operatorname{End}(T_{X})=\Omega^{1}_{X}\otimes T_{X}$ and from the
nondegenerate bilinear map

$\Omega^{1}_{X}\times\Omega^{1}_{X}\longrightarrow\Omega^{2}_{X}\cong K_{X}$

we see that $T_{X}=(\Omega^{1}_{X})^{\vee}\cong\Omega^{1}_{X}(-K_{X})$. This
exactly means that we have an isomorphism
$\operatorname{End}(T_{X})\cong\Omega^{1}_{X}\otimes\Omega^{1}_{X}(-K_{X}).$

Let us see how this isomorphism works in local coordinates $(z_{1},z_{2})$.
I.e., let us see how an element
$\frac{\operatorname{d}z_{i}\otimes\operatorname{d}z_{j}}{\operatorname{d}z_{1}\wedge\operatorname{d}z_{2}}$
in $\Omega^{1}_{X}\otimes\Omega^{1}_{X}(-K_{X})$ acts on a vector of the form
$\frac{\partial}{\partial z_{h}}$. We have

$\frac{\operatorname{d}z_{i}\otimes\operatorname{d}z_{j}}{\operatorname{d}z_{1}\wedge\operatorname{d}z_{2}}\bigl{(}\frac{\partial}{\partial
z_{h}}\bigr{)}=\left\\{\begin{array}[]{cl}\frac{\operatorname{d}z_{j}}{\operatorname{d}z_{1}\wedge\operatorname{d}z_{2}}&\mbox{
if }h=i\\\ 0&\mbox{ if }h\neq i\\\ \end{array}\right.$

In turn,
$\displaystyle{\frac{\operatorname{d}z_{j}}{\operatorname{d}z_{1}\wedge\operatorname{d}z_{2}}}$
evaluated on $\operatorname{d}z_{k}$ gives
$\displaystyle{\frac{\operatorname{d}z_{j}\wedge\operatorname{d}z_{k}}{\operatorname{d}z_{1}\wedge\operatorname{d}z_{2}}}$.

Therefore a generic element
$\displaystyle{\sum_{i,j}a_{ij}\frac{\operatorname{d}z_{i}\otimes\operatorname{d}z_{j}}{\operatorname{d}z_{1}\wedge\operatorname{d}z_{2}}}$
corresponds to an endomorphism, which, with respect to the basis
$\bigl{\\{}\frac{\partial}{\partial z_{1}},\frac{\partial}{\partial
z_{2}}\bigr{\\}}$ is expressed by the matrix

$\begin{pmatrix}-a_{12}&-a_{22}\\\ a_{11}&a_{21}\\\ \end{pmatrix}$

In particular for the symmetric tensors (i.e., $a_{12}=a_{21}$), respectively
for the skewsymmetric tensors (i.e., $a_{12}=-a_{21},a_{11}=a_{22}=0$) the
following isomorphisms hold:

$S^{2}(\Omega^{1}_{X})(-K_{X})\cong\bigg{\\{}\begin{pmatrix}-a&-a_{22}\\\
a_{11}&a\\\ \end{pmatrix}\bigg{\\}}\ ;\ \ \hskip
14.22636pt{\bigwedge}^{2}(\Omega^{1}_{X})(-K_{X})\cong\bigg{\\{}\begin{pmatrix}b&0\\\
0&b\\\ \end{pmatrix}\bigg{\\}}$

We can summarize the above discussion in the following

######  Lemma 2.2.

If $X$ is a complex surface there is a natural isomorphism between the sheaf
$S^{2}(\Omega^{1}_{X})(-K_{X})$ and the sheaf of trace zero endomorphisms of
the (co)tangent sheaf
$\operatorname{End}^{0}(T_{X})\cong\operatorname{End}^{0}(\Omega^{1}_{X})$.

A special tensor $\omega\in H^{0}(S^{2}(\Omega^{1}_{X})(-K_{X}))$ with nonzero
determinant $det(\omega)\in\mathbb{C}$ yields an eigenbundle splitting
$\Omega^{1}_{X}\cong L_{1}\bigoplus L_{2}$ of the cotangent bundle.

If instead $det(\omega)=0\in\mathbb{C}$, the corresponding endomorphism
$\epsilon$ is nilpotent and yields an exact sequence of sheaves

$0\rightarrow
L\rightarrow\Omega^{1}_{X}\rightarrow{\mathcal{I}}_{Z}L(-\Delta)\rightarrow 0$

where $L:=ker(\epsilon)$ is invertible, $\Delta$ is an effective divisor, and
$Z$ is a 0-dimensional subscheme(which is a local complete intersection).

We have in particular $K_{X}\equiv 2L-\Delta$ and
$c_{2}(X)={length}(Z)+L\cdot(L-\Delta)$.

Proof. We need only to observe that $det(\omega)$ is a constant, since
$det(\operatorname{End}(T_{X}))=det(\operatorname{End}(\Omega^{1}_{X}))\cong\mathcal{O}_{X}$.

If $det(\omega)\neq 0$, there is a constant $c\in\mathbb{C}\setminus\\{0\\}$
such that $det(\omega)=c^{2}$, hence at every point of $X$ the endomorphism
$\epsilon$ corresponding to the special tensor $\omega$ has two distinct
eigenvalues $\pm c$.

Let $\omega\in H^{0}(S^{2}\Omega^{1}_{X}(-K_{X}))$, $\omega\neq 0$, be such
that $\det(\omega)=0$. Then the corresponding endomorphism $\epsilon$ is
nilpotent of order 2, and there exists an open nonempty subset $U\subseteq X$
such that
$\operatorname{Ker}(\epsilon_{|U})=\operatorname{Im}(\epsilon_{|U})$. At a
point $p$ where $\operatorname{rank}(\epsilon)=0$, in local coordinates the
endomorphism $\epsilon$ may be expressed by

$\begin{pmatrix}a&b\\\ c&-a\\\ \end{pmatrix}\ \ a,b,c\mbox{ regular functions
such that }a^{2}=-b\cdot c$

Let $\delta:=\operatorname{G.C.D.}(a,b,c)$. After dividing by $\delta$, every
prime factor of $a$ is either not in $b$, or not in $c$, thus we can write

$-b=\beta^{2}\hskip 28.45274ptc=\gamma^{2}\hskip 28.45274pta=\beta\cdot\gamma$

Therefore we obtain

$\begin{pmatrix}u\\\ v\\\
\end{pmatrix}\in\operatorname{Ker}{\epsilon}\Longleftrightarrow\left\\{\begin{array}[]{l}a\cdot
u+b\cdot v=0\\\ c\cdot u-a\cdot
v=0\end{array}\right.\Longleftrightarrow\gamma\cdot u-\beta\cdot
v=0\Longleftrightarrow\begin{pmatrix}u\\\ v\\\
\end{pmatrix}=\begin{pmatrix}\beta\cdot f\\\ \gamma\cdot f\\\ \end{pmatrix}$

and, writing our endomorphism $\epsilon$ as $\epsilon=\delta\cdot\alpha$, we
have

$\operatorname{Im}(\alpha)=\left\\{\begin{array}[]{l}\beta\cdot\gamma\cdot
u-\beta^{2}\cdot v=\beta\cdot(\gamma\cdot u-\beta\cdot v)\\\ \gamma^{2}\cdot
u-\gamma\cdot\beta\cdot v=\gamma\cdot(\gamma\cdot u-\beta\cdot
v)\end{array}\right.$

Let $Z$ be the 0-dimensional scheme defined by $\\{\beta=\gamma=0\\}$ and
$\Delta$ be the Cartier divisor defined by $\\{\delta=0\\}$.

From the above description we deduce that the kernel of $\epsilon$ is a line
bundle $L$ which fits in the following exact sequence:

$0\rightarrow
L\rightarrow\Omega^{1}_{X}\rightarrow{\mathcal{I}}_{Z}L(-\Delta)\rightarrow
0.$

Taking the total Chern classes we infer that: $K_{X}\equiv 2L-\Delta$ as
divisors on $X$ and $c_{2}(X)={length}(Z)+L\cdot(L-\Delta)$. ∎

######  Lemma 2.3.

Let $X$ be a complex surface and let $X^{\prime}$ be the blow up of $X$ at a
point $p$. Then a special tensor $\omega^{\prime}$ on $X^{\prime}$ induces a
special tensor $\omega$ on $X$, and the converse only holds if and only if
$\omega$ vanishes at $p$ (in particular, it must hold : $det(\omega)=0$).

Proof. First of all, $\omega^{\prime}$ induces a special tensor on
$X\setminus\\{p\\}$, and by Hartogs’ theorem the latter extends to a special
tensor $\omega$ on $X$.

Conversely, choose local coordinates $(x,y)$ for $X$ around $p$ and take a
local chart of the blow up with coordinates $(x,u)$ where $y=ux$. Locally
around $p$ we can write

$\omega=\frac{a(\operatorname{d}x)^{2}+b(\operatorname{d}y)^{2}+c(\operatorname{d}x\operatorname{d}y)}{\operatorname{d}x\wedge\operatorname{d}y}.$

The pull back $\omega^{\prime}$ of $\omega$ is given by the following
expression:

$\frac{a(\operatorname{d}x)^{2}+b(u\operatorname{d}x+x\operatorname{d}u)^{2}+c(u\operatorname{d}x+x\operatorname{d}u)\operatorname{d}x}{x\operatorname{d}x\wedge\operatorname{d}u}=$

$=\frac{\operatorname{d}x^{2}(a+bu^{2}+cu)+bx^{2}\operatorname{d}u^{2}+(2bux+cx)\operatorname{d}x\operatorname{d}u}{x\operatorname{d}x\wedge\operatorname{d}u},$

hence $\omega^{\prime}$ is regular if and only if $\frac{a+bu^{2}+cu}{x}$ is a
regular function.

This is obvious if $a,b,c$ vanish at $p$, since then their pull back is
divisible by $x$. Assume on the other side that $a,b,c$ are constant: then we
get a rational function which is only regular if $a=b=c=0.$

∎

######  Lemma 2.4.

Let $X$ be a compact minimal rational surface admitting a special tensor
$\omega$. Then $X\cong\mathbb{P}^{1}\times\mathbb{P}^{1}$ if $det(\omega)\neq
0$.

Proof. Assume that $X$ is a $\mathbb{P}^{1}$ bundle over a curve
$B\cong\mathbb{P}^{1}$, i.e., a ruled surface ${\bf F}_{n}$ with $n\geq 0$.
Let $\pi\colon X\rightarrow B$ the projection.

By the exact sequence

$0\rightarrow\pi^{*}\Omega^{1}_{B}\rightarrow\Omega^{1}_{X}\rightarrow\Omega^{1}_{X|B}\rightarrow
0$

and since on a general fibre $F$ the subsheaf $\pi^{*}\Omega^{1}_{B}$ is
trivial, while the quotient sheaf $\Omega^{1}_{X|B}$ is negative, we conclude
that any endomorphism $\epsilon$ carries $\pi^{*}\Omega^{1}_{B}$ to itself. If
it has non zero determinant we can conclude by Theorem 2.1 that
$X\cong\mathbb{P}^{1}\times\mathbb{P}^{1}$. Otherwise, $\epsilon$ is nilpotent
and we have a nonzero element in ${\rm
Hom}(\Omega^{1}_{X|B},\pi^{*}\Omega^{1}_{B})$.

Since these are invertible sheaves, it suffices to see when

$H^{0}(\mathcal{O}_{X}(2\pi^{*}K_{B}-K_{X}))\neq 0.$

But, letting $\Sigma$ be the section with selfintersection $\Sigma^{2}=-n$,
our vector space equals $H^{0}(\mathcal{O}_{X}(2\Sigma-(n+2)F)).$ Intersecting
this divisor with $\Sigma$ we see that (since each time the intersection
number with $\Sigma$ is negative)
$H^{0}(\mathcal{O}_{X}(2\Sigma-(n+2)F))=H^{0}(\mathcal{O}_{X}(\Sigma-(n+2)F))=H^{0}(\mathcal{O}_{X}(-(n+2)F))=0.$

There remains the case where $X$ is $\mathbb{P}^{2}$.

In this case $\epsilon$ must be a nilpotent endomorphism by Theorem 2.1, and
it cannot vanish at any point by our previous result on ${\bf F}_{1}$.
Therefore the rank of $\epsilon$ equals 1 at each point. By lemma 2.2 it
follows that there is a divisor $L$ such that $K_{X}=2L$, a contradiction.

∎

##  3\. Proof of Theorems 1.7 and 1.9

###### Proof.

If $X$ is strongly uniformized by the bidisk, then $K_{X}$ is ample, in
particular $K^{2}_{X}\geq 1$ and, since by Castelnuovo’s theorem $\chi(X)\geq
1$, by the vanishing theorem of Kodaira and Mumford it follows that
$P_{2}(X)\geq 2$ (see [Bom73]).

Thus one direction follows from proposition 1.5, except that we shall show
only later that (1*) holds.

Assume conversely that $(1),(2)$ hold. Without loss of generality we may
assume by lemma 2.3 that $X$ is minimal, since $K_{X}^{2}$ can only decrease
via a blowup and the bigenus is a birational invariant.

$K^{2}_{X}\geq 1$ implies that either the surface $X$ is of general type, or
it is a rational surface. In the latter case we conclude by lemma 2.4.

Observe that the further hypothesis (3) (obviously implied by (3*)) guarantees
that $X$ is of general type.

Thus, from now on, we may assume that $X$ is of general type and, passing to
an étale double cover if necessary, that $X$ admits a special tensor.

By the cited Theorem 2.1 of [Bea00] it suffices to find a decomposition of the
cotangent bundle $\Omega^{1}_{X}$ as a direct sum of two line bundles $L_{1}$
and $L_{2}$.

The two line bundles $L_{1}$, $L_{2}$ will be given as eigenbundles of a
diagonizable endomorphism $\epsilon\in\operatorname{End}(\Omega^{1}_{X})$.

Our previous discussion shows then that it is sufficient to show that any
special tensor cannot yield a nilpotent endomorphism.

Otherwise, by lemma 2.2, we can write $2L\equiv K_{X}+\Delta$ and then deduce
that $L$ is a big divisor since $\Delta$ is effective by construction and
$K_{X}$ is big because $X$ is of general type. This assertion gives the
required contradiction since by the Bogomolov-Castelnuovo-de Franchis Theorem
(cf. [Bog77]) for an invertible subsheaf $L$ of $\Omega^{1}_{X}$ it is
$h^{0}(X,mL)\leq O(m)$, contradicting the bigness of $L$.

There remains to show (1*). But if $h^{0}(X,S^{2}\Omega^{1}_{X}(-K_{X}))\geq
2$ then, given a point $p\in X$, there is a special tensor which is not
invertible in $p$, hence a special tensor with vanishing determinant, a
contradiction.

∎

##  4\. Proof of proposition 1.11

In this section we consider surfaces $X$ with bigenus $P_{2}(X)\geq 2$
(property (3*)), therefore their Kodaira dimension equals 1 or 2, hence either
they are properly (canonically) elliptic, or they are of general type.

Since we took already care of the latter case in the main theorems 1.7 and
1.9, we restrict our attention here to the former case, and try to see when
does a properly elliptic surface admit a special tensor (we can reduce to this
situation in view of remark 1.14). We can moreover assume that the associated
endomorphism $\epsilon$ is nilpotent by theorem 2.1.

Again without loss of generality we may assume that $X$ is minimal by virtue
of lemma 2.3.

Proof. Let $X$ be a minimal properly elliptic surface and let $f:X\rightarrow
B$ be its (multi)canonical elliptic fibration. Write any fibre $f^{-1}(p)$ as
$F_{p}=\sum_{i=1}^{h_{p}}m_{i}C_{i}$ and, setting $n_{p}:=G.C.D.(m_{i})$,
$F_{p}=n_{p}F^{\prime}_{p}$, we say that a fibre is multiple if $n_{p}>1$. By
Kodaira’s classification ([Kod60]) of the singular fibres we know that in this
case $m_{i}=n_{p},\forall i.$

Assume that the multiple fibres of the elliptic fibration are
$n_{1}F_{1}^{\prime},\dots,n_{r}F_{r}^{\prime}$, and consider the divisorial
part of the critical locus

$\mathcal{S}_{p}:=\sum_{i=1}^{h_{p}}(m_{i}-1)C_{i},\ \ \mathcal{S}:=\sum_{p\in
B}\mathcal{S}_{p}$

so that we have then the exact sequence

$0\rightarrow
f^{*}\Omega^{1}_{B}(\mathcal{S})\rightarrow\Omega^{1}_{X}\rightarrow\mathcal{I}_{{\mathcal{C}}}\
\omega_{X|B}\rightarrow 0,$

where ${\mathcal{C}}$ is a 0-dimensional (l.c.i.) subscheme.

For further calculations we separate the divisorial part of the critical locus
as the sum of two disjoint effective divisors, the multiple fibre contribution
and the rest:

$\mathcal{S}_{m}:=\sum_{i=1}^{r}(n_{i}-1)F^{\prime}_{i},\
\hat{\mathcal{S}}:=\mathcal{S}-\mathcal{S}_{m}.$

Let us assume that we have a nilpotent endomorphism corresponding to another
exact sequence

$0\rightarrow
L\rightarrow\Omega^{1}_{X}\rightarrow{\mathcal{I}}_{Z}L(-\Delta)\rightarrow
0,$

in turn determined by a homomorphism

$\epsilon^{\prime}:{\mathcal{I}}_{Z}L(-\Delta)\rightarrow L,$

i.e., by a section

$s\in H^{0}(\mathcal{O}_{X}(\Delta))=$
$=H^{0}(\mathcal{O}_{X}(2L-K_{X}))=H^{0}(S^{2}(L)(-K_{X}))\subset
H^{0}(S^{2}(\Omega^{1}_{X})(-K_{X})).$

We observe that, since $2L\equiv K_{X}+\Delta$, it follows that, if $F$ is a
general fibre, then

$L\cdot F=\Delta\cdot F=0,$

hence the effective divisor $\Delta$ is contained in a finite union of fibres.

The first candidate to try with is the choice of $L=L^{\prime}$, where we set
$L^{\prime}:=f^{*}\Omega^{1}_{B}(\mathcal{S})$.

To this purpose we recall Kodaira’s canonical bundle formula:

$K_{X}\equiv\mathcal{S}_{m}+f^{*}(\delta)=\sum_{i=1}^{r}(n_{i}-1)F^{\prime}_{i}+f^{*}(\delta),\
deg(\delta)=\chi(X)-2+2b,$

where $b$ is the genus of the base curve $B$.

Then
$H^{0}(\mathcal{O}_{X}(2L^{\prime}-K_{X}))=H^{0}(\mathcal{O}_{X}(f^{*}(2K_{B}-\delta)+2\mathcal{S}-\mathcal{S}_{m})$,
and we search for an effective divisor linearly equivalent to

$f^{*}(2K_{B}-\delta)+2\mathcal{S}-\mathcal{S}_{m}=f^{*}(2K_{B}-\delta)+2\hat{\mathcal{S}}+\mathcal{S}_{m}.$

We claim that
$H^{0}(\mathcal{O}_{X}(2L^{\prime}-K_{X}))=H^{0}(\mathcal{O}_{X}(f^{*}(2K_{B}-\delta))$:
it will then suffice to have examples where $|2K_{B}-\delta|\neq\emptyset.$

Proof of the claim

It suffices to show that
$f_{*}\mathcal{O}_{X}(2\hat{\mathcal{S}}+\mathcal{S}_{m})=\mathcal{O}_{B}$.
Since the divisor $2\hat{\mathcal{S}}+\mathcal{S}_{m}$ is supported on the
singular fibres, and it is effective, we have to show that, for each singular
fibre $F_{p}=\sum_{i=1}^{h_{p}}m_{i}C_{i}$, neither
$2\hat{\mathcal{S}}_{p}\geq F_{p}$ nor ${\mathcal{S}_{m}}_{,p}\geq F_{p}$.

The latter case is obvious since
${\mathcal{S}_{m}}_{,p}=(n_{p}-1)F^{\prime}_{p}<F_{p}=n_{p}F^{\prime}_{p}$.

In the former case,
$2\hat{\mathcal{S}}_{p}=\sum_{i=1}^{h_{p}}2(m_{i}-1)C_{i}$, but it is not
possible that $\forall i$ one has $2(m_{i}-1)\geq m_{i}$, since there is
always an irreducible curve $C_{i}$ with multiplicity $m_{i}=1$.

$Q.E.D.$for the claim

Assume that the elliptic fibration is not a product (in this case there is no
special tensor with vanishing determinant): then the irregularity of $X$
equals the genus of $B$, whence our divisor on the curve $B$ has degree equal
to $2b-2-(1-b+p_{g}(X))=3b-3-p_{g}.$

Since $\chi(X)\geq 1$, $p_{g}:=p_{g}(X)\geq b$, and there exist an elliptic
surface $X$ with any $p_{g}\geq b$ ([Cat07]).

Since any divisor on $B$ of degree $\geq b$ is effective, it suffices to
choose $b\leq p_{g}\leq 2b-3$ and we get a special tensor with trivial
determinant, provided that $b\geq 3$.

Take now a Jacobian elliptic surface in Weierstrass normal form

$ZY^{2}-4X^{3}-g_{2}XZ^{2}-g_{3}Z^{3}=0,$

where $g_{2}\in H^{0}(\mathcal{O}_{B}(4M))$, $g_{3}\in
H^{0}(\mathcal{O}_{B}(6M))$, and assume that all the fibres are irreducible.

Then the space of special tensors corresponding to our choice of $L$
corresponds to the vector space
$H^{0}(\mathcal{O}_{B}(2K_{B}-\delta))=H^{0}(\mathcal{O}_{B}(K_{B}-6M))$. It
suffices to take a hyperelliptic curve $B$ of genus $b=6h+1$, and, denoting by
$H$ the hyperelliptic divisor, set $M:=hH$, so that $K_{B}-6M\equiv 0$ and we
have $h^{0}(\mathcal{O}_{X}(2L-K_{X}))=1$. We leave aside for the time being
the question whether the surface $X$ admits a unique special tensor.

∎

Acknowledgements.

These research was performed in the realm of the SCHWERPUNKT ”Globale Methoden
in der komplexen Geometrie”, and of the FORSCHERGRUPPE 790 ‘Classification of
algebraic surfaces and compact complex manifolds’.

The second author thanks the Universität Bayreuth for its warm hospitality in
the months of november and december 2006 (where the research was begun) and
the DFG for supporting his visit.

We would like to thank Eckart Viehweg and Kang Zuo for pointing out some
aspects of Yau’s uniformization theorem that we had not properly credited in
the first version.

## References

  * [BPV84] W. Barth, C. Peters, A. Van de Ven, Compact complex surfaces. Ergebnisse der Mathematik und ihrer Grenzgebiete (3). Springer-Verlag, Berlin,(1984).
  * [Bea00] A. Beauville, Complex manifolds with split tangent bundle Complex analysis and algebraic geometry, de Gruyter, Berlin, 2000, 61–70.
  * [Bog77] F. A. Bogomolov Families of curves on a surface of general type (Russian) Dokl. Akad. Nauk SSSR, 236 no. 5, 1977 , p.1041–1044.
  * [Bom73] E. Bombieri, Canonical models of surfaces of general type, Publ. Math. I.H.E.S., 42 (1973), 173–219.
  * [Cat07] F. Catanese, “Q.E.D. for algebraic varieties”, Jour. Diff. Geom. 77 no. 1 (2007) 43–75
  * [Kod60] K. Kodaira, On compact complex analytic surfaces, I, Ann. of Math. 71  (1960), 111–152.
  * [K-M71] Kodaira, K. Morrow, J. Complex manifolds Holt, Rinehart and Winston, Inc., New-York-Montreal, Que.-London, 1971
  * [Ma62] Y . Matsushima, On the first Betti number of compact quotient spaces of higher-dimensional symmetric spaces Ann. of Math. (2) 75, 1962, 312–330
  * [MT87] B.Moishezon, M. Teicher, Simply-connected algebraic surfaces of positive index Invent. Math. 89 (1987), no. 3, 601–643.
  * [Miy77] Y. Miyaoka, On the Chern numbers of surfaces of general type Invent. Math. 42 (1977), 225–237.
  * [Miy82] Y. Miyaoka, Algebraic surfaces with positive indices Classification of algebraic and analytic manifolds (Katata, 1982), Progr. Math. 39 Birkh user Boston, Boston, MA, (1983) 281–301
  * [Mu79] D. Mumford, An algebraic surface with $K$ ample, $K^{2}=9$, $p_{g}=q=0$ Amer. J. Math. 101, no. 1, (1979), 233 244.
  * [Sieg73] C.L. Siegel, Topics in complex function theory. Vol. III. Abelian functions and modular functions of several variables.  Translated from the German by E. Gottschling and M. Tretkoff. With a preface by Wilhelm Magnus. Reprint of the 1973 original. Wiley Classics Library. A Wiley-Interscience Publication. John Wiley and Sons, Inc., New York (1989), x+244 pp.
  * [V-Z05] E. Viehweg, K. Zuo, Arakelov inequalities and the uniformization of certain rigid Shimura varieties, arXiv:math/0503339.
  * [Yau77] S. T. Yau, Calabi’ s conjecture and some new results in algebraic geometry Proc. Nat. Acad. Sci. USA 74 (1977), 1798–1799
  * [Yau88] S. T. Yau, Uniformization of geometric structures. The mathematical heritage of Hermann Weyl (Durham, NC, 1987), Proc. Sympos. Pure Math., 48, Amer. Math. Soc., Providence, RI (1988), 265–274.
  * [Yau93] S. T. Yau, A splitting theorem and an algebraic geometric characterization of locally hermitian symmetric spaces Comm. in Analysis and Geometry 1 (1993), 473–486

Authors’ addresses:

Prof. Fabrizio Catanese
Lehrstuhl Mathematik VIII, Universität Bayreuth, NWII
D-95440 Bayreuth, Germany
e-mail<EMAIL_ADDRESS>

Marco Franciosi
Dipartimento di Matemativa Applicata ”U. Dini”, Università di Pisa
via Buonarroti 1C, I-56127, Pisa, Italy
e-mail<EMAIL_ADDRESS>


# Fair and Truthful Allocations Under Leveled Valuations

George Christodoulou  Archimedes/Athena RC  Aristotle University of
Thessaloniki  Vasilis Christoforidis  Archimedes/Athena RC  Aristotle
University of Thessaloniki

###### Abstract

We study the problem of fairly allocating indivisible goods among agents which
are equipped with leveled valuation functions. Such preferences, that have
been studied before in economics and fair division literature, capture a
simple and intuitive economic behavior; larger bundles are always preferred to
smaller ones. We provide a fine-grained analysis for various subclasses of
leveled valuations focusing on two extensively studied notions of fairness,
(approximate) MMS and EFX. In particular, we present a general positive
result, showing the existence of $2/3$-MMS allocations under valuations that
are both leveled and submodular. We also show how some of our ideas can be
used beyond the class of leveled valuations; for the case of two submodular
(not necessarily leveled) agents we show that there always exists a $2/3$-MMS
allocation, complementing a recent impossibility result. Then, we switch to
the case of subadditive and fractionally subadditive leveled agents, where we
are able to show tight (lower and upper) bounds of $1/2$ on the approximation
factor of MMS. Moreover, we show the existence of exact EFX allocations under
general leveled valuations via a simple protocol that in addition satisfies
several natural economic properties. Finally, we take a mechanism design
approach and we propose protocols that are both truthful and approximately
fair under leveled valuations.

##  1 Introduction

Allocating indivisible resources in a fair manner has been of central
importance in economics and computer science. The fundamental notions of
proportionality and envy-freeness provide strong existential results for
divisible goods, but their guarantees do not carry over to the indivisible
setting. Therefore, we resort to various relaxations and approximations
thereof, such as the (approximate) maximin share and envy-freeness up to any
item.

The _maximin share guarantee_ (MMS) is a compelling and well-studied notion
proposed by Budish (2010) which can be seen as a natural extension of the
well-known cut-and-choose protocol. The goal here is to allocate a bundle to
each agent, ensuring that its value is at least as high as her maximin share
(or a large fraction thereof). Intuitively, the maximin share corresponds to
the maximum value an agent can get after proposing an initial allocation and
keeping the least desirable bundle for herself. The study of MMS allocations
and approximations thereof (mostly under additive utilities) has received
significant attention over the last few years Kurokawa et al. (2018),
Amanatidis et al. (2017b), Barman and Krishnamurthy (2020), Garg and Taki
(2021).

In sharp contrast to weaker relaxations, the existence of _envy-freeness up to
any good_ (EFX) allocations Caragiannis et al. (2019) is yet to be settled
beyond a handful of simple settings Plaut and Roughgarden (2020), Chaudhury et
al. (2020). A reasonable approach is to focus on restricted valuation spaces
and approximations.

In this work, we focus on a different class of valuations, namely _leveled_
valuations. They capture a simple economic behavior in which any set of items
is strictly preferred to any other set of smaller cardinality, regardless of
the specific items included; among bundles of equal size any preference
ordering is feasible.111Leveled preferences can be perceived as a way of
prioritizing quantity over quality, thus giving rise to the definition of
_quantity-monotonic_ preferences used by Pápai (2000). Babaioff et al. (2021b)
study leveled preferences in the context of competitive equilibrium in
markets, while Gafni et al. (2023) study EFX allocations under leveled
preferences for chores. We also note that leveled preferences might arise in
the context of web advertising where some competitors aim to increase their
total coverage rather than focusing on specific advertising spots in the ad
space allocation. Lastly, leveled preferences might appear under budget
constraints: when resources are scarce, agents facing budget constraints might
prioritize quantity to ensure that they have enough items to meet their needs.

###  1.1 Our Contributions

We study fair allocation in a setting where a set of $m$ indivisible goods
need to be allocated to $n$ agents in a fair manner. We focus on the case
where the agents are equipped with leveled valuations and study two well-
studied notions of fairness, (approximate) MMS and EFX.

##### (approximate) MMS.

First, in Section 3 we focus on (approximate) MMS and we are able to show that
every instance where $m<2n$ admits an exact MMS solution. In stark contrast,
when $m\geq 2n$ we observe that there are instances (even for two agents and
four items) where there is no approximate MMS solution, for any approximation
factor.

In light of this negative result, and in order to provide a more fine-grained
analysis of approximate MMS under leveled valuations, we focus on important
valuation subclasses such as submodular leveled (Section 3.1), fractionally
subadditive (Section 3.2) and subadditive leveled functions (Section 3.3).
Submodular, XOS, and subadditive valuations capture complex combinatorial
preferences and have been studied extensively in microeconomics and
algorithmic game theory Lehmann et al. (2006), Feige (2009), Christodoulou et
al. (2016), Feldman et al. (2020).

In Section 3.1, in our main technical result, we show the existence of
$2/3$-MMS allocations for any number of agents and items when agents are
equipped with submodular leveled valuations. We note that our positive result
(lower bound) complements the recent impossibility result (upper bound) of
Kulkarni et al. (2023) that states that there are instances with two agents
where a guarantee better than $2/3$ is impossible to achieve. We demonstrate
how some of our proof ideas may help to provide better bounds for valuations
beyond leveled. Indeed, in Theorem 2 we are able to show that for the case of
two submodular (not necessarily leveled) agents and multiple goods there is
always a $2/3$-MMS allocation. We highlight the fact that the nice structure
of leveled valuations does not yield any stronger bounds in this case. Next,
we switch to fractionally subadditive (XOS) and subadditive leveled valuations
where we are able to provide tight approximate MMS bounds.

##### EFX.

In Section 4 we shift our attention to EFX allocations. We prove the existence
of exact EFX allocations under (ordinal or cardinal) leveled preferences via a
simple protocol. In particular, under strict leveled preferences our mechanism
achieves a set of natural properties in addition to EFX, overcoming the
barriers of existing impossibility results on the interplay between fairness,
efficiency, and incentive compatibility. Our results complement the previous
work of Gafni et al. which showed the existence of EFX allocations under the
special case of _additive_ leveled valuations.222We note that the model
studied in Gafni et al. (2023) is different than ours. They consider fair
allocations for goods with copies and develop a duality framework between
chores and goods with copies. Without copies, their proposed fairness concept
coincides with the standard notion of EFX.

##### Truthfulness.

Finally, we explore the interplay of fairness with truthfulness for the class
of leveled valuations. We are able to show that constant factor MMS
approximations can be achieved via truthful mechanisms under leveled
valuations. This is in contrast to (non-leveled) valuations where non-constant
upper bounds persist even for the case of additive valuations Amanatidis et
al. (2017a). Additionally, we show an algorithmic characterization of
mechanisms satisfying truthfulness, Pareto optimality, non-bossiness,
neutrality, and EFX.

###  1.2 Related Work

In this section we discuss prior works closely related to EFX, MMS, and
leveled valuations. The growing literature on fair allocation of indivisible
items is too extensive to cover on this paper and thus, we refer the
interested reader to the recent survey of Amanatidis et al. for a detailed
overview.

EFX. The concept of EFX poses several challenges leading to important open
problems in the area. Plaut and Roughgarden (2020) showed that when agents
exhibit identical valuations or share the same ordinal ranking of goods, EFX
is guaranteed to exist. In a breakthrough result, Chaudhury et al. (2020)
showed that complete, exact EFX allocations always exist for three agents
under additive utilities, later improved to more general valuations Berger et
al. (2022), Akrami et al. (2023a). Other works considered a limited number of
items or agents sharing one of two possible valuation types Amanatidis et al.
(2020), Mahara (2023, 2024), while a major line of work focused on
restrictions on the valuation space, prompting a series of works on
dichotomous valuations Amanatidis et al. (2021), Babaioff et al. (2021a),
Benabbou et al. (2021), Halpern et al. (2020), lexicographic preferences
Hosseini et al. (2021), graph instances Christodoulou et al. (2023), and
allocations of multisets Gorantla et al. (2023). Recent work has shown that
EFX allocations might not exist under general monotone valuations when the
items to be allocated are chores Christoforidis and Santorinaios (2024).

MMS. The existence of maximin fair allocations is not guaranteed for additive
utilities Kurokawa et al. (2018). A series of works established strong
approximation guarantees reaching a factor of $3/4+\mathcal{O}(1/n)$ Kurokawa
et al. (2018), Amanatidis et al. (2017b), Barman and Krishnamurthy (2020),
Ghodsi et al. (2021), Garg and Taki (2021), Akrami et al. (2023b). Very
recently, Akrami and Garg (2024) broke the barrier of $3/4$. Considerable
effort has been shown to the case of four or fewer agents Amanatidis et al.
(2017b), Gourvès and Monnot (2019), Ghodsi et al. (2021), Feige and Norkin
(2022) or settings with few items Feige et al. (2021), Hummel (2023). The
current impossibility result for additive valuations stands at $1-1/n^{4}$ due
to Feige et al. (2021). Moreover, the study of maximin fair allocations beyond
the additive domain has been of growing interest. Barman and Krishnamurthy
(2020), Uziahu and Feige (2023) and Ghodsi et al. (2022), Seddighin and
Seddighin (2024) provided a series of results for complement-free valuations.
We briefly summarize the known results in Table 1.

Leveled Preferences. Typical examples of such preferences mentioned in the
literature include the distribution of cabinet seats among parties forming a
coalition government or the allocation of offices among different departments
at universities. Pápai (2000) characterized the set of strategyproof
mechanisms under standard economic assumptions in assignment problems. Gafni
et al. (2023) prove the existence of EFX allocations under _leveled additive_
valuations, while Babaioff et al. (2021a) consider $\epsilon$-leveled
valuations (additive valuation functions that are $\epsilon$-dichotomous). Oh
et al. (2021) show that there exists a deterministic algorithm that computes
an EF1 allocation using $\mathcal{O}(n^{2})$ queries under leveled valuations.
Despite their simplicity, leveled valuations have played an important role in
constructing counterexamples; we note that the first negative results for both
notions (MMS non-existence and exponential query complexity for EFX) actually
employ leveled valuations Kurokawa et al. (2018), Plaut and Roughgarden
(2020). The best currently known MMS bounds for more general classes are also
(essentially) leveled.

##  2 Model and Preliminaries

In this section we introduce the main concepts and notation.

Model. We want to allocate $m$ goods to $n$ agents. We denote as
$M=\\{1,...,m\\}$ the set of goods and with $N=\\{1,...,n\\}$ the set of
agents. Each agent $i$ is equipped with a valuation function
$v_{i}:2^{M}\rightarrow\mathbb{R}_{\geq 0}$.

Allocations and bundles. An allocation is a tuple of subsets of $M$, namely an
$n$-partition $A=(A_{1},...,A_{n})$ where $A_{i}$ is the bundle allocated to
agent $i$. The elements of $A$ are pairwise disjoint, that is $A_{i}\cap
A_{j}=\emptyset$ for every pair of agents $i,j\in N$. $\Pi_{n}(M)$ denotes the
set of all possible $n$-partitions of $M$. Moreover, we only focus on complete
allocations in which no items remain unallocated, that is $\bigcup_{i\in
N}A_{i}=M$. We denote $[k]=\\{1,...,k\\}$ for any $k\in\mathbb{N}$.

Classes of valuation functions. Throughout this paper, we consider the
valuation functions to be normalized, i.e. $v(\\{\emptyset\\})=0$, and
monotone ($v(S)\leq v(T)$ for $S\subseteq T$). We focus on leveled valuations.

######  Definition 1.

A valuation function $v$ is leveled if for any two bundles $S,T$ with $\lvert
S\rvert>\lvert T\rvert$ it holds that $v(S)>v(T)$.

Moreover, we consider subclasses of complement-free valuations.

  * •

A valuation function $v$ is _additive_ if for every $S\subseteq M$, we have
that $v(S)=\sum_{j\in S}v(\\{g\\})$. For ease of convenience, we may write
$v(g)$ instead of $v(\\{g\\})$.

  * •

A valuation function $v$ is _submodular_ if $v(S)+v(T)\geq v(S\cup T)+v(S\cap
T)$ for all sets $S$ and $T$ in $M$.

  * •

A valuation function $v$ is _fractionally subadditive_ (_XOS_) if there exists
a family of additive functions $a_{1},\dots,a_{k}$ such that
$v(S)=\max_{l\in[k]}a_{l}(S)$

  * •

A valuation function $v$ is _subadditive_ if $v(S)+v(T)\geq(S\cup T)$ for all
sets $S$ and $T$ in $M$.

The hierarchy of the aforementioned classes is as follows: Additive $\subset$
Submodular $\subset$ XOS $\subset$ Subadditive.

Fairness. In envy-free allocations, no agent would strongly prefer to swap her
allocated bundle with someone else. Formally, $v_{i}(A_{i})\geq
v_{i}(A_{j}),\forall i,j\in N$. Envy-free solutions may fail to exist in
settings with indivisible goods. Therefore, several relaxed versions have been
introduced in the literature. We focus on EFX, which requires that envy
vanishes after removing any item from the bundle of the envied agent.

######  Definition 2 (Envy-freeness up to any good (EFX)).

An allocation $A\in\Pi_{n}(M)$ is called envy-free up to any good (EFX) if
$\forall i,j\in N,\forall g\in A_{j}:v_{i}(A_{i})\geq
v_{i}(A_{j}\setminus\\{g\\})$.

Another important notion is that of maximin share. $\mu_{i}^{n}(M)$ denotes
the maximin share for an agent $i$, that is the maximum value she can obtain
after proposing an $n$-partition of the items and securing the worst bundle
for herself.

######  Definition 3 (Maximin share).

An allocation $A$ is said to be maximin share fair (MMS) if
$v_{i}(A_{i})\geq\mu_{i}^{n}(M)=\max_{A\in\Pi_{n}(M)}\min_{k\in[n]}v_{i}(A_{k}),\forall
i\in N$.

When $n$ and $M$ are clear from context, we may write $\mu_{i}$ for notation
simplicity. Furthermore, without loss of generality, we assume that
$\mu_{i}^{n}(M)=1$ for every agent $i\in N$. Since maximin share allocations
do not always exist, we focus on multiplicative approximations of the maximin
share.

######  Definition 4 ($\alpha$-MMS).

Let $\alpha\in(0,1]$. An allocation $A$ is said to be $\alpha$-maximin fair if
it guarantees to an agent an $\alpha$-fraction of her MMS, that is
$v_{i}(A_{i})\geq\alpha\cdot\mu_{i}^{n}(M),\forall i\in N$.

Efficiency. A common notion of economic efficiency is Pareto optimality.
Roughly speaking, under a Pareto efficient allocation, no individual can
become strictly better off without hurting someone else’s value. There exist
instances where EFX cannot be satisfied in conjunction with Pareto optimality,
even for 2 players Plaut and Roughgarden (2020).

Mechanisms and Truthfulness. A deterministic allocation mechanism without
payments, henceforth a _mechanism_ , is a mapping $\mathcal{X}$ from valuation
profiles to allocations. We let $\mathcal{X}_{i}(\boldsymbol{v})$ denote the
set of items agent $i$ receives. A mechanism $\mathcal{X}$ is truthful if for
any instance $\boldsymbol{v}=(v_{1},\dots,v_{n})$, any player $i\in N$, and
any $v_{i}^{\prime}$: $v_{i}(X_{i}(\boldsymbol{v}))\geq
v_{i}(X_{i}(v_{i}^{\prime},v_{-i}))$

##  3 Maximin share (MMS)

In this section, we focus on approximate MMS and show general positive and
negative results under leveled valuations. First, we focus on instances with
few items; we show that every instance with $m<2n$ admits an exact MMS
allocation under general leveled valuations.333Similar settings with a small
number of items have been explored in a surge of works for additive utilities
Bouveret and Lemaître (2016), Kurokawa et al. (2018), Feige et al. (2021),
Hummel (2023). Exceeding this threshold may lead to instances where the
approximation ratio becomes unbounded. Subsequently, we proceed to a more
refined analysis of the concept for valuations that are both leveled and
submodular. We show a general positive result, establishing the existence of
$2/3$-MMS allocations under submodular leveled valuations (Theorem 1). We then
switch to subadditive and fractionally subadditive agents and show tight lower
and upper bounds on the approximation of the maximin share (Section 3.2 and
Section 3.3). We now state our proposition concerning scenarios where the
number of items is limited in relation to the number of agents, specifically
when $m<2n$.

######  Proposition 3.1.

Every instance where $m<2n$ admits an exact MMS allocation under general
leveled valuations.

###### Proof.

For $n\geq m$ verifying the existence of MMS allocations is straightforward.
In the scenario where $n<m<2n$, it is clear that the maximin value for each
agent is achieved via singletons. Suppose that we have $m=n+r$ with $r$ a
positive integer smaller than $n$. Select an arbitrary picking order $\sigma$,
a permutation of $[n]$. We let the first $n-r$ agents choose their preferred
item according to $\sigma$. Subsequently, we allocate the rest of the items in
pairs to the remaining agents in an arbitrary manner. Clearly, agents
receiving two items guarantee their full MMS due to leveled valuations. In the
case of an agent $i$ receiving a single item, it holds that all the agents
that came beforehand in the picking order have received a single item too.
Removing an arbitrary item $g$ and an arbitrary agent $j$ does not decrease
the MMS value for the remaining agents. Such reducibility lemmas have been
used several times in the literature Bouveret and Lemaître (2016), Amanatidis
et al. (2023). ∎

Adding more items beyond this point transitions us from exact MMS solutions to
instances with unbounded approximation ratio, even for two agents and four
goods.

######  Example 1.

Consider an instance with $n$ agents and $m=2n$ goods
$\\{g_{1},\dots,g_{m}\\}$. For all agents $i\in[n-1]$ we have that
$v_{i}(S)=\epsilon$ for all $S$, such that $\lvert S\rvert=1$. Furthermore,
$v_{i}(\\{g_{2j-1},g_{2j}\\})=1,\forall j\in[n],\forall i\in[n]$, while any
other pair of items is valued at $\epsilon+\delta$, with $\epsilon,\delta$
small positive constants. For agent $n$ we have $v_{n}(S)=\epsilon$ for all
$S$, $\lvert S\rvert=1$, and $v_{n}(\\{S^{\prime}\\})=1$ for all bundles
$S^{\prime}\in\mathcal{S}=(\\{g_{1},g_{2n}\\},\\{g_{2},g_{3}\\},\dots,\\{g_{2n-2},g_{2n-1}\\})$;
the rest of the pairs are also valued at $\epsilon+\delta$. Lastly,
$v_{i}(S)=\lvert S\rvert+\epsilon$ for all $\lvert S\rvert>2$. One can easily
check that the valuations described above are leveled. The proof follows the
structure of the proof of Corollary 2 due to Ghodsi et al. (2022), where all
but one agent share the same valuation function. Agent $1$’s maximin share is
equal to $1$; same holds true for agent $2$. We observe that one must receive
a low-valued bundle. It is easy to see that we can make $\epsilon$
infinitesimally small while keeping the valuations leveled, thus making any
approximation guarantee arbitrarily bad. Hence, we shift our attention to
subclasses of leveled valuation functions, such as submodular, fractionally
subadditive, and subadditive leveled valuations. Our results are summarized in
Table 1.

Submodular | Existence | Non-Existence
---|---|---
$n=2$ | $\boldsymbol{2/3}$ | $2/3$
$n\geq 3$ | $10/27$ | $3/4$
Submodular Leveled |  |
$n=2$ | $\boldsymbol{2/3}$ | $2/3^{*}$
$n\geq 3$ | $\boldsymbol{2/3}$ | ${3/4}^{*}$
XOS |  |
$n\geq 2$ | $3/13$ | $1/2$
XOS Leveled |  |
$n\geq 2$ | $\boldsymbol{1/2}$ | $1/2^{*}$
Subadditive |  |
$n\geq 2$ | $\Omega(1/\log{n}\log\log{n})$ | $1/2$
Subadditive Leveled |  |
$n\geq 2$ | $\boldsymbol{1/2}$ | $1/2^{*}$
Table 1: Best known approximations of MMS with submodular agents are due to
Ghodsi et al. (2022), Uziahu and Feige (2023), Kulkarni et al. (2023),
Seddighin and Seddighin (2024). The results on XOS valuations are due to
Ghodsi et al. (2022) and Akrami et al. (2023c), while bounds on subadditive
valuations come from Ghodsi et al. (2022) and Seddighin and Seddighin (2024).
Our results appear in bold. The upper bounds noted with $(^{*})$ are not
explicitly stated in previous works, but one can tweak known counterexamples
to also work for leveled valuations.

###  3.1 Submodular Valuations

In this section we provide a thorough analysis w.r.t approximate MMS for the
case of valuations that are both leveled and submodular. First, we present a
general positive result (Theorem 1), showing that a $2/3$-MMS allocation
always exists, and we present a procedure that computes one. We argue that our
proof ideas can help to provide better bounds for valuations beyond leveled.
Indeed in Theorem 2 we are able to show that for the case of two submodular
(not necessarily leveled) agents and multiple goods there always exists a
$2/3$-MMS allocation. We present our main technical result which is the
existence of a $2/3$-MMS allocation for submodular leveled valuations.

######  Theorem 1.

Every instance where agents have submodular leveled valuations admits a
$2/3$-MMS allocation.

###### Proof.

We split the proof into two different cases444There is also a third case,
where $m<2n$, but this is treated separately by Proposition 3.1 which holds
for general leveled valuations and provides exact MMS. depending on the range
of $m$, namely for $2n\leq m<3n$ and $m\geq 3n$. In both cases, the main
element is a simple combinatorial argument that guarantees the abundance of
bundles of size $\lfloor m/n\rfloor$ with values higher than $2/3$ (Claim 1
and Claim 2 respectively). At a high level we present a partition of the items
which is MMS for one of the agents, and we offer its bundles to the rest of
the agents. The two claims secure that either this partition achieves the
desired MMS guarantee of $2/3$ for all agents (case 2) or that there is some
reallocation of the goods that achieves this (case 1).

Case 1: $2n\leq m<3n$. Notice that in this case, which is the more challenging
one, the MMS value for each agent is achieved by a subset of items of size
equal to $2$.

######  Claim 1.

Fix an agent $i\in N$, and an arbitrary subset $M^{\prime}=\\{a,b,c,d\\}$ of
four items of $M$. Let $S=\\{a,b\\},T=\\{c,d\\}$ be an arbitrary partition of
$M^{\prime}$ into two equal sized sets. Let $\mathcal{U}$ be the family of all
pairs of items that intersect both $S$ and $T$, i.e.
${\mathcal{U}}=\left\\{\\{a,c\\},\\{a,d\\},\\{b,c\\},\\{b,d\\}\right\\}$. If
$\max\\{v_{i}(S),v_{i}(T)\\}<2/3$ then $v_{i}(U)>2/3$ for every
$U\in{\mathcal{U}}$.

###### Proof.

Take a $U\in{\mathcal{U}}$, without loss of generality let this be
$U=\\{a,c\\}$. Recall that the MMS of agent $i$ is achieved by a set of size
equal to $2$. We obtain

$\displaystyle v_{i}(S)+v_{i}(U)\geq
v_{i}(S\cup\\{c\\})+v_{i}(\\{a\\})>1+v_{i}(\\{a\\}),$

where the first inequality holds due to submodularity and the second due to
the fact that $|S\cup\\{c\\}|=3$ and hence (by definition of leveled
valuations) the value obtained by this set must be strictly greater than her
MMS value. Similarly, we obtain

$\displaystyle v_{i}(T)+v_{i}(U)\geq
v_{i}(T\cup\\{a\\})+v_{i}(\\{c\\})>1+v_{i}(\\{c\\}).$

By summing these up, and by using again submodularity we obtain

$v_{i}(S)+v_{i}(T)+v_{i}(U)>2.$

Since $\max\\{v_{i}(S),v_{i}(T)\\}<2/3$ we conclude that $v_{i}(U)>2/3$ as
needed. ∎

We now proceed with the proof of Case 1, thus showing that every instance
where agents have submodular leveled valuations, $2n\leq m<3n$ admits a
$2/3$-MMS allocation. Our goal is to provide a $2/3$-MMS allocation
$(A^{*}_{1},\ldots,A^{*}_{n})$, such that $v_{i}(A^{*}_{i})\geq 2/3$ for every
agent $i$. Initially we consider a partition $A=(A_{1},\ldots,A_{n})$ which is
$2/3$-MMS allocation from the perspective of agent $1$, i.e.,
$v_{1}(A_{j})\geq 2/3$, for every $j=1,\ldots,n$. Notice that due to the fact
that the valuations are leveled, it must be that $2\leq|A_{j}|\leq 3$ for all
$j$. We offer these bundles to agents $2,\ldots,n$; as long as there exists an
agent $i>1$ and a bundle $A_{j}$ such that $v_{i}(A_{j})\geq 2/3$, then we
allocate $A_{j}$ to $i$, i.e. $A^{*}_{i}:=A_{j}$ and we proceed with the
remaining agents and bundles555If there are more than one such agents, we
break ties lexicographically..

If at the end of this stage each of the agents $2,\ldots,n$ is allocated an
$A_{j}$ set then we allocate the remaining bundle to agent $1$ and the
resulting allocation is $2/3$-MMS.

Otherwise, there will be a subset of $k\leq n-1$ agents
$N^{\prime}\subseteq\\{2,\ldots,n\\}$ which value each of the remaining $k+1$
bundles
$A_{i_{1}}=\\{g_{1},g_{2}\\},\ldots,A_{i_{k}}=\\{g_{2k-1},g_{2k}\\},A_{i_{k+1}}=\\{g_{2k+1},g_{2k+2}\\}$
with value less than $2/3$. Notice that each of these bundles must have
cardinality equal to 2, as all bundles of three items are valued higher than
the MMS share by all agents. Let $M^{\prime}=A_{i_{1}}\cup\ldots\cup
A_{i_{k}}\cup A_{i_{k+1}}$ be the subset of the remaining items (it could be
$M^{\prime}=M$).

But then, we can utilize Claim 1 to reshuffle the items; If $k\geq 2$, then we
can assign $A_{i_{k+1}}$ to agent $1$ and partition the rest into $k$ pairs as
follows:
$B_{1}=\\{g_{2},g_{3}\\},B_{2}=\\{g_{4},g_{5}\\},\ldots,B_{k}=\\{g_{2k},g_{1}\\}$.
By Claim 1 the value of each agent in $N^{\prime}$ for every $B_{j}$ bundle is
strictly higher than $2/3$. If $k=1$, then $M^{\prime}$ has four items, and
again by inspection we can verify that either
$B_{1}=\\{g_{2},g_{3}\\},B_{2}=\\{g_{4},g_{1}\\}$ or
$B^{\prime}_{1}=\\{g_{2},g_{4}\\},B^{\prime}_{2}=\\{g_{3},g_{1}\\}$ will
satisfy the conditions for both agents.

Case 2: $m\geq 3n$ The argument can be further simplified when dealing with
instances of $m\geq 3n$.

######  Claim 2.

Fix an agent $i$ and two disjoint subsets $S,T$ of $M$ with $|S|=|T|=\lfloor
m/n\rfloor$. If $v_{i}(S)<2/3$, then $v_{i}(T)>2/3$.

###### Proof.

Take any pair of items $\\{s,t\\}$ with $s\in S$ and $t\in T$. By arguments
similar to those used in the proof of Claim 1 we obtain

$\displaystyle v_{i}(S)+v_{i}(\\{s,t\\})\geq
v_{i}(S\cup\\{t\\})+v_{i}(\\{s\\})>1+v_{i}(\\{s\\}),$

and similarly

$\displaystyle v_{i}(T)+v_{i}(\\{s,t\\})\geq
v_{i}(T\cup\\{s\\})+v_{i}(\\{t\\})>1+v_{i}(\\{t\\}).$

By summing up those inequalities we get

$\displaystyle v_{i}(S)+v_{i}(T)+v_{i}(\\{s,t\\})>2.$

Finally by observing that $v_{i}(\\{s,t\\})\leq\frac{1}{2}(v_{i}(S)+v_{i}(T))$
since the valuations are leveled we conclude that $v_{i}(S)+v_{i}(T)>4/3$ and
the claim follows. ∎

We treat the second case in a similar but simpler fashion. We show that every
instance where all agents have submodular leveled valuations, $3n\leq m$
admits a $2/3$-MMS allocation. As in case 1, we consider a partition
$A=(A_{1},\ldots,A_{n})$ which is an MMS allocation from the perspective of
agent $1$ and we offer these bundles to agents $2,\ldots,n$. Claim 2
guarantees that for each agent there is at most one bundle with value less
than $2/3$, hence at least $n-1$ bundles with value higher than $2/3$. We let
them choose sequentially in a greedy fashion, and we allocate the remaining
bundle to agent 1 who values it at least as high as $2/3$. ∎

####  3.1.1 Lower Bound for Two Submodular Agents

We complement the negative example of Kulkarni et al. (2023) with a positive
result.

######  Theorem 2.

The problem of fairly allocating goods to two submodular agents admits a
$2/3$-MMS allocation.

###### Proof.

Let us consider agents $1$ and $2$ and their respective MMS partitions denoted
as $P_{1}=(S,\bar{S})$ and $P_{2}=(T,\bar{T})$. We define the following sets:
$A=S\cap T$, $B=S\setminus T$, $C=\bar{S}\cap\bar{T}$, $D=T\setminus S$, as
depicted below:

$S$$\bar{S}$

$T$$\bar{T}$

ABDC

Figure 1: A graphic interpretation of the proof given below. The first two
pictures depict the MMS partitions of agent $1$ and agent $2$ respectively.

where the vertical line represents agent $1$’s MMS partition, while the
horizontal line represents agent $2$’s respective MMS partition. Therefore,
the agents’ MMS allocations can be written as $P_{1}=(S,\bar{S})=(A\cup
B,C\cup D)$ and $P_{2}=(T,\bar{T})=(A\cup D,B\cup C)$.

Following an argument similar to those used in the proof of Claim 1, we have
the following submodularity inequalities:

$\displaystyle v_{1}(T)+v_{1}(A\cup C)\geq v_{1}(\bar{S}\cup A)+v_{1}(A)$
$\displaystyle v_{1}(\bar{T})+v_{1}(A\cup C)\geq v_{1}(S\cup C)+v_{1}(C)$

Summing up the two inequalities and using submodularity again, we obtain:

$\displaystyle v_{1}(T)+v_{1}(\bar{T})+v_{1}(A\cup C)\geq 2$

Note that $v_{1}(A)+v_{1}(C)\geq v_{1}(A\cup C)+v_{1}(A\cap C)$ but $A\cap
C=\emptyset$ by construction. The last inequality holds due to the fact that
$S$ and $\bar{S}$ constitute the proposed MMS allocation of agent 1, and thus
$v_{1}(S\cup C)\geq 1$ and $v_{1}(\bar{S}\cup A)\geq 1$. Similarly, for agent
2:

$\displaystyle v_{2}(S)+v_{2}(\bar{S})+v_{2}(B\cup D)\geq 2$

We offer the bundles $T$ and $\bar{T}$ to agent 1 and the bundles $S$ and
$\bar{S}$ to agent 2 respectively. Therefore, we arrive at the following
scenario: either an agent accepts the offer, considering one of the proposed
bundles to be valuable at least $2/3$, or both agents reject the proposed
allocations. In the first case, one of the agents secures her full MMS while
the other one is contented with at least $2/3$ of her MMS. In the latter
situation, we identify an additional allocation $P=(\\{A\cup C,B\cup D\\})$
that is deemed acceptable by both agents, meaning they both value their
allocated bundles at least as high as a $2/3$ fraction of their maximin shares
due to the aforementioned inequalities. This completes the proof. ∎

###  3.2 Fractionally Subadditive Leveled Valuations

We exhibit tight bounds for the case of fractionally subadditive (XOS) leveled
valuations. The existence result follows from Section 3.3. The non-existence
(impossibility) construction relies on a family of additive functions that
replicate the $1/2$ bound given in Section 3.3.

###  3.3 Subadditive Leveled Valuations

We follow a similar approach to demonstrate the existence of $1/2$-MMS
allocations under subadditive valuations. Moreover, we provide a general tight
upper bound by tweaking a known impossibility result due to Ghodsi et al.
(2022).

######  Lemma 1.

Fix an agent $i$ and two disjoint subsets $S,T$ of $M$ with $|S|=|T|=\lfloor
m/n\rfloor$. If $v_{i}(S)<1/2$, then $v_{i}(T)>1/2$.

###### Proof.

By subadditivity, we have $v_{i}(S)+v_{i}(T)\geq v_{i}(S\cup T)>1$. Recall
that the MMS of an agent $i$ is attained by a bundle of size $\lfloor
m/n\rfloor$, thus $S\cup T$ has strictly more items than any MMS bundle.
Therefore, $\max\\{v_{i}(S),v_{i}(T)\\}>1/2$. ∎

######  Theorem 3.

The problem of fairly allocating goods under subadditive leveled valuation
functions admits a 1/2-MMS allocation.

###### Proof.

Fix an agent $i$ and let $A=(A_{1},\ldots,A_{n})$ be her MMS allocation. We
offer each agent two arbitrary bundles among the ones still available in $A$.
According to Lemma 1, one of the bundles is valued at least $1/2$. We let the
agents pick bundles from $A$ sequentially in a greedy fashion; we allocate the
remaining bundle to agent $i$. ∎

###  3.4 Upper Bounds

Kulkarni et al. (2023) showcased a construction that gives an impossibility
result on the existence of better than $2/3$-MMS allocations for two
submodular agents. In fact, they show that the result holds even for a smaller
subclass of submodular valuations, namely OXS functions. One can easily adapt
the construction to make the valuations leveled. For XOS functions, we adapt
the construction given in Akrami et al. (2023c) (Table 2). For subsets $S$
with $\lvert S\rvert>2$, we have $v_{i}(S)=2+\epsilon$ for $\lvert S\rvert=3$
and $v_{i}(S)=2+2\epsilon$ for $\lvert S\rvert=4$. We denote the set of
additive valuations of each agent as $a_{1}$ and $a_{2}$ for agent $1$, and
$a_{3},a_{4}$ for agent $2$ respectively. The XOS function receives the
pointwise maximum value for each subset, i.e.
$v_{1}(b_{1},b_{2})=\max\\{a_{1}(a,b),a_{2}(a,b)\\}=2$. It is easy to see that
the maximin value for each agent is equal to $2$. However, there is no way to
guarantee MMS for both of the agents; one of the agents has to receive a total
value of $1+\epsilon$ for an arbitrarily small $\epsilon>0$. Finally, in order
to make the counterexample general (for $n$ agents), we follow the same
rationale as in Corollary 2, adding multiple copies of type 1 agents.

| $b_{1}$ | $b_{2}$ | $b_{3}$ | $b_{4}$
---|---|---|---|---
$a_{1}$ | 1 | 1 | $\epsilon$ | $\epsilon$
$a_{2}$ | $\epsilon$ | $\epsilon$ | 1 | 1
$a_{3}$ | 1 | $\epsilon$ | $\epsilon$ | 1
$a_{4}$ | $\epsilon$ | 1 | 1 | $\epsilon$
Table 2: Upper bound for XOS functions

For subadditive valuations, one can adapt the construction given in Ghodsi et
al. (2022).

######  Corollary 1.

There exists an instance of the fair allocation problem with two submodular
leveled agents in which no allocation is strictly better than 2/3-MMS Kulkarni
et al. (2023).

######  Corollary 2.

For any $n\geq 2$ there exists an instance of the fair allocation problem with
n subadditive leveled agents where no allocation yields more than $1/2$-MMS to
the agents Ghodsi et al. (2022).

##  4 Envy-freeness up to Any Good

In this section we consider envy-freeness up to any good. We establish the
existence of EFX allocations under general leveled valuations.

Description of the algorithm. Let $m=kn+r$ be the total number of items with
$r$ being a nonnegative integer smaller than $n$ and let $k=\lfloor
m/n\rfloor$. The algorithm runs sequentially. We begin by fixing a quota
system in which the first $n-r$ agents in the sequence are set to pick their
most favourite bundle of $\lfloor m/n\rfloor$ goods. Subsequently, the
remaining agents choose their favourite subsets of items, each containing
$\lfloor m/n\rfloor+1$ goods. Therefore, the agents get to choose a fixed
number of items from a feasible set according to a predefined hierarchy.

Algorithm 1 EFX under Leveled Valuations

Input: An instance with leveled valuations, $m=kn+r$
Output: An EFX allocation

1: Select an arbitrary picking order
$\sigma=[\sigma_{1},\sigma_{2},\ldots,\sigma_{n}]$

2: Let the first $n-r$ agents (according to $\sigma$) pick their favourite
bundle of $\lfloor m/n\rfloor$ available items

3: Let the remaining $r$ agents pick their favourite bundle, each consisting
of $\lfloor m/n\rfloor+1$ items

4: return allocation

######  Theorem 4.

Under general leveled valuations, there exists an EFX allocation.

###### Proof.

The algorithm is shown as Algorithm 1. We divide the agents into two levels,
namely level $L$ and level $H$; agents in the lower level possess an item less
than those in the higher level. Clearly, agents in $H$ attain more value than
agents in $L$; they are in fact envy-free towards them. Therefore, the EFX
criterion might be violated only among agents residing at different levels. In
this case, agents in $L$ might become envious of agents in $H$. Suppose, for
the sake of contradiction, that EFX is violated, that is, there is an agent
$i$ in $L$ that EFX-envies an agent $j$ in level $H$. This would imply that
after removing any item from $A_{j}$, there exists a bundle of $\lfloor
m/n\rfloor$ items that agent $i$ strictly prefers over her own bundle.
However, if such a bundle existed, she would have picked it earlier in the
allocation process since she preceded $j$ in the picking order. Hence, by
contradiction, agent $i$ is EFX towards agent $j$. ∎

##  5 Truthfulness

In this section we study the mechanism design aspect of fairly allocating
goods among agents. In Section 5.1 we show that constant MMS approximations
are possible via a rich class of truthful mechanisms. In Section 5.2 we show a
characterization of truthful, EFX, PO, non-bossy, and neutral mechanisms.
Under leveled valuations, we observe that strategyproofness can be achieved in
conjunction with strong fairness guarantees. Amanatidis et al. introduce the
notion of _controlling items_ ; we say that a player controls an item if
reporting certain values guarantees her this item. Control is the major hurdle
that makes fairness and truthfulness incompatible under additive valuations.
We note that this is not applicable to our case, since control of
singletons666Control of singletons implies that whenever an agent strongly
desires an item, i.e. prefers it more than all the other items combined, she
gets it. (or pairs) is not possible under leveled valuations.

The mechanism described in Section 4 falls under the broad class of _serial
dictatorships with quotas_ (see Definition 5).

######  Definition 5.

[Serial dictatorship with quotas, Pápai (2000)] The serial dictatorship with
quotas (SDQ) mechanism is specified by a permutation of the agents
$\sigma:N\rightarrow N$ and a quota system $q:N\rightarrow N$,
$q=(q_{1},\dots,q_{n})$ such that $\sum_{i=1}^{n}q_{i}=m$.

###  5.1 Maximin Share Guarantee

In the case of additive agents, it is known that an EFX allocation is also a
$2/3$-MMS allocation for $n\in\\{2,3\\}$, due to Amanatidis et al. (2018). The
approximation degrades as the number of agents grow to $4/7=0.5714$. We show
that any allocation obtained via SDQs with the quota system of Algorithm 1
achieves a $2/3$-MMS approximation (along with EFX), even for $n>3$.

######  Proposition 5.1.

There exists a $\frac{2}{3}$-MMS allocation under additive leveled valuations.

###### Proof.

Consider an arbitrary allocation $B=(B_{1},\dots,B_{n})$ obtained via
Algorithm 1. Let $i$ be an agent that receives $B_{i},\lvert
B_{i}\rvert=k=\lfloor m/n\rfloor$ and let allocation
$B^{\prime}=(B_{1}^{\prime},\dots,B_{n}^{\prime})$ denote her MMS allocation.
Assume wlog that $k\geq 2$; the case where $m<2n$ is handled by Proposition
3.1 via an SDQ. Note that since the valuations are additive, there must exist
an item $g\in B_{i}$ such that $v_{i}(g)\leq v_{i}(B_{i})/2$ since $k\geq 2$.
Otherwise, the items would add up to something larger than $v_{i}(B_{i})$. If
all agents’ bundles are of size $k$, then $g$ belongs to a bundle, say
$B_{j}^{\prime}$, in her MMS allocation $B^{\prime}$. We know that $\lvert
B_{j}^{\prime}\setminus g\rvert=k-1$, and thus, due to leveled valuations,
$v_{i}(B_{j}^{\prime}\setminus g)\leq v_{i}(B_{i})$. Therefore, we have
$\mu_{i}\leq v_{i}(B_{i})+v_{i}(g)\leq 3/2v_{i}(B_{i})$. Differently, some
agents may receive one less item than others as shown in Algorithm 1. But
then, $\mu_{i}<v_{i}(B_{j}^{\prime})$ for some bundle $B_{j}^{\prime}$ with
$\lvert B_{j}^{\prime}\rvert=k+1$ that contains $g$, and thus,
$v_{i}(B_{j}^{\prime}\setminus g)\leq v_{i}(B_{i})$ (since $i$ precedes $j$ in
the order). We conclude that $\mu_{i}\leq v_{i}(B_{j}^{\prime})\leq
v_{i}(B_{i})+v_{i}(g)\leq 3/2v_{i}(B_{i})$. ∎

######  Proposition 5.2.

Any balanced allocation achieves a $\frac{k-1}{k}$-MMS approximation under
additive leveled valuations, where $k=\lfloor m/n\rfloor$.

###### Proof.

Let $k=\lfloor m/n\rfloor$ and let $B_{i}^{\prime}$ be the bundle that gives
the MMS value to agent $i$, i.e., $v_{i}(B_{i}^{\prime})=\mu_{i}$. In any
balanced allocation (arbitrary SDQ following the quota system of Algorithm 1),
an agent $i$ either receives $k+1$ items (in which case she trivially
guarantees her MMS) or exactly $k$ items. We examine the latter case. We know
that the MMS bundle consists of $k$ items, and thus, any bundle $B$ with
$\lvert B\rvert=k$ has higher value than any subset $S_{j}$ of
$B_{i}^{\prime}$ with cardinality $\lvert S_{j}\rvert=k-1$; there are
$\binom{k}{k-1}=k$ such combinations (leaving out one item at a time). We
derive a set of equations $v_{i}(B)\geq v_{i}(S_{j})$ for all $j\in[k]$.
Summing over all inequalities, we get $k-1$ copies of $B_{i}^{\prime}$ in the
right-hand side. Hence, we have: $k\cdot v_{i}(B)\geq(k-1)\cdot\mu_{i}\implies
v_{i}(B)\geq\frac{k-1}{k}\cdot\mu_{i}$ ∎

It is easy to see that the aforementioned propositions imply that fixed-point
mechanisms and SDQs trivially achieve strong approximation properties. Lastly,
one can derive analogous propositions for truthful MMS approximations via SDQs
for subadditive valuations.

######  Proposition 5.3.

There exists a $\frac{1}{2}$-MMS approximation under subadditive leveled
valuations via an SDQ.

###  5.2 Envy-freeness up to Any Good

We focus on (strict) ordinal preferences. We give an algorithmic
characterization of the mechanisms satisfying a set of desired properties. The
same characterization holds for the case of lexicographic valuations Hosseini
et al. (2021).

######  Proposition 5.4.

(Pápai (2000)) For leveled preferences, a mechanism is Pareto optimal,
strategyproof, non-bossy, and neutral if and only if it is an SDQ.

######  Theorem 5.

A mechanism satisfies EFX, PO, truthfulness, non-bossiness, and neutrality if
and only if it is a Serial Quota Dictatorship.

###### Proof.

Algorithm 1 is an SDQ with quotas $q_{i}=\lfloor m/n\rfloor$ for all
$i\in[n-r]$ and $q_{i}=\lfloor m/n\rfloor+1$ for all $i>n-r$, and therefore
EFX according to Theorem 4. Moreover, it follows from Proposition 5.4 that it
is PO, truthful, non-bossy, and neutral. We also prove the converse; assume
that there exists a mechanism $f$ that satisfies these properties. By
Proposition 5.4, $f$ must be an SDQ for some $\sigma$ and a specified quota
system such that $\sum_{i=1}^{n}q_{i}=m$. Assume wlog that $m\geq n$. Suppose,
for the sake of contradiction, that the quota system of $f$ violates the quota
system described by Algorithm 1; then there exists a pair of agents $i,j\in N$
such that $\lvert A_{i}\rvert=\lvert A_{j}\rvert-2$, violating EFX due to the
definition of leveled valuations, which is a contradiction. Therefore, $f$
must be an SDQ with the quota system specified in Algorithm 1. ∎

######  Remark.

Any deterministic strategyproof and non-bossy mechanism is also group-
strategyproof Pápai (2000).

##  6 Conclusion and Discussion

We explored fairness under leveled valuations and presented a complete set of
results regarding this class. We studied the maximin share guarantee and
provided strong existence and non-existence results. Furthermore, our analysis
improves the current understanding of EFX allocations. We argue that the study
of leveled preferences provides meaningful insights for more important classes
in the economic paradigm. Our ideas for two agents with submodular valuations
might be of independent interest beyond the domain of leveled valuations.
Lastly, it is interesting to see whether a strict superset of dictatorial
mechanisms achieve better approximation guarantees than the ones presented
here. We suspect that picking-exchange mechanisms defined by Amanatidis et al.
(2017a) may do so.

## Acknowledgements

This work has been partially supported by project MIS 5154714 of the National
Recovery and Resilience Plan Greece 2.0 funded by the European Union under the
NextGenerationEU Program.

## References

  * Akrami and Garg (2024) H. Akrami and J. Garg.  Breaking the 3/4 barrier for approximate maximin share.  In _SODA_ , pages 74–91. SIAM, 2024.
  * Akrami et al. (2023a) H. Akrami, N. Alon, B. R. Chaudhury, J. Garg, K. Mehlhorn, and R. Mehta.  EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle number.  In _EC_ , page 61. ACM, 2023a.
  * Akrami et al. (2023b) H. Akrami, J. Garg, E. Sharma, and S. Taki.  Simplification and improvement of MMS approximation.  In _IJCAI_ , pages 2485–2493. ijcai.org, 2023b.
  * Akrami et al. (2023c) H. Akrami, K. Mehlhorn, M. Seddighin, and G. Shahkarami.  Randomized and deterministic maximin-share approximations for fractionally subadditive valuations.  In _NeurIPS_ , 2023c.
  * Amanatidis et al. (2017a) G. Amanatidis, G. Birmpas, G. Christodoulou, and E. Markakis.  Truthful allocation mechanisms without payments: Characterization and implications on fairness.  In _EC_ , pages 545–562. ACM, 2017a.
  * Amanatidis et al. (2017b) G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi.  Approximation algorithms for computing maximin share allocations.  _ACM Trans. Algorithms_ , 13(4):52:1–52:28, 2017b.
  * Amanatidis et al. (2018) G. Amanatidis, G. Birmpas, and V. Markakis.  Comparing approximate relaxations of envy-freeness.  In _IJCAI_ , pages 42–48. ijcai.org, 2018.
  * Amanatidis et al. (2020) G. Amanatidis, E. Markakis, and A. Ntokos.  Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination.  _Theor. Comput. Sci._ , 841:94–109, 2020.
  * Amanatidis et al. (2021) G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris.  Maximum nash welfare and other stories about EFX.  _Theor. Comput. Sci._ , 863:69–85, 2021.
  * Amanatidis et al. (2023) G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu.  Fair division of indivisible goods: Recent progress and open questions.  _Artif. Intell._ , 322:103965, 2023.
  * Babaioff et al. (2021a) M. Babaioff, T. Ezra, and U. Feige.  Fair and truthful mechanisms for dichotomous valuations.  In _AAAI_ , pages 5119–5126. AAAI Press, 2021a.
  * Babaioff et al. (2021b) M. Babaioff, N. Nisan, and I. Talgam-Cohen.  Competitive equilibrium with indivisible goods and generic budgets.  _Math. Oper. Res._ , 46(1):382–403, Feb. 2021b.
  * Barman and Krishnamurthy (2020) S. Barman and S. K. Krishnamurthy.  Approximation algorithms for maximin fair division.  _ACM Trans. Economics and Comput._ , 8(1):5:1–5:28, 2020.
  * Benabbou et al. (2021) N. Benabbou, M. Chakraborty, A. Igarashi, and Y. Zick.  Finding fair and efficient allocations for matroid rank valuations.  _ACM Trans. Economics and Comput._ , 9(4):21:1–21:41, 2021.
  * Berger et al. (2022) B. Berger, A. Cohen, M. Feldman, and A. Fiat.  Almost full EFX exists for four agents.  In _AAAI_ , pages 4826–4833. AAAI Press, 2022.
  * Bouveret and Lemaître (2016) S. Bouveret and M. Lemaître.  Characterizing conflicts in fair division of indivisible goods using a scale of criteria.  _Auton. Agents Multi Agent Syst._ , 30(2):259–290, 2016.
  * Budish (2010) E. Budish.  The combinatorial assignment problem: approximate competitive equilibrium from equal incomes.  In _BQGT_ , page 74:1. ACM, 2010.
  * Caragiannis et al. (2019) I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang.  The unreasonable fairness of maximum nash welfare.  _ACM Trans. Economics and Comput._ , 7(3):12:1–12:32, 2019.
  * Chaudhury et al. (2020) B. R. Chaudhury, J. Garg, and K. Mehlhorn.  EFX exists for three agents.  In _EC_ , pages 1–19. ACM, 2020.
  * Christodoulou et al. (2016) G. Christodoulou, A. Kovács, and M. Schapira.  Bayesian combinatorial auctions.  _J. ACM_ , 63(2):11:1–11:19, 2016.
  * Christodoulou et al. (2023) G. Christodoulou, A. Fiat, E. Koutsoupias, and A. Sgouritsa.  Fair allocation in graphs.  In _EC_ , pages 473–488. ACM, 2023.
  * Christoforidis and Santorinaios (2024) V. Christoforidis and C. Santorinaios.  On the pursuit of efx for chores: Non-existence and approximations, 2024.  URL https://arxiv.org/abs/2406.10752.
  * Feige (2009) U. Feige.  On maximizing welfare when utility functions are subadditive.  _SIAM J. Comput._ , 39(1):122–142, 2009.
  * Feige and Norkin (2022) U. Feige and A. Norkin.  Improved maximin fair allocation of indivisible items to three agents, 2022.
  * Feige et al. (2021) U. Feige, A. Sapir, and L. Tauber.  A tight negative example for MMS fair allocations.  In _WINE_ , volume 13112 of _Lecture Notes in Computer Science_ , pages 355–372. Springer, 2021.
  * Feldman et al. (2020) M. Feldman, H. Fu, N. Gravin, and B. Lucier.  Simultaneous auctions without complements are (almost) efficient.  _Games Econ. Behav._ , 123:327–341, 2020.
  * Gafni et al. (2023) Y. Gafni, X. Huang, R. Lavi, and I. Talgam-Cohen.  Unified fair allocation of goods and chores via copies.  _ACM Transactions on Economics and Computation_ , 11:1 – 27, 2023.
  * Garg and Taki (2021) J. Garg and S. Taki.  An improved approximation algorithm for maximin shares.  _Artif. Intell._ , 300:103547, 2021.
  * Ghodsi et al. (2021) M. Ghodsi, M. T. Hajiaghayi, M. Seddighin, S. Seddighin, and H. Yami.  Fair allocation of indivisible goods: Improvement.  _Mathematics of Operations Research_ , 46(3):1038–1053, 2021.
  * Ghodsi et al. (2022) M. Ghodsi, M. HajiAghayi, M. Seddighin, S. Seddighin, and H. Yami.  Fair allocation of indivisible goods: Beyond additive valuations.  _Artificial Intelligence_ , 303:103633, 2022.  ISSN 0004-3702.
  * Gorantla et al. (2023) P. Gorantla, K. Marwaha, and S. Velusamy.  Fair allocation of a multiset of indivisible items.  In _SODA_ , pages 304–331. SIAM, 2023.
  * Gourvès and Monnot (2019) L. Gourvès and J. Monnot.  On maximin share allocations in matroids.  _Theor. Comput. Sci._ , 754:50–64, 2019.
  * Halpern et al. (2020) D. Halpern, A. D. Procaccia, A. Psomas, and N. Shah.  Fair division with binary valuations: One rule to rule them all.  In _WINE_ , volume 12495 of _Lecture Notes in Computer Science_ , pages 370–383. Springer, 2020.
  * Hosseini et al. (2021) H. Hosseini, S. Sikdar, R. Vaish, and L. Xia.  Fair and efficient allocations under lexicographic preferences.  In _AAAI_ , pages 5472–5480. AAAI Press, 2021.
  * Hummel (2023) H. Hummel.  On lower bounds for maximin share guarantees.  In _IJCAI_ , pages 2747–2755. ijcai.org, 2023.
  * Kulkarni et al. (2023) P. Kulkarni, R. Kulkarni, and R. Mehta.  Maximin share allocations for assignment valuations.  In _AAMAS_ , pages 2875–2876. ACM, 2023.
  * Kurokawa et al. (2018) D. Kurokawa, A. D. Procaccia, and J. Wang.  Fair enough: Guaranteeing approximate maximin shares.  _J. ACM_ , 65(2):8:1–8:27, 2018.
  * Lehmann et al. (2006) B. Lehmann, D. Lehmann, and N. Nisan.  Combinatorial auctions with decreasing marginal utilities.  _Games Econ. Behav._ , 55(2):270–296, 2006.
  * Mahara (2023) R. Mahara.  Existence of EFX for two additive valuations.  _Discret. Appl. Math._ , 340:115–122, 2023.
  * Mahara (2024) R. Mahara.  Extension of additive valuations to general valuations on the existence of efx.  _Mathematics of Operations Research_ , 49(2):1263–1277, 2024.
  * Oh et al. (2021) H. Oh, A. D. Procaccia, and W. Suksompong.  Fairly allocating many goods with few queries.  _SIAM J. Discret. Math._ , 35(2):788–813, 2021.
  * Pápai (2000) S. Pápai.  Strategyproof multiple assignment using quotas.  _Review of Economic Design_ , 5(1):91–105, Mar 2000.
  * Plaut and Roughgarden (2020) B. Plaut and T. Roughgarden.  Almost envy-freeness with general valuations.  _SIAM J. Discret. Math._ , 34(2):1039–1068, 2020.
  * Seddighin and Seddighin (2024) M. Seddighin and S. Seddighin.  Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem.  _Artif. Intell._ , 327:104049, 2024.
  * Uziahu and Feige (2023) G. B. Uziahu and U. Feige.  On fair allocation of indivisible goods to submodular agents, 2023.