An equilibrium analysis of the probabilistic serial mechanism

Abstract

Two prominent mechanisms in the random assignment problem are the random priority (RP) and the probabilistic serial (PS). When agents are truthful, the outcomes obtained under PS have superior efficiency and fairness properties, but unlike RP, PS is vulnerable to strategizing. We study incentives of agents under PS. We find that when agents strategize, in equilibrium an outcome may be obtained under PS which is not efficient or fair and which is worse in some respects than the RP outcome. The results of our equilibrium analysis of PS call for caution when implementing it in “small” assignment problems.

1 Introduction

In a variety of contexts in everyday life, indivisible resources need to be allocated to agents without resorting to monetary payments.¹ The last decade has seen a surge of interest in such allocation problems as market designers explored important practical applications. Well-known examples are the assignment of dormitory rooms or course seats to college students, slots at public schools to pupils at various levels of pre-college education, and transplantable organs such as kidneys to patients diagnosed with serious forms of disease (Abdulkadiroğlu and Sönmez 1998, 1999, 2003; Bogomolnaia and Moulin 2001; Hylland and Zeckhauser 1979; Roth et al. 2004).

The simplest form of such indivisible resource allocation problems is the so-called random assignment problem: A set of indivisible objects are to be allocated to a set of agents in the absence of any initial claims or priorities. Each agent is entitled to receive at most one object. A mechanism is a systematic rule that prescribes how to assign objects to agents for any given preference profile that may be reported by agents. That is, given a preference profile, a mechanism induces a random assignment, which is a matrix where rows stand for agents and columns for objects, and the ${(i,j)}$th entry specifies the probability with which the ${i}$th-row agent is to receive the ${j}$th-column object. The ${i}$th-row of a random assignment, which specifies the probabilities with which the ${i}$th-row agent receives various objects, is called that agent’s random allotment.

A widely-used mechanism in real-life assignment problems is the random priority (RP),² which proceeds in the following simple manner: First, a priority order of agents is drawn uniformly at random. Then in that order the first agent receives her top-ranked object, the second agent receives her top-ranked object among remaining ones, and so on. Although RP assures ex-post efficient implementation (when executed, it always leads to a Pareto-optimal matching of agents to objects), in their influential paper Bogomolnaia and Moulin (2001) (henceforth BM) drew attention to a striking loss in efficiency under RP. They pointed out that, absent the knowledge of agents’ von-Neumann–Morgenstern (VNM) utility functions, a VNM utility comparison between two random assignments can still be made using preference information if one random assignment (first-order) stochastically dominates (is “sd-superior to”) the other. Building on this, they defined sd-efficiency:³ $^{,}$ ⁴ A random assignment is sd-efficient if it is not stochastically dominated by (is “sd-inferior to”) another random assignment. Sd-efficiency is an appealing notion; it assures a random assignment’s ex-post efficient implementation and is required for its ex-ante efficiency (Pareto-optimality according to VNM utility comparisons). Through a simple example, BM showed that, notwithstanding RP’s widespread use, the random assignment induced under RP for a given preference profile need not be sd-efficient.

Motivated by the clear efficiency loss under RP, as a viable alternative to it BM proposed the probabilistic serial mechanism (PS). For a given preference profile, the random assignment induced under PS is calculated through a “simultaneous eating algorithm” as follows: Each object is viewed as a continuum of probability shares from which 1 unit is available (except the null object, which stands for each agent’s outside option and is infinitely available). At time 0 agents start to simultaneously “eat away” from their top-ranked objects at constant unit speed. Whenever the object eaten by an agent is exhausted, she switches to eating away from her top-ranked object among those that are still available (i.e., not yet exhausted) and so on. Agents stop eating at time 1. The induced random assignment is calculated by setting its $(i,j)$th entry equal to the amount that the $i$th-row agent has consumed from the $j$th-column object throughout this process. Unlike under RP, BM showed that for a given preference profile the random assignment induced under PS is always sd-efficient. Furthermore, they showed that PS performs better than RP also in a “fairness” sense: Given a preference profile, while the random assignment induced under PS is sd-envy-free (each agent finds her random allotment to be sd-superior to that of any other agent), the random assignment induced under RP is only weakly sd-envy-free (an agent never finds her random allotment to be strictly sd-inferior to that of another agent but she may find it to be “sd-incomparable”). The compelling properties of PS over RP—sd-efficiency and sd-no-envy, stimulated a growing body of literature on PS; it has been extended to the domain of weak preferences (Katta and Sethuraman 2006), to on-campus housing problems (Yılmaz 2010), and to multiple-object assignment problems (Kojima 2009).⁵

The superior efficiency and fairness properties of PS come at the cost of an incentive shortcoming, however. Whereas RP is “sd-strategy-proof,” BM showed that PS is only “weakly sd-strategy-proof.” That is, when compared with the random allotment that she would obtain if she were truthful, an agent who lies about her preferences ends up with an sd-inferior random allotment under RP but with an sd-inferior or an sd-incomparable random allotment under PS. This means in utility terms manipulation (i.e., being non-truthful) is never profitable under RP but may sometimes be profitable under PS. Recent studies indicate that the vulnerability of PS to manipulation should not be a major concern for “large” assignment problems: Che and Kojima (2010) showed that PS asymptotically converges to RP, and hence becomes sd-strategy-proof, as the supply of each object type goes to infinity; Kojima and Manea (2010) showed that PS cannot be manipulated even if the supply of each object type is finite but sufficiently large. While these results support the case for PS in large assignment problems, little is known about the implications of incentives that agents face under PS in environments to which the large market assumptions do not apply. In fact, even though RP has been known to induce very high rates of truth-telling in the lab (Chen and Sönmez 2002), it has recently been found that PS may induce behavior in sharp contrast (Hugh-Jones et al. 2014).

It is worth emphasizing that when agents are not truthful, the outcome of PS is no longer guaranteed to be sd-efficient or sd-envy-free with respect to agents’ true preferences. Therefore, in this paper, we investigate whether or not the desirable properties of PS continue to hold in equilibrium.⁶ Given the fact that an assignment problem induces a preference-revelation game, we consider three equilibrium notions: A preference profile is a weak sd Nash equilibrium (a weak sd-NE) if by unilateral deviation from this profile (i.e., one agent changes her preference report while other agents do not) an agent can never attain a strictly sd-superior random allotment.⁷ A preference profile is a Nash equilibrium if by unilateral deviation from this profile an agent can never attain a higher VNM utility. A preference profile is an sd Nash equilibrium (an sd-NE) if by unilateral deviation from this profile an agent always obtains an sd-inferior random allotment. Clearly, an sd-NE is a Nash equilibrium and a Nash equilibrium is a weak sd-NE. As a notion of equilibrium, Nash equilibrium is indeed suitably appealing for our purposes. Nonetheless, the fact that agents reveal only their preference information and not their VNM utility functions motivates us to study also the more stringent sd-NE and the less stringent weak sd-NE.⁸

Since RP is sd-strategy-proof, truth-telling is always an sd-NE under RP. We show some cases when an sd-NE exists under PS (Proposition 1 and Example 1) but in general under PS the existence of an sd-NE is not guaranteed (Example 2). Nevertheless, if an sd-NE exists under PS, it turns out to lead to a desirable outcome—a random assignment which is both sd-efficient and sd-envy-free. This result is due to our Theorem 1, which shows that indeed the random assignment induced in an sd-NE under PS is precisely the random assignment that would be induced if agents were truthful. We prove Theorem 1 by building on a lemma which also helps us show that PS is robust to a sort of manipulation scheme by agents via bribes in the form of “side payments,” a property known in the literature as “non-bossiness”: Under PS, no agent can alter the random allotment of another agent by changing her preference report without also changing her own random allotment (Proposition 2).⁹

Unlike an sd-NE, a weak sd-NE always exists under PS; indeed, since PS is weakly sd-strategy-proof, truth-telling is always a weak sd-NE. There may be multiple weak sd-NEs, however. In Example 2, we show a non-truthful preference profile—where one agent lies about her preferences, which is a weak sd-NE. In the same example, given agents’ VNM utility functions, we show that under PS truth-telling may not be a Nash equilibrium and every Nash equilibrium outcome might lead to the same random assignment, say $R$, which is neither sd-efficient nor sd-envy-free. What is more, on two accounts $R$ fares worse even compared to the outcome that would be obtained if RP were executed. Eliciting honest preferences from agents, RP induces a weakly sd-envy-free random assignment and assures its ex-post efficient implementation; $R$, however, is not even weakly sd-envy-free, and its ex-post efficient implementation cannot be guaranteed given that preferences reported by agents cannot be trusted (we show the existence of an ex-post inefficient decomposition of $R$, which in implementation cannot be discarded when agents’ true preferences are unknown).

