# Multi-Type Resource Allocation with Partial Preferences

Haibin Wang,1 Sujoy Sikdar,2 Xiaoxi Guo,1 Lirong Xia,3 Yongzhi Cao,1* Hanpin
Wang4,1
1Key Laboratory of High Confidence Software Technologies (MOE),
Department of Computer Science and Technology, Peking University, China
2Computer Science & Engineering, Washington University in St. Louis
3Department of Computer Science, Rensselaer Polytechnic Institute
4School of Computer Science and Cyber Engineering, Guangzhou University, China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>*Corresponding Author

###### Abstract

We propose multi-type probabilistic serial (MPS) and multi-type random
priority (MRP) as extensions of the well-known PS and RP mechanisms to the
multi-type resource allocation problems (MTRAs) with partial preferences. In
our setting, there are multiple types of divisible items, and a group of
agents who have partial order preferences over bundles consisting of one item
of each type. We show that for the unrestricted domain of partial order
preferences, no mechanism satisfies both sd-efficiency and sd-envy-freeness.
Notwithstanding this impossibility result, our main message is positive: When
agents’ preferences are represented by acyclic CP-nets, MPS satisfies sd-
efficiency, sd-envy-freeness, ordinal fairness, and upper invariance, while
MRP satisfies ex-post-efficiency, sd-strategyproofness, and upper invariance,
recovering the properties of PS and RP. Besides, we propose a hybrid
mechanism, multi-type general dictatorship (MGD), combining the ideas of MPS
and MRP, which satisfies sd-efficiency, equal treatment of equals and
decomposability under the unrestricted domain of partial order preferences.

## Introduction

Consider the example of rationing (?) two types of divisible resources: food
(F) and beverage (B) among two families who have heterogeneous preferences
over combinations of food and beverage they wish to consume. For example, a
family may prefer water with rice, and milk with wheat. How should we
distribute available resources to the families fairly and efficiently?

In this paper, we consider the problems of divisible multi-type resource
allocation problems (MTRAs) (?) with partial preferences. Here, there are
$p\geq 1$ types of $n$ divisible items per type, with one unit of supply of
each item, and a group of $n$ agents with partial preferences over receiving
bundles consisting of one unit of each type. Our goal is to design mechanisms
to fairly and efficiently allocate one unit of items of each type to every
agent given their partial preferences over bundles. Such mechanisms are called
fractional mechanisms, because an agent may receive fractions of items.

When there is one type ($p=1$), fractional mechanisms broadly fall in two
classes. The random priority (RP) mechanism (?) exemplifies the first class:
agents consume their favorite remaining item one-by-one according to an
ordering drawn from the uniform distribution. Each agent is allocated a
fraction of each item equal to the probability that they consume the item. It
is easy to see that RP satisfies ex-post-efficiency and equal treatment of
equals. Additionally, RP satisfies notions of envy-freeness and
strategyproofness through the idea of stochastic dominance (sd). Given strict
preferences, a fractional allocation $p$ dominates another $q$, if at every
item $o$, the total share of $o$ and items preferred to $o$ under $p$ is at
least the total share under $q$. RP satisfies weak-sd-envy-freeness and sd-
strategyproofness (?).

The probabilistic serial (PS) mechanism belongs to the class of “simultaneous
eating” mechanisms (?). PS proceeds in multiple rounds. In each round, all
agents simultaneously “eat” their favorite remaining item at a constant,
uniform rate, until one of the items being consumed is exhausted. This
terminates when all items are fully consumed, and the output allocates each
agent with a fraction of each item that they would consume by this procedure.
PS satisfies sd-efficiency, sd-envy-freeness, and weak-sd-strategyproofness
(?). Besides, PS is the only mechanism that simultaneously satisfies sd-
efficiency, sd-envy-freeness, and bounded invariance (?; ?).

Table 1: Properties of MRP, MPS and MGD under different domain restrictions on partial preferences. A “Y” indicates that the row mechanism satisfies the column property, and an “N” indicates that it does not. Results annotated with † are from (?), ‡ are from (?). Other results are proved in this paper.  Mechanism and Preference Domain | SE | EPE | OF | SEF | WSEF | ETE | UI | SS | WSS | DC
---|---|---|---|---|---|---|---|---|---|---
| General partial preferences | N${}^{\text{\textdagger}}$ | Y | N${}^{\text{\textdaggerdbl}}$ | N${}^{\text{\textdagger}}$ | Y | Y | N | N | Y | Y
MRP | CP-nets | N${}^{\text{\textdagger}}$ | Y | N${}^{\text{\textdaggerdbl}}$ | N${}^{\text{\textdagger}}$ | Y | Y | Y | Y | Y | Y
| Independent CP-nets | N${}^{\text{\textdagger}}$ | Y | N${}^{\text{\textdaggerdbl}}$ | N${}^{\text{\textdagger}}$ | Y | Y | Y | Y | Y | Y
| General partial preferences | Y | N | N | N | Y | Y | N | N${}^{\text{\textdagger}}$ | N | N
MPS | CP-nets | Y | N | Y | Y | Y | Y | Y | N${}^{\text{\textdagger}}$ | N | N
| Independent CP-nets | Y | N | Y | Y | Y | Y | Y | N${}^{\text{\textdagger}}$ | Y | N
| General partial preferences | Y | Y | N${}^{\text{\textdaggerdbl}}$ | N | N | Y | N | N | N | Y
MGD | CP-nets | Y | Y | N${}^{\text{\textdaggerdbl}}$ | N | N | Y | N | N | N | Y
| Independent CP-nets | Y | Y | N${}^{\text{\textdaggerdbl}}$ | N | N | Y | N | N | N | Y

Our work is the first to consider the design of fair and efficient mechanisms
for MTRAs with partial preferences, and the first to extend fractional
mechanisms to MTRAs with partial preferences, to the best of our knowledge. ?
(?) mention that PS can be extended to partial orders but we are not aware of
a (formal or informal) work that explicitly defines such an extension and
studies its properties. ? (?) and ? (?) consider the problem of MTRAs under
linear preferences, but do not fully address the issue of fairness. ? (?)
consider the problem of allocating multiple types of resources, when the
resources of each type are indistinguishable, and agents have different
demands for each type of resources. However, the problem of finding fair and
efficient assignments for MTRAs with partial preferences remains open.

Our mechanisms output fractional assignments, where each agent receives a
fractional share of bundles consisting of an item of each type, which together
amount to one unit per type. The fractional assignments output by our
mechanisms also specify for each agent how to form bundles for consumption
from the assigned fractional shares of items. Our setting may be interpreted
as a special case of cake cutting (?; ?; ?), where the cake is divided into
parts of unit size of $p$ types, and $n$ parts per type, and agents have
complex combinatorial preferences over being assigned combinations of parts of
the cake which amount to one unit of each type.

Our Contributions. Our work is the first to provide fair and efficient
mechanisms for MTRAs, and the first to extend PS and RP both to MTRAs and to
partial preferences, to the best of our knowledge. We propose multi-type
probabilistic serial (MPS) and multi-type random priority (MRP) as the
extensions of PS and RP to MTRAs, respectively. Our main message is positive:
Under the well-known and natural domain restriction of CP-net preferences (?),
MRP and MPS satisfy all of the fairness and efficiency properties of their
counterparts for single types and complete preferences.

Unlike single-type resources allocations, in MTRAs, not all fractional
assignments are decomposable, where assignments can be represented as a
probability distribution over assignments where each agent receives a bundle
consisting of whole items. Unfortunately, the output of MPS may be
indecomposable. In response to this, we propose a new mechanism, multi-type
general dictatorship (MGD), which is decomposable and matches the efficiency
of MPS, and satisfies equal treatment of equals.

Our technical results are summarized in Table 1. We extend stochastic
dominance to compare two fractional allocations under partial preferences.
Here, a fractional allocation $p$ is said to stochastically dominate another
allocation $q$ w.r.t. an agent’s partial preference, if at any bundle, the
fractional share of weakly dominating bundles in $p$ is larger than or equal
to the fractional shares of the bundles in $q$ according to her preference.
Formal definitions of stochastic dominance and properties in Table 1 can be
found in Preliminaries.

For the unrestricted domain of general partial preferences, unfortunately, no
mechanism satisfies both sd-efficiency (SE) and sd-envy-freeness (SEF) as we
prove in Proposition 3. Despite this impossibility result, MRP, MPS and MGD
satisfy several desirable properties: We show in

  * -

Theorem 1 that MRP satisfies ex-post-efficiency (EPE), weak-sd-envy-freeness
(WSEF), equal treatment of equals (ETE), weak-sd-strategyproofness (WSS), and
decomposibility (DC);

  * -

Theorem 2 that MPS satisfies sd-efficiency (SE), equal treatment of equals
(ETE), weak-sd-envy-freeness (WSEF);

  * -

Theorem 3 that MGD satisfies sd-efficiency (SE), ex-post-efficiency (EPE),
equal treatment of equals (ETE), and decomposibility (DC).

Remarkably, we recover the fairness properties of MPS, and the truthfulness
and invariance properties for MRP and MPS under the well-known and natural
domain restriction of acyclic CP-net preferences (?). We show in:

  * -

Theorem 4, that MRP is sd-strategyproof (SS);

  * -

Theorem 5, that MPS is sd-envy-free (SEF) and ordinally fair (OF);

  * -

Proposition 5 that MPS is upper invariant (UI); and

  * -

Proposition 6 that MPS is weak-sd-strategyproof (WSS) under the special case
where agents’ CP-nets are independent between each type.

Discussions. MGD may be viewed as a hybrid between MRP and MPS: on the one
hand as a modification of MRP where the priorities depend on the preference
profile, instead of being drawn from the uniform distribution; and on the
other hand, as a modification of MPS where only a subset of the agents are
allowed to eat simultaneously in each round. The design of MGD is motivated by
the natural desire for decomposability (not satisfied by MPS), while
maintaining the stronger efficiency notion of sd-efficiency (not satisfied by
MRP), and the basic fairness property of equal treatment of equals.
Decomposable assignments are desired when sharing of items imposes overhead
costs, as noted by (?). However,  (i) for MTRAs, fractional assignments are
not guaranteed to be decomposable as we show in assignment (3) of Example 2,
and indeed, MPS does not guarantee decomposable assignments;  (ii) fractional
mechanisms are inevitable when certain fairness guarantees are desired. Even
when there is one type ($p=1$), no mechanism which assigns each item fully to
a single agent, can satisfy the basic fairness property of equal treatment of
equals, whereby, everything else being equal, agents with the same preferences
should receive the same share of the resources (e.g. two agents having
identical strict preferences). On the flip side, MGD does not satisfy weak-sd-
envy-freeness, while MRP and MPS both do.

## Related Work

MTRAs belong to a long line of research on mechanism design for multi-agent
resource allocation (see (?) for a survey), where the literature focuses on
the settings with a single type of items. ? (?) characterize serial
dictatorships for MTRAs by strategyproofness, neutrality, and non-bossiness.
The exchange economy of multi-type housing markets (?) is considered in (?; ?)
under lexicographic preferences, while ? (?) consider the exchange economy
where agents may consume multiple units of a single type of items under
lexicographic preferences.

Our work is the first to extend RP and PS under partial preferences, to the
best of our knowledge despite the vast literature on fractional assignments. ?
(?) consider RP under lexicographic preferences. The remarkable properties of
PS has encouraged extensions to several settings. ? (?) provide two
characterizations of PS: (1) by sd-efficiency, sd-envy-freeness, and upper
invariance, and (2) by ordinal fairness and non-wastefulness. In (?; ?), there
is a single type of items, and agents have multi-unit demands. In (?), the
supply of items may be different, while agents have unit demand and are
assumed to have lexicographic preferences. Other works extend PS to settings
where indifference relationships are allowed (?; ?). ? (?) consider fair
assignments when indifference allowed in preferences (but not
incomparabilities). ? (?), ? (?) extend PS to the housing markets problem (?).
? (?) study the complexity of computing fair and efficient allocations under
partial preferences represented by SCI-nets for allocation problems with a
single type of indivisible items.

### CP-net Preferences

Compact preference representations are a common approach to deal with the
preference formation and elicitation bottleneck faced in MTRAs, where the
number of bundles grows exponentially with the number of types. CP-nets (?)
are perhaps the most well-studied and natural compact preference
representation language allowing agents to express conditional (in)dependence
of their preferences over combinations of different types (see Example 1). CP-
nets are an important restriction on the domain of partial preferences, and
induce a partial ordering on the set of all bundles. ? (?) design mechanisms
for multi-type housing markets under lexicographic extensions of CP-nets.
Several works in the combinatorial voting literature assume CP-net preferences
(?; ?), and that agents’ CP-nets have a common dependence structure (see (?)
for a recent survey).

## Preliminaries

A multi-type resource allocation problem (MTRA) (?), is given by a tuple
$(N,M,R)$. Here,  (1) $N=\\{1,\dots,n\\}$is a set of agents.  (2)
$M=D_{1}\cup\dots\cup D_{p}$is a set of items of $p$ types, where for each
$i\leq p$, $D_{i}$ is a set of $n$ items of type $i$, and there is one unit of
supply of each item in $M$. We use $\mathcal{D}=D_{1}\times\dots\times D_{p}$
to denote the set of bundles.  (3) $R=(\succ_{j})_{j\leq n}$is a preference
profile, where for each $j\leq n$, $\succ_{j}$ represents the preference of
agent $j$, and $R_{-j}$ represents the preferences of agents in
$N\setminus\\{j\\}$. We use $\mathcal{R}$ to denote the set of all possible
preference profiles.

Bundles. For any type $i\leq p$, we use $k_{i}$ or $k_{t}$ to refer to the
$k$-th item of type $i$ where $t$ represents the name of type $i$. Each bundle
${\bf{x}}\in\mathcal{D}$ is a $p$-tuple, and we use $o\in{\bf{x}}$ to indicate
that bundle ${\bf{x}}$ contains item $o$. We define
$T=\\{D_{1},\dots,D_{p}\\}$, and for any $S\subseteq T$, we define
$\Pi_{S}=\bigtimes_{D\in S}D$, and $-S=T\setminus S$. For any $S\subseteq T$,
$\hat{S}\subseteq T\setminus S$, and any
${\bf{x}}\in\Pi_{S},{\bf{y}}\in\Pi_{\hat{S}}$, $({\bf{x}},{\bf{y}})$ denotes
the bundles consisting of all items in ${\bf{x}}$ and ${\bf{y}}$. For any
$S\subseteq T$, $D\in T\setminus S$, and any ${\bf{x}}\in S,o\in D$,
$(o,{\bf{x}})$ denotes the bundles consisting of $o$ and the items in
${\bf{x}}$.

Partial Preferences and Profiles. A partial preference $\succ$ is a partial
order over $\mathcal{D}$, which is an irreflexive, anti-symmetric, and
transitive binary relation. Given a partial preference $\succ$ over
$\mathcal{D}$, we define the corresponding preference graph, denoted by
$G_{\succ}$, to be the directed graph whose nodes are the bundles in
$\mathcal{D}$, and for every ${\bf{x}},{\bf{y}}\in\mathcal{D}$, there is an
directed edge $({\bf{x}},{\bf{y}})$ if and only if ${\bf{x}}\succ{\bf{y}}$ and
there exists no ${\bf{z}}\in\mathcal{D}$ such that ${\bf{x}}\succ{\bf{z}}$ and
${\bf{z}}\succ{\bf{y}}$. Given a partial order $\succ$ over $\mathcal{D}$, we
define the upper contour set of $\succ$ at a bundle ${\bf{x}}\in\mathcal{D}$
as $U(\succ,{\bf{x}})=\\{\hat{\bf{x}}:\hat{\bf{x}}\succ{\bf{x}}\text{ or
}\hat{\bf{x}}={\bf{x}}\\}$.

