Discussion Paper No. 916

A FOUNDATIONFOR DOMINANT STRATEGYVOTING MECHANISMS

Debasis Mishra

November 2014

The Institute of Social and Economic Research
Osaka University
6-1 Mihogaoka, Ibaraki, Osaka 567-0047, JapanA Foundation for Dominant Strategy
Voting Mechanisms ∗Debasis Mishra †October 15, 2014

Abstract
We study deterministic voting mechanisms by considering an ordinal notion ofBayesian incentive compatibility (OBIC). If the beliefs of agents are independent andgeneric, we show that any OBIC mechanism is dominant strategy incentive compatible
under an additional mild requirement. Our result works in a large class of preference
domains (that include the unrestricted domain, the single peaked domain, a specificclass of single crossing domains) and under a weaker notion of OBIC that we call locally
OBIC. We also discuss the implications of assuming unanimity on our results.

∗

I am grateful to Dipjyoti Majumdar, Benny Moldovanu, Anup Pramanik, Arunava Sen, and seminar
participants at the Osaka University for helpful comments and suggestions. Parts of this research was carriedout when I was visiting Institute of Social and Economic Research (ISER) at Osaka University. I am gratefulfor the hospitality and support provided by ISER, Osaka University.
†
Indian Statistical Institute, Delhi. Email: dmishra@isid.ac.in.

11Introduction

Dominant strategy incentive compatible (DSIC) mechanisms play a central role in the theoryof mechanism design. Among other things, such mechanisms enjoy a strong robustness feature due to their prior-free property. Unfortunately, in voting environments, DSIC turns out
to be too demanding. In particular, the seminal Gibbard-Satterthwaite theorem (Gibbard,
1973; Satterthwaite, 1975) shows that the only deterministic dominant strategy incentive
compatible (DSIC) voting mechanism satisfying unanimity is a dictatorship if there are atleast three alternatives. A crucial assumption in this result is that the domain (of preferences of agents) must be unrestricted. A large body of literature in social choice theory has
tried to relax the assumption of unrestricted domain in the Gibbard-Satterthwaite theorem,
while still working with deterministic DSIC mechanisms. This has led to various (possibility)
characterizations of DSIC mechanisms in restricted domains - an excellent survey is Barbera(2010).
A natural question to ask is if there is any loss of generality in not considering a weakersolution concept in such voting environments that can depend on the priors of the agents the most prominent such solution concept being the Bayes-Nash equilibrium. d’Aspremontand Peleg (1988) introduced the notion of ordinal Bayesian incentive compatibility (OBIC)in this context. OBIC is a natural weakening of DSIC to ordinal voting mechanisms. A
voting mechanism is OBIC if for every agent, his interim/expected allocation probability
vector from truth-telling first-order-stochastic-dominates any interim allocation probability
vector obtained by deviating. This notion is equivalent to requiring that the expected utility
from truth-telling must be no less than the expected utility from deviating for all possible
utility representation of the ordinal preference of the agent.
Our main result shows that if the priors of the agents are independent and generic, then ina large class of domains, an ordinal deterministic mechanism is OBIC and satisfies elementary
monotonicity if and only if it is a DSIC mechanism. 1 This result holds even if we weaken
OBIC to only allow manipulations of each agent to his adjacent preferences - we call thisrequirement locally OBIC (LOBIC). Notice that the result does not require unanimity or any
restriction on number of alternatives. Our result establishes a strong robustness property of
DSIC mechanisms in voting environments.
We call the domains where our main result holds local domains. A domain is local ifevery locally dominant strategy incentive compatible mechanism is a DSIC mechanism. Tworecent papers by Carroll (2012) and Sato (2013) give a comprehensive description of domainsthat are local. Some of the prominent domains identified in these papers are the unrestricteddomain, the single peaked domain (Moulin, 1980), and a particular class of single crossing
1

We discuss elementary monotonicity and generic priors later.

2

domains (Carroll, 2012; Saporiti, 2009). An implication of our result is that in all these
domains, any locally OBIC mechanism (with respect to independent generic prior) satisfying
elementary monotonicity must be a DSIC mechanism.
The proof of our main result reveals another surprising fact. In any domain, locally
OBIC with respect to independent generic priors and elementary monotonicity implies locallyDSIC. This shows that if we only care about designing mechanisms that satisfy local incentive
constraints, then our main result is true in any domain. 2
Majumdar and Sen (2004) investigated OBIC mechanisms in the unrestricted domain.
They assumed that agents have independent priors. If these are uniform priors, then theyshow that a large class of interesting non-dictatorial social choice functions are OBIC in
the unrestricted domain. However, if the priors are generic, then the negative result in the
Gibbard-Satterthwaite theorem persists: if there are at least three alternatives and priors are
generic, then in the unrestricted domain, a deterministic unanimous OBIC mechanism is a
dictatorship. We can reinterpret this result as follows. If there are at least three alternatives
and the priors are generic, then in the unrestricted domain, a unanimous OBIC mechanism
is a DSIC mechanism. Our results generalize this interpretation of their result. Notice that
our result works in a large class of domains and uses elementary monotonicity while theirgenericity result is for the unrestricted domain and uses unanimity.
We show that the conclusion in the Majumdar and Sen (2004) result (using unanimity)
crucially relies on the unrestricted domain assumption, and it may not extend to restricteddomains. In particular, we construct a non-DSIC unanimous mechanism that is OBIC withrespect to some generic priors when the domain of preferences is restricted to be the single
peaked domain - this mechanism works even if there are only two alternatives.
However, we note that such OBIC mechanisms violate elementary monotonicity. Elementary monotonicity is a well-studied axiom in social choice theory (Moulin, 1983). It
requires the following. Suppose agent i has a preference Pi where a is ranked just above
b and consider a preference profile P−i of other agents such that the mechanism chooses bat the profile (Pi , P−i ). Now, suppose agent i reports another preference Pi0 where only the
positions of a and b are swapped from Pi (maintaining the positions of other alternatives).
Elementary monotonicity requires that the outcome at the new profile (Pi0 , P−i ) must be b.
Since our result seems to restore the genericity result of Majumdar and Sen (2004) in alarge class of domains by replacing unanimity with elementary monotonicity, it is natural
to ask if elementary monotonicity is too strong a condition. As noted in Moulin (1983) andMajumdar and Sen (2004), it is satisfied by many well known social choice functions. 3 For
2Carroll (2012) and Sato (2013) contain extensive discussions motivating mechanism design with local
incentive compatibility.
3
We use the terms social choice function and mechanism interchangeably throughout the paper.

3

instance, the well known scoring rules like the Borda and the plurality rules satisfy elementary
monotonicity. Further, in the unrestricted domain with at least three alternatives, we showthat LOBIC with generic priors and unanimity imply elementary monotonicity. This leads
to an immediate strengthening of the result in Majumdar and Sen (2004) as we can now
replace their OBIC requirement by the weaker LOBIC: in the unrestricted domain with atleast three alternatives, a unanimous and LOBIC mechanism is a DSIC mechanism if thepriors are independent and generic. Further, it shows that our main result using elementary
monotonicity is stronger than their result.
In the single peaked domain, we introduce a significantly weaker condition than elementary monotonicity that we call weak elementary monotonicity. We show that in that domain,
every unanimous and LOBIC (with respect to independent generic priors) mechanism satisfying weak elementary monotonicity must be a DSIC mechanism. This illustrates that in
specific restricted domains, we can replace elementary monotonicity in our result by a weakerversion of elementary monotonicity if we assume unanimity.
Interestingly, when agents have uniform priors (a non-generic prior), Majumdar and Sen(2004) show that every neutral social choice function satisfying elementary monotonicity is
OBIC in the unrestricted domain. Since neutrality is also a relatively weak requirement,
it shows that a large class of non-DSIC mechanisms are OBIC with uniform priors in theunrestricted domain. 4 Our result shows two very different implications of elementary monotonicity with generic priors and uniform priors.
In summary, our results suggest that as far as ordinal deterministic mechanisms areconcerned, there is no loss of generality in focusing attention to DSIC mechanisms (underelementary monotonicity) in many domains. However, the nature of equivalence is nuanced.
Our results parallel recent contributions in the single object auction quasilinear utility
models (and some of its extensions) by Manelli and Vincent (2010) and Gershkov et al.
(2013) who establish a weaker version of equivalence between Bayesian incentive compatible
and DSIC mechanisms. We discuss the precise connection between these results and ours
later in the paper.
Our results suggest that if we want to expand the set of incentive compatible mechanisms,
then we need to go beyond OBIC deterministic mechanisms, and consider cardinal and/or
randomized voting mechanisms. A small literature (Borgors and Smith, 2014; Kim, 2014) instrategic voting considers the consequences of using cardinal mechanisms with Bayesian incentive compatibility. These papers also consider randomization and work in the unrestricteddomain. In such cardinal environment, type of an agent is a von-Neumann-Morgenstern utility function over alternatives. They compare the interim expected utilities of agents fromthese mechanisms to DSIC mechanisms. While Borgors and Smith (2014) show that such
4

In Section 6, we illustrate that this result may no longer be true in the restricted domain.

4

mechanisms improve upon the random cardinal DSIC mechanisms, Kim (2014) shows thatsuch mechanisms improve upon the ordinal BIC mechanisms. 5 Along with these results,
our results help to delineate the boundaries of OBIC and DSIC equivalence in voting environments.
OBIC mechanisms have been studied in the context of matching problems in Majumdar(2003); Ehlers and Masso (2007). These papers study the implication of stability and OBICin two-sided matching problems. The general conclusion in these papers is that stability and
OBIC are too restrictive in the two-sided matching problems. Though our main result canbe applied in private good allocation problems like the matching problems (by suitably redefining the notations and definitions), elementary monotonicity is a condition used in voting
environment. Since we use elementary monotonicity in our main result, and its implicationsin private good problems is not very clear, we restrict ourselves to voting problems.
The rest of the paper is organized as follows. We introduce our model and assumptions
about beliefs in Section 2. In Section 3, we formally state the result of Majumdar and Sen(2004) and show how this result breaks down if we consider a model with two alternatives
or restrict the domain to the single peaked domain. Section 4 presents our main result
and its proof. In Section 5, we show how our main result changes in specific domains if
we restrict attention to unanimous social choice functions. We discuss several extensions
and implications of our result in Section 6. Finally, we conclude in Section 7. Appendix
A contains all the omitted proofs and Appendix B contains some omitted examples andillustrations.

2

The Model

Let A be a finite set of alternatives and P be the set of all strict linear orders over A. Let
D ⊆ P be some subset of strict linear orders. We will refer to D as the domain. There aren agents. The set of agents is denoted by N = {1, . . . , n}. The private preference (type) of
each agent i ∈ N is a strict linear order Pi ∈ D.
A social choice function (scf) is a map f : Dn → A.
Definition 1 An scf f : Dn → A is dominant strategy incentive compatible (DSIC)
if for every i ∈ N , every P−i , and every Pi ∈ D, there exists no Pi0 ∈ D such thatf (Pi0 , P−i )Pi f (Pi , P−i ).
5

Kim (2014) also considers OBIC deterministic mechanisms in the single peaked domain. He showsthat such OBIC mechanisms satisfying unanimity must be peaks only. However, he has no results on theequivalence between OBIC and DSIC mechanisms.

5

