# Best of Both Worlds: Agents with Entitlements††thanks: Institute for
Computer Science, Goethe University Frankfurt, Robert-Mayer-Strasse 11-15,
60325 Frankfurt am Main, Germany.
<EMAIL_ADDRESS>Martin Hoefer
and Giovanna Varricchio were supported by DFG grant Ho 3831/5-1.

Martin Hoefer  Marco Schmalhofer  Giovanna Varricchio

###### Abstract

Fair division of indivisible goods is a central challenge in artificial
intelligence. For many prominent fairness criteria including envy-freeness
($\mathsf{EF}$) or proportionality ($\mathsf{PROP}$), no allocations
satisfying these criteria might exist. Two popular remedies to this problem
are randomization or relaxation of fairness concepts. A timely research
direction is to combine the advantages of both, commonly referred to as _Best
of Both Worlds_ (BoBW).

We consider fair division _with entitlements_ , which allows to adjust notions
of fairness to heterogeneous priorities among agents. This is an important
generalization to standard fair division models and is not well-understood in
terms of BoBW results. Our main result is a lottery for additive valuations
and different entitlements that is ex-ante _weighted envy-free_
($\mathsf{WEF}$), as well as ex-post _weighted proportional up to one good_
($\mathsf{WPROP}1$) and _weighted transfer envy-free up to one good_
($\mathsf{WEF}(1,1)$). It can be computed in strongly polynomial time. We show
that this result is tight – ex-ante $\mathsf{WEF}$ is incompatible with any
stronger ex-post $\mathsf{WEF}$ relaxation.

In addition, we extend BoBW results on group fairness to entitlements and
explore generalizations of our results to instances with more expressive
valuation functions.

##  1 Introduction

Fair division of a set of indivisible goods is a prominent challenge at the
intersection of economics and computer science. It has attracted a lot of
attention over the last decades due to many applications in both simple and
complex real-world scenarios. Formally, we face an allocation problem with
finite sets $\mathcal{N}$ of $n$ agents and $\mathcal{G}$ of $m$ goods. Each
agent $i\in\mathcal{N}$ has a valuation function
$v_{i}:2^{\mathcal{G}}\rightarrow\mathbb{R}_{\geq 0}$. The goal is to compute
a “fair” allocation $\mathcal{A}=(A_{1},\ldots,A_{n})$, i.e., a fair partition
of the goods among the agents.

What is fair can certainly be a matter of debate. For this reason, several
fairness criteria have been introduced and studied. Envy-freeness
($\mathsf{EF}$) is probably one of the most intuitive concepts – it postulates
that once goods are allocated no agent strictly prefers goods received by any
other agent, i.e., $v_{i}(A_{i})\geq v_{i}(A_{j})$ for all
$i,j\in\mathcal{N}$. $\mathsf{EF}$ is a comparison-based notion. In contrast,
there are also threshold-based ones such as proportionality ($\mathsf{PROP}$):
$\mathcal{A}$ is proportional if every agent receives a bundle whose value is
at least her proportional share, i.e., $v_{i}(A_{i})\geq v_{i}(\mathcal{G})/n$
for every $i\in\mathcal{N}$.

Unfortunately, for indivisible goods, neither $\mathsf{PROP}$\- nor
$\mathsf{EF}$-allocations may exist. Two natural conceptual remedies to this
non-existence problem are (1) randomization or (2) relaxation of fairness
concepts. Towards (1), a random allocation that is $\mathsf{EF}$ in
expectation always exists (for every set of valuation functions): Select an
agent uniformly at random and give the entire set of goods $\mathcal{G}$ to
her. Then, however, every realization in the support is highly unfair – there
is always an agent who receives everything, while all others get nothing.
Moreover, it is easy to see that such an allocation might not even be Pareto-
optimal. Towards (2), a well-known relaxation of $\mathsf{EF}$ is envy-
freeness up to one good ($\mathsf{EF}1$) [18, 8]: Every agent shall value her
own bundle at least as much as any other agent’s bundle after removing some
good from the latter, i.e., for every $i,j\in\mathcal{N}$ there is
$g\in\mathcal{G}$ such that $v_{i}(A_{i})\geq v_{i}(A_{j}\setminus\\{g\\})$.
Whenever the valuations of the agents are monotone, an $\mathsf{EF}1$
allocation always exists and can be computed in polynomial time [18]. However,
different $\mathsf{EF}1$ allocations may advantage different agents. Similarly
to $\mathsf{EF}1$, proportionality up to one good ($\mathsf{PROP}1$) has also
been studied [14].

A timely research direction is to combine the advantages of both randomization
and relaxation, commonly referred to as Best of Both Worlds (BoBW) results. An
important result was obtained by both Aziz [2] and Freeman et al. [16] for
additive valuations – a lottery that is $\mathsf{EF}$ in expectation (ex-ante)
and $\mathsf{EF}1$ for every allocation in the support (ex-post). Moreover, it
can be implemented as a lottery over deterministic allocations with
polynomial-sized support. Both papers generalize the Probabilistic Serial (PS)
rule [7] for the matching case, when there are $n$ agents and $m=n$ goods. PS
is ex-ante $\mathsf{EF}$. By the Birkhoff-von Neumann decomposition, it can be
represented as a lottery over polynomially many deterministic allocations.
Furthermore, any allocation in the support assigns to each agent exactly one
good. This implies ex-post $\mathsf{EF}1$. Both [2, 16] generalize the
application of the Birkhoff-von Neumann decomposition to instances with
arbitrarily many goods.

In our work, we consider a more general framework to allow more flexibility in
the definition of fairness. Concepts like $\mathsf{EF}$ or $\mathsf{PROP}$
imply that all agents are symmetric, i.e., they are ideally treated as equals.
In many scenarios, however, there is an inherent asymmetry in the agent
population. Alternatively, it can be beneficial for an allocation mechanism to
have the option to reward certain agents. We follow the formal framework of
_entitlements_ [11, 4] that enables increased expressiveness. Formally, each
agent $i\in\mathcal{N}$ now has a weight or a priority $w_{i}>0$. Fairness
notions like $\mathsf{EF}$ or $\mathsf{PROP}$ are then refined based on the
weights (see Section 2 for formal definitions). Generally, we will use a
prefix “W” to refer to a fairness concept in the context of entitlements.

###  1.1 Our Contribution

We study lotteries that guarantee both ex-ante and ex-post guarantees for fair
division with additive valuations and different entitlements. We provide a
lottery that is ex-ante weighted stochastic-dominance envy-free
($\mathsf{WSD}$-$\mathsf{EF}$) and consequently ex-ante $\mathsf{WEF}$.
Applying a bihierarchy decomposition by Budish et al. [9], we show it is
possible to achieve ex-post $\mathsf{WPROP}1$ and $\mathsf{WEF}(1,1)$. The
latter implies that in every allocation $\mathcal{A}$ in the support, weighted
envy from agent $i$ to $j$ can be eliminated by moving entirely one good from
$A_{j}$ to $A_{i}$. All our constructions can be carried out in strongly
polynomial time. Perhaps surprisingly, this result is tight – we show that ex-
ante $\mathsf{WEF}$ is incompatible with any stronger ex-post $\mathsf{WEF}$
notion. In particular, a direct extension of [2, 16] to a lottery with ex-ante
$\mathsf{WEF}$ and ex-post $\mathsf{WEF}1$ is impossible.

Freeman et al. [16] investigate further combinations of ex-ante and ex-post
properties; namely, they provide a lottery that is ex-ante group fair as well
as ex-post $\mathsf{PROP}1$ and $\mathsf{EF}_{1}^{1}$. In an
$\mathsf{EF}_{1}^{1}$-allocation $\mathcal{A}$, we can eliminate envy from $i$
to $j$ when we remove one good from $A_{j}$ and add one good to $A_{i}$;
differently from $\mathsf{EF}(1,1)$, the good added to $A_{i}$ is _not
required_ to come from $A_{j}$. We prove that this result can be adapted to
hold also for instances with entitlements.

Finally, we expand the scope of BoBW towards more general valuations. For
equal entitlements, ex-ante $\mathsf{EF}$ and ex-post $\mathsf{EF}1$ is
possible in more general cases. For different entitlements, ex-ante
$\mathsf{WEF}$ and ex-post $\mathsf{WEF}(1,1)$ or $\mathsf{WPROP}1$ are no
longer compatible (even for two agents, one additive and one unit-demand). For
this reason, we focus on threshold-based guarantees – we show that it is
possible to compute in polynomial time a lottery that is ex-ante
$\mathsf{WPROP}$ and ex-post $\mathsf{WPROP}1$, even for XOS valuations.

###  1.2 Related Work

Fair division attracted an enormous amount of attention, and there is a large
number of surveys. We refer to a rather recent one by Amanatidis et al. [1]
and restrict attention to more directly related works.

In the context of BoBW, the $\mathsf{MMS}$-share is studied by Babaioff et al.
[5], who design a lottery simultaneously achieving ex-ante $\mathsf{PROP}$ and
ex-post $\mathsf{PROP}1$ \+ $\frac{1}{2}$-$\mathsf{MMS}$.

An orthogonal direction is pursued in [10] by introducing interim
$\mathsf{EF}$, a trade-off between ex-ante and ex-post $\mathsf{EF}$. Interim
$\mathsf{EF}$ requires that agent $i$, knowing the realization of her bundle
$A_{i}$, obtains more value from $A_{i}$ than the (conditional) expected value
of the bundle of any other agent $j$. Formally,
$v_{i}(S)\geq\mathbb{E}\left[v_{i}(A_{j})|A_{i}=S\right]$ for each
$S\subseteq\mathcal{G}$ such that $\mathbb{P}(A_{i}=S)>0$.
Interim-$\mathsf{EF}$ implies ex-ante $\mathsf{EF}$, and ex-post $\mathsf{EF}$
implies interim $\mathsf{EF}$. Furthermore, any interim $\mathsf{EF}$
allocation is ex-post $\mathsf{PROP}$, which implies that interim
$\mathsf{EF}$ allocations may not exist. In the matching case, a cleverly
crafted separation oracle for a linear program and an extension of the
Birkhoff-von Neumann decomposition can be combined to design a polynomial-time
algorithm that either provides an interim $\mathsf{EF}$ allocation or
determines it does not exist [10].

When agents are endowed with ordinal preferences rather than cardinal
valuation functions, stochastic-dominance envy-freeness is the most prominent
fairness notion for lotteries. It was first considered in [7] and later
systematically studied in [3].

For fair division with entitlements, the literature has focused on
characterizing picking sequences guaranteeing fairness properties [11, 12,
13], the problem of maximizing Nash social welfare [17, 23], and the
definition of appropriate shares [6]. To the best of our knowledge, BoBW
results have not been addressed so far.

##  2 Preliminaries

A fair division instance $\mathcal{I}$ is given by a triple
$(\mathcal{N},\mathcal{G},\\{v_{i}\\}_{i\in\mathcal{N}})$, where $\mathcal{N}$
is a set of $n$ agents and $\mathcal{G}$ is a set of $m$ indivisible goods.
Every agent $i\in\mathcal{N}$ has a valuation function
$v_{i}:2^{\mathcal{G}}\rightarrow\mathbb{R}^{+}$, where $v_{i}(A)$ represents
the value, or utility, of $i$ for the bundle $A\subseteq\mathcal{G}$. We
assume that valuations are monotone ($v(A)\leq v(B)$ for $A\subseteq B$) and
normalized $(v(\emptyset)=0$).

#### Classes of Valuations.

For each $i\in\mathcal{N}$ and $g\in\mathcal{G}$, $v_{i}(g)\geq 0$ represents
the value $i$ assigns to the good $g$. A valuation $v_{i}$ is _additive_ if
$v_{i}(A)=\sum_{g\in A}v_{i}(g)$.

A valuation function $v_{i}$ is _multi-demand_ if there exists
$k\in\mathbb{N}$ such that $v_{i}(A)$ is given by the sum of the $k$ most
valuable goods in $A$ for $i$. If $k=1$ we talk about _unit-demand_.

A valuation function $v_{i}$ is _cancelable_ if
$v_{i}(S\cup\\{g\\})>v_{i}(T\cup\\{g\\})\implies v_{i}(S)>v_{i}(T)$, for all
$S,T\subseteq\mathcal{G}$ and $\forall g\in\mathcal{G}\setminus(S\cup T)$.
Cancelable valuations generalize several classes studied in the literature,
e.g., additive, weakly-additive, budget-additive, product, and unit-demand.

A valuation function $v_{i}$ is _XOS_ if there is a family of additive set
functions $\mathcal{F}_{i}$ such that
$v_{i}(A)=\max_{f\in\mathcal{F}_{i}}f(A)$. XOS generalize additive and
submodular valuations.

In what follows, whenever we sort the goods in $\mathcal{G}$ according to the
valuation function of a specific agent, we assume ties are broken according to
a fixed ordering of $\mathcal{G}$. This serves to avoid technical and tedious
tie-breaking issues.

#### Entitlements.

We study fair division with entitlements. Each agent $i\in\mathcal{N}$ is
endowed with an _entitlement_ or _weight_ , $w_{i}>0$. For convenience, we
assume w.l.o.g. $\sum_{i\in\mathcal{N}}w_{i}=1$. We say that agents have
_equal entitlements_ if $w_{i}=\frac{1}{n}$, for all $i\in\mathcal{N}$, and
refer to this as the _unweighted setting_.

We next give an example of fair division instance with entitled and additive
agents.

######  Example 1 (A fair division instance with entitlements).

We outline an instance $\mathcal{I}^{*}$ given by
$(\mathcal{N},\mathcal{G},\\{v_{i}\\}_{i\in\mathcal{N}})$ and entitlements
$w$. The agents are $\mathcal{N}=\\{1,2,3\\}$, the goods
$\mathcal{G}=\\{g_{1},g_{2},g_{3},g_{4},g_{5}\\}$, and $w_{1}=\frac{1}{2}$,
$w_{2}=\frac{1}{3}$ and $w_{3}=\frac{1}{6}$ are the entitlements of agent
$1,2$ and $3$, respectively. The valuation functions are additive with values
of the agents for single goods shown in Table 1.

Throughout the paper, whenever we use $\mathcal{I}^{*}$, we mean the instance
we just described.

Table 1:  Agents’ valuations in Example 1 $g$ | $g_{1}$ | $g_{2}$ | $g_{3}$ | $g_{4}$
---|---|---|---|---
$v_{1}(g)$ | 8 | 8 | 5 | 2
$v_{2}(g)$ | 3 | 5 | 4 | 1
$v_{3}(g)$ | 4 | 7 | 6 | 2

$\small\blacksquare$