Acyclic CP-nets. A CP-net (?) $\succ$ over the set of variables $\mathcal{D}$
has two parts:  (i) a directed graph $G=(T,E)$ called the _dependency_ graph,
and  (ii) for each $i\leq p$, there is a conditional preference table
$CPT(D_{i})$ that contains a linear order $\succ^{{\bf{x}}}$ over $D_{i}$ for
each ${\bf{x}}\in\Pi_{Pa(D_{i})}$, where $Pa(D_{i})$ is the set of types
corresponding to the parents of $D_{i}$ in $G$.  When $G$ is (a)cyclic we say
that $\succ$ is a (a)cyclic CP-net. The partial order induced by an acyclic
CP-net $\succ$ over $\mathcal{D}$ is the transitive closure of
$\\{(o,{\bf{x}},{\bf{z}})\succ(\hat{o},{\bf{x}},{\bf{z}}):i\leq p;o,\hat{o}\in
D_{i};o\succ^{{\bf{x}}}\hat{o};{\bf{x}}\in\Pi_{Pa(D_{i})};{\bf{z}}\in\Pi_{-(Pa(D_{i})\cup\\{D_{i}\\})}\\}$.
A CP-profile is a profile of agents’ preferences, each of which is represented
by an acyclic CP-net. We say the acyclic CP-net with a trivial dependency
graph such that there is no edge in the dependency graph as independent CP-
net. An independent CP-profile is a profile of agents’ preferences, each of
which is represented by an independent acyclic CP-net.

Figure 1: Agent $1$’s preferences are represented by an acyclic CP-net with
dependence graph (a), and CP-tables (b), whose preference graph is in (c).
Agent $2$’s preferences are represented by the preference graph in (d).

######  Example 1.

Consider MTRA $(N,M,R)$ with $p=2$ types, food (F) and beverage (B), where
$N=\\{1,2\\},M=\\{1_{F},2_{F},1_{B},2_{B}\\}$, where $1_{B}$ is item $1$ of
type B and so on. Let agent $1$’s preference $\succ_{1}$ be represented by the
acyclic CP-net in Figure 1, where the dependency graph (Figure 1 (a)) shows
that her preference on type B depends on her assignment in type F. The
corresponding conditional preference tables (Figure 1 (b)) show that agent $1$
prefers $1_{B}$ with $1_{F}$, and $2_{B}$ with $2_{F}$. This induces the
preference graph in Figure 1 (c) which happens to be a linear order. Let agent
$2$’s preference $\succ_{2}$ be represented by the preference graph in Figure
1 (d) which represents a partial order, where $1_{F}2_{B}$ is the least
preferred bundle, and providing no information on the relative ordering of
other bundles.  ∎

Assignments. A discrete assignment $A:N\to\mathcal{D}$ is a one to one mapping
from agents to bundles such that no item is assigned to more than one agent. A
fractional allocation shows the fractional shares an agent acquires over
$\mathcal{D}$, represented by a vector
$p=[p_{\bf{x}}]_{{\bf{x}}\in\mathcal{D}}$, $p\in[0,1]^{1\times|\mathcal{D}|}$
such that $\sum_{{\bf{x}}\in\mathcal{D}}p_{\bf{x}}=1$. We use $\Pi$ to denote
the set of all possible fractional allocations on an agent. A fractional
assignment $P$ is a combination of all agents’ fractional allocations, and can
be represented by a matrix $P=[p_{j,{\bf{x}}}]_{j\leq
n,{\bf{x}}\in\mathcal{D}}$, $P\in[0,1]^{|N|\times|\mathcal{D}|}$, such that
(i) for every $j\leq n$, $\sum_{{\bf{x}}\in\mathcal{D}}p_{j,{\bf{x}}}=1$,
(ii) for every $o\in M$, $S_{o}=\\{{\bf{x}}:{\bf{x}}\in\mathcal{D}\text{ and
}o\in{\bf{x}}\\}$, $\sum_{j\leq n,{\bf{x}}\in S_{o}}p_{j,{\bf{x}}}=1$.  The
$j$-th row of $P$ represents agent $j$’s fractional allocation under $P$,
denoted $P(j)$. We use $\mathcal{P}$ to denote the set of all possible
fractional assignments.

Mechanisms. A mechanism $f:\mathcal{R}\to\mathcal{P}$ is a mapping from
profiles to fractional assignments. For any profile $R\in\mathcal{R}$, we use
$f(R)$ to refer to the fractional assignment output by $f$, and for any agent
$j\leq n$ and any bundle ${\bf{x}}\in\mathcal{D}$, we use $f(R)_{j,{\bf{x}}}$
to refer to the value of the element of the matrix $f(R)$ indexed by $j$ and
${\bf{x}}$.

Stochastic Dominance.  In this paper we will use the natural extension of
stochastic dominance (?) to compare fractional allocations.

######  Definition 1.

(stochastic dominance for fractional allocations) Given a partial preference
$\succ$ over $\mathcal{D}$, the stochastic dominance relation associated with
$\succ$, denoted $~{}\nobreak\succ^{sd}\allowbreak~{}$ is a weak ordering over
$\Pi$ such that for any pair of fractional allocations $p,q\in\Pi$, $p$
stochastically dominates $q$, denoted $p~{}\nobreak\succ^{sd}\allowbreak~{}q$,
if and only if for every ${\bf{x}}\in\mathcal{D}$, $\sum_{\hat{\bf{x}}\in
U(\succ,{\bf{x}})}p_{\hat{\bf{x}}}\geq\sum_{\hat{\bf{x}}\in
U(\succ,{\bf{x}})}q_{\hat{\bf{x}}}$.

We use $P~{}\nobreak\succ^{sd}_{j}\allowbreak~{}Q$ to denote
$P(j)~{}\nobreak\succ^{sd}_{j}\allowbreak~{}Q(j)$. We write
$P~{}\nobreak\succ^{sd}\allowbreak~{}Q$ if for every $j\leq n$, we have
$P~{}\nobreak\succ^{sd}_{j}\allowbreak~{}Q$.

######  Example 2.

Consider the situation in Example 1 with the three fractional assignments (1),
(2), and (3) shown below. The four upper contour sets for agent $1$ are
$\\{1_{F}1_{B}\\}$, $\\{1_{F}1_{B},1_{F}2_{B}\\}$,
$\\{1_{F}1_{B},1_{F}2_{B},2_{F}2_{B}\\}$, and
$\\{1_{F}1_{B},1_{F}2_{B},2_{F}1_{B},2_{F}2_{B}\\}$. The allocations of the
four upper contour sets for agent $1$ in assignment (2) are 0.5, 0.5, 1, 1,
respectively and in assignment (3) are 0, 0.5, 0.5, 1. The former is greater
than or equal to the latter respectively, and the same can be concluded for
agent $2$ by considering the upper contour sets $\\{1_{F}1_{B}\\}$,
$\\{2_{F}2_{B}\\}$, $\\{2_{F}1_{B}\\}$, and
$\\{1_{F}1_{B},1_{F}2_{B},2_{F}1_{B},2_{F}2_{B}\\}$. Hence assignment (2)
stochastically dominates (3). We can check that (2) does not dominate (1), and
that the reverse is true by considering the sets of $\\{1_{F}1_{B}\\}$ and
$\\{2_{F}1_{B}\\}$ for agent $2$.

| $1_{F}1_{B}$ | $1_{F}2_{B}$ | $2_{F}1_{B}$ | $2_{F}2_{B}$
---|---|---|---|---
Agent 1 | 0.5 | 0.5 | 0 | 0
Agent 2 | 0 | 0 | 0.5 | 0.5
(1) | $1_{F}1_{B}$ | $1_{F}2_{B}$ | $2_{F}1_{B}$ | $2_{F}2_{B}$
---|---|---|---|---
Agent 1 | 0.5 | 0 | 0 | 0.5
Agent 2 | 0.5 | 0 | 0 | 0.5
(2) | $1_{F}1_{B}$ | $1_{F}2_{B}$ | $2_{F}1_{B}$ | $2_{F}2_{B}$
---|---|---|---|---
Agent 1 | 0 | 0.5 | 0.5 | 0
Agent 2 | 0.5 | 0 | 0 | 0.5
(3)

∎

Desirable Properties. A fractional assignment $P$ satisfies:  (i) sd-
efficiency, if there is no fractional assignment $Q\neq P$ such that
$Q~{}\nobreak\succ^{sd}\allowbreak~{}P$,  (ii) ex-post-efficiency, if $P$ can
be represented as a probability distribution over _sd- efficient_ discrete
assignments,  (iii) sd-envy-freeness, if for every pair of agents
$j,\hat{j}\leq n$, $P(j)~{}\nobreak\succ^{sd}_{j}\allowbreak~{}P(\hat{j})$,
(iv) weak-sd-envy-freeness, if for every pair of agents $j,\hat{j}\leq n$,
$P(\hat{j})~{}\nobreak\succ^{sd}_{j}\allowbreak~{}P(j)\implies
P(j)=P(\hat{j})$,  (v) equal treatment of equals, if for every pair of agents
$j,\hat{j}\leq n$ such that agents $j$ and $\hat{j}$ have the same preference,
$P(j)=P(\hat{j})$,  (vi) ordinal fairness, if for every bundle
${\bf{x}}\in\mathcal{D}$ and every pair of agents $j,\hat{j}\leq n$ with
$P_{j,{\bf{x}}}>0$, $\sum_{\hat{\bf{x}}\in
U(\succ_{j},{\bf{x}})}P_{j,\hat{\bf{x}}}\leq\sum_{\hat{\bf{x}}\in
U(\succ_{\hat{j}},{\bf{x}})}P_{\hat{j},\hat{\bf{x}}}$, and  (vii)
decomposability, if $P$ can be represented as a probability distribution over
discrete assignments.

A mechanism $f$ satisfies $X\in$ {sd-efficiency, ex-post-efficiency, sd-envy-
freeness, weak-sd-envy-freeness, equal treatment of equals, ordinal fairness,
decomposability}, if for every $R\in\mathcal{R}$, $f(R)$ satisfies $X$. A
mechanism $f$ satisfies:  (i) sd-strategyproofnessif for every profile
$R\in\mathcal{R}$, every agent $j\leq n$, every $R^{\prime}\in\mathcal{R}$
such that $R^{\prime}=(\succ^{\prime}_{j},\succ_{-j})$, it holds that
$f(R)~{}\nobreak\succ^{sd}_{j}\allowbreak~{}f(R^{\prime})$, and  (ii) weak-sd-
strategyproofnessif for every profile $R\in\mathcal{R}$, every agent $j\leq
n$, every $R^{\prime}\in\mathcal{R}$ such that
$R^{\prime}=(\succ^{\prime}_{j},\succ_{-j})$, it holds that
$f(R^{\prime})~{}\nobreak\succ^{sd}_{j}\allowbreak~{}f(R)\implies
f(R^{\prime})(j)=f(R)(j)$.

Given any partial preferences $\succ$, we denote $\succ\mid_{\mathcal{B}}$ by
the restriction of $\succ$ to $\mathcal{B}\subseteq\mathcal{D}$, i.e.,
$\succ\mid_{\mathcal{B}}$ is a preference relation over $\mathcal{B}$ such
that for all ${\bf{x}},{\bf{y}}\in\mathcal{B}$,
${\bf{x}}\succ\mid_{\mathcal{B}}{\bf{y}}\Leftrightarrow{\bf{x}}\succ{\bf{y}}$.
Then for any $j\leq n$, $\succ^{\prime}_{j}$ is an upper invariant
transformation of $\succ_{j}$ at ${\bf{x}}\in\mathcal{D}$ under a fractional
assignment $P$ if for some $\mathcal{Z}\subseteq\\{{\bf{y}}\in\mathcal{D}\mid
P_{j,{\bf{y}}}=0\\}$,
$U(\succ^{\prime}_{j},{\bf{x}})=U(\succ_{j},{\bf{x}})\setminus\mathcal{Z}$ and
$\succ^{\prime}_{j}\mid_{U(\succ^{\prime}_{j},{\bf{x}})}=\succ_{j}\mid_{U(\succ^{\prime}_{j},{\bf{x}})}$.
A mechanism $f$ satisfies upper invariance if it holds that
$f(R)_{\hat{j},{\bf{x}}}=f(R^{\prime})_{\hat{j},{\bf{x}}}$ for every
$\hat{j}\leq n$, $j\leq n$, $R\in\mathcal{R}$, $R^{\prime}\in\mathcal{R}$, and
${\bf{x}}\in\mathcal{D}$, such that
$R^{\prime}=(\succ^{\prime}_{j},\succ_{-j})$ and $\succ^{\prime}_{j}$ is an
upper invariant transformation of $\succ_{j}$ at ${\bf{x}}$ under $f(R)$.

## Mechanisms for MTRAs with Partial Preferences

In this section, we propose MRP (Algorithm 1 as extension of RP), MPS
(Algorithm 2, as extension of PS), and MGD (Algorithm 3), which can be seen as
not only an eating algorithm but a special random priority algorithm.

The three mechanisms operate on a modified preference profile of strict
preferences, where for every agent with partial preference $\succ$, an
arbitrary deterministic topological sorting is applied to obtain a strict
ordering $\succ^{\prime}$ over $\mathcal{D}$, such that for any pair of
bundles ${\bf{x}},{\bf{y}}\in\mathcal{D}$,
${\bf{x}}\succ{\bf{y}}\implies{\bf{x}}\succ^{\prime}{\bf{y}}$. Given a strict
order $\succ^{\prime}$ obtained in this way, and remaining $M^{\prime}$, we
use $Ext(\succ^{\prime},M^{\prime})$ to denote the first available bundle in
$\succ^{\prime}$, which we refer to as the agents’ favorite bundle. It is easy
to see that no available bundle is preferred over
$Ext(\succ^{\prime},M^{\prime})$ according to $\succ$.

Our results apply to arbitrary deterministic topological sortings (induced by
a fixed ordering over items), even though different topological sortings may
lead to different outputs.

Algorithm 1 MRP

An MTRA $(N,M,R)$

Assignment $P$

1:For each $j\leq n$, compute a linear ordering $\succ^{\prime}_{j}$
corresponding to a deterministic topological sort of $G_{\succ_{j}}$.

2:$P\leftarrow 0^{|N|\times|\mathcal{D}|}$ and $M^{\prime}\leftarrow M$.

3:Pick a random priority order $\rhd$ over agents.

4:Successively pick a highest priority agent $j^{*}$ according to $\rhd$.
${\bf{x}}^{*}\leftarrow Ext(\succ^{\prime}_{j^{*}},M^{\prime})$ and set
$P_{j^{*},{\bf{x}}^{*}}\leftarrow 1$. Remove $j^{*}$, and remove all items
contained by ${\bf{x}}^{*}$ in $M^{\prime}$.

5:return $P$

Given an instance of MTRA with agents’ partial preferences, MRP fixes an
arbitrary deterministic topological sorting $\succ^{\prime}$ of agents’
preferences, and sorts agents uniformly at random. Then agents get one unit of
their favorite available bundle from the remaining $M^{\prime}$ in turns as in
RP.

Algorithm 2 MPS

An MTRA $(N,M,R)$

Assignment $P$

1:For each $j\leq n$, compute a linear ordering $\succ^{\prime}_{j}$
corresponding to a deterministic topological sort of $G_{\succ_{j}}$.

2:$P\leftarrow 0^{|N|\times|\mathcal{D}|}$ and $M^{\prime}\leftarrow M$. For
every $o\in M$, $\text{supply}(o)\leftarrow 1$, $\nobreak
B\allowbreak\leftarrow\emptyset$,
$\nobreak\text{progress}\allowbreak\leftarrow 0$.

3:while $M^{\prime}\neq\emptyset$ do

4: $\nobreak top(j)\allowbreak\leftarrow Ext(\succ^{\prime}_{j},M^{\prime})$
for every agent $j\leq n$.

5: Consume. 5.1: For each $o\in M^{\prime}$,
$\nobreak\text{consumers}(o)\allowbreak\leftarrow|\\{j\in N:o\text{ is in
}\nobreak top(j)\allowbreak\\}|$. 5.2:
$\nobreak\text{progress}\allowbreak\leftarrow\min_{o\in
M^{\prime}}\frac{\text{supply}(o)}{\nobreak\text{consumers}(o)\allowbreak}$.
5.3: For each $j\leq n$, $P_{j,\nobreak top(j)\allowbreak}\leftarrow
P_{j,\nobreak top(j)\allowbreak}+\nobreak\text{progress}\allowbreak$ 5.4: For
each $o\in M^{\prime}$,
$\text{supply}(o)\leftarrow\text{supply}(o)-{\nobreak\text{progress}\allowbreak\times\nobreak\text{consumers}(o)\allowbreak}$.

6: $\nobreak B\allowbreak\leftarrow\arg\min_{o\in
M^{\prime}}\frac{\text{supply}(o)}{\nobreak\text{consumers}(o)\allowbreak}$,
$M^{\prime}\leftarrow M^{\prime}\setminus B$

