# The Division Problem of Chances111We gratefully acknowledge support from the
Swiss National Science Foundation (SNFS) through Project 100018$-$212311.

Rasoul Ramezanian  I would like to express my gratitude to Bettina Klaus for
her excellent guidance, feedback, and our insightful discussions, which have
significantly enhanced the quality of this work. Additionally, I extend my
appreciation to Arunava Sen for his invaluable and constructive feedback.
Faculty of Business and Economics University of Lausanne Internef, 1015
Lausanne, Switzerland<EMAIL_ADDRESS>
###### Abstract

In frequently repeated matching scenarios, individuals may require
diversification in their choices. Therefore, when faced with a set of
potential outcomes, each individual may have an ideal lottery over outcomes
that represents their preferred option. This suggests that, as people seek
variety, their favorite choice is not a particular outcome, but rather a
lottery over them as their peak for their preferences. We explore matching
problems in situations where agents’ preferences are represented by ideal
lotteries. Our focus lies in addressing the challenge of dividing chances in
matching, where agents express their preferences over a set of objects through
ideal lotteries that reflect their single-peaked preferences. We discuss
properties such as strategy proofness, replacement monotonicity, (Pareto)
efficiency, in-betweenness, non-bossiness, envy-freeness, and anonymity in the
context of dividing chances, and propose a class of mechanisms called URC
mechanisms that satisfy these properties. Subsequently, we prove that if a
mechanism for dividing chances is strategy proof, (Pareto) efficient,
replacement monotonic, in-between, non-bossy, and anonymous (or envy free),
then it is equivalent in terms of welfare to a URC mechanism.

MSC2020 Subject Classification: 9110, 91B32, 91B03, 91B08, 91B68

Keywords: Matching Theory, Fair Division, Single peaked Preferences, Mechanism
Design.

##  1 Introduction

Suppose you have a collection of music records on your smartphone, and there
is an application on your device that allows you to set how frequently you
want certain songs to be played repeatedly. For instance, you could set your
ideal lottery as $c=(a:0.2,b:0.5,c:0.1,d:0.2)$, which indicates that you want
to listen to record $a$, 20 percent of the time, record $b$, 50 percent of the
time, record $c$, 10 percent of the time, and record, $d$, 20 percent of the
time repeatedly. The application repeatedly executes your ideal lottery and
selects a record to play for you. Your favorite option is not a specific music
record (if it were, then your collection would only have one record), but
rather a lottery over them.

In “experimental studies” (e.g., Dwenger, Kübler, and Weizsäcker, 2008 [11],
Agranov and Ortoleva, 2017 [4], Kassas, Palma, and Porter, 2022 [17],
Blavatskyy, Panchenko, and Ortmann, 2022 [8]), it has been observed that
participants often prefer lotteries between outcomes to choosing a certain
outcome. These observations contradict the principle of stochastic dominance
in expected utility theory, which guarantees preference preservation in
probabilistic mixtures222The stochastic dominance property says that for four
outcomes $a,b,c$ and $d$, if $a$ is strictly preferred to $b$, and $c$ is
preferred to $d$ then every probabilistic mixture between $a$ and $c$ is
strictly preferred to the same probabilistic mixture of $b$ and $d$.. For
example, considering two choices $a$: ‘Trip to Japan’ and $b$: ‘Trip to
Europe’, and three options: i) receiving $a$ with probability 1, ii) receiving
$b$ with probability 1, and iii) receiving $a$ with probability 0.4 and $b$
with probability 0.6, utility theory predicts that people never prefer option
iii) to options i) and ii). However, people may prefer randomization due to
their ‘desire for variety’ (e.g., Simonson, 1990 [32], Mohan, Sivakumaran, and
Sharma, 2012 [23], Jung and Yoon, 2012 [16]), ‘relief from possible regrets’
(e.g., Gilovich and Medvec, 1995 [14], Zeelenberg and Pieters, 2007 [38]),
‘aversion to responsibility’ (e.g., Dwenger, Kübler, and Weizsäcker, 2008
[11]), and ‘psychic costs’ (e.g., Anderson, 2003 [5]).

In “matching theory” – encompassing house allocation (e.g., Abdulkadiroğlu and
Sönmez, 1999 [1]), course assignment (e.g., Cechlárová, Katarína, Klaus, and
Manlove, 2018 [10]), marriage problem (e.g., Gale and Shapley, 1962 [13],
Klaus, 2009 [19], Pourpouneh, Ramezanian, and Sen, 2020 [29]), and school
choice (e.g., Abdulkadiroğlu and Sönmez, 2003 [2], Klaus and Klijn, 2021 [20],
Kojima and Ünver, 2014 [21], Pathak and Sönmez, 2013 [28]) – people’s
preferences for a set of objects are usually represented using a linear order
relation and it is assumed that matching is a ‘one-shot’ process. However, in
some ‘frequently repeated’ matching scenarios, individuals’ preferences over a
set of objects cannot be adequately represented by a linear order relation.
Instead, their most preferred outcome may involve lotteries over the objects,
which we refer to as the ‘ideal lottery’.

In this paper, we address the problem of “fairly dividing chances” in repeated
matching scenarios where agents express their preferences using ideal
lotteries over objects that reflect their single-peaked preferences. To
illustrate the problem of dividing chances of matching (with ideal lotteries
as a representation of single peaked preferences), consider the following
scenario as a typical example:

An IT company with four workers labeled as $1,2,3$, and $4$, receives four
different tasks denoted as $T_{1},T_{2},T_{3}$, and $T_{4}$ which arrive at
the company on a recurring basis every hour. The manager should assign tasks
to the workers. Each worker has a ‘desire for variety’ and enjoys learning new
things. Therefore, each worker has an ‘ideal lottery’ over tasks:

  * $c_{1}=(T_{1}:0.6,T_{2}:0.2,T_{3}:0,T_{4}:0.2)$,

  * $c_{2}=(T_{1}:0.5,T_{2}:0.1,T_{3}:0.3,T_{4}:0.1)$,

  * $c_{3}=(T_{1}:0.6,T_{2}:0.1,T_{3}:0.1,T_{4}:0.2)$,

  * $c_{4}=(T_{1}:0.1,T_{2}:0.1,T_{3}:0.1,T_{4}:0.7)$.

A worker $i$ prefers a lottery $p$ to a lottery $q$ whenever $p$ is
closer333We formally define the notion of closeness in Section 2. to his ideal
lottery than $q$ is. Workers ask the manager to fairly divide chances of doing
tasks between them, as closely as possible to their ideal lotteries. The
manager faces a fair division problem when it comes to allocating the chances.
Some tasks (like $T_{1}$) are in excess demand with workers and some (like
$T_{3}$) are in excess supply (lack of demand). The manager requires an
allocation mechanism that divides the chances of doing tasks such that both
agent feasibility (for each worker, the sum of probabilities of allocating
tasks to him is equal to 1) and object feasibility (for each task, the sum of
probabilities of doing the task with workers is equal to 1) are satisfied.

Another way to explain the problem of dividing chances is by considering a
scenario featuring three servers and three clients. In this scenario, each
server possesses a capacity of 1 unit of computational resources, and every
client demands a total of 1 unit of combined computational power from all
three servers. Clients submit their ideal requests to the servers, resulting
in some servers becoming overloaded while others remain underutilized. The
core issue lies in efficiently balancing the computational load, requiring
clients to move some of their requests from overloaded servers to
underutilized ones. The division problem revolves around determining how much
load each client should shift from overloaded servers to underutilized ones.

We can approach the “interpretation” of ideal lotteries in two distinct ways:
firstly, by referring to the frequency with which workers express interest in
performing tasks, and secondly, by referring to the proportion of each task
that captures their interest. For instance, consider ideal lottery
$c_{1}=(T_{1}:0.6,T_{2}:0.2,T_{3}:0,T_{4}:0.2)$. This ideal lottery can be
understood in two different ways: firstly, worker 1 would like to do task
$T_{1}$ with probability $0.6$ in each hour, and secondly, worker 1 has a
preference for contributing a fraction of $0.6$ to task $T_{1}$. In this
paper, we adopt the first interpretation. It is important to note that all the
results remain applicable to the second interpretation as well. The second
interpretation is adopted for task sharing between pairs of agents in Nicolò
et al. 2023 [27].

“Fair division” of a resource has been a subject of substantial research
across various fields, including mathematics, economics, and computer science
(e.g., Robertson and Webb, 1998 [31], Young, 1994 [37], Moulin, 2004 [25]).
This is due to the significant impact that fair resource allocation has on the
design of multi agent systems, spanning various domains including scheduling,
and the allocation of computational resources such as CPU, memory, and
bandwidth (Singh and Chana, 2016 [33]). Dividing an infinitely divisible
commodity among some agents with single peaked preferences is already studied
(e.g., Sprumont, 1999 [34], Thomson, 1995 [35]). A homogeneous commodity is to
be divided among a given set of agents $N$, and each agent $i$ has a single
peaked preference with a peak at $x_{i}\in[0,1]$. If $\sum_{i\in N}x_{i}>1$,
we say we are in excess demand, and if $\sum_{i\in N}x_{i}\leq 1$, we are in
excess supply. One of the mechanisms to divide a commodity among the agents is
the ‘uniform rule’. The Uniform Rule (UR) (Sprumont, 1999 [34], Thomson, 1995
[35]), allocates to each agent his preferred share, provided it falls within
common bounds which are the same for everyone and have been selected to meet
the feasibility requirement. An algorithm (see Moulin 2004 [25]) to compute
uniform rule works as follows: Start with $t=1$ and divide it into equal
shares $t/n$. Let $N^{\prime}$ be the set of all agents whose peaks are on the
“wrong” side of $t/n$ (if we are in excess demand, this means those agents
with $x_{i}\leq t/n$; if we are in excess supply, it means those with
$x_{i}\geq t/n$). Distribute the share $x_{i}$ to each agent $i\in N^{\prime}$
and update $t$ by subtracting $\sum_{i\in N^{\prime}}x_{i}$ to adjust the
remainder of the commodity. Update $N$ to $N\setminus N^{\prime}$ and repeat
the same computation with the remaining resources until all agents are on the
same side of $t/n$, and then give the share $t/n$ to them. The Uniform rule is
strategy proof, meaning that agents have no incentive to misreport their
preferences. It is also (Pareto) efficient, ensuring that no agent can be made
better off without making some other agents worse off. This mechanism is also
anonymous, as the outcome does not depend on the agents’ identities.
Additionally, it is envy free, meaning that no agent would prefer another
agent’s allocation over their own. It has been demonstrated that the uniform
rule is characterized by (Pareto) efficiency, strategy proofness, and
anonymity (or envy freeness) properties (see Sprumont, 1999 [34]), thus it is
the only mechanism that satisfies these properties. Division allocation and
reallocation of one commodity have been studied (Thomson, 1995 [35], Klaus,
2001 [18]), as well as the allocation of multiple commodities (Anno and
Sasaki, 2013 [6], Morimoto, Serizawa, and Ching, 2013 [24]). When dealing with
multiple commodities, the uniform rule is applied independently to each
commodity, and it is called Generalized Uniform Rule (GUR).

Allocation mechanisms for divisible multiple commodities regarding
multidimensional single peaked preferences are investigated in Anno and
Sasaki, 2013 [6], and the generalized uniform rule (GUR) is characterized for
two agents. It has been proven that, for two agents, the generalized uniform
rule (GUR) is the only mechanism that satisfies ‘symmetry’ (agents with
similar preferences are treated equally), ‘weak peak onliness’ (if an agent
changes his preference without altering its peak, his outcome remains
unchanged in the mechanism), and ‘weak second best efficiency among all
strategy proof mechanisms’; this property states that the mechanism is a
maximal element in the pre-ordered set of strategy proof mechanisms based on
the domination relation (see Anno and Sasaki, 2013 [6]). Also, in the context
of multiple commodities, for continuous, strictly convex, and separable
multidimensional single peaked preferences, it has been proven that a
mechanism satisfies strategy proofness, unanimity (if the total sum of peak
values for each commodity matches the supply of that commodity, then each
agent should be assigned according to their respective peaks), weak symmetry,
and non-bossiness (when an agent’s preferences change, if his allocation
remains the same, then the whole outcome of the mechanism should remain the
same) if and only if it is GUR (see Morimoto, Serizawa, and Ching, 2013 [24]).

However, we cannot apply the general uniform rule (GUR) for dividing chances.
In the division of multiple commodities, preferences are represented using
separable multidimensional single peaked preferences, whereas, in the division
of chances, lotteries are treated as whole entities with the sum of their
probabilities equal to 1, which makes it impossible to utilize separable
multidimensional single peaked preferences, as the chances of receiving
objects are not separable. Also because of agent feasibility for dividing
chances, we cannot apply GUR (see Example 7.1). Since the General Uniform Rule
(GUR) is not suitable for addressing the problem of dividing chances in one-
to-one matching scenarios, we propose a new class of mechanisms, referred to
as Uniform Rule for Dividing Chances mechanisms (URC mechanisms). In informal
terms, a URC mechanism operates as follows:

We have a set of agents, denoted as $N$, and a set of objects, denoted as $A$,
where the number of agents is equal to the number of objects. Each agent
possesses an ideal lottery over the objects. Think of each object $a\in A$ as
a tank containing one liter of a specific colored liquid named $a$. Each agent
$i\in N$ is equipped with a tap, $tap_{ia}$, for each tank $a\in A$.
Additionally, each agent $i$ has a bucket $buk_{i}$ with a capacity of one
liter, and the ideal lottery of agent $i$, denoted by $c_{i}=(c_{ia})_{a\in
A}$, signifies the desired combination of liquids that agent $i$ wishes to
have in their bucket. The mechanism functions in two phases. In phase 1, all
agents simultaneously open their taps on the tanks. Each agent $i$ closes tap
$tap_{ia}$ as soon as the amount of liquid $a$ in their bucket reaches their
ideal for object $a$. Phase 1 concludes when one of two conditions is met:
either all taps have been closed, or, if any tap on a tank remains open, it
signifies that the liquid in that tank has been fully exhausted.

Figure 1: URC Mechanisms

At the end of phase 1, it is possible that some tanks are not entirely empty
and some buckets are not yet completely filled. So, in phase 2, we organize
all the buckets in a line, and separately, we arrange all the tanks in another
line. In this phase, we initiate the process by opening the tap of the first
tank, allowing the liquid to flow into the first bucket. If the tank becomes
empty, we proceed to the next tank, and if the bucket becomes full, we move on
to the next bucket. By the end of phase 2, each bucket contains exactly one
liter of liquid. The chance of allocating object $a$ to agent $i$ is
proportional to the amount of liquid of object $a$ present in the
corresponding bucket $buk_{i}$. Different ordering of tanks and buckets
defines different URC mechanisms. We establish that all URC mechanisms are
equivalent in terms of welfare, meaning that for each agent, the distance
between agent’s allocation and their ideal lottery remains the same regardless
of the ordering chosen for the tanks and buckets.

We discuss “properties” of URC mechanisms in our context. We show that URC
mechanisms are strategy proof and efficient. We introduce the concept of
replacement monotonicity for dividing chances, and show that URC mechanisms
satisfy this property. This concept was originally introduced in Barberà,
Jackson, and Neme 1997 [7], to characterize sequential allotment mechanisms
for dividing a commodity. Roughly, the replacement monotonicity property can
be understood as follows: If an agent alters their preferences in a manner
that frees up excess demand resources (objects) without improving their own
welfare, it will not negatively impact the welfare of other agents. We
introduce the concept of in-betweenness for dividing chances, and show that
URC mechanisms satisfy this property. In-betweenness is a type of monotonicity
property that examines situations where if an agent increases their ideals for
objects that the mechanism allocated them more than their ideal, and decreases
their ideals for objects that the mechanism allocated them less than their
ideal, then this change does not lead to a decrease for objects they already
received more and does not lead to an increase for objects they already
received less. We also show that URC mechanisms are anonymous, envy free, and
non-bossy. In one-shot matching scenarios where preferences are represented
with linear order relations, achieving strategy proofness, efficiency, and
fairness simultaneously is impossible (e.g., Bogomolnaia and Moulin, 2001 [9],
Nesterov 2017 [26], Ramezanian and Feizi, 2022 [30]). However, in repeated
matching scenarios with ideal lotteries as preferences, it becomes possible to
satisfy these axioms (Proposition 3.4).

“Characterization” theorems help us understand the inner workings of
mechanisms used to allocate resources. By revealing the essential properties
that define these mechanisms, we gain insights into how they function and make
decisions. We characterize the class of URC mechanisms, up to welfare
equivalence, based on key properties: strategy proofness, (Pareto) efficiency,
replacement monotonicity, non-bossiness, in-betweenness, and anonymity (envy
freeness). By ‘characterization up to welfare equivalence’444In Section 2, we
provide a formal explanation of what we mean by ’characterization up to
welfare equivalence’., we mean that when a mechanism satisfies all these
properties, it is equivalent in terms of welfare (distance between the agents’
allocations and their ideal lotteries) to URC mechanisms.

Investigating “logical independency” of properties aims to shed light on the
relationships between properties and to better understand the trade-offs and
interactions within allocation mechanisms. We explore the independence of
properties that characterize (up to welfare equivalence) URC mechanisms by
introducing alternative mechanisms that fulfill certain properties while
lacking others.

The paper is organized as follows: In Section 2, we formally model the
division problem of chances and discuss properties such as (Pareto) efficiency
and replacement monotonicity within this framework. In Section 3, we introduce
a class of mechanisms, referred to as Uniform Rule for Dividing Chances (URC
mechanisms) in one-to-one matching scenarios, and prove that URC mechanisms
satisfy strategy proofness, (Pareto) efficiency, replacement monotonicity,
non-bossiness, in-betweenness, envy freeness, and anonymity. In Section 4, we
characterize the URC mechanisms up to welfare equivalency. In Section 5, we
study the logical relationship between properties: strategy proofness,
efficiency, replacement monotonicity, in-betweenness, non-bossiness, anonymity
and envy freeness. Section 6 concludes the paper and discusses further work.
The proofs of the lemmas, propositions, and theorems are provided in Appendix
7.

##  2 Model

To define single peaked preferences for lotteries, we first need to establish
a notion of distance, as the preference is determined by the closeness to the
peak. For a finite set of objects, $A$, we define $\Delta(A)$ as the set of
all lotteries over $A$. We also define
$\mathbf{d}:\Delta(A)\times\Delta(A)\xrightarrow{}\mathrm{R}$ as the metric
function $\mathbf{d}(p,q)=\sum_{a\in A}\lvert p_{a}-q_{a}\rvert$, for
$p,q\in\Delta(A)$. While it is possible to consider alternative distance
metrics, such as $d(p,q)=(\sum_{a\in A}(\lvert
p_{a}-q_{a}\rvert)^{\rho})^{1/\rho}$, for $\rho\geq 1$ (referred to as
$\mathit{l}^{\rho}$ distances), in this paper, we specifically focus on the
$\mathit{l}^{1}$ distance, and all of our results hold regarding this
distance. This choice aligns with the utilization of the $\mathit{l}^{1}$
distance for single peaked preferences within the literature of voting and
aggregating mechanisms of probabilistic distributions (see Freeman et al.
2021, [12], and Goel et al. 2019 [15]).