###  2.1 Weighted Fairness Notions

An allocation $\mathcal{A}=(A_{1},\dots,A_{n})$ is a disjoint partition of
$\mathcal{G}$ among the agents, where $A_{i}\cap A_{j}=\emptyset$, for each
$i\neq j$, and $\bigcup_{i\in\mathcal{N}}A_{i}=\mathcal{G}$. An allocation
$\mathcal{A}$ is _weighted envy-free_ ($\mathsf{WEF}$) if $w_{j}\cdot
v_{i}(A_{i})\geq w_{i}\cdot v_{i}(A_{j})$ for every $i,j\in\mathcal{N}$. An
allocation $\mathcal{A}$ is _weighted proportional_ ($\mathsf{WPROP}$) if
$v_{i}(A_{i})\geq w_{i}\cdot v_{i}(\mathcal{G})$ holds, for each
$i\in\mathcal{N}$.

Since goods are indivisible such allocations may not always exist, and relaxed
versions have been defined. An allocation $\mathcal{A}$ is _weighted
proportional up to one good_ ($\mathsf{WPROP}1$) if for each $i\in\mathcal{N}$
there exists $g\in\mathcal{G}\setminus A_{i}$ such that
$v_{i}(A_{i}\cup\\{g\\})\geq w_{i}\cdot v_{i}(\mathcal{G})$. Note that, for
additive valuations, $\mathsf{WEF}\Rightarrow\mathsf{WPROP}$ but, differently
from equal entitlements, $\mathsf{WEF}1\not\Rightarrow\mathsf{WPROP}1$.

Concerning envy-freeness, we have already discussed $\mathsf{EF}$ and
$\mathsf{EF}1$ in the introduction. We here work with a broader definition
that generalizes these notions.

######  Definition 1 ($\mathsf{WEF}(x,y)$).

For $x,y\in[0,1]$, an allocation $\mathcal{A}$ is called $\mathsf{WEF}(x,y)$
if for each $i,j\in\mathcal{N}$ there exists $g\in A_{j}$ such that
$w_{j}\cdot\left(v_{i}(A_{i})+y\cdot v_{i}(g)\right)\geq
w_{i}\cdot\left(v_{i}(A_{j})-x\cdot v_{i}(g)\right)$.

The definition of $\mathsf{WEF}(x,y)$ is meaningful mostly for additive
valuations. For general valuations, the idea of $\mathsf{WEF}(1,1)$ can be
expressed by $w_{j}\cdot v_{i}(A_{i}\cup\\{g\\})\geq w_{i}\cdot
v_{i}(A_{j}\setminus\\{g\\})$, and analogously for $\mathsf{WEF}(0,1)$ and
$\mathsf{WEF}(1,0)$. Conceptually, $\mathsf{WEF}(1,0)$ coincides with a notion
of _weighted envy-freeness up to one good_ ($\mathsf{WEF}1$) while
$\mathsf{WEF}(0,1)$ with a notion termed _weak weighted envy-freeness up to
one good_ ($\mathsf{WWEF}1$). $\mathsf{WEF}(1,1)$ has also been called
_transfer envy-freeness up to one good_ in the unweighted setting. Note that
in $\mathsf{WEF}(1,1)$ the good $g$ added to $A_{i}$ must come from $A_{j}$.
Assuming that $g$ may come from any other bundle leads to the following
(weaker) notion.

######  Definition 2 ($\mathsf{WEF}_{1}^{1}$).

An allocation $\mathcal{A}$ is called _weighted envy-free up to one good more
and less ( $\mathsf{WEF}_{1}^{1}$)_ if for each $i,j\in\mathcal{N}$ there
exist $g_{i},g_{j}\in\mathcal{G}$ such that $w_{j}\cdot
v_{i}(A_{i}\cup\\{g_{i}\\})\geq w_{i}\cdot v_{i}(A_{j}\setminus\\{g_{j}\\})$.

We move on to fairness concepts for fractional allocations. A _fractional
allocation_ $X=(x_{ig})_{i\in\mathcal{N},g\in\mathcal{G}}\in[0,1]^{n\times m}$
specifies the fraction of good $g$ that agent $i$ receives. We assume
fractional allocations are complete, i.e., $\sum_{i\in\mathcal{N}}x_{ig}=1$
for every $g\in\mathcal{G}$.

Towards extending group fairness [15] to weighted agents, consider a subset of
agents $S\subseteq\mathcal{N}$. We define $w_{S}=\sum_{i\in S}w_{i}$ as the
weight of the set, and $\cup_{j\in S}X_{j}=\left(\sum_{j\in
S}x_{jg}\right)_{g\in\mathcal{G}}$ as the total fraction of each good
$g\in\mathcal{G}$ assigned to the agents of $S$.

######  Definition 3 ($\mathsf{WGF}$).

A fractional allocation $X$ is _weighted group fair ( $\mathsf{WGF}$)_ if for
all non-empty subsets of agents $S,T\subseteq\mathcal{N}$, there is no
fractional allocation $X^{\prime}$ of $\cup_{j\in T}X_{j}$ to the agents in
$S$ such that $w_{S}\cdot v_{i}(X^{\prime}_{i})\geq w_{T}\cdot v_{i}(X_{i})$,
for all $i\in S$ and at least one inequality is strict.

Similarly to the unweighted setting, weighted group fairness implies other
(weighted) envy and efficiency notions, for example, $\mathsf{WEF}$ (if
$|S|=|T|=1$), $\mathsf{WPROP}$ (if $|S|=1,T=\mathcal{N}$), and Pareto-
optimality (if $S=T=\mathcal{N}$).

We finally focus on stochastic dominance, a standard fairness notion for
random allocations. For convenience, we here define it using fractional
allocations. Given any $i\in\mathcal{N}$, let us denote by $X_{i}$ and
$X_{i}^{\prime}$ the fractional bundles of agent $i$ in the allocations $X$
and $X^{\prime}$, respectively. Agent $i$ $\mathsf{SD}$ prefers $X_{i}$ to
$X^{\prime}_{i}$, written
$X_{i}\succeq^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{SD}$}}}_{i}X_{i}^{\prime}$,
if for any $g^{*}\in\mathcal{G}$

$\sum_{g\in\\{g|v_{i}(g)\geq
v_{i}(g^{*})\\}}x_{ig}\geq\sum_{g\in\\{g|v_{i}(g)\geq
v_{i}(g^{*})\\}}x^{\prime}_{ig}\enspace,$

where $x_{ig}$ and $x^{\prime}_{ig}$ represents the fraction for $i$ of
receiving $g$ in the two random allocations.

We say
$X_{i}\succ^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{SD}$}}}_{i}X_{i}^{\prime}$,
if
$X_{i}\succeq^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{SD}$}}}_{i}X^{\prime}_{i}$
and not
$X^{\prime}_{i}\succeq^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{SD}$}}}_{i}X_{i}$.
Notice that $\\{g|v_{i}(g)\geq v_{i}(g^{*})\\}$ is the set of goods that $i$
likes at least as much as $g^{*}$. Although we defined it by means of $v_{i}$,
this set only depends on the relative ordering of the goods and not on the
valuation $v_{i}$.

######  Definition 4 ($\mathsf{SD}$-$\mathsf{EF}$ and
$\mathsf{WSD}$-$\mathsf{EF}$).

A random allocation $X$ is _$\mathsf{SD}$ -envy-free
($\mathsf{SD}$-$\mathsf{EF}$)_ if for all $i,j\in\mathcal{N}$,
$X_{i}\succeq^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{SD}$}}}_{i}X_{j}$.
Similarly, we say $X$ is _$\mathsf{WSD}$ -envy-free
($\mathsf{WSD}$-$\mathsf{EF}$)_ if for all $i,j\in\mathcal{N}$, $w_{j}\cdot
X_{i}\succeq^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{SD}$}}}_{i}w_{i}\cdot
X_{j}$.

###  2.2 Deterministic Algorithms and Picking Sequences

For additive valuations, a straightforward round-robin algorithm yields an
$\mathsf{EF}1$ allocation. Clearly, when agents have different entitlements,
the round-robin algorithm might no longer provide a $\mathsf{WEF}1$
allocation. Different entitlements impose different priorities among agents,
which has resulted in the consideration of picking sequences.

A picking sequence for $n$ agents and $m$ goods is a sequence
$\pi=(i_{1},\dots,i_{m})$, where $i_{h}\in\mathcal{N}$, for $h=1,\dots,m$. An
allocation $\mathcal{A}$ is the result of the picking sequence $\pi$ if it is
the output of the following procedure: Initially every bundle is empty; then,
at time step $h$, $i_{h}$ inserts in her bundle the most preferred good among
the available ones. Once a good is selected, it is removed from the set of the
available goods.

In [12, 13], the authors characterize picking sequences for several fairness
criteria, including $\mathsf{WEF}1$, $\mathsf{WWEF}1$ as well as
$\mathsf{WEF}(x,1-x)$. For our purposes, we will rely on the following
characterization for $\mathsf{WEF}(x,y)$ (in the context of additive
valuations).

######  Proposition 1.

Let $t_{i},t_{j}$ be the number of picks of agents $i$, $j$, respectively, in
a prefix of $\pi$. A picking sequence $\pi$ is $\mathsf{WEF}(x,y)$ if and only
if for every prefix of $\pi$ and every pair of agents $i,j$, we have
$\frac{t_{i}+y}{w_{i}}\geq\frac{t_{j}-x}{w_{j}}$.

Chakraborty et al. [13] prove this proposition using the assumption $x+y=1$,
since $\mathsf{WEF}(x,y)$ allocations might not exist for $x+y<1$. The proof
can be easily extended, see the Appendix, beyond the assumption to show the
statement for all $x,y\in[0,1]$.

Note further that round-robin is not the only picking sequence achieving
$\mathsf{EF}1$ for equal entitlements. Any picking sequence that is
recursively balanced (RB), i.e. $|t_{i}-t_{j}\rvert\leq 1$ in any prefix of
$\pi$, results in an $\mathsf{EF}1$ allocation [2].

###  2.3 Random Allocations

A random allocation is a probability distribution $\mathcal{L}$ over
deterministic allocations. We mostly focus on additive valuations, so we
conveniently use a representation as matrix $X$ of marginal assignment
probabilities for each good to each agent (i.e., a complete fractional
allocation as defined above). We denote by $X^{\mathcal{L}}$ the fractional
allocation corresponding to a lottery $\mathcal{L}$. Notice that different
lotteries might produce the very same fractional allocation.

Throughout the paper, we denote by $X$ (resp. $Y$) fractional (resp. integral)
allocations in matrix form. Further, $X_{i}$ (resp. $Y_{i}$) denotes a
fractional (resp. integral) bundle of $i$.

#### Decomposing Fractional Matrices.

A decomposition of a fractional matrix $X$ is a convex combination of
deterministic allocations, i.e. $X=\lambda_{1}Y^{1}+\dots+\lambda_{k}Y^{k}$,
where $\sum_{h=1}^{k}\lambda_{h}=1$ and $y^{h}_{ig}\in\\{0,1\\}$ for each
$i\in\mathcal{N}$, $g\in\mathcal{G}$ and $h\in[k]=\\{1,\dots,k\\}$.

A constraint structure $\mathcal{H}$ consists of a collection of subsets
$S\in\mathcal{N}\times\mathcal{G}$. Every $S\in\mathcal{H}$ comes with a lower
and upper quota denoted by $\underline{q}_{S}$ and $\overline{q}_{S}$,
respectively. Quotas are integer numbers stored in $\mathbf{q}$.

A $n\times m$ matrix $Y$ is feasible under $\mathbf{q}$ if for each
$S\in\mathcal{H}$

$\underline{q}_{S}\leq\sum_{(i,g)\in S}y_{ig}\leq\overline{q}_{S}\enspace.$

A constraint structure $\mathcal{H}$ is a _hierarchy_ if, for every
$S,S^{\prime}\in\mathcal{H}$, either $S\cap S^{\prime}=\emptyset$ or one is
contained in the other. $\mathcal{H}$ is a _bihierarchy_ if it can be
partitioned into $\mathcal{H}=\mathcal{H}_{1}\cup\mathcal{H}_{2}$, such that
$\mathcal{H}_{1}\cap\mathcal{H}_{2}=\emptyset$ and both $\mathcal{H}_{1}$ and
$\mathcal{H}_{2}$ are hierarchies.

Budish et al. [9] generalize the well-known decomposition theorem by Birkhoff
and von Neumann:

######  Theorem 1.

Given any fractional allocation $X$, a bihierarchy $\mathcal{H}$ and
corresponding quotas $\mathbf{q}$, if $X$ is feasible under $\mathbf{q}$,
then, there exists a polynomial decomposition into integral matrices. Every
matrix in the decomposition is feasible under $\mathbf{q}$. Further, the
decomposition can be obtained in strongly polynomial time.

In the rest of this paper, given a fractional allocation $X$ and a bihierarchy
$\mathcal{H}$, we define the quotas in $\mathbf{q}$ as follows: for every
$S\in\mathcal{H}$ we set $\underline{q}_{S}=\lfloor x_{S}\rfloor$ and
$\overline{q}_{S}=\lceil x_{S}\rceil$, where $x_{S}=\sum_{(i,g)\in S}x_{ig}$.
The decomposition obtained with these quotas and bihierarchy $\mathcal{H}$
will be called the $\mathcal{H}$-decomposition.

#### Utility Guarantee Bihierarchy.

An extremely useful bihierarchy is defined as follows. We set
$\mathcal{H}_{1}=\\{C_{g}\ |\ g\in\mathcal{G}\\}$, where $C_{g}=\\{(i,g)\ |\
i\in\mathcal{N}\\}$ represent columns. Roughly speaking, the hierarchy
$\mathcal{H}_{1}$ ensures that, in any allocation of the decomposition, every
good is integrally assigned (and therefore the allocation is complete).

For agent $i\in\mathcal{N}$, we consider the goods in non-increasing order of
$i$’s valuation, i.e., $v_{i}(g_{1})\geq\ldots\geq v_{i}(g_{m})$. Recall that
ties are broken according to a predefined ordering of $\mathcal{G}$. We set
$\mathcal{S}_{i}=\\{\\{g_{1}\\},\\{g_{1},g_{2}\\},\dots,\\{g_{1},\dots,g_{m}\\}\\}$.
In other words, for every $h\in[m]$, $\mathcal{S}_{i}$ contains a set of the
$h$ most preferred goods of $i$. Define $\mathcal{H}_{2}=\\{(i,S)\ |\
i\in\mathcal{N},S\in\mathcal{S}_{i}\\}\cup\\{(i,g)|i\in\mathcal{N},g\in\mathcal{G}\\}$.
The second set of constraints implies that if $x_{ig}=0$ (resp. $x_{ig}=1$)
then $y_{ig}=0$ (resp. $y_{ig}=1$), for any $Y$ in the decomposition. Note
that (for convenience later on) we slightly abuse notation for
$\mathcal{H}_{2}$ as it is not a set of (row, col)-pairs.