7:return $P$

Given an instance of MTRA with agents’ partial preferences, MPS involves
applying the PS mechanism to a modified profile $\succ^{\prime}$ over
$\mathcal{D}$ using an arbitrary deterministic topological sorting in multiple
rounds as follows. In each round, each agent consumes their favorite available
bundle by consuming each item in the bundle at an uniform rate of one unit of
an item per type per unit of time, until one of the bundles being consumed
becomes unavailable because the supply for one of the items in it is
exhausted.

Algorithm 3 MGD

An MTRA $(N,M,R)$

Assignment $P$

1:For each $j\leq n$, compute a linear ordering $\succ^{\prime}_{j}$
corresponding to a deterministic topological sort of $G_{\succ_{j}}$.

2:$P\leftarrow 0^{|N|\times|\mathcal{D}|}$ and $M^{\prime}\leftarrow M$.

3:for $j=1$ to $n$ do

4: $\nobreak top(j)\allowbreak\leftarrow Ext(\succ^{\prime}_{j},M^{\prime})$.

5: For each $j^{\prime}\in Group(j,\succ^{\prime})$, let
$P_{j^{\prime},\nobreak
top(j)\allowbreak}\leftarrow\frac{1}{|Group(j,\succ^{\prime})|}$

6: $M^{\prime}\leftarrow M^{\prime}\setminus\\{o\in M:o\text{ is in }\nobreak
top(j)\allowbreak\\}$.

7:return $P$

Given an instance of MTRA with agents’ partial preferences, MGD proceeds by
operating on an arbitrary deterministic topological sorting $\succ^{\prime}$.
Let $Group(j,\succ^{\prime})$ denote the set of all agents who have the same
order with agent $j$ in $\succ^{\prime}$. MGD proceeds in $n$ rounds as
follows. In each round $j\leq n$, agent $j$ comes and invites other agents
with the same topological sort $\succ^{\prime}_{j}$ to consume her favorite
available bundle $Ext(\succ^{\prime}_{j},M^{\prime})$ with
$\frac{1}{|Group(j,\succ^{\prime})|}$ unit of time and one unit of eating
rate. We present MGD as its eating algorithm version here and show that
$MGD{}(R)$ is the expected result of a special random priority algorithm when
we prove its decomposability.

######  Example 3.

Consider the situation in Example 1, the topological sort of agent $1$’s
preference is
$1_{F}1_{B}\succ^{\prime}1_{F}2_{B}\succ^{\prime}2_{F}2_{B}\succ^{\prime}2_{F}1_{B}$
but both
$2_{F}1_{B}\succ^{\prime}1_{F}1_{B}\succ^{\prime}2_{F}2_{B}\succ^{\prime}1_{F}2_{B}$
and
$1_{F}1_{B}\succ^{\prime}2_{F}2_{B}\succ^{\prime}2_{F}1_{B}\succ^{\prime}1_{F}2_{B}$
can be the topological sort of agent $2$’s preference. If the topological sort
of agent $2$ is the former, in MPS, agent $1$ consumes $1_{F}1_{B}$ and agent
$2$ consumes $2_{F}1_{B}$ at the beginning. When they both consume $0.5$
fraction, $1_{B}$ is exhausted. $1_{F}1_{B}$ and $2_{F}1_{B}$ become
unavailable. They turn to identify the next bundles in line $4$. For example,
the first two bundles $2_{F}1_{B}$ and $1_{F}1_{B}$ are unavailable for agent
$2$, so she turns to the third bundle $2_{F}2_{B}$. Agent $1$ turns to
$1_{F}2_{B}$. Then MPS goes to next round of consumption until all left items
are exhausted at the same time. The result is shown in assignment (1) in
Example 2. However, if the topological sort of agent $2$ is the latter, agent
$1$ and agent $2$ both get $0.5$ of $1_{F}1_{B}$ and $0.5$ of $2_{F}2_{B}$ as
assignment (2) shows. It is easy to check that MRP has the same conclusion.
Suppose agent $1$ has the same partial preference with agent $2$ in Example 1
in MGD. If their topological sorts are both the former, agent $1$ invites
agent $2$ to consume $2_{F}1_{B}$ in round 1 and agent $2$ invites agent $1$
to consume $1_{F}2_{B}$ in round 2. But if their topological sorts are both
the latter, agent $1$ invites agent $2$ to consume $1_{F}1_{B}$ in round 1 and
agent $2$ invites agent $1$ to consume $2_{F}2_{B}$ in round 2.  ∎

There is an unique best available bundle w.r.t. any acyclic CP-net preference
and remaining supply of items, which can be computed in polynomial time by
induction on the types according to the dependency graph as we show in
Proposition 1. This is an extension of the well-known result of ? (?) that
there is a unique best bundle w.r.t. any acyclic CP-net.

######  Proposition 1.

Let $T^{\prime}=\\{D^{\prime}_{1}\subseteq D_{1},\dots,D^{\prime}_{p}\subseteq
D_{p}\\}$, $\mathcal{D}^{\prime}=\Pi_{T^{\prime}}$, and let $\succ$ be any
acyclic CP-net over $\mathcal{D}$. Then, there exists unique
${\bf{x}}\in\mathcal{D}^{\prime}$ such that for every
${\bf{y}}\neq{\bf{x}}\in\mathcal{D}^{\prime}$, ${\bf{x}}\succ{\bf{y}}$.

All missing proofs can be found in Appendix.

We use $Top(\succ,M^{\prime})$ to denote the best available bundle in
remaining $M^{\prime}$ given an acyclic CP-net $\succ$. Under the domain
restriction of acyclic CP-net preferences, for any topological sorting
algorithms, $Ext(\succ^{\prime}_{j},M^{\prime})$ is exact
$Top(\succ_{j},M^{\prime})$ for any $M^{\prime}$ and $j\leq n$ by Proposition
1. Therefore, we can remove line $1$ and instead
$Ext(\succ^{\prime}_{j},M^{\prime})$ with $Top(\succ_{j},M^{\prime})$ in the
three mechanisms to save the time and space.

######  Proposition 2.

MRP, MPS and MGD run in $O(n^{p+1})$ time.

We note that the size of the preference representation is $O(n^{p+1})$, and
forms a part of the input.

## Properties under General Partial Preferences

######  Theorem 1.

Under general partial preferences, $MRP{}$ satisfies ex-post-efficiency, weak-
sd-envy-freeness, equal treatment of equals, weak-sd-strategyproofness, and
decomposability.

The proof of weak-sd-envy-freeness involves showing that for any two agents
$j$ and $\hat{j}$, agents $j$ and $\hat{j}$ receive equal shares of every
bundle in expectation, due to a bijective mapping from the set of orders where
$j$ picks before $\hat{j}$ and vice-versa.

######  Remark 1.

Under general partial preferences, MRP is not upper invariant and sd-
strategyproof.

Given an assignment $P$ and a partial preference profile $R$, for any
${\bf{x}},\hat{\bf{x}}\in\mathcal{D}$, $({\bf{x}},\hat{\bf{x}})$ is an
_improvable tuple_ , denoted by $Imp(P,R)$, if there exists an agent $j<n$
such that ${\bf{x}}\succ_{j}\hat{\bf{x}}$ and $p_{j,\hat{\bf{x}}}>0$. We use
$Imp(P)$ for short when the preferences are clear from the context. ? (?) show
that an assignment $P$ is sd-efficient if and only if the binary relation
$Imp(P)$ has no cycle in single-type resources allocations, but the sufficient
condition fails to hold for MTRAs. As Example 2 shows, assignment (3) is sd-
inefficient, but the set of the improvable tuples,
$\\{(1_{F}1_{B},1_{F}2_{B}),(1_{F}1_{B},$ $2_{F}1_{B}),$
$(1_{F}2_{B},2_{F}1_{B}),(2_{F}2_{B},2_{F}1_{B})\\}$, has no cycle.

######  Theorem 2.

Under general partial preferences, $MPS{}$ satisfies sd-efficiency, weak-sd-
envy-freeness, and equal treatment of equals.

To prove the sd-efficiency of MPS, we relax the cycle from bundles to items
and find a sufficient condition for sd-efficiency in MTRAs under general
partial preferences. For example in assignment (3), agent $1$ can extract
$1_{B}$ from $2_{F}1_{B}$ to match $1_{F}$ and extract $2_{B}$ from
$1_{F}2_{B}$ to match $2_{F}$ to improve her result. We show MPS satisfies sd-
efficiency by proving MPS satisfies the sufficient condition. We find that one
agent does not envy others at the first bundle of her topological sort since
she consumes the bundle from the beginning to the end when the bundle is
exhausted. Based on that, We can prove she does not envy others at any upper
contour set under MPS by induction on bundles under the topological sorting.

######  Remark 2.

MPS is not ex-post-efficient since its output may not be decomposable when
coming to multi-type resources. MPS is not ordinally fair, sd-envy-free and
upper invariant under general partial preferences.

PS is both sd-efficient and decomposable in single-type resources allocations
(?), but not decomposable in MTRAs. Serial dictatorship (?; ?) maintains both
sd-efficiency and decomposability even in MTRAs but perform badly in fairness.
Thankfully, MGD not only satisfies sd-efficiency and decomposability but the
common requirement for fairness, equal treatment of equals.

######  Theorem 3.

Under general partial preferences, $MGD{}$ satisfies sd-efficiency, ex-post-
efficiency, equal treatment of equals, and decomposability.

When agents have different topological sorts with each other, MGD comes to
serial dictatorship. Since the dictator only invite agents who have the same
topological sort with her to share her bundle, the sd-efficiency of serial
dictatorship maintains in MGD. Since agents with the same preference have the
same topological sorts, MGD satisfies equal treatment of equals. MGD is
decomposable since its output can be seen as an expected result of a special
random priority algorithm. Decomposability and sd-efficiency induce ex-post-
efficiency (?).

######  Remark 3.

MGD is not ordinally fair, weak-sd-envy-free, upper invariant and weak-sd-
strategyproof even in single-type resources allocations under linear
preferences.

PS is both sd-efficient and sd-envy-free under linear preferences (?) but this
is no longer true under general partial preferences, as the impossibility
result in Proposition 3 shows.

######  Proposition 3.

No mechanism can satisfy both sd-efficiency and sd-envy-freeness under general
partial preferences.

## Properties under Acyclic CP-net Preferences

######  Theorem 4.

Given any CP-profile $R$, $MRP{}(R)$ is sd-strategyproof.

###### Proof.

Let $P$ and $P^{\prime}$ be the expected assignments of MRP given the CP-
profile $R$ and $R^{\prime}\in\mathcal{R}$ such that
$R^{\prime}=(\succ_{j}^{\prime},\succ_{-j})$ for some $j\leq n$. For an
arbitrary fixed priority order, in any agent $j$’s turn, the set of available
bundles is the same under $R$ and $R^{\prime}$. By Proposition 1, the best
available bundle is also the same and unique. If $j$ lies, she may get a
smaller share of her best available bundle. Therefore, the result of a lie is
stochastic dominated by the result of truthfulness. Since this is true for any
fixed priority order, $P^{\prime}$ is stochastic dominated by $P$. ∎

######  Proposition 4.

Given any CP-profile $R$, $MRP{}(R)$ is upper invariant for any other CP-
profile $R^{\prime}$.

Thanks to Proposition 1, given any upper invariant transformation at some
${\bf{y}}\in\mathcal{D}$, if ${\bf{y}}$ is available in the misreport agent’s
turn, she gets the same bundle despite her lie. Otherwise if ${\bf{y}}$ is
unavailable, the lie does not affect the assignment of ${\bf{y}}$.

######  Theorem 5.

Given any CP-profile $R$, $MPS{}(R)$ is sd-envy-free and ordinally fair.

###### Proof.

W.l.o.g we only prove the case between agent $1$ and agent $2$. Let
$P=MPS{}(R)$. Let
$\mathcal{D}_{1}=\\{{\bf{x}}\in\mathcal{D}:P_{1,{\bf{x}}}>0\\}$ and
$n_{1}=|\mathcal{D}_{1}|$. By Proposition 1, we have an order over
$\mathcal{D}_{1}$ such that
${\bf{x}}_{1}\succ_{1}{\bf{x}}_{2}\succ_{1}\cdots\succ_{1}{\bf{x}}_{n_{1}}$,
${\bf{x}}_{i}\in\mathcal{D}_{1}$ for any $i\leq n_{1}$. For agent $2$, we can
define $\mathcal{D}_{2}$ and $n_{2}$ and have an order over $\mathcal{D}_{2}$,
$\hat{\bf{x}}_{1}\succ_{2}\hat{\bf{x}}_{2}\succ_{2}\cdots\succ_{2}\hat{\bf{x}}_{n_{2}}$,
similarly.

_(1) sd-envy-freeness._ We need to prove
$P(1)~{}\nobreak\succ^{sd}_{1}\allowbreak~{}P(2)$. For any
${\bf{y}}\in\mathcal{D}$, let ${\bf{x}}_{i}$ be the least favorable bundle of
agent $1$ in $U(\succ_{1},{\bf{y}})\cap\mathcal{D}_{1}$. If $i=n_{1}$,
$\sum_{{\bf{x}}\in
U(\succ_{1},{\bf{y}})}P_{1,{\bf{x}}}=\sum_{k=1}^{n_{1}}P_{1,{\bf{x}}_{k}}=1\geq\sum_{{\bf{x}}\in
U(\succ_{1},{\bf{y}})}P_{2,{\bf{x}}}$. If $i<n_{1}$, ${\bf{x}}_{i+1}\notin
U(\succ_{1},{\bf{y}})$. When agent $1$ starts to consume ${\bf{x}}_{i+1}$,
$\hat{\bf{y}}$ is unavailable for any $\hat{\bf{y}}\in U(\succ_{1},{\bf{y}})$.
Otherwise by Proposition 1, we have ${\bf{x}}_{i+1}\succ_{1}\hat{\bf{y}}$ or
${\bf{x}}_{i+1}=\hat{\bf{y}}$ both indicating ${\bf{x}}_{i+1}\in
U(\succ_{1},{\bf{y}})$, a contradiction. Suppose $t({\bf{x}}_{i})$ be the time
when ${\bf{x}}_{i}$ is exhausted and agent $1$ starts to consume
${\bf{x}}_{i+1}$. Then $\sum_{{\bf{x}}\in
U(\succ_{1},{\bf{y}})}P_{1,{\bf{x}}}=\sum_{k=1}^{i}P_{1,{\bf{x}}_{k}}=t({\bf{x}}_{i})\geq\sum_{{\bf{x}}\in
U(\succ_{1},{\bf{y}})}P_{2,{\bf{x}}}$ for any ${\bf{y}}\in\mathcal{D}$. Hence
$P(1)\succ_{1}P(2)$.

_(2) ordinal fairness._ For any ${\bf{y}}\in\mathcal{D}_{1}$, we need to prove
$\sum_{{\bf{x}}\in U(\succ_{1},{\bf{y}})}P_{1,{\bf{x}}}\leq\sum_{{\bf{x}}\in
U(\succ_{2},{\bf{y}})}P_{2,{\bf{x}}}$. For any
${\bf{x}}_{i}\in{\mathcal{D}}_{1}$, suppose that when ${\bf{x}}_{i}$ is
exhausted, agent $2$ is consuming $\hat{\bf{x}}_{\hat{i}}\in{\mathcal{D}}_{2}$
or $\hat{\bf{x}}_{\hat{i}}$ is exhausted at the same time. If
$\hat{\bf{x}}_{\hat{i}}={\bf{x}}_{i}$, we have $\sum_{{\bf{x}}\in
U(\succ_{1},{\bf{x}}_{i})}P_{1,{\bf{x}}}=\sum_{{\bf{x}}\in
U(\succ_{2},{\bf{x}}_{i})}P_{2,{\bf{x}}}$. If
$\hat{\bf{x}}_{\hat{i}}\neq{\bf{x}}_{i}$, since ${\bf{x}}_{i}$ is available
when agent $2$ starts to consume $\hat{\bf{x}}_{\hat{i}}$, we have
$\hat{\bf{x}}_{k}\succ_{2}{\bf{x}}_{i}$ for any $k\leq\hat{i}$. Hence,
$\sum_{{\bf{x}}\in
U(\succ_{1},{\bf{x}}_{i})}P_{1,{\bf{x}}}=\sum_{k=1}^{i}P_{1,{\bf{x}}_{k}}\leq\sum_{k=1}^{\hat{i}}P_{2,\hat{\bf{x}}_{k}}\leq\sum_{{\bf{x}}\in
U(\succ_{2},{\bf{x}}_{i})}P_{2,{\bf{x}}}$. Therefore, for any
${\bf{y}}\in\mathcal{D}$ with $P_{1,{\bf{y}}}>0$, we have $\sum_{{\bf{x}}\in
U(\succ_{1},{\bf{y}})}P_{1,{\bf{x}}}\leq\sum_{{\bf{x}}\in
U(\succ_{2},{\bf{y}})}P_{2,{\bf{x}}}$. ∎