The results of our equilibrium analysis of PS call for caution when implementing this mechanism in “small” assignment problems. In particular, the desirability of the equilibrium outcomes under PS may be sensitive to the specifics of the considered random assignment problem. The rest of the paper is organized as follows. Section 2 introduces the model; Sect. 3 introduces the equilibrium notions; Sect. 4 presents our results.

2 The model

2.1 Basic setup

Let $I\equiv \{1,2,\ldots ,n\}$ be a finite set of agents. Let $O\equiv \{o_{1},o_{2},\ldots ,o_{k}\}$ be a finite set of indivisible objects where $o_{k}$ is the null object (which stands for each agent’s outside option). Also, for expositional convenience, let $J\equiv \{1,2,\ldots ,k\}$ be the set of indices of objects. We will use $i$ and $j$ to denote an arbitrary agent and the index of an arbitrary object, respectively.

Agents are equipped with strict preferences over the set of objects. Let $\mathcal {O}$ be the domain of admissible preference relations over $O$. We reserve $\succ _{_{i}}^{T}$ to represent agent $i$’s true preference relation (i.e., $o\succ _{_{i}}^{T}\overline{o}$ means $o,\overline{o}\in O, o\ne \overline{o}$ and $i$ prefers $o$ to $\overline{o}$). We use $\succ _{i}$ to represent an arbitrary preference relation intended for agent $i$. Here, “arbitrary” means “not necessarily truthful.” Likewise, $\mathcal {O}^{n}$ is the domain of preference (relation) profiles, $\succ ^{T}\equiv (\succ _{i}^{T})_{i\in I}\in \mathcal {O}^{n}$ represents the truthful preference profile, and $\succ \equiv (\succ _{i})_{i\in I}\in \mathcal {O}^{n}$ represents an arbitrary preference profile. The profile $(\succ _{i}^{T},\succ _{-i})$ means $i$ is truthful and remaining agents report their preferences as in profile $\succ \in \mathcal {O}^{n}$. We use $\succsim _{i}^{T}$ and $\succsim _{_{i}}$to represent the weak preference relations associated with $\succ _{_{i}}^{T}$ and $\succ _{_{i}}$, respectively (e.g., for $o,\overline{o}\in O, o\succsim _{i}^{T}\overline{o}$ means $o\succ _{_{i}}^{T}\overline{o}$ or $o=\overline{o}$). Note that our use of different notations for truthful and arbitrary preference profiles is for expositional convenience and does not mean that the truthful preference profile is fixed. Therefore, in what follows, for instance, “for any $\succ ^{T}\in \mathcal {O}^{n}$” is understood as “for any truthful preference profile.”

Agents are equipped with von-Neumann–Morgenstern (VNM) utility functions consistent with their preferences. A utility function $u_{i}:O\rightarrow \mathbb {R}_{+}$ is consistent with a preference relation $\succ _{i}$ if for every $o,\overline{o}\in O$ such that $o\succ _{i}\overline{o}, u_{i}(o)>u_{i}(\overline{o})$. Let $U^{\succ _{i}}$ be the domain of utility functions consistent with $\succ _{i}$. A utility profile $u\equiv (u_{i})_{i\in I}$ is consistent with a preference profile $\succ$ if for each agent $i, u_{i}$ is consistent with $\succ _{i}$. Let $U^{\succ }\equiv (U^{\succ _{i}})_{i\in I}$ be the domain of utility profiles consistent with $\succ$. In our setting agents do not announce their utility functions and hence in what follows we use statements such as “ for any $u_{i}\in U^{\succ _{i}^{T}}$,” which means “for any utility function of agent $i$.” When we want to work with a specific utility profile for agents, however, we represent it with $u^{T}\equiv (u_{i}^{T})_{i\in I}$.

A deterministic assignment is an $(n\times k)$ matrix $D=[d_{ij}]$ such that:

$$\begin{aligned} \forall (i,j)\in (I,J),\text { }d_{ij}\in \{0,1\};\text { }\forall i\in I,\text { }\sum \limits _{j\in J}d_{ij}=1;\text { }\forall j\in J\setminus \{k\},\text { }\sum \limits _{i\in I}d_{ij}\le 1. \end{aligned}$$

Above, $d_{ij}=1$ ($d_{ij} =0$) is understood as agent $i$ is (is not) assigned $o_{j}$ at $D$. As specified, only the null object can be assigned to multiple agents. Abusing the notation, $D(i)$ denotes the object that agent $i$ receives at $D$ (i.e., if $d_{ij} =1$ then $D(i)=o_{j}$). Let $\mathcal {D}$ be the domain of admissible deterministic assignments.

A random allotment is a $(1\times k)$ row vector $r=[r_{1},r_{2},\ldots ,r_{k}]$ such that:

$$\begin{aligned} \forall j\in J,\text { }0\le r_{j}\le 1;\text { }\sum \limits _{j\in J}r_{j}=1. \end{aligned}$$

A random allotment $r$ specifies for an agent the probabilities of receiving various objects: $o_{j}$ is received with probability $r_{j}$. Abusing the notation, $r(s,\succ _{i})$ denotes the cumulative probability at $r$ of receiving one of highest-ranked $s$ objects w.r.t. $\succ _{i}\in \mathcal {O}$. For instance, $r(2,\succ _{_{i}}^{T})$ is the probability that agent $i$ receives at $r$ one of highest-ranked two objects with respect to her true preferences. Also, with respect to a utility function $u_{i}$, the VNM utility at $r$ of agent $i$ is denoted by $u_{i}(r)$, i.e.,

$$\begin{aligned} u_{i}(r)=\sum \limits _{j\in J}r_{j}u_{i}(o_{j}). \end{aligned}$$

A random assignment is an $(n\times k)$ matrix $R\equiv [r_{ij}]$ such that:

$$\begin{aligned} \forall (i,j)\in (I,J),\text { }0\le r_{ij}\le 1;\text { }\forall i\in I,\text { }\sum \limits _{j\in J}r_{ij}=1;\text { }\forall j\in J\setminus \{k\}, \text { }\sum \limits _{i\in I}r_{ij}\le 1. \end{aligned}$$

Above, the $i$th row of $R$, which we will denote by $R_{i}$, is the random allotment at $R$ of agent $i$. Thus, $r_{ij}$ is the probability that $i$ receives $o_{j}$ at $R$; $R_{i}(s,\succ _{i})$ is the cumulative probability that $i$ receives at $R$ one of highest-ranked $s$ objects w.r.t. $\succ _{i}\in \mathcal {O}$; and $u_{i}(R_{i})$ is the VNM utility at $R$ of $i$ with respect to the utility function $u_{i}$. Let $\mathcal {R}$ be the domain of admissible random assignments.

A lottery decomposition of a random assignment $R\in \mathcal {R}$ is a list $(D^{1},D^{2},\ldots ,D^{s})$ of deterministic assignments and a list $(w^{1},w^{2},\ldots ,w^{s})$ of weighting factors such that:

$$\begin{aligned} 0<w^{1},w^{2},\ldots ,w^{s}\le 1\text {; }w^{1}+w^{2}+\cdots +w^{s}=1;\text { }w^{1}D^{1}+w^{2}D^{2}+\cdots +w^{s}D^{s}=R. \end{aligned}$$

The list $(D^{1},D^{2},\ldots ,D^{s})$ is called the basis of the lottery decomposition. By the well-known Birkhoff–von-Neumann theorem and its extension by Budish et al. (2013), every random assignment has at least one lottery decomposition.

2.2 Efficiency and fairness notions

The following definition defines the (first-order) stochastic dominance relation for random allotments and random assignments.

Definition 1

(stochastic dominance)

For two random allotments $r$ and $\overline{r}$, for agent $i$:

• $r$ stochastically dominates $\overline{r}$ , written as $r\,sd(\succ _{i}^{T})\, \overline{r}$, if for $s=1,2,\ldots ,k, r(s,\succ _{i}^{T})\ge \overline{r}(s,\succ _{i}^{T})$;

• $r$ strictly stochastically dominates $\overline{r}$, written as $r$ $S\!D(\succ _{i}^{T})\, \overline{r}$, if $r\,sd(\succ _{i}^{T})\,\overline{r}$ and $r\ne \overline{r}$.¹⁰