The Division Problem of Chances is defined as a tuple $(N,A,(c_{i})_{i\in N})$
where $N$ is a set of agents, $A$ is a set of objects with $|A|=|N|=n$, and
$(c_{i})_{i\in N}$ is a preference profile where each agent $i\in N$ has an
ideal lottery $c_{i}$ over objects such that for each $a\in A$, $c_{ia}\geq 0$
represents the desired chance (fraction) of receiving object $a$ for agent
$i$, and $\sum_{a\in A}c_{ia}=1$. We refer to the set of all preference
profiles by $C^{n}$.

Welfare of an agent increases by getting close to its ideal lottery. An agent
$i$ prefers a lottery $p$ to a lottery $q$, denoted by $p\succ_{c_{i}}q$,
whenever $\mathbf{d}(c_{i},p)<\mathbf{d}(c_{i},q)$. The notations
$p\succeq_{c_{i}}q$ and $p\equiv_{c_{i}}q$ respectively refer to
$\mathbf{d}(c_{i},p)\leq\mathbf{d}(c_{i},q)$ and
$\mathbf{d}(c_{i},p)=\mathbf{d}(c_{i},q)$. Note that since $\mathbf{d}$ is a
metric, $\mathbf{d}(c_{i},p)=\mathbf{d}(p,c_{i})$, and we use both of them
interchangeably in the following sections.

Given a profile of preferences $c$, we say an object $a\in A$ is unanimous
whenever $\sum_{i\in N}c_{ia}=1$, in excess demand whenever $\sum_{i\in
N}c_{ia}>1$, and in excess supply whenever $\sum_{i\in N}c_{ia}<1$. We use
$ED(c)$ to denote the set of excess demand objects, $ES(c)$ for the set of
excess supply objects, and $UN(c)$ for unanimous ones. A random matching is
bistochastic matrix $P=[p_{ia}]_{i\in N,a\in A}$, where for all $i\in N,a\in
A$, $p_{ia}\geq 0$, and

  * •

for each object $a\in A$, $\sum_{i\in N}p_{ia}=1$ (object feasibility) and

  * •

for each agent $i\in N$, $\sum_{a\in A}p_{ia}=1$ (agent feasibility).

For a random matching $P=[p_{ia}]_{i\in N,a\in A}$, for every agent $i\in N$,
$p_{i}=(p_{ia})_{a\in A}$ is called the allocation of agent $i$. And, for
every object $a\in A$, $p_{a}=(p_{ia})_{i\in N}$ is the division of object
$a$. For every profile $c=(c_{i})_{i\in N}$, for every $i\in N$, we let
$c_{-i}=(c_{1},c_{2},...,c_{i-1},c_{i+1},...,c_{n})$. Also for $i\in N$, for
$a\in A$, we use notations $c_{i}=(c_{ia})_{a\in A}$, and
$c_{a}=(c_{ia})_{i\in N}$.

Let $l_{1}$ and $l_{2}$ be two lotteries over a set of objects $A$. We say a
lottery $l$ is between $l_{1}$ and $l_{2}$, denoted by $l\in
Between(l_{1},l_{2})$ whenever for every $a\in A$, either $l_{1}(a)\leq
l(a)\leq l_{2}(a)$ or $l_{2}(a)\leq l(a)\leq l_{1}(a)$.

A mechanism $\mu$ is a mapping from the set of preference profiles to the set
of random matchings. Two mechanism $\mu$ and $\mu^{\prime}$ are considered
welfare equivalent when, for every profile $c=(c_{i})_{i\in N}$, for every
agent $i\in N$, it holds that $\mu_{i}(c)\equiv_{c_{i}}\mu^{\prime}_{i}(c)$.

Let $\Phi_{1},\Phi_{2},...,\Phi_{k}$ be some properties for mechanisms and
$\mathcal{M}$ be a class of mechanisms. We say
$\Phi_{1},\Phi_{2},...,\Phi_{k}$ characterize $\mathcal{M}$ up to welfare
equivalence555It’s worth noting that if the notion of equivalence is replaced
by equality, we obtain the well-known notion of characterization. whenever

  * i-

every $\mu\in\mathcal{M}$ satisfies $\Phi_{1},\Phi_{2},...,\Phi_{k}$, and

  * ii-

for every mechanism $\mu^{\prime}$, if $\mu^{\prime}$ satisfies
$\Phi_{1},\Phi_{2},...,\Phi_{k}$ then $\mu^{\prime}$ is welfare equivalent to
some $\mu\in\mathcal{M}$.

Note that $\Phi_{1},\Phi_{2},...,\Phi_{k}$ are properties of mechanisms and
not of welfare equivalence classes. Therefore, it is possible for two
mechanisms to be welfare equivalent but not satisfy similar properties (see
Figure 3).

A mechanism is strategy proof if it is in the best interest of each
participant to truthfully reveal their preferences, as misrepresentation does
not improve their welfare.

  * Strategy Proofness: A mechanism $\mu$ is strategy proof whenever for every profile $c=(c_{i})_{i\in N}$, for every agent $i\in N$, there exists no ideal lottery $c^{\prime}_{i}$, such that $\mu_{i}(c^{\prime}_{i},c_{-i}))\succ_{c_{i}}\mu_{i}(c)$.

###  2.1 Efficiency

We discuss the concept of efficiency and same-sideness in our context, and
prove that these two notions are logically equivalent. Given a profile of
preferences $c=(c_{i})_{i\in N}$, A random matching $P$ is considered (Pareto)
efficient if it is impossible to enhance the welfare of certain agents without
diminishing the welfare of others. More formally, a random matching $P$ is
lottery dominated by a random matching $Q$ whenever for all agent $i\in N$,
$q_{i}\succeq_{c_{i}}p_{i}$, and strictly lottery dominated by $Q$ whenever it
is lottery dominated and also there exist some $j\in N$ such that
$q_{j}\succ_{c_{j}}p_{j}$. A random matching $P$ is (Pareto) efficient if it
is not strictly lottery dominated by any other random matching. For
convenience, we use the term ‘efficiency’ instead of ‘Pareto efficiency’.

A random matching $P$ is same-sided whenever for every object $a\in A$, if $a$
is in excess demand then for all $i\in N$, $p_{ia}\leq c_{ia}$, if $a$ is in
excess supply then for all $i\in N$, $p_{ia}\geq c_{ia}$, and if $a$ is
unanimous then for all $i\in N$, $p_{ia}=c_{ia}$.

The following lemma demonstrates that, given a same-sided random matching $P$
with respect to a profile $c$, the distance between an agent $i$’s allocation
($p_{i}$) and his ideal lottery ($c_{i}$) how is computed. Note that the Lemma
2.1, works only for same-sided random matchings.

###### Lemma 2.1

Given a profile of preferences $c$, if $P$ is same-sided then for all $i\in
N$,

$\sum_{a\in ED(c)}(c_{ia}-p_{ia})=\sum_{a\in ES(c)}(p_{ia}-c_{ia}),~{}and$

$\mathbf{d}(p_{i},c_{i})=2\times\sum_{a\in
ED(c)}(c_{ia}-p_{ia})=2\times\sum_{a\in ES(c)}(p_{ia}-c_{ia}).$ (1)

Proof. The proof is straightforward as follows:

$0=1-1=\sum_{a\in A}c_{ia}-\sum_{a\in A}p_{ia}=(\sum_{a\in
ED(c)}(c_{ia}-p_{ia}))+(\sum_{a\in ES(c)}(c_{ia}-p_{ia}))+(\sum_{a\in
UN(c)}(c_{ia}-p_{ia}))$,

thus $\sum_{a\in ED(c)}(c_{ia}-p_{ia})=\sum_{a\in ES(c)}(p_{ia}-c_{ia})$, and

$\mathbf{d}(p_{i},c_{i})=\sum_{a\in ED(c)}(c_{ia}-p_{ia})+\sum_{a\in
ES(c)}(p_{ia}-c_{ia})=2\times\sum_{a\in ED(c)}(c_{ia}-p_{ia})$.

$\Box$

In Proposition 2.2, we demonstrate that efficiency and same-sideness are
logically equivalent.

###### Proposition 2.2

A random matching $P$ is efficient if and only if it is same-sided.

Proof. See Appendix 7.2. $\Box$

###  2.2 Replacement Monotonicity

The concept of replacement monotonicity can be classified as a kind of
symmetry property. It was originally introduced in Barberà, Jackson, and Neme,
1997 [7], to characterize sequential allotment mechanisms for dividing a
commodity. It is also used in Masso and Neme, 2007 [22], to characterize bribe
proof mechanisms. The concept of replacement monotonicity is relevant when an
individual’s preferences change, potentially affecting their allocation. In
such cases, there should be an offsetting change in the allocations of the
other individuals. Replacement monotonicity demands that the allocations of
the remaining individuals do not move in opposite directions. More formally,
For dividing a commodity between agents in $N$, suppose that each agent $i\in
N$ has a single peaked preference with a peak at $x_{i}$. A mechanism $\phi$
is replacement monotonic whenever

if $\phi_{i}(x_{i},x_{-i})\leq\phi_{i}(x^{\prime}_{i},x_{-i})$ then for all
$j\neq i$, $\phi_{j}(x_{i},x_{-i})\geq\phi_{j}(x^{\prime}_{i},x_{-i})$.

Replacement monotonicity asserts that if the allocation of some agent $i$ does
not decrease due to the change from $x_{i}$ to $x^{\prime}_{i}$, then the
allocations of all other agents do not increase.

Drawing inspiration from the concept of replacement monotonicity presented in
Barberà, Jackson, and Neme, 1997 [7], we revise the property of replacement
monotonicity for welfare of agents in dividing chances: When an individual
alters their preferences, which can potentially impact their welfare, there
should be a compensatory adjustment in the welfare of the remaining
individuals. Let $\mu$ be a mechanism, and $c=(c_{i})_{i\in N}$ a profile of
preferences. If one agent $i$ (say a worker) modifies his ideal lottery in a
way that

  * •

his modification is with the aim to free up the demand to excess demand
objects (tasks), formally, for all $a\in ED(c)$, $c^{\prime}_{ia}\leq c_{ia}$,

  * •

his modification does not result in another object (task), which was not
already in excess demand, becoming in excess demand. More precisely,
$ED((c^{\prime}_{i},c_{-i}))=ED(c)$), and

  * •

the agent’s own welfare does not increase as a result of this modification,

then there is no decrease in the welfare of other agents.

In other words, when an agent $i$ changes their preferences from $c_{i}$ to
$c^{\prime}_{i}$, freeing up some excess demand objects, this change does not
lead to make some excess supply or unanimous objects becoming in excess
demand, and additionally, agent $i$’s own welfare does not increase as a
result of this change, then the welfare of all other agents does not decrease
either.

###### Definition 2.3

A mechanism $\mu$ is replacement monotonic whenever for every profile
$c=(c_{j})_{j\in N}$, for every agent $i\in N$, for every lottery
$c^{\prime}_{i}$ that satisfies

  * •

$ED((c^{\prime}_{i},c_{-i}))=ED(c)$, and

  * •

for all $a\in ED(c)$, $c^{\prime}_{ia}\leq c_{ia}$,

if $\mu_{i}(c)\succeq_{c_{i}}\mu_{i}((c^{\prime}_{i},c_{-i}))$ then for all
$j\in N\setminus\\{i\\}$,
$\mu_{j}((c^{\prime}_{i},c_{-i}))\succeq_{c_{j}}\mu_{j}(c)$ .

###  2.3 Non-Bossiness

We can define the concept of non-bossiness with two approaches: one with
welfare and one based on allocations. A mechanism is considered welfare non-
bossy when a modification in an agent’s preferences that leaves their own
welfare unchanged also ensures that no one else’s welfare is affected.
Formally, a mechanism $\mu$ is welfare non-bossy whenever for each $c\in
C^{n}$, each $i\in N$, and each $c^{\prime}_{i}\in C$, if
$\mu_{i}(c)\equiv_{c_{i}}\mu_{i}((c^{\prime}_{i},c_{-i}))$ then for all $j\in
N\setminus\\{i\\}$,
$\mu_{j}(c)\equiv_{c_{j}}\mu_{j}((c^{\prime}_{i},c_{-i}))$. However, the URC
mechanisms, the subject of study in this paper, do not satisfy welfare non-
bossiness (see Example 7.2).

We consider the concept of non-bossiness based on allocations for excess
demand objects. A mechanism is non-bossy when a modification in an agent’s
preferences that leaves their own allocation for excess demand objects
unchanged also ensures that no one else’s allocation for excess demand objects
is affected.

  * •

Non-bossiness: For each $c\in C^{n}$, each $i\in N$, and each
$c^{\prime}_{i}$, if for all $a\in ED(c)$,
$\mu_{ia}((c^{\prime}_{i},c_{-i}))=\mu_{ia}(c)$. then for all $j\in
N\setminus\\{i\\}$, for all $a\in ED(c)$,
$\mu_{ja}((c^{\prime}_{i},c_{-i}))=\mu_{ja}(c)$.

So, our concept of non-bossiness considers only allocations for excess demand
objects and not all objects. Also note that if $\mu$ is a same-sided
mechanism, by Lemma 1, then starting from the sentence ‘for all $j\in
N\setminus\\{i\\}$, for all $a\in ED(c)$,
$\mu_{ja}((c^{\prime}_{i},c_{-i}))=\mu_{ja}(c)$’ we can conclude the sentence
‘for all $j\in N\setminus\\{i\\}$,
$\mu_{j}(c)\equiv_{c_{j}}\mu_{j}((c^{\prime}_{i},c_{-i}))$’.

###  2.4 Envy Freenss, Anonymity, In-Betweeness

In this section, we establish the concepts of envy freeness, anonymity and in-
betweenness for the division problem of chances. A random matching $P$ is envy
free when no individual prefers the allocation of another over their own,
meaning no one is envious of others’ outcomes.

  * •

Envy Freeness: For each $c\in C^{n}$, for every $i,j\in N$,
$p_{i}\succ_{c_{i}}p_{j}$.

In our context, anonymity entails that the welfare of the final outcome under
a mechanism is independent of the specific identities of the participating
agents.

  * •

Anonymity: Let $H$ be a permutation of $N$, $c,c^{\prime}\in C^{n}$, and for
every $i\in N$, $c^{\prime}_{H(i)}=c_{i}$. We have
$\mu_{i}(c)\equiv_{c_{i}}\mu_{H(i)}(c^{\prime})$.

The In-Betweenness property is a type of monotonicity properties (Thomson,
2011 [36], Section 7), where a mechanism allocates monotonically with respect
to varying peaks of objects in a specified set. For a profile $c$, for an
agent $i$, and $c^{\prime}_{i}$ between $c_{i}$ and $\mu_{i}(c)$, we say an
object $a$ is a shortage object for $i$, whenever $c_{ia}\geq\mu_{ia}(c)$, and
an abundance object $a$ for $i$, whenever $c_{ia}\leq\mu_{ia}(c)$. In-
betweenness property asserts as follows: If an agent $i$ (a worker) decreases
his ideal for a shortage object (task) $a$ from $c_{ia}$ to $c^{\prime}_{ia}$,
but not less than what the mechanism is allocated to him — that is,
$\mu_{ia}(c)\leq c^{\prime}_{ia}\leq c_{ia}$ — then his allocation does not
increase, that is $\mu_{ia}((c^{\prime}_{i},c_{-i}))\leq\mu_{ia}(c)$.
Similarly, if an agent $i$ (a worker) increases his ideal for an abundance
object (task) $a$, but not more than what the mechanism is allocated to him —
that is, $\mu_{ia}(c)\geq c^{\prime}_{ia}\geq c_{ia}$ — then his allocation
does not decrease, that is $\mu_{ia}((c^{\prime}_{i},c_{-i}))\geq\mu_{ia}(c)$.

  * •

In-Betweenness: For each $c\in C^{n}$, for every $i\in N$, if $c^{\prime}_{i}$
is between $c_{i}$ and $\mu_{i}(c)$, then for all $a\in A$:

if $c^{\prime}_{ia}\leq c_{ia}$ we have
$\mu_{ia}((c^{\prime}_{i},c_{-i}))\leq\mu_{ia}(c)$, and if
$c^{\prime}_{ia}\geq c_{ia}$ we have
$\mu_{ia}((c^{\prime}_{i},c_{-i}))\geq\mu_{ia}(c)$.

In other words, a mechanism satisfies in-betweenness whenever it is monotonic
for lotteries in $between(c_{i},\mu_{i}(c))$. We conclude this section with
the ensuing proposition and its corollary.

###### Proposition 2.4

Suppose $\mu$ is a strategy proof, efficient, and in-between mechanism. Let
$c=(c_{i})_{i\in N}$ be a profile. If an agent $i$ modifies his ideal lottery
$c_{i}$ to a lottery $c^{\prime}_{i}$ where $c^{\prime}_{i}$ is between
$c_{i}$ and $\mu_{i}(c)$, then for all $a\in A$,
$\mu_{ia}(c)=\mu_{ia}((c^{\prime}_{i},c_{-i}))$.

Proof. See Appendix 7.2. $\Box$

###### Corollary 2.5

Suppose mechanism $\mu$ is strategy proof, efficient, in-between and non-
bossy. Let $c=(c_{i})_{i\in N}$ be a profile. If an agent $j$ modifies his
ideal lottery $c_{j}$ to a lottery $c^{\prime}_{j}$ where $c^{\prime}_{j}$ is
between $c_{j}$ and $\mu_{j}(c)$, then for all $a\in ED(c)$, for all $i\in N$,
$\mu_{ia}(c)=\mu_{ia}((c^{\prime}_{j},c_{-j}))$.

In the next section, we discuss URC mechanisms (Uniform Rules for dividing
Chances) and prove that every URC mechanism is strategy proof, efficient,
replacement monotonic, non-bossy, in-between, anonymous, and envy free.

##  3 Uniform Rules for Dividing Chances

In the introduction and Example 7.1, we discussed the difference between
dividing chances in matching scenarios and dividing quantities of multiple
commodities. This difference arises from the requirement of “agent
feasibility” and the fact that lotteries are treated as whole entities that
makes the application of the generalized uniform rule, GRU, inappropriate for
dividing chances. In this section, we introduce a class of mechanisms for
dividing chances, called Uniform Rule for dividing Chances (URC) mechanisms,
and investigate their properties.

We begin by revisiting the uniform rule (Sprumont 1999 [34]), denoted as UR,
for dividing a homogeneous commodity among a given set of agents $N$, where
each agent $i$ has a single peaked preference with a peak at $x_{i}\in[0,1]$.
The uniform rule allocates to each agent his preferred share, provided it
falls within common bounds which are the same for everyone and have been
selected to meet the feasibility requirement. Given a profile $x=(x_{i})_{i\in
N}$, where $x_{i}$ is the peak of agent $i$, the mathematical function
representing the uniform rule is as follows:
$UR:[0,1]^{n}\xrightarrow{}[0,1]^{n}$,

$UR_{i}(x)=\begin{cases}\min(x_{i},\lambda(x))&\quad\text{if}~{}\sum_{j=1...n}x_{j}\geq
1\\\ \max(x_{i},\nu(x))&\quad\text{if}~{}\sum_{j=1...n}x_{j}\leq 1\\\
\end{cases}$

where $\lambda(x)$ solves the equation $\sum_{i\in N}\min(x_{i},\lambda(x))=1$
and $\nu(x)$ solves $\sum_{i\in N}\max(x_{i},\nu(x))=1$.

