# Getting More by Knowing Less:
Bayesian Incentive Compatible Mechanisms for Fair Division

Vasilis Gkatzelis  Department of Computer Science, Drexel University.
<EMAIL_ADDRESS>Alexandros Psomas  Department of Computer Science,
Purdue University<EMAIL_ADDRESS>Xizhi Tan  Department of
Computer Science, Drexel University<EMAIL_ADDRESS>Paritosh Verma
Department of Computer Science, Purdue University.
<EMAIL_ADDRESS>
###### Abstract

We study fair resource allocation with strategic agents. It is well-known
that, across multiple fundamental problems in this domain, truthfulness and
fairness are incompatible. For example, when allocating indivisible goods, no
truthful and deterministic mechanism can guarantee envy-freeness up to one
item (EF1), even for two agents with additive valuations. Or, in cake-cutting,
no truthful and deterministic mechanism always outputs a proportional
allocation, even for two agents with piecewise constant valuations. Our work
stems from the observation that, in the context of fair division, truthfulness
is used as a synonym for Dominant Strategy Incentive Compatibility (DSIC),
requiring that an agent prefers reporting the truth, no matter what other
agents report.

In this paper, we instead focus on Bayesian Incentive Compatible (BIC)
mechanisms, requiring that agents are better off reporting the truth in
expectation over other agents’ reports. We prove that, when agents know a bit
less about each other, a lot more is possible: BIC mechanisms can guarantee
fairness notions that are unattainable by DSIC mechanisms in both the
fundamental problems of allocation of indivisible goods and cake-cutting. We
prove that this is the case even for an arbitrary number of agents, as long as
the agents’ priors about each others’ types satisfy a neutrality condition.
Notably, for the case of indivisible goods, we significantly strengthen the
state-of-the-art negative result for efficient DSIC mechanisms, while also
highlighting the limitations of BIC mechanisms, by showing that a very general
class of welfare objectives is incompatible with Bayesian Incentive
Compatibility. Combined these results give a near-complete picture of the
power and limitations of BIC and DSIC mechanisms for the problem of allocating
indivisible goods.

##  1 Introduction

A central goal within the fair division literature is to design procedures
that distribute indivisible or divisible goods among groups of agents. For a
resource allocation procedure to reach fair and efficient outcomes, however,
it needs to have access to the preferences of the participating agents.
Whenever this information is private and each agent can strategically
misreport it, the literature is riddled with negative results: eliciting the
true preferences of the agents while simultaneously guaranteeing fairness and
efficiency is usually impossible. One of the main underlying reasons is that
monetary payments are commonly infeasible or undesired in fair division, and
designing “truthful” mechanisms in the absence of such payments poses often
insurmountable obstacles.

Another factor that contributes to the plethora of impossibility results is
that “truthfulness” in this literature has been used as a synonym for
“Dominant Strategy Incentive Compatibility” (DSIC). This is a very demanding
notion of incentive compatibility which requires that every agent prefers
truth-telling to misreporting, _no matter what the other agents’ reports are_.
This ensures that no agent will have an incentive to lie, even if they know
_exactly_ what every other agent’s preferences are. However, in most real-
world applications it is unreasonable to assume that the agents know that much
about each other, so this notion may be unnecessarily stringent. In fact, if
we assume that an agent would strategically misreport their preferences only
if they have enough information to suggest that this would be beneficial then,
in some sense, the less an agent knows the less likely it is that they would
misreport. Rather than going to the other extreme and assume the agents have
no information about each other, in this paper we consider the well-
established truthfulness notion of “Bayesian Incentive Compatibility” (BIC).
This instead assumes that each agent’s preference is drawn from a publicly
known prior distribution and the requirement is that telling the truth is the
optimal strategy for each agent _in expectation over the other agents’
reports_. Simply put, our goal in this paper is to understand what can and
what cannot be achieved by BIC mechanisms in the context of fair division, and
the extent to which they can outperform DSIC mechanisms.

###  1.1 Our Contributions

We explore the power and limitations of incentive compatible mechanisms when
allocating either indivisible or divisible goods among $n$ strategic agents
with additive valuations, i.e., such that an agent’s value for a set of goods
is equal to the sum of her values for each good separately.

#### Allocating indivisible goods.

It is well-known that the only deterministic DSIC mechanism for allocating
indivisible goods among two agents in a Pareto efficient way is the patently
unfair “serial dictatorship” mechanism [KM02, Sch96], where one of the agents
is allocated _all_ the goods that they have a positive value for, and the
other agent receives the leftovers. Since Pareto efficiency may be a lot to
ask for, one could imagine that a more forgiving notion of efficiency based on
stochastic dominance (SD) [BM01] may allow us to overcome this obstacle. Our
main negative result shows that this is not the case: even for the more
permissive notion of $\mathrm{SD}^{+}$efficiency (defined in Section 3.1)
instead of Pareto efficiency, we prove that the only deterministic DSIC
mechanism remains the serial dictatorship, and this holds even if for every
agent $i$, their value for each good $j$ can take one of only _three_ possible
values, i.e. $v_{i,j}\in\\{0,x,y\\}$ (Theorem 1). In fact, we show that our
stronger negative result is tight in more than one ways: if we were to further
relax $\mathrm{SD}^{+}$efficiency to $\mathrm{SD}$ efficiency (also defined in
Section 3.1), or to further restrict the number of possible agent values to
two instead of three, this would permit more deterministic DSIC mechanisms
beyond serial dictatorship.

Surprisingly, it is also known that, even if we were to completely drop any
efficiency requirement in order to avoid the extreme unfairness of the serial
dictatorship, our ability to provide non-trivial fairness guarantees would
still be severely limited. For example, if we wanted the outcome to be _envy-
free up to one good_ (EF1), which is a well-studied relaxation of envy-
freeness [LMMS04, Bud11], this is known to be impossible to achieve using
_any_ deterministic DSIC mechanism, even for instances with just two agents
[ABCM17]. Our main positive result shows that we can simultaneously overcome
all of the aforementioned negative results if instead of DSIC we focus on BIC
mechanisms. In fact, we can achieve this using a variation of the very
practical Round-Robin procedure (where agents take turns choosing a single
good each time). We prove that our variation, $\mathrm{RR}^{\text{pass}}$, is
BIC for any distribution over agent preferences that is “neutral” [Mou80], and
it returns allocations that always combine fairness (in the form of EF1) with
efficiency (in the form of $\mathrm{SD}^{+}$efficiency) (Theorem 3). Apart
from providing a separation between BIC and DSIC mechanisms by bypassing both
of these negative results, this also exhibits a third way in which our result
from Theorem 1 is tight. Our definition of a “neutral” prior is satisfied by
the common assumption in the stochastic fair division literature, that
$v_{i,j}$s are drawn i.i.d. from an agent-specific distribution
$\mathcal{D}_{i}$ [BG21, MS20, MS21a, AMNS17], going beyond, it also allows
for certain priors where valuations are neither independently nor identically
distributed (see Section 3.2).

Encouraged by our positive result, which exhibits a practical BIC mechanism
that combines fairness and $\mathrm{SD}^{+}$efficiency, one may wonder whether
BIC mechanisms can even optimize well-motivated welfare functions. For
example, a lot of recent work in fair division has focused on maximizing the
Nash social welfare (the geometric mean of agents’ utilities). Apart from
guaranteeing Pareto efficiency, this outcome is also known to be EF1 for
agents with additive valuations [CKM+19], and it is used in Spliddit, a
popular platform for allocating indivisible goods [GP15, Sha17]. Our findings
along this direction are negative: we show that even for a very simple neutral
distribution (uniform over normalized valuations), a mechanism that maximizes
any welfare function from a large well-studied family that satisfies the
Pigou-Dalton principle (which, e.g., includes the Nash social welfare, the
egalitarian social welfare, the utilitarian social welfare, and the leximin
criterion) is not BIC (Theorem 5). Finally, we prove that if we aim for the
strong efficiency guarantee of fractional Pareto optimality (fPO), requiring
that the outcome is not Pareto dominated even by randomized allocations, then
BIC mechanisms cannot even satisfy _fullfillment_ , which is a fairness notion
that is much weaker than EF1 (Theorem 5). Informally, an allocation is
fulfilling if, whenever agent $i$ values at least $n$ goods strictly
positively, her utility for her bundle is strictly positive.

#### Allocating divisible goods.

Moving beyond indivisible goods, we then consider mechanisms for the fair
allocation of continuous, divisible, heterogeneous resources, using the
classic cake-cutting model. The cake, which captures a divisible resource, is
represented as the interval $[0,1]$ and it must be distributed among $n$
agents with different valuations on different parts of the interval.
Typically, agents’ valuation functions are described by probability density
functions. Recently, [Tao22] showed that, even for $n=2$ agents with piecewise
constant valuation functions, there is no deterministic and DSIC cake-cutting
mechanism that always outputs a proportional allocation, i.e., one where each
agent receives at least a $1/n$ fraction of their total value. Our main result
for this problem circumvents this impossibility for any number of agents by
relaxing to BIC mechanisms (Theorem 5). Specifically, we propose a
deterministic cake-cutting mechanism that is proportional and BIC for all
neutral priors. Our mechanism works over a sequence of $n$ rounds: in round
$i$, agent $i$ arrives and agents $1$ through $i-1$ are asked to cut the
pieces allocated to them so far into $i$ equal-sized and equal-valued crumbs.
Then, agent $i$ takes one crumb from each of the first $i-1$ agents. The fact
that this operation can always be performed crucially relies on the result of
[Alo87] concerning the existence of a perfect partition.111Informally, a
partition is said to be perfect if the value of every piece is the same for
every agent. Apart from piecewise constant valuation functions, our mechanism
also provides the same guarantees for piecewise linear valuations, which can
be succinctly represented, and for which perfect partitions can be computed
efficiently.

###  1.2 Related Work

Bayesian incentive compatibility in fair division has been considered in the
random assignment problem, with $n$ goods and $n$ agents with _ordinal_
preferences. [DM22] consider ordinal BIC mechanisms (OBIC), and show that the
probabilistic serial mechanism, which is ordinally efficient and satisfies
equal treatment of equals, is OBIC with respect to the uniform prior. The
notion of OBIC of [DM22] has been used in voting theory, dating back to
[dP88], to escape infamous dictatorship results [Gib73, Sat75]. For cardinal
valuations, such as ours, [Fuj08] studies the case of a single indivisible
good that must be allocated to one of $n$ agents whose (private) values for
the good are drawn from a known product distribution. When payments are
possible, [Fuj08] designs an envy-free, budget-balanced and BIC mechanism.

Another line of work considers other relaxations of DSIC. For example, in the
random assignment problem, [MS21b] introduce the notion of partial
strategyproofness, a relaxation of DSIC, which is satisfied if truthful
reporting is a dominant strategy for agents who have sufficiently different
valuations for different objects, and show that in the context of school
choice, this notion gives a separation between the classic and the adaptive
Boston mechanism. Starting with [TM20], a number of recent papers [OSH22,
AL21, PV22] relax the DSIC requirement and explore the design of not obviously
manipulable (NOM) mechanisms. Under NOM, an agent reports their true type,
unless lying is obviously better, where the definition of “obvious” for a
strategy follows recent work in Economics [Li17]. Closer to our interest here,
[PV22] study the allocation of indivisible goods among additive agents, and
prove that one can simultaneously guarantee EF1, PO, and NOM. [OSH22] show
that, in the context of cake-cutting, NOM is compatible with proportionality:
an adaptation of the moving-knife procedure satisfies both properties.

Other ways to escape the aforementioned impossibility results in truthful fair
division is restricting agents’ valuations, e.g. by focusing on dichotomous
[HPPS20, BEF21, BCIZ21, BV21] or Leontief valuations [GZH+11, FGP14, PPS15],
or by using money-burning (that is, leave resources unallocated) as a
substitute for payments, while trying to minimize the inefficiency that these
payment substitutes introduce (e.g., [HR08, CGG13, FTTZ16, FGPS19, ACGH20]).
Finally, a recent research thread suggests the study of mechanisms that
produce fair allocations in their equilibria [ABL+23, ABF+23]. Interestingly,
for agents with additive valuations over indivisible goods, it is known that
allocations obtained in equilibria of the Round-Robin algorithm are EF1 with
respect to the agents’ true valuation functions [ABF+23].

##  2 Preliminaries

Allocating indivisible goods. We are given a set $\mathcal{M}$ of $m$
indivisible items indexed by $[m]\coloneqq\\{1,2,\ldots,m\\}$ to be allocated
among a set $\mathcal{N}$ of $n$ agents indexed by $[n]$. An allocation
$\mathbf{x}\in\\{0,1\\}^{n\times m}$ assigns items to agents such that
$x_{i,j}=1$ if agent $i$ gets item $j$ and $0$ otherwise. We use
$\mathbf{x}_{i}=(x_{i,1},\dots,x_{i,m})\in\\{0,1\\}^{m}$ to denote agent $i$’s
_allocation_ and $X_{i}=\\{j:x_{i,j}=1\\}$ to denote agent $i$’s _bundle_ in
$\mathbf{x}$. In an allocation, each item $j\in\mathcal{M}$ must be allocated
to exactly one agent, i.e., $\sum_{i=1}^{n}x_{i,j}=1$. Each agent
$i\in\mathcal{N}$ has a private type which is a valuation vector
$\mathbf{v}_{i}\in\mathbb{R}^{m}_{\geq 0}$ where $v_{i,j}$ is agent $i$’s
value for item $j\in\mathcal{M}$. Collectively, the valuations of all the
agents are represented by a _valuation profile_
$\mathbf{v}=(\mathbf{v}_{1},\ldots,\mathbf{v}_{n})$. The _utility_ of agent
$i$ for a given allocation $\mathbf{x}$, denoted by $u_{i}(\mathbf{x})$, is
_additive_ and defined as
$u_{i}(\mathbf{x})\coloneqq\sum_{j\in\mathcal{M}}v_{i,j}x_{i,j}$. We will
often overload notations and use $u_{i}(X_{k})$ to denote the utility of agent
$i\in\mathcal{N}$ for a specific bundle $X_{k}\in\mathcal{M}$.

An allocation $\mathbf{x}$ _Pareto dominates_ another allocation $\mathbf{y}$
if for all agents $i\in\mathcal{N}$, we have $u_{i}(\mathbf{x})\geq
u_{i}(\mathbf{y})$ and $u_{j}(\mathbf{x})>u_{j}(\mathbf{y})$ for some agent
$j\in\mathcal{N}$. An allocation $\mathbf{x}$ is _Pareto efficient_ (or Pareto
optimal) if there is no other allocation $\mathbf{x}^{\prime}$ that Pareto
dominates it.

An allocation $\mathbf{x}$ is called _envy-free_ (EF) if for every pair of
agents $i$ and $j\in\mathcal{N}$, agent $i$ values their allocation at least
as much as the allocation of agent $j$, i.e., $u_{i}(\mathbf{x}_{i})\geq
u_{i}(\mathbf{x}_{j})$. However, for the indivisible item settings, an envy-
free allocation is not guaranteed to exist. Therefore, we consider a relaxed
notion called _envy-free up to one good_ (EF1). Formally, an allocation
$\mathbf{x}$ is EF1 if for every pair of agents $i$ and $j\in N$ with
$X_{j}\neq\emptyset$, agent $i$ values their allocation at least as much as
the allocation of agent $j$ without agent $i$’s favorite item, i.e.,
$u_{i}(X_{i})\geq u_{i}(X_{j}\setminus\\{g\\})$ for some $g\in X_{j}$.

Allocating divisible goods. We study the cake-cutting problem where the cake
is represented by the interval $[0,1]$ and is to be allocated among the set
$\mathcal{N}$ of $n$ agents. An allocation $\mathbf{x}=(X_{1},\dots,X_{n})$ is
a collection of mutually disjoint subsets of $[0,1]$ where
$X_{i}\subseteq[0,1]$ denotes the subset of the cake allocated to agent
$i\in\mathcal{N}$. Each agent $i$’s private type is a density (valuation)
function $f_{i}:[0,1]\rightarrow\mathbb{R}_{\geq 0}$ over the cake, such that
$\int_{0}^{1}f_{i}(x)dx=1$ for all $i\in\mathcal{N}$. We use
$\mathbf{f}=(f_{1},\ldots,f_{n})$ to denote the collection of density
functions of all agents. Given a subset $S\subseteq[0,1]$, agent $i$’s utility
on $S$ is defined as $u_{i}(S)=\int_{S}f_{i}(x)dx$.

We primarily focus on two classes of valuation functions, namely _piecewise-
constant_ and _piecewise-linear_ valuations. For both families, the interval
$[0,1]$ can be partitioned into finite intervals. For the former class, the
value of the function in each interval is a constant; for the latter class it
is linear.

An allocation $\mathbf{x}=(X_{1},\ldots,X_{n})$ is _proportional_ if each
agent receives her average share of the entire cake. Formally, for each agent
$i\in\mathcal{N}$ we have $u_{i}(X_{i})\geq\frac{1}{n}\cdot
u_{i}([0,1])=\frac{1}{n}$.

Mechanisms and incentive compatibility. For both indivisible and divisible
goods, each agent $i$ has a private type $t_{i}$: the valuations
$\mathbf{v}_{i}$ for the first and the functions $f_{i}$ for the second. The
agents, being strategic, may choose to misreport it if doing so increases
their utility. We use $\mathbf{b}=(\mathbf{b}_{1},\dots,\mathbf{b}_{n})$ to
represent the reported type $\mathbf{b}_{i}$ of all agent $i\in\mathcal{N}$. A
mechanism is represented by an allocation function $\mathbf{x}(\cdot)$, which
takes as input reports $\mathbf{b}=(\mathbf{b}_{1},\dots,\mathbf{b}_{n})$ and
outputs a feasible allocation $\mathbf{x}(\mathbf{b})$. For notational
simplicity, we often refer to a mechanism directly using its allocation
function $\mathbf{x}(\cdot)$.

We say a mechanism is _incentive compatible_ if it offers robustness
guarantees against strategic behaviors of agents. In this paper, we consider
two notions of incentive compatibility. A mechanism is _dominant strategy
incentive compatible (DSIC)_ if truthful reporting is a dominant strategy for
every agent. Formally, for every agent $i\in\mathcal{N}$, every possible
report $\mathbf{b}_{i}$, and all possible reports of all other agents
$\mathbf{b}_{-i}$, we have

$u_{i}(\mathbf{x}(\mathbf{t}_{i},\mathbf{b}_{-i}))\geq
u_{i}(\mathbf{x}(\mathbf{b}_{i},\mathbf{b}_{-i})).$