Finally, the _utility guarantee bihierarchy_ is given by
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}=\mathcal{H}_{1}\cup\mathcal{H}_{2}$.
Clearly, both $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ are hierarchies.

This bihierarchy was fundamental in [9]. We here state it in a slightly
stronger version (see [16] for the proof).

######  Corollary 1 (Utility Guarantee up to one Good More or Less).

Suppose we are given a fractional allocation $X$, $v_{i}$ is an additive
valuation function, and $v_{i}(X_{i})=\mathbb{E}\left[v_{i}(X_{i})\right]$.
Then for any matrix $Y$ in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X$ the following hold:

  1. 1.

if $v_{i}(Y_{i})<v_{i}(X_{i})$, then $\exists\ g\not\in Y_{i}$ with $x_{ig}>0$
such that $v_{i}(Y_{i})+v_{i}(g)>v_{i}(X_{i})$;

  2. 2.

if $v_{i}(Y_{i})>v_{i}(X_{i})$, then $\exists\ g\in Y_{i}$ with $x_{ig}<1$
such that $v_{i}(Y_{i})-v_{i}(g)<v_{i}(X_{i})$.

In other words, Corollary 1 ensures that, in any deterministic allocation in
the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition,
the valuation of any agent $i$ differs from her expected value by at most the
value of one good. Moreover, such a good must have a positive probability of
occurring in $i$’s bundle.

##  3 Additive Valuations with Entitlements

In this section, we present a lottery for additive valuations that
simultaneously achieves ex-ante $\mathsf{WSD}$-$\mathsf{EF}$ (and hence ex-
ante $\mathsf{WEF}$) and ex-post $\mathsf{WEF}(1,1)+\mathsf{WPROP}1$. In
contrast to equal entitlements, we show a weaker ex-post guarantee. However,
we prove that this is necessary since no stronger envy notion is compatible
with ex-ante $\mathsf{WEF}$. We also generalize a result of Freeman et al.
[16] to entitlements: Similarly to the unweighted setting, we design a lottery
that is ex-ante $\mathsf{WGF}$ and ex-post
$\mathsf{WEF}_{1}^{1}+\mathsf{WPROP}1$ .

###  3.1 Ex-ante $\mathsf{WSD}$-$\mathsf{EF}$, Ex-post $\mathsf{WEF}(1,1)$ \+
$\mathsf{WPROP}1$

The main contribution of this subsection is as follows.

######  Theorem 2.

For entitlements and additive valuations, we can compute in strongly
polynomial time a lottery that is ex-ante $\mathsf{WSD}$-$\mathsf{EF}$ and ex-
post $\mathsf{WPROP}1$ \+ $\mathsf{WEF}(1,1)$.

Let us start by introducing our main algorithm DifferentSpeedsEating (DSE),
which is inspired by Eating for equal entitlements in [2]. Agents continuously
eat their most preferred available good at speed equal to her entitlement.
Every agent starts eating her most preferred good; as soon as a good has been
completely eaten it is removed from the set of available goods. Each agent
that was eating this good continues eating her most preferred remaining one.
The procedure terminates when no good remains. See Algorithm 1 for a formal
description. Observe that by precomputing the times at which goods are
removed, we can implement the algorithm in strongly polynomial time.

Input: An instance
$\mathcal{I}=(\mathcal{N},\mathcal{G},\\{v_{i}\\}_{i\in\mathcal{N}})$ and the
entitlements $w_{1},\dots,w_{n}$

Output: A fractional allocation $X$

$X\leftarrow\mathbf{0}_{n\times m}$

// current fractional allocation

$\mathbf{z}\leftarrow\mathbf{1}_{m}$

// remaining supply of each good

1

2while  _$\mathcal{G}\neq\emptyset$_ do

$\mathbf{s}\leftarrow\mathbf{0}_{m}$

// eating speed on each item

3 for  _$i\in\mathcal{N}$_ do

$g^{i}\leftarrow\operatorname*{arg\,max}_{g\in\mathcal{G}}v_{i}(g)$

// most favored item

$\mathbf{s}(g^{i})\leftarrow\mathbf{s}(g^{i})+w_{i}$

// sum speeds of each agent

4

$\mathbf{t}\leftarrow\mathbf{1}_{m}$

// eating time of each item

5 for  _$g\in\mathcal{G}$_ do

$\mathbf{t}(g)\leftarrow\frac{\mathbf{z}(g)}{\mathbf{s}(g)}$

// compute finishing times

6

$t\leftarrow\min_{g\in\mathcal{G}}\mathbf{t}(g)$

// time when first item is finished

7 for  _$i\in\mathcal{N}$_ do

$x\leftarrow t\cdot w_{i}$

// amount of items eaten by $i$

$x_{ig^{i}}\leftarrow x_{ig^{i}}+x$

// eat fraction of $g^{i}$

$\mathbf{z}(g^{i})\leftarrow\mathbf{z}(g^{i})-x$

// reduce supply of $g^{i}$

8

$\mathcal{G}\leftarrow\mathcal{G}\setminus\\{g\in\mathcal{G}\mid\mathbf{t}(g)\leq\mathbf{t}(g^{\prime})\text{
for all }g^{\prime}\in\mathcal{G}\\}$

// remove finished items

9

10return _X_

Algorithm 1 DifferentSpeedsEating

We denote by $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ the
output of DSE. The key properties are summarized in the following lemma.

######  Lemma 1.

Let $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ be the output of
DSE, then

  1. 1.

$\sum_{g\in\mathcal{G}}x^{\textsc{DSE}}_{ig}=w_{i}\cdot m$ for each
$i\in\mathcal{N}$;

  2. 2.

the time needed for agent $i$ to eat one unit of goods is $\frac{1}{w_{i}}$;

  3. 3.

overall, one unit of goods is consumed in one unit of time and, therefore, DSE
runs for $m$ time units.

We define the _eating time_ of a good $g$ as the point in time when it has
been entirely consumed (during a run of DSE). Whenever an agent starts eating
a good $g$, she can start eating another good only after the eating time of
$g$.

Before proceeding to the proof of Theorem 2, let us provide an example
describing a run of DSE on the instance $\mathcal{I}^{*}$ introduced above in
Example 1.

######  Example 2 (DSE at work).

Let us observe the behavior of DSE on $\mathcal{I}^{*}$.

The agents’ priorities for the goods are the following:

$\displaystyle g_{1}\succ_{1}g_{2}\succ_{1}g_{3}\succ_{1}g_{4}\ ,$
$\displaystyle g_{2}\succ_{2}g_{3}\succ_{2}g_{1}\succ_{2}g_{4}\ ,$
$\displaystyle g_{2}\succ_{3}g_{3}\succ_{3}g_{1}\succ_{3}g_{4}\ .$

Notice that, for agent $1$, goods $g_{1}$ and $g_{2}$ are identical and ties
are broken in favor of the good coming first in the ordering
$g_{1},\dots,g_{4}$. Moreover, agents $2$ and $3$ have the same priority
order, for this reason they will always be eating the same good.

During a run of DSE, Whenever a good gets entirely eaten up, the behavior of
agents who were eating this good changes. In the following, we only refer to
time points where these events happen. Indeed, the times are the eating times
of the good(s) that have been completely consumed.

Time $\mathbf{t=0}$ : At the beginning, $x_{ig}=0$, for all $i\in\mathcal{N}$
and $g\in\mathcal{G}$. Agent $1$ starts eating $g_{1}$ while agents $2$ and
$3$ good $g_{2}$. Notice that agents $2$ and $3$ together have the same speed
as agent $1$.

Time $\mathbf{t=2}$ : $g_{1}$ and $g_{2}$ get fully consumed and
$x_{1g_{1}}=1$, $x_{2g_{2}}=\frac{2}{3}$ and $x_{3g_{2}}=\frac{1}{3}$,
respectively. Agent $1$ will start eating $g_{3}$ as well as agents $2$ and
$3$. All the agents together have speed equal to $1$. Notice that agent $1$
would prefer good $g_{2}$, however, it has been consumed entirely by agents
$2$ and $3$.

Time $\mathbf{t=3}$ : $g_{3}$ is now fully consumed. We have
$x_{1g_{3}}=\frac{1}{2}$, $x_{2g_{3}}=\frac{1}{3}$ and
$x_{3g_{3}}=\frac{1}{6}$, respectively. The only remaining available good is
$g_{4}$, all the agents are now starting to eat it.

Time $\mathbf{t=4}$ : All goods are fully consumed and
$x_{1g_{4}}=\frac{1}{2}$, $x_{2g_{4}}=\frac{1}{3}$ and
$x_{3g_{4}}=\frac{1}{6}$. DSE returns the fractional allocation:

$X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}=\begin{pmatrix}\vskip
3.0pt plus 1.0pt minus 1.0pt1&0&\frac{1}{2}&\frac{1}{2}\\\ \vskip 3.0pt plus
1.0pt minus 1.0pt0&\frac{2}{3}&\frac{1}{3}&\frac{1}{3}\\\ \vskip 3.0pt plus
1.0pt minus 1.0pt0&\frac{1}{3}&\frac{1}{6}&\frac{1}{6}\end{pmatrix}\ .$

$\small\blacksquare$

Our first result is that the output of DSE is $\mathsf{WSD}$-$\mathsf{EF}$.

######  Proposition 2.

$X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is
$\mathsf{WSD}$-$\mathsf{EF}$.

###### Proof.

For convenience, we use
$X=X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$. Let us consider an
agent $i\in\mathcal{N}$. Note that the goods $g_{1},\dots,g_{m}$ are ordered
in the same manner as in DSE for agent $i$, since we always break ties
according to a predefined ordering of $\mathcal{G}$. Now consider another
agent $j\in\mathcal{N}$. Using the notation $G_{k}=\\{g_{1},\dots,g_{k}\\}$
for the first $k$ goods in $i$’s ordering, we show

$w_{j}\cdot\sum_{g\in G_{k}}x_{ig}\geq w_{i}\cdot\sum_{g\in
G_{k}}x_{jg}\enspace,$ (1)

for every $k\in[m]$, and $\mathsf{WSD}$-$\mathsf{EF}$ follows for agent $i$.

Let $t_{k}$ be the time when $i$ stops eating $g_{k}$ during the run of DSE.
We set $t_{k}=t_{k-1}$ if good $g_{k}$ has been completely consumed before
time $t_{k-1}$ by others. This means that, by the time $t_{k}$, no good in
$G_{k}$ remains available. On the one hand, until time $t_{k}$, agent $i$
could only consume goods in $G_{k}$, implying $w_{i}\cdot t_{k}=\sum_{g\in
G_{k}}x_{ig}$. On the other hand, every good in $G_{k}$ has been fully
consumed by that time, i.e., $w_{j}\cdot t_{k}\geq\sum_{g\in G_{k}}x_{jg}$,
for every $j\in\mathcal{N}$. Combining these two properties proves Equation 1
and, hence, the theorem. ∎

It is known that $\mathsf{SD}$-$\mathsf{EF}$ implies ex-ante $\mathsf{EF}$ for
additive valuations; it remains true for different entitlements. We refer to
the appendix for the formal proof of the following proposition.

######  Proposition 3.

Given a fractional allocation $X$, if $X$ is ex-ante
$\mathsf{WSD}$-$\mathsf{EF}$, then $X$ is ex-ante $\mathsf{WEF}$.

Proposition 2 and Proposition 3 show that the outcome of DSE satisfies the ex-
ante properties stated in Theorem 2.

So far we have shown ex-ante properties of lotteries having the output of the
DSE as fractional matrix representation. In the remaining part of this
subsection, we show how to get good properties ex-post. In particular, we
start from the output of the DSE, namely,
$X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$. We apply the
Budish’s decomposition with the bihierarchy
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$.

Before proceeding, we give an example of such a decomposition as well as some
insights on the guarantees obtained thanks to the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$ bihierarchy.
We again make use of instance $\mathcal{I}^{*}$; the allocation
$X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ was computed in
Example 2.

######  Example 3 (The $\mathcal{H}^{\mathsf{UG}}$-decomposition).

The
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is a convex
combination $\lambda_{1}Y^{1}+\dots+\lambda_{k}Y^{k}$, for some integer $k$.
Every allocation $Y^{h}$ is deterministic and its properties are determined by
the bihierarchy
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$. In the
following, we use $Y$ to refer to a generic deterministic allocation in the
decomposition.

Recall that
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}=\mathcal{H}_{1}\cup\mathcal{H}_{2}$.
Interpreting an allocation as a matrix, the hierarchy $\mathcal{H}_{1}$
represents columns and only ensures that any $Y$ is complete.

Let us now consider $\mathcal{H}_{2}$. Recall, $\mathcal{H}_{2}=\\{(i,S)\ |\
i\in\mathcal{N},S\in\mathcal{S}_{i}\\}\cup\\{(i,g)|i\in\mathcal{N},g\in\mathcal{G}\\}$.

By Theorem 1, every matrix of an allocation $Y$ in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
is feasible under the quotas $\underline{q}_{A}=\lfloor
x^{\textsc{DSE}}_{A}\rfloor$ and $\overline{q}_{A}=\lceil
x^{\textsc{DSE}}_{A}\rceil$, for every $A\in\mathcal{H}_{2}$, where
$x^{\textsc{DSE}}_{A}=\sum_{(i,g)\in A}x^{\textsc{DSE}}_{ig}$. Note that only
one agent appears in any pair of $\mathcal{H}_{2}$. Hence, we discuss the
implications of Theorem 1 agent by agent.

#### Agent $1$:

The pair $(1,S)$ belongs to $\mathcal{H}_{2}$ if and only if
$S\in\mathcal{S}_{1}\cup\\{\\{g_{2}\\},\\{g_{3}\\},\\{g_{4}\\}\\}$, where
$\mathcal{S}_{1}=\\{\\{g_{1}\\},\\{g_{1},g_{2}\\},\\{g_{1},g_{2},g_{3}\\},\\{g_{1},g_{2},g_{3},g_{4}\\}\\}$.
The feasibility conditions imply:

$\displaystyle y_{1g_{1}}=1,$ $\displaystyle y_{1g_{1}}+y_{1g_{2}}=1,$
$\displaystyle 1\leq y_{1g_{1}}+y_{1g_{2}}+y_{1g_{3}}\leq 2,$ $\displaystyle
y_{1g_{1}}+y_{1g_{2}}+y_{1g_{3}}+y_{1g_{4}}=2\ ,$