Now, we are prepared to introduce the class of URC mechanisms. Think of each
object $a\in A$ as a tank containing one liter of a specific colored liquid
named $a$. Each agent $i\in N$ is equipped with a tap, $tap_{ia}$, for each
tank $a\in A$. Additionally, each agent $i$ has a bucket $buk_{i}$ with a
capacity of one liter. The ideal lottery of agent $i$, denoted by
$c_{i}=(c_{ia})_{a\in A}$, signifies the desired combination of liquids that
agent $i$ wishes to have in their bucket. The mechanism functions in two
phases. In phase 1,

  * •

all agents simultaneously open their taps on the tanks. Each agent $i$ closes
tap $tap_{ia}$ as soon as the amount of liquid $a$ in their bucket reaches
their ideal for object $a$, that is $c_{ia}$.

  * •

Phase 1 concludes when one of two conditions is met: either all taps have been
closed, or, if any tap on a tank remains open, it signifies that the liquid in
that tank has been fully exhausted.

Assuming $w_{ia}$ is the current amount of liquid $a$ in bucket $i$. For
objects that are not in excess demand, agent $i$ closes their tap at their
ideal points, so $w_{ia}=c_{ia}$. For objects that are in excess demand,
either agent $i$ closes their tap before liquid $a$ is exhausted, or they,
along with all other agents who cannot reach their ideal points, receive an
equal amount of $a$ while keeping their taps open until all liquid $a$ is
exhausted, this process implies that excess demand objects are divided based
on the uniform rule. Therefore,

  * •

Phase 1: For every object $a\in A$,

    * –

if $a\not\in ED(c)$, for all $i\in N$, let $w_{ia}=c_{ia}$,

    * –

if $a\in ED(c)$, for all $i\in N$, let $w_{ia}=UR_{i}(c_{a})$.

At the end of phase 1, it is possible that some tanks (objects) are not
entirely empty (exhausted) and some buckets (agents) are not yet completely
filled. Indeed, all objects except excess supply objects are exhausted in
phase 1, so, after the completion of phase 1, excess supply object are not be
exhausted, and some agents do not have reached their capacity (where the sum
of the probabilities they hold is less than 1). Therefore, phase 2 of the
mechanism is executed as follows to ensure object feasibility and agent
feasibility.

In phase 2, we organize all the buckets in a line, and separately, we arrange
all the tanks in another line. We initiate the process by opening the tap of
the first tank, allowing the liquid to flow into the first bucket. If the tank
becomes empty, we proceed to the next tank, and if the bucket becomes full, we
move on to the next bucket. By the end of phase 2, each bucket contains
exactly one liter of liquid. The chance of allocating object $a$ to agent $i$
is proportional to the amount of liquid of object $a$ present in the
corresponding bucket $buk_{i}$.

More formally Let $\alpha$ represent a sequence of all agents in $N$, and
$\beta$ a sequence of all objects in $A$. The second phase operates based on
following informal pseudocode:

  * •

Phase 2:

    * 0.

Initialize $t=1,s=1$

    * 1.

If the bucket of agent $\alpha_{t}$ is full (i.e., $\sum_{a\in
A}w_{\alpha_{t}a}=1$) then proceed to the next agent in the sequence by
updating $t$ to $t+1$, continuing updating $t$ to $t+1$ until either finding
an agent $\alpha_{t}$ in the sequence that their bucket is not full, or the
sequence $\alpha$ is concluded ($t=n$).

    * 2.

If object $\beta_{s}$ is exhausted (i.e., $\sum_{i\in N}w_{i\beta_{s}}=1)$
then move on to the next object by updating $s$ to $s+1$, continuing updating
$s$ to $s+1$ until either finding an object $\beta_{s}$ that the liquid in its
tank is not exhausted, or the sequence $\beta$ is concluded ($s=n$).

    * 3.

Update $w_{\alpha_{t}\beta_{s}}$ to
$w_{\alpha_{t}\beta_{s}}+\min\bigg{(}(1-\sum_{a\in
A}w_{\alpha_{t}a}),(1-\sum_{i\in N}w_{i\beta_{s}})\bigg{)}$.

The value $(1-\sum_{a\in A}w_{\alpha_{t}a})$ is the current free capacity of
the bucket of agent $\alpha_{t}$, and $(1-\sum_{i\in N}w_{i\beta_{s}})$ is the
current remaining liquid in the tank of object $\beta_{s}$.

    * 4.

If $t=n$ and $s=n$, Stop, otherwise return to Step 1.

Finally, we let for every $i\in N$, for every $a\in A$,
$URC^{\alpha,\beta}_{ia}(c)=w_{ia}$ as the outcome of the mechanism.

Phase 2 of URC mechanisms solely forces agents to choose additional fractions
of objects to ensure agent feasibility as well as object feasibility, and does
not impact welfare. So, all URC mechanisms are equivalent in terms of welfare.

###### Proposition 3.1

For every sequences $\alpha$, $\alpha^{\prime}$, $\beta$, and
$\beta^{\prime}$, for every profile $c$, for all $i\in N$,

$URC^{\alpha,\beta}_{i}(c)\equiv_{c_{i}}URC^{\alpha^{\prime},\beta^{\prime}}_{i}(c)$.

Proof. The outcome of URC mechanisms is efficient, as it is shown in
Proposition 3.4. According to Proposition 2.2, efficiency is equivalent to
same-sideness. So, with the help of Lemma 2.1, Equation (1), we can compute
the distance based on excess demand objects. In phase 1, all excess demand
objects are exhausted, and therefore, the allocation of excess demand objects
is determined in phase 1. Phase 1 is independent of sequences $\alpha$ and
$\beta$; thus welfare is independent of sequences $\alpha$ and $\beta$, and we
are done. $\Box$

###### Notation 3.2

For convenience, we use $URC$ instead of $URC^{\alpha,\beta}$, when sequences
$\alpha$ and $\beta$ are arbitrary.

###### Example 3.3

Suppose $N=\\{1,2,3\\}$, $A=\\{a,b,c\\}$ and the preference profile $c$ is

$\begin{matrix}c_{1}=(a:0.6,b:0.2,c:0.2)\\\ c_{2}=(a:0.5,b:0.4,c:0.1)\\\
c_{3}=(a:0.2,b:0,c:0.8)~{}~{}\\\ \end{matrix}$ (2)

For profile $c$, we have $ED(c)=\\{a,c\\}$. The execution of phase 1 leads to
the following outcomes:

  * •

$w_{1a}=0.4$, $w_{2a}=0.4$ and $w_{3a}=0.2$.

  * •

$w_{1c}=0.2$, $w_{2c}=0.1$, and $w_{3c}=0.7$.

  * •

$w_{1b}=0.2$, $w_{2b}=0.4$, and $w_{3b}=0$.

Let $\alpha=123$, and $\beta=abc$. In Phase 2, the remaining chances of object
$b$ is assigned to all agents, making them full. The final random matching is:

  * •

$(p_{1a}=0.4,p_{1b}=0.4,p_{1c}=0.2)$,

  * •

$(p_{2a}=0.4,p_{2b}=0.5,p_{2c}=0.1)$,

  * •

$(p_{3a}=0.2,p_{3b}=0.1,p_{3c}=0.7)$.

We show that URC mechanisms satisfy efficiency, strategy proofness,
replacement monotonicity, non-bossiness, envy freeness, and in-between.

###### Proposition 3.4

URC mechanisms are efficient, strategy proof, in-between, non-bossy,
replacement monotonic, anonymous, and envy free.

Proof. See Appendix 7.3. $\Box$

###  3.1 Exploring Alternative Mechanisms for Dividing Chances

In this section, we explore the possibility of constructing alternative
mechanisms for dividing chance. Then, in Section 4, we demonstrate that any
mechanism satisfying the desired properties stated in Theorem 4.4 is welfare
equivalent to URC mechanisms.

Let’s approach the division problem of chances as a constraint satisfaction
problem and explore the role of a mechanism designer. The mechanism designer
is presented with a profile of preferences, denoted as $c=(c_{i})_{i\in N}$,
faced with the problem that, in $c=(c_{i})_{i\in N}$, some objects are in
excess demand whereas others are in excess supply, and the designer encounters
difficulty in satisfying all agent preferences directly as he needs to satisfy
object feasibility as a constraint. To address this, the designer opts to
transfer requests from excess demand objects to excess supply objects to
ensure object feasibility. The key question becomes determining the
appropriate amount of transfer for each agent.

In URC mechanisms, to ascertain the appropriate amount of transfer, we
concentrate on the surplus of objects in excess demand. Utilizing the uniform
rule, we determine, for each agent, how much of each excess demand object
should be transferred to excess supply objects. In following, we discuss two
other alternative approaches two determine the appropriate amount of transfer.

1) One way to determine the appropriate amount to transfer is to focus on the
deficiency for objects which are in excess supply. Consider the following
profile for three agents and three objects:

  * $c_{1}=(a:0,b:1,c:0)$,

  * $c_{2}=(a:0,b:1,c:0)$,

  * $c_{3}=(a:0,b:0,c:1)$.

For object $a$, we are in excess supply. The mechanism designer may decide to
determine how much each agent should have from object $a$, and then transfer
that amount from other objects to object $a$.

If the mechanism designer, employing the uniform rule (UR), aims to distribute
object $a$ among agents, then we have $p_{1a}=p_{2a}=p_{3a}=1/3$. Due to same-
sideness, the mechanism designer cannot transfer anything from object $c$. So,
they should transfer the required amount from object $b$. However, agent $3$
has nothing from object $b$, and transferring an amount from object $b$
results in a negative quantity of $b$ for agent $3$.

The same argument holds for any other mechanisms such as the proportional
rule, that allocates a positive amount of object $a$ to agent $3$, and leads
to a negative quantity of object $b$ for agent $3$, making it an impractical
choice. We conclude that there is no mechanism that can determine the
appropriate amount to transfer fairly based solely on the ideals of agents for
excess supply objects.

We say two profiles $c$ and $c^{\prime}$ coincide on a subset $S\subseteq A$
when, for every agent $i\in N$, and every object $a\in S$,
$c_{ia}=c^{\prime}_{ia}$. In URC mechanisms, the welfare of all agents (the
distance between their allocation and their ideal lottery) is determined
during phase 1, and the ideals of agents for excess supply objects are not
taken into account when determining the welfare of agents in URC mechanisms –
that is,

> for every two profiles $c$ and $c^{\prime}$ with $ED(c)=ED(c^{\prime})$,
> which coincide on $ED(c)$, we have for every agent $i\in N$, for every
> sequences $\alpha$ and $\beta$,
> $\mathbf{d}(URC^{\alpha,\beta}_{i}(c),c_{i})=\mathbf{d}(URC^{\alpha,\beta}_{i}(c^{\prime}),c^{\prime}_{i})$.

This is because all excess demand objects are exhausted in phase 1, and
divided based on the uniform rule. According to Lemma 2.1 (Equation (1):
$\mathbf{d}(p_{i},c_{i})=2\times\sum_{a\in ED(c)}(c_{ia}-p_{ia})$), as for $c$
and $c^{\prime}$, we have $ED(c)=ED(c^{\prime})$, and they coincide on
$ED(c)$, we can conclude for every agent $i\in N$,
$\mathbf{d}(URC^{\alpha,\beta}_{i}(c),c_{i})=\mathbf{d}(URC^{\alpha,\beta}_{i}(c^{\prime}),c^{\prime}_{i})$.

However, there is no efficient mechanism that behaves similarly for excess
supply objects, and when determining the welfare of agents, the ideals of
agents for excess demand objects are not taken into account.

###### Proposition 3.5

There exists no efficient mechanism $\mu$ such that for every two profiles $c$
and $c^{\prime}$ with $ES(c)=ES(c^{\prime})$, that coincide on $ES(c)$, we
have for every agent $i\in N$,
$\mathbf{d}(\mu_{i}(c),c_{i})=\mathbf{d}(\mu_{i}(c^{\prime}),c^{\prime}_{i})$.

Proof. See Appendix 7.3. $\Box$

In URC mechanisms, the share of each agent $i$ to transfer some amount from
excess demand objects to excess supply ones is equal to $\sum_{a\in
ED(c)}(c_{ia}-URC_{ia}(c_{a}))$.

A result of Proposition 3.5 is that there exists no efficient mechanism where
the transfer for each agent $i$ is equal to $\sum_{a\in
ES(c)}(URC_{ia}(c_{a})-c_{ia})$.

2) Another approach to determining the appropriate amount to transfer is to
simplify the problem to a one-object scenario. Consider the following profile
for three agents and three objects:

  * $c_{1}=(a:0.6,b:0.2,c:0.2)$,

  * $c_{2}=(a:0.5,b:0.4,c:0.1)$,

  * $c_{3}=(a:0.2,b:0,c:0.8)$.

Objects $a$ and $c$ are in excess demand. The mechanism designer treat all
excess demand objects as one proxy object $d$, with
$c_{1d}=c_{1a}+c_{1c}=0.8$, $c_{2d}=c_{2a}+c_{2c}=0.6$, and
$c_{3d}=c_{3a}+c_{3c}=1$, when the amount for object $d$ is assumed to be
equal to $2$. Object $d$ is in excess demand as $c_{1d}+c_{2d}+c_{3d}=2.4>2$.
The mechanism designer employs the uniform rule (UR) for object $d$ and
derives

$p_{1d}=0.7,p_{2d}=0.6,p_{3d}=0.7$.

So agent $1$ must transfer $c_{1d}-p_{id}=0.8-0.7$ from objects $a$ and $c$ to
object $b$, agent $2$ must transfer $(0.6-0.6)$ from objects $a$ and $c$ to
object $b$, and agent $3$ must transfer $(1-0.7)$ from objects $a$ and $c$ to
object $b$.

However, this approach is not strategy proof as agent $3$ has incentive to
misreport $c^{\prime}_{3}=(a:0.2,b:0.1,c:0.7)$. By this misreporting, only
object $a$ is in excess demand, and thus $c_{1d}=c_{1a}=0.6$,
$c_{2d}=c_{2a}=0.5$, and $c_{3d}=c^{\prime}_{3a}=0.2$. The mechanism designer
employs the uniform rule (UR) for object $d$ and derives
$p_{1d}=0.4,p_{2d}=0.4,p_{3d}=0.2$. In this way, agent $3$ transfers $0$ from
object $a$ and $0.1$ from object $c$ to $b$ which is less than $0.3$.

##  4 Characterizing URC

In Section 3, we introduced URC mechanisms and examined their properties. In
this section, we characterize URC mechanisms up to welfare equivalence;
proving our main Theorem 4.4, that asserts

> if a mechanism satisfies strategy proofness, efficiency, non-bossiness,
> replacement monotonicity, in-betweenness, and anonymity then it is welfare
> equivalence to URC mechanisms.

The main idea of the proof of Theorem 4.4 is to demonstrate that every
mechanism satisfying the properties outlined in Theorem 4.4 divides the
chances of all excess demand objects according to the uniform rule. Our
approach is as follows: given a profile $c$, for every $a\in ED(c)$, we
transform $c$ into another profile that includes only object $a$ as its excess
demand object. Subsequently, we will employ the characterization theorem
established by Y. Sprumont in 1999 [34], page 511.

The proof sketch is outlined as follows: Suppose that an arbitrary mechanism
$\mu$ satisfying the properties outlined in Theorem 4.4 is given.

  * Step.1.

First, in Lemma 4.1, using efficiency, strategy proofness and replacement
monotonicity, we prove for every profile $c$ with only one excess demand
object $a$, where $ED(c)=\\{a\\}$, if an agent $j$ misreports solely on non-
excess demand objects without affecting the set $ED(c)$, then all agents’
allocation for the excess demand object $a$ remains unchanged.

###### Lemma 4.1

Let $\mu$ be an efficient, strategy proof and replacement monotonic mechanism.
Suppose $c,c^{\prime}\in C^{n}$ are two profiles where for some object $a\in
A$, and some agent $j\in N$,

  * •

$c^{\prime}=(c^{\prime}_{j},c_{-j})$, that is, for all $l\in
N\setminus\\{j\\}$, $c^{\prime}_{l}=c_{l}$,

  * •

$ED(c)=ED(c^{\prime})=\\{a\\}$, and

  * •

$c_{ja}=c^{\prime}_{ja}$.

Then for all $i\in N$, $\mu_{ia}(c)=\mu_{ia}(c^{\prime})$.

Proof. See Appendix 7.4. $\Box$

  * Step.2.

Subsequently, we prove Lemma 4.2. This lemma asserts that when considering two
preference profiles, where a single object, denoted as $a$, is their only
excess demand object, and these profiles are identical in their ideal peaks of
object $a$, then the outcomes of any strategy proof, efficient, and
replacement monotonic mechanism for these two profiles will also be identical
for object $a$.

###### Lemma 4.2

Let $\mu$ be a strategy proof, efficient, and replacement monotonic. For every
two profiles $c$ and $c^{\prime}$ where for some $a\in A$

  * •

$ED(c)=ED(c^{\prime})=\\{a\\}$ , and

  * •

$c_{a}=c^{\prime}_{a}$ ($c_{ia}=c^{\prime}_{ia}$ for all $i\in N$),

we have

for all $i\in N$, $\mu_{ia}(c)=\mu_{ia}(c^{\prime})$.

Proof. See Appendix 7.4. $\Box$

  * Step.3.

By employing the characterization theorem established by Y. Sprumont, 1999
[34], page 511, we deduce that for every profile $c$ with only one excess
demand object, say $a$, for every agent $i\in N$, $\mu_{ia}(c)=UR_{i}(c_{a})$.

###### Lemma 4.3

Let $\mu$ be a strategy proof, efficient, replacement monotonic, and anonymous
mechanism. Also, let $c$ be a profile with $ED(c)=\\{a\\}$ for some $a\in A$.
Then, for every $i\in N$,

$\mu_{ia}(c)=UR_{i}(c_{a})$,

and
$\mathbf{d}(c_{i},\mu_{i}(c))=2\times(c_{ia}-UR_{i}(c_{a}))=\mathbf{d}(c_{i},URC_{i}(c))$.

Proof. See Appendix 7.4. $\Box$

  * Step.4.

Ultimately, with the aid of Corollary 2.5, given a profile $c$, for every
$a\in ED(c)$, we transform the profile $c$ into another profile $c^{\prime}$
featuring only a single excess demand object $ED(c^{\prime})=\\{a\\}$, and for
every $i\in N$, $\mu_{ia}(c)=\mu_{ia}(c^{\prime})$ . This transformations
enable us to apply Lemma 4.3, and conclude the main Theorem 4.4 which
characterizes URC mechanisms up to welfare equivalency.

###### Theorem 4.4

If a mechanism $\mu$ is strategy proof, efficient, replacement monotonic, non-
bossy, in-between and anonymous then for every profile $c\in C^{n}$, for every
agent $i\in N$, for all $a\in ED(c)$, $\mu_{ia}(c)=UR_{i}(c_{a})$, and

for all $i\in N$, $\mu_{i}(c)\equiv_{c_{i}}URC_{i}(c)$,

Proof. See Appendix 7.4. $\Box$

The reader can refer to Figure 2 for a graphical illustration of Theorem 4.4.

###### Remark 4.5