We also study the incentives in the Bayesian setting where agents have some
prior knowledge of each other’s type. We assume that the type $\mathbf{t}_{i}$
of each agent $i\in\mathcal{N}$ is drawn from some known prior distribution
$\mathcal{D}_{i}$. A mechanism is _Bayesian incentive compatible (BIC)_ for
priors $\times_{i=1}^{n}\mathcal{D}_{i}$ if reporting truthfully is a Bayesian
Nash equilibrium, i.e., no agent can increase her _expected_ utility by
unilaterally misreporting, the expectation being taken over the types of other
agents. We use $\mathcal{D}_{-i}$ to denote the prior $\times_{j\neq
i}\mathcal{D}_{j}$. Formally, for each agent $i\in\mathcal{N}$, and every
possible report $\mathbf{b}_{i}$, we have

$\mathop{\mathbb{E}}\limits_{\mathbf{t}_{-i}\sim\mathcal{D}_{-i}}[u_{i}(\mathbf{x}(\mathbf{t}_{i},\mathbf{t}_{-i})]\geq\mathop{\mathbb{E}}\limits_{\mathbf{t}_{-i}\sim\mathcal{D}_{-i}}[u_{i}(\mathbf{x}(\mathbf{b}_{i},\mathbf{t}_{-i}))].$

##  3 Allocating Indivisible Goods

Previous work on the allocation of indivisible goods has uncovered that DSIC
mechanisms cannot be both fair and efficient. A notable example shows that
requiring Pareto efficiency from a deterministic DSIC mechanism limits the
available options to the patently unfair class of serial dictatorships.

######  Theorem 1 ([KM02]).

For $n=2$ agents, a DSIC deterministic mechanism is Pareto efficient if and
only if it is a serial dictatorship.

Our first result, Theorem 1 in Section 3.1, strengthens Theorem 1, showing
that even if we weaken the efficiency requirement from Pareto efficiency to
$\mathrm{SD}^{+}$efficiency, a natural relaxation defined below, the only
deterministic DSIC mechanisms that can guarantee $\mathrm{SD}^{+}$efficiency
are serial dictatorships. Another notable result shows that no deterministic
DSIC mechanism always outputs EF1 allocations.

######  Theorem 2 ([ABCM17]).

There is no deterministic DSIC mechanism that outputs EF1 allocations, even
for instances involving just $n=2$ agents.

Theorem 3 in Section 3.2 shows that if we relax the notion of truthfulness
from DSIC to BIC, then neither one of these two negative results holds
anymore, i.e., there exists a non-dictatorial deterministic BIC mechanism that
guarantees EF1. In Section 3.3 we also uncover the limitations of BIC
mechanisms by proving that a wide family social choice functions are
incompatible with BIC.

###  3.1 Strengthening the characterization of serial dictatorships

For a given agent $i$ let $\mathbf{p}_{i}$ be a ranking of items
$j\in\mathcal{M}$ in decreasing order of $i$’s value for them, where
$\mathbf{p}_{i}(k)=j$ if item $j$ is agent $i$’s $k^{\text{th}}$ favorite
item.222For items with the same value, we break ties lexicographically, i.e.,
if $v_{i,j}=v_{i,k}$ and $j<k$, then item $j$ is ranked before $k$ in
$\mathbf{p}_{i}$. For two bundles
$\mathbf{x}_{i},\mathbf{y}_{i}\in\\{0,1\\}^{m}$, $\mathbf{x}_{i}$ _weakly
stochastically dominates $\mathbf{y}_{i}$ for agent $i$_, or
$\mathbf{x}_{i}\succeq_{i}\mathbf{y}_{i}$, iff for all $\ell\in[m]$ we have

$\sum^{\ell}_{k=1}x_{i,\mathbf{p}_{i}(k)}\geq\sum^{\ell}_{k=1}y_{i,\mathbf{p}_{i}(k)}.$
(1)

Additionally, we say that $\mathbf{x}_{i}$ _(strictly) stochastically
dominates $\mathbf{y}_{i}$ for agent $i$_, or
$\mathbf{x}_{i}\succ_{i}\mathbf{y}_{i}$, iff
$\mathbf{x}_{i}\succeq_{i}\mathbf{y}_{i}$ and
$\mathbf{x}_{i}\neq\mathbf{y}_{i}$. If
$\mathbf{x}_{i}\succ_{i}\mathbf{y}_{i}$, then there exists an $\ell\in[m]$ for
which Inequality (1) is strict.

To define our refinement of stochastic dominance, for each agent
$i\in\mathcal{N}$ we let $\mathcal{M}^{+}_{i}$ denote the set of items that
$i$ has a positive value for, i.e.,
$\mathcal{M}^{+}_{i}\coloneqq\\{j\in\mathcal{M}\ :\ v_{i,j}>0\\}$. Let
$m_{i}=|\mathcal{M}^{+}_{i}|$. For two bundles
$\mathbf{x}_{i},\mathbf{y}_{i}\in\\{0,1\\}^{m}$, we say that $\mathbf{x}_{i}$
weakly stochastically _and positively_ dominates $\mathbf{y}_{i}$, denoted as
$\mathbf{x}_{i}\succeq^{+}_{i}\mathbf{y}_{i}$, iff Inequality (1) is satisfied
for all $\ell\in\mathcal{M}^{+}_{i}$. Thus, partial order $\succeq^{+}_{i}$ is
essentially the partial order $\succeq$ defined over the set of items
$\mathcal{M}^{+}_{i}$. Similarly, $\mathbf{x}_{i}\succ^{+}_{i}\mathbf{y}_{i}$
iff $\mathbf{x}_{i}\succeq^{+}_{i}\mathbf{y}_{i}$ and
$\mathbf{x}_{i}\neq\mathbf{y}_{i}$. Akin to the previous definition, if
$\mathbf{x}_{i}\succ^{+}_{i}\mathbf{y}_{i}$, then there exists an
$\ell\in\mathcal{M}^{+}_{i}$ for which Inequality (1) is strict. Note that, if
two bundles satisfy $\mathbf{x}_{i}\succeq_{i}\mathbf{y}_{i}$, then by
definition, $\mathbf{x}_{i}\succeq^{+}_{i}\mathbf{y}_{i}$ as well. The
following lemma relates the partial orders defined above with utilities; it’s
proof along with other missing proofs from this subsection are deferred to
Appendix A.

lemmasdUtility For any agent $i\in\mathcal{N}$ and any two bundles
$\mathbf{a},\mathbf{b}\in\\{0,1\\}^{m}$, the following statements hold: $(1)$
If $\mathbf{a}\succeq^{+}_{i}\mathbf{b}$, then $u_{i}(\mathbf{a})\geq
u_{i}(\mathbf{b})$, and $(2)$ If $\mathbf{a}\succ^{+}_{i}\mathbf{b}$, then
$u_{i}(\mathbf{a})>u_{i}(\mathbf{b})$.

We say that an allocation $\mathbf{y}$ _stochastically dominates_
$\mathbf{x}$, denoted as $\mathbf{y}\succ\mathbf{x}$ iff for all agents
$i\in\mathcal{N}$ we have $\mathbf{y}_{i}\succeq_{i}\mathbf{x}_{i}$ and for at
least one agent $j\in\mathcal{N}$ we have
$\mathbf{y}_{j}\succ_{j}\mathbf{x}_{j}$. Similarly, we say that an allocation
$\mathbf{y}$ _stochastically and positively dominates_ $\mathbf{x}$, denoted
as $\mathbf{y}\succ^{+}\mathbf{x}$ iff for all agents $i\in\mathcal{N}$ we
have $\mathbf{y}_{i}\succeq^{+}_{i}\mathbf{x}_{i}$ and for at least one agent
$j\in\mathcal{N}$ we have $\mathbf{y}_{j}\succ^{+}_{j}\mathbf{x}_{j}$.

######  Definition 1.

An allocation $\mathbf{x}$ is $\mathrm{SD}$ efficient iff there is no other
allocation $\mathbf{y}$ such that $\mathbf{y}\succ\mathbf{x}$.

######  Definition 2.

An allocation $\mathbf{x}$ is $\mathrm{SD}^{+}$efficient iff there is no other
allocation $\mathbf{y}$ such that $\mathbf{y}\succ^{+}\mathbf{x}$.

In the following lemma we show that $\mathrm{SD}^{+}\text{efficiency}$ is
implied by Pareto efficiency and $\mathrm{SD}^{+}\text{efficiency}$ implies
$\mathrm{SD}\text{ efficiency}$.

######  Lemma 1.

The following two implications hold for any number of items and agents with
additive preferences: (1) If an allocation $\mathbf{x}$ is Pareto efficient
then $\mathbf{x}$ is $\mathrm{SD}^{+}$efficient as well; (2) If an allocation
$\mathbf{x}$ is $\mathrm{SD}^{+}$efficient then $\mathbf{x}$ is $\mathrm{SD}$
efficient as well. Moreover, there exist allocations that are
$\mathrm{SD}^{+}$efficient and not Pareto efficient, and allocations that are
$\mathrm{SD}$ efficient and not $\mathrm{SD}^{+}$efficient.

###### Proof.

_Proving (1)._ Towards a contradiction assume that allocation $\mathbf{x}$ is
Pareto efficient and not $\mathrm{SD}^{+}$efficient, i.e., there exists an
allocation $\mathbf{y}$ such that
$\mathbf{y}_{i}\succeq^{+}_{i}\mathbf{x}_{i}$ for all agent $i\in\mathcal{N}$
and for some agent $j\in\mathcal{N}$ we have
$\mathbf{y}_{j}\succ^{+}_{j}\mathbf{x}_{j}$. Therefore, on applying Lemma 3.1
we get that for all agents $i\in\mathcal{N}$ we have
$u_{i}(\mathbf{y}_{i})\geq u_{i}(\mathbf{x}_{i})$ and
$u_{j}(\mathbf{y}_{j})>u_{j}(\mathbf{x}_{j})$. This contradicts the fact that
$\mathbf{x}$ is Pareto efficient and thus established the concerned
implication.

_Proving (2)._ Assume, towards a contradiction, that there exists an
allocation $\mathbf{x}$ that is $\mathrm{SD}^{+}$efficient but not
$\mathrm{SD}$ efficient. This implies the existence of another allocation
$\mathbf{y}$ such that for each agent $i\in\mathcal{N}$ we have
$\mathbf{y}_{i}\succeq\mathbf{x}_{i}$ and there exists an agent
${i^{*}}\in\mathcal{N}$ such that
$\mathbf{y}_{i^{*}}\succ_{i^{*}}\mathbf{x}_{i^{*}}$. Note that, for each
$i\in\mathcal{N}$ we have $\mathbf{y}_{i}\succeq_{i}\mathbf{x}_{i}$, which
means that $\mathbf{y}_{i}\succeq^{+}_{i}\mathbf{x}_{i}$ as well. In
particular, $\mathbf{y}_{i^{*}}\succeq^{+}_{i^{*}}\mathbf{x}_{i^{*}}$,
however, it cannot be the case that
$\mathbf{y}_{i^{*}}\succ^{+}_{i^{*}}\mathbf{x}_{i^{*}}$, because this would
violate the fact that $\mathbf{x}$ is $\mathrm{SD}^{+}$efficient. Therefore,
the bundles received by agent $i^{*}$ must be such that
$\mathbf{y}_{i^{*}}\succ_{i^{*}}\mathbf{x}_{i^{*}}$ holds but
$\mathbf{y}_{i^{*}}\succ^{+}_{i^{*}}\mathbf{x}_{i^{*}}$ doesn’t hold.

The only way in which the bundles $\mathbf{y}_{i^{*}},\mathbf{x}_{i^{*}}$ can
satisfy $\mathbf{y}_{i^{*}}\succ_{i^{*}}\mathbf{x}_{i^{*}}$ but not
$\mathbf{y}_{i^{*}}\succ^{+}_{i^{*}}\mathbf{x}_{i^{*}}$ is if $(i)$ for all
$\ell\in[m_{i^{*}}]$, we have
$\sum^{\ell}_{k=1}y_{{i^{*}},\mathbf{p}_{i^{*}}(k)}=\sum^{\ell}_{k=1}x_{{i^{*}},\mathbf{p}_{i^{*}}(k)}$
and $(ii)$
$\sum^{m}_{k=1}y_{{i^{*}},\mathbf{p}_{i^{*}}(k)}>\sum^{m}_{k=1}x_{{i^{*}},\mathbf{p}_{i^{*}}(k)}$.
Since the allocations $\mathbf{y},\mathbf{x}$ are integral, $(ii)$
equivalently implies that the number of items in $\mathbf{y}_{i^{*}}$ is
strictly greater than the number of items in $\mathbf{x}_{i^{*}}$. Since
$\mathbf{y}_{i^{*}}$ has more items than $\mathbf{x}_{i^{*}}$, it must be the
case that for some other agent $t\in\mathcal{N}\setminus\\{i^{*}\\}$, the
bundle $\mathbf{x}_{t}$ has more items than $\mathbf{y}_{t}$. This can be
equivalently stated as
$\sum^{m_{t}}_{k=1}y_{t,\mathbf{p}_{t}(k)}<\sum^{m_{t}}_{k=1}x_{t,\mathbf{p}_{t}(k)}$.
However, this inequality violates the fact that
$\mathbf{y}_{t}\succeq_{t}\mathbf{x}_{t}$, and concludes the proof.

Finally, we show these implications are tight, by constructing allocations
that are $\mathrm{SD}^{+}$efficient but not Pareto efficient, and
$\mathrm{SD}$ efficient but not $\mathrm{SD}^{+}$efficient. These examples are
provided in Appendix C. ∎

Now we state and prove the main result of this subsection.

theoremsdpoplusResult(Characterization of serial dictatorship) For $n=2$
agents, a deterministic DSIC mechanism is $\mathrm{SD}^{+}$efficient if and
only if it is a serial dictatorship. This holds even when agents have ternary
valuations, i.e., for all agents $i$ and items $j$, we have
$v_{i,j}\in\\{0,x,y\\}$ for some $y>x>0$.

###### Proof.

Consider a setting where a fixed set of $m\geq 1$ items are to be divided
among $n=2$ agents. Through an inductive argument will establish that every
deterministic DSIC mechanism that outputs $\mathrm{SD}^{+}$efficient
allocations for this setting is a serial dictatorship. Specifically, our
approach will be as follows. We fix an arbitrary deterministic mechanism that
is DSIC and outputs $\mathrm{SD^{+}}$efficient allocations. Then, we consider
for each $d\in[m]$, the family of input bids
$\mathcal{F}_{d}\coloneqq\\{\mathbf{b}=(\mathbf{b}_{1},\mathbf{b}_{2})\ |\
b_{i,j}=0\text{ for all agents }i\in[2]\text{ and items }j>d\\}$. Note that,
the family of input bids $\\{\mathcal{F}_{d}\\}_{d\in[m]}$ follow a nested
structure:
$\mathcal{F}_{1}\subsetneq\mathcal{F}_{2}\ldots\subsetneq\mathcal{F}_{m-1}\subsetneq\mathcal{F}_{m}$.
Furthermore, $\mathcal{F}_{m}$ represents the set of all possible input bids
for the mechanism. We will inductively show that corresponding to the chosen
mechanism there must exist one agent, who will be the dictator. That is, the
mechanism on any input bid $\mathbf{b}\in\mathcal{F}_{m}$ will allocate all
the items positively-valued by the dictator, to the dictator, and the rest of
the items will be allocated to the other agents.333The items which are valued
zero (i.e., not desired) by both the agents will be allocated by this
mechanism in some arbitrary deterministic manner. Now we will formally state
our induction hypothesis.

Induction Hypothesis. For a parameter $d\in[m]$, the induction hypothesis
parameterized by $d$, $\mathrm{IH}(d)$ states that: the mechanism is a serial
dictatorship for all input bids $\mathbf{b}\in\mathcal{F}_{d}$.

In the subsequent proof, we will show that $\mathrm{IH}(d)$ holds true for all
$d\in[m]$. Indeed, establishing $\mathrm{IH}(m)$ shows that the mechanism is a
serial dictatorship since $\mathcal{F}_{m}$ represents the set of all input
bids to the mechanism. We begin by establishing the base case.

Base Case (proving $\mathrm{IH}(1)$). Consider an input bid
$\mathbf{b}=(\mathbf{b}_{1},\mathbf{b}_{2})\in\mathcal{F}_{1}$ such that
$b_{11}=b_{21}=x$ for some positive real number $x>0$; since
$\mathbf{b}\in\mathcal{F}_{1}$, we have $b_{ij}=0$ for all $i\in[n]$ and
$j>1$. Without loss of generality, we assume that our _deterministic_
mechanism outputs allocation $\mathbf{x}(\mathbf{b})$ such that
$x_{11}(\mathbf{b})=1$ and $x_{12}(\mathbf{b})=0$, i.e., item $1$ gets
allocated to agent $1$.444Indeed, this is without loss of generality since we
can always label the agent who receives item $1$ as being agent $1$. To
complete the base case, we will show that if the input bid
$\widehat{\mathbf{b}}\in\mathcal{F}_{1}$ is such that agent $1$ positively
values item $1$, then irrespective of agent $2$’s reported bid, the mechanism
will allocate item $1$ to agent $1$. This would establish that agent $1$ is a
dictator for bids $\widehat{\mathbf{b}}\in\mathcal{F}_{1}$, implying
$\mathrm{IH}(1)$.

To this end, consider the report
$\mathbf{b}^{\prime}=(\mathbf{b}^{\prime}_{1},\mathbf{b}_{2})\in\mathcal{F}_{1}$
with $b^{\prime}_{11}=y$. The fact that the mechanism is DSIC implies that the
mechanism on input bids $\mathbf{b}^{\prime}$ it must continue to allocate
item $1$ to agent $1$: otherwise, if item $1$ is not allocated to agent $1$,
then agent $1$ can misreport her preference by bidding $\mathbf{b}_{1}$
instead of $\mathbf{b}^{\prime}_{1}$, resulting in the bid profile
$\mathbf{b}=(\mathbf{b}_{1},\mathbf{b}_{2})$, in which case the mechanism will
allocate item $1$ to agent $1$, leading to an increase in agent $1$’s utility,
thereby contradicting the fact that the mechanism is DSIC. Thus, for both the
bids $\mathbf{b}$ and $\mathbf{b}^{\prime}$, item $1$ is not allocated to
agent $2$ despite the fact that agent $2$ has a positive value for it.
Therefore, the fact that the mechanism is DSIC implies that starting from
either bids $\mathbf{b}$ or $\mathbf{b}^{\prime}$, agent $2$ cannot misreport
her preferences in a way that item $1$ gets allocated to her, because this
would lead to an increase in her utility and thus would contradict DSIC. This
show that, if the input bids to the mechanism
$\widehat{\mathbf{b}}=(\widehat{b}_{1},\widehat{b}_{2})\in\mathcal{F}_{1}$ is
such that agent $1$ positively-values item $1$ (i.e.,
$\widehat{b}_{1,1}\in\\{x,y\\}$), then irrespective of agent $2$’s bid, item
$1$ is allocated to agent $1$.

Induction Step. To complete the proof, we will now show that if
$\mathrm{IH}(d)$ is true for some $1\leq d<m$, then $\mathrm{IH}(d+1)$ will be
true as well. Given $\mathrm{IH}(d)$, without loss of generality, we will
assume that agent $1$ is the dictator for all instances
$\widehat{\mathbf{b}}\in\mathcal{F}_{d}$. To prove $\mathrm{IH}(d+1)$, we will
consider a sequence of carefully designed bids. Then, utilizing the fact that
the mechanism is DSIC and outputs $\mathrm{SD}^{+}$efficient allocations along
with the induction hypothesis, $\mathrm{IH}(d)$, we will argue that the
mechanism must behave like a serial dictatorship for these sequence of bids,
eventually establishing $\mathrm{IH}(d+1)$. For ease of exposition, we will
decompose the subsequent proof into the following claims.

######  Claim 1.

Let $\mathbf{c}=(\mathbf{c}_{1},\mathbf{c}_{2})\in\mathcal{F}_{d+1}$ be the
bid shown below,555The first and the second row of the matrix represent
$\mathbf{c}_{1}$ and $\mathbf{c}_{2}$ respectively. For simplicity, the matrix
representation doesn’t show $c_{ij}$ for $i\in[2]$ and $j>d+1$ (columns $d+2$
to $m$ are omitted), because $\mathbf{c}\in\mathcal{F}_{d+1}$ and therefore
$c_{i,j}=0$. where for all $j\leq d$, $c_{2,j}\in\\{0,x,y\\}$ are arbitrary
fixed values. Given $\mathbf{c}$ as input, the mechanism must allocate all the
first $d+1$ items to agent $1$, i.e., $\mathbf{x}_{1,j}(\mathbf{c})=1$ for all
$j\leq d+1$.

$\displaystyle\mathbf{c}=\begin{pmatrix}\mathbf{c}_{1}\\\
\mathbf{c}_{2}\end{pmatrix}=\begin{pmatrix}y&y&\cdots&y&x\\\
c_{2,1}&c_{2,2}&\cdots&c_{2,d}&0\end{pmatrix}$

###### Proof.

First, note that item $d+1$, which is positively valued only by agent $1$,
must be allocated to agent $1$, i.e., $\mathbf{x}_{1,d+1}(\mathbf{c})=1$: if
item $d+1$ is allocated to agent $2$, then it can be transferred to agent $1$,
leading to a strict improvement in agent $1$’s bundle (wrt $\succ^{+}_{1}$)
and without affecting agent $2$’s bundle (wrt $\succeq^{+}_{2}$) since item
$d+1\notin\mathcal{M}^{+}_{2}$. That is, the allocation resulting from this
transfer will stochastically and positively dominate $\mathbf{x}(\mathbf{c})$,
contradicting the fact that the mechanism outputs $\mathrm{SD}^{+}$efficient
allocations. Hence, item $d+1$ must be allocated to agent $1$.

Now, towards a contradiction, suppose that there is an item $j\in[d]$ such
that $\mathbf{x}_{1,j}(\mathbf{c})=0$. This implies that agent $1$ is
allocated the item $d+1$ and at most $d-1$ items from the bundle $[d]$. That
is, her utility, $u_{1}(\mathbf{c})\leq x+(d-1)y$. Now we will show that, in
this case, agent $1$ can improve her utility by misreporting her preference to
be $\mathbf{c}^{\prime}_{1}$ where $c^{\prime}_{1,j}=y$ for all items
$j\in[d]$ and $c^{\prime}_{1,j}=0$ for items $j>d$. Note that, if agent $1$
misreports to $\mathbf{c}^{\prime}_{1}$, then the bid profile
$\mathbf{c}^{\prime}=(\mathbf{c}^{\prime}_{1},\mathbf{c}_{2})\in\mathcal{F}_{d}$
since for all items $j>d$, we have $c^{\prime}_{1,j}=c_{2,j}=0$. Because
$\mathbf{c}^{\prime}\in\mathcal{F}_{d}$, we can invoke $\mathrm{IH}(d)$ to
infer that, agent $1$ will be the dictator, and thus all the items $j\in[d]$
will be allocated to agent $1$. Hence, her utility, as per her true
preference, $\mathbf{c}_{1}$, in $\mathbf{x}(\mathbf{c}^{\prime})$ will be
$u_{i}(\mathbf{c}^{\prime})\geq d\cdot y$. However, this violates the fact
that the mechanism is DSIC, since agent $1$ is able to improve her utility
from $u_{1}(\mathbf{c})\leq x+(d-1)y$ to $u_{i}(\mathbf{c}^{\prime})\geq
d\cdot y$ by misreporting because $y>x$ and hence
$u_{i}(\mathbf{c}^{\prime})\geq d\cdot y>x+(d-1)y\geq u_{1}(\mathbf{c})$.
Therefore, all the items $j\in[d+1]$ must be allocated to agent $1$,
$\mathbf{x}_{1,j}(\mathbf{c})=1$. ∎

######  Claim 2.

Let $\mathbf{e}=(\mathbf{e}_{1},\mathbf{e}_{2})\in\mathcal{F}_{d+1}$ be the
bid shown below. Given $\mathbf{e}$ as input, the mechanism must allocate all
the first $d+1$ items to agent $1$, i.e., $\mathbf{x}_{1,j}(\mathbf{e})=1$ for
all $j\leq d+1$.

$\displaystyle\mathbf{e}=\begin{pmatrix}\mathbf{e}_{1}\\\
\mathbf{e}_{2}\end{pmatrix}=\begin{pmatrix}x&x&\cdots&x&y\\\
y&y&\cdots&y&x\end{pmatrix}$

###### Proof.

Consider the profile
$\mathbf{f}=(\mathbf{f}_{1},\mathbf{f}_{2})\in\mathcal{F}_{d+1}$ shown below
where for all items $j\in[d+1]$ we have $f_{1,j}\in\\{x,y\\}$,
$f_{2,j}\in\\{0,x,y\\}$ for all $j\in[d]$ and $f_{2,d+1}=0$.

$\displaystyle\mathbf{f}=\begin{pmatrix}\mathbf{f}_{1}\\\
\mathbf{f}_{2}\end{pmatrix}=\begin{pmatrix}f_{1,1}&f_{1,2}&\cdots&f_{1,d}&f_{1,d+1}\\\
f_{2,1}&f_{2,2}&\cdots&f_{2,d}&0\end{pmatrix}$

By definition, only items in $[d+1]$ are positively-valued by agent $1$, i.e.,
$\mathcal{M}^{+}_{1}=[d+1]$. We will first show that all items in $[d+1]$ will
be allocated to agent $1$ in $\mathbf{x}(\mathbf{f})$. Towards this, note that
if agent $1$ doesn’t receive all the items in $[d+1]$, then she can increase
her utility by misreporting her preference from $\mathbf{f}_{1}$ to
$\mathbf{c}_{1}$: if agent $1$ misreports, then the resultant bids
$(\mathbf{c}_{1},\mathbf{f}_{2})$ will match the condition in Claim 1, and
hence, by Claim 1, all the items in $[d+1]$ will be allocated to agent $1$
resulting in an increase in utility. This will violate the fact that the
mechanism is DSIC, implying that all the items in $[d+1]$ must be allocated to
agent $1$ in the allocation $\mathbf{x}(\mathbf{f})$. In particular, if we
consider the following bid
$\mathbf{f}^{\prime}=(\mathbf{f}^{\prime}_{1},\mathbf{f}^{\prime}_{2})\in\mathcal{F}_{d+1}$,
which is a particular instantiation of the bids in $\mathbf{f}$, then we know
that all the items in $[d+1]$ will be allocated to agent $1$.

$\displaystyle\mathbf{f}^{\prime}=\begin{pmatrix}\mathbf{f}^{\prime}_{1}\\\
\mathbf{f}^{\prime}_{2}\end{pmatrix}=\begin{pmatrix}x&x&\cdots&x&y\\\
y&y&\cdots&y&0\end{pmatrix}$

Using this, we will now show that, the items $[d+1]$ must be allocated to
agent $1$ in the allocation $\mathbf{x}(\mathbf{e})$ corresponding to the
concerned bids $\mathbf{e}$ shown below.

$\displaystyle\mathbf{e}=\begin{pmatrix}\mathbf{e}_{1}\\\
\mathbf{e}_{2}\end{pmatrix}=\begin{pmatrix}x&x&\cdots&x&y\\\
y&y&\cdots&y&x\end{pmatrix}$

The subsequent proof will be in two parts: first, we will show that all the
items in $[d]$ will be allocated to agent $1$ in $\mathbf{x}(\mathbf{e})$,
then, we will show the same of item $d+1$. For the first part, assume towards
a contradiction, that agent $2$ receives an item $j^{*}\in[d]$ for bid
$\mathbf{e}$, i.e., $\mathbf{x}_{2,j^{*}}(\mathbf{e})=1$. Given this, starting
from the input bids
$\mathbf{f}^{\prime}=(\mathbf{f}^{\prime}_{1},\mathbf{f}^{\prime}_{2})$, agent
$2$, having a true valuation of $\mathbf{f}^{\prime}_{2}$, can increase her
utility by misreporting to $\mathbf{e}_{2}$. Note that, if agent $2$
misreports to $\mathbf{e}_{2}$, then the resultant bids
$(\mathbf{f}^{\prime}_{1},\mathbf{e}_{2})$ is exactly same as the bids
$\mathbf{e}$. Therefore, if agent $2$ misreports, then she will be allocated
the item $j^{*}\in[d]$, since $\mathbf{x}_{2,j^{*}}(\mathbf{e})=1$ where
$j^{*}$ is positively valued by agent $2$,
$\mathbf{f}^{\prime}_{2,j^{*}}=y>0$. On the contrary, if agent $2$ reports her
true valuation, then we know that in the resultant bids,
$\mathbf{f}^{\prime}=(\mathbf{f}^{\prime}_{1},\mathbf{f}^{\prime}_{2})$, all
the items in $[d+1]$ will be allocated to agent $1$. Hence, by misreporting to
$\mathbf{e}_{2}$, agent $2$ can increase her utility, contradicting the fact
that the mechanism is DSIC. Therefore, for all items $j\in[d]$, we must have
$\mathbf{x}_{1,j}(\mathbf{e})=1$. Finally, we will show that
$\mathbf{x}_{1,d+1}(\mathbf{e})=1$ as well. Suppose this is not the case,
i.e., $\mathbf{x}_{1,d+1}(\mathbf{e})=0$. As already shown, item $d$ is
allocated to agent $1$, and as per our assumption, item $d+1$ is allocated to
agent $2$. Note that, in bid $\mathbf{e}$, the value of item $d$ for agent $1$
and item $d+1$ for agent $2$ is $x$, whereas, the value of item $d+1$ for
agent $1$ and item $d$ for agent $2$ is $y$ where $y>x$. Therefore, if agents
$1$ and $2$ exchange items $d$ and $d+1$ between them, then the bundles of
both the agents in the resultant allocation are strictly better wrt
$\succ^{+}_{1}$ and $\succ^{+}_{2}$ respectively. This implies that the
allocation before the exchange was not $\mathrm{SD}^{+}$efficient,
contradicting the fact that the mechanism outputs $\mathrm{SD}^{+}$efficient
allocations. Therefore, item $d+1$ also must be allocated to agent $1$, i.e.,
$\mathbf{x}_{1,d+1}(\mathbf{e})=1$. ∎

Finally, we will show that $\mathrm{IH}(d+1)$ holds. We begin by considering
the bids $\mathbf{g}=(\mathbf{g}_{1},\mathbf{g}_{2})$ shown below, where
$g_{2,j}\in\\{0,x,y\\}$ for all items $j\in[d+1]$, i.e., agent $2$’s bids are
completely arbitrary.

$\displaystyle\mathbf{g}=\begin{pmatrix}\mathbf{g}_{1}\\\
\mathbf{g}_{2}\end{pmatrix}=\begin{pmatrix}x&x&\cdots&x&y\\\
g_{2,1}&g_{2,2}&\cdots&g_{2,d}&g_{2,d+1}\end{pmatrix}$

The allocation $\mathbf{x}(\mathbf{g})$ must be such that all items $[d+1]$
are allocated to agent $1$: otherwise, if there is an item
$j^{\prime}\in[d+1]$ such that $\mathbf{x}_{2,j^{\prime}}(\mathbf{g})=1$, then
starting from the bids $\mathbf{e}$, agent $2$ can misreport her valuation to
$\mathbf{g}_{2}$ and increase her utility. As shown in Claim 2, agent $2$ does
not receive any item from $[d+1]$ in the allocation $\mathbf{x}(\mathbf{e})$
despite having positive value for all of them in $\mathbf{e}$. However, if
starting from profile $\mathbf{e}$, agent $2$ misreports her value to be
$\mathbf{g}_{2}$, then as per our assumption, she will at least receive item
$j^{\prime}\in[d+1]$ in the resultant profile
$(\mathbf{e}_{1},\mathbf{g}_{2})$ because
$\mathbf{g}=(\mathbf{e}_{1},\mathbf{g}_{2})$, thereby increasing her utility.
Since this violates the fact that the mechanism is DSIC, it must be the case
that all items in $[d+1]$ are allocated to agent $1$. This implies that if
agent $1$ reports valuation $\mathbf{g}_{1}$, then irrespective of agent $2$’s
bid all the items in $[d+1]$ are allocated to agent $1$.

As the final step of the proof, we consider a completely arbitrary bid profile
$\mathbf{h}=(\mathbf{h}_{1},\mathbf{h}_{2})\in\mathcal{F}_{d+1}$ shown below
where $h_{i,j}\in\\{0,x,y\\}$ for all agents $i\in[2]$ and items $j\in[d+1]$.
Since the mechanism is DSIC, we have that in allocation
$\mathbf{x}(\mathbf{h})$, agent $1$ must receive all the items she has a
positive value for: since otherwise she can misreport her value as
$\mathbf{g}_{1}$, resulting in the bid profile
$(\mathbf{g}_{1},\mathbf{h}_{2})$ (which is equivalent to $\mathbf{g}$), and
as previously shown, agent $1$ receives all $[d+1]$ items in allocation
$\mathbf{g}$. Therefore, in an arbitrary bid profile,
$\mathbf{h}\in\mathcal{F}_{d+1}$, agent $1$ will receive all the items she has
a positive value for, establishing her to be the dictator and proving
$\mathrm{IH}(d+1)$. Finally, note that the items which are positively valued
only by agent $2$, must be allocated to agent $2$, since the mechanism outputs
$\mathrm{SD}^{+}$efficient allocations. This completes the induction step and
concludes the proof.

$\displaystyle\mathbf{h}=\begin{pmatrix}\mathbf{h}_{1}\\\
\mathbf{h}_{2}\end{pmatrix}=\begin{pmatrix}h_{1,1}&h_{1,2}&\cdots&h_{1,d}&h_{1,d+1}\\\
h_{2,1}&h_{2,2}&\cdots&h_{2,d}&h_{2,d+1}\end{pmatrix}\quad$

∎

#### Tightness of the above characterization

In the following two propositions, we show that Theorem 1 is tight in two
orthogonal ways (their proof appear in Appendix A). Specifically, if we relax
$\mathrm{SD}^{+}\text{efficiency}$ to the weaker notion of $\mathrm{SD}\text{
efficiency}$, then serial dictatorship no longer remains the only DSIC
mechanism — this is formally stated in Proposition 3.1. Note that although
$\mathrm{SD}$ efficiency is widely used in matching (where all agents receive
the same number of items), the notion of $\mathrm{SD}^{+}$efficiency is more
appropriate when each agent may receive a different number of items.
Specifically, an allocation can only be stochastically dominated by another
allocation if all agents receive at least the same number of items; this is
not true for stochastically and positively dominated.

propositiontightnessPropOne For $n=2$ agents, there exists a deterministic
mechanism other than the serial dictatorship that is DSIC and outputs
$\mathrm{SD}$ efficient allocations.

Second, the proof of Theorem 1 holds even for ternary preferences i.e.,
$v_{i,j}\in\\{0,x,y\\}$ for all $i\in\mathcal{N}$ and $j\in\mathcal{M}$. In
fact, Theorem 1 does not hold if we consider the slightly more restricted
class of bivalued preferences, i.e., $v_{i,j}\in\\{x,y\\}$ for fixed
$x,y\in\mathbb{R}_{\geq 0}$.

propositionbivaluedPref For bivalued additive preferences, there exist DSIC,
non-dictatorial mechanisms that output Pareto efficient allocations.

###  3.2 Round Robin is BIC

We now show that a variation of Round-Robin, which we call Round-
Robin${}^{\text{pass}}$ ($\mathrm{RR}^{\text{pass}}$), is BIC for neutral
priors. Moreover, $\mathrm{RR}^{\text{pass}}$ always outputs an
$\mathrm{SD}^{+}$efficient and $\mathrm{EF}1$ allocation,666We note that items
which have zero value for all the agents won’t be allocated by
$\mathrm{RR}^{\text{pass}}$. Indeed, this does not affect the fairness and
efficiency guarantees of $\mathrm{RR}^{\text{pass}}$. bypassing the negative
results of Theorems 2 and 1.

#### The Bayesian Setting.

We assume that the for each agent $i\in\mathcal{N}$, there is a _neutral_
prior distribution $\mathcal{D}_{i}$ supported over $\mathbb{R}_{\geq 0}^{m}$
such that the valuation vector
$\mathbf{v}_{i}=(v_{i,1},\ldots,v_{i,m})\sim\mathcal{D}_{i}$. We say that
$\mathcal{D}_{i}$ is neutral if for every permutation $\sigma:[m]\to[m]$, we
have
$\Pr_{\mathbf{v}_{i}\sim\mathcal{D}_{i}}[v_{i,\sigma(1)}>\ldots>v_{i,\sigma(m)}]=\frac{1}{m!}$,
and for each $j\in\mathcal{M}$, the marginal distribution of $\mathcal{D}_{i}$
wrt $v_{ij}$ does not have point masses. Intuitively, neutral priors imply
that all items are equivalent, in expectation. A natural example of a neutral
prior is $v_{i,j}\sim\widehat{\mathcal{D}}_{i}$ where
$\widehat{\mathcal{D}}_{i}$ is supported on $\mathbb{R}_{\geq 0}$ and does not
have a point mass. This exact prior has been extensively studied in the
literature on stochastic fair division [BG21, MS20, MS21a, AMNS17]; a
stochastic fair division model based on neutrality is also studied in
[BHPV23]. Note that, neutral priors are permissive enough to allow for
correlated item values, for e.g., if $\mathbf{v}_{i}\sim\Delta^{m-1}$ where
$\sim\Delta^{m-1}$ denotes a uniform draw from the $m-1$-simplex,777Recall
that, an $m-1$-simplex
$\Delta^{m-1}=\\{(x_{1},x_{2},\ldots,x_{m}):\sum_{i}x_{i}=1\text{ and
}x_{i}\geq 0\text{ for all }i\\}$ then the item values are identically
distributed but not independent. Additionally, the item values for an agent
don’t even have to be identically drawn: for two items, the prior
$v_{i,1}\sim\mathcal{U}[0,1]$ and
$v_{i,2}\sim\mathcal{U}[\frac{1}{2},\frac{3}{4}]$ is
neutral.888$\mathcal{U}[a,b]$ represents a uniform distribution over the
interval $[a,b]$.

#### Our Mechanism.

We begin by defining the $\mathrm{RR}^{\text{pass}}$ mechanism: intuitively,
we execute the standard Round-Robin procedure but allow agents to _pass_ their
turn if all the remaining items are zero-valued. Formally, given the report
$\mathbf{b}_{i}$ for each agent $i\in\mathcal{N}$, the mechanism first
computes a tuple $(\mathbf{p}_{i},m_{i})$, where $\mathbf{p}_{i}$ is the
strict preference order of items for agent $i$ (ties are broken
lexicographically), and $m_{i}=|\mathcal{M}^{+}_{i}|$, where
$\mathcal{M}^{+}_{i}=\\{j:b_{i,j}>0\\}$ is the set of items agent $i$ values
positively. Then the mechanism constructs the output allocation over rounds.
In each round, agents arrive in the fixed order $1,2,\ldots,n$, and each agent
$i\in\mathcal{N}$ is allocated the item with the smallest (according to
$\mathbf{p}_{i}$) ranking among the set of remaining items; if in agent $i$’s
turn all items in $\mathcal{M}_{i}^{+}$ have already been allocated, then
$\mathrm{RR}^{\text{pass}}$ skips $i$’s turn. This process is repeated until
either all the items are allocated or all remaining items are undesirable for
all the agents. In the latter case, the remaining items are allocated
deterministically and arbitrarily among the agents, resulting in a complete
allocation. $\mathrm{RR}^{\text{pass}}$ is almost ordinal, i.e., to execute it
we need the (strict) preference order $\mathbf{p}_{i}$, but also the number of
zero-valued items $m_{i}$ for each $i\in\mathcal{N}$ (noting that one can
construct $\mathcal{M}^{+}_{i}$ by looking at the bottom $m_{i}$ elements of
$\mathbf{p}_{i}$). Thus, in the subsequent discussion, we often interchange
$\mathbf{v}_{i}$ with $(\mathbf{p}_{i},m_{i})$. Our goal is to prove the
following theorem.

######  Theorem 3.

The Round-Robin${}^{\text{pass}}$ mechanism is Bayesian incentive compatible
for neutral priors, and always outputs SD+efficient and $\mathrm{EF}1$
allocations.

First, we prove that $\mathrm{RR}^{\text{pass}}$ is BIC for neutral priors.
The high-level idea of our proof is similar to the arguments of [DM22] for
showing that the probabilistic serial mechanism is BIC in a setting with
complete ordinal preferences. Unlike the ordinal setting, our cardinal setting
allows agents to have undesirable, zero-valued items. As hinted by Theorem 1
and Proposition 3.1, allowing for zero values makes it harder to establish
incentive guarantees. To mitigate this, our mechanism
$\mathrm{RR}^{\text{pass}}$ (contrary to Round-Robin) never allocates an item
to an agent that doesn’t value it, unless the item is valued at zero by
everyone. This special treatment of zero values is required to prove key
structural properties about the _interim allocation_ (defined below), which
are used throughout our proofs.

For each agent $i\in\mathcal{N}$ and item $j\in\mathcal{M}$ we define the
interim allocation $q_{i,j}(\mathbf{b}_{i})\in[0,1]$ of a mechanism with
allocation function $\mathbf{x}(\cdot)$ to be the probability that agent $i$
is allocated item $j$ when she reports $\mathbf{b}_{i}$. Formally,
$q_{i,j}(\mathbf{b}_{i})=\mathbb{P}_{\mathbf{v}_{-i}\sim\mathcal{D}_{-i}}[x_{i,j}(\mathbf{b}_{i},\mathbf{v}_{-i})]$.

We show that, for each agent $i\in\mathcal{N}$, the interim allocation of the
$\mathrm{RR}^{\text{pass}}$ mechanism, given neutral priors, is very
structured. For each agent $i\in\mathcal{N}$, there is a (fixed) positional
interim allocation
$\mathbf{q_{i}^{\texttt{pos}}}=(q^{\texttt{pos}}_{i,1},q^{\texttt{pos}}_{i,2},\ldots,q^{\texttt{pos}}_{i,m})$
such that, if agent $i$ reports valuation $\mathbf{b}_{i}$ to
$\mathrm{RR}^{\text{pass}}$, then her interim allocation
$q_{i,j}(\mathbf{b}_{i})$ is exactly $q^{\texttt{pos}}_{i,k}$ if $b_{i,j}>0$
and $\mathbf{p}_{i}(k)=j$; otherwise, $q_{i,j}(\mathbf{b}_{i})=0$ if
$b_{i,j}=0$ (Lemma 3). Intuitively, the interim allocation of a positively
valued item depends on only its position in the preference order. Furthermore,
the positional interim allocations are monotone:
$q^{\texttt{pos}}_{i,1}\geq\ldots\geq q^{\texttt{pos}}_{i,m}$ (Lemma 3).

Since $\mathrm{RR}^{\text{pass}}$ only requires the tuples
$\\{(\mathbf{p}_{i},m_{i})\\}_{i\in\mathcal{N}}$ to execute, overloading
notations, we will also write the interim allocation as a function of these
tuples, i.e., $q_{i,j}(\mathbf{p}_{i},m_{i})$. As previously mentioned,
neutral priors ensure that each of the $m!$ possible ordering of
$\mathbf{p}_{j}$, for any agent $j\neq i$ is equally likely. In addition, the
fact that each marginal distribution of $\mathcal{D}_{j}$ does not have any
point mass, implies that, with probability $1$, we have $m_{j}=m$ for all
$j\neq i$. Using these observations, we can write the interim allocation of
agent $i$ as,

$\displaystyle
q_{i,j}(\mathbf{p}_{i},m_{i})=\frac{1}{\left(m!\right)^{n-1}}\sum_{\mathbf{p}_{-i}}x_{i,j}((\mathbf{p}_{i},m_{i}),(\mathbf{p}_{-i},m)),$
(2)

for each item $j\in\mathcal{M}$, where
$(\mathbf{p}_{-i},m)=\\{(\mathbf{p}_{j},m_{j})\\}_{j\neq i}$.

lemmaItemIndependence For each agent $i\in\mathcal{N}$, there exists a
positional interim allocation
$\mathbf{q_{i}^{\texttt{pos}}}=(q^{\texttt{pos}}_{i,1},\ldots,q^{\texttt{pos}}_{i,m})$
such that if agent $i$ reports any valuation $\mathbf{b}_{i}$, then her
interim allocation $q_{i,j}(\mathbf{b}_{i})=q^{\texttt{pos}}_{i,k}$ if (i)
$b_{i,j}>0$, and (ii) $\mathbf{p}_{i}(k)=j$; otherwise,
$q_{i,j}(\mathbf{b}_{i})=0$ if $b_{i,j}=0$.

###### Proof.

By definition of $\mathrm{RR}^{\text{pass}}$, if $b_{i,j}=0$, then agent $i$
can be allocated item $j$ only if $j$ is valued zero by all other agents.
Since the marginal distributions of $\\{\mathcal{D}_{j}\\}_{j\neq i}$ do not
have a point mass, this is a zero probability event, and hence, we get that
$q_{i,j}(\mathbf{b}_{i})=0$ if $b_{i,j}=0$. In the subsequent proof, we will
focus on the case when $b_{i,j}>0$. Let $\widehat{\mathbf{b}}_{i}$ and
$\widetilde{\mathbf{b}}_{i}$ be two bids whose corresponding preference orders
are $\widehat{\mathbf{p}}_{i}$ and $\widetilde{\mathbf{p}}_{i}$ respectively.
Additionally, suppose $\widehat{m}=|\\{j:\widehat{b}_{i,j}>0\\}|$ and
$\widetilde{m}=|\\{j:\widetilde{b}_{i,j}>0\\}|$ for some
$\widehat{m}\leq\widetilde{m}$. Given this, we will show that if
$\widehat{\mathbf{p}}_{i}(k)=r$ and $\widetilde{\mathbf{p}}_{i}(k)=s$ for some
$k\leq\widehat{m}$, then we must have
$q_{i,r}(\widehat{\mathbf{p}}_{i},\widehat{m})=q_{i,s}(\widetilde{\mathbf{p}}_{i},\widetilde{m})$.
This will imply that the interim allocation only depends on the ranking of the
item. Finally, defining $q^{\texttt{pos}}_{i,k}\coloneqq
q_{i,r}(\widehat{\mathbf{p}}_{i},\widehat{m})=q_{i,s}(\widetilde{\mathbf{p}}_{i},\widetilde{m})$
will complete the proof.

The proof of this will be based on establishing the following, simpler,
pairwise-version of the above proposition. For a given preference order
$\mathbf{p}_{i}$, define $\mathbf{p}^{\prime}_{i}=\sigma(\mathbf{p}_{i})$ to
be the preference order obtained by swapping the ranks of items $a$ and $b$,
where $\sigma:[m]\to[m]$ is some permutation of items with $\sigma(a)=b$,
$\sigma(b)=a$, and $\sigma(\ell)=\ell$ for all $\ell\in[m]\setminus\\{a,b\\}$.
Given this, we will show that the interim allocations corresponding to
$\mathbf{p}_{i}$ and $\mathbf{p}^{\prime}_{i}$ are such that, we have

$\displaystyle
q_{i,j}(\mathbf{p}_{i},\widehat{m})=q_{i,\sigma(j)}(\mathbf{p}^{\prime}_{i},\widehat{m}),$
(3)

for all items $j\in\mathcal{M}$. This implies that the interim allocations do
not change wrt the ranking of items if we swap two items. Note that, by
repeatedly swapping pairs of items, we can convert the ordering
$\widehat{\mathbf{p}}_{i}$ to $\widetilde{\mathbf{p}}_{i}$. By Equation (3),
this implies that
$q_{i,r}(\widehat{\mathbf{p}}_{i},\widehat{m})=q_{i,s}(\widetilde{\mathbf{p}}_{i},\widehat{m})$.
Additionally, note that
$q_{i,s}(\widetilde{\mathbf{p}}_{i},\widehat{m})=q_{i,s}(\widetilde{\mathbf{p}}_{i},\widetilde{m})$.
This follows the fact that $k\leq\widehat{m}\leq\widetilde{m}$ (where
$\widetilde{\mathbf{p}}_{i}(k)=s$) and by definition of
$\mathrm{RR}^{\text{pass}}$ increasing the second value of the tuple (i.e.,
$\widehat{m}\leq\widetilde{m}$) cannot change the allocation of an item whose
rank is less than or equal to $\widehat{m}$. Hence, Equation (3), once
established will imply that
$q_{i,r}(\widehat{\mathbf{p}}_{i},\widehat{m})=q_{i,s}(\widetilde{\mathbf{p}}_{i},\widetilde{m})$.

Therefore, to complete the proof will now establish Equation (3). Note that
for every possible report of other agents, $\mathbf{p}_{-i}$ we have,

$\displaystyle x_{i,j}((\mathbf{p}_{i},\widehat{m})(\mathbf{p}_{-i},m))$
$\displaystyle=x_{i,\sigma(j)}((\sigma(\mathbf{p}_{i}),\widehat{m}),(\sigma(\mathbf{p}_{-i}),m))$
$\displaystyle=x_{i,\sigma(j)}((\mathbf{p}^{\prime}_{i},\widehat{m}),(\sigma(\mathbf{p}_{-i}),m)),$
(4)

where $(\sigma(\mathbf{p}_{-i}),m)=\\{(\sigma(\mathbf{p}_{j}),m)\\}_{j\neq
i}$. The first equality above is based on the following observation. Item $j$
is allocated to agent $i$ given preference orders $\mathbf{p}_{i}$ and
$\mathbf{p}_{-i}$ iff agent $i$ receives the item $\sigma(j)$ given preference
orders $\sigma(\mathbf{p}_{i})$ and $\sigma(\mathbf{p}_{-i})$. This is true
because, given the preference orders of each agent, the allocation returned by
$\mathrm{RR}^{\text{pass}}$ depends only on the preference orders and not the
indexes of the items. Using this, we have that for all items
$j\in\mathcal{M}$,

$\displaystyle q_{i,j}(\mathbf{p}_{i},\widehat{m})$
$\displaystyle=\frac{1}{(m!)^{n-1}}\sum_{\mathbf{p}_{-i}}x_{i,j}((\mathbf{p}_{i},\widehat{m}),(\mathbf{p}_{-i},m))$
(via (2))
$\displaystyle=\frac{1}{(m!)^{n-1}}\sum_{\mathbf{p}_{-i}}x_{i,\sigma(j)}((\mathbf{p}^{\prime}_{i},\widehat{m}),(\sigma(\mathbf{p}_{-i}),m))$
(via (3.2))
$\displaystyle=\frac{1}{(m!)^{n-1}}\sum_{\mathbf{p}_{-i}}x_{i,\sigma(j)}((\mathbf{p}^{\prime}_{i},\widehat{m}),(\mathbf{p}_{-i},m))$
$\displaystyle=q_{i,\sigma(j)}(\mathbf{p}^{\prime}_{i},\widehat{m}),$ (via
(2))

where the penultimate equality holds because the set of all $\mathbf{p}_{-i}$
and the set of all $\sigma(\mathbf{p}_{-i})$ is the same. This establishes
Equation (3) and concludes the proof. ∎

lemmainterimMonotonicity Positional interim allocations are monotone, i.e.,
$q^{\texttt{pos}}_{i,1}\geq q^{\texttt{pos}}_{i,2}\geq\ldots\geq
q^{\texttt{pos}}_{i,m}$ for all $i\in\mathcal{N}$.

###### Proof.

We will show that $q^{\texttt{pos}}_{i,k}\geq q^{\texttt{pos}}_{i,k+1}$ for
all $k<m$. Towards this, consider a bid $\mathbf{b}_{i}$ such that $(i)$ all
items are positively valued, $|\mathcal{M}^{+}_{i}|=m$, and $(ii)$ the
corresponding preference order $\mathbf{p}_{i}$ is such that
$\mathbf{p}_{i}(k)=a$ and $\mathbf{p}_{i}(k+1)=b$ for some items
$a,b\in\mathcal{M}$. Additionally, let $\mathbf{p}^{\prime}_{i}$ be a
preference order constructed by swapping $a$ and $b$ in $\mathbf{p}_{i}$,
i.e., $\mathbf{p}^{\prime}_{i}(k)=b$ and $\mathbf{p}^{\prime}_{i}(k+1)=a$, and
$\mathbf{p}^{\prime}_{i}(\ell)=\mathbf{p}_{i}(\ell)$ for all
$\ell\neq\\{k,k+1\\}$.

As the key part of the proof, we will first show that inequality

$\displaystyle x_{i,a}((\mathbf{p}_{i},m),(\mathbf{p}_{-i},m))\geq
x_{i,a}((\mathbf{p}^{\prime}_{i},m),(\mathbf{p}_{-i},m)),$ (5)

where $(\mathbf{p}_{-i},m)=\\{(\mathbf{p}_{j},m)\\}_{j\neq i}$ holds for all
preference orders of other agents $\mathbf{p}_{-i}$.999We note that this
property has been referred to as elementary monotonicity in [DM22]. Note that,
both the quantities are binary,
$x_{i,a}((\mathbf{p}^{\prime}_{i},m),(\mathbf{p}_{-i},m)),x_{i,a}((\mathbf{p}_{i},m),(\mathbf{p}_{-i},m))\in\\{0,1\\}$.
Hence, the concerned inequality is trivially satisfied if
$x_{i,a}((\mathbf{p}_{i},m),(\mathbf{p}_{-i},m))=1$. Otherwise if
$x_{i,a}((\mathbf{p}_{i},m),(\mathbf{p}_{-i},m))=0$, we can show that
necessarily $x_{i,a}((\mathbf{p}^{\prime}_{i},m),(\mathbf{p}_{-i},m))=0$ as
well. This follows from the following observations. Since agent $i$ does not
receive item $a$ when reporting preference $\mathbf{p}_{i}$, $a$ must have
already been allocated to some other agent before agent $i$ could have picked
it. Now if she reports $\mathbf{p}^{\prime}_{i}$, wherein item $a$ has an even
lower rank ($\mathbf{p}^{\prime}_{i}(k+1)=a$), then agent $i$ still won’t
receive item $a$ because similar to the previous case, $a$ would have already
been allocated to the same agent given that $\mathbf{p}_{i}$ and
$\mathbf{p}^{\prime}_{i}$ only differ in ranks $k$ and $k+1$, and preferences
of other agents $\mathbf{p}_{-i}$ remain unchanged. Thus, if
$x_{i,a}((\mathbf{p}_{i},m),(\mathbf{p}_{-i},m))=0$ then we also have
$x_{i,a}((\mathbf{p}^{\prime}_{i},m),(\mathbf{p}_{-i},m))=0$, establishing
Inequality (5).

Now using this, we get the desired inequality.

$\displaystyle q^{\texttt{pos}}_{i,k}$
$\displaystyle=q_{i,a}(\mathbf{p}_{i},m)$ (Using Lemma 3 and
$\mathbf{p}_{i}(k)=a$)
$\displaystyle=\frac{1}{\left(m!\right)^{n-1}}\sum_{\mathbf{p}_{-i}}x_{i,a}((\mathbf{p}_{i},m),(\mathbf{p}_{-i},m))$
(via (2))
$\displaystyle\geq\frac{1}{(m!)^{n-1}}\sum_{\mathbf{p}_{-i}}x_{i,a}((\mathbf{p}^{\prime}_{i},m),(\mathbf{p}_{-i},m))$
(via (5)) $\displaystyle=q_{i,a}(\mathbf{p}^{\prime}_{i},m)$ (via (2))
$\displaystyle=q^{\texttt{pos}}_{i,k+1}$ (Using Lemma 3 and
$\mathbf{p}^{\prime}_{i}(k+1)=a$)

∎

Using the previous two lemmas we now show that $\mathrm{RR}^{\text{pass}}$ is
BIC for neutral priors. The high-level intuition is as follows. If agent $i$
reports valuation $\mathbf{b}_{i}$ having a corresponding preference order
$\mathbf{p}_{i}=(j_{1},j_{2},\ldots,j_{m})$, then Lemma 3 implies that the
interim allocations
$q_{i,j_{1}}(\mathbf{b}_{i}),q_{i,j_{2}}(\mathbf{b}_{i}),\ldots,q_{i,j_{n}}(\mathbf{b}_{i})$
will be (a prefix of) the positional interim allocation
$\mathbf{q_{i}^{\texttt{pos}}}$, which, as per Lemma 3 is monotone,
$q^{\texttt{pos}}_{i,1}\geq\ldots\geq q^{\texttt{pos}}_{i,m}$. That is, the
interim allocations are non-increasing in the reported preference order and
are always a permutation of $\mathbf{q_{i}^{\texttt{pos}}}$. Note that, the
expected utility of agent $i$ as per her true preference $\mathbf{v}_{i}$ is
$\sum_{k=1}^{m}q_{i,j_{k}}(\mathbf{b}_{i})\cdot v_{i,j_{k}}$, which
essentially is a vector dot product of the true valuation and the interim
allocation. This dot product is maximized when the true valuations and the
interim allocations are _aligned_ (i.e., are in the same order). Given that
the interim allocation is always a permutation of
$\mathbf{q_{i}^{\texttt{pos}}}$, this alignment happens when agent $i$’s
reported preference order matches her true preference order, i.e., when agent
$i$ reports $\mathbf{v}_{i}$, establishing that $\mathrm{RR}^{\text{pass}}$ is
BIC. This intuition is formalized in the following lemma.

lemmaRRisBIC The Round-Robin${}^{\text{pass}}$ mechanism is Bayesian incentive
compatible for neutral priors.

###### Proof.

Consider any agent $i$ with a valuation $\mathbf{v}_{i}$ and some report
$\mathbf{b}_{i}$; let $(\mathbf{p}^{v}_{i},m_{i}^{v})$ and
$(\mathbf{p}^{b}_{i},m_{i}^{b})$ be the tuples corresponding to
$\mathbf{v}_{i}$ and $\mathbf{b}_{i}$ respectively. Without loss of
generality, we assume that $m_{i}^{b}=m$ because reporting
$(\mathbf{p}^{b}_{i},m)$ instead of $(\mathbf{p}^{b}_{i},m_{i}^{b})$ can only
only increase the expected utility of agent $i$: since $m\geq m_{i}^{b}$
Theorem 3 implies that, $q_{i,j}(\mathbf{p}^{b}_{i},m)\geq
q_{i,j}(\mathbf{p}^{b}_{i},m_{i}^{b})$ for all items $j\in\mathcal{M}$. Thus,
to show that $\mathrm{RR}^{\text{pass}}$ is BIC, we will show that the
expected utility of agent $i$ as per $\mathbf{v}_{i}$ when reporting
$(\mathbf{p}^{v}_{i},m_{i}^{v})$ (i.e., $\mathbf{v}_{i}$) is at least as much
as when reporting $(\mathbf{p}^{b}_{i},m)$ (i.e., $\mathbf{b}_{i}$).

_Case $\mathbf{(1)}$_: $\mathbf{p}^{v}_{i}=\mathbf{p}^{b}_{i}$. Using Theorem
3, the expected utility of agent $i$ when reporting $(\mathbf{p}^{b}_{i},m)$
is,

$\displaystyle\mathop{\mathbb{E}}\limits_{\mathbf{v}_{-i}\sim\mathcal{D}_{-i}}[u_{i}((\mathbf{p}^{b}_{i},m),\mathbf{v}_{-i})]$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}\limits_{\mathbf{v}_{-i}\sim\mathcal{D}_{-i}}[u_{i}((\mathbf{p}^{v}_{i},m),\mathbf{v}_{-i})]$
($\mathbf{p}^{v}_{i}=\mathbf{p}^{b}_{i}$) $\displaystyle=$
$\displaystyle\sum_{\ell=1}^{m}q^{\texttt{pos}}_{i,\ell}\cdot
v_{i,\mathbf{p}^{v}_{i}(\ell)}$ (Theorem 3) $\displaystyle=$
$\displaystyle\sum_{\ell=1}^{m_{i}^{v}}q^{\texttt{pos}}_{i,\ell}\cdot
v_{i,\mathbf{p}^{v}_{i}(\ell)}+\sum_{\ell=m_{i}^{v}+1}^{m}q^{\texttt{pos}}_{i,\ell}\cdot
v_{i,\mathbf{p}^{v}_{i}(\ell)}$ $\displaystyle=$
$\displaystyle\sum_{\ell=1}^{m_{i}^{v}}q^{\texttt{pos}}_{i,\ell}\cdot
v_{i,\mathbf{p}^{v}_{i}(\ell)}+\sum_{\ell=m_{i}^{v}+1}^{m}q^{\texttt{pos}}_{i,\ell}\cdot
0$ $\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}\limits_{\mathbf{v}_{-i}\sim\mathcal{D}_{-i}}[u_{i}((\mathbf{p}^{v}_{i},m_{i}^{v}),\mathbf{v}_{-i})],$
(Theorem 3)