For two random assignments $R$ and $\overline{R}$:

• $R$ stochastically dominates $\overline{R}$, written as $R\,sd(\succ ^{T})\, \overline{R}$, if for each $i\in I, R_{i}\,sd(\succ _{i}^{T})\, \overline{R}_{i}$;

• $R$ strictly stochastically dominates $\overline{R}$, written as $R\,S\!D(\succ ^{T})\, \overline{R}$, if $R\,sd(\succ ^{T})\, \overline{R}$ and $R\ne \overline{R}$.¹¹

If $R$ (strictly) stochastically dominates $\overline{R}$, we also say that $R$ is (strictly) sd-superior to $\overline{R}$ or $\overline{R}$ is (strictly) sd-inferior to $R$; if these two random assignments do not stochastically dominate one another, we say that they are sd-incomparable. We use the same language also when comparing random allotments according to the stochastic dominance relation. The following lemma follows from the properties of the stochastic dominance relation.

Lemma 1

For two random allotments $r$ and $\overline{r}$ and an agent $i$:

• (i) $r\,sd(\succ _{i}^{T})\, \overline{r}\Rightarrow \forall u_{i}\in U^{\succ _{i}^{T}}, u_{i}(r)\ge u_{i}(\overline{r})$;

• (ii) $r\,S\!D(\succ _{i}^{T})\, \overline{r}\Rightarrow \forall u_{i}\in U^{\succ _{i}^{T}}, u_{i}(r)>u_{i}(\overline{r})$;

• (iii) $r\,sd(\succ _{i}^{T})\, \overline{r}$ does not hold $\Rightarrow \,\exists u_{i}\in U^{\succ _{i}^{T}}$ such that $u_{i}(\overline{r})>u_{i}(r)$.

In Lemma 1, (i) and (ii) evidently hold. To see why (iii) holds, pick some number $\overline{s}$ such that $\overline{r}(\overline{s},\succ _{i}^{T})>r(\overline{s},\succ _{i}^{T})$. Then, at $u_{i}$ let $i$’s utility from her $s$th-ranked object be $M+\epsilon (k-s)$ for $s\le \overline{s}$ and $\epsilon (k-s)$ for $s>\overline{s}$ where $M>0$ and $\epsilon >0$ are set sufficiently large and small, respectively.

In what follows, we define various notions using comparisons according to the stochastic dominance relation. In some of these definitions, the basis of comparison is “stochastic dominance,” which is signified in the defined notion’s name by using the prefix sd-. In others, the basis of comparison is “not being stochastically dominated,” which is signified in the defined notion’s name by using the prefix weak sd-. The following definition defines the efficiency notions for deterministic and random assignments in the literature.

Definition 2

(efficiency notions)

A deterministic assignment $D$ is Pareto-optimal if there does not exist $\overline{D}\in \mathcal {D}$ such that for each $i\in I, \overline{D}(i)\succsim _{i}^{T}D(i)$, and for some $i\in I, \overline{D}(i)\succ _{i}^{T}D(i)$.

A random assignment $R$:

• is ex-post efficiently implementable, if it has a lottery decomposition such that every deterministic assignment in the basis is Pareto-optimal;

• is sd-efficient, if there does not exist $\overline{R}\in \mathcal {R}$ such that $\overline{R}$ $S\!D(\succ ^{T})\,R$;

• is ex-ante efficient given $u^{T}$, if there does not exist $\overline{R}\in \mathcal {R}$ such that for each $i\in I, u_{i}^{T}(\overline{R}_{i})\ge u_{i}^{T}(R_{i})$, and for some $i\in I, u_{i}^{T}(\overline{R}_{i})>u_{i}^{T}(R_{i})$.

As BM showed, for random assignments, ex-ante efficiency implies sd-efficiency and sd-efficiency guarantees ex-post efficient implementability; the converse statements are not necessarily true. The following definition defines the fairness notions for random assignments in the literature.

Definition 3

(fairness notions)

For an agent-pair $(i,\overline{i})$, at a random assignment $R$:

• $i$ sd-envies $\overline{i}$, if $R_{\overline{i}}\,S\!D(\succ _{i}^{T})\,R_{i}$;

• $i$ weakly sd-envies $\overline{i}$, if $R_{i}\,sd(\succ _{i}^{T})\,R_{\overline{i}}$ does not hold.

A random assignment $R$:

• is sd-envy-free (satisfies sd-no-envy), if for every agent-pair $(i,\overline{i}), R_{i}\,sd(\succ _{i}^{T})\,R_{\overline{i}}$;

• is weakly sd-envy-free (satisfies weak sd-no-envy), if no agent-pair $(i,\overline{i})$ exists such that $R_{\overline{i}}\,S\!D(\succ _{i}^{T})\,R_{i}$.¹²

Due to Lemma 1, for agents sd-envy implies weak sd-envy, and for random assignments, sd-no-envy implies weak sd-no-envy; the converse statements are not necessarily true.

2.3 Random priority and probabilistic serial

A mechanism $\varphi :\mathcal {O}^{n}\rightarrow \mathcal {R}$ is a function that maps the domain of preference profiles to the codomain of random assignments: $\varphi (\succ )$ is the random assignment induced when agents report a profile $\succ \in \mathcal {O}^{n}$; we use $\varphi _{i}(\succ )$ to denote the random allotment at $\varphi (\succ )$ of agent $i$. This paper considers two random mechanisms. The first one is the “random priority,” which is widely used in real-life assignment problems. To introduce it, we should first describe “priority rules.”

A priority order $\pi :I\rightarrow I$ is a bijection that orders agents: $\pi (s)=i$ means agent $i$ is ordered $s$th. Let $\Pi$ be the domain of priority orders; note that $\left| \Pi \right| =n!$. A priority rule is a deterministic mechanism that is associated with a priority order and which in that order subsequently assigns agents their top-ranked objects among remaining ones. More formally: A priority rule $Prio^{\pi }:\mathcal {O}^{n}\rightarrow \mathcal {D}$ is a deterministic mechanism such that $\pi \in \Pi$, and at $Prio^{\pi }(\succ )$, with respect to the reported profile $\succ$, agent $\pi (1)$ is assigned her top-ranked object, agent $\pi (2)$ is assigned her top-ranked object among remaining ones, and so on.

Random priority works as follows: First, a priority order is chosen uniformly at random. Then objects are assigned to agents by executing the priority rule associated with the chosen priority order. This is the procedural definition of random priority; below is given its definition as a mapping from preference profiles to random assignments.

2.3.1 Random priority (RP)

Random priority $RP:\mathcal {O}^{n}\rightarrow \mathcal {R}$ is a random mechanism such that for $\succ \in \mathcal {O}^{n}$,

$$\begin{aligned} RP(\succ )=\frac{1}{n!}\sum \limits _{\pi \in \Pi }Prio^{\pi }(\succ ). \end{aligned}$$

It is worth emphasizing that the procedural definition of RP is “more precise” than its definition as a mapping; for a given preference profile, the procedural definition not only induces a random assignment but also formulates how to implement that random assignment, by decomposing it into deterministic assignments in a specific manner. This additional precision under the procedural definition turns out to bear significance; as we will argue later, RP induces agents to be truthful and hence implements $RP(\succ ^{T})$ in an ex-post efficient manner even when $RP(\succ ^{T})$ is not sd-efficient and thus has ex-post inefficient decompositions.

The second random mechanism that we consider is the “probabilistic serial,” which obtains from the “simultaneous eating algorithm.” This algorithm takes as input a profile $f=(f_{i})_{i\in I}$ of eating-speed functions, where any agent $i$’s eating-speed function $f_{i}:[0,1]\rightarrow \mathbb {R}_{+}$ is measurable and satisfies,

$$\begin{aligned} \int \limits _{t\in [0,1]}f_{i}(t)dt=1. \end{aligned}$$

Given the profile $f$, for a given preference profile reported by agents, the simultaneous eating algorithm induces a random assignment in the following manner: Think of each object as an infinitely divisible good from which one unit is available, except the null object, which is infinitely available. At time $t=0$ each agent starts to simultaneously “eat away” from her top-ranked object (top-ranked with respect to reported preferences); agent $i$’s eating speed at time $t\in [0,1]$ is $f_{i}(t)$. Whenever the object eaten by an agent is exhausted, she switches to eating away from her top-ranked object among those that are still available (i.e., not yet exhausted) and so on. (An object is exhausted at time $t$ if the cumulative amount eaten from it by all agents until time $t$ is less than $1$; the null object is an exception, which is never exhausted). The algorithm stops at time $t=1$. At the random assignment induced, say $R$, the entry $r_{ij}$ equals the total amount that agent $i$ has consumed from $o_{j}$ throughout this process.