Theorem 4.4 remains valid if we replace the anonymity property with envy
freeness. The proof follows a similar argument, with the only difference being
that in the proofs, we rely on the characterization theorem established by Y.
SPrumont, 1999, [34], page 517, for envy freeness, strategy proofness, and
efficiency.

##  5 Logical Relationship between Properties

We discussed properties strategy proofness, efficiency, replacement
monotonicity, non-bossiness, anonymity (and envy freeness), and show that
every mechanism that satisfies these properties is welfare equivalent to URC
mechanisms (Theorem 4.4, and Remark 4.5). In this section, we study logical
Independency of these properties. To investigate the logical relationship
between properties, We introduce some other mechanisms for the division
problem of chances: a class of Serial Dictatorship mechanisms for dividing
chances (SDC mechanisms), and a class of Proportional Division of Chances
mechanisms (PDC mechanisms).

###  5.1 SDC Mechanisms

Serial Dictatorship mechanisms for dividing chances (SDC mechanisms) consist
of two phases. In Phase 1, all agents are arranged in a line, and then each
agent, in their turn, takes out the amount closest to their preference from
each object. Phase 2 of SDC mechanisms is exactly the same as Phase 2 of URC
mechanisms. Let $\alpha$ represent a sequence of all agents in $N$, and
$\beta$ a sequence of all objects in $A$. Given a profile $c=(c_{i})_{i\in
N}$, the mechanism $SDC^{\alpha,\beta}$ operates in two phases:

  * •

Phase 1:

    * 0.

Initialize $t=1$ and let the $r_{a}$ represents the remainder of each object
$a\in A$, and initially $r_{a}=1$.

    * 1.

For all $a\in A$, let $w_{\alpha(t)a}=\min(r_{a},c_{\alpha(t)a})$ (agent
$\alpha(t)$, in their turn, either extracts their ideal $c_{\alpha(t)a}$ from
the remainder of object $a$, or, if the remainder is less than their ideal,
then they extract the whole remainder).

    * 2.

For every object $a\in A$, update its remainder
$r_{a}\leftarrow(r_{a}-c_{\alpha(t)a})$.

    * 3.

if $t=n$, Stop, otherwise move to next agent by updating $t$ to $t+1$ and
return to Step 1.

  * •

Phase 2: Phase 2 of SDC mechanisms is executing Phase 2 of URC mechanisms for
sequences $\alpha$ and $\beta$.

Finally, we let for every $i\in N$, for every $a\in A$,
$SDC^{\alpha,\beta}_{ia}(c)=w_{ia}$ as the outcome of the mechanism.

Note that the distances between the allocations and ideal lotteries are
contingent upon the excess demand objects. Since all excess demand objects are
exhausted in phase 1 of SDC mechanisms, the determination of distances takes
place during this phase. Subsequently, phase 2 serves primarily to ensure the
feasibility properties.

###### Example 5.1

For $N=\\{1,2,3\\}$ and $A=\\{a,b,c\\}$, suppose the preference profile (2) is
given. Consider the sequence $\alpha$ of agents is as follows: agent 1 is
ahead, agent 2 is next, and agent 3 is in the third position, and $\beta=abc$.

We run the phase 1 of $SDC^{\alpha,\beta}$: Agent 1 receives
$w_{1a}=0.6,w_{1b}=0.2$ and $w_{1c}=0.2$. Hence the remaining of objects are:

$r_{a}=0.4$, $r_{b}=0.8$, and $r_{c}=0.8$.

Then it is the turn of agent 2. He takes $w_{2a}=0.4$, $w_{2b}=0.4$, and
$w_{2c}=0.1$. The remaining of objects are:

$r_{a}=0$, $r_{b}=0.4$, and $r_{c}=0.7$.

Next, agent 3 takes $w_{3a}=0$, $w_{3b}=0$, and $w_{3c}=0.7$. Thus the
remaining of objects are:

$r_{a}=0$, $r_{b}=0.4$, and $r_{c}=0$.

Finally, in phase 2, for sequencing $\beta$ of objects, the remaining are
given to those agents who are not yet full. Hence the final random matching
is:

  * •

$(p_{1a}=0.6,p_{1b}=0.2,p_{1c}=0.2)$,

  * •

$(p_{2a}=0.4,p_{2b}=0.4+0.1,p_{2c}=0.1)$, and

  * •

$(p_{3a}=0,p_{3b}=0+0.3,p_{3c}=0.7)$.

###  5.2 PDC Mechanisms

Proportional Division of Chances mechanisms (PDC mechanisms) consist of two
phases. In phase 1, each agent is given their ideal for non-excess demand
objects, and excess demand objects are divided proportional to the ideals of
agents. Phase 2 of PDC mechanisms is exactly the same as Phase 2 of URC
mechanisms. Let $\alpha$ represent a sequence of all agents in $N$, and
$\beta$ a sequence of all objects in $A$. Given a profile $c=(c_{i})_{i\in
N}$, the mechanism $PDC^{\alpha,\beta}$ operates in two phases as follows:

  * •

Phase 1: For every object $a\in A$,

    * –

if $a\not\in ED(c)$, for all $i\in N$, let $w_{ia}=c_{ia}$,

    * –

if $a\in ED(c)$, for all $i\in N$, let $w_{ia}=c_{ia}/(\sum_{j\in N}c_{ja})$.

  * •

Phase 2: Phase 2 of PDC mechanisms is identical to Phase 2 of URC mechanisms.

Finally, we let for every $i\in N$, for every $a\in A$,
$PDC^{\alpha,\beta}_{ia}(c)=w_{ia}$ as the outcome of the mechanism. Similar
to URC mechanisms and SDC mechanisms, phase 2 of PDC mechanisms serves
primarily to ensure the feasibility properties.

###### Proposition 5.2

  * i)

SDC mechanisms are efficient, strategy-proof, replacement monotonic, in-
between and non-bossy, but they are neither anonymous nor envy-free.

  * ii)

PDC mechanism are anonymous, efficient, replacement monotonic, in-between, and
non-bossy but they are neither strategy proof nor envy free.

Proof. See Appendix 7.5. $\Box$

In addition to Proposition 5.2, following logical relations between properties
also hold true. Let $N=\\{1,2,3\\}$ and $A=\\{a,b,c\\}$.

  * iii)

Non-bossiness + strategy proofness + efficiency does not imply replacement
monotonicity.

To show this claim, we introduce a mechanism denoted as $Except$. Let
$\alpha=23$ , and $\beta=abc$. Given a profile $c=(c_{i})_{i\in N}$, the
mechanism $Except^{\alpha,\beta}$ assigns agent 1 his ideal lottery. Then if
the ideal lottery of agent 1 is $(c_{1a}=1/3)_{a\in A}$, the mechanism
proceeds with serial dictatorship for sequences $\alpha$, and $\beta$, i.e.,
$SDC^{\alpha,\beta}$. Otherwise it proceeds with serial dictatorship for
sequences $\alpha^{r}$, and $\beta$, i.e., $SDC^{\alpha^{r},\beta}$ where
$\alpha^{r}=32$ is the reverse of $\alpha$.

The $Except^{\alpha,\beta}$ is not replacement monotonic. Let

    * $c_{1}=(a:0.4,b:0.4,c:0.2)$

    * $c_{2}=(a:0.4,b:0.4,c:0.2)$

    * $c_{3}=(a:0.4,b:0.4,c:0.2)$.

Let $c^{\prime}_{1}=(a:1/3,b:1/3,c:1/3)$. We have

    * –

$ED(c)=ED((c^{\prime}_{1},c_{-1}))=\\{a,b\\}$, and

    * –

for all object $o\in ED(c)=\\{a,b\\}$, $c^{\prime}_{1o}\leq c_{1o}$.