and

$\displaystyle y_{1g_{2}}=0,$ $\displaystyle 0\leq y_{1g_{3}}\leq 1,$
$\displaystyle 0\leq y_{1g_{4}}\leq 1\ .$

In other words, in any deterministic allocation $Y$, agent $1$ always receives
$2$ goods. In particular, she always gets $g_{1}$ but never $g_{2}$. Moreover,
she gets either $g_{3}$ or $g_{4}$, but not both of them.

#### Agent $2$:

The pair $(2,S)$ belongs to $\mathcal{H}_{2}$ if and only if
$S\in\mathcal{S}_{2}\cup\\{\\{g_{1}\\},\\{g_{3}\\},\\{g_{4}\\}\\}$, where
$\mathcal{S}_{2}=\\{\\{g_{2}\\},\\{g_{2},g_{3}\\},\\{g_{2},g_{3},g_{1}\\},\\{g_{2},g_{3},g_{1},g_{4}\\}\\}$.
In this case, the feasibility conditions imply

$\displaystyle 0\leq y_{2g_{2}}\leq 1,$ $\displaystyle
y_{2g_{2}}+y_{2g_{3}}=1,$ $\displaystyle y_{2g_{2}}+y_{2g_{3}}+y_{2g_{1}}=1,$
$\displaystyle 1\leq y_{2g_{2}}+y_{2g_{3}}+y_{2g_{1}}+y_{2g_{4}}\leq 2\ ,$

and

$\displaystyle y_{2g_{1}}=0,$ $\displaystyle 0\leq y_{2g_{3}}\leq 1,$
$\displaystyle 0\leq y_{2g_{4}}\leq 1\ .$

Therefore, the bundle of agent $2$ is of size either $1$ or $2$. It never
contains $g_{1}$, but must contain one good between $g_{2}$ and $g_{3}$, and
possibly contains $g_{4}$.

#### Agent $3$:

The pair $(3,S)$ belongs to $\mathcal{H}_{2}$ if and only if
$S\in\mathcal{S}_{3}\cup\\{\\{g_{1}\\},\\{g_{3}\\},\\{g_{4}\\}\\}$, where
$\mathcal{S}_{3}=\\{\\{g_{2}\\},\\{g_{2},g_{3}\\},\\{g_{2},g_{3},g_{1}\\},\\{g_{2},g_{3},g_{1},g_{4}\\}\\}$.
In this case, $0\leq y_{3g_{2}}+y_{3g_{3}}+y_{3g_{1}}+y_{3g_{4}}\leq 1$ and
$y_{3g_{1}}=0$, hence, agent $3$ can receive at most one of
$g_{2},g_{3},g_{4}$ and never receives $g_{1}$.

Finally, we provide a concrete
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ for
$\mathcal{I}^{*}$. Considering that rows represent agents and columns
represent goods, it is easy to verify that every deterministic allocation
satisfies the aforementioned properties.

$X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}=\frac{1}{6}\cdot\underbrace{\begin{pmatrix}1&0&0&1\\\
0&1&0&0\\\ 0&0&1&0\end{pmatrix}}_{Y^{1}}\ +\
\frac{1}{6}\cdot\underbrace{\begin{pmatrix}1&0&1&0\\\ 0&1&0&0\\\
0&0&0&1\end{pmatrix}}_{Y^{2}}\ +\
\frac{1}{3}\cdot\underbrace{\begin{pmatrix}1&0&0&1\\\ 0&0&1&0\\\
0&1&0&0\end{pmatrix}}_{Y^{3}}\ +\
\frac{1}{3}\cdot\underbrace{\begin{pmatrix}1&0&1&0\\\ 0&1&0&1\\\
0&0&0&0\end{pmatrix}}_{Y^{4}}\ .$

$\small\blacksquare$

We notice that $Y^{4}$ in Example 3 is not $\mathsf{WEF}1$. Indeed, in $Y^{4}$
agents $1$ and $2$ receive two goods each while agent $3$ has an empty bundle,
thus agent $3$ $\mathsf{WEF}1$-envies any other agent. On the other hand,
every allocation $Y^{h}$, for $h=1,\dots,4$, is $\mathsf{WEF}(1,1)$ and
$\mathsf{WPROP}1$. We next show this is always the case for the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of any $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$.

######  Theorem 3.

Every deterministic allocation $Y$ in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is
$\mathsf{WEF}(1,1)$.

To show the theorem we need some preliminary notions.

#### Goods Eaten by $i$ at Time $t$.

Recall that DSE runs for $m$ units of time. Every agent $i$ exactly eats a
total mass of $w_{i}\cdot m$ of $\mathcal{G}$ during DSE. Let
$g_{1},\dots,g_{m}$ be the ordering of goods according to $v_{i}$. We define
$\mathsf{Eaten}(i,t)=\\{g_{1},\dots,g_{\ell}\\}=G_{\ell}$, where $g_{\ell}$ is
either a good that agent $i$ just finished to consume (i.e., $t$ is the eating
time of $g_{\ell}$ and agent $i$ was consuming it) or agent $i$ at time $t$ is
eating the good $g_{\ell+1}$, which has not been finished yet. Consequently,
by time $t$, agent $i$ may have contributed only to the consumption of goods
in $G_{\ell}$. In particular, all goods in $G_{\ell}$ have been entirely
consumed (by $i$ or others), since otherwise $i$ would not start eating
$g_{\ell+1}$.

Recall that $w_{i}$ is the speed of $i$. At time $t=\frac{k}{w_{i}}$ agent $i$
ate a total mass $k$ of goods. With the next lemma, we show that the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
guarantees agent $i$ deterministically receives at most $k$ goods from the
ones eaten by time $\frac{k}{w_{i}}$.

######  Lemma 2.

Given any deterministic allocation $Y$ in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$, for every
$i\in\mathcal{N}$ and $k=1,\dots,\lfloor w_{i}\cdot m\rfloor$,
$|Y_{i}\cap\mathsf{Eaten}(i,\frac{k}{w_{i}})\rvert\leq k$. Furthermore,
$\lfloor w_{i}\cdot m\rfloor\leq|Y_{i}\rvert\leq\lceil w_{i}\cdot m\rceil$.

###### Proof.

By definition, $\mathsf{Eaten}(i,\frac{k}{w_{i}})=G_{\ell}$, the $\ell$ most
preferred goods of $i$, for some $\ell$. Thus, by the time $\frac{k}{w_{i}}$,
agent $i$ only ate goods in $G_{\ell}$ and possibly is currently eating the
next less preferred good. Moreover, goods are eaten by $i$ in the same
ordering we used to build the collection $\mathcal{S}_{i}$ in the definition
of $\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$ implying
$(i,G_{\ell})\in\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$.
Since $|Y_{i}\cap\mathsf{Eaten}(i,\frac{k}{w_{i}})\rvert=\sum_{g\in
G_{\ell}}y_{ig}$, the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
properties imply $\sum_{g\in G_{\ell}}y_{ig}\leq\big{\lceil}\sum_{g\in
G_{\ell}}x_{ig}\big{\rceil}$. This last is upper-bounded by $k$ because of
these two simple observations: $g_{\ell}$ is fully consumed by the time
$\frac{k}{w_{i}}$, and at that time agent $i$ ate $k$ units of goods. The
first claim follows.

The second claim immediately follows by the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
properties, since
$(i,\mathcal{G})\in\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$.
∎

Given any deterministic allocation $Y$ in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition,
consider agent $i$ and sort the goods in $Y_{i}$ in a non-increasing manner
with respect to $v_{i}$: $Y_{i}=\\{g^{i}_{1},\dots,g^{i}_{h_{i}}\\}$ and
$v_{i}(g^{i}_{1})\geq\dots\geq v_{i}(g^{i}_{h_{i}})$. By Lemma 2, we see
$h_{i}=\lfloor w_{i}\cdot m\rfloor$ or $h_{i}=\lceil w_{i}\cdot m\rceil$.

#### Stopping vs. Eating Time.

Given any deterministic allocation $Y$ in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X$, for each $i\in\mathcal{N}$ and $k\in[h_{i}]$, we define the stopping
time by $s(g_{k}^{i})=\min\\{t(g_{k}^{i}),\frac{k}{w_{i}}\\}$. Here
$t(g_{k}^{i})$ is the time when $g_{k}^{i}$ has been entirely consumed during
the DSE, i.e., the eating time of $g_{k}^{i}$. Note that $s(g_{k}^{i})$,
differently from $t(g_{k}^{i})$, depends on $Y$: Indeed, in $Y_{i}$ good
$g_{k}^{i}$ is the $k$-th most preferred good. However, if the eating time is
greater than $\frac{k}{w_{i}}$, this good might appear as $(k+1)$-th most
preferred good in another deterministic allocation of the decomposition. For
convenience, we omit $Y$ in the notation since we only discuss stopping times
of single allocations. Let us show a couple of useful properties of stopping
times.

######  Lemma 3.

Given any deterministic allocation $Y$ in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$, let $g_{k}^{i}$
be the $k$-th most preferred good in $Y_{i}$, it holds
$s(g_{k}^{i})\in\left(\frac{k-1}{w_{i}},\frac{k}{w_{i}}\right]$.

###### Proof.

By definition,
$s(g_{k}^{i})=\min\\{t(g_{k}^{i}),\frac{k}{w_{i}}\\}\leq\frac{k}{w_{i}}$. For
contradiction, suppose $t(g_{k}^{i})\leq\frac{k-1}{w_{i}}$. Then,
$g_{k}^{i}\in Y_{i}\cap\mathsf{Eaten}\left(i,\frac{k-1}{w_{i}}\right)$. Notice
that $t(g_{1}^{i})\leq\dots\leq t(g_{k}^{i})$, by definition of DSE, and
therefore $g_{h}^{i}\in
Y_{i}\cap\mathsf{Eaten}\left(i,\frac{k-1}{w_{i}}\right)$, for each
$h=1,\dots,k$. In conclusion,
$\left|Y_{i}\cap\mathsf{Eaten}\left(i,\frac{k-1}{w_{i}}\right)\right|\geq k$
which is a contradiction by Lemma 2, and hence
$t(g_{k}^{i})>\frac{k-1}{w_{i}}$. ∎

For the eating time $t(g_{k}^{i})$ the same lower bound holds, but we can only
upper bound it by $\frac{k+1}{w_{i}}$. This difference will be crucial in the
proof of Theorem 3 and requires the definition of stopping times.

######  Lemma 4.

Given any deterministic allocation $Y$ in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$, let $g_{k}^{i}$
be the $k$-th most preferred good in $Y_{i}$. For every good $g$ coming
earlier in $i$’s ordering of goods, it holds that $s(g)<s(g_{k}^{i})$.

###### Proof.

The claim follows by the definition of stopping time and the properties of
DSE. Indeed, by the definition of stopping time $s(g)\leq t(g)$, and
$t(g)<\min\\{t(g_{k}^{i}),\frac{k}{w_{i}}\\}=s(g_{k}^{i})$. The second
inequality holds because at time $s(g_{k}^{i})$ agent $i$ is eating or
finishes to eat $g_{k}^{i}$, and $g$ must have been eaten before $i$ starts
eating $g_{k}^{i}$. Further, the inequality is strict since agent $i$ ate a
positive fraction of $g_{k}^{i}$ (that is, $x_{ig_{k}^{i}}>0$); otherwise,
since $(i,g_{k}^{i})\in\mathcal{H}_{2}$, $x_{ig_{k}^{i}}=0$ would imply
$y_{ig_{k}^{i}}=0$ and, hence, $g_{k}^{i}\not\in Y_{i}$. ∎

We are now ready to show Theorem 3.

###### Proof of Theorem 3.

Let $Y$ be any deterministic allocation in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$. The proof
proceeds as follows: We first generate a picking sequence $\pi$, then show
that $Y$ is the output of such a picking sequence, and finally prove that
$\pi$ satisfies Proposition 1, for $x=y=1$. This shows that $Y$ is
$\mathsf{WEF}(1,1)$.

Defining $\pi$.  We sort the goods $\mathcal{G}$ in a non-increasing order of
stopping times $s_{1},\dots,s_{m}$ (defined according to $Y$). If $g\in Y_{i}$
is the $h$-th good in this ordering, then $\pi(h)=i$.

$Y$ is the result of $\pi$.  Assume $i$ is the $h$-th agent in $\pi$. Assume
that $\pi(h)=i$ is the $k$-th occurrence of $i$ in $\pi$. We show that for
each $h\in[m]$, the most preferred available good for $i$ is exactly
$g_{k}^{i}$. Let us proceed by induction on $h$.

For $h=1$, clearly, $k=1$. By Lemma 4, $g_{1}^{i}$ must be the most preferred
good of $i$, otherwise we contradict the fact that $s_{1}=s(g_{1}^{i})$ is the
minimum stopping time. At this point no good has been assigned, so $i$ selects
$g_{1}^{i}$.

Assume the statement is true until the $h$-th component of $\pi$. We show it
is true for $h+1\leq m$. Suppose a good $g$ coming before $g_{k}^{i}$, in
$i$’s ordering, is still available. By Lemma 4, there exists $h^{\prime}$ s.t.
$s_{h^{\prime}}=s(g)<s(g_{k}^{i})$ with $h^{\prime}\leq h$. By the inductive
hypothesis, $g$ must have been assigned to $\pi(h^{\prime})$. On the other
hand, $g_{k}^{i}$ is still available, otherwise there exists $h^{\prime}\leq
h$, such that $\pi(h^{\prime})$ picked $g_{k}^{i}$ during the $h^{\prime}$-th
round – a contradiction with the inductive hypothesis.

$\pi$ satisfies Proposition 1.  We now show that $\pi$ satisfies
$\mathsf{WEF}(1,1)$. Consider any prefix of $\pi$ and any pair of agents
$i,j$. Let us denote by $t_{i}$ (resp. $t_{j}$) the number of picks of agent
$i$ (resp. $j$) in the considered prefix. Let $s_{j}$ and $s_{i}$ be the
stopping times of the good selected by $j$ at her $t_{j}$-th pick and the
stopping time of the good selected by $i$ at her $(t_{i}+1)$-th pick,
respectively. If $i$ has no $(t_{i}+1)$-th pick, we set
$s_{i}=m<\frac{t_{i}+1}{w_{i}}$. Within the considered prefix of $\pi$, agent
$j$ already made its $t_{j}$-th pick but $i$ didn’t make its $(t_{i}+1)$-th
pick. Now by definition of $\pi$, $s_{j}\leq s_{i}$. By Lemma 3,
$s_{j}>\frac{t_{j}-1}{w_{j}}$ and $s_{i}\leq\frac{t_{i}+1}{w_{i}}$. We finally
get $\frac{t_{j}-1}{w_{j}}<\frac{t_{i}+1}{w_{i}}$. This shows that the
hypothesis of Proposition 1 is fulfilled for $x=y=1$. ∎

