Abstract
We explore the consequences of weakening the notion of incentive compatibility from strategy-proofness to ordinal Bayesian incentive compatibility (OBIC) in the random assignment model. If the common prior of the agents is the uniform prior, then a large class of random mechanisms are OBIC with respect to this prior—this includes the probabilistic serial mechanism. We then introduce a robust version of OBIC: a mechanism is locally robust OBIC if it is OBIC with respect all independent and identical priors in some neighborhood of a given independent and identical prior. We show that every locally robust OBIC mechanism satisfying a mild property called elementary monotonicity is strategy-proof. This leads to a strengthening of the impossibility result in Bogomolnaia and Moulin (J Econ Theory 100:295–328, 2001): if there are at least four agents, there is no locally robust OBIC and ordinally efficient mechanism satisfying equal treatment of equals.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
This paper explores the consequences of weakening incentive compatibility from strategy-proofness to ordinal Bayesian incentive compatibility in the random assignment model (one-sided matching model). Ordinal Bayesian incentive compatibility (OBIC) requires that the truth-telling expected share vector of an agent first-order stochastically dominates the expected share vector from reporting any other preference. It is the natural analogue of Bayesian incentive compatibility in an ordinal mechanism. This weakening of strategy-proofness was proposed by d’Aspremont and Peleg (1988). We study OBIC by considering mechanisms that allow for randomization in the assignment model.
In the random assignment model, the set of mechanisms satisfying ex-post efficiency and strategy-proofness is quite rich.Footnote 1 Despite satisfying such strong incentive properties, all of them either fail to satisfy equal treatment of equals, a weak notion of fairness, or ordinal efficiency.Footnote 2 Indeed, Bogomolnaia and Moulin (2001) propose a new mechanism, called the probabilistic serial mechanism, which satisfies equal treatment of equals and ordinal efficiency. However, they show that it fails strategy-proofness, and no mechanism can satisfy all these three properties simultaneously if there are at least four agents. A primary motivation for weakening the notion of incentive compatibility to OBIC is to investigate if we can escape this impossibility result.
We show two types of results. First, if the (common) prior is a uniform probability distribution over the set of possible preferences, then every neutral mechanism satisfying a mild property called elementary monotonicity is OBIC.Footnote 3 An example of such a mechanism is the probabilistic serial mechanism. This is a positive result and provides a strategic foundation for the probabilistic serial mechanism. In particular, it shows that there exist ordinally efficient mechanisms satisfying equal treatment of equals which are OBIC with respect to the uniform prior.
Second, we explore the implications of strengthening OBIC as follows. A mechanism is locally robust OBIC (LROBIC) with respect to an independent and identical prior if it is OBIC with respect to every independent and identical prior in its “neighborhood". The motivation for such requirement of robustness in the mechanism design literature is now well-known, and referred to as the Wilson doctrine (Wilson 1987). We show that every LROBIC mechanism satisfying elementary monotonicity is strategy-proof. An immediate corollary of this result is that the probabilistic serial mechanism is not LROBIC (though it is OBIC with respect to the uniform prior). As a corollary, we can show that when there are at least four agents, there is no LROBIC and ordinally efficient mechanism satisfying equal treatment of equals. This strengthens the seminal impossibility result of Bogomolnaia and Moulin (2001) by replacing strategy-proofness with LROBIC.
Both our results point to very different implications of OBIC in the presence of elementary monotonicity—if the prior is uniform, this notion of incentive compatibility is very permissive; but if we require OBIC with respect to a set of independent and identical priors in any neighborhood of a given prior, this notion of incentive compatibility is very restrictive.
1.1 Related literature
There is a large literature on random assignment problems. We summarize them below.
The notion of incentive compatibility that we use, OBIC, has been used in voting models by Majumdar and Sen (2004); Bhargava et al. (2015); Mishra (2016); Hong and Kim (2018) to escape the dictatorship result in (Gibbard 1973; Satterthwaite 1975; Gibbard 1977). All these papers use deterministic mechanisms in voting models, whereas we apply OBIC to the random assignment model. Majumdar and Sen (2004) show that every deterministic neutral voting mechanism satisfying elementary monotonicity is OBIC with respect to uniform priors. Our Theorem 1 shows that this result generalizes to the random assignment model. Mishra (2016) shows that in the deterministic voting model, elementary monotonicity and OBIC with respect to “generic" prior is equivalent to strategy-proofness in a variety of restricted domains—see also Hong and Kim (2018) for a strengthening of this result. Though these results are similar to our Theorem 2, there are significant differences. First, we consider randomization while these results are only for deterministic mechanisms. Our notion of locally robust OBIC is stronger than OBIC with respect to generic priors used in these papers. Second, ours is a model of private good allocation (random assignment), while these papers deal with the voting model.
Bogomolnaia and Moulin (2001) introduce a family of mechanisms in the random assignment model. They call these the simultaneous eating algorithms. which generate ordinally efficient random assignments, a stronger notion of efficiency than ex-post efficiency.Footnote 4 The probabilistic serial mechanism belongs to this family and it is anonymous. However, it is not strategy-proof. In fact, Bogomolnaia and Moulin (2001) show that there is no ordinally efficient and strategy-proof mechanism satisfying equal treatment of equals when there are at least four agents.Footnote 5
There is a large literature that provides strategic foundations to the probabilistic serial (PS) mechanism. Bogomolnaia and Moulin (2001) show that the PS mechanism satisfies weak-strategy-proofness. Their notion of weak strategy-proofness requires that the manipulation share vector cannot first-order-stochastic-dominate the truth-telling share vector. Bogomolnaia and Moulin (2002) study a problem where agents have an outside option. When agents have the same ordinal ranking over objects but the position of outside option in the ranking of objects is the only private information, they show that the PS mechanism is strategy-proof. Other contributions in this direction include Liu (2020); Liu and Zeng (2019), who identify domains where the probabilistic serial mechanism is strategy-proof. Che and Kojima (2010) show that the PS mechanism and the random priority mechanism (which is strategy-proof) are asymptotically equivalent. Similarly, Kojima and Manea (2010) show that when sufficiently many copies of an object are present, then the PS mechanism is strategy-proof. Thus, in large economies, the PS mechanism is strategy-proof. Balbuzanov (2016) introduce a notion of strategy-proofness which is stronger than weak strategy-proofness and show that the PS mechanism satisfies it. His notion of strategy-proofness is based on the “convex” domination of lotteries, and hence, called convex strategy-proofness. Mennle and Seuken (2021) define a notion called partial strategy-proofness, which is weaker than strategy-proofness and show that the PS mechanism satisfies it. They show that strategy-proofness is equivalent to upper invariant, lower invariant and elementary monotonicity (they call it swap monotonicity). Their notion of partial strategy-proofness is equivalent to upper invariance and elementary monotonicity, and hence, it is weaker than strategy-proofness.
The main difference between these weakenings of strategy-proofness and ours is that OBIC is a prior-based notion of incentive compatibility. It is the natural analogue of Bayesian incentive compatibility in an ordinal environment. Ehlers and Massó (2007) study OBIC in a two-sided matching problem. Their main focus is on OBIC mechanism that select a stable matching. They characterize the beliefs for which such a mechanism exists. There is a literature in computer science studying computational aspects of manipulation of the PS rule—see Aziz et al. (2014, 2015) and references therein.
2 Model
2.1 Assignments
There are n agents and n objects.Footnote 6 Let \(N:=\{1,\ldots ,n\}\) be the set of agents and A be the set of objects. We define the notion of a feasible assignment first.
Definition 1
An \(n \times n\) matrix L is an assignment if
Hence, an assignment is a bistochastic matrix. For any assignment L, we write \(L_i\) as the share vector of agent i.Footnote 7 Formally, a share vector is a probability distribution over the set of objects. For any \(i \in N\) and any \(a \in A\), \(L_{ia}\) denotes the “share" of agent i of object a. The second constraint of the assignment definition requires that the total share of every agent is 1. The third constraint of the assignment requires that every object is completely assigned. Let \({\mathcal {L}}\) be the set of all assignments.
An assignment L is deterministic if \(L_{ia} \in \{0,1\}\) for all \(i \in N\) and for all \(a \in A\). Let \({\mathcal {L}}^d\) be the set of all deterministic assignments. By the Birkohff-von-Neumann theorem, for every \(L \in {\mathcal {L}}\), there exists a set of deterministic assignments in \({\mathcal {L}}^d\) whose convex combination equals L.
2.2 Preferences
A preference is a strict ordering of A. The preference of an agent i will be denoted by \(P_i\). The set of all preferences over A is denoted by \({\mathcal {P}}\). A preference profile is \({\mathbf {P}} \equiv (P_1,\ldots ,P_{n})\), and we will denote by \(P_{-i}\) the preference profile \({\mathbf {P}}\) excluding the preference \(P_i\) of agent i. We write \(aP_ib\) to denote that a is strictly preferred over b in preference \(P_i\).
2.3 Prior
We assume that the preference of each agent is independently and identically drawn using a common prior \(\mu \), which is a probability distribution over \({\mathcal {P}}\). From now on, whenever we say a prior, we refer to such an independent and identical prior. We will denote by \(\mu (P_i)\) the probability with which agent i has preference \(P_i\). We assume that \(\mu (P_i) > 0\) for each \(P_i\). With some abuse of notation, we will denote the probability with which agents in \(N \setminus \{i\}\) have preference profile \(P_{-i}\) as \(\mu (P_{-i})\). Note that by independence, \(\mu (P_{-i}) = \times _{j \ne i}\mu (P_j)\).
3 Ordinal Bayesian incentive compatibility
Our solution concept is Bayes-Nash equilibrium but we restrict attention to ordinal mechanisms, i.e., mechanisms where we only elicit ranking over objects from each agent. Hence, whenever we say mechanism, we refer to such ordinal mechanisms.Footnote 8 Formally, a mechanism is a map \(Q: {\mathcal {P}}^n \rightarrow {\mathcal {L}}\). A mechanism Q assigns a share vector \(Q_i({\mathbf {P}})\) to agent i at every preference profile \({\mathbf {P}}\).
Before discussing the notions of incentive compatibility, it is useful to think how agents compare share vectors in our model. Fix agent i with a preference \(P_i\) over the set of objects A. Denote the k-th ranked object in \(P_i\) as \(P_i(k)\). Consider two share vectors \(\pi , \pi '\). For every \(a \in A\), we will denote by \(\pi _a\) and \(\pi '_a\) the share assigned to object a in \(\pi \) and \(\pi '\) respectively. We will say \(\pi \) first-order-stochastically-dominates (FOSD) \(\pi '\) according to \(P_i\) if
In this case, we will write \(\pi \succ _{P_i} \pi '\). Notice that \(\succ _{P_i}\) is not a complete relation over the outcomes. An equivalent (and well known) definition of \(\succ _{P_i}\) relation is that for every von-Neumann–Morgenstern utility representation of \(P_i\), the expected utility from \(\pi \) is at least as much as \(\pi '\).
The most standard notion of incentive compatibility is strategy-proofness (dominant strategy incentive compatibility), which uses the FOSD relation to compare share vectors.
Definition 2
A mechanism Q is strategy-proof if for every \(i \in N\), every \(P_{-i} \in {\mathcal {P}}^{n-1}\), and every \(P_i, P'_i \in {\mathcal {P}}\), we have
The interpretation of this definition is that fixing the preferences of other agents, the truth-telling share vector must FOSD other share vectors that can be obtained by deviation. This definition of strategy-proofness appeared in Gibbard (1977) for voting problems, and has been the standard notion in the literature on random voting and random assignment problems.
The ordinal Bayesian incentive compatibility notion is an adaptation of this by changing the solution concept to Bayes-Nash equilibrium. It was first introduced and studied in a voting committee model in d’Aspremont and Peleg (1988), and was later used in many voting models (Majumdar and Sen 2004). To define it formally, we introduce the notion of an interim share vector. Fix an agent i with preference \(P_i\). Given a mechanism Q, the interim share of object a for agent i by reporting \(P'_i\) is:
The interim share vector of agent i by reporting \(P'_i\) will be denoted as \(q_{i}(P'_i)\).
Definition 3
A mechanism Q is ordinally Bayesian incentive compatible (OBIC) (with respect to prior \(\mu \)) if for every \(i \in N\) and every \(P_i, P'_i \in {\mathcal {P}}\), we have
It is immediate that if a mechanism Q is strategy-proof it is OBIC with respect to every (including correlated and non-identical) prior. Conversely, if a mechanism is OBIC with respect to all priors (including correlated and non-identical priors), then it is strategy-proof.
3.1 A motivating example
We investigate a simple example to understand the implications of strategy-proofness and OBIC for the probabilistic serial mechanism. Suppose \(n=3\) with three objects \(\{a,b,c\}\). Consider the preference profiles \((P_1,P_2,P_3)\) and \((P'_1,P_2,P_3)\) shown in Table 1—the table also shows the share vector of each agent in the probabilistic serial mechanism of Bogomolnaia and Moulin (2001). In the probabilistic serial mechanism, each agent starts “eating" her favorite object simultaneously till the object is finished. Then, she moves to the best available object according to her preference and so on. Each agent has the same eating speed. Table 1 shows the output of the probabilistic serial mechanism for preference profiles \((P_1,P_2,P_3)\) and \((P'_1,P_2,P_3)\). Since \(Q_{1a}(P'_1,P_2,P_3)+Q_{1c}(P'_1,P_2,P_3) > Q_{1a}(P_1,P_2,P_3)+Q_{1c}(P_1,P_2,P_3)\), we conclude that \(Q_1(P_1,P_2,P_3) \nsucc _{P'_1} Q_1(P'_1,P_2,P_3)\). Hence, agent 1 can manipulate from \(P_1\) to \(P'_1\), when agents 2 and 3 have preferences \((P_2,P_3)\).
When can such a manipulation be prevented by OBIC? Note that \(P_1\) is generated from \(P'_1\) by permuting a and c. Suppose we permute \(P_2\) and \(P_3\) also to get \(P'_2\) and \(P'_3\) respectively:
Since the probabilistic serial mechanism is neutral (with respect to objects), the share vector of agent 1 at \((P_1,P_2,P_3)\) is a permutation of its share vector at \((P'_1,P'_2,P'_3)\). Further, when all the preferences are equally likely, the probability of \((P_2,P_3)\) is equal to the probability of \((P'_2,P'_3)\). So, the total expected probability of a and c for agent 1 at \(P_1\) and \(P'_1\) is the same (where expectation is taken over \((P_2,P_3)\) and \((P'_2,P'_3)\)). As we show below, this argument generalizes and the expected share vector at \(P_1\) first-order-stochastic-dominates the expected share vector at \(P'_1\) when the true preference is \(P_1\) and prior is uniform.
4 Uniform prior and possibilities
In this section, we present our first result which shows that the set of OBIC mechanisms is much larger than the set of strategy-proof mechanisms if the prior is the uniform prior. A prior \(\mu \) is the uniform prior if \(\mu (P_i) = \frac{1}{|{\mathcal {P}}|} = \frac{1}{n!}\) for each \(P_i \in {\mathcal {P}}\). Uniform prior puts equal probability on each of the possible preferences. We call a mechanism U-OBIC if it is OBIC with respect to the uniform prior.
We show that there is a large class of mechanisms which are U-OBIC - this will include some well-known mechanisms which are known to be not strategy-proof. This class is characterized by two axioms, neutrality and elementary monotonicity, which we define next. To define neutrality, consider any permutation \(\sigma : A \rightarrow A\) of the set of objects. For every preference \(P_i\), define \(P_i^{\sigma }\) as the preference that satisfies: \(aP_ib\) if and only if \(\sigma (a)P^{\sigma }_i\sigma (b)\). Let \({\mathbf {P}}^{\sigma }\) be the preference profile generated by permuting each preference in the preference profile \({\mathbf {P}}\) by the permutation \(\sigma \).
Definition 4
A mechanism Q is neutral if for every \({\mathbf {P}}\) and every permutation \(\sigma \),
Neutrality requires that objects be treated symmetrically by the mechanism. Any mechanism which does not use the “names" of the objects is neutral—this includes all priority mechanisms (including the random priority mechanism), the simultaneous eating algorithms (including the probabilistic serial mechanism) in Bogomolnaia and Moulin (2001).
Our next axiom is elementary monotonicity, an axiom which requires a mild form of monotonicity. This was introduced in Majumdar and Sen (2004). To define it, we need the notion of “adjacency" of preferences. We say preferences \(P_i\) and \(P'_i\) are adjacent if there exists a \(k \in \{1,\ldots ,n-1\}\) such that
In other words, \(P'_i\) is obtained by swapping consecutively ranked objects in \(P_i\). Here, if \(P_i(k)=a\) and \(P_i(k+1)=b\), we say that \(P'_i\) is an (a, b)-swap of \(P_i\).
Definition 5
A mechanism Q satisfies elementary monotonicity if for every \(i \in N\), every \(P_{-i} \in {\mathcal {P}}^{n-1}\), and every \(P_i, P'_i \in {\mathcal {P}}\) such that \(P'_i\) is an (a, b)-swap of \(P_i\) for some a, b, we have
In other words, as agent i lifts alternative b in ranking by one position by swapping it with a (and keeping the ranking of every other object the same), elementary monotonicity requires that the share of object b should weakly increase for agent i, while share of object a should weakly decrease. A similar axiom called swap monotonicity is used in Mennle and Seuken (2021).Footnote 9
It is not difficult to see that elementary monotonicity is a necessary condition for strategy-proofness—see Majumdar and Sen (2004). As we show later, elementary monotonicity is satisfied by a variety of mechanisms - including those which are not strategy-proof. However, every neutral mechanism satisfying elementary monotonicity is U-OBIC.
Theorem 1
Every neutral mechanism satisfying elementary monotonicity is U-OBIC.
Proof
Fix a neutral mechanism Q satisfying elementary monotonicity. The proof goes in various steps.
Step 1 Pick an agent i and two preferences \(P_i\) and \(P'_i\). Pick any \(k \in \{1,\ldots ,n\}\) and suppose \(P_i(k)=a\) and \(P'_i(k)=b\). We show that the interim shares of a and b are same for agent i in preferences \(P_i\) and \(P'_i\): \(q_{ia}(P_i) = q_{ib}(P'_i)\). This is a consequence of uniform prior and neutrality. To see this, let \(P'_i = P_i^{\sigma }\) for some permutation \(\sigma \) of objects in A. Then, \(b = \sigma (a)\) and hence, for every \(P_{-i}\), we have
Due to uniform prior and using the above expression,
where the third equality follows from the fact that \(\{P_{-i}: P_{-i} \in {\mathcal {P}}^{n-1}\}=\{P_{-i}^{\sigma }: P_{-i} \in {\mathcal {P}}^{n-1}\}\).
In view of step 1, with some abuse of notation, we write \(q_{ik}\) to denote the interim share of the object at rank k in the preference. We call \(q_i\) the interim rank vector of agent i.
Step 2 Pick an agent i and a preference \(P_i\). We show that interim shares are non-decreasing with rank: \(q_{ik} \ge q_{i(k+1)}\) for all \(k \in \{1,\ldots ,n-1\}\). Fix a number k and let \(P_i(k)=a\) and \(P_i(k+1)=b\). Then, consider the preference \(P'_i\), which is an (a, b)-swap of \(P_i\). For every \(P_{-i}\), elementary monotonicity implies \(Q_{ia}(P_i,P_{-i}) \ge Q_{ia}(P'_i,P_{-i})\). Due to uniform prior, \(q_{ia}(P_i) \ge q_{ia}(P'_i)\). But by Step 1,
Step 3 We show that Q is OBIC with respect to the uniform prior. Suppose agent i has preference \(P_i\). By Steps 1 and 2, she gets interim rank vector \((q_{i1},\ldots ,q_{in})\) by reporting \(P_i\) with \(q_{ij} \ge q_{ij+1}\) for all \(j \in \{1,\ldots ,n-1\}\). Suppose she reports \(P'_i=P^{\sigma }_i\), where \(\sigma \) is some permutation of set of objects. By Steps 1 and 2, the interim share vector is a permutation of interim rank vector \(q_i\) . Using non-decreasingness of this interim share vector with respect to ranks, we get \(q_i(P_i) \succ _{P_i} q_i(P'_i)\). Hence, Q is OBIC with respect to uniform prior. \(\square \)
Theorem 1 generalizes, an analogous result in Majumdar and Sen (2004), who consider the voting problem and only deterministic mechanisms. They arrive at the same conclusion as Theorem 1 in their model. Theorem 1 shows that their result holds even in the random assignment problem.
4.1 Probabilistic serial mechanism and U-OBIC
Bogomolnaia and Moulin (2001) define a family of mechanisms, which they call the simultaneous eating algorithms (SEA). Though the SEAs are not strategy-proof, they satisfy compelling efficiency and fairness properties, which we discuss in Sect. 5. We informally introduce the SEAs—for a formal discussion, see Bogomolnaia and Moulin (2001).
Each SEA is defined by a (possibly time-varying) eating speed function for each agent. At every preference profile, agents simultaneously start “eating" their favorite objects at a rate equal to their eating speed. Once an object is completely eaten (i.e., the entire share of 1 is consumed), the amount eaten by each agent is the share of that agent of that object. Once an object completely eaten, agents go to their next preferred object and so on.
If the eating speed of each agent is the same, then the simultaneous eating algorithm is anonymous. Bogomolnaia and Moulin (2001) call the unique anonymous SEA, the probabilistic serial mechanism.Footnote 10
Corollary 1
Every simultaneous eating algorithm is U-OBIC.
Proof
Clearly, the SEAs are neutral since eating speeds do not depend on the objects. The SEAs also satisfy elementary monotonicity: Theorem 3 in Cho (2018) and Theorem 1 in Mennle and Seuken (2021). Hence, by Theorem 1, we are done. \(\square \)
5 Locally robust OBIC
While the uniform prior is an important prior in decision theory, it is natural to ask if Theorem 1 extends to other “generic” priors. Though we do not have a full answer to this question, we have been able to answer this question in negative under a natural robustness requirement. Our robustness requirement is local. Take any (independent and identical) prior \(\mu \), and let \(\mu '\) be any (independent and identical) prior in the \(\epsilon \)-radius ball around \(\mu \) (where \(\epsilon > 0\)), i.e., \(||\mu (P) - \mu '(P)|| < \epsilon \) for all \(P \in {\mathcal {P}}\). In this case, we write \(\mu ' \in B_{\epsilon }(\mu )\). Our local robustness requirement is the following.
Definition 6
A mechanism Q is locally robust OBIC (LROBIC) with respect to a prior \(\mu \) if there exists an \(\epsilon > 0\) such that for every prior \(\mu ' \in B_{\epsilon }(\mu )\), Q is OBIC with respect to \(\mu '\).
It is well known that Bayesian incentive compatibility with respect to all priors lead to strategy-proofness (Ledyard 1978). Here, we require OBIC with respect to all independent and identical priors in the \(\epsilon \)-neighborhood of an independent and identical prior. Bhargava et al. (2015) study a version of robust OBIC with respect to uniform prior but their robustness also allows the mechanism to be OBIC with respect to correlated priors. They show that a large class of voting rules satisfy their notion of LROBIC. We show that in the random assignment model, LROBIC with respect to any independent and identical prior has a very different implication.
Theorem 2
A mechanism is LROBIC with respect to a prior and satisfies elementary monotonicity if and only if it is strategy-proof.
Remark
Though relatively strong, the notion of LROBIC is in the spirit of robust mechanism design (Bergemann and Morris 2005). It remains to be seen if Theorem 2 continues to hold under weaker notions of OBIC than LROBIC—for instance, OBIC with respect to generic priors as in Majumdar and Sen (2004).Footnote 11 It may be possible to construct a OBIC mechanism satisfying elementary monotonicity which is not strategy-proof if the prior is approriately chosen. Theorem 1 shows this possibility for uniform priors.
The proof of Theorem 2 builds on some earlier results. Before giving the proof, we define some notions and preliminary results. We first decompose OBIC into three conditions. This decomposition is similar to the decomposition of strategy-proofness in Mennle and Seuken (2021)—there are some minor differences in axioms and we look at interim share vectors whereas they look at ex-post share vectors.
Our decomposition of OBIC uses the following three axioms.
Definition 7
A mechanism Q satisfies interim elementary monotonicity if for every \(i \in N\) and every \(P_i,P'_i\) such that \(P'_i\) is an (a, b)-swap of \(P_i\), we have
Give a preference \(P_i\) of agent i and an object \(a \in A\), define \(U(a,P_i):=\{x \in A: x~P_i~a\}\) and \(L(a,P_i):=\{x \in A: a~P_i~x\}\).
Definition 8
A mechanism Q satisfies interim upper invariance if for every \(i \in N\) and every \(P_i,P'_i\) such that \(P'_i\) is an (a, b)-swap of \(P_i\), and for every \(x \in U(a,P_i)\), we have
Definition 9
A mechanism Q satisfies interim lower invariance if for every \(i \in N\) and every \(P_i,P'_i\) such that \(P'_i\) is an (a, b)-swap of \(P_i\), and for every \(x \in L(b,P_i)\), we have
The following proposition characterizes OBIC using these axioms.
Proposition 1
A mechanism Q is OBIC with respect to a prior if and only if it satisfies interim elementary monotonicity, interim upper invariance, and interim lower invariance.
Since the proof of Proposition 1 is similar to the characteration of strategy-proofness in Mennle and Seuken (2021), we skip its proof.Footnote 12 The proof of Theorem 2 is based on Proposition 1 and the following lemma.
Lemma 1
Suppose Q mechanism is LROBIC with respect to a prior. Then, for every i, for every \(P_{-i}\), for every \(P_i\) and \(P'_i\) such that \(P'_i\) is an (a, b) swap of \(P_i\), we have
Proof
Pick an agent \(i \in N\) and \(P_i,P'_i \in {\mathcal {P}}\) such that \(P'_i\) is an (a, b)-swap of \(P_i\). Fix some \(P_{-i}\). By Proposition 1, Q satisfies interim upper invariance and interim lower invariance. Hence, we know that for all \(c \notin \{a,b\}\), we get
Since \(\mu \) is a probability distribution over \({\mathcal {P}}\), we can treat it as a vector in \({\mathbb {R}}^{n!-1}\). Using \(\mu (P_{-i}) \equiv \times _{j \ne i}\mu (P_j)\), we note that the LHS of the Equation (3) is a polynomial function of \(\{\mu (P)\}_{P \in {\mathcal {P}}}\). The equation describes the zero set of this polynomial function. For non-zero polynomials, the set of zeros has measure zero (Caron and Traynor 2005), i.e., the set of \(\mu \) satisfying Equation (3) has measure zero.Footnote 13 Hence, given any prior \(\mu ^*\) and \(\epsilon > 0\), if Equation 3 has to hold for all \(\mu \in B_{\epsilon }(\mu ^*)\) (which has non-zero measure), then \(Q_{ic}(P_i,P_{-i})=Q_{ic}(P'_i,P_{-i})\) for all \(c \notin \{a,b\}\). \(\square \)
We now complete the proof of Theorem 2.
Proof of Theorem 2
Proof: Every strategy-proof mechanism is OBIC with respect to any prior. A strategy-proof mechanism satisfies elementary monotonicity. So, we now focus on the other direction of the proof. Let Q be an LROBIC mechanism with respect to a prior \(\mu \). Suppose Q satisfies elementary monotonicity.
By Lemma 1, any LROBIC mechanism Q, Q satisfies ex-post versions of interim lower invariance and interim upper invariance. Mennle and Seuken (2021) refer to these properties as upper invariance and lower invariance (see also Cho 2018). They show that upper invariance, lower invariance, and elementary monotonicity are equivalent to strategy-proofness. By the assumption of the theorem, Q satisfies elementary monotonicity. Hence, it is strategy-proof. \(\square \)
We now explore the compatibility of LROBIC and ordinal efficiency.
Definition 10
A mechansim Q is ordinally efficient if at every preference profile \({\mathbf {P}}\) there exists no assignment L such that
with \(L_i \ne Q_i({\mathbf {P}})\) for some i.
Bogomolnaia and Moulin (2001) show that every ordinally efficient mechanism is ex-post efficient but the converse is not true if \(n \ge 4\). In fact, for \(n \ge 4\), strategy-proofness is incompatible with ordinally efficiency along with the following weak fairness criterion.
Definition 11
A mechanism Q satisfies equal treatment of equals if at every preference profile \({\mathbf {P}}\) and for every \(i,j \in N\), we have
Due to Theorem 2, we can strengthen the impossibility results in Bogomolnaia and Moulin (2001) and Mennle and Seuken (2017) as follows.
Corollary 2
Suppose \(n \ge 4\). Then, there is no locally robust OBIC and ordinally efficient mechanism satisfying equal treatment of equals.
Proof
By Lemma 1, a locally robust OBIC mechanism satisfies ex-post versions of upper invariance and lower invariance. Mennle and Seuken (2017) show that the proof in Bogomolnaia and Moulin (2001) can be adapted by replacing strategy-proofness with ex-post versions of upper invariance and lower invariance. Hence, these two properties are incompatible with ordinal efficiency and equal treatment of equals for \(n \ge 4\), and we are done. \(\square \)
Note that Corollary 2 does not use elementary monotonicity, and hence, cannot be directly inferred from Theorem 2.
Notes
Pycia and Ünver (2017) characterize the set of deterministic, strategy-proof, Pareto efficient, and non-bossy mechanisms in this model. This includes generalizations of the top-trading-cycle mechanism.
For instance, Bogomolnaia and Moulin (2001) show that the (uniform) random priority mechanism is ex-post efficient, strategy-proof and satisfies equal treatment of equals, but fails ordinal efficiency (which is stronger than ex-post efficiency).
Neutrality is a standard axiom in social choice theory which requires that objects are treated symmetrically. Elementary monotonicity is a monotonicity requirement of a mechanism. We define it formally in Sect. 4.
Katta and Sethuraman (2006) extend the simultaneous eating algorithm to allow for ties in preferences.
With three agent, the random priority mechanism satisfies these properties.
All our results extend even if the number of objects is not the same as the number of agents. We assume this only to compare our results with the random assignment literature, where this assumption is common.
Whenever we say an assignment, we mean a random assignment from now on.
The restriction to not consider cardinal mechanisms is arguably arbitrary. It is usually done to simplify the process of elicitation. Such restriction is also consistent with the literature on random assignment models. The set of incentive compatible mechanisms expand if we consider cardinal mechanisms (Miralles 2012; Abebe et al. 2020).
For three objects and three agents, we can show that the probabilistic serial mechanism cannot be OBIC with respect to a generic prior.
Note that we are not characterizing the set of \(\mu \) for which (3) has a solution. Our claim is only about the measure of the set of solutions.
References
Abebe R, Cole R, Gkatzelis V, Hartline JD (2020) A truthful cardinal mechanism for one-sided matching. In: Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, pp 2096–2113
Aziz H, Gaspers S, Mattei N, Narodytska N, Walsh T (2014) Strategic aspects of the probabilistic serial rule for the allocation of goods. arXiv preprint arXiv:1401.6523
Aziz H, Gaspers S, Mackenzie S, Mattei N, Narodytska N, Walsh T (2015) Equilibria under the probabilistic serial rule. arXiv preprint arXiv:1502.04888
Balbuzanov I (2016) Convex strategyproofness with an application to the probabilistic serial mechanism. Soc Choice Welf 46:511–520
Bergemann D, Morris S (2005) Robust mechanism design. Econometrica 73(6):1771–1813
Bhargava M, Majumdar D, Sen A (2015) Incentive-compatible voting rules with positively correlated beliefs. Theor Econ 10:867–885
Bogomolnaia A, Heo EJ (2012) Probabilistic assignment of objects: characterizing the serial rule. J Econ Theory 147:2072–2082
Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J Econ Theory 100:295–328
Bogomolnaia A, Moulin H (2002) A simple random assignment problem with a unique solution. Econ Theory 19:623–636
Caron R, Traynor T (2005) The zero set of a polynomial. University of Windsor, Technical Report
Che Y-K, Kojima F (2010) Asymptotic equivalence of probabilistic serial and random priority mechanisms. Econometrica 78:1625–1672
Cho WJ (2018) Probabilistic assignment: an extension approach. Soc Choice Welf 51:137–162
d’Aspremont C, Peleg B (1988) Ordinal Bayesian incentive compatible representations of committees. Soc Choice Welf 5:261–279
Ehlers L, Massó J (2007) Incomplete information and singleton cores in matching markets. J Econ Theory 136:587–600
Gibbard A (1973) Manipulation of voting schemes: a general result. Econometrica 41:587–601
Gibbard A (1977) Manipulation of schemes that mix voting with chance. Econometrica 45:665–681
Hashimoto T, Hirata D, Kesten O, Kurino M, Ünver MU (2014) Two axiomatic approaches to the probabilistic serial mechanism. Theor Econ 9:253–277
Hong M, Kim S (2018) Unanimity and local incentive compatibility. Working paper, Yonsei University
Katta A-K, Sethuraman J (2006) A solution to the random assignment problem on the full preference domain. J Econ Theory 131:231–250
Kojima F, Manea M (2010) Incentives in the probabilistic serial mechanism. J Econ Theory 145:106–123
Ledyard JO (1978) Incentive compatibility and incomplete information. J Econ Theory 18:171–189
Liu P (2020) Random assignments on sequentially dichotomous domains. Games Econ Behav 121:565–584
Liu P, Zeng H (2019) Random assignments on preference domains with a tier structure. J Math Econ 84:176–194
Majumdar D, Sen A (2004) Ordinally Bayesian incentive compatible voting rules. Econometrica 72:523–540
Mennle T, Seuken S (2017) Two new impossibility results for the random assignment problem. Working paper, University of Zurich. https://www.ifi.uzh.ch/ce/publications/IPS.pdf
Mennle T, Seuken S (2021) Partial strategyproofness: relaxing strategyproofness for the random assignment problem. J Econ Theory 191:105144
Miralles A (2012) Cardinal Bayesian allocation mechanisms without transfers. J Econ Theory 147:179–206
Mishra D (2016) Ordinal Bayesian incentive compatibility in restricted domains. J Econ Theory 163:925–954
Pycia M, Ünver MU (2017) Incentive compatible allocation and exchange of discrete resources. Theor Econ 12:287–329
Satterthwaite MA (1975) Strategy-proofness and Arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions. J Econ Theory 10:187–217
Wilson R (1987) Game theoretic approaches to trading processess. In: Bewley T (ed) Advances in economic theory: fifth world congress of econometric society. Cambridge University Press, Cambridge, pp 201–213
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
We are grateful to an anonymous referee, Sven Seuken, Timo Mennle, Arunava Sen, Dipjyoti Majumdar, Souvik Roy, and Wonki Cho for their comments.
Rights and permissions
About this article
Cite this article
Dasgupta, S., Mishra, D. Ordinal Bayesian incentive compatibility in random assignment model. Rev Econ Design 26, 651–664 (2022). https://doi.org/10.1007/s10058-022-00289-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10058-022-00289-4