The outcome of the Except mechanism for agent 1 is as follows:

    * $Except^{\alpha,\beta}_{1}(c))=(a:0.4,b:0.4,c:0.2)$, and

    * $Except^{\alpha,\beta}_{1}((c^{\prime}_{1},c_{-1})=(a:1/3,b:1/3,c:1/3)$.

Thus, we have
$\mathbf{d}(c_{1},Except^{\alpha,\beta}_{1}(c))=0<\mathbf{d}(c_{1},Except^{\alpha,\beta}_{1}((c^{\prime}_{1},c_{-1}))$.
By Definition 2.3 of replacement monotonicity, we must have for
$j\in\\{2,3\\}$,
$\mathbf{d}(c_{j},Except^{\alpha,\beta}_{j}(c))\geq\mathbf{d}(c_{j},Except^{\alpha,\beta}_{j}((c^{\prime}_{1},c_{-1}))$.
However, for agent 2, $\mathbf{d}(c_{2},Except^{\alpha,\beta}_{2}(c))=0$ and
$\mathbf{d}(c_{2},Except^{\alpha,\beta}_{2}((c^{\prime}_{1},c_{-1}))>0$, as
agent $2$ is at the end of the sequence $\alpha^{r}=32$.

The proofs of strategy proofness, efficiency, and non-bossiness for the Except
mechanism are similar to the corresponding proofs for the SDC mechanisms. The
proofs of strategy-proofness, efficiency, and non-bossiness for the Except
mechanism are similar to the corresponding proofs for the SDC mechanisms.
Concerning non-bossiness, note that although the first agent in the sequence
can change the order of agents after himself, by misreporting to
$c^{\prime}_{1}=(a:1/3,b:1/3,c:1/3)$, however, he also changes his own
allocation on excess demand objects.

  * iv)

Replacement monotonicity does not imply non-bossiness. We introduce a
mechanism denoted as $ME$ which is replacement monotonic but not non-bossy.
Given a profile $c=(c_{i})_{i\in N}$, the mechanism $ME$ operates as follows:

    * –

If $ED(c)=\\{a\\}$ then $ME_{1a}(c)=1,ME_{2b}(c)=1,ME_{3c}(c)=1$.

    * –

Otherwise $ME_{1b}(c)=1,ME_{2a}(c)=1,ME_{3c}(c)=1$.

The mechanism $ME$ operates in such a way that for two profiles $c_{1}$ and
$c_{2}$, if we have $ED(c_{1})=ED(c_{2})$ then $ME(c_{1})=ME(c_{2})$.
Therefore, the concept of replacement monotonicity, as defined in Definition
2.3, holds for the $ME$ mechanism. However, the $ME$ mechanism is not non-
bossy, as agent 3 can change the outcomes for other agents without changing
his own outcome.

  * v)

We construct a mechanism, called $MEU$, that is efficient and welfare
equivalent to URC mechanisms but is not strategy proof.

Consider the preference profile $e=(e_{1},e_{2},e_{3})$:

    * $e_{1}=(a:2/3,b:1/3,c:0)$

    * $e_{2}=(a:1/3,b:2/3,c:0)$

    * $e_{3}=(a:1/3,b:1/3,c:1/3)$

Let $\alpha=123$ and $\beta=abc$. We define a mechanism $MEU$ as follows: for
every profile $c$, if $c\neq e$ then $MEU(c)=URC^{\alpha,\beta}(c)$, and for
$c=e$, let $MEU_{1}(e)=(a:2/3,b:0,c:1/3)$, $MEU_{2}(e)=(a:0,b:2/3,c:1/3)$,
$MEU_{3}(e)=(a:1/3,b:1/3,c:1/3)$.

It is easy to check that the mechanism $MEU$ is welfare equivalent to
$URC^{\alpha,\beta}$, as
$URC^{\alpha,\beta}_{1}(e)=URC^{\alpha,\beta}_{2}(e)=URC^{\alpha,\beta}_{3}(e)=(a:1/3,b:1/3,c:1/3)$,
and

    * $\mathbf{d}(e_{1},URC^{\alpha,\beta}_{1}(e))=\mathbf{d}(e_{1},MEU_{1}(e))=2/3$,

    * $\mathbf{d}(e_{2},URC^{\alpha,\beta}_{2}(e))=\mathbf{d}(e_{2},MEU_{2}(e))=2/3$, and

    * $\mathbf{d}(e_{3},URC^{\alpha,\beta}_{3}(e))=\mathbf{d}(e_{3},MEU_{3}(e))=0$.

The mechanism $MEU$ is not strategy proof, as agent 1 in profile
$c=(c_{1},e_{2},e_{3})$ where $c_{1}=(a:2/3,b:0,c:1/3)$, has incentive to
misreport $c^{\prime}_{1}=e_{1}$.

Note that the existence of $MEU$ does not conflict with Theorem 4.4. If a
mechanism satisfies the properties outlined in Theorem 4.4, it is welfare
equivalent to URC mechanisms, but the reverse is not necessarily true (see
Figure 2 and Figure 3).

Figure 2: URC Mechanisms

W: the set of all mechanisms that are welfare equivalent to URC mechanisms.

T: the set of all mechanisms that satisfy the properties outlined in Theorem
4.4.

Proposition 3.4 says: $URC\subseteq T$, and Theorem 4.4 says: $T\subseteq W$.

Figure 3: Welfare Equivalency

Assume $w$ and $m$ as two mechanisms. These two mechanisms are welfare
equivalent since $d(c,m(c))=d(c,w(c))$ and
$d(c^{\prime},m(c^{\prime}))=d(c^{\prime},w(c^{\prime}))$. The mechanism $m$
is strategy proof, since $d(c,m(c))<d(c,m(c^{\prime}))$ and
$d(c^{\prime},m(c^{\prime}))<d(c^{\prime},m(c))$. However, the mechanism $w$
is not strategy proof as $d(c,w(c))>d(c,w(c^{\prime}))$.

In Table 1 we illustrate how introduced mechanisms fulfill properties. The
Equal-Division mechanism in table 1, is simply a mechanism that regardless of
the given preference profile, for all agents $i\in N$ and objects $a\in A$,
assigns each agent $i\in N$ a share of $p_{ia}=1/n$ of object $a$.

The following propositions are yet unknown and pose open questions for us.

  * •

Is there a mechanism satisfying strategy proofness and efficiency but not non-
bossiness?

  * •

Is there a mechanism satisfying strategy proofness and efficiency but not in-
betweenness?

  * •

Although, we explored alternative mechanisms for dividing chances, in Sections
3.1 and 5, yet the following question remains unsolved:

> Is there a mechanism that is strategy proof, efficient, and satisfies either
> anonymity or envy freeness, yet is not welfare equivalent to URC mechanisms?

The likelihood of affirming ‘Yes’ diminishes based on Proposition 3.5. The SDC
mechanisms are strategy proof and efficient, and not welfare equivalent to URC
mechanisms, but they are not fair and lack both anonymity and envy freeness.
Theorem 4.4, which characterizes URC mechanisms in terms of welfare
equivalence, doesn’t provide a conclusive answer to our open question because
it considers additional properties such as non-bossiness, in-betweenness, and
replacement monotonicity.

Mechanisms/Properties | SP | PF | RM | NB | IB | ANO | EF
---|---|---|---|---|---|---|---
URC | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
SDC | ✓ | ✓ | ✓ | ✓ | ✓ | $\times$ | $\times$
PDC | $\times$ | ✓ | ✓ | ✓ | ✓ | ✓ | $\times$
Equal-Division | ✓ | $\times$ | ✓ | ✓ | ✓ | ✓ | ✓

Table 1:  Mechanisms/Properties

SP: Strategy Proofness, PF: (Pareto) Efficiency, RM: Replacement Monotonicity
NB: Non-Bossiness,

IB: In-Betweeness, ANO: Anonymity, EF: Envy Freeness, ✓: Yes, $\times$: No.

##  6 Concluding Remarks and Further Works

We delved into frequently repeated matching scenarios where individuals seek
diversification in their choices, and their favored option is not a specific
outcome but rather a lottery over them, representing the peak of their
preferences. Subsequently, we introduced a class of mechanisms known as URC
mechanisms designed for dividing chances in repeated matching problems. We
then established a characterization theorem up to welfare equivalence,
demonstrating that any mechanism satisfying Pareto efficiency, strategy
proofness, replacement monotonicity, non-bossiness, in-betweenness, and
anonymity (or envy freeness) is welfare equivalent to URC mechanisms. In our
exploration of alternative approaches in Sections 3.1 and 5, a fundamental
question remains open: Can a mechanism be both strategy-proof and efficient
while adhering to either anonymity or envy-freeness, and still not be welfare-
equivalent to URC mechanisms?

In this paper, we addressed the problem of dividing chances using ideal
lotteries to represent preferences for one-sided, one-to-one matching. As a
potential avenue for future research, we could explore two-sided markets, such
as the marriage problem and the roommate problem, where agents’ preferences
are also represented using ideal lotteries.

We can also consider extending the concept of ideal lotteries to ideal Markov
chains. In the introduction, we discussed an example involving a collection of
music on a smartphone, where an individual’s favorite option is not a specific
music record, but rather a lottery over them. Taking this a step further, we
can argue that their preferred option is not merely a lottery but a Markov
chain. This Markov chain can be learned by the application’s artificial
intelligence based on collected data, including how songs are replayed and
transitions between songs within their collection. For instance, consider a
collection of four songs, $\\{a,b,c,d\\}$. A favorite option could be
represented as a Markov chain, where each song is a state, and transitions
between songs occur with certain probabilities. For example, an ideal Markov
chain for an agent might show that after listening to song ‘a’, the agent
would like to replay ‘a’ with a probability of 0.5, transition to ‘b’ with a
probability of 0.3, and switch to ‘c’ with a probability of 0.2.

An Ideal Markov Chain of Songs

Also, consider the example of a company with two workers and two tasks that
hourly repeated, where, each worker has an “ideal Markov chain” over tasks
that represent their favorite option. Let $N=\\{1,2\\}$ and $A=\\{a,b\\}$. The
ideal Markov chain for agent 1 is shown by $M1$ and for agent 2 by $M2$.

Ideal Markov Chains of workers

After doing task $a$, agent 1, with probability $0.7$, would like to do task
$a$ again in the next hour, and with probability $0.3$, would like to do task
$b$ in the next hour. Also, after doing task $b$, agent 1, with probability
$0.4$, would like to do task $b$ in the next hour, and with probability $0.6$
do task $a$.

Representing agents’ preferences through ideal Markov chains finds application
in designing recommender systems (Aggarwal, 2016 [3]), particularly to address
users’ ’desire for variety.’ Mechanism design becomes especially intriguing
when agents’ preferences are modeled using advanced techniques such as Markov
chains, recurrent neural networks (RNN), and long short-term memory networks
(LSTM). These models capture individual preferences over a set of objects in a
dynamic and evolving manner, departing from simple linear orderings.

To illustrate this concept, consider a scenario with four friends on a road
trip, sharing a car and a music collection for their journey. Each person in
the car has their own Markov chain representing song preferences and how they
want songs repeated during the trip. The challenge is to develop an algorithm
for the car’s music player that aggregates individual Markov chains, creating
a coherent social Markov chain to maximize overall passenger utility.

This challenge extends to platforms like Spotify, where dynamic user
preferences learned by RNN or LSTM models need effective aggregation
mechanisms. Our future work explores developing mechanisms and algorithms with
potential benefits for platforms like Netflix and Spotify. We also delve into
questions of fairness, incentive compatibility, stability, and other
considerations in recommender systems regarding Markov chain modeling of
preferences. For instance, our further research may enhance job satisfaction
by optimizing matching algorithms on freelance platforms.

## References

  * [1] Atila Abdulkadiroğlu and Tayfun Sönmez  “House allocation with existing tenants”  In _Journal of Economic Theory_ 88.2 Elsevier, 1999, pp. 233–260
  * [2] Atila Abdulkadiroğlu and Tayfun Sönmez  “School choice: A mechanism design approach”  In _American Economic Review_ 93.3, 2003, pp. 729–747
  * [3] Charu C. Aggarwal  “Recommender Systems”  Springer, 2016
  * [4] Marina Agranov and Pietro Ortoleva  “Stochastic choice and preferences for randomization”  In _Journal of Political Economy_ 125.1, 2017, pp. 40–68
  * [5] Christopher J. Anderson  “The Psychology of Doing Nothing: Forms of Decision Avoidance Result from Reason and Emotion”  In _Psychological Bulletin_ 129, 2003, pp. 139–167
  * [6] Hidekazu Anno and Hiroo Sasaki  “Second-Best Efficiency of Allocation Rules: Strategy-Proofness and Single-Peaked Preferences with Multiple Commodities.”  In _Economic Theory_ 54.3 Springer, 2013, pp. 693–716
  * [7] Salvador Barberà, Matthew Jackson and Alejandro Neme  “Strategy-Proof Allotment Rules”  In _Games and Economic Behavior_ 18.1, 1997, pp. 1–21
  * [8] Pavlo Blavatskyy, Valentyn Panchenko and Andreas Ortmann  “How common is the common-ratio effect?”  In _Experimental Economics_ 21.Sep, 2022
  * [9] Anna Bogomolnaia and Hervé Moulin  “A New Solution to the Random Assignment Problem”  In _Journal of Economic Theory_ 100.2, 2001, pp. 295–328
  * [10] Katarína Cechlárová, Bettina Klaus and David F Manlove  “Pareto optimal matchings of students to courses in the presence of prerequisites”  In _Discrete Optimization_ 29 Elsevier, 2018, pp. 174–195
  * [11] Nadja Dwenger, Dorothea Kübler and Georg Weizsäcker  “Flipping a coin: Evidence from university applications”  In _Journal of Public Economics_ 167.November 2018, 2008, pp. 240–250
  * [12] Rupert Freeman, David Pennock, Dominik Peters and Jennifer Wortman Vaughan  “Truthful aggregation of budget proposals”  In _Journal of Economic Theory_ 193.April, 2021, pp. 105234
  * [13] David Gale and Lloyd S Shapley  “College admissions and the stability of marriage”  In _The American Mathematical Monthly_ 69.1 Taylor & Francis, 1962, pp. 9–15
  * [14] Thomas Gilovich and Victoria H. Medvec  “The Experience of Regret: What, When, and Why”  In _Psychological Review_ 102, 1995, pp. 379–395
  * [15] Ashish Goel, Anilesh K Krishnaswamy, Sukolsak Sakshuwong and Tanja Aitamurto  “Knapsack voting for participatory budgeting”  In _ACM Transactions on Economics and Computation (TEAC)_ 7.2, 2019, pp. 1–27
  * [16] Hyo Sun Jung and Hye Hyun Yoon  “Why do satisfied customers switch? Focus on the restaurant patron variety-seeking orientation and purchase decision involvement.”  In _International Journal of Hospitality Management_ 31, 2012, pp. 875–884
  * [17] Bachir Kassas, Marco A. Palma and Maria Porter  “Happy to take some risk: Estimating the effect of induced emotions on risk preferences”  In _Journal of Economic Psychology_ 91.Aug, 2022, pp. 102527
  * [18] Bettina Klaus  “Uniform allocation and reallocation revisited”  In _Review of Economic Design_ 6, 2001, pp. 85–98
  * [19] Bettina Klaus  ““Fair marriages”: An impossibility”  In _Economics Letters_ 105.1 Elsevier, 2009, pp. 74–75
  * [20] Bettina Klaus and Flip Klijn  “Minimal-access rights in school choice and the deferred acceptance mechanism” Cahier de recherches économiques No. 21.11, available at https://ideas.repec.org/p/lau/crdeep/21.11.html, 2021
  * [21] Fuhito Kojima and M Utku Ünver  “The “Boston” school-choice mechanism: An axiomatic approach”  In _Economic Theory_ 55.3 Springer, 2014, pp. 515–544
  * [22] Jordi Masso and Alejandro Neme  “Bribe-proof rules in the division problem”  In _Games and Economic Behavior_ 61.2, 2007, pp. 331–343
  * [23] Geetha Mohan, Bharadhwaj Sivakumaran and Piyush Sharma  “Store environment’s impact on variety seeking behavior”  In _Journal of Retailing and Consumer Services_ 19.4, 2012, pp. 419–428
  * [24] Shuhei Morimoto, Shigehiro Serizawa and Stephen Ching  “A characterization of the uniform rule with several commodities and agents”  In _Social Choice and Welfare_ 40 Springer, 2013, pp. 871–911
  * [25] Herve Moulin  “Fair Division and Collective Welfare”  MIT Press, 2004
  * [26] Alexander S. Nesterov  “Fairness and efficiency in strategy-proof object allocation mechanisms”  In _Journal of Economic Theory_ 170, 2017, pp. 145–168
  * [27] Antonio Nicolò, Pietro Salmaso, Arunanva Sen and Sonal Yadav  “Stable sharing”  In _Games and Economic Behavior_ 141.Sep, 2023, pp. 337–363
  * [28] Parag A Pathak and Tayfun Sönmez  “School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation”  In _American Economic Review_ 103.1, 2013, pp. 80–106
  * [29] Mohsen Pourpouneh, Rasoul Ramezanian and Arunava Sen  “The Marriage Problem with Interdependent Preferences”  In _International Game Theory Review_ 22.02 World Scientific, 2020, pp. 2040005
  * [30] Rasoul Ramezanian and Mehdi Feizi  “Robust ex-post Pareto Efficiency and Fairness in Random Assignments: Two Impossibility Results,”  In _Games and Economic Behavior_ 135, 2022, pp. 356–367
  * [31] Jack Robertson and William Webb  “Cake-Cutting Algorithms: Be Fair if You Can”  CRC Press, 1998
  * [32] Itar Simonson  “Purchase Quantity and Timing on Variety-Seeking Behavior”  In _Journal of Marketing Research_ 27, 1990, pp. 150–162
  * [33] Sukhpal Singh and Inderveer Chana  “A Survey on Resource Scheduling in Cloud Computing: Issues and Challenges”  In _Journal of Grid Computing_ 14, 2016, pp. 217–264
  * [34] Yves Sprumont  “The Division Problem with Single-Peaked Preferences: A Characterization of the Uniform Allocation Rule”  In _Econometrica_ 59.2, 1999, pp. 509–519
  * [35] William Thomson  “Population-Monotonic Solutions to the Problem of Fair Division When Preferences Are Single-Peaked”  In _Economic Theory_ 5.2 Springer, 1995, pp. 229–246
  * [36] William Thomson  “Chapter Twenty-One - Fair Allocation Rules”  In _Handbook of Social Choice and Welfare_ 2 Elsevier, 2011, pp. 393–506
  * [37] H. Young  “Equity: In Theory and Practice”  Princeton University Press, 1994
  * [38] Marcel Zeelenberg and Rik Pieters  “A Theory of Regret Regulation 1.0”  In _Journal of Consumer Psychology_ 17.2, 2007, pp. 3–18

##  7 Appendix

In the appendix, we provide proofs of lemmas, propositions, and theorems that
have not been addressed in earlier sections. Additionally, we offer some
examples that are referenced in preceding sections.

###  7.1 Examples

###### Example 7.1

This example illustrates how the division of chances in matching scenarios
differs from the division of quantities of multiple commodities due to the
concept of agent feasibility. Applying the generalized uniform rule is not
applicable as a result.

Suppose that $N=\\{1,2,3\\}$ is a set of agents, $A=\\{a,b,c\\}$ is a set of
objects, and ideal lotteries of agents over objects are

  * $c_{1}=(a:0.2,b:0.6,c:0.2)$,

  * $c_{2}=(a:0.4,b:0.6,c:0)$,

  * $c_{3}=(a:0,b:0.2,c:0.8)$.

Object $a$ is in excess supply, $(\sum_{i\in N}c_{ia}<1)$. If we divide the
chance of receiving object $a$ using the uniform rule then we have
$p_{1a}=0.3$, $p_{2a}=0.4$, and $p_{3a}=0.3$. Dividing the chance of object
$c$ using the uniform rule, we have $p_{1c}=c_{1c}=0.2$, $p_{2c}=c_{2c}=0$,
and $p_{3c}=c_{3c}=0.8$.

For agent $3$, we have $p_{3a}+p_{3c}=0.3+0.8>1$, which contradicts agent
feasibility, that is, $(p_{3a}+p_{3b}+p_{3c}=1)$.

###### Example 7.2

This example illustrates that URC mechanisms are not welfare non-bossy.
Suppose that $N=\\{1,2,3\\}$ is a set of agents, $A=\\{a,b,c\\}$ is a set of
objects, and ideal lotteries of agents over objects are

  * $c_{1}=(a:0.3,b:0.5,c:0.2)$,

  * $c_{2}=(a:0.7,b:0.2,c:0.1)$,

  * $c_{3}=(a:0.1,b:0.4,c:0.5)$.

Let $\alpha=123$ and $\beta=abc$. If we run $URC^{\alpha,\beta}$ on the
profile $c$, we have the following outcome

  * $p_{1}=(a:0.3,b:0.4,c:0.3)$,

  * $p_{2}=(a:0.6,b:0.2,c:0.2)$,

  * $p_{3}=(a:0.1,b:0.4,c:0.5)$.

Let $c^{\prime}_{2}=(a:0.7,b:0.3,c:0)$. The outcome of $URC^{\alpha,\beta}$ on
the profile $(c_{1},c^{\prime}_{2},c_{3})$ is

  * $p^{\prime}_{1}=(a:0.3,b:0.35,c:0.35)$,

  * $p^{\prime}_{2}=(a:0.6,b:0.3,c:0.1)$,

  * $p^{\prime}_{3}=(a:0.1,b:0.35,c:0.55)$.

We have $\mathbf{d}(c_{2},p_{2})=\mathbf{d}(c_{2},p^{\prime}_{2})=0.2$.
However, $\mathbf{d}(c_{3},p_{3})\neq\mathbf{d}(c_{3},p^{\prime}_{3})$.

###  7.2 Proofs for Section 2

Proof. Proof of Proposition 2.2:

Proof of if: If $P$ is an efficient random matching then it is not strictly
lottery dominated by any other random matching and thus by Lemma 7.3, it is
same-sided.

Proof of only if: Suppose that $P$ is same-sided but not efficient. Then $P$
is strictly lottery dominated by another random matching $J$. Either $J$ is
same-sided or not; if not, then by Lemma 7.3, there exists a same-sided random
matching $Q$ that strictly lottery dominates $J$ and thus strictly lottery
dominates $P$. So, there exists a same-sided random matching $Q$ that strictly
lottery dominates $P$.

As both $P$ and $Q$ are same-sided, for every object $a\in A$,

  * •

if it is $ED(c)$ then for all $i\in N$ $p_{ia}\leq c_{ia}$ and $q_{ia}\leq
c_{ia}$,

  * •

if it is $ES(c)$ then for all $i\in N$ $p_{ia}\geq c_{ia}$ and $q_{ia}\geq
c_{ia}$, and

  * •

if it it is $UN(c)$ then for all $i\in N$ $p_{ia}=c_{ia}$ and $q_{ia}=c_{ia}$.

Since $Q$ strictly lottery dominates $P$ there exists an agent $i$ such that
$\mathbf{d}(q_{i},c_{i})<\mathbf{d}(p_{i},c_{i})$.

We have

  * •

$d(p_{i},c_{i})=\sum_{a\in ED(c)}(c_{ia}-p_{ia})+\sum_{a\in
ES(c)}(p_{ia}-c_{ia})$

  * •

$d(q_{i},c_{i})=\sum_{a\in ED(c)}(c_{ia}-q_{ia})+\sum_{a\in
ES(c)}(q_{ia}-c_{ia})$

so, $\sum_{a\in ED(c)}(c_{ia}-p_{ia})+\sum_{a\in
ES(c)}(p_{ia}-c_{ia})>\sum_{a\in ED(c)}(c_{ia}-q_{ia})+\sum_{a\in
ES(c)}(q_{ia}-c_{ia})$ and thus

$\sum_{a\in ED(c)}(q_{ia}-p_{ia})+\sum_{a\in ES(c)}(p_{ia}-q_{ia})>0$.

Also, for all other agents $j\in N/\\{i\\}$, we have
$\mathbf{d}(q_{j},c_{j})\leq\mathbf{d}(p_{j},c_{j})$ and thus

$\sum_{a\in ED(c)}(q_{ja}-p_{ja})+\sum_{a\in ES(c)}(p_{ja}-q_{ja})\geq 0$

Therefore we have

$\sum_{j\in N}(\sum_{a\in ED(c)}(q_{ja}-p_{ja})+\sum_{a\in
ES(c)}(p_{ja}-q_{ja}))>0$

which implies

$\sum_{a\in ED(c)}(\sum_{j\in N}q_{ja}-\sum_{j\in N}p_{ja})+\sum_{a\in
ES(c)}(\sum_{j\in N}p_{ja}-\sum_{j\in N}q_{ja})>0$

$\sum_{a\in ED(c)}(1-1)+\sum_{a\in ES(c)}(1-1)>0$

Contradiction. $\Box$

###### Lemma 7.3

For every random matching $P$, either $P$ is same-sided or there exists a
same-sided random matching $Q$ that strictly lottery dominates $P$.

Proof. Proof of Lemma 7.3: Let $P$ be an arbitrary random matching. If $P$ is
same-sided we are done. Else, there exists a tuple $(b_{0},i,j)$ such that
$b_{0}\in A$, $i,j\in N$ and $p_{ib_{0}}<c_{ib_{0}}$ and
$p_{jb_{0}}>c_{jb_{0}}$. As $p_{ib_{0}}<c_{ib_{0}}$, and $\sum_{a\in
A}p_{ia}=\sum_{a\in A}c_{ia}=1$ there exists an object $b_{1}$ such that
$p_{ib_{1}}>c_{ib_{1}}$. If $p_{jb_{1}}<c_{jb_{1}}$ let $\alpha=c_{jb_{1}}$
else let $\alpha=1$. Consider

$0<\epsilon=\min(c_{ib_{0}}-p_{ib_{0}},p_{jb_{0}}-c_{jb_{0}},p_{ib_{1}}-c_{ib_{1}},\alpha-
p_{jb_{1}})$.

For agent $i$, let $q_{ib_{0}}=p_{ib_{0}}+\epsilon$,
$q_{ib_{1}}=p_{ib_{1}}-\epsilon$, and for all $a\in A/\\{b_{0},b_{1}\\}$,
$q_{ia}=p_{ia}$. For agent $j$, let $q_{jb_{0}}=p_{jb_{0}}-\epsilon$,
$q_{jb_{1}}=p_{jb_{1}}+\epsilon$, and for all $a\in A/\\{b_{0},b_{1}\\}$,
$q_{ja}=p_{ja}$. For any agent $i^{\prime}\in N/\\{i,j\\}$ let
$q_{i^{\prime}a}=p_{ia}$ for all $a\in A$.

For agent $j$,

$|q_{jb_{0}}-c_{jb_{0}}|+|q_{jb_{1}}-c_{jb_{1}}|=|p_{jb_{0}}-\epsilon-
c_{jb_{0}}|+|p_{jb_{1}}+\epsilon-c_{jb_{1}}|=$
$|p_{jb_{0}}-c_{jb_{0}}|-\epsilon+|p_{jb_{1}}-c_{jb_{1}}+\epsilon|$
$\leq|p_{jb_{0}}-c_{jb_{0}}|+|p_{jb_{1}}-c_{jb_{1}}|$.

Therefore, $\mathbf{d}(c_{j},q_{j})\leq\mathbf{d}(c_{j},p_{j})$. Also, for any
agent $i^{\prime}\in N/\\{i,j\\}$,
$\mathbf{d}(c_{i^{\prime}},q_{i^{\prime}})=\mathbf{d}(c_{i^{\prime}},p_{i^{\prime}})$.
For agent $i$, we have $\mathbf{d}(c_{i},q_{i})<\mathbf{d}(c_{i},p_{i})$, and
thus $Q$ strictly lottery-dominates $P$.

The value of $\epsilon$ is equal to one the values
$c_{ib_{0}}-p_{ib_{0}},p_{jb_{0}}-c_{jb_{0}},p_{ib_{1}}-c_{ib_{1}}$, or
$\alpha-p_{jb_{1}}$. So for the random matching $Q$, at least one of the
following equalities hold:

$q_{ib_{0}}=c_{ib_{0}},~{}q_{ib_{1}}=c_{ib_{1}},~{}q_{jb_{0}}=c_{jb_{0}},~{}q_{jb_{1}}=c_{jb_{1}}~{}or~{}q_{jb_{1}}=1.$
(3)

If $Q$ is same-sided, then we are done. Otherwise, we repeat the above process
for $Q$ until we obtain a same-sided bistochastic matrix. At each repetition,
at least one of the equalities in (3) holds true for the obtained $Q$ and some
agents $i,j\in A$, which guarantees that we cannot repeat the process an
infinite number of times. After a finite number of repetitions, we will
finally reach a bistochastic matrix $Q$ that is same-sided and strictly
lottery dominates $P$. $\Box$

Proof. Proof of Proposition 2.4.

Since $c^{\prime}_{i}$ is between $c_{i}$ and $\mu_{i}(c)$, and $\mu$ is same-
sided, we have for all $a\in A$

  * •

if $a\in ED(c)$ then $\mu_{ia}(c)\leq c^{\prime}_{ia}\leq c_{ia}$,

  * •

if $a\in UN(c)$ then $c^{\prime}_{ia}=c_{ia}$, and

  * •

if $a\in ES(c)$ then $c_{ia}\leq c^{\prime}_{ia}\leq\mu_{ia}(c)$.

Since $\mu$ is same-sided (efficient), we have

$\mathbf{d}(c_{i},\mu_{i}(c))=\sum_{a\in ED(c)}(c_{ia}-\mu_{ia}(c))+\sum_{a\in
ES(c)}(\mu_{ia}(c)-c_{ia})$

$=\sum_{a\in
ED(c)}\bigg{(}(c_{ia}-c^{\prime}_{ia})+(c^{\prime}_{ia}-\mu_{ia}(c))\bigg{)}+\sum_{a\in
ES(c)}\bigg{(}(\mu_{ia}(c)-c^{\prime}_{ia})+(c^{\prime}_{ia}-c_{ia})\bigg{)}$

$=\mathbf{d}(c_{i},c^{\prime}_{i})+\mathbf{d}(c^{\prime}_{i},\mu_{i}(c))$.

Therefore,

$\mathbf{d}(c_{i},\mu_{i}(c))=\mathbf{d}(c_{i},c^{\prime}_{i})+\mathbf{d}(c^{\prime}_{i},\mu_{i}(c)).$
(4)

By strategy proofness, we derive

$\mathbf{d}(c_{i},\mu_{i}(c))\leq\mathbf{d}(c_{i},\mu_{i}((c^{\prime}_{i},c_{-i})))$
(5)

and

$\mathbf{d}(c^{\prime}_{i},\mu_{i}((c^{\prime}_{i},c_{-i})))\leq\mathbf{d}(c^{\prime}_{i},\mu_{i}(c)).$
(6)

By triangle inequality, we have

$\mathbf{d}(c_{i},\mu_{i}((c^{\prime}_{i},c_{-i})))\leq\mathbf{d}(c_{i},c^{\prime}_{i})+\mathbf{d}(c^{\prime}_{i},\mu_{i}((c^{\prime}_{i},c_{-i}))).$
(7)

By Equations (6) and (7), we derive
$\mathbf{d}(c_{i},\mu_{i}((c^{\prime}_{i},c_{-i})))\leq\mathbf{d}(c_{i},c^{\prime}_{i})+\mathbf{d}(c^{\prime}_{i},\mu_{i}(c))$,
and by (4), we have
$\mathbf{d}(c_{i},\mu_{i}((c^{\prime}_{i},c_{-i})))\leq\mathbf{d}(c_{i},\mu_{i}(c))$.
Considering (5), we conclude

$\mathbf{d}(c_{i},\mu_{i}(c))=\mathbf{d}(c_{i},\mu_{i}((c^{\prime}_{i},c_{-i})).$
(8)

Since $c^{\prime}_{i}$ is between $c_{i}$ and $\mu_{i}(c)$, by in-betweenness
property, for all $a\in ED(c)$,
$\mu_{ia}((c^{\prime}_{i},c_{-i}))\leq\mu_{ia}(c)$, for all $a\in ES(c)$,
$\mu_{ia}((c^{\prime}_{i},c_{-i}))\geq\mu_{ia}(c)$, and for all $a\in UN(c)$,
$\mu_{ia}((c^{\prime}_{i},c_{-i}))=\mu_{ia}(c)$. Using equality (8), we derive
for all $a\in A$, $\mu_{ia}(c)=\mu_{ia}((c^{\prime}_{i},c_{-i}))$. $\Box$

###  7.3 Proofs for Section 3

Proof. Proof of Proposition 3.4.

We consider an arbitrary sequence of agents, denoted as $\alpha$, and an
arbitrary sequence of objects, denoted as $\beta$. For simplicity, instead of
using the notation $URC^{\alpha,\beta}$, we will use the shorthand $URC$. We
also Let $c=(c_{i})_{i\in N}$ be an arbitrary profile.

Proof of Efficiency.

It is easy to show that the outcome of the every URC mechanism is same-sided
and by Proposition 2.2, efficient. According to the definition of phase 1 in
URC mechanisms, for every $a\in ED(c)$, for all $i\in N$, we have
$URC_{ia}(c)=UR_{i}(c_{a})$, and for all $a\not\in ED(c)$, $w_{ia}=c_{ia}$. As
the uniform rule is same sided, we have for all $a\in ED(c)$, $URC_{ia}(c)\leq
c_{ia}$. For all $a\not\in ED(c)$, in phase 2 of URC, some amount is added to
$w_{ia}$, and since $w_{ia}=c_{ia}$, we will have $c_{ia}\leq URC_{ia}(c)$.
Therefore, $URC(c)$ is same-sided.

Proof of Strategy Proofness.

First of all since URC is same-sided, by Lemma 2.1, Equation (1),

$\mathbf{d}(c_{i},URC_{i}(c))=2\times\sum_{a\in ED(c)}(c_{ia}-URC_{ia}(c)).$
(9)

Since URC is same-sided, we have for all $a\in ED(c)$, $URC_{ia}(c)\leq
c_{ia}$. We partition $ED(c)$ into subsets $S_{1}$ and $S_{2}$ where $a\in
S_{1}$ if and only if $c_{ia}>URC_{ia}(c)$, and $a\in S_{2}$ if and only if
$c_{ia}=URC_{ia}(c)$. So, (9) implies

$\mathbf{d}(c_{i},URC_{i}(c))=2\times\sum_{a\in S_{1}}(c_{ia}-URC_{ia}(c)).$
(10)

If $S_{1}=\emptyset$, then the distance is equal zero and agent $i$ cannot get
better off by misreporting. So, we assume $S_{1}\neq\emptyset$.

In URC mechanisms, for every $a\in S_{1}$, before agent $i$ closes his tap on
tank $a$, the liquid in tank $a$ is exhausted. Suppose that agent $i$
misreports $c^{\prime}_{i}$ instead of $c_{i}$. For every $a\in S_{1}$,

  * •

if $c_{ia}\leq c^{\prime}_{ia}$ then before agent $i$ closes his tap on tank
$a$, the liquid in tank $a$ is exhausted. So,
$URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c)$. This implies
$(c_{ia}-URC_{ia}(c))=(c_{ia}-URC_{ia}((c^{\prime}_{i},c_{-i})))$,

  * •

if $c^{\prime}_{ia}<c_{ia}$ then either again before agent $i$ closes his tap
on tank $a$, the liquid in tank $a$ is exhausted, and
$URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c)$, or agent $i$ closes his tap
exactly when he receives $c^{\prime}_{ia}$, and thus
$URC_{ia}((c^{\prime}_{i},c_{-i}))=c^{\prime}_{ia}\leq URC_{ia}(c)$. This
implies $(c_{ia}-URC_{ia}(c))\leq(c_{ia}-URC_{ia}((c^{\prime}_{i},c_{-i})))$.

Therefore,

$\sum_{a\in S_{1}}(c_{ia}-URC_{ia}(c))\leq\sum_{a\in
S_{1}}(c_{ia}-URC_{ia}((c^{\prime}_{i},c_{-i}))).$ (11)

We have $\sum_{a\in A}c_{ia}-\sum_{a\in
A}URC_{ia}((c^{\prime}_{i},c_{-i}))=1-1=0$.

$0=\sum_{a\in A}c_{ia}-\sum_{a\in
A}URC_{ia}((c^{\prime}_{i},c_{-i}))=\sum_{a\in
S_{1}}(c_{ia}-URC_{ia}((c^{\prime}_{i},c_{-i})))+\sum_{a\in A\setminus
S_{1}}(c_{ia}-URC_{ia}((c^{\prime}_{i},c_{-i})))$

Because the above equality is equal zero, there are some objects
$b_{1},b_{2},...,b_{m}\in A\setminus S_{1}$ such that for all $k$,
$(c_{ib_{k}}-URC_{ib_{k}}((c^{\prime}_{i},c_{-i})))<0$, and

$-\sum_{k=1...m}(c_{ib_{k}}-URC_{ib_{k}}((c^{\prime}_{i},c_{-i})))\geq\sum_{a\in
S_{1}}(c_{ia}-URC_{ia}((c^{\prime}_{i},c_{-i})))$.

Therefore, the total distance of $URC_{ia}((c^{\prime}_{i},c_{-i}))$ from
$c_{ia}$ for objects $a\in S_{1}\cup\\{b_{1},b_{2},...,b_{m}\\}$ is greater
than $2\times\sum_{a\in S_{1}}(c_{ia}-URC_{ia}((c^{\prime}_{i},c_{-i}))$.
Using (10) and (11), we have the total distance of
$URC_{ia}((c^{\prime}_{i},c_{-i}))$ from $c_{ia}$ for objects $a\in
S_{1}\cup\\{b_{1},b_{2},...,b_{m}\\}$ is greater than
$\mathbf{d}(c_{i},URC_{i}(c))$. Therefore, agent $i$ by misreporting
$c^{\prime}_{i}$ gets further from his ideal lottery $c_{i}$.

Proof of Replacement Monotonicity.

Let $i\in N$ be an arbitrary. Let $c^{\prime}_{i}$ be such that

  * •

$ED(c)=ED((c^{\prime}_{i},c_{-i}))$, and

  * •

for all $a\in ED(c)$, $c^{\prime}_{ia}\leq c_{ia}$.

Let $a\in ED(c)$ be arbitrary. According to the definition of phase 1 in URC
mechanisms, for all $j\in N$, $URC_{ja}(c)=UR_{j}(c_{a})$, and
$URC_{ja}((c^{\prime}_{i},c_{-i}))=UR_{j}(c^{\prime}_{a})$ where
$c^{\prime}_{a}=(c^{\prime}_{ia},c_{-ia})$. It is easy to show that since
$c^{\prime}_{ia}\leq c_{ia}$ then for every other agents $j\in
N\setminus\\{i\\}$, in the uniform rule mechanism, agent $j$ can obtain more
or at least an equal amount from object $a$. In other words, for all $j\in
N\setminus\\{i\\}$, $UR_{j}(c_{a})\leq UR_{j}(c^{\prime}_{a})\leq c_{ja}$.
Thus for all $a\in ED(c)$,
$(c_{ja}-URC_{ja}(c))\geq(c_{ja}-URC_{ja}((c^{\prime}_{i},c_{-i})))$.
Utilizing Lemma 2.1, Equation (1), we have for all $j\in N\setminus\\{i\\}$,

$\mathbf{d}(c_{j},URC_{j}(c))\geq\mathbf{d}(c_{j},URC_{j}((c^{\prime}_{i},c_{-i}))$,

which is equivalent to
$URC_{j}((c^{\prime}_{i},c_{-i})\succeq_{c_{j}}URC_{j}(c)$.

Proof of Non-bossiness.

Let $i\in N$, and $c^{\prime}_{i}$ be such that for all $a\in ED(c)$,
$URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c)$. Let $a\in ED(c)$ be
arbitrary. There are two cases possible:

  * 1.

If, when agent $i$ closes his tap on tank $a$, there exists still liquid in
the tank, then closing the tap later $(c^{\prime}_{ia}>c_{ia})$ or closing the
tap sooner $(c^{\prime}_{ia}<c_{ia})$ would result in
$URC_{ia}((c^{\prime}_{i},c_{-i}))\neq URC_{ia}(c)$. So, we must have
$c^{\prime}_{ia}=c_{ia}$. Thus, for all $j\in N$,
$URC_{ja}((c^{\prime}_{i},c_{-i}))=URC_{ja}(c)$.

  * 2.

If, when agent $i$ closes his tap on tank $a$, already the liquid in the tank
is exhausted, then

    * –

if he closes the tap later $(c^{\prime}_{ia}>c_{ia})$, it does not effect the
process, and thus for all $j\in N$,
$URC_{ja}((c^{\prime}_{i},c_{-i}))=URC_{ja}(c)$.

    * –

If he closes the tap sooner $(c^{\prime}_{ia}<c_{ia})$ but not sooner than the
time when the liquid in the tank is not yet exhausted, then again it does not
effect the process, and thus for all $j\in N$,
$URC_{ja}((c^{\prime}_{i},c_{-i}))=URC_{ja}(c)$.

    * –

If he closes the tap sooner $(c^{\prime}_{ia}<c_{ia})$ such that the liquid in
the tank is not yet exhausted, then the amount that agent $i$ receives in
phase 1, i.e., $w_{ia}((c^{\prime}_{i},c_{-i}))$ is less than $URC_{ia}(c)$.
If $(\sum_{j\in N\setminus\\{i\\}}c_{ja})\leq(1-URC_{ia}(c))$, then for all
$j\in N$, $URC_{ja}((c^{\prime}_{i},c_{-i}))=URC_{ja}(c)$, and we are done. If
$(\sum_{j\in N\setminus\\{i\\}}c_{ja})>(1-URC_{ia}(c))$, then since agent $i$
closes sooner other agents receive more, that is $(\sum_{j\in
N\setminus\\{i\\}}URC_{ia}((c^{\prime}_{i},c_{-i})))>(1-URC_{ia}(c))$. So, the
amount of object $a$ remaining for phase 2 (after phase 1) is insufficient for
agent $i$ to reach $URC_{ia}(c)$, and thus
$URC_{ia}((c^{\prime}_{i},c_{-i}))<URC_{ia}(c)$, and the assumption
$URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c)$ does not hold true.

Proof of In-Betweenness.

Let $i\in N$ be arbitrary, and $c^{\prime}_{i}$ be between $c_{i}$ and
$URC_{i}(c)$. We prove

for all $a\in A$, $URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c)$.

1) For $a\in UN(c)$, due to same-sideness of URC, we have
$URC_{ia}(c)=c_{ia}$. Since $c^{\prime}_{i}\in Between(c_{i},URC_{i}(c))$, we
have $c^{\prime}_{ia}=c_{ia}$, and thus
$URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c)$.