Note that if we had chosen eating rather than stopping times for the picking
sequence, we could only deduce $\frac{t_{j}-1}{w_{j}}<\frac{t_{i}+2}{w_{i}}$
which is not sufficient to show $\mathsf{WEF}(1,1)$.

As $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is (ex-ante)
$\mathsf{WEF}$, it is also $\mathsf{WPROP}$. By ex-ante $\mathsf{WPROP}$ and
Corollary 1, the following holds.

######  Proposition 4.

Every deterministic allocation $Y$ in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is
$\mathsf{WPROP}1$.

###### Proof.

The fractional allocation
$X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is $\mathsf{WEF}$,
and hence $\mathsf{WPROP}$. Therefore, $v_{i}(X_{i})\geq w_{i}\cdot
v_{i}(\mathcal{G})$. By Corollary 1, for any $Y$ in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition,
$v_{i}(Y_{i})\geq v_{i}(X_{i})-v_{i}(g)$, for some $g\in\mathcal{G}\setminus
Y_{i}$. This implies $v_{i}(Y_{i}\cup\\{g\\})\geq w_{i}\cdot
v_{i}(\mathcal{G})$, and $\mathsf{WPROP}1$ follows. ∎

In conclusion, we proved that the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is a lottery
achieving ex-ante $\mathsf{WSD}$-$\mathsf{EF}$, and therefore ex-ante
$\mathsf{WEF}$, and ex-post $\mathsf{WEF}(1,1)+\mathsf{WPROP}1$. As a
consequence of Theorem 1, our lottery has polynomial support and the
computation requires strongly polynomial time.

While our guarantee is weaker than the ex-post $\mathsf{EF}1$ for equal
entitlements, we show that our lottery is, in a sense, best possible in terms
of ex-post guarantees. Indeed, we prove that no stronger ex-post envy notion
is compatible with ex-ante $\mathsf{WEF}$.

######  Proposition 5.

For every pair $x,y\in[0,1]$ such that $x+y<2$, ex-ante $\mathsf{WEF}$ is
incompatible with ex-post $\mathsf{WEF}(x,y)$.

###### Proof.

Consider a fair division instance $\mathcal{I}=(\mathcal{N},\mathcal{G},v)$,
with $\mathcal{N}=\\{1,2\\}$ and $\mathcal{G}=\\{g_{1},g_{2}\\}$. Moreover,
$v_{i}(g_{1})=v_{i}(g_{2})=1$, for $i=1,2$. Let us set
$w_{1}\in\left(\frac{y}{2+y-x},\frac{1}{2}\right)$ and $w_{2}=1-w_{1}$.
Observe that $\frac{y}{2+y-x}<\frac{1}{2}$, since $x+y<2$. In any ex-ante
$\mathsf{WEF}$ allocation agent $1$ receives in expectation less than one
good. This means, the allocation $Y=(Y_{1},Y_{2})=(\emptyset,\mathcal{G})$ is
in the support of any ex-ante $\mathsf{WEF}$ lottery. Therefore, since
$w_{1}+w_{2}=1$, for each $g\in Y_{2}$,

$\displaystyle w_{1}\cdot\left(v_{1}(Y_{2})-x\cdot
v_{1}(g)\right)=w_{1}\cdot(2-x)>\frac{y}{2+y-x}\cdot(2-x)>w_{2}\cdot
y=w_{2}\cdot\left(v_{1}(Y_{1})+y\cdot v_{1}(g)\right)\ .$

This proves $Y$ is not $\mathsf{WEF}(x,y)$. ∎

#### Remark: Equal Entitlements Case.

Let us remark that for equal entitlements our approach also provides ex-ante
$\mathsf{EF}$ and ex-post $\mathsf{EF}1$. The ex-ante property follows
directly since $w_{i}=1/n$. For ex-post $\mathsf{EF}1$, similarly to [2], it
is possible to show that any allocation $Y$ in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of the $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is the result
of an RB picking sequence. In particular, this holds for the picking sequence
defined in the proof of Theorem 3.

###  3.2 Ex-ante $\mathsf{WGF}$ and Ex-post $\mathsf{WPROP}1$ \+
$\mathsf{WEF}_{1}^{1}$

In this subsection, we generalize a result of Freeman et al. [16] to
entitlements. We follow the general argument and incorporate some technical
extensions to allow for different agent weights.

For our purposes, we recall the weighted version of the well known Nash
Welfare.

######  Definition 5 (Weighted Nash Welfare).

Given a fair division instance $\mathcal{I}$, with entitlements
$w_{1},\dots,w_{n}$, and an allocation $\mathcal{A}=(A_{1},\dots,A_{n})$, the
weighted Nash welfare of $\mathcal{A}$ is given by
$\prod_{i=1}^{n}\left(v_{i}(A_{i})\right)^{w_{i}}\ .$

######  Theorem 4.

For entitlements and additive valuations, we can compute in strongly
polynomial time a lottery that is ex-ante $\mathsf{WGF}$ and ex-post
$\mathsf{WPROP}1$ \+ $\mathsf{WEF}_{1}^{1}$.

###### Proof.

We follow the proof steps of [16], where the same result was shown in the
unweighted setting. In a first step, we show that fractional maximum weighted
Nash welfare allocations (MWN allocations) form competitive equilibria (CE)
(Lemma 6), and in a second step, we show that CE allocations are
$\mathsf{WGF}$ (Lemma 7). Finally, we show that the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of any fractional MWN allocation yields the desired ex-post properties (Lemma
8).

The next lemmas hold even in the more general cake cutting model introduced by
Steinhaus [21]. In this model, instead of a finite number of goods, a single
continuous good $C$ (a “cake”) needs to be split among the $n$ agents. An
allocation is a partition of $C$ into $n$ subsets, and the valuation of an
agent $i\in\mathcal{N}$ is given by a measure $v_{i}$ on $C$.

First, we use a slight generalization of [20, Lemma 4.8] to derive a useful
inequality for MWN allocations.

######  Lemma 5.

Let $f_{i}:\mathbb{R}^{+}\mapsto\mathbb{R}^{+}$, $i\in\mathcal{N}$, be
differentiable functions. If an allocation $X$ of cake maximizes the welfare
function $S(X)=\sum_{i\in\mathcal{N}}f_{i}(v_{i}(X_{i}))$, then for any two
agents $i,j\in\mathcal{N}$ and any slice $Z_{j}\subseteq X_{j}$,

$f_{j}^{\prime}(v_{j}(X_{j}))\cdot v_{j}(Z_{j})\geq
f_{i}^{\prime}(v_{i}(X_{i}))\cdot v_{i}(Z_{j}).$

###### Proof.

Like in [20], we use a result of [22], which states that for any part $Z$ of
the cake and $\alpha\in[0,1]$, there is $Z_{\alpha}\subseteq Z_{j}$ such that
$v_{i}(Z_{\alpha})=\alpha\cdot v_{i}(Z)$ and $v_{j}(Z_{\alpha})=\alpha\cdot
v_{j}(Z)$. Let $X^{\prime}$ be the allocation obtained by giving $Z_{\alpha}$
from agent $j$ to $i$. The welfare difference $D=S(X^{\prime})-S(X)$ is now a
function of $\alpha$, i.e.,

$\displaystyle D(\alpha)=\ $ $\displaystyle
f_{i}\big{(}v_{i}(X_{i}^{\prime})\big{)}-f_{i}\big{(}v_{i}(X_{i})\big{)}+f_{j}\big{(}v_{j}(X_{j}^{\prime})\big{)}-f_{j}\big{(}v_{j}(X_{j})\big{)}$
$\displaystyle=\ $ $\displaystyle f_{i}\big{(}v_{i}(X_{i})+\alpha\cdot
v_{i}(Z_{j})\big{)}-f_{i}\big{(}v_{i}(X_{i})\big{)}+f_{j}\big{(}v_{j}(X_{j})-\alpha\cdot
v_{j}(Z_{j})\big{)}-f_{j}\big{(}v_{j}(X_{j})\big{)}.$

The derivative of $D$ is

$\displaystyle D^{\prime}(\alpha)=\ $ $\displaystyle v_{i}(Z_{j})\cdot
f_{i}^{\prime}\big{(}v_{i}(X_{i})+\alpha\cdot
v_{i}(Z_{j})\big{)}-v_{j}(Z_{j})\cdot
f_{j}^{\prime}\big{(}v_{j}(X_{j})-\alpha\cdot v_{j}(Z_{j})\big{)}.$

Since $X$ maximizes the welfare $S(X)$, we must have $D^{\prime}(0)\leq 0$,
and hence $v_{i}(Z_{j})\cdot f_{i}^{\prime}(v_{i}(X_{i}))\leq
v_{j}(Z_{j})\cdot f_{j}^{\prime}(v_{j}(X_{j})).$ ∎

If we set $f_{i}=w_{i}\ln v_{i}(X_{i})$ in Lemma 5, we obtain the following
useful inequality.

######  Corollary 2.

If $X$ is an MWN allocation, then for any two agents $i,j\in\mathcal{N}$ and
$Z_{j}\subseteq X_{j}$,

$w_{j}\cdot\frac{v_{j}(Z_{j})}{v_{j}(X_{j})}\geq
w_{i}\cdot\frac{v_{i}(Z_{j})}{v_{i}(X_{i})}\enspace.$

For the next proofs we need the notion of competitive equilibrium.

######  Definition 6.

A pair $(X,P)$ of allocation and prices is a competitive equilibrium (CE), if

  1. 1)

$P(Z)>0$ iff $Z$ is a positive slice111A part $Z$ of the cake is called
positive slice if $v_{i}(Z)>0$ for at least one agent $i\in\mathcal{N}$.,

  2. 2)

for all agents $i\in\mathcal{N}$, $Z_{i}\subseteq X_{i}$, and slice $Z$,
$\frac{v_{i}(Z_{i})}{P(Z_{i})}\geq\frac{v_{i}(Z)}{P(Z)}$ (MBB),

  3. 3)

for all $i\in\mathcal{N}$, $P(X_{i})=w_{i}$.

This equilibrium notion stems from [20], where the authors define it only for
equally entitled agents and call it _strong competitive equilibrium from equal
incomes_ (sCEEI).

######  Lemma 6.

For every MWN allocation $X$ there exists a price measure $P$ such that
$(X,P)$ is a competitive equilibrium.

###### Proof.

Let $X$ be an MWN allocation. For an agent $i\in\mathcal{N}$, we define the
price of a slice $Z_{i}\subseteq X_{i}$ as

$P(Z_{i})=w_{i}\cdot\frac{v_{i}(Z_{i})}{v_{i}(X_{i})}.$

The price of an arbitrary slice $Z$ is then given by adding the agent-specific
parts, i.e.,

$P(Z)=\sum_{i\in\mathcal{N}}P(Z\cap X_{i}).$

We need to show that conditions 1) to 3) are fulfilled by $(X,P)$. Condition
3) follows simply from the definition of prices. Condition 1) can be derived
as follows: Suppose $P(Z)>0$ for some slice $Z$. Then, again by the definition
of prices, there must be at least one agent $i\in\mathcal{N}$ such that
$P(Z\cap X_{i})>0$. Hence $Z$ is a positive slice. For the other direction,
suppose $Z$ is a positive slice, i.e., $v_{i}(Z)>0$ for some agent
$i\in\mathcal{N}$. Then either $P(Z\cap X_{i})>0$ or $P(Z\cap X_{i})=0$. In
the first case we are done. In the second case there needs to be an agent
$j\in\mathcal{N}$ with $P(Z\cap X_{j})>0$ as otherwise $Z$ would be liked by
$i$ but given only to agents $j$ not liking it, a contradiction to $X$ being
an MWN allocation.

Now it remains to show condition 2). Consider any agent $i$, any
$Z_{i}\subseteq X_{i}$, and any slice $Z$. We partition $Z$ into agent
specific parts $Z_{j}=Z\cap X_{j}$ (note that $Z=\bigcup_{j}Z_{j}$). By
plugging in prices into Corollary 2 we obtain for each part $Z_{j}$,

$v_{i}(X_{i})P(Z_{j})\geq v_{i}(Z_{j})w_{i}.$

Summing over all agent-specific parts $Z_{j}$ and using additivity of prices
yields

$v_{i}(X_{i})P(Z)\geq v_{i}(Z)w_{i}.$

Finally, by definition of prices,
$v_{i}(X_{i})=w_{i}\frac{v_{i}(Z_{i})}{P(Z_{i})}$, and therefore
$\frac{v_{i}(Z_{i})}{P(Z_{i})}\geq\frac{v_{i}(Z)}{P(Z)}.$ ∎

######  Lemma 7.

For every competitive equilibrium $(X,P)$, the allocation $X$ is
$\mathsf{WGF}$.

###### Proof.

Let $(X,P)$ be a CE. Assume for sake of contradiction that for some
$S,T\subseteq\mathcal{N}$ there is a reallocation $X^{\prime}$ of $\cup_{j\in
T}X_{j}$ among agents in $S$, such that for all $i\in S$,

$\frac{v_{i}(X^{\prime}_{i})}{v_{i}(X_{i})}\geq\frac{w_{T}}{w_{S}},$ (2)

and at least one inequality is strict. Consider an agent $i\in S$. By choosing
$Z_{i}=X_{i}$ and $Z=X^{\prime}_{i}$ in the second condition of CE we obtain

$P(X^{\prime}_{i})\geq\frac{v_{i}(X^{\prime}_{i})}{v_{i}(X_{i})}P(X_{i})=\frac{v_{i}(X^{\prime}_{i})}{v_{i}(X_{i})}w_{i},$

where the last equation comes from the third condition of CE. Now summing over
$i\in S$ and using (2) yields

$\sum_{i\in S}P(X^{\prime}_{i})>\frac{w_{T}}{w_{S}}\sum_{i\in S}w_{i}=w_{T},$

which is a contradiction since

$\displaystyle\sum_{i\in S}P(X^{\prime}_{i})$ $\displaystyle=P(\cup_{i\in
S}X^{\prime}_{i})=P(\cup_{j\in T}X_{j})=\sum_{j\in T}P(X_{j})=\sum_{j\in
T}w_{j}=w_{T}.$

∎

It remains to show the ex-post guarantee. At this point, we drop the
consideration of the cake cutting setting and shift to the indivisible domain.