2.3.2 Probabilistic Serial (PS)

Probabilistic serial PS $:\mathcal {O}^{n}\rightarrow \mathcal {R}$ is the random mechanism that obtains in the simultaneous eating algorithm when each agent has the unit eating-speed function, i.e., $f_{i}(t)=1$ for every $i\in I$ and every $t\in [0,1]$.

BM showed that when agents are truthful and report $\succ ^{T}$, under PS the resulting random assignment $PS(\succ ^{T})$ is sd-efficient and sd-envy-free, but under RP the resulting random assignment $RP(\succ ^{T})$ may not be sd-efficient and is only weakly sd-envy-free.

3 Equilibrium notions

The following definition defines the non-manipulability notions for mechanisms.

Definition 4

(non-manipulability notions)

A mechanism $\varphi$:

• is sd-strategy-proof if for any $(i,\succ _{i}^{T},\succ _{-i})\in (I,\mathcal {O},\mathcal {O}^{n-1})$,

  $$\begin{aligned} \forall \overline{\succ }_{i}\in \mathcal {O},\text { }\varphi _{i}\left( \succ _{i}^{T},\succ _{-i}\right) \,sd\left( \succ _{i}^{T}\right) \, \varphi _{i}\left( \overline{\succ } _{i},\succ _{-i}\right) \text {;} \end{aligned}$$

• is weakly sd-strategy-proof if for any $(i,\succ _{i}^{T},\succ _{-i})\in (I,\mathcal {O},\mathcal {O}^{n-1})$,

  $$\begin{aligned} \not \exists \overline{\succ }_{i}\in \mathcal {O}\text {, }\varphi _{i}(\overline{ \succ }_{i},\succ _{-i})\,S\!D\left( \succ _{i}^{T}\right) \, \varphi _{i}\left( \succ _{i}^{T},\succ _{-i}\right) . \end{aligned}$$

RP is sd-strategy-proof. Incentives for being truthful are sharp under an sd-strategy-proof mechanism: An agent “always” attains the “best” random allotment that she possibly can by being truthful. Here, “best” means, according to the stochastic dominance relation and hence also in terms of VNM utilities (due to Lemma 1 (i)), and “always” means for any true preference relation of the agent and irrespective of the preference reports of other agents.

BM showed that PS is weakly sd-strategy-proof but not sd-strategy-proof. Incentives for being truthful are not as sharp under a weakly sd-strategy-proof mechanism: The random allotment that an agent obtains by being truthful is never strictly stochastically dominated by a random allotment that she obtains by manipulation. The two random allotments may be sd-incomparable, however, in which case, as shown in Lemma 1 (iii), manipulation may result in a higher VNM utility and hence be profitable.

To study potential implications of manipulation under PS, we pursue an equilibrium analysis in this paper. We define first the best-response strategy notions and then introduce our equilibrium notions. Note that in this paper we confine our attention to pure strategies and hence, the introduced best-response and equilibrium notions are only for pure strategies (i.e., agents do not randomize when submitting their preferences).

Definition 5

(best-response strategy notions)

Under a mechanism $\varphi$, for an agent $i$, reporting $\succ _{i}\in \mathcal {O}$:

• is a weak sd-best-response to $\succ _{-i}\in \mathcal {O}^{n-1}$, if there does not exist $\overline{\succ }_{i}\in \mathcal {O}$ such that $\varphi _{i}(\overline{\succ }_{i},\succ _{-i})\,S\!D(\succ _{i}^{T})\, \varphi _{i}(\succ _{i},\succ _{-i})$;

• is a best-response to $\succ _{-i}\in \mathcal {O}^{n-1}$ given $u^{T}$, if for each $\overline{\succ }_{i}\in \mathcal {O}, u_{i}^{T}(\varphi _{i}(\succ _{i},\succ _{-i}))\ge u_{i}^{T}(\varphi _{i}(\overline{\succ }_{i},\succ _{-i}))$;

• is an sd-best-response to $\succ _{-i}\in \mathcal {O}^{n-1}$, if for each $\overline{\succ }_{i}\in \mathcal {O}, \varphi _{i}(\succ _{i},\succ _{-i})\,sd(\succ _{i}^{T})\, \varphi _{i}(\overline{\succ } _{i},\succ _{-i})$.

Definition 6

(equilibrium notions)

Under a mechanism $\varphi$, a preference profile $\succ \in \mathcal {O}^{n}$:

• is a weak sd Nash equilibrium (a weak sd-NE), if for each agent $i$ reporting $\succ _{i}$ is a weak sd-best-response to $\succ _{-i}$.

• is a Nash equilibrium given $u^{T}$, if for each agent $i$ reporting $\succ _{i}$ is a best-response to $\succ _{-i}$.

• is an sd Nash equilibrium (an sd-NE), if for each agent $i$ reporting $\succ _{i}$ is an sd-best-response to $\succ _{-i}$.

Due to Lemma 1, it is clear that an sd-NE is a Nash equilibrium and a Nash equilibrium is a weak sd-NE. If a preference profile is a Nash equilibrium, at this profile no agent benefits from unilaterally changing her preference report. This is indeed a suitably appealing equilibrium notion. Nevertheless, our interest of study is mechanisms under which VNM utility functions remain unannounced. In the absence of agents’ VNM utility functions, due to Lemma 1, we can conclude that a preference profile is guaranteed to be a Nash equilibrium only if it is an sd-NE, and may be a Nash equilibrium only if it is a weak sd-NE. That is why in our equilibrium analysis we also pursue weak sd-NE and sd-NE, equilibrium notions that are defined using only preference information.

4 Results

We introduce some new tools in order to ease exposition and shorten our arguments in our equilibrium analysis of PS:

• We use $t^{\succ }(o)$ to denote the time when an object $o$ is exhausted under PS when agents report $\succ \in \mathcal {O}^{n}$. If an object $o$ is not exhausted until time 1, we set $t^{\succ }(o)=1$. Note that, irrespective of $\succ , t^{\succ }(o_{k})=1$. Also, in order to shorten our arguments in our proofs, we augment our model with a “non-existent object,” denoted by $o_{0}$, and for any $\succ \in \mathcal {O}^{n}$, we set $t^{\succ }(o_{0})=0$. The non-existent object $o_{0}$ should not be confused with the null object $o_{k}$; in probability terms, the amounts available for assignment from $o_{0}$ and $o_{k}$ are zero and infinite, respectively.

• We use $O^{\succ }(t)$ to denote the set of available objects at time $t\in [0,1]$ under PS when agents report $\succ \in \mathcal {O}^{n}$. We adopt the convention that, for an object $o, o\notin O^{\succ }(t^{\succ }(o))$. This is simply to say that an agent who begins to eat away from object $o$ at time $t$ eats it in the time interval $[t,t^{\succ }(o))$ but not at the precise moment $t^{\succ }(o)$, at which time she starts eating away from another object. Note that, irrespective of $\succ , O^{\succ }(0)=O$.

We also introduce a new notion that becomes useful later in showing our results: We say that for an agent $i, \overline{\succ }_{i}\in \mathcal {O}$ is outcome-preserving at $\succ \in \mathcal {O}^{n}$ under PS if $PS(\overline{\succ }_{i},\succ _{-i})=PS(\succ ).$ In words, this means that when agent $i$ changes her preference report from $\succ _{i}$ to $\overline{\succ }_{i}$ while other agents’ preference reports remain the same, the random assignment induced does not change.

Lemma 2

Without loss of generality, let the objects $o_{0},o_{1},\ldots ,o_{k}$ be such that $0=t^{\succ }(o_{0})\le t^{\succ }(o_{1})\le \cdots \le t^{\succ }(o_{k})=1$.

• (i) Suppose agent $i$’s top-ranked object in $O^{\succ }(t^{\succ }(o_{s}))$ is the same w.r.t. $\overline{\succ }_{i}$ and $\succ _{i}$ for $s=0,1,\ldots ,k-2$. Then $\overline{\succ }_{i}$ is outcome-preserving at $\succ$ under PS.