2) Let $a\in ED(c)$ be arbitrary. Since $c^{\prime}_{i}\in
Between(c_{i},URC_{i}(c))$, we have

$URC_{ia}(c)\leq c^{\prime}_{ia}\leq c_{ia}.$ (12)

Regarding the profile $c$, two cases are possible:

  * •

Case 1: when agent $i$ closes his tap on tank $a$, there exists still liquid
in the tank. In this case, we have $URC_{ia}(c)=c_{ia}$. By (12), we have
$c^{\prime}_{ia}=c_{ia}$ and thus
$URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c)$.

  * •

Case 2: when agent $i$ closes his tap on tank $a$, the liquid is already
exhausted. So, the amount of liquid $a$ that agent $i$ takes is dependent on
the ideals of other agents for object $a$. In this case, due to (12), since
$c^{\prime}_{ia}\geq URC_{ia}(c)$, when agent $i$ closes his tap on the tank
for ideal $c^{\prime}_{ia}$, the liquid is also exhausted already. Therefore,
$URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c)$.

Therefore, we have for all $i\in N$, for all $a\in ED(c)\cup UN(c)$

$URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c)\leq c_{ia}$ (13)

3) Let $a\in ES(c)$, since $c^{\prime}_{i}$ is between $c_{i}$ and
$URC_{i}(c)$, we have

$c_{ia}\leq c^{\prime}_{ia}\leq URC_{ia}(c).$ (14)

In phase 1, for the profile $(c^{\prime}_{i},c_{-i})$, agent $i$ takes
$w_{ia}=c^{\prime}_{ia}\leq URC_{ia}(c)$ amount of object $a$, and other
agents $j\in N\setminus\\{i\\}$ takes $w_{ia}=c_{ia}$. So, after the end of
phase 1, for all $a\in ES(c)$, for every agent $i\in N$,

$w_{ia}\leq URC_{ia}(c).$ (15)

Now let’s analyze phase 2 of URC, and suppose that for some $t$,
$\alpha(t)=i$, and for some $s$, $\beta(s)=a$. Let $t=1$ and $s=1$, and we are
at the start of phase 2, and it is the turn of agent $\alpha(t)=i$ to take
some amount of $\beta(s)=a$. Recall that in the URC mechanism $w_{jb}$
represents the current amount of object $b$ taken by agent $j$. By (13) and
(15), at the current state:

  * *)

Agent $i$ has taken $(1-\sum_{b\in A\setminus\\{a\\}}w_{ib})\geq(1-\sum_{b\in
A\setminus\\{a\\}}URC_{ib}(c))=URC_{ia}(c)$ of other objects except object
$a$. The inequality $(1-\sum_{b\in A\setminus\\{a\\}}w_{ib})\geq URC_{ia}(c)$
means that the bucket of agent $i$ has capacity to contain $URC_{ia}(c)$ of
object $a$.

  * **)

Other agents except $i$ has taken $(1-\sum_{j\in
N\setminus\\{i\\}}w_{ja})\geq(1-\sum_{j\in
N\setminus\\{i\\}}URC_{ja}(c))=URC_{ia}(c)$. amount of object $a$. The
inequality $(1-\sum_{j\in N\setminus\\{i\\}}w_{ja})\geq URC_{ia}(c)$ means
that there exists still at least $URC_{ia}(c)$ amount of liquid $a$ totally in
tank $a$ and in bucket of agent $i$.

In phase 2, when agent $\alpha(t)=i$ wants to take from object $\beta(s)=a$,
he takes as much as he can until either the object $a$ is exhausted (the tank
$a$ is empty) or he has no capacity (his bucket is full).

By (*) and (**), agent $i$, in his turn, can reach $URC_{ia}(c)$ for liquid
$a$, in his bucket, and thus

$URC_{ia}((c^{\prime}_{i},c_{-i}))\geq URC_{ia}(c).$ (16)

Furthermore, we argue $URC_{ia}((c^{\prime}_{i},c_{-i}))\leq URC_{ia}(c)$. We
compare the bucket of agent $i$ at the beginning of phase 2, for two profiles
$c$ and $(c^{\prime}_{i},c_{-i})$. Let $buk_{i}(c)$ refers to the bucket of
agent $i$ at the beginning of phase 2 for profile $c$, and similarly
$buk_{i}((c^{\prime}_{i},c_{-i}))$ refers to the bucket of agent $i$ at the
beginning of phase 2 for profile $(c^{\prime}_{i},c_{-i})$. Because of (13),
for every object $b\in ED(c)\cup UN(c)$, the amount of liquid $b$ in
$buk_{i}(c)$ is the same as in $buk_{i}((c^{\prime}_{i},c_{-i}))$, and since
$c^{\prime}_{i}$ is between $c_{i}$ and $URC_{i}(c)$, for every object $b\in
ES(c)$, at the beginning of phase 2, according to the instruction of URC
mechanisms, the amount of liquid $v$ in $buk_{i}(c)$ is equal to $c_{ib}$ not
more than the amount of $a$ in $buk_{i}((c^{\prime}_{i},c_{-i}))$ which is
equal to $c^{\prime}_{ib}$. So, at the beginning of phase 2,

$buk_{i}(c)$ has more free capacity than $buk_{i}((c^{\prime}_{i},c_{-i}))$
($\\#$)

Also, let $tank_{a}(c)$ be the status of tank $a$ running URC for profile $c$,
and $tank_{a}((c^{\prime}_{i},c_{-i}))$ be the status of tank $a$ running URC
for profile $(c^{\prime}_{i},c_{-i})$. Since $c^{\prime}_{i}$ is between
$c_{i}$ and $URC_{i}(c)$, at the beginning of phase 2,

> the amount of liquid in $tank_{a}(c)$ is not less than the the amount of
> liquid in $tank_{a}((c^{\prime}_{i},c_{-i}))$ ($\\#\\#$)

Since $buk_{i}(c)$ has more free capacity than
$buk_{i}((c^{\prime}_{i},c_{-i}))$ ($\\#$) and the amount of liquid in
$tank_{a}(c)$ is not less than the the amount of liquid in
$tank_{a}((c^{\prime}_{i},c_{-i}))$ ($\\#\\#$), for profile $c$, agent $i$
takes out from object $a$ not less than the amount he takes outs from object
$a$ for profile $(c^{\prime}_{i},c_{-i})$, so we conclude

$~{}URC_{ia}((c^{\prime}_{i},c_{-i}))\leq URC_{ia}(c).$ (17)

Therefore, (16) and (17) implies:

$URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c).$ (18)

So, we proved for $t=1$, and $s=1$ that Equation 18 holds true. For $t=1$ and
$s=2$, since we already showed Equation 18 for $t=1$ and $s=1$, the conditions
*) and **) yet holds true and we can repeat the same argument, and prove that
For $t=1$ and $s=2$, also Equation 18 holds. By induction, we have for all
$k=1...n$, for $t=1$ and $s=k$, Equation 18 holds true. For $t>1$, since

  * •

the ideal lottery of all agents $\alpha(1),\alpha(2),...,\alpha(t-1)$ are the
same in both profiles $c$ and $(c^{\prime}_{i},c_{-i})$,

  * •

for every excess supply object $b$, $c^{\prime}_{ib}\leq\mu_{ib}(c)$,

  * •

for all $j\in N$, for all $b\in ED(c)\cup UN(c)$,
$URC_{ib}(c)=URC_{ib}((c^{\prime}_{i},c_{-i}))$,

when we run the mechanism for profile $(c^{\prime}_{i},c_{-i})$, agents
$\alpha(1),\alpha(2),...,\alpha(t-1)$, in their turn, take out the same amount
of objects as they would for the profile $c$. Thus, again conditions *) and
**) holds true and we can repeat the same argument for $t>1$. Therefore,