Hence, in this case, the expected utility of reporting
$(\mathbf{p}^{v}_{i},m_{i}^{v})$ is at least as much as when reporting
$(\mathbf{p}^{b}_{i},m)$, which in turn is at least the expected utility when
reporting $(\mathbf{p}^{b}_{i},m_{i}^{b})$.

_Case $\mathbf{(2)}$_: $\mathbf{p}^{v}_{i}\neq\mathbf{p}^{b}_{i}$. Let $k$ be
the lowest position where $\mathbf{p}^{v}_{i}$ and $\mathbf{p}^{b}_{i}$ differ
such that $\mathbf{p}^{b}_{i}(k)=x$ and $\mathbf{p}^{v}_{i}(k)=y$.
Additionally, let $k^{\prime}$ be such that
$\mathbf{p}^{b}_{i}(k^{\prime})=y$; note that $k^{\prime}>k$ by the definition
of $k$.

We will first show that agent $i$ can weakly increase her expected utility by
reporting the tuple $(\mathbf{p}^{\prime}_{i},m)$, instead of
$(\mathbf{p}^{b}_{i},m)$, where ordering $\mathbf{p}^{\prime}_{i}$ is
constructed by swapping the position of $x$ and $y$ in $\mathbf{p}^{b}_{i}$.
We will then apply this swapping argument repeatedly to conclude the proof.
Towards this, note that $v_{i,y}\geq v_{i,x}$ since the preference order
$\mathbf{p}_{i}$ is based on the true valuations, and additionally by Theorem
3, we have $q^{\texttt{pos}}_{i,k}\geq q^{\texttt{pos}}_{i,k^{\prime}}$.
Together, these two inequalities imply that $q^{\texttt{pos}}_{i,k}\cdot
v_{i,y}+q^{\texttt{pos}}_{i,k^{\prime}}\cdot v_{i,x}\geq
q^{\texttt{pos}}_{i,k}\cdot v_{i,x}+q^{\texttt{pos}}_{i,k^{\prime}}\cdot
v_{i,y}$. Given this, the expected utility of reporting
$(\mathbf{p}^{\prime}_{i},m)$ can be written as:

$\displaystyle\mathop{\mathbb{E}}\limits_{\mathbf{v}_{-i}\sim\mathcal{D}_{-i}}[u_{i}((\mathbf{p}^{\prime}_{i},m),\mathbf{v}_{-i})]$
$\displaystyle=$ $\displaystyle\ q^{\texttt{pos}}_{i,k}\cdot
v_{i,y}+q^{\texttt{pos}}_{i,k^{\prime}}\cdot
v_{i,x}+\sum_{\ell\notin\\{k,k^{\prime}\\}}q^{\texttt{pos}}_{i,\ell}\cdot
v_{i,\mathbf{p}^{b}_{i}(\ell)}$ (Theorem 3) $\displaystyle\geq$
$\displaystyle\ q^{\texttt{pos}}_{i,k}\cdot
v_{i,x}+q^{\texttt{pos}}_{i,k^{\prime}}\cdot
v_{i,y}+\sum_{\ell\notin\\{k,k^{\prime}\\}}q^{\texttt{pos}}_{i,\ell}\cdot
v_{i,\mathbf{p}^{b}_{i}(\ell)}$ $\displaystyle=$
$\displaystyle\sum_{\ell=1}^{m}q^{\texttt{pos}}_{i,\ell}\cdot
v_{i,\mathbf{p}^{b}_{i}(\ell)}$ ($\mathbf{p}^{b}_{i}(k)=x$ and
$\mathbf{p}^{b}_{i}(k^{\prime})=y$) $\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}\limits_{\mathbf{v}_{-i}\sim\mathcal{D}_{-i}}[u_{i}((\mathbf{p}^{b}_{i},m),\mathbf{v}_{-i})].$
(Theorem 3)