######  Lemma 8.

The
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of a fractional MWN allocation is $\mathsf{WPROP}1$ and
$\mathsf{WEF}_{1}^{1}$.

###### Proof.

We proceed like in [16]. Let $X$ be a fractional MWN allocation and let $Y$ be
any deterministic allocation in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X$.

We first show that $Y$ is $\mathsf{WPROP}1$. Consider an agent
$i\in\mathcal{N}$. Observe that $X$ as an MWN allocation is $\mathsf{WGF}$ and
hence $\mathsf{WPROP}$, i.e., it holds $v_{i}(X_{i})\geq w_{i}\cdot
v_{i}(\mathcal{G})$. Hence if $v_{i}(Y_{i})\geq v_{i}(X_{i})$, we are done.
Otherwise, it holds $v_{i}(Y_{i})<v_{i}(X_{i})$. From Corollary 1 we know that
in this case there exists $g^{*}\notin Y_{i}$ such that
$v_{i}(Y_{i})+v_{i}(g^{*})>v_{i}(X_{i})\geq w_{i}\cdot v_{i}(\mathcal{G})$.
Hence $Y$ is $\mathsf{WPROP}1$.

It remains to show that $Y$ is $\mathsf{WEF}_{1}^{1}$. Consider two agents
$i,j\in\mathcal{N}$. From Corollary 1 it follows that if
$v_{i}(Y_{i})<v_{i}(X_{i})$, then there exists $g_{i}\notin Y_{i}$ such that

$v_{i}(Y_{i})+v_{i}(g_{i})>v_{i}(X_{i}).$ (3)

Analogously, if $v_{j}(Y_{j})>v_{j}(X_{j})$, then there exists $g_{j}\in
Y_{j}$ such that

$v_{j}(Y_{j})-v_{j}(g_{j})<v_{j}(X_{j}).$ (4)

Next, we use Corollary 2 again, this time in the setting with discrete goods.
It implies for any two agents $i,j\in\mathcal{N}$ and any $g\in\mathcal{G}$
with $x_{jg}>0$,

$w_{j}\frac{v_{j}(g)}{v_{j}(X_{j})}\geq w_{i}\frac{v_{i}(g)}{v_{i}(X_{i})}.$

Summing over all $g\in Y_{j}\setminus\\{g_{j}\\}$ yields

$w_{j}\frac{v_{j}(Y_{j}\setminus\\{g_{j}\\})}{v_{j}(X_{j})}\geq
w_{i}\frac{v_{i}(Y_{j}\setminus\\{g_{j}\\})}{v_{i}(X_{i})}.$

Note that the left-hand side of this inequality is strictly less than $w_{j}$
due to (3). Hence, by inequality (4) it follows
$w_{j}\cdot(v_{i}(Y_{i})+v_{i}(g_{i}))>w_{j}\cdot v_{i}(X_{i})>w_{i}\cdot
v_{i}(Y_{j}\setminus\\{g_{j}\\})$. This shows $Y$ is $\mathsf{WEF}_{1}^{1}$. ∎

Theorem 4 now follows from Lemmas 6, 7, 8 and the fact that we can can compute
in strongly polynomial time an MWN allocation [19] as well as the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
(Theorem 1). ∎

#### Remark.

One might wonder whether the ex-post guarantee in Theorem 4 could be replaced
with $\mathsf{WEF}(x,y)$ for some parameters $x,y\in[0,1]$. There are
instances where this is impossible, even in the unweighted setting. Consider
the following example: There are three agents $1,2,3$, three light goods, and
one heavy good. Agents $1$ and $2$ have the same valuation function, they
value the heavy good at 6, and each light good at 1. Agent $3$ values the
light goods at 1 and the heavy good at 0.

Now consider a fractional group fair allocation $X$. Observe that all light
goods need to be allocated completely to agent $3$ in $X$. If one of the first
two agents (say, agent 1) gets a fraction $\epsilon>0$ of light goods, the
group fairness condition is violated for $S=\\{2,3\\}$ and $T=\\{1,3\\}$: If
one reallocates the fraction $\epsilon$ of light goods from agent $1$ to agent
$3$, then agent $3$ strictly improves and the utility of agent $2$ remains
unchanged.

Now consider any allocation $Y$ in the support of a lottery implementing $X$.
$Y$ needs to give all light goods to agent $3$, so at least one of the first
two agents gets no good at all. This agent is then envious to agent $3$, and
transferring one good from agent $3$ to agent $1$ cannot remove this envy.

##  4 Extensions to General Valuations

In this section, we explore to which extent our techniques apply to more
general valuations. A major challenging problem for non-additive valuations is
that the (expected) utility of an agent for a lottery is not uniquely
determined by its fractional matrix. Nonetheless, both ex-ante $\mathsf{WEF}$
and ex-ante $\mathsf{WSD}$-$\mathsf{EF}$ allocations exist for all valuations
$\\{v_{i}\\}_{i\in\mathcal{N}}$. In particular, for ex-ante $\mathsf{WEF}$ one
can simply assign $\mathcal{G}$ to agent $i$ with probability $w_{i}$. For ex-
ante $\mathsf{WSD}$-$\mathsf{EF}$ it is sufficient to invoke DSE only using
agents’ priorities over single goods. Observe that for general valuations it
is no longer true that ex-ante $\mathsf{WSD}$-$\mathsf{EF}$ implies ex-ante
$\mathsf{WEF}$, not even in the unweighted setting. We next show that ex-ante
$\mathsf{WEF}$ and either ex-post $\mathsf{WPROP}1$ or ex-post
$\mathsf{WEF}(1,1)$ might no longer be possible.

######  Theorem 5.

For general valuations, ex-ante $\mathsf{WEF}$ is not compatible with
$\mathsf{WPROP}1$ or $\mathsf{WEF}(1,1)$.

###### Proof.

Let us consider a fair division instance with two agents and four goods.
Suppose agent $1$ has an entitlement of $\frac{2}{3}$, and has value $1$ for
any bundle (except the empty bundle, for which she has value $0$). Agent $2$
has entitlement $\frac{1}{3}$ and value $k$ for any bundle of size $k$, for
$k=0,\dots,4$.

Let us denote by $p_{k}$ the probability that $1$ receives $k$ goods. Clearly,
if the allocation is ex-post $\mathsf{WPROP}$ or ex-post $\mathsf{WEF}(1,1)$,
then $p_{0}=0$ and $\sum_{k=1}^{4}p_{k}=1$. Since the allocation is complete,
$p_{k}$ is also the probability that agent $2$ receives $4-k$ goods. Agent $1$
is ex-ante $\mathsf{WEF}$ if and only if

$\displaystyle\frac{1}{3}\cdot(p_{1}+p_{2}+p_{3}+p_{4})$
$\displaystyle\geq\frac{2}{3}\cdot(p_{0}+p_{1}+p_{2}+p_{3})$

which implies $1-p_{0}\geq 2\cdot(1-p_{4})$ and, hence, $2p_{4}\geq 1+p_{0}$.
Thus, $p_{4}\geq\frac{1}{2}$. Therefore, the allocation where agent $1$
receives every good and $2$ no good occurs with positive probability. However,
such an allocation is neither $\mathsf{WPROP}1$ nor $\mathsf{WEF}(1,1)$ (not
even $\mathsf{WEF}_{1}^{1}$) for agent $2$. ∎

Notice that both agents in the proof value $1$ each good, and, hence, agent
$1$ is unit-demand and agent $2$ is additive. This means that as soon as one
agent is not additive in the weighted case our positive result no longer
holds. We further observe that the proof relies on the fact that agents are
asymmetric. Therefore, we next consider two questions: 1) what combination of
ex-ante and ex-post properties we can guarantee in the weighted setting
assuming slightly more general valuations (namely, XOS)?, and 2) which
valuations still guarantee ex-ante $\mathsf{EF}$ and $\mathsf{EF}1$ ex-post
for symmetric agents?.

We try to reply to question 1) and 2) in Section 4.1 and 4.2, respectively.

###  4.1 XOS Valuations

For an agent $i$ with XOS valuation, our algorithms only make use of the
additive function $f_{i}$ such that
$v_{i}(\mathcal{G})=\sum_{g\in\mathcal{G}}f_{i}(g)$. We either assume $f_{i}$
to be known or have access to an XOS-oracle (using which $f_{i}$ can be
obtained with a single query). Given a query with a set
$A\subseteq\mathcal{G}$, the XOS-oracle returns a function
$f\in\mathcal{F}_{i}$ that maximizes $f(A)$.

Let $X$ be the fractional allocation with $x_{ig}=w_{i}$, for each
$i\in\mathcal{N}$ and $g\in\mathcal{G}$.

######  Proposition 6.

$X$ is ex-ante $\mathsf{WPROP}$.

###### Proof.

For any allocation $Y$, $v_{i}(Y_{i})=\max_{f\in\mathcal{F}_{i}}f(Y_{i})\geq
f_{i}(Y_{i})$, since $f_{i}\in\mathcal{F}_{i}$. Hence, $v_{i}(X_{i})\geq
f_{i}(X_{i})=\sum_{g\in\mathcal{G}}x_{ig}\cdot
f_{i}(g)=w_{i}\cdot\sum_{g\in\mathcal{G}}{f_{i}(g)}=w_{i}\cdot
v_{i}(\mathcal{G})$. ∎

In order to apply Theorem 1, we need to set up an appropriate additive
function. For the next result, we assume that agent $i$ has additive valuation
$f_{i}$, for each $i\in\mathcal{N}$.

######  Proposition 7.

The
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X$ is ex-post $\mathsf{WPROP}1$.

###### Proof.

Given any allocation $Y$ of the decomposition, by definition of XOS, Corollary
1 and Proposition 6, we see that $v_{i}(Y_{i}\cup\\{g\\})\geq
f_{i}(Y_{i}\cup\\{g\\})=f_{i}(Y_{i})+f_{i}(g)>f_{i}(X_{i})=w_{i}\cdot
v_{i}(\mathcal{G})$. ∎

###  4.2 Equal Entitlements

Here we discuss to which extent we can guarantee BoBW results for equally
entitled agents and general valuations. In particular, we explore valuation
functions for which DSE with the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
can be used to guarantee ex-ante $\mathsf{EF}$ and ex-post $\mathsf{EF}1$.
Recall that DSE was already introduced as the Eating procedure by Aziz [2] for
equally entitled agents.

Both DSE and the definition of the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$ bihierarchy
only depend on the ranking of each agent for singleton bundles of goods.
Therefore, we can determine a random allocation with DSE and compute its
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
for any class of valuation functions. Since the concept of
$\mathsf{SD}$-$\mathsf{EF}$ depends only on the ranking of single goods
provided by the agents, the output of DSE is always an ex-ante
$\mathsf{SD}$-$\mathsf{EF}$ allocation, regardless of the considered valuation
functions.

Unfortunately, for general valuations, it is no longer true that an
$\mathsf{SD}$-$\mathsf{EF}$ allocation $X$ is ex-ante $\mathsf{EF}$ not even
if $X$ is the output of DSE. Such an impossibility holds also for agents
having unit-demand valuations as the following example shows.

######  Example 4.

Let $\mathcal{I}$ be a fair division instance with three agents and three
goods. Assume agents to have identical unit-demand valuations; goods have all
value $1$. Having all agents the same priorities over goods, the output of DSE
is given by the following:

$X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}=\begin{pmatrix}\vskip
3.0pt plus 1.0pt minus 1.0pt\frac{1}{3}&\frac{1}{3}&\frac{1}{3}\\\ \vskip
3.0pt plus 1.0pt minus 1.0pt\frac{1}{3}&\frac{1}{3}&\frac{1}{3}\\\ \vskip
3.0pt plus 1.0pt minus 1.0pt\frac{1}{3}&\frac{1}{3}&\frac{1}{3}\end{pmatrix}\
.$

Being $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ the output of
DSE it is $\mathsf{SD}$-$\mathsf{EF}$; we next provide a decomposition of
$X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ showing that
$X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is not necessarily
ex-ante $\mathsf{EF}$. Let us consider the following decomposition:

$X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}=\frac{1}{3}\cdot\underbrace{\begin{pmatrix}1&1&0\\\
0&0&1\\\ 0&0&0\end{pmatrix}}_{Y^{1}}\ +\
\frac{1}{3}\cdot\underbrace{\begin{pmatrix}0&0&1\\\ 1&0&0\\\
0&1&0\end{pmatrix}}_{Y^{2}}\ +\
\frac{1}{3}\cdot\underbrace{\begin{pmatrix}0&0&0\\\ 0&1&0\\\
1&0&1\end{pmatrix}}_{Y^{3}}\ .$

Notice that such a decomposition is not an
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ (in any
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$, every agent
receives deterministically exactly one good). We claim that agent $1$
(corresponding to the first row) is not ex-ante $\mathsf{EF}$. In fact, the
expected utility she has for her random bundle is given by

$\frac{1}{3}\cdot\left(v_{1}(Y_{1}^{1})+v_{1}(Y_{1}^{2})+v_{1}(Y_{1}^{3})\right)=\frac{1}{3}\cdot(1+1+0)=\frac{2}{3}\
;$

while the expected value of agent $1$ for the random bundle of agent $2$
(second row) is

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

$\small\blacksquare$

Although for multi-demand valuations $\mathsf{SD}$-$\mathsf{EF}$ does not
imply ex-ante $\mathsf{EF}$, we next prove that the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is indeed ex-ante
$\mathsf{EF}$. Moreover, such a decomposition also guarantees ex-post
$\mathsf{EF}1$.

######  Theorem 6.

For equal entitlements and multi-demand valuations, the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is ex-ante
$\mathsf{EF}$ and ex-post $\mathsf{EF}1$.

###### Proof.

As already observed, any allocation in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is result of an RB
picking sequence (in case of equal entitlements our approach coincides with
the one of [2]). Hence, ex-post $\mathsf{EF}1$ follows by noticing that any RB
picking sequence is $\mathsf{EF}1$ for multi-demand valuations.

We now prove ex-ante $\mathsf{EF}$ of the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$. For convenience,
we denote $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ by $X$ and
assume $i$ to be $k$-unit-demand. Consider any agent $i\in\mathcal{N}$. Given
any $j\in\mathcal{N}\setminus{\\{i\\}}$, we need to show that
${v_{i}(X_{i})}\geq{v_{i}(X_{j})}$. In what follows, we again sort goods
$g_{1},\dots,g_{m}$ in the ordering induced by agent $i$ over $\mathcal{G}$.

Let us first show that
${v_{i}(X_{i})}=\sum_{g\in\mathcal{G}}v_{i}(g)\cdot\overline{x}_{ig}$, where