$for~{}all~{}a\in EC(c),~{}URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c).$

In this way, we proved

$for~{}all~{}a\in A,~{}URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c),$

which implies that URC mechanisms satisfy in-betweenness.

Proof of Envy Freeness.

The proof of envy freeness is derived from Lemma 2.1, Equation (1), and the
fact that the uniform rule is envy free. By Equation (1), we can calculate the
distance based on excess demand objects, and all excess demand objects are
exhausted in phase 1 of URC, and divided among the agents uniformly. Since the
uniform rule is envy free, we have URC mechanisms are also envy free.

Proof of Anonymity.

The proof of anonymity is straightforward. By Lemma 2.1, Equation (1), we can
calculate the distance based on excess demand objects, and all excess demand
objects are exhausted in phase 1 of URC. So, the distances are independent on
phase 2 of URC mechanisms, and permutations does not effect phase 1 of URC
mechanisms. $\Box$

Proof. Proof of Proposition 3.5.

Let $|A|=|N|=n\geq 3$, and $a,b\in A$. For every agent $j\in N$, let $z^{j}$
be a profile where

  * •

$ES(z^{j})=\\{a\\}$,

  * •

for all $i\in N$, $z^{j}_{ia}=0$,

  * •

$z^{j}_{jb}=1$ and $b\in UN(z^{j})$.

Let’s assume, for the sake of contradiction, that there exists an efficient
mechanism $\mu$ satisfying the following assumption:

> for every two profiles $c$ and $c^{\prime}$ with $ES(c)=ES(c^{\prime})$,
> that coincide on $ES(c)$, we have for every $i\in N$,
> $\mathbf{d}(\mu_{i}(c),c_{i})=\mathbf{d}(\mu_{i}(c^{\prime}),c^{\prime}_{i})$.

Because $\mu$ is efficient (same-sided, as per Proposition 2.2), and $b\in
UN(z^{j})$, we have $\mu_{jb}(z^{j})=z^{j}_{jb}=1$ implying
$\mathbf{d}(\mu_{j}(z^{j}),z^{j}_{j})=0$, implying $\mu_{j}(z^{j})=z^{j}_{j}$,
specifically $\mu_{ja}(z^{j})=z^{j}_{ja}=0$.

Consider an arbitrary profile $x$ with $ES(x)=ES(z^{j})=\\{a\\}$, where $x$
coincides with $z^{j}$ on the set $\\{a\\}$. As $x$ and $z^{j}$ coincide on
$ES(z^{j})$, according to the assumption for the mechanism $\mu$, we conclude
$\mathbf{d}(\mu_{j}(x),x_{j})=\mathbf{d}(\mu_{j}(z^{j}),z^{j}_{j})=0$. leading
to $\mu_{j}(x)=x_{j}$, especially $\mu_{ja}(x)=x_{ja}=0$. So,

> for every profile $x$ with $ES(x)=ES(z^{j})=\\{a\\}$, where $x$ coincides
> with $z^{j}$ on the set $\\{a\\}$ we have $\mu_{ja}(x)=x_{ja}=0$.

Let $x$ be a profile such that $ES(x)=\\{a\\}$, and for all agent $i\in N$,
$x_{ia}=0$. For every agent $j\in N$, the profile $x$ coincides with $z^{j}$
on the set $\\{a\\}$, and thus we have: for every $j\in N$,
$\mu_{ja}(x)=x_{ja}=0$ which implies $\sum_{i\in N}\mu_{ia}=0<1$. It
contradicts with object feasibility of the mechanism $\mu$. $\Box$

###  7.4 Proofs for Section 4

Proof. Proof of Lemma 4.1:

Let $c$ and $c^{\prime}$ be two profiles such that

  * $ED(c)=ED(c^{\prime})=\\{a\\}$,

  * for an agent $j\in N$, for all $b\in ED(c)$, $c_{jb}=c^{\prime}_{jb}$, and

  * for all agents $i\in N\setminus\\{j\\}$, $c^{\prime}_{i}=c_{i}$, i.e. $c^{\prime}=(c^{\prime}_{j},c_{-j})$.

Since $\mu$ is strategy proof, we have

$\mathbf{d}(c_{j},\mu_{j}(c))\leq\mathbf{d}(c_{j},\mu_{j}(c^{\prime})).$ (19)

Furthermore, due to (19) and having that for all objects $b\in ED(c)$,
$c^{\prime}_{jb}\leq c_{jb}$, we can apply Definition 2.3 of replacement
monotonicity, and conclude as follows:

$for~{}all~{}i\in
N\setminus\\{j\\},~{}\mathbf{d}(c_{i},\mu_{i}(c))\geq\mathbf{d}(c_{i},\mu_{i}(c^{\prime})).$
(20)

Similarly, because $\mu$ is strategy proof, we have

$\mathbf{d}(c^{\prime}_{j},\mu_{j}(c^{\prime}))\leq\mathbf{d}(c^{\prime}_{j},\mu_{j}(c)).$
(21)

Since for all objects $b\in ED(c^{\prime})$, we have $c_{jb}\leq
c^{\prime}_{jb}$, and due to (21), we can apply the replacement monotonicity
property, leading to the following conclusion:

$for~{}all~{}i\in
N\setminus\\{j\\},~{}\mathbf{d}(c_{i},\mu_{i}(c^{\prime}))\geq\mathbf{d}(c_{i},\mu_{i}(c)).$
(22)

Due to (20) and (22), we have:

$for~{}all~{}i\in
N\setminus\\{j\\},~{}\mathbf{d}(c_{i},\mu_{i}(c^{\prime}))=\mathbf{d}(c_{i},\mu_{i}(c)).$
(23)

By efficiency and using Lemma 2.1, Equation (1), we have for all $i\in
N\setminus\\{j\\}$, $\mathbf{d}(c_{i},\mu_{i}(c))=2\times\sum_{b\in
ED(c)}(c_{ib}-\mu_{ib}(c))$ and
$\mathbf{d}(c_{i},\mu_{i}(c^{\prime}))=2\times\sum_{b\in
ED(c^{\prime})}(c^{\prime}_{ib}-\mu_{ib}(c^{\prime}))$. Since for all $i\neq
j$, $c^{\prime}_{i}=c_{i}$, and $ED(c)=ED(c^{\prime})$, using (23), we derive

$for~{}all~{}i\in N\setminus\\{j\\},~{}\sum_{b\in ED(c)}\mu_{ib}(c)=\sum_{b\in
ED(c)}\mu_{ib}(c^{\prime}).$ (24)

By object feasibility and (24), we have for all $i\in N$, $\sum_{b\in
ED(c)}\mu_{ib}(c)=\sum_{b\in ED(c)}\mu_{ib}(c^{\prime})$. Since
$ED(c)=ED(c^{\prime})=\\{a\\}$, we have for all $i\in N$,
$\mu_{ia}(c)=\mu_{ia}(c^{\prime})$. $\Box$

Proof. Proof of Lemma 4.2.

Let $c$ and $c^{\prime}$ be two profile with $ED(c)=ED(c^{\prime})=\\{a\\}$,
and $c_{a}=c^{\prime}_{a}$. We start from the profile $c^{0}=c$ and construct
a sequence of profiles

$c=c^{0},c^{1},c^{2},c^{3},\ldots,c^{m}=c^{\prime}$

such that for all $t<m$, $c^{t}$ and $c^{t+1}$ satisfies conditions of Lemma
4.1 for some agent $j_{t}\in N$, and thus we have for all $i\in N$,
$\mu_{ia}(c^{t})=\mu_{ia}(c^{t+1})$.

Visualize each non-excess demand object (objects in the set
$A\setminus\\{a\\}$) as a warehouse with a capacity 1. In this setup, we have
a collection of warehouses:
$A\setminus\\{a\\}=\\{w_{1},w_{2},\ldots,w_{n-1}\\}$. We imagine that each
agent has occupied warehouses with their items, and each profile corresponds
to an occupation of warehouses with the agent’s items.

We start at the initial profile $c^{0}=c$, where for each
$k\in\\{1,2,\ldots,n-1\\}$, each agent $i\in N$ has occupied a quantity
$c_{iw_{k}}$ of the warehouse $w_{k}$. We denote the available capacity of
each warehouse $w_{k}$, by $Q(w_{k})$. We say a warehouse does not have
available capacity whenever $Q(w_{k})=0$. Initially, for every
$k\in\\{1,2,\ldots,n-1\\}$, $Q(w_{k})=1-\sum_{i\in N}c_{iw_{k}}$. Note that
since the only excess demand object of $c^{0}=c$ is object $a$, we have for
all $k$, $Q(w_{k})\geq 0$. The following algorithm explains how we convert
profile $c$ to $c^{\prime}$ by asking agents to move their items between
warehouses.

  * •

Initially, for each $k\in\\{1,2,\ldots,n-1\\}$, each agent $i\in N$ has
occupied a quantity $c_{iw_{k}}$ of the warehouse $w_{k}$.

  * •

At the end of the algorithm, for each $k\in\\{1,2,\ldots,n-1\\}$, each agent
$i\in N$ has occupied a quantity $c^{\prime}_{iw_{k}}$ of the warehouse
$w_{k}$.

  * 0.

Set $t=1$ and $s=1$.

  * 1.

For agent $t$, we want to change $c_{tw_{s}}$ to $c^{\prime}_{tw_{s}}$.

    * 1.1.

If $c_{tw_{s}}>c^{\prime}_{tw_{s}}$ then we ask agent $t$ to move the excess,
denoted as $\epsilon=(c_{tw_{s}}-c^{\prime}_{tw_{s}})$, from the warehouse
$w_{s}$ to warehouses $w_{s+1},w_{s+2},\ldots,w_{n-1}$. To do this, we ask him
first transfer an amount $v=\min(\epsilon,\sum_{k=s+1}^{n-1}Q(w_{k}))$ from
$w_{s}$ to warehouses $w_{s+1},w_{s+2},\ldots,w_{n-1}$. If $v<\epsilon$,
agents $t+1,t+2,\ldots,n$ are sequentially requested to move their items as
much as possible from warehouses $w_{s+1},w_{s+2},...,w_{n-1}$ to those
warehouses $w_{1},w_{2},...,w_{s}$ that have available capacity, effectively
freeing up space in warehouses $w_{s+1},w_{s+2},...,w_{n-1}$. Then agent $t$
proceeds to move as much as possible from $w_{s}$ to warehouses
$w_{s+1},w_{s+2},...,w_{n-1}$. This process continues until agent $i$ has the
quantity $c^{\prime}_{tw_{s}}$ in the warehouse $w_{s}$.

    * 1.2.

If $c_{tw_{s}}<c^{\prime}_{tw_{s}}$ then we ask agent $t$ to make up for the
shortfall, represented as $\epsilon=(c^{\prime}_{tw_{s}}-c_{tw_{s}})$, by
moving items from warehouses $w_{s+1},w_{s+2},\ldots,w_{n-1}$ to warehouse
$w_{s}$. He moves items from $w_{s+1},w_{s+2},\ldots,w_{n-1}$ to $w_{s}$ until
one of the following occurs: either he has moved $\epsilon$ items, or,
warehouses $w_{s+1},w_{s+2},\ldots,w_{n-1}$ are empty, or $w_{s}$ has no
available capacity. In the first case, the goal is achieved. The second case
does not happen, because $\sum_{k\geq s}c_{tw_{k}}=\sum_{k\geq
s}c^{\prime}_{tw_{k}}$, and since $c_{tw_{s}}<c^{\prime}_{tw_{s}}$,
$w_{s+1},w_{s+2},\ldots,w_{n-1}$ cannot be empty. If the third case occurs,
agents $t+1,t+2,\ldots,n$ are sequentially requested to move their items as
much as possible from warehouses $w_{s}$ to warehouses
$w_{s+1},w_{s+2},...,w_{n-1}$, effectively freeing up space in warehouses
$w_{s}$. Then agent $t$ proceeds to move his items as much as possible from
$w_{s+1},w_{s+2},...,w_{n-1}$ to the warehouse $w_{s}$. This process continues
until agent $i$ has the quantity $c^{\prime}_{tw_{s}}$ in the warehouse
$w_{s}$.

    * 1.3.

If $s<n-1$, update $s$ to $s+1$, go to Step 1.1.

  * 2.

If $t<n$, update $t$ to $t+1$, go to Step 1.

For $s=n-1$, since agent $t$ has already changed $c_{tw_{s}}$ to
$c^{\prime}_{tw_{s}}$ for all $s<n-1$, according to agent feasibility, the
amount of his items that finally ends up in warehouse $w_{n-1}$ is equal to
$c^{\prime}_{tw_{n-1}}$.

For $t=n$, since all agents $1,2,\ldots,n-1$ have already changed for all $s$,
$c_{tw_{s}}$ to $c^{\prime}_{tw_{s}}$, when agent $n$ wants to move his items
according to Step 1.1 and Step 1.2, he does not face a situation where the
warehouses do not have available capacity.

During execution of the algorithm, each $(c_{ia},(w_{ik})_{1\leq k\leq
n-1})_{i\in N}$, which corresponds to an occupation of warehouses with the
agent’s items, forms a profile. These profiles are updated during the
execution of the algorithm, gradually converging to the final profile
$c^{\prime}$. Note that in the above algorithm, always one agent move his
items between warehouses which are representing non-excess demand objects. So,
in above algorithm, every time that an agent moves his items between
warehouses conditions of Lemma 4.1 are fulfilled. Therefore, thanks to Lemma
4.1, for all agents $i\in N$, the value of $\mu_{ia}$ remains unaltered for
all profiles $(c_{ia},(w_{ik})_{1\leq k\leq n-1})_{i\in N}$ that occur during
the execution of the above algorithm. Therefore, we have for all $i\in N$,
$\mu_{ia}(c)=\mu_{ia}(c^{\prime})$. $\Box$

###### Remark 7.4

One may note that in the proofs of Lemma 4.1 and Lemma 4.2, we did not make
use of the assumption that $ED(c)$ has only one element. Therefore, if $\mu$
is a strategy proof, efficient, and replacement monotonic mechanism, then for
any two profiles $c$ and $c^{\prime}$ with $ED(c)=ED(c^{\prime})$ and for all
$a\in ED(c)$, $c_{a}=c^{\prime}_{a}$, we have the following result: for all
$i\in N$,

$\sum_{a\in ED(c)}\mu_{ia}(c)=\sum_{a\in ED(c)}\mu_{ia}(c^{\prime})$, and
$\mathbf{d}(c_{i},\mu_{i}(c))=\mathbf{d}(c_{i},\mu_{i}(c^{\prime}))$.

Proof. Proof of Lemma 4.3.

Let $\mu$ be a strategy proof, efficient, replacement monotonic and anonymous
mechanism. Let $c$ be a profile with $ED(c)=\\{a\\}$. By utilizing Lemma 4.2,
it becomes evident that for any other profile $c^{\prime}$ with
$c^{\prime}_{a}=c_{a}$ and $ED(c^{\prime})=ED(c)={a}$, for every agent $i\in
N$, $\mu_{ia}(c^{\prime})=\mu_{ia}(c)$. So, for every agent $i$, his
allocation for object $a$ is independent on the ideals for non-excess demand
objects and only is dependent on $c_{a}$. This means that the function
$\pi_{a}\circ\mu~{}(-)=(\mu_{ia}(-))_{i\in N}$ is a well-defined function of
$c_{a}$, where $\pi_{a}$ is a projection mapping on the allocation for object
$a$. Since $\mu$ is same-sided, strategy proof and anonymous, these properties
extend to $\pi_{a}\circ\mu$. According to the characterization theorem proved
by Y. SPrumont, (1999) in page 511 of [34], $\pi_{a}\circ\mu$ is the uniform
rule, and thus for all $i\in N$, $\mu_{ia}(c)=UR_{i}(c_{a})$. Hence, by Lemma
2.1, Equation (1), for every profile $c$ with $ED(c)=\\{a\\}$, we have for all
$i\in N$, $\mathbf{d}(c_{i},\mu_{i}(c))=2\times(c_{ia}-UR_{i}(c_{a}))$.

On the other hand, because URC mechanisms are efficient, utilizing Lemma 2.1,
Equation (1), and definition of phase 1 of URC mechanisms, for all $i\in N$,
$\mathbf{d}(c_{i},URC_{i}(c))=2\times(c_{ia}-UR_{i}(c_{a}))$. Therefore,
$\mathbf{d}(c_{i},\mu_{i}(c))=\mathbf{d}(c_{i},URC_{i}(c))$, and we are done.
$\Box$

Proof. Proof of Theorem 4.4.

Let $\mu$ be a strategy proof, efficient, replacement monotonic, non-bossy,
in-between and anonymous mechanism. Let $c=(c_{i})_{i\in N}$ be arbitrary
profile. Utilizing Corollary 2.5, and Lemma 4.3, we prove for all $b\in
ED(c)$, for all $i\in N$, $\mu_{ib}(c)=UR_{i}(c_{b})$ where
$c_{b}=(c_{ib})_{i\in N}$. Thus for all $i\in N$,
$\mu_{i}(c)\equiv_{c_{i}}URC_{i}(c)$.

Let $a\in ED(c)$ be arbitrary. we transform the profile $c$ into another
profile called $z^{n}$ featuring only a single excess demand object,
$ED(z^{n})=\\{a\\}$, and for every $i\in N$, $\mu_{ia}(c)=\mu_{ia}(z^{n})$ .

For agent $1\in N$, we let

$c^{\prime}_{1}=(c_{1a},(\mu_{1b}(c))_{b\in
ED(c)\setminus\\{a\\}},(c_{1b})_{b\in UN(c)},(l_{1b})_{b\in ES(c)}))$

where for each $b\in ES(c)$, $c_{1b}\leq l_{1b}\leq\mu_{1b}(c)$. The lottery
$c^{\prime}_{1}$ is between $c_{1}$ and $\mu_{1}(c)$.

We replace $c_{1}$ with $c^{\prime}_{1}$ in profile $c$ and construct the
profile $z^{1}=(c^{\prime}_{1},c_{2},c_{3},\ldots c_{n})$. By Proposition 2.4,

$for~{}all~{}b\in A~{}\mu_{1b}(c)=\mu_{1b}(z^{1}).$ (25)

Since $\mu$ is same-sided, we have

$ED(z^{1})\subseteq ED(c),~{}ES(z^{1})\subseteq ES(c),~{}a\in
ED(z^{1}),~{}z^{1}_{a}=c_{a}$ (26)

By non-bossiness (Section 2.3), and (25) we have

$for~{}all~{}j\in N,~{}for~{}all~{}b\in ED(c),~{}\mu_{jb}(z^{1})=\mu_{jb}(c).$
(27)

We repeat the above process on the profile $z^{1}$ for agent $2\in N$, and
construct a lottery $c^{\prime}_{2}$ (similar to the way that we construct
$c^{\prime}_{1}$)