We now define the notion of ordinal Bayesian incentive compatiblity. For this, we need toPdefine beliefs. A belief for agent i is a mapping βi : Dn → [0, 1] such that P∈Dn βi (P) = 1.
Throughout the paper, we will assume that agents have common belief, i.e., βi = βj for alli, j ∈ N . Denote this common belief as β. For every agent i ∈ N and every agent P−i , denotethe conditional belief of agent i that others have preferences P−i when he has preference Pi
as β(P−i |Pi ).
We will also assume that beliefs are independent, i.e., for every agent i ∈ N , there
exists a probability distribution µi : D → [0, 1] such that for every P−i ∈ Dn , the conditional
belief that agents other than i have preference P−i when i has preference Pi isβ(P−i |Pi ) = ×j6=i µj (Pj ).
Since we will only deal with common and independent beliefs, we will assume that theunderlying probability distributions of agents are {µi }i∈N , and refer to them as priors ofagents. Further, for agent i, the probability that agents other than i have a type profile P−iwill be denoted as µ(P−i ) ≡ ×j6=i µj (Pj ).
Given a social choice function f , we can compute the interim allocation probability ofeach agent from this scf using the priors. For this, consider a profile of priors {µi }i∈N . For
each agent i ∈ N , define πif (a, Pi ) as the interim allocation probability of the scf f choosing
alternative a when agent i reports Pi as his type:X
πif (a, Pi ) =µ(P−i ).
P−i ∈Dn−1 :f (Pi ,P−i )=a

Note that πif depends on the priors, but we have suppressed it to make the notation lesscomplex.
A utility function is a map u : A → R. A utility function u represents a preference
ordering P if for all a, b ∈ A, u(a) > u(b) if and only if aP b. Denote the set of all utility
functions representing a preference ordering P as U(P ).
We are now ready to define the notion of ordinal Bayesian incentive compatibility. It was
introduced to the literature by d’Aspremont and Peleg (1988).
Definition 2 An scf f is ordinally Bayesian incentive compatible (OBIC) with respect to profile of priors {µi }i∈N if for every i ∈ N , for every Pi , Pi0 ∈ D, for every u ∈ U(Pi ),we haveXXu(a)πif (a, Pi ) ≥u(a)πif (a, Pi0 ).
a∈A

a∈A

An equivalent definition using first order stochastic dominance can also be given. For
any alternative a ∈ A and any Pi ∈ D, let B(a, Pi ) := {a} ∪ {b ∈ A : bPi a}.
6

Definition 3 An scf f is ordinally Bayesian incentive compatible (OBIC) with respect to profile of priors {µi }i∈N if for every i ∈ N , for every Pi , Pi0 ∈ D, and for everya ∈ A, we haveXX
πif (b, Pi ) ≥πif (b, Pi0 ).
b∈B(a,Pi )b∈B(a,Pi )OBIC is clearly a weakening of DSIC. A well known fact to note is that if an scf is OBIC
with respect to all beliefs, then it is DSIC.

2.1 Generic Priors and G-OBIC
We make the following assumption about generic priors in the paper.
Definition 4 The profile of priors {µi }i∈N is generic if for every j ∈ N and for every
S, T ⊆ Dn−1 we haveX
 Xµ(P−j ) ⇔ [S = T ].
µ(P−j ) =P−j ∈SP−j ∈T