$\displaystyle\overline{x}_{ig_{\ell}}=\begin{cases}{x}_{ig_{\ell}}&\text{ if
}\sum_{h=1}^{\ell}x_{ig_{h}}\leq k\\\ k-\sum_{h=1}^{\ell-1}x_{ig_{h}}&\text{
if }\sum_{h=1}^{\ell}x_{ig_{h}}>k\\\ &\text{ and
}\sum_{h=1}^{\ell-1}x_{ig_{h}}<k\\\ 0&\text{ otherwise.}\end{cases}$

In other words, only the fraction of goods agent $i$ ate during the first $k$
units of time do count. Let us denote by $g_{h^{*}}$ the less valuable good
for which $\overline{x}_{ig_{h^{*}}}>0$. Notice that at time $t=k$ of DSE
agent $i$ is eating or finishes eating good $g_{h^{*}}$.

Recall that any agent needs $1/w_{i}=n$ units of time to eat $1$ unit of
goods. The feasibility conditions of Theorem 1 ensure that in any allocation
$Y$ in the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition,
the $h$-most preferred good of agent $i$ in her bundle $Y_{i}$ is one good she
ate in the time interval $(n(h-1),nh]$. Further, only one good eaten in this
interval will be the $h$-most preferred in the bundle $Y_{i}$. Since the
valuation of $i$ is $k$-unit-demand, only the goods she ate by the time $kn$
will contribute to her utility. This implies
${v_{i}(X_{i})}=\sum_{g\in\mathcal{G}}v_{i}(g)\cdot\overline{x}_{ig}$.

We now provide an upper bound on ${v_{i}(X_{j})}$. Let us denote by $p_{h}$
the probability that $g_{h}$ is in the bundle $X_{j}$ and is one of the $k$
most preferred goods of agent $i$ among the ones in $X_{j}$. The probability
$p_{h}$ is upper-bounded by the probability of having $g_{h}$ in the bundle of
$j$, and therefore $p_{h}\leq x_{jg_{h}}$. Moreover,
$\sum_{h=1}^{m}p_{h}=\sum_{h=1}^{m}\sum_{\ell=1}^{k}p_{h}^{\ell}=\sum_{\ell=1}^{k}\sum_{h=1}^{m}p_{h}^{\ell}\leq
k$, where $p_{h}^{\ell}$ is the probability that $g_{h}$ is the $\ell$-th most
preferred good of $i$ in $j$’s bundle. Notice also that
$\sum_{h=1}^{h^{*}-1}x_{jg_{h}}\leq k$ since, because of the DSE,
$\sum_{h=1}^{h^{*}-1}x_{jg_{h}}\leq\sum_{h=1}^{h^{*}-1}x_{ig_{h}}$, and
$\sum_{h=1}^{h^{*}-1}x_{ig_{h}}\leq k$ by definition of $h^{*}$. Therefore,
the expected utility of $i$ for $j$’s bundle is give by

$\displaystyle{v_{i}(X_{j})}=\sum_{h=1}^{m}p_{h}\cdot
v_{i}(g_{h})\leq\sum_{h=1}^{h^{*}-1}x_{jg_{h}}\cdot
v_{i}(g_{h})+\left(k-\sum_{h=1}^{h^{*}-1}x_{jg_{h}}\right)\cdot
v_{i}(g_{h^{*}})\ ,$

where the inequality holds because of the aforementioned properties of $p_{h}$
and $x_{jg_{h}}$, and the fact that $g_{1},\dots,g_{m}$ are sorted in a
decreasing manner with respect to $i$’s valuations. Moreover, by stochastic
dominance,

$\displaystyle\sum_{h=1}^{h^{*}-1}x_{jg_{h}}\cdot
v_{i}(g_{h})+\left(k-\sum_{h=1}^{h^{*}-1}x_{jg_{h}}\right)\cdot
v_{i}(g_{h^{*}})$ $\displaystyle\leq\sum_{h=1}^{h^{*}-1}x_{ig_{h}}\cdot
v_{i}(g_{h})+\left(k-\sum_{h=1}^{h^{*}-1}x_{ig_{h}}\right)\cdot
v_{i}(g_{h^{*}})$
$\displaystyle=\sum_{g\in\mathcal{G}}v_{i}(g)\cdot\overline{x}_{ig}\leq{v_{i}(X_{i})}\
.$

In conclusion, $v_{i}(X_{j})\leq v_{i}(X_{i})$ and the theorem follows. ∎

Notice that the proof of Theorem 6 takes into account only an agent $i$ having
multi-demand valuations for a given $k$, and not the valuations of the others.
For this reason the theorem holds for multi-demand agents having different
demands $k$. Moreover, when $k\geq m$ the agent is additive. These simple
observations lead to the following.

######  Corollary 3.

For equal entitlements and any combination of additive and multi-demand
valuations, the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is ex-ante
$\mathsf{EF}$ and ex-post $\mathsf{EF}1$.

Turning to more general cancelable valuations, we can show that RB picking
sequences (see Appendix C.1) still provide an $\mathsf{EF}1$ allocation, and
therefore the ex-post guarantee is maintained. Unfortunately, we were not able
to prove that the lottery is ex-ante $\mathsf{EF}$ (only ex-ante
$\mathsf{SD}$-$\mathsf{EF}$), and this remains an interesting open question.

##  5 Conclusions and Future Work

In this paper, we obtain best of both worlds results for fair division with
entitlements. Our results for additive valuations paint a rather complete
picture. We present a lottery that can be computed in strongly polynomial time
and guarantees ex-ante $\mathsf{WEF}$ and ex-post $\mathsf{WPROP}1$ \+
$\mathsf{WEF}(1,1)$. This is tight in the sense that any stronger notion of
$\mathsf{WEF}(x,y)$ is incompatible with ex-ante $\mathsf{WEF}$. We also
present a lottery that is ex-ante $\mathsf{WGF}$ and ex-post $\mathsf{WPROP}1$
\+ $\mathsf{WEF}_{1}^{1}$. Again, ex-ante $\mathsf{WGF}$ is incompatible with
stronger ex-post notions.

We also explore how some of our results can be extended to more general
valuation functions. These insights represent an interesting first step, but
many important open problems remain. As a prominent one, to the best of our
knowledge, it is open for which classes of valuations functions ex-ante
$\mathsf{EF}$ is always compatible with ex-post $\mathsf{EF}1$ in the
unweighted setting. In addition, providing tight guarantees with entitlements
and combinations of other fairness concepts (such as, e.g., variants of the
Max-Min Share ($\mathsf{MMS}$)) is an interesting direction for future work.

## References

  * [1] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A Voudouris.  Fair division of indivisible goods: A survey.  arXiv preprint arXiv:2202.07551, to appear IJCAI’22, 2022.
  * [2] Haris Aziz.  Simultaneously achieving ex-ante and ex-post fairness.  In Proc. 16th Conf. Web and Internet Econ. (WINE), pages 341–355. Springer, 2020.
  * [3] Haris Aziz, Serge Gaspers, Simon Mackenzie, and Toby Walsh.  Fair assignment of indivisible objects under ordinal preferences.  In Proc. Conf. Auton. Agents and Multi-Agent Syst. (AAMAS), pages 1305–1312, 2014.
  * [4] Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy.  A polynomial-time algorithm for computing a pareto optimal and almost proportional allocation.  Oper. Res. Lett., 48(5):573–578, 2020.
  * [5] Moshe Babaioff, Tomer Ezra, and Uriel Feige.  Best-of-both-worlds fair-share allocations.  arXiv preprint arXiv:2102.04909, 2021.
  * [6] Moshe Babaioff, Tomer Ezra, and Uriel Feige.  Fair-share allocations for agents with arbitrary entitlements.  In Proc. 22nd Conf. Econ. Comput. (EC), pages 127–127, 2021\.
  * [7] Anna Bogomolnaia and Herve Moulin.  A new solution to the random assignment problem.  J. Econ. Theory, 100:295–328, 2001.
  * [8] Eric Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  J. Policial Econ., 119(6):1061–1103, 2011.
  * [9] Eric Budish, Yeon-Koo Che, Fuhito Kojima, and Paul Milgrom.  Designing random allocation mechanisms: Theory and applications.  Amer. Econ. Rev., 103(2):585–623, 2013.
  * [10] Ioannis Caragiannis, Panagiotis Kanellopoulos, and Maria Kyropoulou.  On interim envy-free allocation lotteries.  In Proc. 22nd Conf. Econ. Comput. (EC), pages 264–284, 2021\.
  * [11] Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, and Yair Zick.  Weighted envy-freeness in indivisible item allocation.  ACM Trans. Econ. Comput., 9(3):1–39, 2021.
  * [12] Mithun Chakraborty, Ulrike Schmidt-Kraepelin, and Warut Suksompong.  Picking sequences and monotonicity in weighted fair division.  Artif. Intell., 301:103578, 2021.
  * [13] Mithun Chakraborty, Erel Segal-Halevi, and Warut Suksompong.  Weighted fairness notions for indivisible items revisited.  In Proc. 36th Conf. Artif. Intell. (AAAI), pages 4949–4956, 2022.
  * [14] Vincent Conitzer, Rupert Freeman, and Nisarg Shah.  Fair public decision making.  In Proc. 18th Conf. Econ. Comput. (EC), pages 629–646, 2017\.
  * [15] Vincent Conitzer, Rupert Freeman, Nisarg Shah, and Jennifer Wortman Vaughan.  Group fairness for the allocation of indivisible goods.  In Proc. 33rd Conf. Artif. Intell. (AAAI), pages 1853–1860, 2019.
  * [16] Rupert Freeman, Nisarg Shah, and Rohit Vaish.  Best of both worlds: Ex-ante and ex-post fairness in resource allocation.  In Proc. 21st Conf. Econ. Comput. (EC), pages 21–22, 2020.
  * [17] Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni.  Approximating Nash social welfare under submodular valuations through (un)matchings.  In Proc. 31st Symp. Discret. Algorithms (SODA), pages 2673–2687, 2020.
  * [18] Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi.  On approximately fair allocations of indivisible goods.  In Proc. 5th Conf. Electr. Commerce (EC), pages 125–131, 2004\.
  * [19] James Orlin.  Improved algorithms for computing Fisher’s market clearing prices.  In Proc. 42nd Symp. Theory Comput. (STOC), pages 291–300, 2010\.
  * [20] Erel Segal-Halevi and Balazs Sziklai.  Monotonicity and competitive equilibrium in cake-cutting.  Economic Theory, 68(2):363–401, 2019.
  * [21] Hugo Steinhaus.  Sets on which several measures agree.  Econometrica, 16:101–104, 1948.
  * [22] Walter Stromquist and Douglas Woodall.  Sets on which several measures agree.  J. Math. Anal. Appl., 108:241–248, 1985.
  * [23] Warut Suksompong and Nicholas Teh.  On maximum weighted nash welfare for binary valuations.  Math. Soc. Sci., 117:101–108, 2022.

##  Appendix A Preliminaries

######  Customtheorem 1 (Proposition 1).

Let $t_{i},t_{j}$ be the number of picks of agents $i$, $j$, respectively, in
a prefix of $\pi$. A picking sequence $\pi$ is $\mathsf{WEF}(x,y)$ if and only
if for every prefix of $\pi$ and every pair of agents $i,j$, we have
$\frac{t_{i}+y}{w_{i}}\geq\frac{t_{j}-x}{w_{j}}.$

###### Proof.

For completeness, we report every step of the proof of Theorem 3.2 in Appendix
A.2 of the full version of [13]. We point out that our adapted proof requires
only a minor modification in inductive proof of Eq. (7).

($\Rightarrow$) Assume that $\pi$ fulfills $\mathsf{WEF}(x,y)$. Since the
$\mathsf{WEF}(x,y)$ condition must be satisfied for every instance, we can
choose a special one that forces the utility of every agent to equal her
number of picks up to a certain point. Consider a prefix of $\pi$. Every agent
values each item which has been picked so far with 1, and the remaining ones
with 0. If $t_{j}=0$, the claim trivially holds. Otherwise,
$\mathsf{WEF}(x,y)$ gives us existence of $g\in A_{j}$ such that

$\displaystyle\frac{v_{i}(A_{i})+y\cdot
v_{i}(g)}{w_{i}}\geq\frac{v_{i}(A_{j})-x\cdot v_{i}(g)}{w_{j}}.$

Plugging in $v_{i}(g)=1$ and $v_{i}(A_{i})=t_{i}$ as well as
$v_{i}(A_{j})=t_{j}$ yields the claim.

($\Leftarrow$) Consider any two agents $i,j$. We show that the
$\mathsf{WEF}(x,y)$ condition for agent $i$ towards agent $j$ is fulfilled
after every pick of $j$. Consider the $t_{j}$-th pick of agent $j$. We divide
the sequence of picks up to this point into _phases_ , where each phase
$\ell\in\\{1,\dots,t_{j}\\}$ consists of the picks after agent $j$’s
$(\ell-1)$-th pick up to (and including) the agent’s $\ell$-th pick. We use
the following notation:

  * •

$\tau_{\ell}:=$ the number of times agent $i$ picks in phase $\ell$ (that is,
between agent $j$’s $(\ell-1)$-th and $\ell$-th picks),

  * •

$\alpha_{\ell}:=$ the total utility gained by agent $i$ in phase $\ell$,

  * •

$\beta_{\ell}:=$ agent $i$’s utility for the item that agent $j$ picks at the
end of phase $\ell$.

Let $\rho:=w_{i}/w_{j}$. For any integer $s\in[t_{j}]$, applying the condition
in the theorem statement to the picking sequence up to and including phase
$s$, we have

$y+\sum_{\ell=1}^{s}\tau_{\ell}~{}\geq~{}\rho(s-x).$ (5)

Every time agent $i$ picks, she picks an item with the highest value for her.
In particular, in each phase $\ell$, she picks $\tau_{\ell}$ items each of
which gives at least as high value to her as each item picked by agent $j$
after (and including) phase $\ell$. Hence for all phases
$\ell\in\\{1,\dots,t_{j}\\}$,

$\alpha_{\ell}\geq\tau_{\ell}\cdot\max_{\ell\leq r\leq t_{j}}\beta_{r}.$ (6)

To show the claim, we prove the following inequality for all $s\in[t_{j}]$:

$\displaystyle y\cdot\max_{1\leq r\leq t_{j}}\beta_{r}$
$\displaystyle+\sum_{\ell=1}^{s}\alpha_{\ell}\geq\rho\left(\sum_{\ell=1}^{s}\beta_{\ell}-x\beta_{1}\right)$
$\displaystyle+\left(y+\sum_{\ell=1}^{s}\tau_{\ell}-\rho(s-x)\right)\max_{s\leq
r\leq t_{j}}\beta_{r}.$ (7)