$c^{\prime}_{2}=(z^{1}_{2a},(\mu_{2b}(z^{1}))_{b\in
ED(z^{1})\setminus\\{a\\}},(z^{1}_{2b})_{b\in UN(z^{1})},(l_{2b})_{b\in
ES(z^{1})}))$

where for each $b\in ES(z^{1})$, $c_{2b}\leq l_{2b}\leq\mu_{2b}(z^{1})$. The
lottery $c^{\prime}_{2}$ is between $c_{2}$, and $\mu_{2}(z^{1})$. Note that
because of (27) and (26), we have

$c^{\prime}_{2}=(c_{2a},(\mu_{2b}(c))_{b\in
ED(z^{1})\setminus\\{a\\}},(z^{1}_{2b})_{b\in UN(z^{1})},(l_{2b})_{b\in
ES(z^{1})}))$.

We replace $z^{1}_{2}$ with $c^{\prime}_{2}$ in profile $z^{1}$ and construct
the profile $z^{2}=(c^{\prime}_{1},c^{\prime}_{2},c_{3},\ldots c_{n})$. since
$\mu$ is same-sided $ED(z^{2})\subseteq ED(z^{1})$. According to the
definition of the lottery $c^{\prime}_{2}$, and (27), we have

for agents $i=1,2$, for all objects $b\in ED(z^{2})\setminus\\{a\\}$,
$z^{2}_{ib}=\mu_{ib}(c)$.

Also it is easy to check that $z^{2}_{a}=z^{1}_{a}=c_{a}$.

Since $c^{\prime}_{2}$ is between $c_{2}$, and $\mu_{2}(z^{1})$, by
Proposition 2.4, we derive for all $b\in A$,
$\mu_{2b}(z^{1})=\mu_{2b}(z^{2})$. With a similar line of reasoning, and by
leveraging Corollary 2.5, we can demonstrate

$for~{}all~{}i\in N,~{}for~{}all~{}b\in
ED(z^{1}),~{}\mu_{ib}(z^{2})=\mu_{ib}(z^{1}).$ (28)

If we repeat the above process for all agents $k\in N=\\{1,2,...,n\\}$, we
construct profiles

$z^{0}=c,z^{1},z^{2},...,z^{n}$

where for $k<n$: $z^{k+1}_{a}=z^{k}_{a}=c_{a}$, $a\in ED(z^{k+1})\subseteq
ED(z^{k})$, and

$for~{}all~{}i\in N,~{}for~{}all~{}b\in
ED(z^{k}),~{}\mu_{ib}(z^{k+1})=\mu_{ib}(z^{k}).$ (29)

By (29) and the definitions of profiles $z^{1},z^{2},...,z^{n}$, we have for
all $k<n$,

$for~{}agents~{}i=1,2,...,k+1,~{}for~{}all~{}b\in
ED(z^{k+1})\setminus\\{a\\},~{}z^{k+1}_{ib}=\mu_{ib}(c).$ (30)

For the profile $z^{n}$ we prove $ED(z^{n})=\\{a\\}$. Suppose that $d\in
ED(z^{n})\setminus\\{a\\}$. By (30), we have for all $i\in N$,
$z^{n}_{id}=\mu_{id}(c)$. Thus $\sum_{i\in N}z^{n}_{id}=\sum_{i\in
N}\mu_{id}(c)=1$, hence $d\in UN(z^{n})$, contradiction. Also, by (29), we
have for every $i\in N$, $\mu_{ia}(c)=\mu_{ia}(z^{n})$ .

Since $ED(z^{n})=\\{a\\}$, by Lemma 4.3, we have for every $i\in N$,
$\mu_{ia}(z^{n})=UR_{i}(z^{n}_{a})$. By (29), for all $i\in N$,
$\mu_{ia}(c)=\mu_{ia}(z^{n})$, thus we conclude $\mu_{ia}(c)=UR_{i}(c_{a})$
for all $i\in N$.

As $a\in ED(c)$ is assumed arbitrary, the same argument holds for all objects
in $ED(c)$ and thus

for all $b\in ED(c)$, for all $i\in N$, $\mu_{ib}(c)=UR_{i}(c_{b})$.

Since $\mathbf{d}(c_{i},\mu_{i}(c))=2\times\sum_{o\in
ED(c)}(c_{io}-\mu_{io}(c))$, we have $\mu$ is welfare equivalent to URC
mechanisms, that is for every profile $c$, for every agent $i\in N$,
$\mathbf{d}(c_{i},\mu_{i}(c))=\mathbf{d}(c_{i},URC_{i}(c))$. $\Box$

###  7.5 Proofs for Section 5

Proof. Proof of Proposition 5.2.

Proof of Properties for SDC Mechanisms:

Suppose a profile $c=(c_{i})_{i\in N}$ is given. Let $\alpha$ be a sequence of
agetns and $\beta$ a sequence of objects. In phase 1 of SDC mechanisms, when
$w_{\alpha(t)a}=\min(r_{a},c_{\alpha(t)a})$, if $a\in ED(c)$, then the object
is exhausted in phase 1, and thus nothing remains for phase 2, and for every
$i\in N$, $SDC^{\alpha,\beta}_{\alpha(t)a}(c)=w_{\alpha(t)a}\leq
c_{\alpha(t)a}$. If $a\in ES(c)\cup UN(c)$, then in phase 1,
$w_{\alpha(t)a}=\min(r_{a},c_{\alpha(t)a})=c_{\alpha(t)a}$, and thus
$SDC^{\alpha,\beta}_{\alpha(t)a}(c)\geq c_{\alpha(t)a}$. This is an evident
that the outcome is same-sided and, therefore, efficient by Proposition 2.2.

The proof that SDC mechanisms are strategy-proof is straightforward. In phase
1, each agent, during their turn, tries to get as close as possible to their
peaks. Note that for all $a\in ED(c)$, $SDC^{\alpha,\beta}(c)$ is determined
in phase 1. For $a\in ED(c)$, if $c_{\alpha(t)a}\leq r_{a}$, then
$w_{\alpha(t)a}=c_{\alpha(t)a}$, and if $c_{\alpha(t)a}>r_{a}$ then
$w_{\alpha(t)a}=r_{a}$. Suppose agent $\alpha(t)$ misreport $c^{\prime}_{i}$.
Then it is easy to see that for all $a\in ED(c)$,
$(c_{\alpha(t)a}-SDC^{\alpha,\beta}_{\alpha(t)a}(c))\leq(c_{\alpha(t)a}-SDC^{\alpha,\beta}_{\alpha(t)a}((c^{\prime}_{i},c_{-i}))$.
Thus, by Lemma 2.1, Equation (1), misreporting does not result in a decrease
in distance.

The SDC mechanisms are replacement monotonic. Let $c^{\prime}_{i}$ be such
that

  * •

$ED(c)=ED((c^{\prime}_{i},c_{-i}))$, and

  * •

for all $a\in ED(c)$, $c^{\prime}_{ia}\leq c_{ia}$.

Let $s$ be the index such that $\alpha(s)=i$. For all $t<s$, for all $a\in A$,
$SDC^{\alpha,\beta}_{\alpha(t)a}(c)=SDC^{\alpha,\beta}_{\alpha(t)a}((c^{\prime}_{i},c_{-i}))$.
This is because the change made by agent $i$ from $c_{i}$ to $c^{\prime}_{i}$
does not affect the agents who precede him in the sequence. In the case where
$t>s$, consider the remainder of object $a$ at agent $\alpha(t)$’s turn in
phase 1, denoted as $r_{a}(t)$. Also let $r^{\prime}_{a}(t)$ be the remainder
of object $a$ at agent $\alpha(t)$’s turn in phase 1, when agent $\alpha(s)=i$
changed from $c_{i}$ to $c^{\prime}_{i}$. For all $a\in ED(c)$, since
$c^{\prime}_{ia}\leq c_{ia}$, we have $r_{a}(t)\leq r^{\prime}_{a}(t)$. This
enables agent $\alpha(t)$ to still have the opportunity to get as close to his
peak as he did before changing from $c_{i}$ to $c^{\prime}_{i}$. Consequently,
for all $j\in N\setminus\\{i\\}$,
$\mathbf{d}(c_{j},\mu_{j}(c))\geq\mathbf{d}(c_{j},\mu_{j}((c^{\prime}_{i},c_{-i})))$.

To prove non-bossiness, let’s consider an agent $\alpha(t)$ who intends to
behave in a bossy manner. This agent cannot affect those agents who precede
him in the sequence $\alpha$. Additionally, if agent $\alpha(t)$ does not take
a different amount of excess demand objects in his turn, then he does not
affect the remainder of excess demand objects for agents who succeed him in
the sequence $\alpha$. Consequently, all agents $\alpha(s)$, where $s>t$,
receive the same amount for excess demand objects as they would have received
without the interference of agent $\alpha(t)$.

To prove in-betweenness, suppose for an arbitrary agent $i=\alpha(t)$,
$c^{\prime}_{\alpha(t)}$ is a lottery between $c_{\alpha(t)}$ and
$SDC^{\alpha,\beta}_{\alpha(t)}(c)$. Then as SDC mechanisms are same-sided, we
have for all $a\in A$,

  * •

if $a\in UN(c)$, then
$c^{\prime}_{\alpha(t)a}=c_{\alpha(t)a}=SDC^{\alpha,\beta}_{\alpha(t)a}(c)$,

  * •

if $a\in ED(c)$, then $SDC^{\alpha,\beta}_{\alpha(t)a}(c)\leq
c^{\prime}_{\alpha(t)a}\leq c_{\alpha(t)a}$, and

  * •

if $a\in ES(c)$, then $SDC^{\alpha,\beta}_{\alpha(t)a}(c)\geq
c^{\prime}_{\alpha(t)a}\geq c_{\alpha(t)a}$.

In phase 1 of SDC mechanisms, after changing from $c_{\alpha(t)}$ to
$c^{\prime}_{\alpha(t)}$, agent $\alpha(t)$ takes

$w^{\prime}_{\alpha(t)a}=\min(r_{a},c^{\prime}_{\alpha(t)a})$.

If $a\in ED(c)\cup UN(c)$, then since
$SDC^{\alpha,\beta}_{\alpha(t)a}(c)=\min(r_{a},c_{\alpha(t)a})$, and
$SDC^{\alpha,\beta}_{\alpha(t)a}(c)\leq c^{\prime}_{\alpha(t)a}\leq
c_{\alpha(t)a}$, we have

$SDC^{\alpha,\beta}_{\alpha(t)a}((c^{\prime}_{\alpha(t)},c_{{-\alpha(t)}}))=w^{\prime}_{\alpha(t)a}=\min(r_{a},c^{\prime}_{\alpha(t)a})=\min(r_{a},c_{\alpha(t)a})=SDC^{\alpha,\beta}_{\alpha(t)a}(c).$

Thus,

$for~{}all~{}a\in ED(c)\cup
UN(c),~{}SDC^{\alpha,\beta}_{\alpha(t)a}((c^{\prime}_{\alpha(t)},c_{{-\alpha(t)}}))=SDC^{\alpha,\beta}_{\alpha(t)a}(c).$
(31)

By non-bossiness, the allocation for excess demand objects does not change for
all agents.

As the phase 2 of SDC mechanisms resembles the phase 2 of URC mechanisms, and
also similar to URC mechanisms, the outcome of SDC mechanisms remains
unchanged for excess demand and unanimous objects (see 31), therefore, the
same proof demonstrated for URC mechanisms, which establishes that for all
$a\in ES(c)$, $URC_{ia}((c^{\prime}_{i},c_{-i}))=URC_{ia}(c)$, (see 18), works
for proving “for all $a\in ES(c)$,
$SDC^{\alpha,\beta}_{\alpha(t)a}((c^{\prime}_{\alpha(t)},c_{{-\alpha(t)}}))=SDC^{\alpha,\beta}_{\alpha(t)a}(c)$”.
Hence, for all $a\in A$, $SDC_{ia}((c^{\prime}_{i},c_{-i}))=SDC_{ia}(c)$, and
we are done.

The proof that SDC mechanisms are neither anonymous nor envy free is
straightforward.

Proof of Properties for PDC Mechanisms:

It is easy to verify that the outcome of PDC mechanisms is same-sided and thus
efficient by Proposition 2.2. The proof of anonymity for PDC mechanisms is
also straightforward.

The proof of non-bossiness for PDC mechanisms is straightforward. Since excess
demand objects are allocated proportionally, if an agent wants to not change
his own allocation for excess demand objects, then he should not change his
ideals for excess demand objects, and thus the allocations of excess demand
objects for other agents remain unchanged.

The PDC mechanisms are replacement monotonic. Let $c^{\prime}_{i}$ be such
that

  * •

$ED(c)=ED((c^{\prime}_{i},c_{-i}))$, and

  * •

for all $a\in ED(c)$, $c^{\prime}_{ia}\leq c_{ia}$.

Since, for all $a\in ED(c)$, $c^{\prime}_{ia}\leq c_{ia}$, and the allocation
of excess demand objects is proportional, it follows that other agents $j\in
N\setminus\\{i\\}$, obtain an equal or larger proportion. Consequently,
applying Lemma 2.1, Equation (1), we have for all $j\in N\setminus\\{i\\}$,
$\mathbf{d}(c_{j},\mu_{j}(c))\geq\mathbf{d}(c_{j},\mu_{j}((c^{\prime}_{i},c_{-i})))$.

PDC mechanisms satisfy in betweenness. Let $\alpha$ be a sequence of agents
and $\beta$ a sequence of objects, both arbitrary. Suppose that for some agent
$i$, a lottery $c^{\prime}_{i}$ is between $c_{i}$ and
$PDC^{\alpha,\beta}_{i}(c)$. As in phase 1 of PDC mechanisms, excess demand
objects and unanimous objects are allocated proportionally, and for every
$a\in ED(c)\cup UN(c)$, $PDC^{\alpha,\beta}_{ia}(c)\leq c^{\prime}_{ia}\leq
c_{ia}$. Therefore, after accomplishing phase 1, we have

  * •

for all $a\in UN(c)$,
$PDC^{\alpha,\beta}_{ia}((c^{\prime}_{i},c_{-i}))=PDC^{\alpha,\beta}_{ia}(c)$,

  * •

for all $a\in ED(c)$, $PDC^{\alpha,\beta}_{ia}((c^{\prime}_{i},c_{-i}))\leq
PDC^{\alpha,\beta}_{ia}(c)$, and

  * •

since for all $a\in ES(c)$, $c_{ia}\leq c^{\prime}_{ia}\leq\mu_{ia}(c)$,
$w_{ia}=c^{\prime}_{ia}\leq\mu_{ia}(c)$.

Additionally, because for every $a\in ED(c)$, $c^{\prime}_{ia}\leq c_{ia}$ and
$PDC^{\alpha,\beta}_{ia}(c)\leq c^{\prime}_{ia}$, we have for all other agents
$j\in N\setminus\\{i\\}$, for every $a\in ED(c)$,
$PDC^{\alpha,\beta}_{ja}((c^{\prime}_{i},c_{-i}))\geq
PDC^{\alpha,\beta}_{ja}(c)$.

Let $v=(\sum_{a\in ED(c)}PDC_{ia}(c)-\sum_{a\in
ED(c)}PDC_{ia}((c^{\prime}_{i},c_{-i})))$ be the amount that agent $i$ takes
less from excess demand objects, when changing from $c_{i}$ to
$c^{\prime}_{i}$. Since PDC is proportional for excess demand objects and for
every $a\in ED(c)$, $c^{\prime}_{ia}\leq c_{ia}$ and
$PDC^{\alpha,\beta}_{ia}(c)\leq c^{\prime}_{ia}$, we have $v$ is also equal to
the amount that other agents takes out more from excess demand objects, when
changing from $c_{i}$ to $c^{\prime}_{i}$, that is, $v=\sum_{j\in
N\setminus\\{i\\}}(\sum_{a\in
ED(c)}PDC_{ja}((c^{\prime}_{i},c_{-i}))-\sum_{a\in ED(c)}PDC_{ja}(c))$.

We prove by contradiction that for every $a\in ES(c)$,
$PDC_{ia}((c^{\prime}_{i},c_{-i}))\geq PDC_{ia}(c)$. Suppose not and there
exists an object $b\in ES(c)$ such that
$PDC_{ib}((c^{\prime}_{i},c_{-i}))<PDC_{ib}(c)$.

Suppose that for the sequence of objects $\beta$, for some number $k$,
$\beta(k)=b$. Since $b\in ES(c)$, already in phase 1, agent $i$ has taken
$c^{\prime}_{ib}\leq PDC_{ib}(c)$ amount of object $b$. In phase 2 of running
$PDC$ for the profile $(c^{\prime}_{i},c_{-i})$, when it is the turn of agent
$i$ to take some amount of object $b$, the inequality
$PDC_{ib}((c^{\prime}_{i},c_{-i}))<PDC_{ib}(c)$ implies that agent $i$ could
not take as much of object $b$ as he would in profile $c$, so

  * case1:

We are either facing a shortage of object $b$, and the tank containing object
$b$ has less liquid compared to the time of profile $c$. This scarcity results
in agent $i$ being unable to take as much of object $b$ to reach
$PDC_{ib}(c)$.

  * case2:

or the bucket of agent $i$ has less available capacity compared to the time of
profile $c$, and it caused that agent $i$ cannot reach $PDC_{ib}(c)$.

As for the profile $(c^{\prime}_{i},c_{-i})$, all agents $j\in
N\setminus\\{i\\}$ takes more from excess demand objects compared to the time
of profile $c$, therefore, they have less free capacity for excess supply
object $b$, and they take less from object $b$ compared to the time of profile
$c$. So the case1 is impossible.

We argue that the case2 is also impossible. Suppose that the bucket of agent
$i$ has less capacity compared to the time of profile $c$. For all objects
$\beta(1),\beta(2),...\beta(k-1)$, agents in $N\setminus\\{i\\}$, can, at
most, collectively take $v$ amount less than the objects
$\beta(1),\beta(2),...\beta(k-1)$ compared to the time of profile $c$. So
agent $i$ can take at most $v$ amount more than than the objects
$\beta(1),\beta(2),...\beta(k-1)$ compared to the time of profile $c$, and
since he has already takes $v$ amount less than excess demand objects, his
bucket has enough capacity to reach $PDC_{ib}(c)$ for object $b$.

Thus both case1 and case2 are impossible, contradiction. Therefore, for every
$a\in ES(c)$, $PDC_{ia}((c^{\prime}_{i},c_{-i}))\geq PDC_{ia}(c)$.

The proof that PDC mechanisms is not strategy proof is straightforward. For
envy freeness, consider $N=\\{1,2,3,4\\}$ and $A=\\{a,b,d,e\\}$. Let $c$ be
preference profile where $ED(c)=\\{a\\}$, and $c_{1a}=c_{2a}=c_{3a}=1$, and
$c_{4a}=1/3$. In phase 1 of PDC mechanisms, object $a$ is divided
proportionally as follows: $p_{1a}=p_{2a}=p_{3a}=0.3$ and $p_{4a}=0.1$. Since
PDC mechanisms are same-sided, because of Lemma 1, we can compute the welfare
based on excess demand objects. Agent 4 envy agent 1, since
$|c_{4a}-p_{1a}|<|c_{4a}-p_{4a}|$. $\Box$