? (?) shows that ordinal fairness characterizes PS when we come to single-type
resources. However, this is not the case in MTRAs: for example, if two agents’
preferences are both as (c) in Figure 1 shows, the result that two agents both
get 0.5 $1_{F}2_{B}$ and 0.5 $2_{F}1_{B}$ is ordinally fair but not the output
of MPS.

######  Proposition 5.

Given any CP-profile $R$, $MPS{}(R)$ is upper invariant for any other CP-
profile $R^{\prime}$.

Given any upper invariant transformation at some ${\bf{y}}\in\mathcal{D}$, we
show the consumption processes are identical until ${\bf{y}}$ is exhausted
whether the misreport agent is truthful or lies, by induction on the bundles
consumed by the misreport agent under $R$. Details are in the Appendix.

######  Remark 4.

MPS is not weak-sd-strategyproof under acyclic CP-net profiles even when all
agents have a shared dependency graph, and agents are only allowed to
misreport their CPTs.

######  Proposition 6.

Given any independent CP-profile $R$, MPS(R) is weak-sd-strategyproof for any
profile $R^{\prime}$.

Independent CP-nets are a special case of acyclic CP-nets where the dependency
graph has no edges, and the CPT for each type represents preferences over
items of that type without any conditional dependencies on the allocation of
items of other types. Strict preferences over a single type of resources are a
special case where $p=1$. Moreover, when $p=1$, MPS is equivalent to PS, and
at any point during the execution of MPS agents consume their favorite
remaining item until it is exhausted. The proof for 6 is along similar lines
to the proof of weak-sd-strategyproofness of PS due to (?).

## Conclusion and Future Work

We proposed and studied MRP and MPS as extensions of RP and PS to MTRAs. We
also proposed MGD that is both sd-efficient and decomposable. For future work,
we are interested in axiomatic characterization of MRP, MPS and MGD. More
generally, designing desirable mechanism for MTRAs is still an interesting and
challenging open question.

## Acknowledgments

We are grateful to the anonymous reviewers for their helpful comments. LX
acknowledges NSF #1453542 and #1716333 for support. YC acknowledges NSFC under
Grants 61772035, 61751210, and 61932001, and the National Science and
Technology Major Project for IND (investigational new drug) under Grant
2018ZX09201-014 for support. HW acknowledges NSFC under Grants 61572003 and
61972005, and the National Key R&D Program under Grants 2018YFB1003904 and
2018YFC1314200 for support.

## References

  * [Abdulkadiroğlu and Sönmez 1998] Abdulkadiroğlu, A., and Sönmez, T.  1998\.  Random serial dictatorship and the core from random endowments in house allocation problems.  Econometrica 66(3):689–702.
  * [Athanassoglou and Sethuraman 2011] Athanassoglou, S., and Sethuraman, J.  2011\.  House allocation with fractional endowments.  International Journal of Game Theory 40(3):481–513.
  * [Aziz et al. 2015] Aziz, H.; Gaspers, S.; Mackenzie, S.; and Walsh, T.  2015\.  Fair assignment of indivisible objects under ordinal preferences.  Artificial Intelligence 227:71–92.
  * [Bogomolnaia and Heo 2012] Bogomolnaia, A., and Heo, E. J.  2012\.  Probabilistic assignment of objects: Characterizing the serial rule.  Journal of Economic Theory 147(5):2072–2082.
  * [Bogomolnaia and Moulin 2001] Bogomolnaia, A., and Moulin, H.  2001\.  A new solution to the random assignment problem.  Journal of Economic Theory 100(2):295–328.
  * [Bogomolnaia 2015] Bogomolnaia, A.  2015\.  Random assignment: Redefining the serial rule.  Journal of Economic Theory 158:308–318.
  * [Boutilier et al. 2004a] Boutilier, C.; Brafman, R.; Domshlak, C.; Hoos, H.; and Poole, D.  2004a.  CP-nets: A tool for representing and reasoning with conditional ceteris paribus statements.  Journal of Artificial Intelligence Research 21:135–191.
  * [Boutilier et al. 2004b] Boutilier, C.; Brafman, R.; Domshlak, C.; Hoos, H.; and Poole, D.  2004b.  Preference-based constrained optimization with CP-nets.  Computational Intelligence 20(2):137–157.
  * [Bouveret, Endriss, and Lang 2010] Bouveret, S.; Endriss, U.; and Lang, J.  2010\.  Fair division under ordinal preferences: Computing envy-free allocations of indivisible goods.  In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI-2010).
  * [Brams and Taylor 1996] Brams, S. J., and Taylor, A. D.  1996\.  Fair Division: From Cake-Cutting to Dispute Resolution.  Cambridge University Press.
  * [Brams, Jones, and Klamler 2006] Brams, S. J.; Jones, M. A.; and Klamler, C.  2006\.  Better ways to cut a cake.  Notices of the AMS 53(11):1314–1321.
  * [Chevaleyre et al. 2006] Chevaleyre, Y.; Dunne, P. E.; Endriss, U.; Lang, J.; Lemaitre, M.; Maudet, N.; Padget, J.; Phelps, S.; Rodríguez-Aguilar, J. A.; and Sousa, P.  2006\.  Issues in multiagent resource allocation.  Informatica 30:3–31.
  * [Elster 1992] Elster, J.  1992\.  Local justice: How institutions allocate scarce goods and necessary burdens.  Russell Sage Foundation.
  * [Fujita et al. 2015] Fujita, E.; Lesca, J.; Sonoda, A.; Todo, T.; and Yokoo, M.  2015\.  A complexity approach for core-selecting exchange with multiple indivisible goods under lexicographic preferences.  In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 907–913.
  * [Ghodsi et al. 2011] Ghodsi, A.; Zaharia, M.; Hindman, B.; Konwinski, A.; Shenker, S.; and Stoica, I.  2011\.  Dominant resource fairness: Fair allocation of multiple resource types.  In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, 323–336.
  * [Hashimoto et al. 2014] Hashimoto, T.; Hirata, D.; Kesten, O.; Kurino, M.; and Ünver, M. U.  2014\.  Two axiomatic approaches to the probabilistic serial mechanism.  Theoretical Economics 9(1):253–277.
  * [Hatfield 2009] Hatfield, J. W.  2009\.  Strategy-proof, efficient, and nonbossy quota allocations.  Social Choice and Welfare 33(3):505–515.
  * [Heo and Yılmaz 2015] Heo, E. J., and Yılmaz, Ö.  2015\.  A characterization of the extended serial correspondence.  Journal of Mathematical Economics 59:102–110.
  * [Heo 2014] Heo, E. J.  2014\.  Probabilistic assignment problem with multi-unit demands: A generalization of the serial rule and its characterization.  Journal of Mathematical Economics 54:40–47.
  * [Hosseini and Larson 2019] Hosseini, H., and Larson, K.  2019\.  Multiple assignment problems under lexicographic preferences.  In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-19).
  * [Katta and Sethuraman 2006] Katta, A.-K., and Sethuraman, J.  2006\.  A solution to the random assignment problem on the full preference domain.  Journal of Economic theory 131(1):231–250.
  * [Lang and Xia 2016] Lang, J., and Xia, L.  2016\.  Voting in combinatorial domains.  In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A., eds., Handbook of Computational Social Choice. Cambridge University Press.  chapter 9.
  * [Lang 2007] Lang, J.  2007\.  Vote and aggregation in combinatorial domains with structured preferences.  In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI), 1366–1371.
  * [Mackin and Xia 2016] Mackin, E., and Xia, L.  2016\.  Allocating indivisible items in categorized domains.  In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16), 359–365.
  * [Monte and Tumennasan 2015] Monte, D., and Tumennasan, N.  2015\.  Centralized allocation in multiple markets.  Journal of Mathematical Economics 61:74—85.
  * [Moulin 1995] Moulin, H.  1995\.  Cooperative Microeconomics: A Game-Theoretic Introduction.  Prentice Hall.
  * [Procaccia 2013] Procaccia, A. D.  2013\.  Cake cutting: Not just child’s play.  Communications of the ACM 56(7):78–87.
  * [Rossi, Venable, and Walsh 2004] Rossi, F.; Venable, K. B.; and Walsh, T.  2004\.  mCP nets: Representing and reasoning with preferences of multiple agents.  In Proceedings of AAAI-04, 729–734.
  * [Saban and Sethuraman 2014] Saban, D., and Sethuraman, J.  2014\.  A note on object allocation under lexicographic preferences.  Journal of Mathematical Economics 50:283–289.
  * [Sandomirskiy and Segal-Halevi 2019] Sandomirskiy, F., and Segal-Halevi, E.  2019\.  Fair division with minimal sharing.  arXiv preprint arXiv:1908.01669.
  * [Shapley and Scarf 1974] Shapley, L., and Scarf, H.  1974\.  On cores and indivisibility.  Journal of Mathematical Economics 1(1):23–37.
  * [Sikdar, Adali, and Xia 2017] Sikdar, S.; Adali, S.; and Xia, L.  2017\.  Mechanism design for multi-type housing markets.  In Proceedings of the 31st AAAI Conference on Artificial Intelligence.
  * [Sikdar, Adali, and Xia 2018] Sikdar, S.; Adali, S.; and Xia, L.  2018\.  Top-trading-cycles mechanisms with acceptable bundles.  In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, AAAI, volume 18.
  * [Yilmaz 2009] Yilmaz, Ö.  2009\.  Random assignment under weak preferences.  Games and Economic Behavior 66(1):546–558.

##  Appendix A Appendix

#### Proof of Proposition 1.

See 1

###### Proof.

Given any acyclic CP-net $\succ$, suppose the dependency graph in the CP-net
is $G$. As $G$ has no circle, there is $D_{i_{1}}\in T$ such that $D_{i_{1}}$
has no parent and there is $o_{1}$ in $D_{i_{1}}^{\prime}$ such that the agent
prefers $o_{1}$ than any other item in $D_{i_{1}}^{\prime}$. Then there is
$D_{i_{2}}\in T$ such that $Pa(D_{i_{2}})\subseteq\\{D_{i_{1}}\\}$. By
$CPT(D_{i_{2}})$, we know the agent has a linear preference over $D_{i_{2}}$
given $o_{1}$. So there is $o_{2}\in D_{i_{2}}^{\prime}$ such that the agent
prefers $o_{2}$ than any other item in $D_{i_{2}}^{\prime}$ when she is
holding $o_{1}$. The same procedure can be easily adapted to obtain $o_{3}$ in
$D_{i_{3}}^{\prime}$, $o_{4}$ in $D_{i_{4}}^{\prime}$,…, $o_{p}$ in
$D_{i_{p}}^{\prime}$.

We claim that $o_{1}o_{2}...o_{p}\succ\hat{o}_{1}\hat{o}_{2}...\hat{o}_{p}$
for any $\hat{o}_{1}\hat{o}_{2}...\hat{o}_{p}\in\mathcal{D}^{\prime}$ and
$\hat{o}_{1}\hat{o}_{2}...\hat{o}_{p}\neq o_{1}o_{2}...o_{p}$. If
$o_{1}\neq\hat{o}_{1}$, the agent prefers $o_{1}$ than $\hat{o}_{1}$ and we
have
$o_{1}\hat{o}_{2}...\hat{o}_{p}\succ\hat{o}_{1}\hat{o}_{2}...\hat{o}_{p}$,
else we have
$o_{1}\hat{o}_{2}...\hat{o}_{p}=\hat{o}_{1}\hat{o}_{2}...\hat{o}_{p}$. Since
$Pa(D_{i_{k+1}})\subseteq\\{D_{i_{1}},D_{i_{2}},...,D_{i_{k}}\\}$ for any
$k<p$, the agent prefers $o_{k+1}$ than $\hat{o}_{k+1}$ given
$o_{1},o_{2},...,o_{k}$ or $o_{k+1}=\hat{o}_{k+1}$. Therefor,
$o_{1}o_{2}...o_{k}o_{k+1}\hat{o}_{k+2}...\hat{o}_{p}\succ
o_{1}o_{2}...o_{k}\hat{o}_{k+1}\hat{o}_{k+2}...\hat{o}_{p}$ or
$o_{1}o_{2}...o_{k}o_{k+1}\hat{o}_{k+2}...\hat{o}_{p}=o_{1}o_{2}...o_{k}\hat{o}_{k+1}\hat{o}_{k+2}...\hat{o}_{p}$.
Since $\succ$ is transitive and
$o_{1}o_{2}...o_{p}\neq\hat{o}_{1}\hat{o}_{2}...\hat{o}_{p}$, we have
$o_{1}o_{2}...o_{p}\succ\hat{o}_{1}\hat{o}_{2}...\hat{o}_{p}$. Since the
selection of $o_{k}$ ($k\leq p$) only depends on the selections of its
parents, $o_{1}o_{2}...o_{p}$ is unique.

∎

#### Proof of Proposition 2.

See 2

###### Proof.

_(1) MRP._ For a preference graph with $n^{p}$ nodes, we can get its
topological sort in $O(n^{p})$ via a queue and a vector to mark. Hence, the
running time of line 1 in MRP is $O(n^{p+1})$. Line 1 run in $O(n)$. In line
4, MRP cost $O(n^{p})$ to get $Ext$ for each agent. Hence, line 4 cost
$O(n^{p+1})$ totally. Other lines run in constant. Hence, although the
computation of the expected results of MRP is difficult, as a random
algorithm, MRP run in $O(n^{p+1})$ time.

_(2) MPS._ Line 1 cost $O(n^{p+1})$ in MPS. Line 2 run in constant. Since we
can get all $Ext$s we need for all agents in all rounds by going through each
topological sort only once. The total running time in line 4 is $O(n^{p+1})$.
Since MPS remove at least one item in $M^{\prime}$ each round, MPS run $np$
rounds at most to consume. In each round of consumption, MPS cost $O(np)$ in
line 5.1, 5.2, 5.4 and $O(n)$ in line 5.3. Hence, MPS cost $O(n^{2}p^{2})$ to
consume totally. Since $p$ is a small number, the cost of MPS is still
$O(n^{p+1})$.

_(3) MGD._ Line 1 cost $O(n^{p+1})$ in MGD. Line 4 cost $O(n^{p})$ in each
round and $O(n^{p+1})$ totally. There are some previous work for getting
$Group(j,\succ^{\prime})$ in line 5. We should compute the segmentation of $N$
such that agents with the same topological sort is in and only in the same
set. To do so, we let all agents be in a same set with $n^{p}$ rounds
following. In each round $k\leq n^{p}$, for each set, visit the $k$-th bundles
in the topological sorts of the agents in the set, divide agents in the set
into several new sets such that the visited bundles of agents in the same new
set is same. That can be done in linear time by using a map with $n^{p}$ size
in each round. The final sets make up the segmentation. The previous work cost
$O(n^{p+1})$ totally. After the previous work, line 5 can be done in $O(n)$.
The total cost in line 6 is $O(np)$ since there are only $np$ items totally.
Hence, the running time of MGD is $O(n^{p+1})$.

∎

#### Proof of Theorem 1.

See 1

###### Proof.

_(1) ex-post-efficiency._ Given any priority order of agents in MRP, suppose
$P$ is the output. Assume for the sake of contradiction that there exists an
assignment $Q\neq P\in\mathcal{P}$ such that
$Q~{}\nobreak\succ^{sd}\allowbreak~{}P$. Let $j$ be the first agent in the set
of agents who get different bundles between $P$ and $Q$. Then, any bundle she
gets in $Q$ is available in her turn in MRP. Let ${\bf{x}}$ be the bundle
agent $j$ gets in $P$. Since $Q~{}\nobreak\succ^{sd}\allowbreak~{}P$, there is
a bundle ${\bf{y}}\in\mathcal{D}$ such that ${\bf{y}}\succ_{j}{\bf{x}}$,
$Q_{j,{\bf{y}}}>0$ and ${\bf{y}}$ is available in agent $j$’s turn. That is
contradicted with that agent $j$ gets ${\bf{x}}$ in her turn. Therefore, the
result of MRP is sd-efficient for any fixed priority order. The expected
result of MRP is the result by randomizing the priority orders, so it is the
linear combination of some sd-efficient discrete assignments.