• (ii) Suppose agent $i$’s top-ranked object in $O^{\succ }(t^{\succ }(o_{s}))$ is the same w.r.t. $\overline{\succ }_{i}$ and $\succ _{i}$ for $s=0,1,\ldots ,m,$ where $m\le k-3,$ but not the same for $s=m+1$. Then $i$ receives $o_{s}$ with the same probability at $PS(\overline{\succ }_{i},\succ _{-i})$ and $PS(\succ )$ for $s=0,1,\ldots ,m+1$, but she receives the object top-ranked in $O^{\succ }(t^{\succ }(o_{m+1}))$ w.r.t. $\overline{\succ }_{i}$ with a greater probability at $PS(\overline{\succ }_{i},\succ _{-i})$ than at $PS(\succ )$.

Proof

(i) Consider the eating patterns of agents under PS for preference profiles $(\overline{\succ }_{i},\succ _{-i})$ and $\succ$: Since agents’ top-ranked objects in $O^{\succ }(0)$ are the same for both profiles, their eating patterns are the same until an object in $O^{\succ }(0)$ is exhausted. With same eating patterns, no object in $O^{\succ }(0)$ is exhausted until time $t^{\succ }(o_{1})$. At time $t^{\succ }(o_{1}), o_{1}$ is exhausted (along with possibly some other objects). With same eating patterns in the time interval $[0,t^{\succ }(o_{1}))$, the set of available objects and the quantities that remain from them are clearly the same at time $t^{\succ }(o_{1})$.

We can iteratively apply similar arguments as above for the time intervals $[t^{\succ }(o_{1}),t^{\succ }(o_{2})), [t^{\succ }(o_{2}),t^{\succ }(o_{3})), \cdots , [t^{\succ }(o_{k-2}),t^{\succ }(o_{k-1}))$, and thereby conclude that, for profiles $(\overline{\succ }_{i},\succ _{-i})$ and $\succ$, agents’ eating patterns are exactly the same in the time interval $[0,t^{\succ }(o_{k-1}))$. If $t^{\succ }(o_{k-1})=1$, this means agents’ eating patterns are the same in the entire time interval $[0,1)$, and hence $PS(\overline{\succ }_{i},\succ _{-i})=PS(\succ )$. If $t^{\succ }(o_{k-1})<1$, after time $t^{\succ }(o_{k-1})$ every agent eats the null object since it is the only object still available. Therefore, agents’ eating patterns are again the same in the entire time interval $[0,1)$, and hence $PS(\overline{\succ }_{i},\succ _{-i})=PS(\succ )$. Thus, $\overline{\succ }_{i}$ is outcome-preserving at $\succ$.

(ii) Due to arguments similar as above in (i), we conclude that under PS, for preference profiles $(\overline{\succ }_{i},\succ _{-i})$ and $\succ$, agents’ eating patterns are exactly the same in the time interval $[0,t^{\succ }(o_{m+1}))$. Thus, for each $s\in \{1,2,\ldots ,m+1\}$, agent $i$ eats from $o_{s}$ the same amount for profiles $(\overline{\succ }_{i},\succ _{-i})$ and $\succ$. Also, the set of available objects and the quantities that remain from them are the same at time $t^{\succ }(o_{m+1})$ (note that $t^{\succ }(o_{m+1})=t^{(\overline{\succ }_{i},\succ _{-i})}(o_{m+1})$).

Let $x$ be $i$’s top-ranked object in $O^{\succ }(t^{\succ }(o_{m+1}))$ w.r.t. $\overline{\succ }_{i}$. To complete the proof, we need to show that the amount that $i$ eats from $x$ is greater for profile $(\overline{\succ }_{i},\succ _{-i})$ than for $\succ$.

For profile $(\overline{\succ }_{i},\succ _{-i}), i$ eats away from $x$ in the time interval $[t^{\succ }(o_{m+1}),t^{(\overline{\succ }_{i},\succ _{-i})}(x))$. For profile $\succ , i$ does not begin to eat $x$ right away at time $t^{\succ }(o_{m+1})$ because $x$ is not the top-ranked object in $O^{\succ }(t^{\succ }(o_{m+1}))$ w.r.t. $\succ _{i}$ (note that $\left| O^{\succ }(t^{\succ }(o_{m+1}))\right| \ge 2$). For profile $\succ$, let $o\in O^{\succ }(t^{\succ }(o_{m+1}))$ be the object that $i$ eats right before she begins to eat $x$. (Note that the proof becomes trivial if for profile $\succ$ agent $i$ never eats from $x$). Thus, for profile $\succ , i$ eats away from $x$ in the time interval $[t^{\succ }(o),t^{\succ }(x))$. Note that $t^{\succ }(o)>t^{\succ }(o_{m+1})$ because $o\in O^{\succ }(t^{\succ }(o_{m+1}))$.

To complete our proof, we need to show that $t^{(\overline{\succ }_{i},\succ _{-i})}(x)-t^{\succ }(o_{m+1})>t^{\succ }(x)-t^{\succ }(o)$. This follows immediately if $t^{(\overline{\succ }_{i},\succ _{-i})}(x)\ge t^{\succ }(x)$, since $t^{\succ }(o)>t^{\succ }(o_{m+1})$. Suppose $t^{(\overline{\succ }_{i},\succ _{-i})}(x)<t^{\succ }(x)$. The following diagram illustrates the relative positions of the points in time when $o_{m+1}$ and $x$ are exhausted for profiles $(\overline{\succ }_{i},\succ _{-i})$ and $\succ$.

We separate the rest of the proof into four steps.

Step 1: $x$ is not the null object.

The null object always lasts until time 1. Since $t^{(\overline{\succ }_{i},\succ _{-i})}(x)<t^{\succ }(x)\le 1, x$ cannot be the null object.

Step 2: For profile $(\overline{\succ }_{i},\succ _{-i})$ if an agent $i^{\prime }\ne i$ eats $x$ at some time $t\in [t^{\succ }(o_{m+1}),t^{(\overline{\succ }_{i},\succ _{-i})}(x))$ , then also for profile $\succ$ she eats $x$ at time $t$ .

By way of contradiction, suppose that at time $t\in [t^{\succ }(o_{m+1}),t^{(\overline{\succ }_{i},\succ _{-i})}(x))$, agent $i^{\prime }\ne i$ eats object $x$ for profile $(\overline{\succ }_{i},\succ _{-i})$ but object $y\ne x$ for $\succ$. Then $y\in O^{\succ }(t^{\succ }(o_{m+1}))$, and hence $t^{(\overline{\succ }_{i},\succ _{-i})}(y)>t^{\succ }(o_{m+1})$. The following diagram augments the preceding one by showing the objects that $i^{\prime }$ eats at time $t$ for profiles $(\overline{\succ }_{i},\succ _{-i})$ and $\succ$.

Since $t\le t^{(\overline{\succ }_{i},\succ _{-i})}(x)<t^{\succ }(x)$, for $\succ$ at time $t$ agent $i^{\prime }$ eats from $y$ when $x$ is also available. Then $y$ is preferred to $x$ w.r.t. $\succ _{i^{\prime }}$. Then, for profile $(\overline{\succ }_{i},\succ _{-i})$ the fact that $i^{\prime }$ eats $x$ and not $y$ at time $t$ implies that $y$ is not available at time $t$, and hence $t^{(\overline{\succ }_{i},\succ _{-i})}(y)<t$. Thus, $t^{(\overline{\succ }_{i},\succ _{-i})}(y)<t^{\succ }(y)$. Therefore, we found an object, $y$, such that: (1) $y\ne x$ and $y\in O^{\succ }(t^{\succ }(o_{m+1}))$; (2) for profile $(\overline{\succ }_{i},\succ _{-i}), y$ is exhausted earlier than $x$ does (i.e., $t^{(\overline{\succ }_{i},\succ _{-i})}(y)<t^{(\overline{\succ }_{i},\succ _{-i})}(x)$); (3) and $y$ is exhausted earlier for profile $(\overline{\succ }_{i},\succ _{-i})$ than for $\succ$ (i.e., $t^{(\overline{\succ }_{i},\succ _{-i})}(y)<t^{\succ }(y)$). The following diagram augments the preceding one by illustrating these points.