Thus, this “swapping” step used to obtain $\mathbf{p}^{\prime}_{i}$ from
$\mathbf{p}^{b}_{i}$ weakly increases the expected utility. Additionally, by
definition, the length of the longest common prefix of
$\mathbf{p}^{\prime}_{i}$ and $\mathbf{p}_{i}^{v}$ is strictly greater than
that of $\mathbf{p}^{b}_{i}$ and $\mathbf{p}_{i}^{v}$, i.e.,
$\mathbf{p}^{\prime}_{i}$ is closer to $\mathbf{p}_{i}^{v}$ than
$\mathbf{p}^{b}_{i}$. Therefore, by repeatedly performing these swaps till
$\mathbf{p}^{\prime}_{i}$ becomes $\mathbf{p}_{i}^{v}$, we get that the
expected utility of reporting $(\mathbf{p}_{i}^{v},m)$ is at least as when
reporting $(\mathbf{p}^{b}_{i},m)$. Following the arguments of Case $(1)$, we
also know that the expected utility of reporting
$(\mathbf{p}_{i}^{v},m^{v}_{i})$ is at least as when reporting
$(\mathbf{p}^{v}_{i},m)$. Hence, in this case, we also get that the expected
utility of reporting $(\mathbf{p}^{v}_{i},m_{i}^{v})$ is at least as much as
when reporting $(\mathbf{p}^{b}_{i},m)$. That is, reporting $\mathbf{v}_{i}$
is always better than reporting any other $\mathbf{b}_{i}$. This concludes the
proof. ∎

The following lemma proves that $\mathrm{RR}^{\text{pass}}$ also satisfies
SD+efficiency and $\mathrm{EF}1$, its proof can be found in Appendix B.
lemmaRRsdpoplus The Round-Robin${}^{\text{pass}}$ mechanism outputs
SD+efficient and $\mathrm{EF}1$ allocations. Combined, Lemmas 3 and 3 imply
Theorem 3.

###  3.3 Welfare functions and BIC

In this section, we prove that a large family of “welfare maximization”
mechanisms is not Bayesian incentive compatible.

A _welfare function_ $f:\mathbb{R}^{n}_{\geq 0}\to\mathbb{R}$ is a function
that, given the utilities of agents
$u_{1}(\mathbf{x}),\ldots,u_{n}(\mathbf{x})$ in allocation $\mathbf{x}$,
outputs $f(u_{1}(\mathbf{x}),\ldots,u_{n}(\mathbf{x}))$, that represents the
collective welfare of all the agents in allocation $\mathbf{x}$. An allocation
$\mathbf{x}$ is said to maximize $f$ if for all other feasible allocations
$\mathbf{y}$ we have $f(u_{1}(\mathbf{x}),\ldots,u_{n}(\mathbf{x}))\geq
f(u_{1}(\mathbf{y}),\ldots,u_{n}(\mathbf{y}))$.

######  Definition 3 (Anonymous).

A welfare function $f$ is called _anonymous_ iff
$f(x_{1},x_{2},\ldots,x_{n})=f(x_{\pi_{1}},x_{\pi_{2}},\ldots,x_{\pi_{n}})$
for any permutation $\pi:[n]\to[n]$.

######  Definition 4 (Strictly monotone).

A welfare function $f$ is _strictly monotone_ iff
$f(x_{1},x_{2},\ldots,x_{n})>f(y_{1},y_{2},\ldots,y_{n})$ whenever we have
$x_{i}\geq y_{i}$ for all $i\in[n]$ and $x_{j}>y_{j}$ for some $j\in[n]$.

######  Definition 5 (The Pigou-Dalton principle).

The Pigou-Dalton Principle (PDP) states that a welfare function should weakly
prefer a profile that reduces the inequality between two agents, assuming that
the utilities of all other agents stay unchanged. Formally, a welfare function
$f$ satisfies PDP iff for any two vectors $(x_{1},\ldots,x_{n})$ and
$(y_{1},\ldots,y_{n})$ such that there are two distinct $i,j\in[n]$ satisfying
$(i)$ $x_{i}+x_{j}=y_{i}+y_{j}$, $(ii)$ $x_{i}>x_{j}$, $(iii)$
$x_{i}>y_{i}>x_{j}$ (equivalently $x_{i}>y_{j}>x_{j}$), and $(iv)$
$x_{k}=y_{k}$ for all $k\in[n]\setminus\\{i,j\\}$, we have
$f(x_{1},x_{2},\ldots,x_{n})\leq f(y_{1},y_{2},\ldots,y_{n})$.

Welfare functions satisfying anonymity, strict monotonicity, and the PDP
constitute a broad set of functions that include, e.g., the class of all the
$p$-mean welfare functions101010For a given $p\in\mathbb{R}_{\geq 0}$, the
$p$-mean welfare function is defined as
$f_{p}(x_{1},x_{,}\ldots,x_{n})\coloneqq\big{(}\frac{1}{n}\sum_{i=1}^{n}x_{i}^{p}\big{)}^{1/p}$.
Notably, $f_{p}$ captures utilitarian welfare if $p=1$, Nash welfare if $p\to
0$, and egalitarian welfare if $p\to-\infty$. for $p\leq 1$ [Mou04]. The class
of $p$-mean welfare functions, in turn, includes Nash social welfare,
egalitarian social welfare, utilitarian social welfare, and the leximin
criterion. In Theorem 5, we show that, for any deterministic (or randomized)
mechanism that outputs allocations that (ex-post) maximize such a welfare
function, $f$, is not BIC. We prove this fact for a very simple neutral prior
distribution according to which each agent $i$’s values are drawn uniformly
from the $m-1$-simplex, i.e.,
$\mathbf{v}_{i}=(v_{1},v_{2},\ldots,v_{m})\sim\Delta^{m-1}$. Notably, Theorem
3 also holds for this neutral prior supported over normalized
valuations.111111It is necessary to consider normalized valuations when
studying welfare objectives that aren’t scale-free, for e.g. social welfare.
In particular, if the valuations aren’t normalized, then agents could
(mis)report large values for all the items, thereby forcing the mechanism to
allocate all the items to them.

theoremBICWelfare There is no deterministic (or randomized) mechanism that is
Bayesian incentive compatible for the uniform prior and which always outputs
allocations that ex-post maximize welfare function $f$, where $f$ is any
anonymous, strictly monotone function satisfying the Pigou-Dalton principle.

###### Proof.