_(2) weak-sd-envy-freeness._ W.l.o.g we only consider agent $1$ and agent $2$.
Let assignment $P$ be the expected result of MRP. Suppose
$P(2)~{}\nobreak\succ^{sd}_{1}\allowbreak~{}P(1)$. We need to prove that
$P(2)=P(1)$.

Suppose the topological order of agent $1$’s preference in MRP is
${\bf{x}}_{1}\succ^{\prime}{\bf{x}}_{2}\succ^{\prime}...\succ^{\prime}{\bf{x}}_{n^{p}}$.
Let $O$ be the set of any possible priority order, $O_{1}$ be the set of
orders in which agent $1$ is ranked in the front of agent $2$ and $O_{2}$ be
the set of orders in which agent $2$ is ranked in the front of agent $1$. It
is obvious that $\\{O_{1},O_{2}\\}$ is one division of $O$. Let
$f:O_{1}\mapsto O_{2}$ such that for any $o_{1}\in O_{1}$, $f(o_{1})$ is the
order that exchange the positions of agent $1$ and agent $2$ in $o_{1}$. $f$
is a one-to-one mapping and a surjection from $O_{1}$ to $O_{2}$ obviously.

We define the proposition $F({\bf{x}})$ as follow. For any $o_{1}\in O_{1}$,
$o_{2}\in O_{2}$ and $f(o_{1})=o_{2}$, either case (i) or case (ii) happens:
(i) agent $1$ gets ${\bf{x}}$ under $o_{1}$ or $o_{2}$ while agent $2$ gets
${\bf{x}}$ under the other order;  (ii) both agent $1$ and agent $2$ do not
get ${\bf{x}}$ under $o_{1}$ and $o_{2}$.

Then, we prove that $F({\bf{x}}_{1})$ is true. We consider two cases.

  1. 1.

For any $o_{2}\in O_{2}$, let $o_{1}\in O_{1}$ such that $f(o_{1})=o_{2}$. If
agent $2$ gets ${\bf{x}}_{1}$ under $o_{2}$, ${\bf{x}}_{1}$ is available for
agent $1$ under $o_{1}$ and agent $1$ gets ${\bf{x}}_{1}$ under $o_{1}$.

  2. 2.

For any $o_{1}\in O_{1}$, agent $1$ is front of agent $2$ and ${\bf{x}}_{1}$
is the first bundle in topological order of agent $1$’s preference, so agent
$2$ has no chance to get ${\bf{x}}_{1}$ under $o_{1}$.

Based on the two cases above, we can conclude that $p_{2,{\bf{x}}_{1}}\leq
p_{1,{\bf{x}}_{1}}$. But $P(2)~{}\nobreak\succ^{sd}_{1}\allowbreak~{}P(1)$
leads to $p_{2,{\bf{x}}_{1}}\geq p_{1,{\bf{x}}_{1}}$. So
$p_{2,{\bf{x}}_{1}}=p_{1,{\bf{x}}_{1}}$ that induce that $F({\bf{x}}_{1})$ is
true in addition to the two points above.

Next, supposing for any $i<k$ ($k\in\\{2,3,...,n^{p}\\}$),
$p_{2,{\bf{x}}_{i}}=p_{1,{\bf{x}}_{i}}$ and $F({\bf{x}}_{i})$ is true, we
prove that $p_{2,{\bf{x}}_{k}}=p_{1,{\bf{x}}_{k}}$ and $F({\bf{x}}_{k})$ is
true. Consider the two cases again.

  1. 1.

For any $o_{2}\in O_{2}$, there is $o_{1}\in O_{1}$ such that
$f(o_{1})=o_{2}$. If agent $2$ gets ${\bf{x}}_{k}$ under $o_{2}$,
${\bf{x}}_{k}$ is available for agent $1$ under $o_{1}$. Besides, it means
that agent $2$ does not get ${\bf{x}}_{i}$ for any $i<k$ under $o_{2}$. So the
case (ii) in $F({\bf{x}}_{i})$ happens, agent $1$ does not get ${\bf{x}}_{i}$
under $o_{1}$. Agent $1$ choose ${\bf{x}}_{k}$ in her turn under $o_{1}$.

  2. 2.

For any $o_{1}\in O_{1}$, there is $o_{2}\in O_{2}$ such that
$f(o_{1})=o_{2}$. If agent $2$ dose not get ${\bf{x}}_{k}$ under $o_{1}$, it
dose not influence the result that the expectation of ${\bf{x}}_{k}$ agent $1$
gets is bigger than what agent $2$ gets. If agent $2$ gets ${\bf{x}}_{k}$
under $o_{1}$, ${\bf{x}}_{k}$ is available for agent $1$ under $o_{2}$. Agent
$2$ does not get ${\bf{x}}_{i}$ for any $i<k$ under $o_{1}$ and the case (ii)
in $F({\bf{x}}_{i})$ happens, that indicates Agent $1$ does not get
${\bf{x}}_{i}$ for any $i<k$ under $o_{2}$. Hence, Agent $1$ gets
${\bf{x}}_{k}$ under $o_{2}$.

The two cases above imply that $p_{2,{\bf{x}}_{k}}\leq
p_{1,{\bf{x}}_{k}}$.Since $P(2)~{}\nobreak\succ^{sd}_{1}\allowbreak~{}P(1)$
and $p_{2,{\bf{x}}_{i}}=p_{1,{\bf{x}}_{i}}$ for any $i<k$ and
$U(\succ_{1},{\bf{x}}_{k})\subseteq\\{{\bf{x}}_{i}:i\leq k\\}$, we have
$p_{2,{\bf{x}}_{k}}\geq p_{1,{\bf{x}}_{k}}$. Hence
$p_{2,{\bf{x}}_{k}}=p_{1,{\bf{x}}_{k}}$ that induce that $F({\bf{x}}_{k})$ is
true in addition to the two points above.

We have $P(2)=P(1)$ by induction.

_(3) weak-sd-strategyproofness._ W.l.o.g Suppose agent $1$ is the misreport
agent. Given any partial preference $R$, let
$R^{\prime}=(\succ^{\prime}_{1},\succ_{-1})$ and $\succ^{\prime}$ be the fixed
topological order over $\succ_{1}$ in MRP. Let assignment $P$ and $P^{\prime}$
be the expected results of MRP under $R$ and $R^{\prime}$. Suppose
$P^{\prime}\succ^{sd}_{1}P$. Assume for the sake of contradiction that
$P^{\prime}(1)\neq P(1)$. Let ${\bf{x}}_{0}$ be the first bundle in
$\succ^{\prime}$ such that $P^{\prime}_{1,{\bf{x}}_{0}}\neq
P_{1,{\bf{x}}_{0}}$. We have $P^{\prime}_{1,{\bf{x}}_{0}}>P_{1,{\bf{x}}_{0}}$
since $P^{\prime}\succ^{sd}_{1}P$. Under a priority order of agent, if agent
$1$ gets ${\bf{y}}\in\mathcal{D}$ such that
${\bf{x}}_{0}\succ^{\prime}{\bf{y}}$ under $R$, ${\bf{x}}_{0}$ is unavailable
under $R$ and $R^{\prime}$. Hence, there is a priority order $\rhd_{1}$ such
that agent $1$ gets ${\bf{x}}_{0}$ under $R^{\prime}$ and gets ${\bf{x}}_{1}$
where ${\bf{x}}_{1}\succ^{\prime}{\bf{x}}_{0}$ under $R$, otherwise we have
$P^{\prime}_{1,{\bf{x}}_{1}}\leq P_{1,{\bf{x}}}$, a contradiction. If
${\bf{x}}_{1}$ isn’t the first bundle in $\succ^{\prime}$, since
$P^{\prime}_{1,{\bf{x}}_{1}}=P_{1,{\bf{x}}}$, there is a priority order
$\rhd_{2}$ such that agent $1$ gets ${\bf{x}}_{1}$ under $R^{\prime}$ and gets
${\bf{x}}_{2}$ where ${\bf{x}}_{2}\succ^{\prime}{\bf{x}}_{1}$ under $R$.
Continue the process until we find the first bundle ${\bf{x}}_{i}$ in
$\succ^{\prime}$ and there is no such priority order for ${\bf{x}}_{i}$.
Hence, $P_{1,{\bf{x}}_{i}}>P^{\prime}_{1,{\bf{x}}_{i}}$, a contradiction with
$P^{\prime}\succ^{sd}_{1}P$. Therefore, $P^{\prime}(1)=P(1)$.

_(4) equal treatment of equals and decomposability._ That is obvious.

∎

#### Counterexample for Remark 1.

See 1

###### Proof.

Consider the case where $N=\\{1,2\\}$, $M=D_{1}=\\{1_{F},2_{F}\\}$, and
$R=\\{\succ_{1},\succ_{2}\\}$ where $\succ_{1}=\emptyset$,
$\succ_{2}=\\{1_{F}\succ_{2}2_{F}\\}$. In MRP, the fixed topological orders
are $1_{F}\succ^{\prime}2_{F}$ for $\succ_{1}$ and $1_{F}\succ^{\prime}2_{F}$
for $\succ_{2}$. It is obvious that agents both get 0.5 $1_{F}$ and 0.5
$2_{F}$ under this situation. Let
$R^{\prime}=\\{\succ^{\prime}_{1},\succ_{2}\\}$ where
$\succ^{\prime}_{1}=\\{2_{F}\succ^{\prime}_{1}1_{F}\\}$. Under $R^{\prime}$,
agent $1$ gets $2_{F}$ and agent $2$ gets $1_{F}$. Let $P$ and $P^{\prime}$ be
the expected output of MRP. We don’t have $P\succ^{sd}_{1}P^{\prime}$. Hence,
MRP is not sd-strategyproof under general partial preferences.
$\succ^{\prime}_{1}$ is an upper invariant transformation of $\succ_{1}$ at
$2_{F}$ under $P$, but $P^{\prime}_{1,2_{F}}\neq P_{1,2_{F}}$. Hence, MRP is
not upper invariant under general partial preferences.

∎

#### Proof of Theorem 2.

See 2

###### Proof.

_(1) sd-efficiency._ Given any partial preference $R$ and any assignment $P$
for an MTRA, a set $C\subseteq Imp(P)$ is a generalized cycle if it holds for
every $o\in M$ that: if there exists an improvable tuple
${({\bf{x}}_{1},\hat{\bf{x}}_{1})}\in C$ such that $o\in{\bf{x}}_{1}$, then
there exists a tuple ${({\bf{x}}_{2},\hat{\bf{x}}_{2})}\in C$, such that
$o\in\hat{\bf{x}}_{2}$.

######  Claim 1.

Given any partial preference profile $R$ and assignment $P$, $P$ is sd-
efficient if $P$ admits no generalized cycle at $R$.

Proof: By inversions, we assume that the assignment $P$ admits no generalized
cycle at $R$ and there exists another assignment $Q\neq P$ such that
$Q~{}\nobreak\succ^{sd}\allowbreak~{}P$. We try to find a generalized cycle in
$P$.

Let $\hat{N}=\\{j\in N:P(k)\neq Q(k)\\}$ and $\hat{N}\neq\emptyset$ because
$Q\neq P$. Let C be the set of all tuples (${\bf{x}},\hat{\bf{x}}$) such that
for some $j\in\hat{N}$, ${\bf{x}}\succ_{j}\hat{\bf{x}}$ and
$q_{j,{\bf{x}}}>p_{j,{\bf{x}}}$, $q_{j,\hat{\bf{x}}}<p_{j,\hat{\bf{x}}}$.
Because $p_{j,\hat{\bf{x}}}>q_{j,\hat{\bf{x}}}\geq 0$, we have $C\subseteq
Imp(P)$.

For any $j\in\hat{N}$, there exists ${\bf{x}}\in\mathcal{D}$ such that
$q_{j,{\bf{x}}}\neq p_{j,{\bf{x}}}$. If we have
$q_{j,{\bf{x}}}>p_{j,{\bf{x}}}$ for all $q_{j,{\bf{x}}}\neq p_{j,{\bf{x}}}$,
we would have
$1=\sum_{{\bf{x}}\in\mathcal{D}}q_{j,{\bf{x}}}>\sum_{{\bf{x}}\in\mathcal{D}}p_{j,{\bf{x}}}=1$
which is a contradiction. Hence there exists ${\bf{x}}_{0}\in\mathcal{D}$ such
that $q_{j,{\bf{x}}_{0}}<p_{j,{\bf{x}}_{0}}$. We have $\sum_{{\bf{x}}\in
U(\succ_{j},{\bf{x}}_{0})}q_{j,{\bf{x}}}\geq\sum_{{\bf{x}}\in
U(\succ_{j},{\bf{x}}_{0})}p_{j,{\bf{x}}}$ because $Q\succ P$. Hence, there
exists some ${\bf{x}}_{1}\in\mathcal{D}$ such that
${\bf{x}}_{1}\succ_{j}{\bf{x}}_{0}$ and
$q_{j,{\bf{x}}_{1}}>p_{j,{\bf{x}}_{1}}$, otherwise we induce a contradiction
that $\sum_{{\bf{x}}\in
U(\succ_{k},{\bf{x}}_{0})}q_{j,{\bf{x}}}<\sum_{{\bf{x}}\in
U(\succ_{k},{\bf{x}}_{0})}p_{j,{\bf{x}}}$. Therefore,
$({\bf{x}}_{1},{\bf{x}}_{0})\in C$ and $C\neq\emptyset$.

Suppose for the sake of contradiction that $C$ is not a generalized cycle.
Then there exists an item $o$ such that for any ${\bf{x}}\in\mathcal{D}$
containing $o$ and there is ${\bf{x}}$ in some tuple in $C$, ${\bf{x}}$ is
always the left component of any improvable tuple involving ${\bf{x}}$.
Obviously, we have $q_{j,{\bf{x}}}=p_{j,{\bf{x}}}$ for any $j\notin\hat{N}$.
Suppose there exists $j\in\hat{N}$ such that $q_{j,{\bf{x}}}<p_{j,{\bf{x}}}$.
Since $\sum_{\hat{\bf{x}}\in
U(\succ_{j},{\bf{x}})}q_{j,\hat{\bf{x}}}\geq\sum_{\hat{\bf{x}}\in
U(\succ_{j},{\bf{x}})}p_{j,\hat{\bf{x}}}$, there exists some
$\hat{\bf{x}}\in\mathcal{D}$ such that $\hat{\bf{x}}\succ_{j}{\bf{x}}$ and
$q_{j,\hat{\bf{x}}}>p_{j,\hat{\bf{x}}}$. Hence $(\hat{\bf{x}},{\bf{x}})\in C$
and ${\bf{x}}$ is the right component which is a contradiction to ${\bf{x}}$
is always the left component. Therefore, for any $j\in\hat{N}$, we have
$q_{j,{\bf{x}}}\geq p_{j,{\bf{x}}}$. Since ${\bf{x}}$ is the left component of
some tuple in $C$, there exists $j_{1}\in N$, such that
$q_{j_{1},{\bf{x}}}>p_{j_{1},{\bf{x}}}$. Therefore $1=\sum_{j\in
N,o\in{\bf{x}}}q_{j,{\bf{x}}}>\sum_{j\in N,o\in{\bf{x}}}p_{j,{\bf{x}}}=1$, a
contradiction. Therefore for any tuple $({\bf{x}},\hat{\bf{x}})\in C$ and
$o\in{\bf{x}}$, there is a tuple $(\hat{\bf{y}},{\bf{y}})\in C$ such that
$o\in{\bf{y}}$. Hence $C$ is a generalized cycle. $\blacksquare$

Suppose $P$ is the output of MPS given any partial preference profile $R$. We
next prove $P$ admits no generalized cycle, and therefore is sd-efficient by
Lemma 1.