Since $x\overline{\succ }_{i}y$ and $t^{(\overline{\succ }_{i},\succ _{-i})}(y)<t^{(\overline{\succ }_{i},\succ _{-i})}(x), i$ never eats from $y$ for profile $(\overline{\succ }_{i},\succ _{-i})$. But then, the fact that $t^{(\overline{\succ }_{i},\succ _{-i})}(y)<t^{\succ }(y)$ necessitates the existence of an agent $i^{\prime \prime }\ne i$ and a time $t^{\prime }\in [t^{\succ }(o_{m+1}),t^{(\overline{\succ }_{i},\succ _{-i})}(y))$ such that at time $t^{\prime }, i^{\prime \prime }$ eats $y$ for profile $(\overline{\succ }_{i},\succ _{-i})$ but an object $z\ne y$ for profile $\succ$. But then, we can repeatedly apply similar arguments as above and find an infinite-length sequence of distinct objects $x,y,z,\ldots \in O^{\succ }(t^{\succ }(o_{m+1}))$ such that $\cdots <t^{(\overline{\succ }_{i},\succ _{-i})}(z)<t^{(\overline{\succ }_{i},\succ _{-i})}(y)<t^{(\overline{\succ }_{i},\succ _{-i})}(x)$ and these objects are exhausted earlier for profile $(\overline{\succ }_{i},\succ _{-i})$ than for $\succ$. This contradicts the fact that the set $O^{\succ }(t^{\succ }(o_{m+1}))$ is finite.

Step 3: For profile $\succ$, there exists an agent $i^{\prime }\ne i$ who eats $x$ at time $t^{(\overline{\succ }_{i},\succ _{-i})}(x)$ .

By way of contradiction, suppose that no such agent exists. Under PS, by construction, an agent who eats from an object at some moment continues to eat it until the object is exhausted (or until time 1). Then, for profile $\succ$, no agent except $i$ ever eats $x$ in the time interval $[0,t^{(\overline{\succ }_{i},\succ _{-i})}(x))$. Then, by Step 2, for profile $(\overline{\succ }_{i},\succ _{-i})$, no agent except $i$ ever eats $x$ in the time interval $[t^{\succ }(o_{m+1}),t^{(\overline{\succ }_{i},\succ _{-i})}(x))$, which is in contradiction with the fact that for profile $(\overline{\succ }_{i},\succ _{-i})$ object $x$ is exhausted at time $t^{(\overline{\succ }_{i},\succ _{-i})}(x)<1$.

Step 4: $i$ receives $x$ with a higher probability at $PS(\overline{\succ }_{i},\succ _{-i})$ than at $PS(\succ )$ .

When agents report $(\overline{\succ }_{i},\succ _{-i})$ rather than $\succ$, the cumulative amount that agents in $I\setminus \{i\}$ eat from $x$: (1) does not change in the time interval $[0,t^{\succ }(o_{m+1}))$ (due to the fact that eating patterns are the same up to time $t^{\succ }(o_{m+1})$); (2) weakly decreases for the time interval $[t^{\succ }(o_{m+1}),t^{\overline{\succ }}(x))$ (due to Step 2); (3) strictly decreases for the time interval $[t^{(\overline{\succ }_{i},\succ _{-i})}(x),t^{\succ }(x))$ (due to Step 3). Therefore, when agents report $(\overline{\succ }_{i},\succ _{-i})$ rather than $\succ$, the cumulative amount that agents in $I\setminus \{i\}$ eat from $x$ strictly decreases. But then, as $x$ is not the null object (due to Step 1), the amount that $i$ eats from $x$ must be higher for profile $(\overline{\succ }_{i},\succ _{-i})$ than for $\succ$. $\square$

We begin our equilibrium analysis of PS with sd-NE, our most strict equilibrium notion. Two natural questions regarding sd-NE under PS are: Does it exist, and when it does, does the outcome obtained in an sd-NE satisfy desirable properties? We take up the second question first, to which the answer turns out to be affirmative; the random assignment induced in an sd-NE under PS is sd-efficient and sd-envy-free. This is due to Theorem 1, presented below, which states that under PS the random assignment induced in an sd-NE is indeed precisely the random assignment induced under the truthful profile.

Theorem 1

If $\succ$ is an sd-NE under PS, then $PS(\succ )=PS(\succ ^{T})$.

Proof

Under PS, at profile $\succ$, let agent $i$ change her preference report from $\succ _{i}$ to $\succ _{i}^{T}$. There are two possibilities regarding $\succ _{i}^{T}$: $\succ _{i}^{T}$ satisfies either the supposition in Lemma 2 (i) or the supposition in Lemma 2 (ii). Considering the latter case, suppose that agent $i$’s top-ranked object in $O^{\succ }(t^{\succ }(o_{s}))$ is the same w.r.t. $\succ _{i}^{T}$ and $\succ _{i}$ for $s=0,1,\ldots ,m$, where $m<k-3$, but not the same for $s=m+1$. Then, by Lemma 2 (ii), at $PS(\succ _{i}^{T},\succ _{-i})$ and $PS(\succ ), i$ eats the same amount from $o_{s}$ for $s=1,\ldots ,m+1$, but the amount $i$ eats from her true favorite object in $O^{\succ }(t(o_{m+1}))$ is higher at $PS(\succ _{i}^{T},\succ _{-i})$ than at $PS(\succ )$. Then clearly $PS_{i}(\succ )\,sd(\succ _{i}^{T})\,PS_{i}(\succ _{i}^{T},\succ _{-i})$ does not hold, contradicting that $\succ$ is an sd-NE under PS. Thus the supposition in Lemma 2 (i) must be true for every agent. But then, due to similar arguments as in the Proof of Lemma 2 (i), we conclude that under PS when each agent $i$ changes her preference report from $\succ _{i}$ to $\succ _{i}^{T}$ agents’ eating patterns remain the same, meaning that $PS(\succ )=PS(\succ ^{T})$. $\square$

Turning to the question of existence of an sd-NE: We illustrate in Example 2 that an sd-NE may not exist under PS. There are situations when an sd-NE exists under PS, however. An example is when each agent has at most one desirable object—an object that she prefers to the outside option $o_{k}$.

Proposition 1

Let each agent have “at most one desirable object,” i.e., for each $i\in I$, if $o\succ _{i}^{T}o_{k}$ and $\overline{o}\succ _{i}^{T}o_{k}$ then $o=\overline{o}$. Then, the preference profile $\succ$ is an sd-NE under PS if for every $(i,o)\in (I,O) , o\succ _{i}o_{k}$ if and only if $o\succ _{i}^{T}o_{k}$.

Proof

For agent $i$, if her top-ranked object w.r.t. $\succ _{i}^{T}$ is $o_{k}$, then so is it w.r.t. $\succ _{i}$. Then $i$ receives her favorite object $o_{k}$ with probability $1$ under PS at profile $\succ$, showing that for $i$ reporting $\succ _{i}$ is an sd-best-response to $\succ _{-i}$.

For agent $i$, if her highest-ranked two objects w.r.t. $\succ _{i}^{T}$ are $o$ and $o_{k}$ ($o\ne o_{k}$), in that order, then so are they w.r.t. $\succ _{i}$. Then $i$ receives her favorite two objects with probability $1$ under PS at profile $\succ$. Also, due to Lemma 2 (ii) for agent $i$ the probability of receiving her favorite object $o$ is maximized when she reports $\succ _{i}$. Thus for $i$ reporting $\succ _{i}$ is an sd-best-response to $\succ _{-i}$.

Since for each agent $i$ reporting $\succ _{i}$ is an sd-best-response to $\succ _{-i}$, we find that $\succ$ is an sd-NE under PS. $\square$

The “at most one desirable object” assumption is extremely restrictive. We present below an example in which there are agents with multiple desirable objects and nonetheless an sd-NE exists.

Example 1

Let the sets of agents and objects be $I\!\equiv \! \{1,2,3,4\}$ and $O\!\equiv \! \{o_{1},o_{2},o_{3},o_{4}\}$ ($o_{4}$ is the null object). The preference relations of agents are as given below where $(x,y,z,t)$ means $x$ is preferred to $y, y$ is preferred to $z$, and $z$ is preferred to $t$.

$$\begin{aligned} \succ _{1}^{T}=(o_{1},o_{2},o_{3},o_{4})\quad \succ _{2}^{T},\succ _{3}^{T}=(o_{1},o_{4},o_{2},o_{3})\quad \succ _{4}^{T}=(o_{2},o_{3},o_{4},o_{1}) \end{aligned}$$