We will show that this negative result holds even for the simple setting of
$n=2$ agents and $m=2$ items. Let $\mathbf{x}$ be any deterministic or
randomized BIC mechanism that (ex-post) outputs allocations that maximize $f$.
To arrive at a contradiction, we will show that show that if agent $1$ has a
true normalized preference $\mathbf{v}_{1}=(x,1-x)$ such that $x>1/2$, then it
is better for the agent to report $\mathbf{b}_{1}=(x+\epsilon,1-x-\epsilon)$
for any $\epsilon\in(0,1-x]$. This would show that $\mathbf{x}$ is not BIC
since truthful reporting is not the best strategy for agent $1$. More
specifically, we will show that if agent $1$ having true preference
$\mathbf{v}_{1}=(x,1-x)$ reports $\mathbf{b}_{1}=(b,1-b)$,where $b>x$, then
her expected utility
$\mathbb{E}_{\mathbf{v}_{2}\sim\Delta_{2}}[u_{1}(\mathbf{x}(\mathbf{b}_{1},\mathbf{v}_{2})]=xb+(1-x)(1-b)$
for any mechanism $\mathbf{x}$. Note that this will imply that
$\mathbb{E}_{\mathbf{v}_{2}\sim\Delta_{2}}[u_{1}(\mathbf{x}(\mathbf{b}_{1},\mathbf{v}_{2})]>\mathbb{E}_{\mathbf{v}_{2}\sim\Delta_{2}}[u_{1}(\mathbf{x}(\mathbf{v}_{1},\mathbf{v}_{2})]$
since

$\displaystyle\mathop{\mathbb{E}}_{\mathbf{v}_{2}\sim\Delta_{2}}[u_{1}(\mathbf{x}(\mathbf{b}_{1},\mathbf{v}_{2})]-\mathop{\mathbb{E}}_{\mathbf{v}_{2}\sim\Delta_{2}}[u_{1}(\mathbf{x}(\mathbf{v}_{1},\mathbf{v}_{2})]$
$\displaystyle=\big{(}x(x+\epsilon)+(1-x)(1-x-\epsilon)\big{)}-\big{(}x^{2}+(1-x)^{2}\big{)}$
$\displaystyle=\epsilon x-\epsilon(1-x)=\epsilon(2x-1)>0,$ (6)

the final inequality follows from the fact that $x>1/2$ and $\epsilon>0$. This
will imply that $\mathbf{x}$ is not BIC, giving us the desired contradiction.
To conclude the proof, we will show that
$\mathbb{E}_{\mathbf{v}_{2}\sim\Delta_{2}}[u_{1}(\mathbf{x}(\mathbf{b}_{1},\mathbf{v}_{2})]=xb+(1-x)(1-b)$.
Consider $\mathbf{v}_{2}=(y,1-y)\sim\Delta_{2}$. First, will show that if
$y>b$, then the unique allocation that maximizes $f$ for the report
$(\mathbf{b}_{1},\mathbf{v}_{1})$ is $\\{\\{2\\},\\{1\\}\\}$. Otherwise, if
$y<b$, then the unique allocation that maximizes $f$ is
$\\{\\{1\\},\\{2\\}\\}$. Suppose $y>b$. Since there are two items and two
agents, there are four possible allocations having the utility profiles
$P=\\{(1,0),(0,1),(b,1-y),(1-b,y)\\}$. Next we will show that
$f(1-b,y)>f(p,q)$, for any $(p,q)\in P\setminus\\{(1-b,y)\\}$, implying the
allocation $\mathbf{x}=\\{\\{2\\},\\{1\\}\\}$ is the unique allocation that
maximizes $f$. Towards this, note that $f(1-b,y)=f(y,1-b)<f(b,1-y)$; the first
equality follows from the fact that $f$ is symmetric and second from the fact
that $f$ is strictly monotone and $b>y$ (thereby $1-y>1-b$). Additionally,
$f(1,0)=f(0,1)<f(b,1-b)<f(b,1-y)$; here the first, second, and the third step
follow respectively from the fact that $f$ is symmetric, satisfies PDP, and
strictly monotone along with the fact that $1-y>1-b$.

Thus, if $y>b$ we have $f(1-b,y)>f(p,q)$, for any $(p,q)\in
P\setminus\\{(1-b,y)\\}$, which implies that the allocation
$\mathbf{x}=\\{\\{2\\},\\{1\\}\\}$ is the unique allocation that maximizes
$f$. Note that using the same argument, we can get that if $y<b$, then the
unique allocation that maximizes $f$ is $\mathbf{x}=\\{\\{1\\},\\{2\\}\\}$.

Finally, we will use this to prove that
$\mathbb{E}_{\mathbf{v}_{2}\sim\Delta_{2}}[u_{1}(\mathbf{x}(\mathbf{b}_{1},\mathbf{v}_{2}))]=xb+(1-x)(1-b)$.
Note that if $\mathbf{v}_{2}=(y,1-y)\sim\Delta_{2}$ then the distribution of
$y$ is uniform, i.e., $y\in\mathcal{U}[0,1]$. Therefore, $y<b$ with
probability $b$ and $y>b$ with probability $1-b$. Combining this with the
aforementioned observation we have that with probability $b$ the unique $f$
maximizing allocation is $\mathbf{x}=\\{\\{1\\},\\{2\\}\\}$ wherein agent
$1$’s true utility is $x$, and with probability $1-b$ the unique $f$
maximizing allocation is $\mathbf{x}=\\{\\{2\\},\\{1\\}\\}$ wherein agent
$1$’s true utility is $1-x$. Since these allocations are unique, any
randomized or deterministic mechanism $\mathbf{x}$ must (ex-post) output them.
Therefore,
$\mathbb{E}_{\mathbf{v}_{2}\sim\Delta_{2}}[u_{1}(\mathbf{x}(\mathbf{b}_{1},\mathbf{v}_{2})]=xb+(1-x)(1-b)$,
this concludes the proof. ∎

So far we have been focusing on deterministic allocations, i.e.,
$x_{i,j}\in\\{0,1\\}$ for all $i$, $j$. A _randomized_ allocation is a
distribution over a set of deterministic allocations, where $x_{i,j}\in[0,1]$
denotes the probability item $j$ is assigned to agent $i$ received under the
allocation. We say that an allocation is _ex-post fPO_ if no randomized
allocation Pareto dominates it. A slightly modified version of the above proof
can be used to show the non-existence of deterministic (or randomized)
mechanisms that are Bayesian incentive compatible and output allocations that
are ex-post $\mathrm{fPO}$ and EF1. In fact, we can rule out BIC mechanisms
that output $\mathrm{fPO}$ allocations that satisfy a fairness criterion we
call _fulfillment_ , that is much weaker than $\mathrm{EF}1$. Specifically, an
allocation $\mathbf{x}$ is fulfilling iff the following condition is satisfied
for all agents $i\in\mathcal{N}$: if $i$ has at least $n$ items that she
values positively, then agent $i$ gets a bundle of positive utility. It is
easy to see that an $\mathrm{EF}1$ allocation must be fulfilling. Formally,
this result is stated as Theorem 5.

theoremBICfulfilling There is no deterministic (or randomized) Bayesian
incentive compatible mechanism that outputs $\mathrm{fPO}$ allocations that
are fulfilling.

###### Proof.

Structurally, the proof is similar to the proof of Theorem 5. For the sake of
brevity, we will only describe the points where the proof differs. In proof of
Theorem 5, we showed that allocations that maximize $f$ are unique if $y>b$ or
$y<b$. Similarly, here we will show that if $y<b$, then
$\mathbf{x}=\\{\\{1\\},\\{2\\}\\}$ is the unique allocation that is
$\mathrm{fPO}$ and fulfilling, and if $y>b$, then
$\mathbf{x}=\\{\\{2\\},\\{1\\}\\}$ is the unique such allocation. Proving this
would imply that for any randomized or deterministic mechanism $\mathbf{x}$
that outputs $\mathrm{fPO}$ and fulfilling allocations,
$\mathbb{E}_{\mathbf{v}_{2}\sim\Delta_{2}}[u_{1}(\mathbf{x}(\mathbf{b}_{1},\mathbf{v}_{2})]=xb+(1-x)(1-b)$
where the bid and the true value of agent $1$ is $\mathbf{b}_{1}=(b,1-b)$ and
$\mathbf{v}_{1}=(v,1-v)$ respectively. Finally, together with inequality (6)
this will imply that $\mathbf{x}$ is not BIC and would conclude the proof.

Now consider the case when $y<b$; since $y\sim\mathcal{U}[0,1]$ almost surely
$y>0$, thus, $0<y<b$. Any fulfilling allocation for this instance must give
one item to each of the agents since both agents value $n=2$ items positively.
These allocations have utility profiles $(b,1-y)$ and $(1-b,y)$. Among these
two profiles, $(1-b,y)$ is not $\mathrm{fPO}$ because we can show that it is
Pareto dominated by a linear combination of the profiles $(0,1)$ and
$(b,1-y)$. Specifically, consider the following linear combination,
$(a,b)=(1-\alpha)(0,1)+\alpha(b,1-y)$ where $\alpha=\frac{1-y}{y}$. On
simplifying we get, $(a,b)=(\frac{b(1-y)}{y},1-\alpha
y)=(\frac{b(1-y)}{y},y)$. The profile $(a,b)$ Pareto dominates $(1-b,y)$
because $b=y$ and $a=\frac{b(1-y)}{y}>1-b$ where the final inequality follows
from the fact that $b>y$. Therefore, if $y<b$ then allocation
$\mathbf{x}=\\{\\{1\\},\\{2\\}\\}$ having utility profile $(b,1-y)$ is the
only $\mathrm{fPO}$ and fulfilling allocation.

If $y>b$, then we can show that the profile $(b,1-y)$ is not $\mathrm{fPO}$,
thereby making $(1-b,y)$ the only $\mathrm{fPO}$ and fulfilling profile.
Towards this consider the following linear combination of profiles:
$(a^{\prime},b^{\prime})=\beta(1-b,y)+(1-\beta)(1,0)$ for
$\beta=\frac{1-y}{y}$. On simplifying we get,
$(a^{\prime},b^{\prime})=(1-\beta b,1-y)=(\frac{y-b+by}{y},1-y)$; this Pareto
dominates $(b,1-y)$ because $\frac{y-b+by}{y}>b$ which is implied by $y>b$.
Hence, if $y>b$, then the allocation $\mathbf{x}=\\{\\{2\\},\\{1\\}\\}$ having
utility profile $(1-b,y)$ is the only $\mathrm{fPO}$ and fulfilling
allocation. This concludes the proof. ∎

##  4 Allocating Divisible Goods: Cake Cutting

Recently, [Tao22] proved a strong incompatibility between fairness and
incentives in the cake-cutting problem: no deterministic DSIC cake-cutting
mechanism can always output proportional allocations (see Theorem 4), for the
case of $n=2$ agents and piecewise constant density functions.

######  Theorem 4 ([Tao22]).

There is no deterministic, DSIC, and proportional cake-cutting mechanism for
piecewise-constant valuations, even for $n=2$ agents.

#### The Bayesian Setting.

The _private_ piecewise-constant valuation function $f^{*}_{i}$ of each agent
$i$ is drawn from a _neutral_ prior distribution $\mathcal{D}_{i}$. We say a
prior distribution $\mathcal{D}$ is neutral, iff for all integers $k>1$, and
disjoint pieces of cake $X_{1},X_{2},\ldots,X_{k}$ satisfying
$|X_{1}|=|X_{2}|=\ldots=|X_{k}|$, we have
$\mathop{\Pr}\limits_{f^{*}\sim\mathcal{D}}[j=\arg\max_{i=1}^{k}f^{*}(X_{i})]=1/k.$

Intuitively, neutral priors represent a distribution of density functions such
that the probability of an agent preferring an interval over another same-
length interval is the same, i.e., same-length intervals are _equivalent_ in
expectation.

Towards bypassing Theorem 4, we provide a deterministic mechanism (Mechanism
1), which we refer to as IncrementalAccommodation (IA), and we show that IA is
Bayesian incentive compatible for neutral priors and it always outputs
proportional allocations (Theorem 5). Moreover, IA can be executed in
polynomial time for piecewise constant density functions.

######  Theorem 5.

The IncrementalAccommodation mechanism is Bayesian incentive compatible for
neutral product distributions, and always outputs proportional allocations.

At a high level, given reported preferences $f_{1},f_{2},\ldots,f_{n}$, IA
operates as follows. Initially, the entire cake $[0,1]$ is allocated to agent
$1$. Other agents arrive one-by-one following the order $2,3,\ldots,n$. Before
the arrival of agent $i$, the entire cake is always allocated among the agents
$\\{1,2,\ldots,i-1\\}$; this allocation is denoted by
$X_{1},X_{2},\ldots,X_{i-1}$. When agent $i$ arrives, each agent
$j\in\\{1,2,\ldots,i-1\\}$ cuts their piece of cake, $X_{j}$, into $i$ pieces,
$C_{j}^{1},C_{j}^{2},\ldots,C_{j}^{i}$ using the SplitEqualoperation
(Subroutine 2) described below.

SplitEqual operation. Given a piece of cake $X$, a function $f$, and a number
$k$, the SplitEqual operation partitions $X$ into pieces
$C^{1},C^{2},\ldots,C^{k}$ having _equal sizes_ and _equal values_ , i.e.,
$|C^{1}|=|C^{2}|=\ldots=|C^{k}|$ and $f(C^{1})=f(C^{2})=\ldots=f(C^{k})$. Note
that this operation can always be performed given “any” density function $f$
and $k>1$ since the existence of such a split is directly implied by the
existence of a _perfect partition_.121212[Alo87] proved that given arbitrary
density functions $y_{1},y_{2},\ldots,y_{n}$, there always exists a partition
$X_{1},X_{2},\ldots,X_{n}$ of $[0,1]$ such that $y_{i}(X_{j})=1/n$ for all
$i,j\in[n]$. Specifically, if we consider $k$ density functions where the
first function, $y_{1}(X)=|X|$ while the other $k-1$ density functions are
$f$, then a perfect partition $C^{1},C^{2},\ldots,C^{i}$ of $X$ — which always
exists — will satisfy the two required conditions of equal value (since
$f(C^{r})=f(C^{s})$ for all $r,s\in[i]$) and equal size (since
$|C^{r}|=y_{1}(C^{r})=y_{1}(C^{s})=|C^{s}|$ for all $r,s\in[k]$). The
SplitEqual operation can be efficiently performed for piecewise constant
valuations by simply dividing each subinterval within $X$ having a constant-
value w.r.t. $f$ into $k$ pieces of equal size; the equal value condition will
follow from the fact the subinterval being divided has a constant-value.
Furthermore, it is known that a perfect partition can be computed efficiently
for the significantly more general class of piecewise linear valuations
[CLPP13], allowing for efficient execution of IA for this class of valuations
as well.

After performing the SplitEqual operation, each agent $j\in\\{1,\dots,i-1\\}$
offers agent $i$ one piece amongst $C_{j}^{1},C_{j}^{2},\ldots,C_{j}^{i}$, and
agent $i$ picks the one that maximizes her value, as per the reported density
function $f_{i}$. The resulting allocation, after the arrival of the
$n^{\text{th}}$ agent, is then returned as the final allocation. In Lemma 2,
we show that IA is BIC for neutral priors. In Lemma 2, we show that IA always
outputs proportional allocations. The proof of Lemma 2 resembles a proof of
[Fin64] wherein proportionality is established for a similar recursive cake-
cutting algorithm.

1 Input: $(f_{1},\dots,f_{n})$, the reported valuations of the agents

2 set $X_{1}\leftarrow[0,1]$, and $X_{i}\leftarrow\emptyset$ for all
$i\in\\{2,\dots,n\\}$

3 for  _ $i\leftarrow 2,3,\dots,n$_ do

4 for  _$j\leftarrow 1,2,\dots,i-1$_ do

5 set $(C^{1}_{j},C^{2}_{j},\dots,C^{i}_{j})\leftarrow$
SplitEqual($X_{j},f_{j},i$)

6 let $k^{*}\leftarrow\operatorname*{arg\,max}_{k}f_{i}(C_{j}^{k})$

7 set $X_{i}\leftarrow X_{i}\cup C_{j}^{k^{*}}$

8 set $X_{j}\leftarrow X_{j}\setminus C_{j}^{k^{*}}$

return _$(X_{1},X_{2},\dots,X_{n})$_

Mechanism 1 IncrementalAccommodation

1 Input: $(X,f,k)$ a set of intervals $X$, valuation function $f$, and number
$k>1$

Partition $X$ into $k$ subintervals $C^{1},C^{2}\dots,C^{k}$ such that the
following two conditions are true:

  1. (1)

$|C^{i}|=|C^{j}|$ for all $i,j\in[k]$

  2. (2)

$f(C_{i})=f(C_{j})$ for all $i,j\in[k]$

return _$(C^{1},C^{2},\dots,C^{k})$_

Subroutine 2 SplitEqual

lemmaexpectedUtilLemma Let $X^{\prime}_{j}$, $X_{j}$ be the pieces of cake
that agent $j$ is allocated at the beginning and the end of iteration $t$,
respectively, for some $1\leq j<t\leq n$.131313Noting that $X_{j}$ is a random
variable which depends on the valuation function of agent $t$, $f^{*}_{t}$,
drawn from $\mathcal{D}$. Then, for any valuation function $\hat{f}$, the
expected value of $\hat{f}(X_{j})$ is equal to
$\frac{t-1}{t}\cdot\hat{f}(X^{\prime}_{j})$, where the expectation is over the
randomness of the valuation function of agent $t$, $f^{*}_{t}$, drawn from a
neutral prior $\mathcal{D}$. Formally,

$\mathop{\mathbb{E}}\limits_{f^{*}_{t}\sim\mathcal{D}}[\hat{f}(X_{j})]=\frac{t-1}{t}\cdot\hat{f}(X^{\prime}_{j}).$

###### Proof.

In iteration $t$, via the split-equal subroutine, the piece $X^{\prime}_{j}$
is partitioned into disjoint intervals $C_{j}^{1},C_{j}^{2},\dots,C_{j}^{t}$.
Then agent $t$, having a valuation function $f^{*}_{t}\sim\mathcal{D}_{t}$
picks her favorite piece amongst $C_{j}^{1},C_{j}^{2},\ldots,C_{j}^{t}$. For
each $k\in[t]$, define $a_{k}$ to be the indicator random variable such that
$a_{k}=1$ if the piece $C_{j}^{k}$ is picked by agent $t$, and $0$ otherwise.
If agent $t$ picks the piece $C_{j}^{k}$ in iteration $t$, then the piece of
cake agent $j$ has at the end of iteration satisfies
$X_{j}=X^{\prime}_{j}\setminus C_{j}^{k}$. This allows us to express the
expected value $\mathbb{E}_{f^{*}_{t}\sim\mathcal{D}_{t}}[\hat{f}(X_{j})]$ as,

$\displaystyle\mathop{\mathbb{E}}\limits_{f^{*}_{t}\sim\mathcal{D}_{t}}[\hat{f}(X_{j})]$
$\displaystyle=\mathop{\mathbb{E}}\limits_{f^{*}_{t}\sim\mathcal{D}_{t}}\left[\sum_{k=1}^{t}a_{k}\Big{(}\hat{f}(X^{\prime}_{j})-\hat{f}(C_{j}^{k})\Big{)}\right]$
$\displaystyle=\hat{f}(X^{\prime}_{j})\mathop{\mathbb{E}}\limits_{f^{*}_{t}\sim\mathcal{D}_{t}}\left[\sum_{k=1}^{t}a_{k}\right]-\mathop{\mathbb{E}}\limits_{f^{*}_{t}\sim\mathcal{D}_{t}}\left[\sum_{k=1}^{t}a_{k}\hat{f}(C_{j}^{k})\right],$

where the final inequality follows from the fact that
$\hat{f}(X^{\prime}_{j})$ and $\hat{f}(C_{j}^{k})$ are independent of $f_{t}$.
To obtain the desired equality we will now use the following two observations.
First, the prior $\mathcal{D}_{t}$ is neutral, i.e.,
$\mathbb{E}_{f_{t}\sim\mathcal{D}_{t}}[X_{k}]=1/t$ because the $t$ intervals
$C_{j}^{1},C_{j}^{2},\dots,C_{j}^{t}$ have equal sizes,
$|C_{j}^{1}|=|C_{j}^{2}|=\dots=|C_{j}^{t}|$. Second, $\sum_{k=1}^{t}X_{k}=1$
since agent $t$ always picks a piece from agent $j$. Using these two
observations we get,

$\displaystyle\mathop{\mathbb{E}}\limits_{f_{t}\sim\mathcal{D}_{t}}[\hat{f}(X_{j})]$
$\displaystyle=\hat{f}(X^{\prime}_{j})\mathop{\mathbb{E}}\limits_{f^{*}_{t}\sim\mathcal{D}_{t}}\left[\sum_{k=1}^{t}a_{k}\right]-\mathop{\mathbb{E}}\limits_{f^{*}_{t}\sim\mathcal{D}_{t}}\left[\sum_{k=1}^{t}a_{k}\hat{f}(C_{j}^{k})\right]$
$\displaystyle=\hat{f}(X^{\prime}_{j})\cdot
1-\sum_{k=1}^{t}\frac{1}{t}\hat{f}(C_{j}^{k})$
$\displaystyle=\hat{f}(X^{\prime}_{j})-\frac{1}{t}\hat{f}(X^{\prime}_{j})$
($\cup_{k=1}^{t}C_{j}^{k}=X^{\prime}_{j}$)
$\displaystyle=\frac{t-1}{t}\cdot\hat{f}(X^{\prime}_{j}).\qed$

Now using Lemma 2, we will show that IA is Bayesian incentive compatible for
neutral priors. At a high level, we show that if agent $i$ has piece
$X^{i}_{i}$ after her arrival, then, eventually, in the final allocation, her
utility, as per her true valuation $f^{*}_{i}$, will be proportional to
$f^{*}_{i}(X^{i}_{i})$. Specifically, let $X^{n}_{i}$ be the piece that agent
$i$ has at the end of the mechanism’s execution. Through repeated applications
of Lemma 2 we prove that $f^{*}_{i}(X_{i}^{n})=\frac{i}{n}\cdot
f^{*}_{i}(X^{i}_{i})$ for any reported valuation function $f_{i}$. Therefore,
it suffices to prove that truthfully reporting $f^{*}_{i}$ maximizes
$f^{*}_{i}(X^{i}_{i})$. lemmacakecuttingBICLemma The IncrementalAccommodation
is Bayesian incentive compatible with respect to product distributions that
are neutral.

###### Proof.

Fixing an agent $i<n$, we will show that IA is BIC wrt neutral prior
$\times_{j=1}^{n}\mathcal{D}_{j}$ for agent $i$; for agent $n$, the mechanism
is trivially DSIC. Let the true valuation of agent $i$ be $f^{*}_{i}$ and let
her reported valuation be $f_{i}$. Denote by $X_{i}^{t}$ the piece of cake
agent $i$ has at the end of iteration $t$; for $t=1$, define $X_{i}^{1}=[0,1]$
for $i=1$, and $X_{i}^{1}=\emptyset$ otherwise. By definition of our
mechanism, we have $X_{i}^{t}=\emptyset$ for $t<i$. Additionally, note that
the reported function $f_{i}$ has no influence on the execution of the
mechanism prior to the arrival of agent $i$: agent $i$, using her report
$f_{i}$, cannot change the allocation
$X_{1}^{i-1},X_{2}^{i-1},\ldots,X_{n}^{i-1}$.

In the subsequent analysis, we will show that reporting $f^{*}_{i}$ is at
least as good as reporting any $f_{i}$ for agent $i$ even if we fix the
valuations of agents in $[i-1]$, i.e., IA is BIC for agent $i$ conditioned on
valuations $f_{1},f_{2},\ldots,f_{i-1}$. Formally, for any fixed true
valuation functions $f^{*}_{1},f^{*}_{2},\ldots,f^{*}_{i-1}$,

$\displaystyle\mathop{\mathbb{E}}\limits_{f^{*}_{i+1},f^{*}_{i+2},\ldots,f^{*}_{n}}[u_{i}(\text{IA}(f^{*}_{i},\mathbf{f}^{*}_{-i})]\geq\mathop{\mathbb{E}}\limits_{f^{*}_{i+1},f^{*}_{i+2},\ldots,f^{*}_{n}}[u_{i}(\text{IA}(f_{i},\mathbf{f}^{*}_{-i})].$
(7)

Note that the above inequality implies that IA is BIC for agent $i$ because
taking an expectation over
$f^{*}_{1}\sim\mathcal{D}_{1},f^{*}_{2}\sim\mathcal{D}_{2},\ldots,f^{*}_{i-1}\sim\mathcal{D}_{i-1}$
on both sides of the above inequality gives us

$\displaystyle\mathop{\mathbb{E}}\limits_{\mathbf{f}^{*}_{-i}\sim\mathcal{D}_{-i}}[u_{i}(\text{IA}(f^{*}_{i},\mathbf{f}^{*}_{-i})]\geq\mathop{\mathbb{E}}\limits_{\mathbf{f}^{*}_{-i}\sim\mathcal{D}_{-i}}[u_{i}(\text{IA}(f_{i},\mathbf{f}^{*}_{-i})].$

To complete the proof, we will now prove inequality (7). First, we will show
that, for any fixed $f^{*}_{1},f^{*}_{2},\ldots,f^{*}_{i-1}$ and report of
agent $i$, $f_{i}$, we will have

$\displaystyle\mathop{\mathbb{E}}\limits_{f^{*}_{i+1},f^{*}_{i+2},\ldots,f^{*}_{n}}[f^{*}_{i}(X_{i}^{n})]=\frac{i}{n}\cdot
f^{*}_{i}(X^{i}_{i}).$ (8)

Consider the following equality,
$\mathop{\mathbb{E}}\limits_{f^{*}_{n}}[f^{*}_{i}(X_{i}^{n})]=\frac{n-1}{n}f^{*}_{i}(X_{i}^{n-1})$,
implied by Lemma 2,

To prove equation (8), starting from the above equality, we will repeatedly
take expectation over $f^{*}_{j}\sim\mathcal{D}_{j}$ over both sides and we
will invoke Lemma 2 for agent $i$ and iteration $j$, beginning from $j=n-1$
down to $j=i+1$. Performing this sequence of operations gives us the following
chain of equalities, leading to equation (8),

$\displaystyle\mathop{\mathbb{E}}\limits_{f^{*}_{n}\sim\mathcal{D}_{n}}$
$\displaystyle[f^{*}_{i}(X_{i}^{n})]=\frac{n-1}{n}f^{*}_{i}(X_{i}^{n-1})$
$\displaystyle\implies\mathop{\mathbb{E}}\limits_{f^{*}_{n-1},f^{*}_{n}}$
$\displaystyle[f^{*}_{i}(X_{i}^{n})]=\frac{n-1}{n}\mathop{\mathbb{E}}\limits_{f^{*}_{n-1}}[f^{*}_{i}(X_{i}^{n-1})]=\frac{n-1}{n}\cdot\frac{n-2}{n-1}f^{*}_{i}(X_{i}^{n-2})$
(via Lemma 2) $\displaystyle\;\dots$
$\displaystyle\implies\mathop{\mathbb{E}}\limits_{f^{*}_{i+1},\ldots,f^{*}_{n}}$
$\displaystyle[f^{*}_{i}(X_{i}^{n})]=\frac{n-1}{n}\cdot\frac{n-2}{n-1}\cdots\frac{i-1}{i}f^{*}_{i}(X^{i}_{i})=\frac{i}{n}f^{*}_{i}(X^{i}_{i}).$
(via Lemma 2)

Finally, using equation (8) we will prove inequality (7). For fixed
$f_{1},f_{2},\ldots,f_{i-1}$, if agent $i$ reports $f_{i}$, then the piece
$X^{i}_{i}=\cup_{j=1}^{i-1}C_{j}^{k_{j}}$ where $C_{j}^{k_{j}}$ is the piece
that agent $i$ picked from agent $j$, i.e., we have
$k_{j}\in\arg\max_{k=1}^{i}f_{i}(C_{j}^{k})$. Thus,the mechanism picks the
pieces $X^{i}_{i}$ that maximize value wrt the reported value $f_{i}$.
However, given the pieces picked by her, equality (8) implies that the final
expected utility she derives is directly proportional to
$f^{*}_{i}(X^{i}_{i})$, her true value for $X_{i}^{i}$. Therefore, the final
expected utility of agent $i$ is maximized when $f_{i}=f^{*}_{i}$,i.e., agent
$i$ reports truthfully. We therefore have:

$\mathop{\mathbb{E}}\limits_{f^{*}_{i+1},f^{*}_{i+2},\ldots,f^{*}_{n}}[u_{i}(\text{IA}(f^{*}_{i},\mathbf{f}^{*}_{-i})]\geq\mathop{\mathbb{E}}\limits_{f^{*}_{i+1},f^{*}_{i+2},\ldots,f^{*}_{n}}[u_{i}(\text{IA}(f^{*}_{i},\mathbf{f}^{*}_{-i})].\qed$

The following lemma proves that IA outputs proportional allocations, its proof
appear in Appendix D.

lemmaIAprop The IncrementalAccommodation mechanism outputs proportional
allocations.

Combining Lemmas 2 and 2 implies Theorem 5.

## Acknowledgements

Alexandros Psomas and Paritosh Verma are supported in part by the NSF CAREER
award CCF-2144208, a Google Research Scholar Award, and a Google AI for Social
Good award. Vasilis Gkatzelis and Xizhi Tan are partially supported by the NSF
CAREER award CCF-2047907.

## References

  * [ABCM17] Georgios Amanatidis, Georgios Birmpas, George Christodoulou, and Evangelos Markakis.  Truthful allocation mechanisms without payments: Characterization and implications on fairness.  In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 545–562, 2017.
  * [ABF+23] Georgios Amanatidis, Georgios Birmpas, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser.  Allocating indivisible goods to strategic agents: Pure nash equilibria and fairness.  Mathematics of Operations Research, 2023.
  * [ABL+23] Georgios Amanatidis, Georgios Birmpas, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser.  Round-robin beyond additive agents: Existence and fairness of approximate equilibria.  arXiv preprint arXiv:2301.13652, 2023.
  * [ACGH20] Rediet Abebe, Richard Cole, Vasilis Gkatzelis, and Jason D Hartline.  A truthful cardinal mechanism for one-sided matching.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2096–2113. SIAM, 2020.
  * [AL21] Haris Aziz and Alexander Lam.  Obvious manipulability of voting rules.  In Algorithmic Decision Theory: 7th International Conference, ADT 2021, Toulouse, France, November 3–5, 2021, Proceedings 7, pages 179–193. Springer, 2021.
  * [Alo87] Noga Alon.  Splitting necklaces.  Advances in Mathematics, 63(3):247–253, 1987.
  * [AMNS17] Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi.  Approximation algorithms for computing maximin share allocations.  ACM Transactions on Algorithms (TALG), 13(4):1–28, 2017.
  * [BCIZ21] Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick.  Finding fair and efficient allocations for matroid rank valuations.  ACM Transactions on Economics and Computation, 9(4):1–41, 2021\.
  * [BEF21] Moshe Babaioff, Tomer Ezra, and Uriel Feige.  Fair and truthful mechanisms for dichotomous valuations.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5119–5126, 2021.
  * [BG21] Yushi Bai and Paul Gölz.  Envy-free and pareto-optimal allocations for agents with asymmetric random valuations.  arXiv preprint arXiv:2109.08971, 2021.
  * [BHPV23] Gerdus Benadè, Daniel Halpern, Alexandros Psomas, and Paritosh Verma.  On the existence of envy-free allocations beyond additive valuations.  arXiv preprint arXiv:2307.09648, 2023.
  * [BM01] Anna Bogomolnaia and Hervé Moulin.  A new solution to the random assignment problem.  Journal of Economic Theory, 100(2):295–328, 2001.
  * [Bud11] Eric Budish.  The combinatorial assignment problem: approximate competitive equilibrium from equal incomes.  Journal of Political Economy, 119(6):1061–1103, 2011.
  * [BV21] Siddharth Barman and Paritosh Verma.  Truthful and fair mechanisms for matroid-rank valuations.  arXiv preprint arXiv:2109.05810, 2021.
  * [CGG13] Richard Cole, Vasilis Gkatzelis, and Gagan Goel.  Mechanism design for fair division: allocating divisible items without payments.  In Proceedings of the fourteenth ACM conference on Electronic commerce, pages 251–268, 2013.
  * [CKM+19] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang.  The unreasonable fairness of maximum nash welfare.  ACM Transactions on Economics and Computation (TEAC), 7(3):1–32, 2019.
  * [CLPP13] Yiling Chen, John K Lai, David C Parkes, and Ariel D Procaccia.  Truth, justice, and cake cutting.  Games and Economic Behavior, 77(1):284–297, 2013.
  * [DM22] Sulagna Dasgupta and Debasis Mishra.  Ordinal Bayesian incentive compatibility in random assignment model.  Review of Economic Design, pages 1–14, 2022.
  * [dP88] Claude d’Aspremont and Bezalel Peleg.  Ordinal Bayesian incentive compatible representations of committees.  Social Choice and Welfare, 5(4):261–279, 1988.
  * [FGP14] Eric Friedman, Ali Ghodsi, and Christos-Alexandros Psomas.  Strategyproof allocation of discrete jobs on multiple machines.  In Proceedings of the fifteenth ACM conference on Economics and computation, pages 529–546, 2014.
  * [FGPS19] Eric J Friedman, Vasilis Gkatzelis, Christos-Alexandros Psomas, and Scott Shenker.  Fair and efficient memory sharing: Confronting free riders.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1965–1972, 2019.
  * [Fin64] AM Fink.  A note on the fair division problem.  Mathematics Magazine, 37(5):341–342, 1964.
  * [FTTZ16] Dimitris Fotakis, Dimitris Tsipras, Christos Tzamos, and Emmanouil Zampetakis.  Efficient money burning in general domains.  Theory of Computing Systems, 59(4):619–640, 2016.
  * [Fuj08] Yuji Fujinaka.  A Bayesian incentive compatible mechanism for fair division.  2008\.
  * [Gib73] Allan Gibbard.  Manipulation of voting schemes: a general result.  Econometrica: journal of the Econometric Society, pages 587–601, 1973.
  * [GP15] Jonathan Goldman and Ariel D Procaccia.  Spliddit: Unleashing fair division algorithms.  ACM SIGecom Exchanges, 13(2):41–46, 2015.
  * [GZH+11] Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica.  Dominant resource fairness: Fair allocation of multiple resource types.  In Nsdi, volume 11, pages 24–24, 2011.
  * [HPPS20] Daniel Halpern, Ariel D Procaccia, Alexandros Psomas, and Nisarg Shah.  Fair division with binary valuations: One rule to rule them all.  In International Conference on Web and Internet Economics, pages 370–383. Springer, 2020.
  * [HR08] Jason D Hartline and Tim Roughgarden.  Optimal mechanism design and money burning.  In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 75–84, 2008.
  * [KM02] Bettina Klaus and Eiichi Miyagawa.  Strategy-proofness, solidarity, and consistency for multiple assignment problems.  International Journal of Game Theory, 30(3):421–435, 2002.
  * [Li17] Shengwu Li.  Obviously strategy-proof mechanisms.  American Economic Review, 107(11):3257–87, 2017.
  * [LMMS04] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi.  On approximately fair allocations of indivisible goods.  In Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), pages 125–131, 2004.
  * [Mou80] Hervé Moulin.  Implementing efficient, anonymous and neutral social choice functions.  Journal of Mathematical Economics, 7(3):249–269, 1980.
  * [Mou04] Hervé Moulin.  Fair division and collective welfare.  MIT press, 2004.
  * [MS20] Pasin Manurangsi and Warut Suksompong.  When do envy-free allocations exist?  SIAM Journal on Discrete Mathematics, 34(3):1505–1521, 2020.
  * [MS21a] Pasin Manurangsi and Warut Suksompong.  Closing gaps in asymptotic fair division.  SIAM Journal on Discrete Mathematics, 35(2):668–706, 2021.
  * [MS21b] Timo Mennle and Sven Seuken.  Partial strategyproofness: Relaxing strategyproofness for the random assignment problem.  Journal of Economic Theory, 191:105144, 2021.
  * [OSH22] Josué Ortega and Erel Segal-Halevi.  Obvious manipulations in cake-cutting.  Social Choice and Welfare, 59(4):969–988, 2022.
  * [PPS15] David C Parkes, Ariel D Procaccia, and Nisarg Shah.  Beyond dominant resource fairness: Extensions, limitations, and indivisibilities.  ACM Transactions on Economics and Computation (TEAC), 3(1):1–22, 2015.
  * [PV22] Alexandros Psomas and Paritosh Verma.  Fair and efficient allocations without obvious manipulations.  In Advances in Neural Information Processing Systems, 2022.
  * [Sat75] Mark Allen Satterthwaite.  Strategy-proofness and arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions.  Journal of economic theory, 10(2):187–217, 1975.
  * [Sch96] James Schummer.  Strategy-proofness versus efficiency on restricted domains of exchange economies.  Social Choice and Welfare, 14(1):47–56, 1996.
  * [Sha17] Nisarg Shah.  Spliddit: two years of making the world fairer.  XRDS: Crossroads, The ACM Magazine for Students, 24(1):24–28, 2017\.
  * [Tao22] Biaoshuai Tao.  On existence of truthful fair cake cutting mechanisms.  In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 404–434, 2022.
  * [TM20] Peter Troyan and Thayer Morrill.  Obvious manipulations.  Journal of Economic Theory, 185:104970, 2020.

##  Appendix A Missing proofs from Section 3.1

*

###### Proof.

Without loss of generality assume that the items are indexed such that
$v_{i,1}\geq v_{i,2}\geq\ldots\geq v_{i,m}$. Let $\ell$ be the largest index
of an item for which agent $i$ has a positive value, i.e.,
$\ell=\max\limits_{v_{i,j}>0}j$. Note that $\ell$ is not defined if
$v_{i,j}=0$ for all $j\in[m]$. However, in this case,
$\mathbf{a}\succeq_{i}\mathbf{b}$ trivially holds and
$\mathbf{a}\succ^{+}_{i}\mathbf{b}$ can never be true. Hence, we will assume
that $\ell$ is well-defined.

_Proving $(1)$._ To establish that $u_{i}(\mathbf{a})\geq u_{i}(\mathbf{b})$
if $\mathbf{a}\succeq^{+}_{i}\mathbf{b}$, we will inductively show that for
each $j\in[\ell]$, the inequality

$\displaystyle\sum_{k=1}^{j}(y_{i,k}-x_{i,k})v_{i,k}\geq
v_{i,j}\sum_{k=1}^{j}(y_{i,k}-x_{i,k}),$ (9)

is satisfied. Note that proving Equation 9 for all $j\in[\ell]$ establishes
the proposition, since instantiating Equation 9 with $j=\ell$ gives us

$\displaystyle\sum_{k=1}^{\ell}(y_{i,k}-x_{i,k})v_{i,k}\geq
v_{i,\ell}\sum_{k=1}^{\ell}(y_{i,k}-x_{i,k}).$ (10)

The left-hand side of the above inequality is equal to
$\sum_{k=1}^{\ell}(y_{i,k}-x_{i,k})v_{i,k}=u_{i}(\mathbf{a})-u_{i}(\mathbf{b})$,
and the right-hand side, $v_{i,\ell}\sum_{k=1}^{\ell}(y_{i,k}-x_{i,k})\geq 0$
because $v_{i,\ell}>0$ along with the fact that
$\sum_{k=1}^{\ell}(y_{i,k}-x_{i,k})=\sum_{k=1}^{\ell}y_{i,k}-\sum_{k=1}^{\ell}x_{i,k}\geq
0$; here the final inequality follows from the fact that
$\mathbf{a}\succeq^{+}_{i}\mathbf{b}$.

Now, by induction on $j$, we will show that Equation 9 holds for all
$j\in[\ell]$. For the base case of the induction, note that Equation 9
trivially holds for $j=1$. As part of the induction step, we will show that
assuming Equation 9 holds for some $j<\ell$ implies that Equation 9 holds for
$j+1$ as well. To this end, consider the following

$\displaystyle\sum_{k=1}^{j+1}(y_{i,k}-x_{i,k})v_{i,k}$
$\displaystyle=\sum_{k=1}^{j}(y_{i,k}-x_{i,k})v_{i,k}+(y_{i,j+1}-x_{i,j+1})v_{i,j+1}$
$\displaystyle\geq
v_{i,j}\sum_{k=1}^{j}(y_{i,k}-x_{i,k})+(y_{i,j+1}-x_{i,j+1})v_{i,j+1}$
(Equation (9) holds for $j$) $\displaystyle\geq
v_{i,j+1}\sum_{k=1}^{j}(y_{i,k}-x_{i,k})+(y_{i,j+1}-x_{i,j+1})v_{i,j+1}$
($v_{i,j}\geq v_{i,j+1}$)
$\displaystyle=v_{i,j+1}\sum_{k=1}^{j+1}y_{i,k}-x_{i,k}.$

This implies that Inequality (9) holds for $j+1$ and completes the induction
step, thereby establishing that $u_{i}(\mathbf{a})\geq u_{i}(\mathbf{b})$.

_Proving $(2)$._ The proof of this part is very similar to the proof of the
previous part. Hence, we will only highlight the point where the proofs
differ. Since $\mathbf{a}\succ^{+}_{i}\mathbf{b}$, we know that there exists a
$j\in[\ell]$ for which the strict inequality
$\sum_{k=1}^{j}(y_{i,k}-x_{i,k})>0$ holds. Following the same inductive
argument and additionally using the strict inequality
$\sum_{k=1}^{j}(y_{i,k}-x_{i,k})>0$ in the inductive step establishes the
strict inequality $u_{i}(\mathbf{a})>u_{i}(\mathbf{b})$.

∎

*

###### Proof.

Consider the following mechanism for $n=2$ agents: starting from the set of
all items $\mathcal{M}$, agent $1$ computes her preference $\mathbf{p}_{1}$
based her valuation and the lexicographic tie-breaking. Let
$j^{*}=\mathbf{p}_{1}(m)$, i.e., $j^{*}$ is agent $1$’s least favorite item in
the ranking. The mechanism assigns $\mathcal{M}\setminus\\{j^{*}\\}$ to agent
1 and $\\{j^{*}\\}$ to agent 2. It is easy to see that this mechanism is
truthful for agent $1$: she only wants to get rid of her least favorite item
as per his true utility. And $v_{1,j^{*}}\leq v_{1,k}$ for all
$j\in\mathcal{M}$. Since the mechanism is independent of agent $2$’s
reporting, it is also truthful for agent $2$.

Finally, note that the output allocation is $\mathrm{SD}$ efficient, because
we cannot improve an agent’s bundle without making the other agent’s bundle
worse. Specifically, in order to improve the bundle of agent $1$ wrt
$\succ_{1}$ we must give item $j^{*}$ to her, which will make the bundle of
agent $2$ strictly worse wrt $\succ_{2}$ since her bundle size would decrease.
Similarly, to improve agent $2$’s bundle wrt $\succ_{2}$ we must allocate her
another item, which also will make the bundle of agent $1$ worse wrt
$\succ_{1}$. This implies that the described mechanism, which is not the
serial dictatorship, is truthful and outputs $\mathrm{SD}$ efficient
allocations. ∎

*

###### Proof.

This proposition essentially follows from the following well-known results
from the literature. First, it is known that for binary additive preferences
(i.e., $v_{i,j}\in\\{0,x\\}$ for some fixed $x>0$) there exists a
deterministic DSIC mechanism that outputs allocations that are Pareto
efficient as well as $\mathrm{EF}1$ [HPPS20].

Additionally, it is also known that for additive preferences where $0$ is not
allowed as a valid report, i.e., $v_{i,j}>0$ (this includes as a special case,
the bivalued additive preferences, satisfying $v_{i,j}\in\\{a,b\\}$ for some
$a,b>0$) there exists DSIC mechanisms — other than serial dictatorship — which
output Pareto efficient allocations [ABCM17][Corollary 3.20]. ∎

##  Appendix B Missing proofs from Section 3.2

*

###### Proof.

We first show that $\mathrm{RR}^{\text{pass}}$ is $\mathrm{SD}^{+}$efficient.
We let $A=(A_{1},A_{2}\ldots,A_{n})$ be an allocation where $A_{i}$ is the
bundle agent $i$ receives. In $\mathrm{RR}^{\text{pass}}$, one item is
allocated in each timestep. We let
$A^{t}=(A^{t}_{1},A^{t}_{2}\ldots,A^{t}_{n})$ denote the partial allocation of
all the allocated items up to and including timestep $t$, where $A^{t}_{i}$
denotes the bundle of agent $i$ in $A^{t}$. We have $A^{0}_{i}=\emptyset$ and
$A^{m}_{i}=A_{i}$ for all agent $i$. Assume, for contradiction that $A$ is not
$\mathrm{SD}^{+}$efficient, i.e., there exists another allocation
$B=(B_{1},B_{2},\ldots,B_{n})$ such that

$B_{j}\succeq^{+}A_{j}\text{ for all }j\quad\text{and}\quad
B_{i}\succ^{+}A_{i}\text{ for some }i.$

We let $B_{i}^{t}=B_{i}\cap A_{i}^{t}$, and let $t^{*}=\min\\{t:B_{i}^{t}\neq
A_{i}^{t}\text{ for some }i\\}$. Further, let $i^{*}$ be the agent with the
turn to pick in $\mathrm{RR}^{\text{pass}}$ at timestep $t^{*}$ and
$\mathbf{p}^{*}$ be the preference order of agent $i^{*}$, and
$\mathbf{p}^{*}(a)$ be the item agent $i^{*}$ picks at timestep $t^{*}$ for an
index $a\geq 1$. Note that $B^{t}_{i^{*}}=A^{t}_{i^{*}}$ for all $t<t^{*}$,
since $t^{*}$ is the first timestep where $A$ and $B$ start to differ.

Define $U\coloneqq\mathcal{M}\setminus\cup_{i=1}^{n}A_{i}^{t^{*}-1}$ (which is
same as $\mathcal{M}\setminus\cup_{i=1}^{n}B_{i}^{t^{*}-1}$) to be the set of
items that are unallocated after $t^{*}-1$ timesteps. To arrive at a
contradiction, we will first note that the item
$\mathbf{p}^{*}(a)\in\mathcal{M}_{i^{*}}^{+}$. Otherwise, if
$\mathbf{p}^{*}(a)\notin\mathcal{M}_{i^{*}}^{+}$, then all the items $j\in U$
must also satisfy $j\notin\cup_{i=1}^{n}\mathcal{M}_{i}^{+}$ since
$\mathrm{RR}^{\text{pass}}$ will allocate a zero-valued item to an agent
$i^{*}$ only if it is zero-valued by every other agent. However, if all the
unallocated items after timestep $t^{*}-1$ are zero-valued by everyone, and
$A_{i}^{t^{*}-1}=B_{i}^{t^{*}-1}$ for agents $i$, then allocation $B$ cannot
stochastically and positively dominate $A$ since each agent’s utility will be
the same in both the allocations. Therefore, it must be the case that
$\mathbf{p}^{*}(a)\in\mathcal{M}_{i^{*}}^{+}$, i.e., $a\leq
m_{i^{*}}=|\mathcal{M}_{i^{*}}^{+}|$.

To complete the proof, we will now show that
$\mathbf{p}^{*}(a)\in\mathcal{M}_{i^{*}}^{+}$ implies that $B$ cannot
stochastically and positively dominate $A$, contradicting our initial
assumption. Recall that, $\mathrm{RR}^{\text{pass}}$ constructs the preference
order $\mathbf{p}^{*}$ lexicographically, for any $k<a$, we have
$B_{i^{*},\mathbf{p}^{*}(k)}=A_{i^{*},\mathbf{p}^{*}(k)}$. Additionally, since
$t^{*}$ is the first timestep where $A$ and $B$ differ,
$A_{i^{*},\mathbf{p}^{*}(a)}=1$ and $B_{i^{*},\mathbf{p}^{*}(a)}=0$ as well.
We, therefore, have:

$\displaystyle\sum_{\ell=1}^{a}B_{i^{*},\mathbf{p}^{*}(\ell)}$
$\displaystyle=\sum_{\ell=1}^{a-1}B_{i^{*},\mathbf{p}^{*}(\ell)}=\sum_{\ell=1}^{a-1}A_{i^{*},\mathbf{p}^{*}(\ell)}$
$\displaystyle<\sum_{\ell=1}^{a-1}A_{i^{*},\mathbf{p}^{*}(\ell)}+A_{i^{*},\mathbf{p}^{*}(a)}$
($A_{i^{*},\mathbf{p}^{*}(a)}=1$)
$\displaystyle=\sum_{\ell=1}^{a}A_{i^{*},\mathbf{p}^{*}(\ell)}.$

However, note that
$\sum_{\ell=1}^{a}B_{i^{*},\mathbf{p}^{*}(\ell)}<\sum_{\ell=1}^{a}A_{i^{*},\mathbf{p}^{*}(\ell)}$
and the fact that $a\leq m_{i^{*}}$ contradicts with the assumption that $B$
stochastically and positively dominates $A$. Thus, $A$ must have been
$\mathrm{SD}^{+}$efficient.

For completeness, we will now show that $\mathrm{RR}^{\text{pass}}$ is EF1;
this argument is the same which is used to show that Round-Robin outputs EF1
allocations. Recall that $\mathrm{RR}^{\text{pass}}$ considers agents in a
fixed order $\pi$. First, note that agent $1$ in this order does not envy
anyone since she always picks first. Similarly, for any $i\in[2,n-1]$, agent
$i$ does not envy agents $i+1$ to agent $n$. Now consider agent $i-1$. We will
break $\mathrm{RR}^{\text{pass}}$ into two stages. In the first stage, each of
the first $i-1$ agents receives 1 item, and in the second stage, the rest of
$\mathrm{RR}^{\text{pass}}$ takes place. We denote the bundle that agent $i$
receives in the second stage of the mechanism as $X_{i}^{2}$. Note that agent
$i$ is considered first in the second stage of the mechanism, and by the same
argument, she does not envy any agent. In particular, for any agent
$j\in[i-1]$, we have:

$v_{i}(X^{2}_{i})\geq v_{i}(X_{j}^{2}).$

Note that in the first stage of the mechanism, agent $i$ did not receive any
item and agent $j$ received exactly one item. Therefore, we have for any
$j\in[i-1]$:

$v_{i}(X_{i})=v_{i}(X_{i}^{2})>v_{1}(X_{j}^{2})\geq
v_{1}(X_{j}^{2}\setminus\\{g_{j}\\}),$

where $g_{j}$ is the item that agent $j$ receives in the first stage of
$\mathrm{RR}^{\text{pass}}$. ∎

##  Appendix C Separation between Pareto efficiency,
$\mathrm{SD}^{+}\text{efficiency}$, and $\mathrm{SD}\text{ efficiency}$

In this section, we will show that the implications established in Lemma 1
$(1)$ and $(2)$ are tight, i.e., the other direction of the implications is
not true. Towards this, first, we will describe an allocation that is
$\mathrm{SD}^{+}$efficient but not Pareto efficient. Consider an instance with
$n=2$ agents and $m=4$ items such that the valuations of the agents are
$\mathbf{v}_{1}=(5,4,3,2)$ and $\mathbf{v}_{2}=(6,1,2,3)$ respectively. Let
$\mathbf{x}=(\mathbf{x}_{1},\mathbf{x}_{2})$ be an allocation wherein agent
$1$ receives the first two items and the rest of the items are allocated to
agent $2$, i.e., $x_{1,1}=x_{1,2}=x_{2,3}=x_{2,4}=1$. We will show that
$\mathbf{x}$ is $\mathrm{SD}^{+}$efficient but not Pareto efficient. The
allocation $\mathbf{x}$ is $\mathrm{SD}^{+}$efficient because, in order to
improve the bundle of agent $1$ wrt $\succ^{+}_{1}$ we must give her another
item (she already has her top two items in $\mathbf{x}$), which will make the
bundle of agent $2$ worse wrt $\succ^{+}_{2}$ (since agent $2$ will be left
with only one item). Similarly, to improve agent $2$’s bundle wrt
$\succ^{+}_{2}$, we must either $(i)$ give her at least three items, or $(ii)$
give her items $1$ and $4$ — top-2 items as per $\mathbf{v}_{2}$. Both $(i)$
and $(ii)$ will make the bundle of agent $1$ worse. Thus, $\mathbf{x}$ is
$\mathrm{SD}^{+}$efficient. Now, to show that $\mathbf{x}$ is not Pareto
efficient consider the allocation $\mathbf{y}=(\mathbf{y}_{1},\mathbf{y}_{2})$
where agent $2$ gets only item $1$, i.e., $y_{2,1}=y_{1,2}=y_{1,3}=y_{1,4}=1$.
Note that $u_{1}(\mathbf{x})=u_{1}(\mathbf{y})=9$, while $u_{2}(\mathbf{x})=5$
and $u_{2}(\mathbf{y})=6$ implying $\mathbf{y}$ Pareto dominates $\mathbf{x}$.
Thus, $\mathbf{x}$ is $\mathrm{SD}^{+}$efficient but not Pareto efficient.

Finally, we describe an allocation that is $\mathrm{SD}$ efficient but not
$\mathrm{SD}^{+}$efficient. Consider an instance with $n=2$ agents and $m=2$
items such that $\mathbf{v}_{1}=(1,1)$ and $\mathbf{v}_{2}=(1,0)$; note that
$2\notin\mathcal{M}_{2}^{+}$. Let
$\mathbf{x}^{\prime}=(\mathbf{x}^{\prime}_{1},\mathbf{x}^{\prime}_{2})$ be an
allocation such that $x^{\prime}_{1,1}=x^{\prime}_{2,2}=1$. This allocation is
not $\mathrm{SD}^{+}$efficient: transferring item $2$ from agent $2$ to agent
$1$ doesn’t affect agent $2$’s bundle wrt $\succeq^{+}_{2}$, however, it
improves agent $1$’s bundle wrt $\succ^{+}_{1}$, i.e., the allocation
resulting from this transfer stochastically and positively dominates
$\mathbf{x}$. Contrary to this, the allocation $\mathbf{x}$ is $\mathrm{SD}$
efficient because in order to improve the bundle of agent $1$ wrt $\succ_{1}$
(or agent $2$ wrt $\succ_{2}$) we must necessarily decrease the bundle size of
agent $2$ (agent $1$). This will make the bundle of agent $2$ (agent $1$)
strictly worse, since as per the definition of $\succeq_{i}$, a decrease in
bundle size necessarily makes the bundle strictly worse. Therefore,
$\mathbf{x}^{\prime}$ is $\mathrm{SD}$ efficient but not
$\mathrm{SD}^{+}$efficient.

##  Appendix D Missing proofs from Section 4

*

###### Proof.

We will show this via an inductive argument. In particular, we will prove that
at the partial allocation $(X_{1},X_{2},\dots,X_{i})$ at the end of iteration
$i$ of the outer loop, is proportional for agents $1,2,\dots,i$ for all
$i\in\\{2,3,\ldots,n\\}$.

Base case: In the iteration $i=2$, agent $1$ splits the interval $[0,1]$ into
2 pieces $C_{1}^{1}$ and $C_{1}^{2}$ such that
$f^{*}_{1}(C_{1}^{1})=f^{*}_{1}(C^{1}_{2})=1/2$, where the final equality
follows from the fact that $C_{1}^{1}\cup C_{1}^{2}=[0,1]$. Agent $2$ then
picks the piece $C^{k^{*}}_{1}$ having a higher value wrt $f^{*}_{2}$, leaving
the remaining piece for agent $1$. The resultant allocation is proportional
since agent $1$’s value for both pieces is $1/2$, and agent $2$ gets to pick
her favorite piece, implying that $f^{*}_{2}(C^{k^{*}}_{1})\geq
f^{*}_{2}([0,1])/2=1/2$.

Induction step: For $i>2$, let
$\mathbf{x}^{\prime}=(X^{\prime}_{i},X^{\prime}_{2}\dots,X^{\prime}_{i-1})$
denote the allocation before the arrival of agent $i$ (i.e., at the beginning
of iteration $i$). Assuming that $\mathbf{x}^{\prime}$ is proportional for
agents $[i-1]$, we will now show that the allocation
$\mathbf{x}=(X_{1},X_{2},\ldots,X_{i})$ at the end of iteration $i$ will be
proportional for agents $[i]$. First, we will show that $\mathbf{x}$ is
proportional for agents $j\in[i-1]$. Towards this, note that
$\mathbf{x}^{\prime}$ is proportional for agents $j\in[i-1]$, i.e., for any
agent $j\in[i-1]$, we have, $f^{*}_{j}(X^{\prime}_{j})\geq\frac{1}{i-1}$.
Additionally, from the definition of the Split-Equal subroutine, we know that
$f^{*}_{j}(C_{j}^{k})=\frac{1}{i}f^{*}_{j}(X^{\prime}_{j})$ for all $k\in[i]$
and $j\in[i-1]$, where pieces $C_{j}^{1},C_{j}^{2},\ldots,C_{j}^{i}$ are
obtained from the performing Split-Equal operation on inputs
$(f^{*}_{j},X^{\prime}_{j},i)$. On combining these two observations, we get
that for all $j\in[i-1]$,

$f^{*}_{j}(X_{j})=f^{*}_{j}(X^{\prime}_{j}\setminus
C_{j}^{k^{*}})=\left(1-\frac{1}{i}\right)f^{*}_{j}(X_{j})\geq\frac{i-1}{i}\cdot\frac{1}{i-1}=\frac{1}{i},$

where $C_{j}^{k^{*}}$ is the piece picked by agent $i$ from agent $j$ in
iteration $i$. This implies that $\mathbf{x}$ is proportional for agents
$j\in[i-1]$. Finally, we consider agent $i$. Note that by definition of the
mechanism, agent $i$ picks her favorite interval from each agent $j\in[i-1]$,
this implies that,

$\displaystyle f^{*}_{i}(X_{i})=\sum_{j=1}^{i-1}\max_{k}f^{*}_{i}(C_{j}^{k})$
$\displaystyle\geq\sum_{j=1}^{i-1}\frac{1}{i}\sum_{k=1}^{i}f^{*}_{i}(C_{j}^{k})$
(maximum is at least the average)
$\displaystyle=\sum_{j=1}^{i-1}\frac{1}{i}f^{*}_{i}(X^{\prime}_{j})$
($X^{\prime}_{j}=\cup_{k=1}^{i}C_{j}^{k}$)
$\displaystyle=\frac{1}{i}f^{*}_{i}([0,1])=\frac{1}{i},$

where the penultimate inequality follows from the fact that
$\cup_{j=1}^{i-1}X^{\prime}_{j}=[0,1]$, i.e., $\mathbf{x}^{\prime}$ is a
complete allocation among agents $[i-1]$. This implies that $\mathbf{x}$ is
proportional for agent $i$ as well. This completes the induction step and
concludes the proof. ∎