Suppose for the sake of contradiction that $P$ admits a generalized cycle $C$.
Let $({\bf{x}},\hat{\bf{x}})$ be an arbitrary improvable tuple in $C$. Let
_Seq_ be the partial order on $M$ which reflects the time when items are
exhausted. Formally, for any pair of items $o$ and $\hat{o}$ exhausted at
times $t$ and $\hat{t}$ during the execution of ESP respectively, if
$t\leq\hat{t}$, then $o$ _Seq_ $\hat{o}$.

Let $\hat{M}$ be the set of items that are in some left components involved in
C, and let $\hat{o}\in\hat{M}$ be one of top items according to _Seq_. By
definition of generalized cycles, there is an improvable tuple
$({\bf{x}},\hat{\bf{x}})\in C$ such that $\hat{o}\in\hat{\bf{x}}$. Since
$({\bf{x}},\hat{\bf{x}})\in Imp(P)$, there exists an agent $j\in N$ such that
${\bf{x}}\succ_{j}\hat{\bf{x}}$ and $p_{j,\hat{\bf{x}}}>0$. Hence when agent
$j$ starts to consume $\hat{\bf{x}}$, ${\bf{x}}$ is unavailable and there is
an item $o\in{\bf{x}}$ such that $o$ is unavailable when $j$ starts to consume
$\hat{\bf{x}}$. If we use $t(o)$ and $t(\hat{o})$ to stand for the times when
$o$ and $\hat{o}$ exhausted in MPS respectively, we have $t(o)\leq
t(\hat{o})-p_{j,\hat{\bf{x}}}<t(\hat{o})$. Besides, since
$({\bf{x}},\hat{\bf{x}})\in C$, we have $o\in\hat{M}$, a contradiction to that
$\hat{o}$ is one of top items according to _Seq_ in $\hat{M}$.

_(2) weak-sd-envy-freeness._ Suppose $P$ is the output of MPS given any
partial preference profile $R$. W.l.o.g we only prove the case for agent $1$
and agent $2$, that is if $P(2)~{}\nobreak\succ^{sd}_{1}\allowbreak~{}P(1)$,
then $P(1)=P(2)$.

Suppose $P(2)~{}\nobreak\succ^{sd}_{1}\allowbreak~{}P(1)$. Suppose the
topological order of agent $1$’s preference in MPS is
${\bf{x}}_{1}\succ^{\prime}{\bf{x}}_{2}\succ^{\prime}...\succ^{\prime}{\bf{x}}_{n^{p}}$.
There exists $0=t_{0}\leq t_{1}\leq\cdots\leq t_{n^{p}}=1$ such that for any
$i\leq n^{p}$, if $p_{1,{\bf{x}}_{i}}>0$, $t_{i}>t_{i-1}$ and $t_{i}$ is the
time when ${\bf{x}}_{i}$ is exhausted, else $t_{i}=t_{i-1}$ and ${\bf{x}}_{i}$
is unavailable at $t_{i}$.

At the beginning, any bundle is available. Hence, $p_{1,{\bf{x}}_{1}}>0$ and
agent $1$ starts to consume ${\bf{x}}_{1}$ at $t_{0}=0$ till ${\bf{x}}_{1}$ is
exhausted. That indicates $p_{1,{\bf{x}}_{1}}\geq p_{2,{\bf{x}}_{1}}$. Since
$P(2)~{}\nobreak\succ^{sd}_{1}\allowbreak~{}P(1)$ and ${\bf{x}}_{1}$ is the
first bundle in the topological order over $\succ_{1}$, we have
$p_{2,{\bf{x}}_{1}}=\sum_{{\bf{x}}\in
U(\succ_{1},{\bf{x}}_{1})}p_{2,{\bf{x}}}\geq\sum_{{\bf{x}}\in
U(\succ_{1},{\bf{x}}_{1})}p_{1,{\bf{x}}}=p_{1,{\bf{x}}_{1}}$. Therefore,
$p_{1,{\bf{x}}_{1}}=p_{2,{\bf{x}}_{1}}$ and agent $1$ and agent $2$ are both
consuming ${\bf{x}}_{1}$ in the whole interval of $[t_{0},t_{1})$.

Suppose for any $i<k$, $p_{1,{\bf{x}}_{i}}=p_{2,{\bf{x}}_{i}}$ and agent $1$
and agent $2$ are both consuming the same bundle at any time in
$[t_{i-1},t_{i})$. We want to prove agent $1$ and agent $2$ are both consuming
the same bundle at any time in $[t_{k-1},t_{k})$. If $t_{k}=t_{k-1}$, that is
true for $[t_{k-1},t_{k})$. If $t_{k}>t_{k-1}$, agent $1$ is consuming
${\bf{x}}_{k}$ in the whole interval of $[t_{k-1},t_{k})$ but never in
$[t_{0},t_{k-1})$. Hence, agent $2$ never consumes ${\bf{x}}_{k}$ in
$[t_{0},t_{k-1})$. Since ${\bf{x}}_{k}$ is exhausted at $t_{k}$, we have
$p_{1,{\bf{x}}_{k}}=t_{k}-t_{k-1}\geq p_{2,{\bf{x}}_{k}}$. Since
$P_{2}~{}\nobreak\succ^{sd}_{1}\allowbreak~{}P_{1}$, we have
$\sum_{{\bf{x}}\in
U(\succ_{1},{\bf{x}}_{k})}p_{2,{\bf{x}}}\geq\sum_{{\bf{x}}\in
U(\succ_{1},{\bf{x}}_{k})}p_{1,{\bf{x}}}$. Since
$U(\succ_{1},{\bf{x}}_{k})\subseteq\\{{\bf{x}}_{1},{\bf{x}}_{2},...,{\bf{x}}_{k-1},{\bf{x}}_{k}\\}$
and $p_{1,{\bf{x}}_{i}}=p_{2,{\bf{x}}_{i}}$ for any $i<k$, we have
$p_{2,{\bf{x}}_{k}}\geq p_{1,{\bf{x}}_{k}}$. Therefore,
$p_{1,{\bf{x}}_{k}}=p_{2,{\bf{x}}_{k}}$ and agent $1$ and agent $2$ are both
consuming ${\bf{x}}_{k}$ in the whole interval of $[t_{k-1},t_{k})$.

By induction, we have $p_{1,{\bf{x}}_{k}}=p_{2,{\bf{x}}_{k}}$ for any $k\leq
n^{p}$. Hence $P(1)=P(2)$.

_(3) equal treatment of equals._ That is obvious.

∎

#### Counterexamples for Remark 2.

See 2

###### Proof.

_(1) MPS is not ex-post-efficient coming to multi-type resources._ We consider
a special case for partial preferences, CP-net preferences with the shared
dependency graph as shown in Figure 2. We can induce that the preferences are
$1_{F}2_{B}\succ_{1}1_{F}1_{B}\succ_{1}2_{F}1_{B}\succ_{1}2_{F}2_{B}$ and
$1_{F}1_{B}\succ_{2}1_{F}2_{B}\succ_{2}2_{F}2_{B}\succ_{2}2_{F}1_{B}$.
$MPS{}(R)$ is shown in assignment 4 which cannot be realized obviously.

| $1_{F}1_{B}$ | $1_{F}2_{B}$ | $2_{F}1_{B}$ | $2_{F}2_{B}$
---|---|---|---|---
Agent 1 | 0 | 0.5 | 0.5 | 0
Agent 2 | 0.5 | 0 | 0 | 0.5
(4)

Figure 2: CP-net preferences with the shared dependency graph: (a) the
dependency graph for agents; (b) CPTs for agent $1$; (c) CPTs for agent $2$.

_(2) MPS is not ordinally fair and sd-envy-free under general partial
preferences._ Consider the case where $N=\\{1,2\\}$,
$M=D_{1}=\\{1_{F},2_{F}\\}$, and $R=\\{\succ_{1},\succ_{2}\\}$ where
$\succ_{1}=\emptyset$, $\succ_{2}=\\{1_{F}\succ_{2}2_{F}\\}$. In MPS, the
fixed topological orders are $2_{F}\succ^{\prime}1_{F}$ for $\succ_{1}$ and
$1_{F}\succ^{\prime}2_{F}$ for $\succ_{2}$. It is obvious agent $1$ gets
$2_{F}$ and agent $2$ gets $1_{F}$. Let $P=MPS{}(R)$. We have $P_{2,1_{F}}>0$
and $\sum_{{\bf{x}}\in U(\succ_{2},1_{F})}P_{2,{\bf{x}}}>\sum_{{\bf{x}}\in
U(\succ_{1},1_{F})}P_{1,{\bf{x}}}$. Hence, MPS is not ordinally fair. We don’t
have $P(1)\succ^{sd}_{1}P(2)$. Hence, MPS is not sd-envy-free.

_(3) MPS is not upper invariant under general partial preferences._ The
counterexample of upper invariance for MRP can be also an counterexample for
MPS.

∎

#### Proof of Theorem 3.

See 3

###### Proof.

Given any partial preference $R$, there are $n$ eating rounds in MGD. For each
round $j\leq n$, let $\nobreak top(j)\allowbreak$ be the first available
bundle in agent $j$’s topological sort and $Group(j,\succ^{\prime})$ be the
set of agents who have the same topological sort $\succ^{\prime}_{j}$. Then
for each $j^{\prime}\in Group(j,\succ^{\prime})$, $P_{j^{\prime},\nobreak
top(j)\allowbreak}\leftarrow\frac{1}{|Group(j,\succ^{\prime})|}$.

_(1) sd-efficiency._ Given any partial preference profile $R$, let
$P=MGD{}(R)$. Assume for the sake of contradiction that there exists an
assignment $Q\neq P\in\mathcal{P}$ such that
$Q~{}\nobreak\succ^{sd}\allowbreak~{}P$.

In round $j=1$, for each $j^{\prime}\in Group(j,\succ^{\prime})$, since
$\sum_{{\bf{x}}\in U(\succ_{j^{\prime}},\nobreak
top(1)\allowbreak)}P_{j^{\prime},{\bf{x}}}\leq\sum_{{\bf{x}}\in
U(\succ_{j^{\prime}},\nobreak top(1)\allowbreak)}Q_{j^{\prime},{\bf{x}}}$ and
$U(\succ_{j^{\prime}},\nobreak top(1)\allowbreak)=\\{\nobreak
top(1)\allowbreak\\}$, we have $P_{j^{\prime},\nobreak top(1)\allowbreak}\leq
Q_{j^{\prime},\nobreak top(1)\allowbreak}$. Since $\sum_{j^{\prime}\in
Group(1,\succ^{\prime})}P_{j^{\prime},\nobreak
top(1)\allowbreak}=1\geq\sum_{j^{\prime}\in
Group(1,\succ^{\prime})}Q_{j^{\prime},\nobreak top(1)\allowbreak}$, we have
$P_{\hat{j},\nobreak top(1)\allowbreak}=Q_{\hat{j},\nobreak
top(1)\allowbreak}$ for each $\hat{j}\leq n$. Suppose for $j<k$,
$P_{\hat{j},\nobreak top(j)\allowbreak}=Q_{\hat{j},\nobreak
top(j)\allowbreak}$ for each $\hat{j}\leq n$. When $j=k$, for any
$j^{\prime}\in Group(k,\succ^{\prime})$ and any ${\bf{x}}\neq\nobreak
top(k)\allowbreak\in U(\succ_{j^{\prime}},\nobreak top(k)\allowbreak)$,
${\bf{x}}$ is unavailable. For any ${\bf{x}}\neq\nobreak top(k)\allowbreak\in
U(\succ_{j^{\prime}},\nobreak top(k)\allowbreak)$,
$Q_{j^{\prime},{\bf{x}}}\leq P_{j^{\prime},{\bf{x}}}$ since
$Q_{j^{\prime},{\bf{x}}}>P_{j^{\prime},{\bf{x}}}$ implies ${\bf{x}}$ is
available in round $k$. Hence,
$Q_{j^{\prime},{\bf{x}}}=P_{j^{\prime},{\bf{x}}}$, otherwise,
$Q_{j^{\prime},{\bf{x}}}<P_{j^{\prime},{\bf{x}}}$ would cause a contradiction
with $Q~{}\nobreak\succ^{sd}\allowbreak~{}P$. By $\sum_{{\bf{x}}\in
U(\succ_{j^{\prime}},\nobreak
top(k)\allowbreak)}P_{j^{\prime},{\bf{x}}}\leq\sum_{{\bf{x}}\in
U(\succ_{j^{\prime}},\nobreak top(k)\allowbreak)}Q_{j^{\prime},{\bf{x}}}$, we
have $P_{j^{\prime},\nobreak top(k)\allowbreak}\leq Q_{j^{\prime},\nobreak
top(k)\allowbreak}$ for each $j^{\prime}\in Group(k,\succ^{\prime})$. Since
$\sum_{j^{\prime}\in Group(k,\succ^{\prime})}P_{j^{\prime},\nobreak
top(k)\allowbreak}=1\geq\sum_{j^{\prime}\in
Group(k,\succ^{\prime})}Q_{j^{\prime},\nobreak top(k)\allowbreak}$, we have
$P_{\hat{j},\nobreak top(k)\allowbreak}=Q_{\hat{j},\nobreak
top(k)\allowbreak}$ for each $\hat{j}\leq n$. By induction on $k$, we have
$P_{\hat{j},\nobreak top(j)\allowbreak}=Q_{\hat{j},\nobreak
top(j)\allowbreak}$ for each $\hat{j},j\leq n$. Hence, $P=Q$, a contradiction.

Therefore, $P$ is sd-efficient.

_(2) equal treatment of equals._ That is obvious.

_(3) decomposability._ Let $S=\\{Group(j,\succ^{\prime}):j\leq n\\}$ which is
an segmentation of $N$. For $l\leq|S|$, $s_{l}\in S$ and $m\leq|s_{l}|$, sort
agents in $s_{l}$ in ascending order and let $s_{l,m}$ be the $m$-th agent.
Let $k$ be the least common multiple of $\\{|s|:s\in S\\}$. We forge a set of
$k$ priority orders denoted $O$. For $u\leq k$ and $v\leq n$, let $O_{u,v}$ be
the $v$-th agent in the $u$-th priority order in $O$. For each $u\leq k$,
$l\leq|S|$, and $m\leq|s_{l}|$, let $w=((m+u-2)\bmod|s_{l}|)+1$ and
$O_{u,(s_{l,m})}=s_{l,w}$. Consider the special random priority mechanism that
random in $O$ with $\frac{1}{k}$ possibility for each priority order. Since
agents in the same group have the same partial preference, it is obvious the
expected result of the mechanism is that for each $j^{\prime}\in
Group(j,\succ^{\prime})$, $P_{j^{\prime},\nobreak
top(j)\allowbreak}\leftarrow\frac{1}{|Group(j,\succ^{\prime})|}$. That is same
as $MGD{}(R)$. Since the expected result of random priority mechanism is
decomposable, $MGD{}(R)$ is decomposable.

_(4) ex-post-efficiency._ Decomposability and sd-efficiency induce ex-post-
efficiency (?).

∎

#### Counterexamples for Remark 3.

See 3

###### Proof.

Consider the case where $N=\\{1,2,3\\}$, $M=D_{1}=\\{1_{F},2_{F},3_{F}\\}$,
and $R=\\{\succ_{1},\succ_{2},\succ_{3}\\}$ where
$\succ_{1}=\\{1_{F}\succ_{1}2_{F},1_{F}\succ_{1}3_{F},2_{F}\succ_{1}3_{F}\\}$,
$\succ_{2}=\\{1_{F}\succ_{2}3_{F},1_{F}\succ_{2}2_{F},3_{F}\succ_{2}2_{F}\\}$,
and
$\succ_{3}=\\{3_{F}\succ_{3}1_{F},3_{F}\succ_{3}2_{F},1_{F}\succ_{3}2_{F}\\}$.
It is obvious that agent $1$ gets $1_{F}$, agent $2$ gets $3_{F}$ and agent
$3$ gets $2_{F}$ in MGD. Let $P=MGD{}(R)$. Since $P_{1,1_{F}}=1>P_{2,1_{F}}$
and $1_{F}$ is better than $3_{F}$ for agent $2$, MGD is not ordinally fair
and weak-sd-envy-free. Suppose agent $3$ misreport her preference as same as
agent $1$, which is an upper invariant transformation of $\succ_{3}$ at
$2_{F}$ under $P$. Agent $1$ and agent $3$ share their bundles. Agent $3$ gets
0.5 $1_{F}$ and 0.5 $2_{F}$ which is better than only $2_{F}$ for him. Hence,
MGD is not upper invariant and weak-sd-strategyproof.