The reader can verify that in this example any preference profile at which agents are truthful when comparing objects that they weakly prefer to the null object is an sd-NE under PS. That is, $\succ$ is an sd-NE under PS if for every $(i,o,\overline{o})\in (I,O,O)$ such that $o\succsim _{i}^{T}o_{4}$ and $\overline{o}\succsim _{i}^{T}o_{4}, o\succsim _{i}\overline{o}$ if and only if $o\succsim _{i}^{T}\overline{o}$.

The above examples illustrate that an sd-NE may exist but does not say much about how likely that it exists in an assignment problem. One possible future research question is then identifying conditions on preferences of agents that are less restrictive than the “at most one desirable object” assumption and that allow for the existence of an sd-NE.¹³

Although PS is not strategy-proof, Lemma 2 helps us show that it is robust to a sort of manipulation scheme by agents via bribes in the form of “side payments,” a property known in the literature as “non-bossiness”: Given the preference reports $\succ _{-i}$ of other agents, suppose that agent $i$ is to choose from reporting $\overline{\succ }_{i}$ or $\succ _{i}$. Imagine that the random allotment of $i$ is the same for profiles $(\overline{\succ }_{i},\succ _{-i})$ and $(\succ _{i},\succ _{-i})$ but that of agent $\overline{i}\ne i$ is superior for profile $(\overline{\succ }_{i},\succ _{-i})$ (it may be sd-superior or may lead to a higher VNM utility). Then $\overline{i}$ may bribe $i$ by making her a side payment so that she reports $\overline{\succ }_{i}$ rather than $\succ _{i}$. (Or, equally, $i$ may exhort a side payment from $\overline{i}$ by threatening her to report $\succ _{i}$ rather than $\overline{\succ }_{i}$.) Such manipulation schemes do not exist under a non-bossy mechanism. More formally in our context: A mechanism $\varphi$ is non-bossy if there does not exist a four-tuple $(i,\overline{i},\overline{\succ }_{i},\succ )\in (I,I,\mathcal {O},\mathcal {O}^{n})$ such that $i\ne \overline{i}, \varphi _{i}(\overline{\succ }_{i},\succ _{-i})=\varphi _{i}(\succ )$, and $\varphi _{\overline{i}}(\overline{\succ }_{i},\succ _{-i})\ne \varphi _{\overline{i}}(\succ )$. Using Lemma 2, we next show that PS is a non-bossy mechanism.

Proposition 2

PS is non-bossy.

Proof

Under PS, at some profile $\succ$, let agent $i$ change her preference report from $\succ _{i}$ to $\overline{\succ }_{i}$. There are two possibilities regarding $\overline{\succ }_{i}$: $\overline{\succ }_{i}$ satisfies either the supposition in Lemma 2 (i) or the supposition in Lemma 2 (ii). If the supposition in Lemma 2 (i) is true, then by Lemma 2 (i) $\overline{\succ }_{i}$ is outcome-preserving at $\succ$ (i.e., $PS(\overline{\succ }_{i},\succ _{-i})=PS(\succ )$); if the supposition in Lemma 2 (ii) is true, then by Lemma 2 (ii) $PS_{i}(\overline{\succ }_{i},\succ _{-i})\ne PS_{i}(\succ )$. Either way the non-bossiness property is not violated, proving that PS is non-bossy. $\square$

Given the limitations pertaining to the sd-NE, we turn our attention to our weaker equilibrium notion defined in the preference domain, the weak sd-NE. Unlike an sd-NE, a weak sd-NE always exists under PS. Indeed, by its weak sd-strategy-proofness, under PS the truthful profile is always a weak sd-NE, and it gives rise to a desirable outcome—an sd-efficient and sd-envy-free random assignment. The natural question is then whether or not the weak sd-NE outcomes for non-truthful profiles satisfy appealing properties. Theorem 2, the results of which are illustrated in Example 2, provides a negative answer to this question. As it turns out, the outcome obtained in a weak sd-NE where one or more agents are non-truthful may not be sd-efficient and sd-envy-free. Worse, this random assignment may not be even weakly sd-envy-free and the VNM utility functions of agents may be such that this arguably undesirable outcome can be obtained in every Nash equilibrium.

Theorem 2

In an assignment problem, under PS

• (i) there may not exist an sd-NE,

  and there may exist a non-truthful profile $\succ \in \mathcal {O}^{n}$ such that:

• (ii) $\succ$ is a weak sd-NE;

• (iii) $PS(\succ )$ is not sd-efficient;

• (iv) $PS(\succ )$ is not weakly sd-envy-free;

• (v) $PS(\succ )$ admits an ex-post inefficient decomposition;

• (vi) for some specification of agents’ utility profile $u^{T}, \succ$ may be a Nash equilibrium while $\succ ^{T}$ may not be and every Nash equilibrium may lead to the random assignment $PS(\succ )$.

Proof

See Example 2. $\square$

Example 2

Let the sets of agents and objects be $I\equiv \{1,2,3,4,5\}$ and $O\equiv \{o_{1},o_{2},o_{3}\}$ ($o_{3}$ is the null object). The preference relations of agents are as given below where $(x,y,z)$ means $x$ is preferred to $y$ and $y$ is preferred to $z$. Below is also given a potential manipulation for agent 1.

$$\begin{aligned} \succ _{1}^{T},\succ _{2}^{T}= & {} (o_{2},o_{1},o_{3})\qquad \succ _{5}^{T}=(o_{1},o_{3},o_{2}) \\ \succ _{3}^{T},\succ _{4}^{T}= & {} (o_{1},o_{2},o_{3})\qquad \succ _{1}=(o_{1},o_{2},o_{3}) \end{aligned}$$

Consider the profile $\succ =(\succ _{1},\succ _{-1}^{T})$. Under PS, the random assignments induced for profiles $\succ ^{T}$ and $\succ$ are as given below.

$PS(\succ ^{T})$	$o_{1}$	$o_{2}$	$o_{3}$	$PS(\succ )$	$o_{1}$	$o_{2}$	$o_{3}$
1	0	$\frac{5}{12}$	$\frac{7}{12}$	1	$\frac{1}{4}$	$\frac{3}{16}$	$\frac{9}{16}$
2	0	$\frac{5}{12}$	$\frac{7}{12}$	2	0	$\frac{7}{16}$	$\frac{9}{16}$
3	$\frac{1}{3}$	$\frac{1}{12}$	$\frac{7}{12}$	3	$\frac{1}{4}$	$\frac{3}{16}$	$\frac{9}{16}$
4	$\frac{1}{3}$	$\frac{1}{12}$	$\frac{7}{12}$	4	$\frac{1}{4}$	$\frac{3}{16}$	$\frac{9}{16}$
5	$\frac{1}{3}$	0	$\frac{2}{3}$	5	$\frac{1}{4}$	0	$\frac{3}{4}$

We show the arguments made in Theorem 2 through this example; for ease in exposition, we show part (i) in the end.

(ii) Since PS is weakly sd-strategy-proof, under PS for any agent truth-telling is always a weak sd-best-response to other agents’ preference reports. Thus, to show that $\succ =(\succ _{1},\succ _{-1}^{T})$ is a weak sd-NE, we only need to show that for agent 1 reporting $\succ _{1}$ is a weak sd-best-response to $\succ _{-1}^{T}$. That is, we need to show that there does not exist $\overline{\succ }_{1}\in \mathcal {O}$ such that $PS_{1}(\overline{\succ }_{1},\succ _{-1}^{T})\,S\!D(\succ _{1}^{T})\,PS(\succ )$. In our search of such $\overline{\succ }_{1}$: $\overline{\succ }_{1}$ cannot be $(o_{3},o_{1},o_{2})$ or $(o_{3},o_{2},o_{1})$ because if it were so, at $PS_{1}(\overline{\succ }_{1},\succ _{-1}^{T})$ agent 1 receives $o_{3}$ with probability 1, which is for agent 1 sd-inferior to $PS(\succ )$. Also, w.l.o.g. we can discard from consideration the preference relations $(o_{1},o_{3},o_{2})$ and $(o_{2},o_{3},o_{1})$ because by reporting instead $(o_{1},o_{2},o_{3})$ and $(o_{2},o_{1},o_{3})$, respectively, agent 1 clearly attains random allotments that are sd-superior. Then, to find $\overline{\succ }_{1}$ as specified, the only candidate left to check for is $\succ _{1}^{T}$. But this also cannot be the case because for agent 1, $PS_{1}(\succ ^{T})$ is not strictly sd-superior to $PS_{1}(\succ )$ (see the tables above).