Genericity requires that if we consider an agent i and consider two distinct subsets ofprofiles of types of agents in N \ {i}, then the probability that agents in N \ {i} have types
in these subsets cannot be the same.
Mathematically, these priors are generic in a topological sense. Denote by ∆ the unit
simplex of dimension |D| − 1. The set of common independent beliefs is the n-th order
Cartesian product of unit simplices ∆, and is given by ∆n . The set of priors ruled out bygenericity are given by equations that define a finite set of hyperplanes in ∆n . Excludingthese hyperplanes excludes only a set of Lebesgue measure zero in ∆n . Hence, the generic
beliefs identified in Definition 4 is a generic (in a topological sense) subset of ∆n , i.e., adense subset of the set of all common independent beliefs whose complement has measurezero (Majumdar and Sen, 2004) - to be precise, Majumdar and Sen (2004) show this fact
when D = P, but an identical proof works if D ⊆ P. Notice that generic priors require thatagents must be ex-ante asymmetric, i.e., for any i, j ∈ N , µi 6= µj .
If we consider any prior over D ( P, it also defines a prior over P. Then, we can imagine∆ to be a unit simplex of dimension |P| − 1. Obviously, such priors define beliefs that haveLebesgue measure zero in this extended simplex. Hence, our set of generic priors is not
generic if we extend it to P and then consider its genericity.
One notable prior that is not generic is the uniform prior.
Definition 5 A profile of independent priors {µi }i∈N are uniform priors if for every i ∈N , for every Pi , Pi0 ∈ D, we haveµi (Pi ) = µi (Pi0 ).
7

We will discuss the implications of using uniform priors later and assume for the moment
generic priors.
Definition 6 An scf f is G-OBIC if there exist some profile of generic priors {µi }i∈Nsuch that f is OBIC with respect to {µi }i∈N .
An important point to remember is that G-OBIC requires OBIC with respect to some profile
of generic priors (it may be just one profile of generic priors), but not all profile of genericpriors. For instance, an scf may be OBIC with respect to uniform priors, but it can still be
G-OBIC if it is OBIC with respect to some profile of generic priors.

3

Equivalence of G-OBIC and DSIC under Unanimity

We now discuss the implication of G-OBIC along with unanimity. Initially, we discuss this
implication in the unrestricted domain. To do so, we need the following standard definition ofunanimity. At any preference ordering P , we will denote by P (k) the k-th ranked alternative
according to P .
Definition 7 An scf f : Dn → A is unanimous if for every P ≡ (P1 , . . . , Pn ) withP1 (1) = . . . = Pn (1), we have f (P) = P1 (1).
An scf f is a dictatorship if there exists an agent (called the dictator) i such that for every
P ∈ Dn , f (P) = Pi (1). Gibbard (1973) and Satterthwaite (1975) showed that if |A| ≥ 3 and
D = P, then an scf is DSIC and unanimous if and only if it is a dictatorship. The following
result from Majumdar and Sen (2004) extends the Gibbard-Satterthwaite theorem in theunrestricted domain.
Theorem 1 (Majumdar and Sen (2004)) Let |A| ≥ 3 and f : P n → A be a unanimous
scf, where P is the unrestricted domain. Then, f is G-OBIC if and only if it is DSIC.
We must point out that the proof in Majumdar and Sen (2004) is direct. Instead of showing that every unanimous and G-OBIC mechanism is DSIC, and then using the GibbardSatterthwaite theorem to conclude dictatorship, they directly prove that G-OBIC and unanimity imply dictatorship. Hence, one does not obtain any intuition from their proof whether
Theorem 1 will hold in other domains.
We now show how relaxing the assumptions in Theorem 1 alters the equivalence between
G-OBIC and DSIC.

8

3.1 Two Alternatives
We start off by giving an example of an scf with two alternatives and three agents which isunanimous and G-OBIC but not DSIC. This shows that Theorem 1 fails if |A| = 2.
Example 1 Let A = {a, b} and N = {1, 2, 3}. The scf f we consider is defined below
formally. If all the agents have the same top ranked alternative, then f picks that alternative.
Else, f picks the alternative which is top ranked for less number of agents.
Formally, given a preference profile P ≡ (P1 , P2 , P3 ), alternative a is the loser at P if|{i ∈ N : bPi a}| > |{i ∈ N : aPi b}|. Else, b is the loser at P. Since there are odd number of
agents, the loser is well defined. We denote the loser at profile P as κ(P).
Now, the scf f¯ is defined as follows. For any preference profile P ≡ (P1 , P2 , P3 ), define(
P1 (1) if P1 (1) = P2 (1) = P3 (1)f¯(P) =
κ(P) otherwise
Clearly, f¯ is unanimous. We next argue that f¯ is G-OBIC. Since there are only two¯¯
alternatives, we only need to show that πif (Pi (1), Pi ) ≥ πif (Pi (1), Pi0 ) for all i ∈ N , for all
Pi , Pi0 . For simplicity, for every agent i ∈ N , we will denote the preference ordering where ais top ranked as Pi and the preference ordering where b is top ranked as Pi0 . For every i ∈ N ,let the probability that agent i has type Pi be pi and the probability that he has type Pi0 be(1 − pi ). Now, we can compute the interim allocation probabilities for agent 1 as follows.
If agent 1 has type P1 (where a is top ranked), then the probability that b will be theoutcome in f¯ is the probability that agents 2 and 3 have different types. This probability isexactly p2 (1 − p3 ) + p3 (1 − p2 ) = p2 + p3 − 2p2 p3 . Hence, if agent 1 has type P1 , then theprobability that a will be the outcome in f¯ is 1 − p2 − p3 + 2p2 p3 . An analogous calculation
can be used to compute interim allocation probabilities when agent 1 has type P10 . This issummarized in Table 1.
¯
π1f (a, ·)¯
π1f (b, ·)P1
1 − p2 − p3 + 2p2 p3
p2 + p3 − 2p2 p3

P10
p2 + p3 − 2p2 p3
1 − p2 − p3 + 2p2 p3

Table 1: Interim allocation probabilities of agent 1 in f¯
The interim allocation probabilities of agents 2 and 3 can be computed in an analogous
manner. It is easily seen from Table 1 that OBIC constraints can be satisfied for agent 1
if and only if 1 − p2 − p3 + 2p2 p3 ≥ p2 + p3 − 2p2 p3 , which is equivalent to requiring that
(1 − 2p2 )(1 − 2p3 ) ≥ 0. Collecting the OBIC constraints for all agents, we can then conclude
9

that f¯ is OBIC if and only if priors satisfy(1 − 2p2 )(1 − 2p3 ) ≥ 0(1 − 2p1 )(1 − 2p3 ) ≥ 0(1 − 2p1 )(1 − 2p2 ) ≥ 0This is possible if and only if either p1 , p2 , p3 ∈ (0, 0.5) or p1 , p2 , p3 ∈ (0.5, 1). To see why
p1 , p2 , p3 can be picked such that the priors become generic, note that the set of priors
satisfying either p1 , p2 , p3 ∈ (0, 0.5) or p1 , p2 , p3 ∈ (0.5, 1) is a subset of (0, 1)3 with a nonempty interior. Hence, it will have a non-empty intersection with the set of generic priors. 6
This example also illustrates that Theorem 1 is not true if we do not assume unanimity.
This is because even when there are more than three alternatives we can define the scf f¯ byconsidering any two alternatives a, b ∈ A. Such an scf will not be unanimous any more (withrange two), but it will be G-OBIC.

3.2 Single Peaked Domain
We now consider the single peaked domain which is a smaller domain than the unrestricteddomain. Single peaked domain is an important domain restriction in strategic voting literature with applications in political economy and other disciplines. It is a domain where
existence of anonymous, unanimous, and DSIC scfs is guaranteed (Moulin, 1980), and thus,
allows one to escape the negative consequences of the Gibbard-Satterthwaite theorem.
In this domain, we give an example of an scf with three alternatives and three agentsthat is G-OBIC, unanimous, anonymous but not DSIC. 7
The single peaked domain is defined as follows. Let  be a strict linear order of the setof alternatives A.
Definition 8 A preference ordering P is single peaked with respect to  if for every b, c ∈ Awith P (1)  b  c or c  b  P (1), we have bP c.
Our scf in this domain is an extension of the scf we considered for the two alternatives
case. We assume that A = {a, b, c} and N = {1, 2, 3} - we will later clarify why at least
three agents are required. Suppose the preferences are single peaked with respect to thestrict linear order  given by a  b  c. The set of all single peaked preference orderings
with respect to  is denoted by S. For this example, the domain S is shown in Table 2,
where each column is a preference in S. Before defining the scf, we note that a and b are the6

For instance, one can verify that p1 = 0.49, p2 = 0.47, p3 = 0.43 results in generic priors.
Informally, anonymity requires that if we permute the preferences of agents and consider the new profile
of preferences, the outcome at the new profile must be the same as the old one.
7

10

a
b
c

b
a
c

b
c
a

c
b
a

Table 2: The single peaked domain
two “left-most” alternatives in . Our scf considers the number of agents who prefer a to b
and the number of agents who prefer b to a. We say a is a loser in {a, b} at P if|{i ∈ N : aPi b}| < |{i ∈ N : bPi a}|.
Else, we say b is a loser in {a, b} at P. We denote by κa,b (P) the loser in {a, b} at P.
Now, the scf f ∗ is defined as follows. For any preference profile P ∈ S 3 , defineP1 (1)
if P1 (1) = P2 (1) = P3 (1)



 a
if ¬(P1 (1) = P2 (1) = P3 (1)) and aPi b for all i ∈ N
f ∗ (P) =bif ¬(P1 (1) = P2 (1) = P3 (1)) and bPi a for all i ∈ N


 a,b
κ (P) otherwise,
where we used the notaion ¬(P1 (1) = P2 (1) = P3 (1)) to mean that the top ranked alternativesof agents are not the same (“logical not” operation). The following proposition shows thatf ∗ is G-OBIC.
Proposition 1 The scf f ∗ is unanimous, anonymous, and G-OBIC, but not DSIC.
The proof of Proposition 1 is given in Appendix A. It builds on the ideas developed in theprevious section for establishing f¯ as a G-OBIC scf.

4

Equivalence of Locally G-OBIC and DSIC Mechanisms

Although we constructed a non-DSIC scf f ∗ in the single peaked domain and showed it to
be unanimous and G-OBIC in Proposition 1, we would now like to point out that f ∗ violatesa mild monotonicity property. Consider the profiles of preferences shown in Table 3. By
definition, f ∗ (P1 , P2 , P3 ) = b and f ∗ (P10 , P2 , P3 ) = a. Notice that the preferences of agents
2 and 3 did not change across the two profiles. Moreover, the only change in agent 1’s
preference is that a and b swapped their positions: a is top ranked and b second ranked in
P1 and b becomes top ranked and a second ranked P10 . This means, even though the positionof b improves in agent 1’s ranking and the scf was picking b in the starting profile, the scf
does not pick b any more. We call this violated property elementary monotonicity. We show
below that if a unanimous and G-OBIC scf is not DSIC, then it must fail this property in alarge class of domains.
11

P1
a
b
c

P2
a
b
c

P10
b
a
c

P3
b
a
c

P2
a
b
c

P3
b
a
c

Table 3: Violation of elementary monotonicity by f ∗To define elementary monotonicity formally, we introduce some notation. Consider anagent i and two alternatives a, b ∈ A. Suppose Pi is a preference ordering such that Pi (k) = a
and Pi (k + 1) = b. Now, consider Pi0 such that Pi0 (k + 1) = a, Pi0 (k) = b, and Pi0 (j) = Pi (j)for all j ∈/ {k, k + 1}. In other words, a and b are consecutively ranked in Pi , and Pi0 is
constructed by swapping only their positions. In this case, we say that Pi0 is a (a, b)-swapof Pi . Note that if Pi0 is an (a, b)-swap of Pi , then the position of b improves from Pi to Pi0 .
Hence, (a, b)-swap is different from (b, a)-swap.
Definition 9 An scf f satisfies elementary monotonicity if for every i ∈ N , every
P−i ∈ Dn−1 , and every Pi , Pi0 ∈ D such that Pi0 is a (a, b)-swap of Pi for some a, b ∈ A andf (Pi , P−i ) = b, we have f (Pi0 , P−i ) = b.
As discussed earlier, a large class of scfs satisfy elementary monotonicity. Moulin (1983)
contains an extensive discussion on the scfs that satisfy elementary monotonicity - see also
Majumdar and Sen (2004). Notable examples include all the scoring rules (like Borda rule,
plurality rule) and all the Condorcet rules (rules that pick the majority winner whenever it
exists, e.g., the Kramer rule, the Copeland rule, the Top-cycle rule, the uncovered set rule).
We now define the class of restricted domains we consider. For this, we first introduce
the notion of local incentive compatibility.
Definition 10 An scf f is locally dominant strategy incentive compatible (LDSIC)
if for every i ∈ N , every P−i ∈ Dn−1 , and every Pi ∈ D there exists no Pi0 ∈ D such that Pi0
is an (a, b)-swap of Pi for some a, b ∈ A andf (Pi0 , P−i )Pi f (Pi , P−i ).
Local DSIC only prevents manipulations across types which are swaps of each other.
Using the notion of LDSIC, we now define a class of domains.
Definition 11 A domain D is a local domain if every LDSIC f : Dn → A in that domain
is also DSIC.
The role of local domain and related discussions are done after we state our main result. To
be able to state our main result, we need to define a local version of OBIC.
12

Definition 12 An scf f is locally ordinally Bayesian incentive compatible (LOBIC) with respect to profile of priors {µi }i∈N if for every i ∈ N , for every Pi , Pi0 ∈ D suchthat Pi0 is an (x, y)-swap of Pi for some x, y ∈ A, and for every a ∈ A, we haveXb∈B(a,Pi )X

πif (b, Pi ) ≥πif (b, Pi0 ).

b∈B(a,Pi )An scf f is G-LOBIC if there exists some profile of generic priors {µi }i∈N such that f is
LOBIC with respect to {µi }i∈N .
Clearly, if f is OBIC, then it is also LOBIC. In general, LOBIC is a very weak incentive
compatibility requirement since it requires only a small subset of incentive constraints tohold. Further, LOBIC may not imply OBIC even in the local domain - local domain only
requires that LDSIC implies DSIC. We now state the main result of the paper.
Theorem 2 Suppose D is a local domain and f : Dn → A is an scf on this domain. Then,the following statements are equivalent.
1. f is G-LOBIC and satisfies elementary monotonicity.
2. f is DSIC.
Note that Theorem 2 does not assume unanimity. It also does not require any conditionon the range of the scf. Before giving the proof of Theorem 2, we make some remarks.
• G-LOBIC and LDSIC. The proof of Theorem 2 reveals another interesting result.
In any domain D, G-LOBIC and elementary monotonicity are equivalent to LDSIC see Lemma 2 in the proof of Theorem 2 below. The proof of Theorem 2 then follows
by the definition of local domain. Thus, if we use local incentive constraints, then our
main result becomes very strong since it works in any domain of preferences.
• Which domains are local? There are two recent papers that identify many interesting local domains. Sato (2013) identifies necessary and sufficient conditions for adomain to be a local domain. One of his sufficient conditions is a minimal connectedness property that requires that we should be able to go from one preference ordering
to another in a domain by performing swaps in a “minimal” way - we refer the reader
to Sato (2013) for details. 8 He shows that this necessary condition is satisfied by theunrestricted domain and the single peaked domain. His condition also holds in some
generalizations of the single
8

The proof of Theorem 4 discusses these conditions in some detail.

13

Carroll (2012) considers the same question, but his results are slightly general since heallows his scfs to be randomized (Sato (2013), like us, restricts attention to deterministicscfs). He identifies specific domains that are local - they include the unrestricteddomain, the single peaked domain, and the successive single crossing domain. 9
These papers show that there are important restricted domains, like the single peakeddomain and the single crossing domain, that are local. 10 However, there are local
domains not covered in these papers, and our result works in those domains too.
• Elementary monotonicity and uniform priors. Elementary monotonicity plays
an important role in the analysis of OBIC scfs with uniform priors and correlated priors. Majumdar and Sen (2004) show that when agents have uniform priors, every
neutral scf satisfying elementary monotonicity is OBIC in the unrestricted domain we discuss this result further in Section 6. Thus, they show that a large class of scfs
that are not DSIC are OBIC with uniform priors in the unrestricted domain. A similar
result is shown with correlated priors in Bhargava et al. (2014). Theorem 2 shows thatelementary monotonicity brings us back to DSIC scfs under independent generic priors
in a large class of domains. We will also show later that in the unrestricted domain, elementary monotonicity is weaker than unanimity for a G-LOBIC scf. Hence, Theorem
2 is a stronger than Theorem 1 in the unrestricted domain.
• Independence of G-LOBIC and elementary monotonicity. The scf f ∗ discussed in Proposition 1 is an example of an scf that satisfies G-LOBIC but fails elementary monotonicity. Hence, we cannot hope to drop elementary monotonicity in
Theorem 2. However, we will show later that we can replace elementary monotonicity
with other properties in specific domains. In particular, unanimity and G-LOBIC will
imply DSIC in the unrestricted domain and a significantly weaker version of elementary
monotonicity along with unanimity will work in the single peaked domain.

4.1 Proof of Theorem 2
The proof is done by establishing two important lemmas. We start by identifying a property
that is implied by G-LOBIC.
Definition 13 An scf f satisfies swap monotonicity if for every i ∈ N , for every Pi , Pi0 ∈D, where Pi0 is an (a, b)-swap of Pi , we have for every P−i ∈ Dn−1 ,9For a definition and analysis of the single crossing domain, see Saporiti (2009). Successive single crossing
is a class of single crossing domains identified in Carroll (2012).
10
A prominent example of a domain that is not local is the multidimensional separable domain studied in
Barbera et al. (1993); Le Breton and Sen (1999).

14• f (Pi0 , P−i ) = f (Pi , P−i ) if f (Pi , P−i ) ∈/ {a, b},• f (Pi0 , P−i ) ∈ {a, b} if f (Pi , P−i ) ∈ {a, b}.
Our first claim shows the necessity of swap monotonicity.
Lemma 1 If an scf is G-LOBIC, then it satisfies swap monotonicity.
Proof : Let f be an LOBIC scf with respect to independent generic priors {µi }i∈N . For
this, consider agent i ∈ N , and pick two preference orderings Pi and Pi0 such that Pi0 is an(a, b) swap of Pi . By definition Pi (k) = a, Pi (k + 1) = b and Pi0 (k + 1) = a, Pi0 (k) = b forsome k and Pi (j) = Pi0 (j) for all j ∈/ {k, k + 1}. We will do the proof in three steps.
Step 1. Consider an alternative x ∈ A \ {a, b} such that Pi (k 0 ) = Pi0 (k 0 ) = x, where k 0 < k.
We will show that {P−i ∈ Dn−1 : f (Pi , P−i ) = x} = {P−i ∈ Dn−1 : f (Pi0 , P−i ) = x}. We
do this using induction on k 0 . If k 0 = 1, by observing that Pi (k 00 ) = Pi0 (k 00 ) for all k 00 < k,
LOBIC implies thatX
Xµ(P−i )µ(P−i ) ≥P−i :f (Pi ,P−i )=Pi (1)P−i :f (Pi0 ,P−i )=Pi (1)X

Xµ(P−i ) ≥P−i :f (Pi0 ,P−i )=Pi0 (1)Combining these inequalities, we getXµ(P−i ).

P−i :f (Pi ,P−i )=Pi0 (1)µ(P−i ) =Xµ(P−i ).

P−i :f (Pi0 ,P−i )=Pi (1)P−i :f (Pi ,P−i )=Pi (1)Since priors are generic, we get that
{P−i : f (Pi , P−i ) = Pi (1)} = {P−i : f (Pi0 , P−i ) = Pi (1)}.
Now, suppose the claim is true for all k 00 < k 0 . Notice that the top k 0 alternatives in Pi andPi0 are the same - denote this set as B. Now, we apply LOBIC to top k 0 alternatives in Pi
and Pi0 to getXXµi (P−i ) ≥µi (P−i )P−i :f (Pi ,P−i )∈B

P−i :f (Pi0 ,P−i )∈BXXµi (P−i ) ≥P−i :f (Pi0 ,P−i )∈Bµi (P−i ).

P−i :f (Pi ,P−i )∈B

Using genericity of µi gives us{P−i : f (Pi , P−i ) ∈ B} = {P−i : f (Pi0 , P−i ) ∈ B}.
15

Using the induction hypothesis, we have for all k 00 < k 0 ,{P−i : f (Pi , P−i ) = Pi (k 00 )} = {P−i : f (Pi0 , P−i ) = Pi (k 00 )}.
Hence, we get{P−i : f (Pi , P−i ) = Pi (k 0 )} = {P−i : f (Pi0 , P−i ) = Pi (k 0 )}.
Step 2. In this step, we show that {P−i : f (Pi , P−i ) ∈ {a, b}} = {P−i : f (Pi0 , P−i ) ∈ {a, b}}.
Applying LOBIC, we getXXµi (P−i ) ≥µi (P−i )P−i :f (Pi ,P−i )∈B(b,Pi )P−i :f (Pi0 ,P−i )∈B(b,Pi )X

Xµi (P−i ) ≥P−i :f (Pi0 ,P−i )∈B(a,Pi0 )µi (P−i ).

P−i :f (Pi ,P−i )∈B(a,Pi0 )Since B(b, Pi ) = B(a, Pi0 ), by genericity we get{P−i : f (Pi , P−i ) ∈ B(b, Pi )} = {P−i : f (Pi0 , P−i ) ∈ B(b, Pi )}.
By Step 1, this implies that {P−i : f (Pi , P−i ) ∈ {a, b}} = {P−i : f (Pi0 , P−i ) ∈ {a, b}}.
Step 3. Consider an alternative x ∈ A \ {a, b} such that Pi (k 0 ) = Pi0 (k 0 ) = x, wherek 0 > k + 1. Using the facts in Steps 1 and 2, we can mimic the method in Step 1 to showthat {P−i ∈ Dn−1 : f (Pi , P−i ) = x} = {P−i ∈ Dn−1 : f (Pi0 , P−i ) = x}.
Steps 1, 2, and 3 show that f satisfies swap monotonicity.

Note that Lemma 1 holds in any arbitrary domain. We now use this to prove the following
result.
Lemma 2 Suppose D is any domain and f : Dn → A is an scf on this domain. Then, thefollowing statements are equivalent.
1. f is G-LOBIC and satisfies elementary monotonicity.
2. f is LDSIC.
Proof : First, we show that a LDSIC scf f satisfies elementary monotonicity. To see this,consider i ∈ N and P−i . Let Pi and Pi0 be two preferences in D such that Pi0 is an (a, b)-swapof Pi and f (Pi , P−i ) = b. Assume for contradiction that f (Pi0 , P−i ) = c 6= b. If cPi b, then ican manipulate from Pi to Pi0 . If bPi c, then, by construction, bPi0 c, and again, agent i canmanipulate from Pi0 to Pi . This is a contradiction.
16

Further, an LDSIC scf is LOBIC with respect to any priors, and hence, G-LOBIC. Now,
we show that if f : Dn → A is G-LOBIC and satisfies elementary monotonicity, then it is
LDSIC. Fix an agent i and P−i . Now, pick two preference orderings Pi and Pi0 such that Pi0
is an (a, b) swap of Pi , where Pi (k) = a, Pi (k + 1) = b and Pi0 (k + 1) = a, Pi0 (k) = b for somek. Suppose f (Pi , P−i ) = x and f (Pi0 , P−i ) = y. Suppose Pi (k 0 ) = x. If k 0 < k or k 0 > k + 1,
then by Lemma 1, we have y = x (swap monotonicity). So, agent i cannot manipulate fromPi to Pi0 . If k 0 = k, then x = a, and by swap monotonicity f (Pi0 , P−i ) ∈ {a, b}. Since aPi b,
agent i cannot manipulate from Pi to Pi0 . The other possibility is k 0 = k + 1. In that case,x = b, and elementary monotonicity ensures that f (Pi0 , P−i ) = b. Hence, agent i cannot

manipulate from Pi to Pi0 . This shows that f is LDSIC.
Proof of Theorem 2: This follows from Lemma 2 and the definition of a local domain (every
LDSIC scf is a DSIC scf).

5

G-LOBIC with Unanimity and DSIC Mechanisms

In this section, we investigate if we can replace/weaken elementary monotonicity in Theorem
2 by other reasonable conditions. One familiar axiom used in strategic voting literature isPareto efficiency.
Definition 14 An scf f is Pareto efficient if for every P ∈ Dn there exists no b ∈ Asuch that bPi f (P) for all i ∈ N .
We first show that if there are two agents, then elementary monotonicity is implied in any
domain by G-LOBIC and Pareto efficiency.
Proposition 2 Suppose n = 2. Then, every Pareto efficient and G-LOBIC scf satisfies
elementary monotonicity.
Proof : Let f be a Pareto efficient scf that is LOBIC with respect to generic priors. Pick a
profile (P1 , P2 ). Suppose f (P1 , P2 ) = b and aP1 b. We need to show that if P10 is an (a, b)-swapof Pi , then f (P10 , P2 ) = b. Since aP1 b and f (P1 , P2 ) = b, Pareto efficiency implies that bP2 a.
But bP10 a and Pareto efficiency implies that f (P10 , P2 ) 6= a. Since f is G-LOBIC, by swap
monotonicity (Lemma 1), f (P10 , P2 ) ∈ {a, b}, and hence, f (P10 , P2 ) = b.
Note that Proposition 2 holds in every domain D. This gives us the following simple
corollary.
Corollary 1 Let n = 2 and D be a local domain. Then, every Pareto efficient and GLOBIC scf f : Dn → A is DSIC.
17

Proof : This follows from Theorem 2 and Proposition 2.

Corollary 1 is not true if n > 2 - the scf f ∗ defined in Proposition 1 is an example of aPareto efficient scf that is G-LOBIC in the single peaked domain (a local domain) but not
DSIC. Corollary 1 also explains why we needed at least three agents for the scf in Proposition
1.
In some specific domains, we can replace Pareto efficiency by unanimity in Proposition 2
and Corollary 1. For instance, in the proofs of Theorems 3 and 4, we show that G-LOBIC
and unanimity implies Pareto efficiency in the unrestricted domain and in the single peakeddomain respectively. This implies that if there are two agents and the domain is either theunrestricted domain or the single peaked domain, then every unanimous G-LOBIC scf is a
DSIC scf. We now discuss the implications of assuming unanimity when n ≥ 3.

5.1 Unrestricted Domain
We now explore the implication of G-LOBIC along with unanimity when n ≥ 3. Our first
result assumes the unrestricted domain.
Theorem 3 Suppose |A| ≥ 3 and f : P n → A is a G-LOBIC scf, where P is the unrestricteddomain. If f satisfies unanimity, then it satisfies elementary monotonicity. Hence, if f is
G-LOBIC and unanimous, then it is DSIC.
The proof of this theorem is given in Appendix A. Note that Theorem 3 is a strengtheningof Theorem 1 since we use G-LOBIC instead of G-OBIC. However, one can still deduce theresult of Theorem 3 from existing results in the literature as follows. Carroll (2012) notesthat his results also hold if we consider Bayesian incentive compatibility. Since he shows
local incentive compatibility implies full incentive compatibility in the unrestricted domain,
we can conclude that if f is LOBIC (with respect to any prior) then it is OBIC. We canthen use Theorem 1 to conclude that if f is G-LOBIC and unanimous, then it must be adictatorship.
However, we give an independent proof in Appendix A. Our proof establishes directlythat in the unrestricted domain, unanimity and G-LOBIC imply elementary monotonicity,and then the result follows by using Theorem 2 and noting that the unrestricted domain is alocal domain. Since the proof of Theorem 1 in Majumdar and Sen (2004) directly establishes
dictatorship (using induction on the number of agents), our proof provides an alternate andstronger version of their result.
Theorem 3 implies that under G-LOBIC, elementary monotonicity is weaker than unanimity in the unrestricted domain. This implies that our main result in Theorem 2 is astronger result than Theorem 1.
18

P1
a
b
c
d

P2
a
b
c
d

P10
b
a
c
d

P3
b
a
c
d

P2
a
b
c
d

P3
b
a
c
d

Table 4: Weak elementary monotonicity

5.2 Single Peaked Domain
Unfortunately, Theorem 3 heavily relies on the unrestricted domain assumption and Proposition 1 shows that it cannot be extended to restricted domains like the single peaked domain.
We are able to show that the conclusions of Theorem 2 can nevertheless be obtained in the
single peaked domain by assuming unanimity and a significantly weaker version of elementary
monotonicity. We discuss this next.
As before, we will assume that S is the single peaked domain with respect to an ordering over alternatives in A. We now introduce a weakening of the elementary monotonicity
condition.
Definition 15 An scf f : S n → A satisfies weak elementary monotonicity if for everyi ∈ N , for every Pi , Pi0 ∈ S such that Pi0 is a (Pi (1), Pi (2))-swap of Pi and for every P−i suchthat f (Pi , P−i ) = Pi (2), Pj ∈ {Pi , Pi0 } for all j 6= i, and Pj 6= Pk for some j, k ∈ N \ {i}, wehave f (Pi0 , P−i ) = f (Pi , P−i ).
Weak elementary monotonicity applies to very specific type profiles. First, it requires that
Pi0 is an (a, b)-swap of Pi , where Pi (1) = a, Pi (2) = b, i.e., the swaps happen at the top.
Second, it requires that every agent in N \ {i} must have either Pi or Pi0 as his type. Finally,
agents in N \ {i} cannot have the same type, i.e., there is at least one agent who has Pi as
his type and at least one agent who has Pi0 as his type.
A typical pair of type profiles where weak elementary monotonicity can be applied isshown in Table 4. We assume A = {a, b, c, d} and a  b  c  d and n = 3. Profiles(P1 , P2 , P3 ) and (P10 , P2 , P3 ) in Table 4 differ in agent 1’s preference and P10 is a (a, b)-swapof Pi . Also, notice that a and b are neighbors in , and P2 = P1 , P3 = P10 (hence, P2 6= P3 ).
Weak elementary monotonicity applies to such profiles and requires that if f (P1 , P2 , P3 ) = b,then f (P10 , P2 , P3 ) = b.
The following result shows that weak elementary monotonicity can be used with unanimity in the single peaked domain to get a counterpart of Theorem 2.
Theorem 4 Suppose f : S n → A is a unanimous scf. Then, the following statements areequivalent.
19

1. f is G-LOBIC and satisfies weak elementary monotonicity.
2. f is DSIC.
The proof of Theorem 4 is in Appendix A. Since weak elementary monotonicity is anextremely weak condition, this result shows how little is required on top of unanimity to
get the counterpart of Theorem 3 in the single peaked domain. We believe that in specificrestricted domains, we can find similar weakening of elementary monotonicity that may be
used in conjunction with unanimity to get a result similar to Theorem 4.
The result in Theorem 4 can also be extended to some extensions of single peaked domain.
For instance, Demange (1982) defines a notion of single peakedness on a tree graph, which
requires single peakedness along paths of a tree graph whose vertices are alternatives. Our
result can be easily extended to such a domain.

6

Discussions

We discuss some extensions and implications of our result.
Weaker OBIC-DSIC equivalence. The G-OBIC and DSIC equivalence established inthis paper is very strong - under some reasonable assumptions, every G-OBIC mechanism is
a DSIC mechanism. However, one could consider the following weaker notion of equivalence.

Definition 16 A pair of scfs f : Dn → A and f 0 : Dn → A are weakly equivalent if forevery i ∈ N , for every Pi ∈ D, and for every a ∈ A,
0

πif (a, Pi ) = πif (a, Pi ).
We can then ask if for every OBIC mechanism f , there exists a DSIC mechanism f 0 that is
weakly equivalent to f . Of course, one can ask this question under additional conditions likeunanimity or elementary monotonicity. Since, this is a weaker requirement, it is plausiblethat we can get the weak equivalence in a larger class of domains than identified in Theorem
2. However, the answer does not look very clear.
In Appendix B, we show that for the scf f ∗ considered in Proposition 1, there is no DSIC,
unanimous, and anonymous scf that is weakly equivalent to it. The scf f ∗ is an anonymousand unanimous scf. Further, Proposition 1 showed that f ∗ is OBIC with respect to a large
class of priors (including generic priors). This illustrates that we can have unanimous andanonymous scfs that are OBIC in the single peaked domain for which there are no weakly
equivalent DSIC, unanimous, and anonymous scf.
20

We point out that in cardinal environments with quasilinear preferences over transfers,
more specifically, in the single object auction problem and in some specific one dimensional
mechanism design problems, the weak equivalence question has been addressed in Manelli
and Vincent (2010) and Gershkov et al. (2013). They show that for every Bayesian incentive compatible single object auction mechanism, there exists a DSIC single object auction
mechanism that generates the same interim allocation probability of winning the object forevery agent. 11
Apart from the weak equivalence notion, there are many other subtle differences between
these papers and ours. First, they look at cardinal mechanisms with quasilinearity, whereas
ours is a completely ordinal environment without transfer. Second, they allow for mechanisms to be randomized - their result will fail if we restrict attention to only deterministic
mechanisms (an example is available upon request). On the other hand, our results arefor deterministic mechanisms and we do not know if our result will continue to hold if we
consider randomized voting mechanisms. Finally, our results require independent genericpriors but the results in these papers only make the independence assumption - see Kushnir(2014) for extension of the results in Manelli and Vincent (2010); Gershkov et al. (2013) tocorrelated priors.
Chung and Ely (2007); Chen and Li (2014) address a related issue in quasilinear environment with transfers. They consider a mechanism designer who has no specific information
about beliefs of agents. They show that if the designer wants to maximize the worst case(over a set of possible beliefs) revenue from the mechanisms, then he should use a dominant
strategy mechanism in the single object auction and other specific settings. These results
provide a different foundation for dominant strategy mechanisms in their cardinal quasilinear
setting than ours - see also Borgors (2013).
Necessary conditions on domains. We do not know if our main result can hold indomains that are not local. We have used the idea of local incentive constraints extensively
in our proof. Indeed, Lemma 2 established equivalence between G-LOBIC and G-LDSIC
under elementary monotonicity in any arbitrary domain. Using this and the results in Sato(2013), we can easily identify necessary conditions on the domain for the equivalence of
G-LOBIC and DSIC. For instance, consider the following condition from Sato (2013).
Definition 17 A domain D is connected if for every P, P 0 ∈ D, there exists a sequenceof distinct types (P = P 0 , P 1 , . . . , P k , P k+1 = P 0 ) such that for all j ∈ {0, 1, . . . , k}, P j ∈ D
and P j+1 is a (x, y)-swap of P j for some x, y ∈ A.
11

They also consider an even weaker notion of equivalence, where they compare interim expected utilities
of agents.

21

Connectedness requires that we can go from any type in a domain to another type using asequence of distinct types that are generated by swaps. Sato (2013) gives many examplesof domains, which include the unrestricted domain and the single peaked domain, that areconnected. He shows that if a domain is a local domain, then it must be connected. We can
now prove the following lemma.
Lemma 3 Suppose D is a domain such that every G-LOBIC scf f : Dn → A satisfying
elementary monotonicity is DSIC. Then, D is connected.
Proof : By Lemma 2, any G-LOBIC scf f : Dn → A satisfying elementary monotonicity is
LDSIC. Since, LDSIC implies DSIC in D, by Sato (2013), D is connected.

Since the separable domains in Le Breton and Sen (1999) are not connected, a consequence of this lemma is that G-LOBIC and elementary monotonicity does not imply DSIC inthese domains. We do not have any necessary conditions on domains where G-OBIC alongwith elementary monotonicity will imply DSIC.
Indirect implications. We can use our results to strengthen some results on DSIC mechanisms. We list some of these results below.
• Description of mechanisms. In many domains, the class of DSIC mechanisms havebeen explicitly characterized. For instance, in the single peaked domain, Moulin (1980)shows that the only DSIC, anonymous and unanimous mechanisms are generalized
median voting mechanisms. 12 Our Theorem 4 will imply that in the single peakeddomain, the only G-OBIC, unanimous, and anonymous mechanisms satisfying weakelementary monotonicity are generalized median voting mechanisms.
Similarly, Saporiti (2009) shows that in the maximal single crossing domain, the only
DSIC, anonymous, and unanimous mechanisms are generalized median voting mechanisms. Since the maximal single crossing domain is a local domain (Carroll, 2012), ourTheorem 2 will imply that in the maximal single crossing domain, the only G-OBIC,
unanimous, and anonymous mechanisms satisfying elementary monotonicity are generalized median voting mechanisms.
• Group strategy-proof mechanisms. Barbera et al. (2010) identify a large class of
domains where DSIC imply the stronger property of group strategy-proofness. Groupstrategy-proofness requires that no coalition of agents can manipulate the mechanism.
12

A generalized median voting scf is defined by locating n − 1 phantom peaks at various alternatives andthen taking the median of these peaks and the top ranked alternatives of n agents.

22

The class of such domains include many local domains (unrestricted domain, single
peaked domain). Our results will imply that if any such domain is a local domain,then a G-OBIC mechanism satisfying elementary monotonicity will be a group strategyproof mechanism.
• Optimization. Gershkov et al. (2014) find the expected utility maximizing DSIC,
unanimous, and anonymous mechanism in the maximal single crossing domain of
Saporiti (2009). Using our Theorem 2, their mechanism will also remain optimal ifthey search over the set of all G-OBIC mechanisms satisfying elementary monotonicity.
Uniform priors. Though uniform priors are non-generic, they play an important role indecision theory. In their paper, Majumdar and Sen (2004) show that in the unrestricteddomain, there are unanimous scfs that are OBIC with respect to uniform priors but not
DSIC. They show that any scf satisfying neutrality and elementary monotonicity is OBIC
with respect to uniform priors. These conditions are mild and hence, cover many scfs.
Unfortunately, this result is no longer true in restricted domains. This is an artifact of
the notion of Bayesian incentive compatibility. Suppose we have an OBIC (with respect touniform priors) scf in a domain D and we consider the restriction of this scf to a smaller
domain D0 . The restriction of the original scf need not be OBIC with respect to uniform
priors in the smaller domain D0 .
Appendix B contains an example of an scf in the unrestricted domain that is OBIC
with respect to uniform priors but its restriction to the single peaked domain is no longer
OBIC with respect to uniform priors. This illustrates that unlike in the unrestricted domain,elementary monotonicity and neutrality are not sufficient conditions for an scf to be OBIC
with uniform priors in restricted domains.

7

Conclusion

We have identified a large class of domains where G-LOBIC and elementary monotonicity areequivalent to DSIC. The equivalence of G-LOBIC and elementary monotonicity with LDSIC
works in every domain. We also explored the consequence of using unanimity in place ofelementary monotonicity. Unfortunately, except for the unrestricted domain, unanimity is
not enough to guarantee similar equivalences. However, in restricted domains like the single
peaked domain, we can replace elementary monotonicity by a significantly weaker condition
along with unanimity to get our result. Our results are foundations in the sense that they
point out an amazing robustness property of DSIC mechanisms in voting environments. To

23

look beyond DSIC mechanisms, our results point to the use of cardinal and/or randomized
BIC mechanisms in voting environments.

Appendix A: Omitted Proofs
Proof of Proposition 1
Clearly, f ∗ is unanimous and anonymous. However, f ∗ is not DSIC. To see this, consider aprofile P such that for all agents i 6= 3, we have Pi (1) = a - note that since a is the leftmost
alternative, there is a unique preference ordering where a is top ranked. For agent 3, pick
any preference ordering where b is preferred to a. As a result, f ∗ (P) = b. A possible profileis shown in Table 5 - note that aP1 b. Now, fixing the preference profile of all agents except
agent 1, if agent 1 reports a preference ordering P10 such that P10 (1) = b, P10 (2) = a, then f ∗will choose a - see Table 5. Hence, agent 1 can manipulate.
P1
a
b
c

P2
a
b
c

P10
b
a
c

P3
b
a
c

P2
a
b
c

P3
b
a
c

Table 5: Failure of DSIC of f ∗However, we show that f ∗ is G-OBIC. Let the prior of each agent i be given by the mapµi : S → (0, 1). To show that f ∗ is OBIC with respect to {µi }i∈N such that these are genericpriors, we will compute the interim allocation probabilities of every agent in {1, 2, 3}.
If an agent i ∈ {1, 2, 3} has type Pi then define∗

Oif (Pi ) := {x ∈ A : f ∗ (Pi , P−i ) = x for some P−i }.
∗By definition of f ∗ , for every i ∈ {1, 2, 3} and for every Pi ∈ S, Oif (Pi ) ⊆ {a, b, Pi (1)}, and if∗
Pi (1) 6= c, then Oif (Pi ) = {a, b}. Let P̄ be the unique preference ordering where the leftmost
alternative a is top ranked. Denote the probability that agent i has type P̄ as qi ≡ µi (P̄ ).
Similarly, denote by q̂i ≡ µi (P̂ ), where P̂ is the unique ordering where alternative c is top
ranked. We fix an agent i ∈ {1, 2, 3} and denote the other two agents in {1, 2, 3} as j and k.
We consider three possible cases.
∗

Case 1. Suppose Pi = P̄ . Note that Oif (Pi ) = {a, b}. Then his interim allocation probability for alternative a can be computed as follows. Note that f ∗ (Pi , Pj , Pk ) 6= a if Pj and
Pk are such that either (aPj b and bPk a) or (aPk b and bPj a). The probability of this event is
qj (1 − qk ) + qk (1 − qj ).
24

Here, we used the fact that the probability that agent j has type Pj such that bPj a is just
(1 − pj ) and, similarly, the probability that agent k has type Pk such that bPk a is (1 − qk ).
Since f ∗ (Pi , Pj , Pk ) ∈ {a, b}, the interim allocation probability of choosing a at Pi for agent
i is
1 − qj − qk + 2qj qk ,and the interim allocation probability of choosing b at Pi for agent i is
qj + qk − 2qj qk .

Case 2. Suppose Pi is such that Pi (1) = b - this is possible for two preference orderings.
∗
Note that Oif (Pi ) = {a, b}. Then, his interim allocation probability for alternative b can becomputed as follows. Note that f ∗ (Pi , Pj , Pk ) 6= b if Pj and Pk are such that either (aPj b
and bPk a) or (aPk b and bPj a). The probability of this event is
qj (1 − qk ) + qk (1 − qj ).
Hence, the interim allocation probability of choosing b at Pi for agent i is
1 − qj − qk + 2qj qk .
∗Since Oif (Pi ) = {a, b}, the interim allocation probability of choosing a at Pi for agent i is
qj + qk − 2qj qk .
∗Case 3. Suppose Pi is such that Pi (1) = c, i.e., Pi = P̂ . Then, Oif (Pi ) = {a, b, c}. Hisinterim allocation probability for alternative c can be computed straightforwardly - c is chosen if and only if Pj (1) = Pk (1) = Pi (1) = c. This is possible if and only if both agents jand k have the type P̂ . The probability of this event is q̂j q̂k . Hence, the interim allocation
probability for alternative Pi (1) at Pi for agent i is q̂j q̂k . Next, the interim allocation probability for agent i for alternative a can be computed as follows. For this, note that cPi bPi a.
Hence, f ∗ (Pi , Pj , Pk ) = a if Pj and Pk are such that either (aPj b and bPk a) or (aPk b andbPj a) - notice that these events ensure that tops of all agents are not the same and a is not
dominated by b. The probability of this event is
qj (1 − qk ) + qk (1 − qj ).
Hence, the interim allocation probability of choosing a at Pi for agent i is
qj + qk − 2qj qk .
25

∗Since Oif (Pi ) = {a, b, Pi (1)}, the interim allocation probability of choosing b at Pi for agent
i is
1 − qj − qk + 2qj qk − q̂j q̂k .
We enumerate all the interim allocation probabilities in Table 6 by considering the threecases for an agent i ∈ {1, 2, 3} by denoting the other two agents as j and k.

∗
πif (a, Pi )∗πif (b, Pi )∗πif (c, Pi )Case 1: Pi = P̄
1 − qj − qk + 2qj qk
qj + qk − 2qj qk
0

Case 2: Pi (1) = b
qj + qk − 2qj qk
1 − qj − qk + 2qj qk
0

Case 3: Pi = P̂
qj + qk − 2qj qk
1 − qj − qk + 2qj qk − q̂j q̂kq̂j q̂k

Table 6: Interim allocation probabilities
Now, notice from Table 6 that if agent i has type Pi such that Pi (1) = a, the only OBIC
constraint to satisfy is
1 − qj − qk + 2qj qk ≥ qj + qk − 2qj qk .
Alternatively, we must have
(1 − 2qj )(1 − 2qk ) ≥ 0.

(1)This prevents any manipulation of agent i to a type in Case 2 or Case 3. Also, Inequality 1
ensures OBIC constraints when agent i has a type Pi such that Pi (1) = b. Finally, Inequality
1 also ensures OBIC constraints when agent i has a type Pi such that Pi (1) = c - this can beverified by checking from Table 6 that the truthtelling lottery first-order stochastic dominates
other lotteries as long as Inequality 1 is satisfied.
Hence, f ∗ is OBIC if and only if the priors of agents 1,2, and 3 satisfy(1 − 2q2 )(1 − 2q3 ) ≥ 0,
(1 − 2q1 )(1 − 2q3 ) ≥ 0,
(1 − 2q1 )(1 − 2q2 ) ≥ 0.
This is satisfied if and only if q1 , q2 , q3 ∈ (0, 0.5) or q1 , q2 , q3 ∈ (0.5, 1). It also puts norestriction on the probabilities of orderings in S \ {P̄ }. Hence, the set of priors of all agentssatisfying q1 , q2 , q3 ∈ (0, 0.5) or q1 , q2 , q3 ∈ (0.5, 1) is a full dimensional subset of the set of
all independent priors. As a result, it must have a non-empty intersection with the set ofindependent generic priors.

26

Proof of Theorem 3
We first show that if f : P n → A is G-LOBIC and unanimous, then it is Pareto efficient.
Suppose f is G-LOBIC and unanimous but assume for contradiction that it is not Pareto
efficient. For this, we consider a profile P such that f (P) = b but there exists a ∈ Asuch that aPi b for all i ∈ N . Consider an agent i ∈ N such that Pi (k) = a and k 6= 1.
Suppose Pi (k − 1) = x. Consider Pi0 which is a (x, a)-swap of Pi . By swap monotonicity,f (Pi0 , P−i ) = b. We can repeat such swaps to reach a preference ordering Pi00 for agent i suchthat Pi00 (1) = a and f (Pi00 , P−i ) = b. Now, we can repeat this procedure for every agent jsuch that Pj (k) = a and k 6= 1 to arrive at a profile P00 such that f (P00 ) = b. But this willcontradict unanimity since Pj00 (1) = a for all j ∈ N .
Hence, we show that any f : P n → A that is G-LOBIC and Pareto efficient must satisfy
elementary monotonicity. By Theorem 2, we will be done.
To do so, we consider an agent i ∈ N , a preference profile P−i of other agents, and Pi , Pi0such that Pi0 is an (a, b)-swap of Pi and f (Pi , P−i ) = b. The two profiles are shown in Table
7. Notice that there are some agents in P−i who prefer a to b and some prefer b to a. If
all the agents in P−i prefer a to b, then the outcome at (Pi , P−i ) cannot be b due to Pareto
efficiency. Similarly, if all the agents in P−i prefer b to a, the outcome at (Pi0 , P−i ) cannot bea, and hence, must be b, which gives us the desired result.
Hence, we will assume that there is at least one agent in P−i who prefers a to b and at
least one agent who prefers b to a.
Pi
·
·
a
b
·
·

P−i
...
...
b...
...
a...
...

Pi0
·
·
b
a
·
·

...
...
a...
...
b...
...

P−i
...
...
b...
...
a...
...

...
...
a...
...
b...
...

Table 7: Profiles (Pi , P−i ) and (Pi0 , P−i )We will now show that f (Pi0 , P−i ) = b. By swap monotonicity, f (Pi0 , P−i ) ∈ {a, b}. Assume for contradiction that f (Pi0 , P−i ) = a. Now, we do the proof in steps. In the proof, if
x and y are consecutive alternatives in an ordering, an (x, y)-swap of this ordering will bereferred to as a swap.
Step 1. We modify the profile (Pi , P−i ) to bring one of the alternatives not in {a, b} (suchan alternative exists since |A| ≥ 3) just below {a, b} for all the agents. Let x ∈/ {a, b} be27some alternative. If aPj x and bPj x for some j ∈ N , then we can do a series of swaps tolift x up such that it is just below b if aPj b or just below a if bPj a (note that none of theseswaps will involve b). By swap monotonicity, the outcome at the new profile continues tobe b. Using a similar argument, if bPj x and xPj a for some j ∈ N , then we can come to apreference ordering where x is just below a maintaining the outcome to be b.
Now, consider j ∈ N , such that xPj b. If x and b are not consecutive in Pj , then again we
can do a series of swaps to come to a preference ordering such that x is just above b (noteagain that none of these swaps will involve b). By swap monotonicity, the outcome at the
new profile continues to be b. Let us denote this new profile by P̄.
So, we have reached a profile, where for every j ∈ N , either x is just above b in P̄jor [x is just below b if aP̄j b and x is just below a if bP̄j a]. Now, we pick a j ∈ N suchthat x is just above b in P̄j . We do a (x, b)-swap to get a preference ordering P̄j0 . By swap
monotonicity f (P̄j0 , P̄−j ) ∈ {x, b}. We repeat this procedure for every agent k such thatx is just above b in P̄k . Denote the new profile as P̄0 . By repeated application of swap
monotonicity, f (P̄0 ) ∈ {x, b}. But bP̄j0 x for all j ∈ N . Hence, by Pareto efficiency, f (P̄0 ) = b.
Now, consider the (a, b)-swap of P̄i0 and denote this preference ordering as P̄i00 . Since0f (Pi0 , P−i ) = a, an analogous argument will show that f (P̄i00 , P̄−i
) = a. The two profiles
0000
0(P̄i , P̄−i ) and (P̄i , P̄−i ) are shown in Table 8.
P̄i0
·
·
a
b
x
·
·

0
P̄−i
...
...
b...
...
a...
x...
...

P̄i00
·
·
b
a
x
·
·

...
...
a...
...
b...
x...
...

0
P̄−i
...
...
b...
...
a...
x...
...

...
...
a...
...
b...
x...
...

0
0
Table 8: Profiles (P̄i0 , P̄−i
) and (P̄i00 , P̄−i)0
Step 2. In this step, we modify the profile (P̄i0 , P̄−i
) in a particular way. First, we look at00
an agent j ∈ N , such that aP̄j b and bP̄j x. We perform a (b, x) swap for each of these agents.
The new profile is shown in Table 9. By swap monotonicity, the outcome at the new profile
must be in {b, x}. But since a is ranked higher than x for all the agents, Pareto efficiency
implies the outcome at the new profile must be b.

Step 3. In this step, we modify the profile in Table 9 further. In particular, we lift x just28

Agent i
·
·
a
x
b
·
·

Other agents
...
...
b...
...
a...
x...
...

...
...
a...
...
x...
b...
...

Table 9: New profile in Step 2
above a. For agent i and for all j 6= i such that x is just below a, this can be done bya (a, x)-swap. For all other agents, this requires a series of swaps - note that these swaps
can be done by without involving b. The new profile is shown in Table 10. Since none of
the swaps involve b, swap monotonicity implies that the outcome at the new profile remains b.

Agent i
·
·
x
a
b
·
·

Other agents
...
...
b...
...
x...
a...
...

...
...
x...
a...
...
b...
...

Table 10: New profile in Step 3
Step 4. In this step, we modify the profile in Step 3 by changing only agent i’s preference
ordering. We do this by doing an (a, b)-swap of the preference ordering of agent i in the
profile shown in Table 10. The new profile is shown in Table 11. By swap monotonicity,
the outcome at the new profile is in {a, b}. But x is better than a for all agents, and hence,
Pareto efficiency implies the outcome at the new profile is b.
Step 5. In this step, we modify the profile in Step 4 by changing the preferences of thoseagents who prefer x to a and a to b (the third column of agents in Table 11). We perform aseries of swaps to bring x just one position above b. The new profile is shown in Table 12.
By swap monotonicity, the outcome at this profile remains b.

29

Agent i
·
·
x
b
a
·
·

Other agents
...
...
b...
...
x...
a...
...

...
...
x...
a...
...
b...
...

Table 11: New profile in Step 4
Agent i
·
·
x
b
a
·
·

Other agents
...
...
b...
...
x...
a...
...

...
...
a...
...
x...
b...
...

Table 12: New profile in Step 5
Step 6. Now, we perform an (x, b)-swap of preferences of those agents who rank x justabove b in the profile in Step 5 - this will be agent i and agents in the third column in Table
12. The new profile is shown in Table 13. By swap monotonicity, the outcome at the new
profile is in {x, b}. But b is preferred to x for all the agents. Hence, Pareto efficiency implies
the outcome at the new profile remains b.

Agent i
·
·
b
x
a
·
·

Other agents
...
...
b...
...
x...
a...
...

...
...
a...
...
b...
x...
...

Table 13: New profile in Step 630

Step 7. Finally, we perform a (x, a)-swap for the preferences of all agents in the profile in
Step 6 who rank x just above a - this will include agent i and agents in the second columnof Table 13. The new profile is shown Table 14. By swap monotonicity, the outcome at thisprofile remains b.
0
But the profile shown in Table 14 is exactly the profile (P̄i00 , P̄−i
) (see Table 8) and we00
0
had assumed that f (P̄i , P̄−i ) = a. This is a contradiction.
Agent i
·
·
b
a
x
·
·

Other agents
...
...
b...
...
a...
x...
...

...
...
a...
...
b...
x...
...

Table 14: New profile in Step 7

Proof of Theorem 4
Let f be a unanimous scf that is G-LOBIC. The proof goes in many steps.
Step 1. In this step, we collect some facts about single peaked domain from Sato (2013).
These facts will be used in subsequent steps. We have already defined the notion of aconnected domain in Definition 17. We now propose a strengthening of this notion.
Definition 18 A distinct sequence of types (P 0 , P 1 , . . . , P k , P k+1 ) is without restoration
if there exists no distinct j, j 0 ∈ {0, 1, . . . , k} and x, y ∈ A such that P j+1 is a (x, y)-swap of00
P j and P j +1 is a (y, x)-swap of P j .
The without restoration property requires that no pair of alternatives is swapped morethan once along the sequence. With this notion, we can strengthen the notion of connectedness.
Definition 19 A domain D is connected without restoration if for every P, P 0 ∈ D,
there exists a sequence of distinct types (P = P 0 , P 1 , . . . , P k , P k+1 = P 0 ) without restorationsuch that for all j ∈ {1, . . . , k}, P j ∈ D and for all j ∈ {0, 1, . . . , k}, P j+1 is a (x, y)-swap
of P j for some x, y ∈ A.

31

Sato (2013) shows that if a domain is connected without restoration, then it is a local
domain. The unrestricted domain and the single peaked domains are examples of domainsthat are connected without restoration. We will use this fact in our proofs.
Step 2. In this step, we will prove a claim using the facts in Step 1.
Claim 1 Suppose Pi ∈ S is a preference ordering such that aPi b. Then, there exists a
preference ordering Pi0 ∈ S such that Pi0 (1) = a and B(b, Pi ) = B(b, Pi0 ). Moreover, for all
P−i ∈ S n−1 with f (Pi , P−i ) = b, we have f (Pi0 , P−i ) = b.
Proof : The first part of the claim follows from the single peaked domain - if aPi b, then wecan always lift a to the top and keep all the alternatives that are above b in Pi between a and b
and all others below b in the new preference ordering. Let Pi0 be such an ordering. By the facts
in Step 1, we know that there is a distinct sequence of types (Pi = P 0 , P 1 , P 2 , . . . , P k , P k+1 =Pi0 ) without restoration such that consecutive types in the sequence are swaps of each other.
Since B(b, Pi ) = B(b, Pi0 ) and the sequence is without restoration, none of these swaps
involve b. By repeatedly applying swap monotonicity along the sequence, we get f (Pi0 , P−i ) =f (Pi , P−i ) = b.

Step 3. In this step, we show that if an scf is G-LOBIC and unanimous, then it must be
Pareto efficient. For this consider a profile P with f (P) = b. Assume for contradiction that
there exists a 6= b such that aPi b for all i ∈ N . By Claim 1, there exists a preference profile
P0 such that f (P0 ) = b and Pi0 (1) = a for all i ∈ N . This is a contradiction since unanimity
implies that f (P0 ) = a.
Step 4. Now, consider an agent i ∈ N and P−i ∈ S n−1 . Let Pi , Pi0 ∈ S be such that Pi0 is an(a, b)-swap of Pi and f (Pi , P−i ) = b. We will show that f (Pi0 , P−i ) = b. We consider various
cases.
Case 1. Suppose Pi (k) = a and k > 1, i.e., the swap from Pi to Pi0 is not happening at
the top of the preference ordering. Since a and b are consecutively ranked in Pi and Pi0 andneither of them are top ranked in Pi and Pi0 , it must be that a and b are not neighbors (in). This is because if a and b are neighbors then they can only be swapped if they are at
the top.
Hence, consider a neighbor c of a such that c is between a and b in  (i.e., if a  b,then a  c  b and if b  a then b  c  a). By definition, cPi a and cPi0 b. Further, for
any other agent j 6= i, there are four possible rankings between a, b, c in Pj : (1) cPj aPj b, (2)cPj bPj a, (3) bPj cPj a, and (4) aPj cPj b. The two profiles (Pi , P−i ) and (Pi0 , P−i ) are shown in
32

Table 15. Table 15 shows that there are four group of agents in P−i with different possible
rankings between a, b, c. We now modify the profile (Pi , P−i ) in a sequence of steps to reachthe profile (Pi0 , P−i ).

Pi
·
c
·
a
b
·
·

P−i
...
c...
...
a...
...
b...
...

...
c...
...
b...
...
a...
...

Pi0
·
c
...
b
a
·
·

...
...
b... a...
...
...
c... c...
...
...
a... b...
...
...

P−i
...
c...
...
a...
...
b...
...

...
c...
...
b...
...
a...
...

...
...
b... a...
...
...
c... c...
...
...
a... b...
...
...

Table 15: Profiles (Pi , P−i ) and (Pi0 , P−i )Step 1a. In this step, we modify the preferences of agents in P−i who rank a better thanc better than b. For each such agent j, we construct Pj0 such that Pj0 (1) = a, Pj0 (2) = c andB(b, Pj0 ) = B(b, Pj ). Notice that since a and c are neighbors, single peakedness implies thatsuch a Pj0 can be constructed such that it is single peaked. Further, using a reasoning similar
to Claim 1, we can argue that we can go from Pj to Pj0 using a without restoration sequenceand since B(b, Pj0 ) = B(b, Pj ), b will not be involved in any swaps. As a result, the outcome
at the new profile will be b. The new profile is shown in Table 16.

Pi
·
c
·
a
b
·
·

Other
...
c...
...
a...
...
b...
...

agents
...
...
c...
b...
...
...
b...
c...
...
...
a... a...
...
...

a...
c...
...
...
...
b...
...

Table 16: Profile in Step 1a.
Step 1b. In this step, we modify the profile in Table 16 as follows. For every agent otherthan i who rank a at the top, c second, we perform the (a, c)-swap. Notice that this leads
to a feasible single peaked preference ordering since a and c are neighbors. The new profile33

is shown in Table 17. By swap monotonicity, the outcome at the new profile is b.

Other
...
c...
...
a...
...
b...
...

Pi
·
c
·
a
b
·
·

agents
...
...
c...
b...
...
...
b...
c...
...
...
a... a...
...
...

c...
a...
...
...
...
b...
...

Table 17: Profile in Step 1b.
Step 1c. In this step, we perform (a, b)-swap of Pi to reach Pi0 . The new profile is shown in
Table 18. By swap monotonicity, the outcome at the new profile is in {a, b}. Note that at the
new profile cPj a for all j ∈ N . Hence, by Pareto efficiency the outcome at the new profile is b.
Pi0
·
c
·
b
a
·
·

Other
...
c...
...
a...
...
b...
...

agents
...
...
c...
b...
...
...
b...
c...
...
...
a... a...
...
...

c...
a...
...
...
...
b...
...

Table 18: Profile in Step 1c.
Step 1d. We can now consider the profile in Table 18 and alter the preferences of last(fifth) column of agents by performing a (c, a)-swap and then doing a sequence of without
restoration swaps to go to their preference in Step 1a (see preferences in Table 16). The new
profile is shown in Table 19.
Since none of these swaps involve alternative b, the outcome at this new profile is b due
to swap monotonicity. But this profile is exactly (Pi0 , P−i ). Hence, f (Pi0 , P−i ) = b.
Case 2. The other case is Pi (k) = a and k = 1, i.e., the swap from Pi to Pi0 is occurringat the top. The profile (Pi , P−i ) is shown below in Table 20. We now do the proof in many
34

Pi0
·
c
·
b
a
·
·

Other
...
c...
...
a...
...
b...
...

agents
...
...
c...
b...
...
...
b...
c...
...
...
a... a...
...
...

...
a...
...
c...
...
b...
...

Table 19: Profile in Step 1d.
steps.

Pi
a
b
·
·
·

P−i
...
a...
...
b...
...

...
b...
...
a...
...

Table 20: Profile in Case 2.
Step 2a. Now, consider every agent j 6= i such that aPj b (agents in second column of Table
20). By Claim 1, we can construct a preference ordering from Pj such that a is top ranked
and the outcome remains b. We change the preferences of all the agents in the profile in
Table 20 who prefer a to b in this manner to arrive at the new profile. The new profile isshown in Table 21 and the outcome at the new profile is b.

Pi
a
b
·
·
·

P−i
a...
...
...
b...
...

...
b...
...
a...
...

Table 21: Profile in Step 2a.
Step 2b. Now, for every agent j 6= i such that a is top tanked in the profile in Table 20,35

we consider a preference ordering where a is top ranked and b is second ranked. The new
profile is shown in Table 22.
Pi
a
b
·
·
·

P−i
a...
b...
...
...
...

...
b...
...
a...
...

Table 22: Profile in Step 2b.
By Sato (2013), such a preference ordering can be reached by swaps without restoration.
Hence, a will not be involved in such swaps. Swap monotonicity implies that the outcome
at the new profile is not a.
Step 2c. Now, consider every agent j 6= i such that b is preferred to a in the preference profilein Step 2b (agents in third column of Table 22). By Claim 1, we can construct a preference
ordering from this preference ordering such that b is top ranked and the alternatives thatwere below a do not change. The new profile is shown in Table 23. By definition, we cango to this new profile by doing a sequence of without restoration swaps that do not involvea. Hence, by swap monotonicity, the outcome at the new profile is not a. Then, by Pareto
efficiency, the outcome at this new profile must be b.

Pi
a
b
·
·
·

P−i
a...
b...
...
...
...

b...
...
...
a...
...

Table 23: Profile in Step 2c.
Step 2d. In this step, we consider all the agents who have b top-ranked in the profile in
Step 2c (agents in the third column in Table 23). For every such agent, we consider anotherpreference ordering where b is top-ranked and a is second ranked. The new profile is shownin Table 24. By Sato (2013), we can go to this new preference ordering by doing a sequenceof without restoration swaps. Hence, by swap monotonicity, the outcome at the new profile
is b.
36

Pi
a
b
·
·
·

P−i
a...
b...
...
...
...

b...
a...
...
...
...

Table 24: Profile in Step 2d.
Now, consider any agent who ranks a at the top in the profile in Step 2d. If his preference
ordering is not the same as Pi , then we can transform it to Pi by a sequence of without
restoration swaps. Since this will not involve any swaps of b, by swap monotonicity theoutcome will remain b at the new profile. A similar argument can be made to transform thepreference ordering of every agent who ranks b at the top to the preference ordering Pi0 . As aconsequence, the profile in Table 24 can be transformed to a profile where every agent j 6= i
has preference ordering Pi or Pi0 and the outcome at this profile is b. Denote this profile as(Pi , P̄−i ).
Now, assume for contradiction f (Pi0 , P−i ) = a. We now repeat the above procedure atthe profile (Pi0 , P−i ) to arrive at the profile (Pi0 , P̄−i ) and the outcome at this profile is a.
If all j 6= i have preference Pi , then unanimity implies f (Pi , P̄−i ) = a, hence, we reach acontradiction. Similarly, if all j 6= i have preference Pi0 , then unanimity implies f (Pi0 , P̄−i ) =b, and again, we reach a contradiction. Hence, there exist j, k 6= i such that P̄j = Pi andP̄k = Pi0 . Since f (Pi , P̄i ) = b, weak elementary monotonicity implies that f (Pi0 , P̄−i ) = b.
This is a contradiction. This completes the proof.

Appendix B
Failure of Weak Equivalence under Unanimity and Anonymity
Here, we will show that for the scf f ∗ identified in Proposition 1, there is no DSIC, unanimous,and anonymous scf that is weakly equivalent to it for a generic set of priors. Without lossof generality, we show this for N = {1, 2, 3}.
To remind, an scf is anonymous if by permuting the preferences of agents, the outcome
remains the same at the new profile. Hence, f ∗ is an anonymous scf if the number of agentsis three.
We remind some of the notations we used earlier. Suppose the domain is single peakedwith respect to . As before, we denote the left-most alternative and the second left-mostalternative according to  as a and b respectively. The unique type where a is top ranked is37

denoted by P̄ . The probability that agent i ∈ {1, 2, 3} has type P̄ is denoted as qi .
For agent 1, the interim allocation probabilities from f ∗ were computed earlier in the
proof of Proposition 1. We will only be interested in the interim allocation probabilities ofalternatives a and b when P1 (1) ∈ {a, b}. We reproduce that part of the interim allocation
probabilities below in Table 25.

∗
π1f (a, P1 )∗π1f (b, P1 )Case 1: P1 (1) = a
1 − q2 − q3 + 2q2 q3
q2 + q3 − 2q2 q3

Case 2: P1 (1) = b
q2 + q3 − 2q2 q3
1 − q2 − q3 + 2q2 q2

Table 25: Interim allocation probabilities of a and b
We also remind that since f ∗ is OBIC, we must have
(1 − 2q2 )(1 − 2q3 ) ≥ 0.
This implies that either q2 , q3 ∈ [0, 0.5] or q2 , q3 ∈ [0.5, 1].
Now, assume for contradiction that there is a DSIC, unanimous, and anonymous scf fthat is weakly equivalent to f ∗ . By Moulin (1980), f must be a median voter scf. To remind,
when there are three agents, a median voter scf is defined by locating two phantom peaks denote them by a1 , a2 ∈ A. At every preference profile (P1 , P2 , P3 ) ∈ S 3 , a median voter scf
chooses the alternative which is the median of (a1 , a2 , P1 (1), P2 (1), P3 (1)) according to theordering . We will argue that the location of phantom peaks a1 and a2 for f has to bedifferent (i.e., a1 6= a2 ) and both of them have to be located either at a or at b.
Note that if agent 1 has type P̄ , then for any P−1 , the outcome of f ∗ can only be a or b.
Hence, the interim allocation probability of all the alternatives except a and b are zero (seeTable 25). This means that for all c ∈/ {a, b},∗π1f (c, P̄ ) = π1f (c, P̄ ) = 0,
where the first equality followed from the weak equivalence of f and f ∗ . Now, if the locationof one of the phantom peaks of f is not in {a, b}, then when agents 2 and 3 have their top
ranked alternative outside {a, b}, because of the median property, the scf will not choose aor b. As a result, we will have π1f (c, P̄ ) > 0, contradicting the above equation. Hence, thephantom peaks must be located either at a or b.
If both the phantom peaks are located at a, then the median will be a when agent 1 has
type P̄ , irrespective of the type of agents 2 and 3. Hence, π1f (a, P̄ ) = 1. But, using Table 25∗
and weak equivalence of f and f ∗ , we can conclude that π1f (a, P̄ ) = π1f (a, P̄ ) < 1, which isa contradiction. Hence, both the phantom peaks cannot be at a.
38

Consider any preference ordering where b is top ranked - denote it by P̂ . Note that
π f (b, P̂ ) = π1f ∗ (b, P̂ ) < 1 (Table 25). In that case, if both the phantom peaks are located atb, by the median property the scf f will choose b as the outcome for any preference orderingof agents 2 and 3. Hence, π f (b, P̂ ) = 1, which is a contradiction. Hence, we conclude thatin the median voter scf f , one of the phantom peaks is located at a and the other one islocated at b.
Now, in the median voter scf f , if agent 1 has type P̄ , then f chooses a if at least
one more agent has his top ranked alternative a (this follows from the median property),i.e., at least one more agent has type P̄ . The probability of this event is exactly 1 − (1 −q2 )(1 − q3 ) = q2 + q3 − q2 q3 . Hence, we have π1f (a, P̄ ) = q2 + q3 − q2 q3 . But from Table 25,∗
π1f (a, P̄ ) = 1 − q2 − q3 + 2q2 q3 . This implies that q2 + q3 − q2 q3 = 1 − q2 − q3 + 2q2 q3 , orequivalently,
q 2 + q3 =1 + 3q2 q3
.
2

(2)

Now, consider the case where agent 1 has a type where his top ranked alternative is b as before, denote such a type as P̂ . In this case, f chooses a as the outcome if both agent
2 and agent 3 have their top ranked alternative as a (by the median property), i.e., agent
2 and agent 3 have type P̄ . The probability of this event is q2 q3 . Hence, π1f (a, P̂ ) = q2 q3 .
∗But from Table 25, π1f (a, P̂ ) = q2 + q3 − 2q2 q3 . This implies that q2 q3 = q2 + q3 − 2q2 q3 , orequivalently,
q2 + q3 = 3q2 q3 .

(3)Equations 2 and 3 give us q2 q3 = 31 and q2 + q3 = 1. But this has no real solution.
This shows that there is no DSIC, unanimous, and anonymous scf that is weakly equivalent to f ∗ .

Uniform Priors Example
Suppose A = {a, b, c} and n = 2. Consider the unrestricted domain consisting of 6 possible
types for each agent. The type profiles along with the outcome of an scf f˜ is shown in Table
26. In Table 26, a preference ordering aP bP c is written as abc. Also, the rows of Table are
preferences of agent 1 and columns of agent 2. The profiles corresponding to top four rows
and first four columns correspond to the single peaked domain (with respect to the orderinga  b  c).
The scf f˜ in Table 26 is unanimous, but not DSIC - e.g., agent 2 can manipulate when
his true type is cba and agent 1 reports abc by reporting bca (notice that the manipulation
took place inside the single peaked domain, and hence, the scf is not DSIC in the single
39

abc
a
b
b
c
a
a

abc
bac
bca
cba
acb
cab

bac
a
b
b
b
a
c

bca
b
b
b
c
a
c

cba
a
b
b
c
c
c

acb
a
a
b
c
a
c

cab
a
b
c
c
a
c

Table 26: An OBIC scf with respect to uniform priors
peaked domain also). However, this is a neutral scf satisfying elementary monotonicity - infact, f˜ is equivalent to the Borda scoring rule where the top ranked alternative gets score
2, the second ranked alternative gets score 1 and ties are broken in favor of agent 1’s top
ranked alternative. Hence, it is OBIC with respect to uniform priors in the unrestricteddomain (Majumdar and Sen, 2004).
We now consider the single peaked domain and uniform priors in the single peaked domain. Now, we calculate the interim allocation probabilities for agent 2 in the single peakeddomain from f˜. They are shown in Table 27. Now, notice that˜˜

π2f (a, abc) + π2f (b, abc) =3
˜˜< 1 = π2f (a, bac) + π2f (b, bac).
4

This implies that f˜ is not OBIC with respect to uniform priors in the single peaked domain.

˜
π2f (·, abc)˜
π2f (·, bac)˜
π2f (·, bca)˜
π2f (·, cba)

a

b

c

1
4
1
4

1
2
3
4
3
4
1
2

1
4

0
1
4

0
1
4
1
4

Table 27: Interim allocation probability of agent 2 in f˜

References
Barbera, S. (2010): “Strategy-proof Social Choice,” in Handbook of Social Choice andWelfare, ed. by K. J. Arrow, A. K. Sen, and K. Suzumura, North-Holland, 441–449.
Barbera, S., D. Berga, and B. Moreno (2010): “Individual versus group strategyproofness: when do they coincide?” Journal of Economic Theory, 145, 1648–1674.
40

Barbera, S., F. Gul, and E. Stacchetti (1993): “Generalized Median Voter Schemes
and Committees,” Journal of Economic Theory, 61, 262–289.
Bhargava, M., D. Majumdar, and A. Sen (2014): “Incentive-Compatible Voting Rules
with Positively Correlated Beliefs,” Forthcoming, Theoretical Economics.
Borgors, T. (2013): “(No) Foundations of Dominant-Strategy Mechanisms: A Comment
on Chung and Ely (2007),” Working Paper, University of Michigan.
Borgors, T. and D. Smith (2014): “Robust Mechanism Design and Dominant Strategy
Voting Rules,” Theoretical Economics, 9, 339–360.
Carroll, G. (2012): “When are local incentive constraints sufficient?” Econometrica, 80,
661–686.
Chen, Y.-C. and J. Li (2014): “Uniform Order and Foundations of Dominant-Strategy
Mechanisms,” Working Paper, National University of Singapore.
Chung, K.-S. and J. C. Ely (2007): “Foundations of Dominant-Strategy Mechanisms,”
Review of Economic Studies, 74, 447–476.
d’Aspremont, C. and B. Peleg (1988): “Ordinal Bayesian Incentive Compatible Representations of Committees,” Social Choice and Welfare, 5, 261–279.
Demange, G. (1982): “Single-peaked Orders on a Tree,” Mathematical Social Sciences, 3,
389–396.
Ehlers, L. and J. Masso (2007): “Incomplete Information and Singleton Cores in Matching Markets,” Journal of Economic Theory, 136, 587–600.
Gershkov, A., J. K. Goeree, A. Kushnir, B. Moldovanu, and X. Shi (2013): “Onthe Equivalence of Bayesian and Dominant Strategy Implementation,” Econometrica, 81,
197–220.
Gershkov, A., B. Moldovanu, and X. Shi (2014): “Optimal Voting Rules,” Working
Paper, University of Toronto.
Gibbard, A. (1973): “Manipulation of Voting Schemes: A General Result,” Econometrica,
41, 587–602.
Kim, S. (2014): “Ordinal versus Cardinal Voting Rules: A Mechanism Design Approach,”
Working Paper, National Taiwan University.

41

Kushnir, A. (2014): “On the Equivalence of Bayesian and Dominant Strategy Implementation: The Case of Correlated Types,” Working Paper.
Le Breton, M. and A. Sen (1999): “Separable preferences, strategyproofness, and decomposability,” Econometrica, 67, 605–628.
Majumdar, D. (2003): “Ordinally Bayesian Incentive Compatible Stable Matching,” Working Paper, Concordia University.
Majumdar, D. and A. Sen (2004): “Ordinally Bayesian Incentive Compatible Voting
Rules,” Econometrica, 72, 523–540.
Manelli, A. M. and D. R. Vincent (2010): “Bayesian and Dominant Strategy Implementation in the Independent Private Values Model,” Econometrica, 78, 1905–1938.
Moulin, H. (1980): “On Strategyproofness and Single-peakedness,” Public Choice, 35, 437–455.
——— (1983): The Strategy of Social Choice, North-Holland.
Saporiti, A. (2009): “Strategy-proofness and single-crossing,” Theoretical Economics, 4,
127–163.
Sato, S. (2013): “A sufficient condition for the equivalence of strategy-proofness and nonmanipulability by preferences adjacent to the sincere one,” Journal of Economic Theory,
148, 259–278.
Satterthwaite, M. (1975): “Strategy-proofness and Arrow’s Conditions: Existence andCorrespondence Theorems for Voting Procedures and Social Welfare Functions,” Journalof Economic Theory, 10, 187–217.

42