∎

#### Proof of Proposition 3.

See 3

###### Proof.

We just consider the case of the allocation of single-type items and it is
easy to example in similar manner when $p\geq$. Consider the case where
$N=\\{1,2,3\\}$, $M=D_{1}=\\{1_{F},2_{F},3_{F}\\}$, and $R=(\succ_{j})_{j\leq
3}$ where
$\succ_{1}=\\{1_{F}\succ_{1}2_{F},1_{F}\succ_{1}3_{F},2_{F}\succ_{1}3_{F}\\}$,
$\succ_{2}=\\{3_{F}\succ_{2}2_{F},3_{F}\succ_{2}1_{F},2_{F}\succ_{2}1_{F}\\}$,
and $\succ_{3}={\emptyset}$. It is easy to conclude that assignment (5) is the
only assignment that agent $3$ does not envy others under the concept of sd-
envy-freeness. However, it is dominated by assignment (6).

| $1_{F}$ | $2_{F}$ | $3_{F}$
---|---|---|---
Agent 1 | $\frac{1}{3}$ | $\frac{1}{3}$ | $\frac{1}{3}$
Agent 2 | $\frac{1}{3}$ | $\frac{1}{3}$ | $\frac{1}{3}$
Agent 3 | $\frac{1}{3}$ | $\frac{1}{3}$ | $\frac{1}{3}$
(5) | $1_{F}$ | $2_{F}$ | $3_{F}$
---|---|---|---
Agent 1 | $\frac{2}{3}$ | $\frac{1}{3}$ | $0$
Agent 2 | $0$ | $\frac{1}{3}$ | $\frac{2}{3}$
Agent 3 | $\frac{1}{3}$ | $\frac{1}{3}$ | $\frac{1}{3}$
(6)

∎

#### Proof of Proposition 4.

See 4

###### Proof.

W.l.o.g we only prove the cases when agent $1$ lies. Given any CP-profile
$R=(\succ_{j})_{j\leq n}$, let $P$ be the expected output of $MRP{}$ under
$R$. For any CP-profile $R^{\prime}=(\succ^{\prime}_{1},\succ_{-1})$ where
$\succ^{\prime}_{1}$ is an upper invariant transformation of $\succ_{1}$ at
${\bf{y}}\in\mathcal{D}$, let $P^{\prime}$ be the expected output of $MRP{}$
under $R^{\prime}$. Next, we prove that
$P_{j,{\bf{y}}}=P^{\prime}_{j,{\bf{y}}}$ for any $j\leq n$ by showing that
given any priority order $\rhd$ over agents, any agent gets ${\bf{y}}$ under
$R^{\prime}$ if and only if she gets ${\bf{y}}$ under $R$.

Since the preferences of other agents keep same, given $\rhd$, the sets of
available bundles are same in agent $1$’s turn under $R$ and $R^{\prime}$.
Suppose $\mathcal{D}^{\prime}\subseteq\mathcal{D}$ is the set of all available
bundles in agent $1$’s turn in $MRP{}$ under $R$ and $R^{\prime}$. Suppose
agent $1$ gets ${\bf{x}}\in\mathcal{D}^{\prime}$ under $R$ and
${\bf{x}}^{\prime}\in\mathcal{D}^{\prime}$ under $R^{\prime}$. By Proposition
1, ${\bf{x}}\succ_{1}{\bf{z}}$ for any
${\bf{z}}\neq{\bf{x}}\in\mathcal{D}^{\prime}$ and
${\bf{x}}^{\prime}\succ^{\prime}_{1}{\bf{z}}^{\prime}$ for any
${\bf{z}}^{\prime}\neq{\bf{x}}^{\prime}\in\mathcal{D}^{\prime}$. Given $\rhd$,
we divide all situations to two cases, ${\bf{y}}\in\mathcal{D}^{\prime}$ and
${\bf{y}}\notin\mathcal{D}^{\prime}$.

Case 1, ${\bf{y}}\in\mathcal{D}^{\prime}$. We have ${\bf{x}}\in
U{}(\succ_{1},{\bf{y}})$ and ${\bf{x}}^{\prime}\in
U{}(\succ^{\prime}_{1},{\bf{y}})$. Since $P_{1,{\bf{x}}}>0$, we have
${\bf{x}}\in U{}(\succ^{\prime}_{1},{\bf{y}})$ by the definition of upper
invariant transformation. If ${\bf{x}}\neq{\bf{x}}^{\prime}$, we have
${\bf{x}}\succ_{1}{\bf{x}}^{\prime}$ and
${\bf{x}}^{\prime}\succ^{\prime}_{1}{\bf{x}}$ which is a contradiction to the
definition of upper invariant transformation where
$\succ^{\prime}_{1}\mid_{U{}(\succ^{\prime}_{1},{\bf{y}})}=\succ_{1}\mid_{U{}(\succ^{\prime}_{1},{\bf{y}})}$.
Hence, ${\bf{x}}={\bf{x}}^{\prime}$ and agent $1$ gets ${\bf{x}}$ under $R$
and $R^{\prime}$. Therefore, all agents get the same bundles under $R$ and
$R^{\prime}$ in this case.

Case 2, ${\bf{y}}\notin\mathcal{D}^{\prime}$. Agents after agent $1$ in $\rhd$
and agent $1$ get no ${\bf{y}}$ both under $R$ and $R^{\prime}$. Besides,
agents before agent $1$ in $\rhd$ get the same bundles under $R$ and
$R^{\prime}$. Hence, one agent gets ${\bf{y}}$ under $R^{\prime}$ if and only
if she gets ${\bf{y}}$ under $R$ in this case.

To sum up the two cases, given any priority order $\rhd$ over agents, any
agent gets ${\bf{y}}$ under $R^{\prime}$ if and only if she gets ${\bf{y}}$
under $R$. Therefore, $P_{j,{\bf{y}}}=P^{\prime}_{j,{\bf{y}}}$ for any $j\leq
n$.

∎

#### Proof of Proposition 5.

See 5

###### Proof.

W.l.o.g we only prove the cases when agent $1$ lies. Given any CP-profile
$R=(\succ_{j})_{j\leq n}$ and any CP-profile
$R^{\prime}=(\succ^{\prime}_{1},\succ_{-1})$ where $\succ^{\prime}_{1}$ is an
upper invariant transformation of $\succ_{1}$ at ${\bf{y}}\in\mathcal{D}$, let
$P=MPS{}(R)$ and $P^{\prime}=MPS{}(R^{\prime})$.

Let $\hat{\mathcal{D}}=\\{{\bf{x}}\in\mathcal{D}:P_{1,{\bf{x}}}>0\\}$ and
$\hat{n}=|\hat{\mathcal{D}}|$. By Proposition 1, we have an order over
$\hat{\mathcal{D}}$ such that
${\bf{x}}_{1}\succ_{1}{\bf{x}}_{2}\succ_{1}\cdots\succ_{1}{\bf{x}}_{\hat{n}}$,
${\bf{x}}_{i}\in\hat{\mathcal{D}}$ for any $i\leq\hat{n}$. There is
${\bf{x}}_{i_{0}}$ such that under $R$, when agent $1$ starts to consume
${\bf{x}}_{i_{0}}$, ${\bf{y}}$ is available and after ${\bf{x}}_{i_{0}}$ is
exhausted, ${\bf{y}}$ is unavailable. Suppose $t_{i}$ is the time when
${\bf{x}}_{i}$ is exhausted for $i\leq\hat{n}$ under $R$. Let $t_{0}=0$. Next,
we prove that the consumption processes of all agents are same before
$t_{i_{0}}$ under $R$ and $R^{\prime}$ by induction.

Suppose before $t_{k}$ ($k<i_{0}$), the consumption processes of all agents
are same under $R$ and $R^{\prime}$ (That is true for $k=0$). Hence, the
remaining resources are same under $R$ and $R^{\prime}$ at $t_{k}$. If agent
$1$ turns to consume ${\bf{x}}_{k+1}$ under $R^{\prime}$ at $t_{k}$, the
consumption processes are same between $t_{k}$ and $t_{k+1}$ because the
preferences of the other agents are same under $R$ and $R^{\prime}$. Next, we
prove that ${\bf{x}}_{k+1}$ is the exact bundle agent $1$ turns to at $t_{k}$.
Suppose $\mathcal{D}^{\prime}\subseteq\mathcal{D}$ is the set of all available
bundle at $t_{k}$ under $R$ and $R^{\prime}$. By Proposition 1,
${\bf{x}}_{k+1}\succ_{1}\hat{\bf{x}}$ for any
$\hat{\bf{x}}\neq{\bf{x}}_{k+1}\in\mathcal{D}^{\prime}$. As the same reason,
there is ${\bf{x}}\in\mathcal{D}^{\prime}$ such that
${\bf{x}}\succ^{\prime}_{1}\hat{\bf{x}}$ for any
$\hat{\bf{x}}\neq{\bf{x}}\in\mathcal{D}^{\prime}$. Since $k<i_{0}$, ${\bf{y}}$
is available at $t_{k}$. Hence, ${\bf{x}}_{k+1}\in U{}(\succ_{1},{\bf{y}})$
and ${\bf{x}}\in U{}(\succ^{\prime}_{1},{\bf{y}})$. Since
$P_{1,{\bf{x}}_{k+1}}>0$, we have ${\bf{x}}_{k+1}\in
U{}(\succ^{\prime}_{1},{\bf{y}})$ by the definition of upper invariant
transformation. If ${\bf{x}}\neq{\bf{x}}_{k+1}$, we have
${\bf{x}}\succ^{\prime}_{1}{\bf{x}}_{k+1}$ and
${\bf{x}}_{k+1}\succ_{1}{\bf{x}}$ which is a contradiction to the definition
of upper invariant transformation where
$\succ^{\prime}_{1}\mid_{U{}(\succ^{\prime}_{1},{\bf{y}})}=\succ_{1}\mid_{U{}(\succ^{\prime}_{1},{\bf{y}})}$.
Hence, ${\bf{x}}={\bf{x}}_{k+1}$, agent $1$ turns to ${\bf{x}}_{k+1}$ at
$t_{k}$ under $R^{\prime}$ and the consumption processes are same between
$t_{k}$ and $t_{k+1}$ under $R$ and $R^{\prime}$.

By induction, the consumption processes of all agents are same before
$t_{i_{0}}$ under $R$ and $R^{\prime}$. Hence, the consumption processes are
same until ${\bf{y}}$ is exhausted. Hence,
$P_{j,{\bf{y}}}=P^{\prime}_{j,{\bf{y}}}$ for any $j\leq n$.

∎

Figure 3: CP-net preferences with the shared dependency graph: (a) the shared
dependency graph for agents; (b) CPTs for agent $1$; (c) CPTs for agent $2$
and $3$; (d) The misreported CPTs; (e) The corresponding preference graph of
(b); (f) The corresponding preference graph of (c); (g) The corresponding
preference graph of (d).

#### Counterexample for Remark 4.

See 4

###### Proof.

Consider the MTRA where $N=\\{1,2,3\\}$,
$M=\\{1_{F},2_{F},3_{F},1_{B},2_{B},3_{B}\\}$, and let agents’ preferences be
the same as in Figure 3, where agents have a shared dependency graph shown in
Figure 3(a). The CPTs of agent $1$ are shown as Figure 3(b) while agent $2$
and agent $3$ have the same CPTs as Figure 3(c) shows. Suppose that agent $1$
misreports her CPTs as Figure 3(d). Then, Figures 3(e), 3(f), and 3(g) are the
preference graphs corresponding to the CPTs in Figures 3(b), 3(c), and 3(d)
respectively with the shared dependency graph in Figure 3(a). When agent $1$
reports her CPTs as Figure 3(b), she gets $\frac{1}{3}1_{F}2_{B}$,
$\frac{1}{3}2_{F}1_{B}$ and $\frac{1}{3}2_{F}3_{B}$ under MPS. But if agent
$1$ misreports her CPTs as Figure 3(d), she gets $\frac{1}{3}1_{F}2_{B}$,
$\frac{1}{3}2_{F}1_{B}$, $\frac{2}{9}2_{F}2_{B}$ and $\frac{1}{9}2_{F}3_{B}$
which is a better result for her under the notion of stochastic dominance.
Hence, MPS is not weak-sd-strategyproof even under this restriction.

∎

#### Proof of Proposition 6.

See 6

###### Proof.

Before the main body of the proof, we list three claims about independent CP-
nets for convenience. The proofs of Claim 3 and 4 are based on Claim 2.

######  Claim 2.

Given any independent CP-net $\succ$, for any $D_{i}\in T$, $o\in D_{i}$ and
$\hat{o}\in D_{i}$, if there are some
${\bf{y}}\in\Pi_{-\\{D_{i}\\}},\hat{\bf{y}}\in\Pi_{-\\{D_{i}\\}}$ such that
$(o,{\bf{y}})\succ(\hat{o},\hat{\bf{y}})$, then we have $o\in
U(\succ,\hat{o})$.

Given any independent CP-net $\succ$, for any $D_{i}\in T$, $o\in D_{i}$,
$\hat{o}\in D_{i}$, suppose there are some
${\bf{y}}\in\Pi_{-\\{D_{i}\\}},\hat{\bf{y}}\in\Pi_{-\\{D_{i}\\}}$ such that
$(o,{\bf{y}})\succ(\hat{o},\hat{\bf{y}})$. Then there exists one path from
$(o,{\bf{y}})$ to $(\hat{o},\hat{\bf{y}})$ in the preference graph of $\succ$.
Suppose the path is
$(o_{1},{\bf{y}}_{1})\succ(o_{2},{\bf{y}}_{2})\succ\cdots\succ(o_{t},{\bf{y}}_{t})$
such that $o_{1}=o$, ${\bf{y}}_{1}={\bf{y}}$, $o_{t}=\hat{o}$,
${\bf{y}}_{t}=\hat{\bf{y}}$, and only one pair of items is different between
$(o_{k},{\bf{y}}_{k})$ and $(o_{k+1},{\bf{y}}_{k+1})$ for any $k<t$. For any
${\bf{z}}\in\Pi_{-\\{D_{i}\\}}$, we try to find a path from $(o,{\bf{z}})$ to
$(\hat{o},{\bf{z}})$ by referring the path from $(o,{\bf{y}})$ to
$(\hat{o},\hat{\bf{y}})$. Initialize $E$ as $\emptyset$. For any $k<t$,
suppose the different items between $(o_{k},{\bf{y}}_{k})$ and
$(o_{k+1},{\bf{y}}_{k+1})$ belong to $D_{i_{k}}\in T$. If $D_{i_{k}}=D_{i}$,
we have ${\bf{y}}_{k}={\bf{y}}_{k+1}$ which implies
$(o_{k},{\bf{z}})\succ(o_{k+1},{\bf{z}})$. Add the edge between
$(o_{k},{\bf{z}})$ and $(o_{k+1},{\bf{z}})$ to $E$. It is easy to see that the
edges in $E$ together make up a path from $(o,{\bf{z}})$ to
$(\hat{o},{\bf{z}})$. Therefore $(o,{\bf{z}})\succ(\hat{o},{\bf{z}})$ for any
${\bf{z}}\in\Pi_{-\\{D_{i}\\}}$. Hence, $o\in U(\succ,\hat{o})$.

######  Claim 3.

Given any independent CP-profile $R$ and two assignments $Q$ and $P$, if
$Q\succ^{sd}_{j}P$, for any $D_{i}\in T$, $\hat{o}\in D_{i}$, we have

$\sum_{o\in U(\succ_{j},\hat{o})}Q_{j,o}\geq\sum_{o\in
U(\succ_{j},\hat{o})}P_{j,o}.$

Given any independent CP-profile $R$ and two assignments $Q$ and $P$, suppose
$Q\succ^{sd}_{j}P$. For any ${\bf{x}}\in\mathcal{D}$ and $D\in T$, we define
function $f_{D}$ as $f_{D}({\bf{x}})=o$ such that $o\in{\bf{x}}$ and $o\in D$.
For any $D_{i}\in T$ and $\hat{o}\in D_{i}$, there is
${\bf{x}}_{0}\in\mathcal{D}$ such that $f_{D_{i}}({\bf{x}}_{0})=\hat{o}$ and
for any $D\neq D_{i}\in T$, $o\in D$, we have $f_{D}({\bf{x}}_{0})=o$ or
$o\succ_{j}f_{D}({\bf{x}}_{0})$. For any $o\in U(\succ_{j},\hat{o})$,
${\bf{y}}\in\Pi_{-\\{D_{i}\\}}$, we have $(o,{\bf{y}})\succ_{j}{\bf{x}}_{0}$.
Hence,