(iii) At $PS(\succ )$ agent 1 receives $o_{1}$ and agent 3 receives $o_{2}$ with positive probabilities, which are one another’s favorite objects. Therefore, we can obtain from $PS(\succ )$ a random assignment which is strictly sd-superior to $PS(\succ )$ by letting these two agents trade probability shares of these two objects (e.g., agent 1 gives agent 3 a probability share of $\frac{3}{16}$ units from $o_{1}$ and in exchange receives from her $\frac{3}{16}$ units of $o_{2}$).

(iv) At $PS(\succ )$ agent 1 sd-envies agent 2.

(v) An ex-post inefficient decomposition of $PS(\succ )$ is given below. In this decomposition, the first two deterministic assignments are not Pareto-optimal w.r.t. $\succ ^{T}$.

$$\begin{aligned} PS(\succ )= & {} \left[ \begin{array}{ccc} \frac{1}{4} &{}\quad \frac{3}{16} &{}\quad \frac{9}{16} \\ 0 &{}\quad \frac{7}{16} &{}\quad \frac{9}{16} \\ \frac{1}{4} &{}\quad \frac{3}{16} &{}\quad \frac{9}{16} \\ \frac{1}{4} &{}\quad \frac{3}{16} &{}\quad \frac{9}{16} \\ \frac{1}{4} &{}\quad 0 &{}\quad \frac{3}{4} \end{array} \right] =\frac{3}{16}\left[ \begin{array}{ccc} 1 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 1 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 0 &{}\quad 1 \end{array} \right] +\frac{1}{16}\left[ \begin{array}{ccc} 1 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 1 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \end{array} \right] +\frac{1}{8}\left[ \begin{array}{ccc} 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 0 &{}\quad 1 \\ 1 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 1 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \end{array} \right] \\&+\,\frac{1}{8}\left[ \begin{array}{ccc}4 0 &{}\quad 1 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \\ 1 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 0 &{}\quad 1 \end{array} \right] +\frac{1}{16}\left[ \begin{array}{ccc} 0 &{}\quad 1 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 0 &{}\quad 1 \\ 1 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \end{array} \right] +\frac{3}{16}\left[ \begin{array}{ccc} 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 1 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \\ 1 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \end{array} \right] +\frac{1}{4}\left[ \begin{array}{ccc} 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 1 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 0 &{}\quad 1 \\ 1 &{}\quad 0 &{}\quad 0 \end{array} \right] \end{aligned}$$

(vi) Let agents’ utility profile $u^{T}$ be as follows: for agent 1, $u_{1}^{T}(o_{1})=14, u_{1}^{T}(o_{2})=15$, and $u_{1}^{T}(o_{3})=0$; and for an agent $i\in \{2,3,4,5\}$ with a preference relation $\succ _{i}^{T}=(x,y,z), u_{i}^{T}(x)=M\times u_{i}^{T}(y)=M^{2}\times u_{i}^{T}(z)$ where $u_{i}^{T}(z)>0, M>0$, and $M$ is set sufficiently large.

By our choice of VNM utility functions and due to Lemma 2 (ii), at a preference profile which is a Nash equilibrium under PS, any agent $i\in \{2,3,4,5\}$ must have reported her top-ranked object truthfully. When that is the case, it is easy to verify that $o_{1}$ is exhausted before $o_{2}, o_{2}$ is exhausted before $o_{3}$, and $o_{3}$ lasts until time 1.

For an agent $i\in \{3,4,5\}$, given that she truthfully reports $o_{1}$ as her top-ranked object and that $o_{2}$ and $o_{3}$ are still available when $o_{1}$ is exhausted, it is clear that her utility-maximizing strategy is to rank $o_{2}$ and $o_{3}$ truthfully. Then, at any preference profile which is a Nash equilibrium, agents 3, 4 and 5 are truthful.

For agent 2, given that she truthfully reports $o_{2}$ as her top-ranked object and that $o_{1}$ is exhausted before $o_{2}$, the random assignment induced is the same whether she reports $(o_{2},o_{1},o_{3})$ or $(o_{2},o_{3},o_{1})$. Then, at any preference profile which is a Nash equilibrium, agent 2 reports $(o_{2},o_{1},o_{3})$ or $(o_{2},o_{3},o_{1})$.

For agent 1, clearly a preference report where $o_{3}$ is the top-ranked object can never be a best-response to other agents’ preference reports. Then, at a preference profile which is a Nash equilibrium, her preference report must be one of the following: $(o_{1},o_{2},o_{3}), (o_{2},o_{1},o_{3}), (o_{1},o_{3},o_{2}), (o_{2},o_{3},o_{1})$. Given that $o_{1}$ is exhausted before $o_{2}$ and that $o_{2}$ is exhausted before $o_{3}$, for agent 1 reporting $(o_{1},o_{2},o_{3})$ clearly yields a higher VNM utility than reporting $(o_{1},o_{3},o_{2})$. Given that agents 3, 4 and 5 are truthful and that agent 2 reports $(o_{2},o_{1},o_{3})$ or $(o_{2},o_{3},o_{1})$, the random assignment induced is $PS(\succ )$ if agent 1 reports $(o_{1},o_{2},o_{3})$ and $PS(\succ ^{T})$ if she reports $(o_{2},o_{1},o_{3})$ or $(o_{2},o_{3},o_{1})$. With respect to $u_{1}^{T}$, agent 1’s VNM utilities at $PS(\succ )$ and $PS(\succ ^{T})$ are respectively $\frac{101}{16}\,(=6.3125)$ and $\frac{25}{4}\,(=6.25)$. Then, at any preference profile which is a Nash equilibrium, agent 1’s preference report is $\succ _{1}=(o_{1},o_{2},o_{3})$.

Due to the arguments above, for $u^{T}$ specified as above, there are two Nash equilibria under PS: In one Nash equilibrium agent 2 reports $(o_{2},o_{1},o_{3})$ and in the other she reports $(o_{2},o_{3},o_{1})$; in both Nash equilibria, agent 1 reports $\succ _{1}$ and agents 3, 4, and 5 are truthful. The random assignment induced in both Nash equilibria is $PS(\succ )$.

(i) Since an sd-NE is a Nash equilibrium and due to (vi), we need to consider only two preference profiles as potential sd-NEs: At one profile agent 2 reports $(o_{2},o_{1},o_{3})$ and at the other she reports $(o_{2},o_{3},o_{1})$; at both profiles agent 1 reports $\succ _{1}$ and agents 3, 4, and 5 are truthful. But for both these profiles, agent 1 increases the probability with which she receives her favorite object, $o_{2}$, if she changes her preference report from $\succ _{1}$ to $\succ _{1}^{T}$, which proves that there exists no sd-NE in this assignment problem.

5 Conclusion

The probabilistic serial (PS) mechanism has attracted much attention in recent literature for its superior efficiency and fairness properties. When agents are truthful, the outcome obtained under PS satisfies sd-efficiency and sd-no-envy, two compelling properties violated by the outcome of random priority (RP). Since PS converges to RP as the problem size gets large Che and Kojima (2010), gains in efficiency and fairness under PS can be of practical value especially in small assignment problems. Nevertheless, in small assignment problems agents may resort to strategizing under PS and in equilibrium PS may not deliver more efficient and fair outcomes as originally intended. We studied the Nash equilibria (NEs) of the preference revelation game induced by PS. We considered two equilibrium notions defined in the preference domain using the stochastic dominance (sd-) relation—sd-NE and weak sd-NE. Absent the knowledge of agents’ von-Neumann–Morgenstern (VNM) utility functions, a preference profile is guaranteed to be a Nash equilibrium only if it is an sd-NE and may possibly be a Nash equilibrium only if it is a weak sd-NE.

We show that under PS an sd-NE always leads to a desirable outcome—an sd-efficient and sd-envy-free random assignment, yet its existence is not guaranteed. In contrast, a weak sd-NE always exists under PS yet a weak sd-NE where one or more agents are non-truthful may lead to an undesirable outcome—a random assignment which is neither sd-efficient nor sd-envy-free. Worse, on two accounts this outcome may be even worse than the outcome obtained under RP when agents are truthful; it may not be even weakly sd-envy-free, and absent the knowledge of agents’ true preferences, the ex-post efficient implementation of this random assignment cannot be guaranteed. Worse still, the agents may have such VNM utility functions as to give rise to this undesirable outcome in every Nash equilibrium of the preference revelation game. The results of our equilibrium analysis of PS cautions that in small assignment problems whether or not desirable outcomes are obtained in equilibrium under PS depends on the specifics of the considered random assignment problem.