We prove (7) by induction on $s$. The base case $s=1$ can be obtained by
setting $\ell=1$ in (6) and adding the term $y\cdot\max_{1\leq r\leq
t_{j}}\beta_{r}$ on both sides:

$\displaystyle y\cdot\max_{1\leq r\leq t_{j}}$
$\displaystyle\beta_{r}+\alpha_{1}\geq(y+\tau_{1})\cdot\max_{1\leq r\leq
t_{j}}\beta_{r}$
$\displaystyle\geq\rho(1-x)\beta_{1}+(y+\tau_{1}-\rho(1-x))\cdot\max_{1\leq
r\leq t_{j}}\beta_{r}$

For the inductive step, assume that (7) holds for some $s-1$. Using the
inductive hypothesis (i.h.), we have

$\displaystyle y\cdot\max_{1\leq r\leq
t_{j}}\beta_{r}+\sum_{\ell=1}^{s}\alpha_{\ell}$
$\displaystyle=y\cdot\max_{1\leq r\leq
t_{j}}\beta_{r}+\sum_{\ell=1}^{s-1}\alpha_{\ell}+\alpha_{s}$
$\displaystyle\overset{\text{(i.h.)}}{\geq}\rho\left(\sum_{\ell=1}^{s-1}\beta_{\ell}-x\beta_{1}\right)+\left(y+\sum_{\ell=1}^{s-1}\tau_{\ell}-\rho(s-1-x)\right)\cdot\max_{s-1\leq
r\leq t_{j}}\beta_{r}+\alpha_{s}$ $\displaystyle\overset{\eqref{eq:WWEF-
picks}}{\geq}\rho\left(\sum_{\ell=1}^{s-1}\beta_{\ell}-x\beta_{1}\right)+\left(y+\sum_{\ell=1}^{s-1}\tau_{\ell}-\rho(s-1-x)\right)\cdot\max_{s\leq
r\leq t_{j}}\beta_{r}+\alpha_{s}$ $\displaystyle\overset{\eqref{eq:WWEF-
utils}}{\geq}\rho\left(\sum_{\ell=1}^{s-1}\beta_{\ell}-x\beta_{1}\right)+\left(y+\sum_{\ell=1}^{s-1}\tau_{\ell}-\rho(s-1-x)\right)\cdot\max_{s\leq
r\leq t_{j}}\beta_{r}+\tau_{s}\max_{s\leq r\leq t_{j}}\beta_{r}$
$\displaystyle=\rho\left(\sum_{\ell=1}^{s-1}\beta_{\ell}-x\beta_{1}\right)+\left(y+\sum_{\ell=1}^{s}\tau_{\ell}-\rho(s-1-x)\right)\cdot\max_{s\leq
r\leq t_{j}}\beta_{r}$
$\displaystyle=\rho\left(\sum_{\ell=1}^{s-1}\beta_{\ell}-x\beta_{1}\right)+\rho\max_{s\leq
r\leq
t_{j}}\beta_{r}+\left(y+\sum_{\ell=1}^{s}\tau_{\ell}-\rho(s-x)\right)\cdot\max_{s\leq
r\leq t_{j}}\beta_{r}$
$\displaystyle\geq\rho\left(\sum_{\ell=1}^{s-1}\beta_{\ell}-x\beta_{1}\right)+\rho\beta_{s}+\left(y+\sum_{\ell=1}^{s}\tau_{\ell}-\rho(s-x)\right)\cdot\max_{s\leq
r\leq t_{j}}\beta_{r}$
$\displaystyle=\rho\left(\sum_{\ell=1}^{s}\beta_{\ell}-x\beta_{1}\right)+\left(y+\sum_{\ell=1}^{s}\tau_{\ell}-\rho(s-x)\right)\cdot\max_{s\leq
r\leq t_{j}}\beta_{r}.$

This completes the induction and shows (7).

Using (7) with $s=t_{j}$ together with (5) yields

$\displaystyle y\cdot\max_{1\leq r\leq
t_{j}}\beta_{r}+\sum_{\ell=1}^{t_{j}}\alpha_{\ell}~{}\geq~{}\rho\left(\sum_{\ell=1}^{t_{j}}\beta_{\ell}-x\beta_{1}\right).$

Now letting $A_{i}$ and $A_{j}$ be the bundles of agents $i$ and $j$ after
agent $j$’s $t_{j}$-th pick, and $g$ be an item in $A_{j}$ for which agent $i$
has highest utility, we obtain from the last inequality that

$\displaystyle y\cdot v_{i}(g)+v_{i}(A_{i})$
$\displaystyle\geq\frac{w_{i}}{w_{j}}\cdot(v_{i}(A_{j})-x\beta_{1})$
$\displaystyle\geq\frac{w_{i}}{w_{j}}\cdot(v_{i}(A_{j})-x\cdot v_{i}(g)).$

Therefore the $\mathsf{WEF}(x,y)$ condition for agent $i$ towards agent $j$ is
fulfilled, completing the proof.

∎

##  Appendix B Additive Valuations

###  B.1 Ex-ante $\mathsf{WEF}$ and Ex-post
$\mathsf{WEF}(1,1)$+$\mathsf{WPROP}1$

######  Customtheorem 2 (Proposition 3).

Given a fractional allocation $X$, if $X$ is ex-ante
$\mathsf{WSD}$-$\mathsf{EF}$, then $X$ is ex-ante $\mathsf{WEF}$.

###### Proof.

Let $X$ be a fractional allocation satisfying $\mathsf{WSD}$-$\mathsf{EF}$.
Let $i$ and $j$ be two distinct agents.

First notice that, by $\mathsf{WSD}$-$\mathsf{EF}$,
$a=w_{j}\cdot\sum_{g\in\mathcal{G}}x_{ig}\geq
w_{i}\cdot\sum_{g\in\mathcal{G}}x_{jg}=b$.

Let us consider $g_{1},\dots,g_{m}$ sorted according to $i$’s valuations. We
define $f,h:[0,a]\rightarrow\mathbb{R}^{+}$ in the following way:

$\displaystyle f(x)=\begin{cases}v_{i}(g_{1})&\text{ if }x=0\\\
v_{i}(g_{k})&\text{ if }x\in\left(y_{k-1},y_{k}\right]\end{cases}$

where $y_{k}=w_{j}\cdot\sum_{\ell=1}^{k}x_{ig_{\ell}}$ , and

$\displaystyle h(x)=\begin{cases}v_{i}(g_{1})&\text{ if }x=0\\\ 0&\text{ if
}x\in(b,a]\\\ v_{i}(g_{k})&\text{ if
}x\in\left(z_{k-1},z_{k}\right],\end{cases}$

where, $z_{k}=w_{i}\cdot\sum_{\ell=1}^{k}x_{jg_{\ell}}$.

Notice that the difference between $y_{k}$ and $z_{k}$ is that the summations
concern fractions of $g_{1},\dots,g_{k}$ in $X_{i}$ and $X_{j}$, respectively.
Moreover, the summations are multiplied by $w_{j}$ and $w_{i}$, respectively.

We next show that $\mathsf{WSD}$-$\mathsf{EF}$ implies $f(x)\geq h(x)$, for
all $x\in[0,a]$.

Notice that for $x\in[b,a]$, $f(x)>0$ and $h(x)=0$. Assume towards a
contradiction that there exists $x\in[0,b]$ such that $f(x)<h(x)$. Then, there
exist $\ell_{1}$ and $\ell_{2}$ such that

$v_{i}(g_{\ell_{1}})=f(x)<h(x)=v_{i}(g_{\ell_{2}})\,.$

By definition of $f$ and $h$, we have

$x\in(y_{\ell_{1}-1},y_{\ell_{1}}]\cap(z_{\ell_{2}-1},z_{\ell_{2}}]\,.$

Hence, $y_{\ell_{1}-1}<z_{\ell_{2}}$.

Moreover, since $v_{i}(g_{\ell_{1}-1})\leq
v_{i}(g_{\ell_{1}})<v_{i}(g_{\ell_{2}})$ and goods sorted in a non-increasing
ordering with respect to $i$’s valuations,

$\\{g_{1},\dots,g_{\ell_{2}}\\}\subseteq\\{g\ :\ v_{i}(g)\geq
v_{i}(g_{\ell_{2}})\\}\subset\\{g_{1},\dots,g_{\ell_{1}}\\}\,.$

These imply

$y_{\ell_{1}-1}=w_{j}\cdot\sum_{\ell=1}^{\ell_{1}}x_{ig_{\ell}}\geq
w_{j}\cdot\sum_{g\in\\{g\ :\ v_{i}(g)\geq
v_{i}(g_{\ell_{2}})\\}}x_{ig_{\ell}}$

and

$z_{\ell_{2}}=w_{i}\cdot\sum_{\ell=1}^{\ell_{2}}x_{jg_{\ell}}\leq
w_{i}\cdot\sum_{g\in\\{g\ :\ v_{i}(g)\geq
v_{i}(g_{\ell_{2}})\\}}x_{jg_{\ell}}\ .$

These two inequalities together with $y_{\ell_{1}-1}<z_{\ell_{2}}$, show

$w_{j}\cdot\sum\limits_{g\in\\{g\ :\ v_{i}(g)\geq
v_{i}(g_{\ell_{2}})\\}}x_{ig_{\ell}}<w_{i}\cdot\sum\limits_{g\in\\{g\ :\
v_{i}(g)\geq v_{i}(g_{\ell_{2}})\\}}x_{jg_{\ell}}$

– a contradiction with $\mathsf{WSD}$-$\mathsf{EF}$.

To conclude, we notice that

$w_{j}\cdot\mathbb{E}\left[v_{i}(X_{i})\right]=\int_{0}^{a}f(x)dx$

and

$w_{i}\cdot\mathbb{E}\left[v_{i}(X_{j})\right]=\int_{0}^{a}h(x)dx\,.$

Since $f(x)\geq h(x)$, for all $x\in[0,a]$,
$w_{j}\cdot\mathbb{E}\left[v_{i}(X_{i})\right]\geq
w_{i}\cdot\mathbb{E}\left[v_{i}(X_{j})\right]$ follows. ∎

##  Appendix C General Valuations and Equal Entitlements

###  C.1 Cancelable Valuations

As mentioned above, for additive valuations and equal entitlements the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is ex-ante
$\mathsf{SD}$-$\mathsf{EF}$ as well as ex-post $\mathsf{EF}1$. The latter
results from the fact that every allocation in the support of the lottery
emerges from an RB picking sequence. We now describe what implications this
approach has on cancelable valuations functions. Given the cancelable
valuation function $v_{i}$, for each $i\in\mathcal{N}$, we create a
corresponding additive valuation function $\hat{v}_{i}$ with
$\hat{v}_{i}(g)=v_{i}(g)$. Then we apply the result for additive valuations
and equal entitlements. This implies the obtained lottery is ex-ante
$\mathsf{SD}$-$\mathsf{EF}$, as the priorities over goods are the same for
$v_{i}$ and $\hat{v}_{i}$.

Let us discuss ex-post properties. We show that any RB picking sequence for
$\hat{v}$ yields an allocation that is ex-post $\mathsf{EF}1$ for $v$. To this
aim, we need the following lemmas.

######  Lemma 9.

Let $v$ be a cancelable valuation function. Given any
$S,T\subseteq\mathcal{G}$ and any $R\subseteq\mathcal{G}\setminus(S\cup T)$,
if $v(S)\geq v(T)$, then

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

###### Proof.

Let $R_{i}=\\{g_{1},\ldots,g_{i}\\}$ and $R_{k}=R$. If $v(T\cup R_{i})>v(S\cup
R_{i})$, then $v(T\cup R_{i-1})>v(S\cup R_{i-1})$ by cancelability of $v$.
Applying this result for all $i$ from $k$ down to $1$, we get that if $v(T\cup
R)>v(S\cup R)$, then $v(T)>v(S)$ – a contradiction. ∎

######  Lemma 10.

Let $v$ be a cancelable valuation function. Given any
$S,T\subseteq\mathcal{G}$ and any $g,g^{\prime}\in\mathcal{G}\setminus(S\cup
T)$, if $v(S)\geq v(T)$ and $v(g)\geq v(g^{\prime})$, then

$v(S\cup\\{g\\})\geq v(T\cup\\{g^{\prime}\\}).$

###### Proof.

Applying Lemma 9 twice, $v(S\cup\\{g\\})\geq v(T\cup\\{g\\})\geq
v(T\cup\\{g^{\prime}\\})$ follows. ∎

Recall that an RB picking sequence takes as input an ordering of the agents
and agents’ priorities over goods. Consequently, an RB picking sequence
produces the very same outcome for $v$ and $\hat{v}$ (if ties are broken in
the same manner).

######  Proposition 8.

Given a fair division instance with cancelable valuations, any RB picking
sequence yields an allocation that is $\mathsf{EF}1$.

###### Proof.

Let $Y$ be an allocation obtained by an RB picking sequence.

Given any pair of agents $i,j$, the sizes of $Y_{i}$ and $Y_{j}$ differ by at
most $1$. We next show that agent $i$ is $\mathsf{EF}1$ towards agent $j$:
Without loss of generality, we can assume $|Y_{j}\rvert=|Y_{i}\rvert+1$. Let
us denote by $g^{*}$ the most preferred good of $i$ in $Y_{j}$. Because of the
RB property, there exists a matching $M=\\{(g,g^{\prime})|g\in
Y_{i},g^{\prime}\in Y_{j}\setminus\\{g^{*}\\}\\}$ such that $v_{i}(g)\geq
v_{i}(g^{\prime})$ for each $(g,g^{\prime})\in M$. Recursively applying Lemma
10 over the pairs in $M$ we obtain $v_{i}(Y_{i})\geq
v_{i}(Y_{j}\setminus\\{g^{*}\\})$. Therefore, $i$ is $\mathsf{EF}1$ towards
agent $j$; applying the same arguments on any pair of agents the thesis
follows. ∎

Overall, our result for cancelable valuations is as follows.

######  Theorem 7.

For equal entitlements and cancelable valuations, the
$\mathcal{H}^{\scalebox{0.6}{\mbox{$\displaystyle\mathsf{UG}$}}}$-decomposition
of $X^{\scalebox{0.6}{\mbox{$\displaystyle\textsc{DSE}$}}}$ is ex-ante
$\mathsf{SD}$-$\mathsf{EF}$ and ex-post $\mathsf{EF}1$.

It remains to explore whether ex-ante $\mathsf{SD}$-$\mathsf{EF}$ implies ex-
ante $\mathsf{EF}$ for cancelable valuations.