$\sum_{o\in U(\succ_{j},\hat{o})}Q_{j,o}=\sum_{o\in
U(\succ_{j},\hat{o})}\sum_{{\bf{y}}\in\Pi_{-\\{D_{i}\\}}}Q_{j,(o,{\bf{y}})}\leq\sum_{{\bf{x}}\in
U(\succ_{j},{\bf{x}}_{0})}Q_{j,{\bf{x}}}.$

For any $(o,{\bf{y}})\in\mathcal{D}$ such that
$(o,{\bf{y}})\succ_{j}{\bf{x}}_{0}$, by Claim 2, we have $o\in
U(\succ_{j},\hat{o})$. Hence,

$\sum_{o\in U(\succ_{j},\hat{o})}Q_{j,o}=\sum_{o\in
U(\succ_{j},\hat{o})}\sum_{{\bf{y}}\in\Pi_{-\\{D_{i}\\}}}Q_{j,(o,{\bf{y}})}\geq\sum_{{\bf{x}}\in
U(\succ_{j},{\bf{x}}_{0})}Q_{j,{\bf{x}}}.$

Therefore, $\sum_{o\in U(\succ_{j},\hat{o})}Q_{j,o}=\sum_{{\bf{x}}\in
U(\succ_{j},{\bf{x}}_{0})}Q_{j,{\bf{x}}}$. In like manner, we have $\sum_{o\in
U(\succ_{j},\hat{o})}P_{j,o}=\sum_{{\bf{x}}\in
U(\succ_{j},{\bf{x}}_{0})}P_{j,{\bf{x}}}$. Since $Q\succ^{sd}_{j}P$,
$\sum_{{\bf{x}}\in
U(\succ_{j},{\bf{x}}_{0})}Q_{j,{\bf{x}}}\geq\sum_{{\bf{x}}\in
U(\succ_{j},{\bf{x}}_{0})}P_{j,{\bf{x}}}$. Hence we have $\sum_{o\in
U(\succ_{j},\hat{o})}Q_{j,o}\geq\sum_{o\in U(\succ_{j},\hat{o})}P_{j,o}$.

######  Claim 4.

Under MPS, given any independent CP-profile $R$, for any $D_{i}\in T$ and
$j\leq n$, there exists $o_{1}\succ_{j}o_{2}\succ_{j}\cdots\succ_{j}o_{l}$ and
$0=t_{0}<t_{1}<\cdots<t_{l}=1$ such that $o_{k}\in D_{i}$, $t_{k}$ is the time
when $o_{k}$ is exhausted and agent $j$ consumes $o_{k}$ in the time interval
$[t_{k-1},t_{k}]$ for $k\leq l$.

Given $D_{i}\in T$ and an independent CP-net $\succ_{j}$ which is the
preference of agent $j\in N$. By Proposition 1, at the beginning of MPS, agent
$j$ starts to consume her unique favorite bundle ${\bf{y}}_{1}\in\mathcal{D}$.
Let $o_{1}\in D_{i}$ such that $o_{1}\in{\bf{y}}_{1}$. Suppose agent $j$ turns
to consume $\hat{\bf{y}}$ such that $o_{1}\notin\hat{\bf{y}}$ before $o_{1}$
is exhausted. Let $\hat{\bf{y}}|o_{1}$ be the bundle which changes the item of
$D_{i}$ in $\hat{\bf{y}}$ to $o_{1}$. Then $\hat{\bf{y}}|o_{1}$ is available
when agent $j$ turns to $\hat{\bf{y}}$. By ${\bf{y}}_{1}\succ_{j}\hat{\bf{y}}$
and Claim 2, we have $\hat{\bf{y}}|o_{1}\succ_{j}\hat{\bf{y}}$, a
contradiction. Hence, agent $j$ consumes $o_{1}$ in $[0,t_{1})$ where $o_{1}$
is exhausted at $t_{1}$. Suppose agent $j$ turns to consume ${\bf{y}}_{2}$ at
$t_{1}$. Let $o_{2}\in D_{i}$ such that $o_{2}\in{\bf{y}}_{2}$. In the same
manner, we have agent $j$ consumes $o_{2}$ in $[t_{1},t_{2})$ where $o_{2}$ is
exhausted at $t_{2}$. Continue the process. Finally, we find orders,
$o_{1}\succ_{j}o_{2}\succ_{j}\cdots\succ_{j}o_{l}$ and
$0=t_{0}<t_{1}<\cdots<t_{l}=1$, such that $o_{k}\in D_{i}$, $t_{k}$ is the
time when $o_{k}$ is exhausted and agent $j$ consumes $o_{k}$ in the time
interval $[t_{k-1},t_{k}]$ for $k\leq l$.

After the proofs of the three claims, we begin the main body of the proof.
W.l.o.g we prove that it is not beneficial for agent $1$ to misreport. Let $R$
be an arbitrary independent CP-profile. Suppose for the sake of contradiction,
that $R^{\prime}=(\succ^{\prime}_{1},\succ_{-1})$ is a profile where agent $1$
misreports her preference as any partial preference relation
$\succ^{\prime}_{1}$, such that
$\text{MPS{}}(R^{\prime})\succ_{1}^{sd}\text{MPS{}}(R)$. Let
$P=\text{MPS{}}(R)$ and $P^{\prime}=\text{MPS{}}(R^{\prime})$. We prove that
$P^{\prime}\succ_{1}^{sd}P$ implies that $P(1)=P^{\prime}(1)$.

For the sake of convenience, we define the following quantities to track the
execution of $\text{MPS{}}(R)$. At any time $t$ during the execution of
$\text{MPS{}}(R)$, let $S(j,t,D_{i})$ be the item $o\in D_{i}$ that agent $j$
is consuming at $t$, and for any item $o\in M$, let $N(o,t)$ be the set of
agents who are consuming an item $o$ at $t$ and $n(o,t)=|N(o,t)|$. For any
$o\in M$, let $\tau(o)$ be the time when $o$ is exhausted during the execution
of $\text{MPS{}}(R)$. Then, we have $\tau(o)=sup\\{t:n(o,t)\geq 1\\}$. For the
execution of $\text{MPS{}}(R^{\prime})$, we define $S^{\prime}(j,t,D_{i})$,
$N^{\prime}(a,t)$, $n^{\prime}(a,t)$ and $\tau^{\prime}(o)$ in a similar way.

Our proof involves showing that $S(j,t,D_{i})=S^{\prime}(j,t,D_{i})$ for any
$j\leq n$, $t\in[1,0)$ and $D_{i}\in T$, which is a stronger condition than
$P_{1}=P_{1}^{\prime}$.

For any $D_{i}\in T$, let $O_{i}=\\{o_{1},\cdots,o_{l}\\}$ be the set of items
that agent $1$ gets a positive fractional share of in $\text{MPS{}}(R)$, i.e.
for each item $o\in O_{i}$, $P_{1,o}>0$, and for each $\hat{o}\in
D_{i}\setminus O_{i}$, $P_{1.\hat{o}}=0$. W.l.o.g. let
$o_{1}\succ_{1}\cdots\succ_{1}o_{l}$. Then, by Claim 4, there are time steps
$0=t_{0}<t_{1}<\cdots<t_{l}=1$, such that for each $k\leq l$, agent $1$ only
consumes $o_{k}$ from $D_{i}$ during the whole interval $[t_{k-1},t_{k})$.

Consider any type $i\leq p$. We prove by induction that
$S(j,t,D_{i})=S^{\prime}(j,t,D_{i})$ for any $j\leq n$, $t\in[1,0)$. Since the
proof for the base case where $S(j,t,D_{i})=S^{\prime}(j,t,D_{i})$ for the
interval $[t_{0},t_{1})$ is similar with the inductive steps, we only prove
the induction hypothesis that for any $k\leq l$,
$S(j,t,D_{i})=S^{\prime}(j,t,D_{i})=o_{k}$ for the interval $[t_{k-1},t_{k})$,
for every $j\leq n$.

Assume that the induction hypothesis is true for each $m<k$. We claim that
there exists no $o\in D_{i}$ such that $o\succ_{1}o_{k}$, $o\notin O_{i}$, and
$P^{\prime}_{1,o}>0$. Otherwise, since $S(j,t,D_{i})=S^{\prime}(j,t,D_{i})$
for any $j\leq n$, $t\in[0,t_{k-1})$, $o$ is available at $t_{k-1}$, and
$o\succ_{1}o_{k}$. However, agent $1$ starts to consume $o_{k}$ at $t_{k-1}$,
a contradiction to our assumption that $P=\text{MPS{}}(R)$. Therefore, by
$P^{\prime}~{}\nobreak\succ^{sd}\allowbreak~{}P$ and Claim 3, we have
$\sum_{m=1}^{k}P_{1,o_{m}}^{\prime}=\sum_{o\in
U(\succ_{1},o_{k})}P_{1,o}^{\prime}\geq\sum_{o\in
U(\succ_{1},o_{k})}P_{1,o}=\sum_{m=1}^{k}P_{1,o_{m}}$. By the induction
hypothesis, we have $P_{1,o_{m}}=P_{1,o_{m}}^{\prime}$ for any $m<k$. Hence,
$P_{1,o_{k}}^{\prime}\geq P_{1,o_{k}}$. Agent $1$ is consuming $o_{k}$ during
the whole interval $[t_{k-1},\tau(o_{k}))$ under $R$ but during the sub
interval of $[t_{k-1},\tau^{\prime}(o_{k}))$ under $R^{\prime}$. Therefore,
$\tau(o_{k})\leq\tau^{\prime}(o_{k})$.

We claim that for all $t\in[0,\tau(o_{k}))$ and all agents $j$, $j\neq 1$, we
have:

$j\in N(o_{k},t)\Rightarrow j\in N^{\prime}(o_{k},t).$ (7)

Suppose for the sake of contradiction that there is an agent $j$, $j\neq 1$,
and a time $t$, $0\leq t<\tau(o_{k})$ such that $j\in N(o_{k},t)$ and $j\in
N^{\prime}(\hat{o}_{1},t)$, for some item $\hat{o}_{1}\neq o_{k}\in D_{i}$. As
$t<\tau(o_{k})\leq\tau^{\prime}(o_{k})$, $o_{k}$ is available at time $t$
under $R^{\prime}$. Then $\hat{o}_{1}\succ_{j}o_{k}$ because the preferences
of agent $j$ are same under $R$ and $R^{\prime}$. So $\hat{o}_{1}$ is
unavailable at $t$ under $R$. This says $\tau(\hat{o}_{1})\leq
t<\tau^{\prime}(\hat{o}_{1})$. Let $A=\\{o\in D_{i}:o\neq
o_{k}\wedge\tau(o)<\tau^{\prime}(o)\\}$, we have $\hat{o}_{1}\in A$ and
$A\neq\emptyset$. We pick $\hat{o}_{2}$ in $A$ such that
$\tau(\hat{o}_{2})=\min\\{\tau(o):o\in A\\}$. Note that
$\tau(\hat{o}_{2})<\tau(o_{k})$ because $\tau(\hat{o}_{1})<\tau(o_{k})$ and
$\hat{o}_{1}\in A$. We claim that at some $t<\tau(\hat{o}_{2})$, there is an
agent $\hat{j}$ such that $\hat{j}\in N(\hat{o}_{2},t)$ and $\hat{j}\notin
N^{\prime}(\hat{o}_{2},t)$. Otherwise we have $N(\hat{o}_{2},t)\subseteq
N^{\prime}(\hat{o}_{2},t)$ for $t\in[0,\tau(\hat{o}_{2}))$. And there is some
sub interval of $[\tau(\hat{o}_{2}),\tau^{\prime}(\hat{o}_{2}))$ such that
$n^{\prime}(\hat{o}_{2},t)\geq 1$ for any $t$ in the sub interval since
$\tau^{\prime}(\hat{o}_{2})=sup\\{t:n^{\prime}(\hat{o}_{2},t)\geq 1\\}$. Hence

$\int_{0}^{\tau(\hat{o}_{2})}n(\hat{o}_{2},t)dt<\int_{0}^{\tau^{\prime}(\hat{o}_{2})}n^{\prime}(\hat{o}_{2},t)dt,$
(8)

a contradiction with

$\int_{0}^{\tau(\hat{o}_{2})}n(\hat{o}_{2},t)dt=1=\int_{0}^{\tau^{\prime}(\hat{o}_{2})}n^{\prime}(\hat{o}_{2},t)dt.$
(9)

Note that $\hat{j}\neq 1$ because agent $1$ is consuming $o_{k}$ during
$[t_{k-1},\tau(o_{k}))$ under $R$. Suppose $\hat{j}\in N(\hat{o}_{2},t)$ and
$\hat{j}\in N^{\prime}(\hat{o}_{3},t)$, for some $t<\tau(\hat{o}_{2})$ and
$\hat{o}_{3}\in D_{i}$. As $\hat{o}_{2}$ is available at $t$ under
$R^{\prime}$ (because $t<\tau(\hat{o}_{2})<\tau^{\prime}(\hat{o}_{2})$), we
have $\hat{o}_{3}\succ_{\hat{j}}\hat{o}_{2}$. Hence $\hat{o}_{3}$ is
unavailable at $t$ under $R$ ($\hat{j}\neq 1$ and her preferences are same
under $R$ and $R^{\prime}$). Therefore,
$\tau(\hat{o}_{3})<t<\tau^{\prime}(\hat{o}_{3})$ and
$\tau(\hat{o}_{3})<t<\tau(\hat{o}_{2})$, a contradiction with
$\tau(\hat{o}_{2})=\min\\{\tau(o):o\in A\\}$.

Thus we have proved claim (7) is true. Suppose that agent $1$ consumes $o$
such that $o\neq o_{k}$ in the sub interval of $[t_{k-1},t_{k}]$ under
$R^{\prime}$. Then $o_{k}$ is available after $t_{k}$. If $t_{k}=1$, we have a
contradiction. If $t_{k}<1$, we have $P_{1,o_{k}}<1$ and $o_{k}$ is allocated
to at least two agents. Since agents continue consuming an item until the item
is exhausted once they start to consume the item in MPS under independent CP-
nets by Claim 4. There is at least one agent except agent $1$ consumes $o_{k}$
just before $t_{k}$ under $R$ and $R^{\prime}$ and the agent continues
consuming $o_{k}$ after $t_{k}$ under $R^{\prime}$. In that case, we have
$P^{\prime}_{1,o_{k}}=1-\sum_{j=2}^{n}P^{\prime}_{j,o_{k}}<1-\sum_{j=2}^{n}P_{j,o_{k}}=P_{1,o_{k}}$,
a contradiction with $P^{\prime}_{1,o_{k}}\geq P_{1,o_{k}}$. Therefore, we
have shown $N(o_{k},t)\subseteq N^{\prime}(o_{k},t)$ for
$t\in[0,\tau(o_{k}))$. If $\tau(o_{k})<\tau^{\prime}(o_{k})$, we would have a
contradiction like (8) and (9). Hence
$\tau(o_{k})=\tau^{\prime}(o_{k})=t_{k}$. Since $P_{1,o_{k}}^{\prime}\geq
P_{1,o_{k}}$ and $P_{1,o_{k}}=\tau(o_{k})-t_{k-1}$, agent $1$ is consuming
$o_{k}$ during the whole interval $[t_{k-1},\tau^{\prime}(o_{k}))$ under
$R^{\prime}$ and $P_{1,o_{k}}^{\prime}=P_{1,o_{k}}$. Since the preferences of
all agents except agent $1$ keep same under $R$ and $R^{\prime}$,
$S(j,t,D_{i})=S^{\prime}(j,t,D_{i})$ for any $j\in N$ and
$t\in[t_{k-1},t_{k})$.

By induction, we have $S(j,t,D_{i})=S^{\prime}(j,t,D_{i})$ for any $j\leq N$,
$t\in[0,1)$ and $D_{i}\in T$. Hence, $P(1)=P^{\prime}(1)$.

∎