HIAS-E-47

Treading a fine line: (Im)possibilities for Nash
implementation with partially-honest individualsMichele Lombardi
Adam Smith Business School, University of Glasgow, Glasgow, G12 8QQ, United Kingdom

Naoki Yoshihara
University of Massachusetts Amherst, Crotty Hall, 412 North Pleasant Street, Amherst, MA 01002, USA
The Institute of Economic Research, Hitotsubashi University, Naka 2-1, Kuni- tachi, Tokyo 186-8603, Japan
School of Management, Kochi University of Technology, Tosayamada, Kami-city, Kochi 782-8502, Japan

July 2017

Hitotsubashi Institute for Advanced Study, Hitotsubashi University
2-1, Naka, Kunitachi, Tokyo 186-8601, Japan
tel:+81 42 580 8604
http://hias.ad.hit-u.ac.jp/
HIAS discussion papers can be downloaded without charge from:http://hdl.handle.net/10086/27202
https://ideas.repec.org/s/hit/hiasdp.html

All rights reserved.

Treading a fine line: (Im)possibilities for Nash
implementation with partially-honest individuals∗
M. Lombardi†
University of Glasgow

N. Yoshihara‡
University of Massachusetts Amherst
July 5, 2017

Abstract
This paper investigates the robustness of Dutta and Sen’s (2012) Theorem 1 to weaker
notions of truth-telling. An individual honesty standard is modeled as a subgroup of
the society, including the individual herself, for which she feels truth-telling concerns.
An individual i is honest when she states her true preferences as well as rankings(not necessarily complete) of outcomes that are consistent with the true preferences ofindividuals in her honesty standard. The paper o§ers a necessary condition for Nash
implementation, called partial-honesty monotonicity, and shows that in an independent
domain of preferences that condition is equivalent to Maskin monotonicity.
JEL classification: C72; D71; D82.
Keywords: Nash implementation; partial-honesty; non-connected honesty standards,
independent domain.

∗
Special thanks go to Luis Corchón and Hans Peters, whose comments and suggestions have led to
substantial improvements in the paper. We are also grateful to an associate editor and a referee of this journal
for their helpful and thoughtful comments and suggestions. They are not responsible for any remaining
deficiencies.
†
Corresponding author: Michele Lombardi, Adam Smith Business School, University of Glasgow, Glasgow,
G12 8QQ, United Kingdom, e-mail: michele.lombardi@glasgow.ac.uk.
‡
Department of Economics, University of Massachusetts Amherst, Crotty Hall, 412 North Pleasant Street,
Amherst, MA 01002, USA; The Institute of Economic Research, Hitotsubashi University, Naka 2-1, Kunitachi, Tokyo 186-8603, Japan; and School of Management, Kochi University of Technology, Tosayamada,Kami-city, Kochi 782-8502, Japan. E-mail: nyoshihara@econs.umass.edu

1. Introduction
The implementation problem is the problem of designing a mechanism or game form
with the property that for each profile of participants’ preferences, the equilibrium outcomesof the mechanism played with those preferences coincide with the recommendations that agiven social choice rule (SCR) would prescribe for that profile. If that mechanism design
exercise can be accomplished, the SCR is said to be implementable. The fundamental paper
on implementation in Nash equilibrium is thanks to Maskin (1999; circulated since 1977), whoproves that any SCR that can be Nash implemented satisfies a remarkably strong invariancecondition, now widely referred to as Maskin monotonicity. Moreover, he shows that whenthe mechanism designer faces at least three individuals, a SCR is Nash implementable if it
is Maskin monotonic and satisfies the condition of no veto-power, subsequently, Maskin’s
theorem. Maskin (1999) obtains his original result by means of a mechanism that requires
each individual to report, besides two auxiliary data, the whole description of the state.
In a preference model, this means that each participant is asked to report preferences thatmembers of the society have (preference profile).
Since Maskin’s theorem, economists have also been interested in understanding how tocircumvent the limitations imposed by Maskin monotonicity by exploring the possibilitieso§ered by approximate (as opposed to exact) implementation (Matsushima, 1988; Abreu
and Sen, 1991), as well as by implementation in refinements of Nash equilibrium (Moore andRepullo, 1988; Abreu and Sen, 1990; Palfrey and Srivastava, 1991; Jackson, 1992) and by
repeated implementation (Kalai and Ledyard, 1998; Lee and Sabourian, 2011; Mezzetti andRenou, 2016). One additional way around those limitations is o§ered by implementation
with partially-honest individuals.
A partially-honest individual is an individual who deceives the mechanism designer when
the truth poses some obstacle to her material well-being. Thus, she does not deceive when
the truth is equally e¢cacious. Simply put, a partially-honest individual follows the maxim,“Do not lie if you do not have to” to serve her material interest.
In a general environment, a seminal paper on Nash implementation problems involving partially-honest individuals is Dutta and Sen (2012), whose Theorem 1 (p. 157) showsthat for implementation problems involving at least three individuals and in which there is atleast one partially-honest individual, the Nash implementability is assured by no veto-power.
Similar positive results are uncovered in other environments by Matsushima (2008a,b), Kartik and Tercieux (2012), Kartik et al. (2014), Lombardi and Yoshihara (2016b,c), Saporiti(2014) and Ortner (2015). Thus, there are far fewer limitations for Nash implementation
when there are partially-honest individuals.1
1
A pioneering work on the impact of decency constraints on Nash implementation problems is Corchónand Herrero (2004). These authors propose restrictions on sets of strategies available to agents that depend1

As in Maskin’s (1999) original result, Dutta and Sen’s (2012) Theorem 1 uses a mechanism that asks participants to report, among two auxiliary data, the whole preference profile.
Moreover, according to Dutta and Sen’s (2012) definition of honesty, a participant’s play ishonest if she plays a strategy choice which is veracious in its preference profile announcement
component. In this paper, we consider weaker notions of honesty and then investigate therobustness of Dutta and Sen’s (2012) Theorem 1 to these notions of truth-telling.
Under a general arbitrary definition of truth-telling, the paper shows that any SCR
that can be Nash implemented with partially-honest individuals satisfies a variant of Maskin
monotonicity, called partial-honesty monotonicity. First, this condition requires that a deviant is able to find a set of truthful outcomes for θ0 when x is one of the outcomes selectedby a given SCR at state θ and the state moves from θ to θ0 . Second, it prescribes that fora deviant partially-honest individual h the set of truthful strategy choices for θ di§ers fromthat for θ0 if this deviant h can find a truthful outcome z for θ0 that is equally good to x
according to her ordering Rh (θ), under the presumption that this x is one of the outcomesselected by the given SCR at state θ but is not selected at θ0 , there is a monotonic change ofpreferences around x from θ to θ0 and, moreover, this deviant h can find a truthful outcome
z 0 for θ0 that is equally good to x according to her ordering Rh (θ0 ).
The condition is always satisfied since it always allows the case that honesty means
reporting the true state of the world - as in Dutta and Sen (2012). This implies that if
one would like to derive a Maskin monotonicity-type condition as a necessary condition that
imposes restrictions on the class of implementable SCRs, it is bound to give a weaker meaning
to the notion of honesty. Clearly, its notion needs to be compatible with the implementation
environment as well as be based on testable parameters.
Since the main goal of this study is to o§er notions of honesty that are weaker than that
employed by Dutta and Sen (2012) and then to investigate the robustness of their result
to these notions, we model individual i’s honesty standard, denoted by S (i), as a profile
of (possibly non-empty) collections of ordered pairs of outcomes, one for each member ofsociety, over which individual i feels truth-telling concerns. We write S (N ) ≡ (S (i))i2N fora typical honesty standard of society.
This notion of individual i’s honesty standard is flexible enough to allow the individual
i’s collection for individual j to be empty. Our interpretation is that in this case individual
i does not have any truth-telling concern about individual j. We also adopt the view that
individual i concerns herself with at least her own self; that is, her own collection of orderedpairs is not empty. Also, we require that the collection over which individual i feels truthtelling concerns about herself has the property that she is able to reveal truthfully her own
on the state of the world. They refer to these strategies as decent strategies and study Nash implementation problems in decent strategies. For a particular formulation of decent strategies, they are also able tocircumvent the limitations imposed by Maskin monotonicity.

2complete ranking of outcomes. This requirement turned to be an indispensable condition forhonesty under which a Maskin monotonicity-type condition for Nash implementation can bederived as a necessary condition (details are in Remark 2).
Thus, an individual i is honest provided that she states her true preferences as well as
rankings (not necessarily complete) of outcomes that are consistent with the true preferencesof individuals in her honesty standard. It is worth emphasizing that this notion of truthtelling encompasses, as a special case, that of Dutta and Sen (2012).
With these notions of honesty and honesty standards, the paper shows that any SCR
that can be Nash implemented with partially-honest individuals satisfies a variant of Maskin
monotonicity, called S (N )-partial-honesty monotonicity. The idea of this axiom is quite
intuitive. If x is one of the outcomes selected by a given SCR at state θ but is not selected
when there is a monotonic change of preferences around x from θ to θ0 , then the rankingsof outcomes in the honesty standard of a partially-honest individual has been altered bythis monotonic change. This condition implies partial-honesty monotonicity - indeed, they
are equivalent under some qualifications. Furthermore, it is trivially satisfied when partiallyhonest individuals concern themselves with the announcement of the whole preference profile
as in Dutta and Sen (2012). However, it can have more bite when weaker notions of honesty
are considered.
Indeed, in section 5, a specific type of an individual honesty standard is considered,
which is modeled as a subset of individuals involved in an implementation problem. Ourinterpretation is that participant i concerns herself with the truth-telling of individuals in
her honesty standard when she plays a strategy choice. Also, this definition endorses theview that an individual concerns herself with at least her own self. Thus, an individual i istruthful provided that she states the true preferences of individuals in her honesty standard.
Moreover, we consider what we call non-connected honesty standards. Simply put, individualhonesty standards are connected if some participant is in the honest standard of every otherparticipant. When that is not the case, we call them non-connected honesty standards.
In other words, they are non-connected if every participant is excluded from the honesty
standard of another participant.
In an independent domain of preferences, where the set of the profiles of participants’
preferences takes the structure of the Cartesian product of individual preferences, we showthat S (N )-partial-honesty monotonicity is equivalent to Maskin monotonicity whenever
there exists at least one partially-honest individual and individuals’ honesty standards are
non-connected. Thus, under those hypotheses, Maskin’s theorem provides an almost complete characterization of SCRs that are Nash implementable in the society with partiallyhonest individuals.
The remainder of the paper is divided into five sections. Section 2 presents the theoret-3

ical framework and outlines the implementation model. Section 3 presents partial-honesty
monotonicity, with the notions of truth-telling and of an honesty standard presented in subsection 3.1. Section 4 presents S (N )-partial-honesty monotonicity, with the equivalence
result o§ered in section 5. Section 6 concludes.

2. Preliminaries
2.1 Basic framework
We consider a finite set of individuals indexed by i 2 N = {1, · · · , n}, which we will referto as a society. The set of outcomes available to individuals is X. The information held by
the individuals is summarized in the concept of a state. Write Θ for the domain of possible
states, with θ as a typical state. In the usual fashion, individual i’s preferences in state θ aregiven by a complete and transitive binary relation, subsequently an ordering, Ri (θ) over theset X. The corresponding strict and indi§erence relations are denoted by Pi (θ) and Ii (θ),
respectively. The preference profile in state θ is a list of orderings for individuals in N thatare consistent with this state and is denoted by RN (θ).
We assume that the mechanism designer does not know the true state. We assume,
however, that there is complete information among the individuals in N and that the mechanism designer knows the preference domain consistent with the domain Θ. In this paper,
sometimes we identify states with preference profiles.
The goal of the mechanism designer is to implement a social choice rule (SCR) F :Θ ! X where F (θ) is non-empty for any θ 2 Θ. We shall refer to x 2 F (θ) as an F optimal outcome at θ. Given that individuals will have to be given the necessary incentives
to reveal the state truthfully, the mechanism! designer delegates the choice to individualsYaccording to a mechanism Γ ≡Mi , g , where Mi is the strategy space of individual ii2NYand g : M ! X, the outcome function, assigns to every strategy profile m 2 M ≡
Mi a
i2N

unique outcome in X. We shall sometimes write (mi , m−i ) for the strategy profile m, wherem−i = (m1 , · · · , mi−1 , mi+1 , · · · , mn ).

2.2 Intrinsic preferences for honesty
An individual who has an intrinsic preference for truth-telling can be thought of as anindividual who is torn by a fundamental conflict between her deeply and ingrained propensity
to respond to material incentives and the desire to think of herself as an honest person. In
this paper, the theoretical construct of the balancing act between those contradictory desires4

is based on two ideas.
First, the pair (Γ, θ) acts as a “context” for individuals’ conflicts. The reason for thisis that an individual who has an intrinsic preference for honesty can categorize her strategy
choices as truthful or untruthful relative to the state θ and the mechanism Γ designed by
the mechanism designer to govern the communication with individuals. That categorization
can be captured by the following notion of truth-telling correspondence:
Definition 1 For each Γ and each individual i 2 N , individual i’s truth-telling correspondence is a (non-empty) correspondence TiΓ : Θ ! Mi such that, for each θ 2 Θ andmi 2 TiΓ (θ), the strategy choice mi encodes information that is consistent with the state θ.
Strategy choices in TiΓ (θ) will be referred to as truthful strategy choices for θ.
Second, in modeling intrinsic preferences for honesty, we endorse the notion of partiallyhonest individuals introduced by Dutta and Sen (2012). First, a partially-honest individual
is an individual who responds primarily to material incentives. Second, she strictly prefers
to tell the truth whenever lying has no e§ect on her material well-being. That behavioral
choice of a partially-honest individual can be modeled by introducing an individual’s ordering over the strategy space M which contains the information of this individual’s orderingover X, because that individual’s preference between being truthful and being untruthfulis contingent upon announcements made by other individuals as well as the outcome(s) obtained from them. By following standard conventions of orderings, write <Γ,θfor individuali
i’s ordering over M in state θ whenever she is confronted with the mechanism Γ. Formally,
our notion of a partially-honest individual is as follows:
Definition 2 For each Γ, individual i 2 N is partially-honest if for all θ 2 Θ individual i’s
intrinsic preference for honesty <Γ,θon M satisfies the following properties: for all m−i andi0
all mi , mi 2 Mi it holds that:(i) If mi 2 TiΓ (θ), m0i 2/ TiΓ (θ) and g (m) Ri (θ) g (m0i , m−i ), then m ≻Γ,θ(m0i , m−i ).
i(ii) In all other cases, m <Γ,θ(m0i , m−i ) if and only if g (m) Ri (θ) g (m0i , m−i ).
iAn intrinsic preference for honesty of individual i is captured by the first part of the above
definition, in that, for a given mechanism Γ and state θ, individual i strictly prefers thestrategy profile (mi , m−i ) to (m0i , m−i ) provided that the outcome g (mi , m−i ) is at least as
good as g (m0i , m−i ) according to her ordering Ri (θ) and that mi is truthful for θ and m0i is
not truthful for θ.
If individual i is not partially-honest, this individual cares for her material well-being
associated with outcomes of the mechanism and nothing else. Then, individual i’s orderingover M is just the transposition into space M of individual i’s relative ranking of outcomes.
More formally:5

Definition 3 For each Γ, individual i 2 N is not partially-honest if for all θ 2 Θ, individual
i’s intrinsic preference for honesty <Γ,θon M satisfies the following property:im <Γ,θ
m0 () g (m) Ri (θ) g (m0 ) , for all m, m0 2 M .
i

2.3 Implementation problems
In formalizing the mechanism designer’s problem with partially-honest individuals, wefirst introduce an informational assumption and discuss its implications for our analysis. It
is:Assumption 1 There exists at least one partially-honest individual in the society N .
Thus, in our setting, the mechanism designer only knows the set Θ as well as thefact that there is at least one partially-honest individual among the individuals, but she
does not know either the true state or the identity (or identities) of the partially-honest
individual(s). Indeed, the mechanism designer cannot exclude any member(s) of society
from being partially-honest purely on the basis of Assumption 1. Therefore, the following
considerations are in order from the viewpoint of the mechanism designer.
An environment is described by two parameters, (θ, H): a state θ and a conceivable setof partially-honest individuals H. We denote by H a typical conceivable set of partiallyhonest individuals in N , with h as a typical element, and by H the class of conceivable setsof partially-honest individuals.
$%
A mechanism Γ and an environment (θ, H) induce a strategic game Γ, <Γ,θ,H , where:&'<Γ,θ,H ≡ <Γ,θii2N

is a profile of orderings over the strategy space M as formulated in Definition 2 and in
Definition 3. Specifically, <Γ,θis individual i’s ordering over M as formulated in Definitioni
2 if individual i is in H, whereas it is the individual i’s ordering over M as formulated in
Definition 3 if individual i is not in H.
$%
A (pure strategy) Nash equilibrium of the strategic game Γ, <Γ,θ,H is a strategy profilem such that for all i 2 N , it holds thatm <Γ,θ
(m0i , m−i ) , for all m0i 2 Mi .
i
$
%
$
%
Write N E Γ, <Γ,θ,H for the set of Nash equilibrium strategies of the strategic game Γ, <Γ,θ,H$%
and N A Γ, <Γ,θ,H for its corresponding set of Nash equilibrium outcomes.
6

The following definition is to formulate the designer’s Nash implementation problem
involving partially-honest individuals.
Definition 4 Let Assumption 1 hold. A mechanism Γ partially-honestly Nash implementsa SCR F : Θ ! X provided that for all θ 2 Θ there exists a truth-telling correspondenceTiΓ (θ) as formulated in Definition 1 for every i 2 N and, moreover, it holds that$%
F (θ) = N A Γ, <Γ,θ,H , for every pair (θ, H) 2 Θ × H.

If such a mechanism exists, F is said to be partially-honestly Nash implementable.
The objective of the mechanism designer is thus to design a mechanism whose Nashequilibrium outcomes coincide with F (θ) for each state θ as well as each set H. Note that
there is no distinction between the above formulation and the standard Nash implementation
problem as long as Assumption 1 is discarded.

3. Why is a notion of truth-telling needed?
In this section, we present a necessary condition for partially-honest implementation,
which we call partial-honesty monotonicity. This condition prescribes that for a deviant
partially-honest individual h (2 H) the set of truthful strategy choices for θ di§ers from thatfor θ0 if this individual h can find a truthful outcome z for the state θ0 that is equally good to x
according to her ordering Rh (θ) and provided that x is F -optimal at θ but not F -optimal atθ0 , that there is a monotonic change of preferences around x from θ to θ0 and that this deviant
h can find a truthful outcome z 0 for θ0 that is equally good to x according to her ordering
Rh (θ0 ). Let us formalize the condition as follows. Given a state θ, an individual i, and an
outcome x 2 X, the weak lower contour set of Ri (θ) at x is Li (θ, x) ≡ {x0 2 X|xRi (θ) x0 };and the indi§erent contour set of Ri (θ) at x is Ii (θ, x) ≡ {x0 2 X|xIi (θ) x0 }. Therefore:
Definition 5 A SCR F : Θ ! X is partial-honesty monotonic provided that for eachindividual i 2 N , there exist a (non-empty) set Ai and a (non-empty) correspondence Ti :
Θ ! Ai such that for all H 2 H and all θ, θ0 2 Θ, if x 2 F (θ) \F (θ0 ) and Li (θ, x) ⊆ Li (θ0 , x)
for each i 2 N , then for at least one h 2 H there exists a (non-empty) set Sh (θ0 ; x, θ) ⊆Lh (θ, x) such that Sh (θ0 ; x, θ) \ Ih (θ0 , x) 6= ? holds, and:Sh (θ0 ; x, θ) \ Ih (θ, x) 6= ? =) Th (θ) 6= Th (θ0 ) .
Let us give an intuitive explanation of the set Si (θ0 ; x, θ). Suppose that F is partiallyhonestly Nash implementable. Suppose that x = g (m) is F -optimal at θ, that is, x 2 F (θ).
7

Whilst the set g (Mi , m−i ) represents the set of outcomes that individual i can generate
by varying her own strategy, keeping the other individuals’ equilibrium strategy choices$%
fixed at m−i , the set Si (θ0 ; x, θ) = g TiΓ (θ0 ) , m−i represents the set of outcomes that thisindividual can attain by playing truthful strategy choices for θ0 when the state moves fromθ to θ0 , keeping the other individuals’ equilibrium strategy choices fixed at m−i . Given thisidea of the set of Si (θ0 ; x, θ), we refer to elements of Si (θ0 ; x, θ) as truthful outcomes forindividual i at the state θ0 when the state moves from θ to θ0 and x is an F -optimal outcomeat θ.
Our first main result is that only partial-honesty monotonic SCRs are partially-honestly
Nash implementable.
Theorem 1 Let Assumption 1 be given. A SCR F : Θ ! X is partial-honesty monotonic
if it is partially-honestly Nash implementable.
Proof. Let Assumption 1 be given. Suppose that Γ ≡ (M, g) partially-honestly Nash
implements the SCR F : Θ ! X. Thus, for all θ̄ 2 Θ there exists a (non-empty) truth$ %telling correspondence T&iΓ θ̄ as formulated
in Definition 1 for every i 2 N and, moreover, it
'
$ %
$
%
Γ,θ̄,Hholds that F θ̄ = N A Γ, <for every pair θ̄, H 2 Θ × H. Thus, for each individual

i, let us define the set Ai by Ai = Mi and the correspondence Ti by Ti = TiΓ .
$%Fix any (θ, H) 2 Θ × H such that x 2 F (θ). Thus, there is m 2 N E Γ, <Γ,θ,H suchthat g (m) = x.
Consider any state θ0 2 Θ such thatfor all i 2 N and all x0 2 X : xRi (θ) x0 =) xRi (θ0 ) x0 .

(1)

If there exists an individual i 2 N such that g (m0i , m−i ) Pi (θ0 ) g (m), then, from (1),g (m0i , m−i ) Pi (θ) g (m) ,$%a contradiction of the fact that m 2 N E Γ, <Γ,θ,H . Therefore, we conclude thatfor all i 2 N and all m0i 2 Mi : g (m) Ri (θ0 ) g (m0i , m−i ) .

(2)

Suppose that x 2/ F (θ0 ). Then, the strategy profile m is not a Nash equilibrium for%0
Γ, <Γ,θ ,H ; that is, there exists an individual i 2 N who can find a strategy choice m0i 2 Mi
0such that (m0i , m−i ) ≻Γ,θm. Given that (2) holds, it must be the case that i 2 H. Fromipart (i) of Definition 2 we conclude, therefore, that$mi 2
/ TiΓ (θ0 ) and m0i 2 TiΓ (θ0 )(3)8and thatg (m0i , m−i ) Ri (θ0 ) g (m) .

(4)

For this i 2 H, let us define the set Si (θ0 ; x, θ) by$%
Si (θ0 ; x, θ) = g TiΓ (θ0 ) , m−i .

(5)

It is plain that this set is not empty - since TiΓ (θ0 ) is not empty - and that Si (θ0 ; x, θ) ⊆Li (θ, x). Moreover, by (2) and (4), individual i is indi§erent between g(m) and g (m0i , m−i ),and by (3) and (5), g (m0i , m−i ) is an element of Si (θ0 ; x, θ). Thus, g (m0i , m−i ) 2 Si (θ0 ; x, θ) \Ii (θ0 , x), which implies Si (θ0 ; x, θ) \ Ii (θ0 , x) 6= ?.
To show the remaining property, we use a proof by contrapositive here. Assume that
ΓTi (θ0 ) = TiΓ (θ). Suppose that there is a w 2 X such that w 2 Si (θ0 ; x, θ) \ Ii (θ, x). Thus,
by definition of Si (θ0 ; x, θ) in (5), it follows that there exists m00i 2 TiΓ (θ0 ) = TiΓ (θ) such thatg (m00i , m−i ) = w and thatg (m00i , m−i ) Ii (θ) g (m) .
(6)
Furthermore, since TiΓ (θ0 ) = TiΓ (θ), it follows from (3) that mi 2
/ TiΓ (θ). Given that (6)holds, from part (i) of Definition 2 we conclude, therefore, that m is not a Nash equilibrium$%for Γ, <Γ,θ,H , which is a contradiction. Then, the intersection Si (θ0 ; x, θ) \ Ii (θ, x) needs
to be empty, and so F is partial-honesty monotonic.
It is worth emphasizing that the above condition does not impose any restriction on theclass of SCRs that are partially-honestly Nash implementable. This is so because for any
θ, θ0 2 Θ with x 2 F (θ) \F (θ0 ), the set Si (θ0 ; x, θ) can be defined as Si (θ0 ; x, θ) = Li (θ, x)
for each i 2 N , and there always exists an individual i’s correspondence Ti defined byTi (θ) = {θ} for each θ 2 Θ, for each i 2 N , under which Ti (θ) 6= Ti (θ0 ) always holds for any
θ, θ0 2 Θ with θ 6= θ0 . This is consistent with Theorem 1 of Dutta and Sen (2012), according
to which the partially-honest Nash implementability is assured by no veto-power when to behonest means to report the true state of the world.
Corollary 1 Every SCR F : Θ ! X is partial-honesty monotonic.
However, the condition may be stringent when for each individual i, the value of thecorrespondence Ti is constrained by a weaker notion of honesty: for any admissible corrrespondence profile (Ti )i2N , there exist θ 2 Θ and j 2 N such that Tj (θ) 6= {θ}. This will be
the subject of what follows below.

93.1 Truth-telling and honesty standards
The main practical aim of adopting an axiomatic approach to Nash implementation
theory is to distinguish between implementable and non-implementable SCRs. Thus, theimportance and usefulness of a necessary condition for implementation relies on its testability. This means that it has to involve only observable parameters such as preferences andoutcomes.
Furthermore, the seminal result of Dutta and Sen (2012) requires that an individual’sreport is truthful when it conveys the true preferences of individuals. However, since thegoal of this paper is to check the robustness of this seminal result to weaker notions of truthtelling, we adopt the view that an individual i is truthful when she states her true preference
as well as rankings (not necessarily complete) of outcomes that are consistent with the true
preferences of individuals for whom this individual i feels truth-telling concerns.
Let us formalize our notions of truth-telling as well as individuals’ honesty standards.
Let the family X have as elements all non-empty subsets of the space X × X as well as
the set whose element is the empty set. As usual, let us denote by X n the n-fold Cartesian
product of the family X .
An honesty standard of individual i, denoted by S (i) ≡ (Sj (i))j2N , is an element of X n(that is, S (i) 2 X n ). Whilst our interpretation of the set Sj (i) = {?j } is that individual
i does not have any truth-telling concern about individual j, our interpretation of the set
Sj (i) 6= {?j } is that individual i concerns herself about individual j and the set Sj (i)represents the collection of ordered pairs over which this i feels truth-telling concerns - when
she plays a strategy choice. An honesty standard of society is a list of honesty standards for
all members of society. Write S (N ) ≡ (S (i))i2N for a typical honesty standard of society.
We adopt the view that individual i concerns herself with at least her own self; that
is, Si (i) 6= {?i }. Moreover, the collection Si (i) of ordered pairs over which she feels truthtelling concerns has the property that this i is able to reveal truthfully her complete rankingof outcomes; formally, we adopt the view that S (i) is an honesty standard of individual iprovided that
Si (i) \ Ri (θ) = Ri (θ) for all θ 2 Θ.
(7)
The indispensability of these requirements for the honesty standard of individual i will be
discussed in Remark 2. Our interpretation of these requirements is that individual i, toview herself as an honest person, has at least to concern herself with the truth-telling of her
own preference ordering. This also means that individual i may display an honesty standard
which allows her to hide partially or totally other individuals’ rankings over outcomes withoutthat being harmful to her self view as an honest person.
Let us observe that this formulation of an honesty standard satisfies important proper-

10

ties. First, it does not depend on the current state of the world. Second, it is also independentof the social objectives that society or its representatives want to achieve. Last but not least,
our formulation of honesty standards do not hinge on the existence of any mechanism. All
in all, it has the property to be formulated only on observable parameters.
We are now in a position to state our notion of truth-telling. Formally, for a given
state θ and individual i’s honesty standard S (i), to save notation we write RN (θ) \ S (i) forRj (θ) \ Sj (i) for each individual j. Thus:
Definition 6 For each Γ and each individual i 2 N with an honesty standard S (i) satisfying the requirement in (7), individual i’s truth-telling correspondence is a (non-empty)
correspondence TiΓ (·; S (i)) : Θ ! Mi with the property that for any two states θ and θ0 , itholds thatTiΓ (θ; S (i)) = TiΓ (θ0 ; S (i)) () RN (θ) \ S (i) = RN (θ0 ) \ S (i) .

(8)Strategy choices in TiΓ (θ; S (i)) will be referred to as truthful strategy choices for θ according
to S (i).
According to the above definition, in a state θ, every truthful strategy choice of individual i is to encode information of individuals’ rankings of outcomes that are consistent
with the profile of individuals’ orderings at the state θ. Moreover, if in two di§erent states,say θ and θ0 , it holds that for each individual j, the set of ordered pairs in Sj (i) that areconsistent with individual j’s ordering at θ is identical to the set of ordered pairs that areconsistent with individual j’s ordering at θ0 (that is, Rj (θ) \ Sj (i) = Rj (θ0 ) \ Sj (i)), thenthe sets of individual i’s truthful strategy choices for those two states need to be identicalaccording to her honesty standard S (i).
The above definition of truth-telling imposes a mild restriction on the class of truthtelling correspondences and, perhaps more interestingly, it represents a minimal notion ofhonesty that one can formulate in our general environment. It is vital to emphasize herethat our notion of veracity encompasses, as a special case, that of Dutta and Sen (2012)
when each individual i’s honesty standard S (i) is such that Sj (i) \ Rj (θ) = Rj (θ) for every
individual j and every state θ.

4. S (N )-partial-honesty monotonicity
In this section, we discuss a condition, called S (N )-partial-honesty monotonicity, thatis necessary for the partially-honest Nash implementation when the honesty standard ofsociety is prescribed by S (N ). We also show that this condition implies partial-honesty
11monotonicity. Moreover, for any given honesty standard of society summarized in S (N ),the two conditions are equivalent when each individual i’s correspondence Ti presented in
Definition 5 is required to be consistent with S (N ) (see below).
A condition that is central to the implementation of SCRs in Nash equilibrium is Maskin
monotonicity. This condition says that if an outcome x is F -optimal at the state θ, and thisx does not strictly fall in preference for anyone when the state is changed to θ0 , then x mustremain an F -optimal outcome at θ0 . Let us formalize that condition as follows:
Definition 7 A SCR F : Θ ! X is Maskin monotonic provided that for all x 2 X and allθ, θ0 2 Θ, if x 2 F (θ) and Li (θ, x) ⊆ Li (θ0 , x) for all i 2 N , then x 2 F (θ0 ).
An equivalent statement of Maskin monotonicity stated above follows the reasoningthat if x is F -optimal at θ but not F -optimal at θ0 , then the outcome x must have fallen
strictly in someone’s ordering at the state θ0 in order to break the Nash equilibrium via somedeviation. Therefore, there must exist some (outcome-)preference reversal if an equilibrium
strategy profile at θ is to be broken at θ0 .
Our variant of Maskin monotonicity for Nash implementation problems involving partiallyhonest individuals when the standard of honesty in a society is represented by S (N ) can beformulated as follows:
Definition 8 A SCR F : Θ ! X is S (N )-partial-honesty monotonic given the standard
S (N ) (satisfying the requirement in (7) for each individual i) provided that for all x 2 X,
all H 2 H and all θ, θ0 2 Θ, if x 2 F (θ) \F (θ0 ) and Li (θ, x) ⊆ Li (θ0 , x) for all i 2 N , thenthere exists at least one h 2 H such that RN (θ) \ S (h) 6= RN (θ0 ) \ S (h).
This says that if x is F -optimal at θ but not F -optimal at θ0 and, moreover, there isa monotonic change of preferences around x from θ to θ0 (that is, whenever xRi (θ) x0 , one
has that xRi (θ0 ) x0 ), then the rankings of outcomes in the honesty standard of a partiallyhonest individual h has been altered by this monotonic change (that is, RN (θ) \ S (h) 6=
RN (θ0 ) \ S (h)). Stated in the contrapositive, this says that if x is F -optimal at θ and there
is a monotonic change of preferences around x from θ to θ0 and, moreover, the rankings ofoutcomes in the honesty standard of every partially-honest individual h in H has not beenaltered by this monotonic change, then x must continue to be one of the outcomes selectedby F at the state θ0 .
Remark 1 Note that if each individual i’s honesty standard S (i) is such that Sj (i) \Rj (θ) = Rj (θ), for every individual j and every state θ, and if x is F -optimal at θ but not
F -optimal at θ0 and it happens that the lower contour sets of preferences at x are nested forevery agent across the two environments, then one has that RN (θ) 6= RN (θ0 ). Thus, any
12

SCR is S (N )-partial-honesty monotonic whenever the honesty standard of society is thatstudied by Dutta and Sen (2012).
The above condition is necessary for partially-honest Nash implementation. This isbecause if x is F -optimal at θ but not F -optimal at θ0 and, moreover, the outcome x has
not fallen strictly in any individual’s ordering at the state θ0 , then only a partially-honest
individual in the given conceivable set H can break the Nash equilibrium via a unilateraldeviation. Therefore, there must exist a partially-honest individual h 2 H whose equilibrium
strategy to attain x at (θ, S (N ) , H) is not a truthful strategy choice at (θ0 , S (N ) , H). Thismeans that RN (θ) \ S (h) 6= RN (θ0 ) \ S (h), according to Definition 6.
Note that the above definitions of partially-honest individuals (that is, Definition 2) aswell as of partially-honest Nash implementation can be easily adapted to the environmentswith honesty standards. Now, a mechanism Γ and an environment with honesty standards$%(θ, S (N ) , H) induces a strategic game Γ, <Γ,θ,S(N ),H , where:&'
Γ,θ,S(i)<Γ,θ,S(N ),H ≡ <ii2N

is a profile of orderings over the strategy space M as formulated in Definition 2 and in Definition 3 where the truth-telling correspondence of individual i is that provided in Definition
6. Moreover, our notion of implementation in an environment with honesty standards canbe stated as follows:
Definition 9 Let Assumption 1 be given. Let the honesty standard of society be summarized in S (N ). A mechanism Γ partially-honestly Nash implements a SCR F : Θ ! X
provided that for all θ 2 Θ and H 2 H there exists for any h 2 H a truth-tellingcorrespondence ThΓ (θ; S (h)) as formulated in Definition 6 and, moreover, it holds that$%
F (θ) = N A Γ, <Γ,θ,S(N ),H . If such a mechanism exists, F is said to be partially-honestly
Nash implementable.
Therefore, our second main result can be stated as follows:
Theorem 2 Let Assumption 1 be given. Let the honesty standard of society be summarizedin S (N ). A SCR F : Θ ! X is S (N )-partial-honesty monotonic given the standard S (N )if it is partially-honestly Nash implementable.
Proof. Let Assumption 1 be given. Let the honesty standard of society be summarized in
S (N ). Suppose that Γ ≡ (M, g) partially-honestly Nash implements the SCR F : Θ ! X.
This proof is almost identical to the proof of Theorem 1 up to equation (4). We thus urge
the reader to consult that part of the proof before reading what follows.

13

Therefore, the premises of the condition are met. Moreover, note that (2) and (4) jointly
imply thatg (m0i , m−i ) Ii (θ0 ) g (m) .
(9)
We show that RN (θ) \ S (i) 6= RN (θ0 ) \ S (i). Assume, to the contrary, thatfor all h 2 H : RN (θ) \ S (h) = RN (θ0 ) \ S (h) .

(10)Definition 6 implies thatfor all h 2 H : ThΓ (θ; S (h)) = ThΓ (θ0 ; S (h)) .

(11)

Given that (3) is equivalent tomi 2/ TiΓ (θ0 ; S (i)) and m0i 2 TiΓ (θ0 ; S (i)) ,(11) implies thatmi 2
/ TiΓ (θ; S (i)) and m0i 2 TiΓ (θ; S (i)) .

(12)

Furthermore, given that requirement (7) holds, (9) and (10) jointly imply that Ri (θ) = Ri (θ0 )and thatg (m0i , m−i ) Ii (θ) g (m) .
(13)
Γ,θ,S(i)Given (12) and (13) and the fact that i 2 H, Definition 2 implies that (m0i , m−i ) ≻im,$%Γ,θ,S(N ),H
which is a contradiction of the fact that m 2 N E Γ, <. Thus, F is S (N )-partialhonesty monotonic given the honesty standard S (N ).
Remark 2 The necessity of the S (N )-partial-honesty monotonicity for partially-honest
Nash implementation relies on the requirement that every individual to view herself as anhonest person has at least to concern herself with the truth-telling of her own preference
ordering (that is, on the requirement in (7)). Indeed, if this requirement fails to hold, then it
would not be possible to conclude in (13) that individual i judges the outcomes g (m0i , m−i )and g (m) as equally good according to her preference ordering at the state θ, and so it would
not be possible to conclude that this i can break the Nash equilibrium strategy profile m at
the state θ via a unilateral deviation. From this perspective, we view this requirement as asu¢cient condition for honesty under which a Maskin monotonicity-type condition can bederived as a necessary condition for partially-honest Nash implementation.
Furthermore, S (N )-partial-honesty monotonicity implies partial-honesty monotonicity,
as we show next.
14

Theorem 3 If a SCR F : Θ ! X is S (N )-partial-honesty monotonic, then it is partialhonesty monotonic.
Proof. Assume that the SCR F : Θ ! X is S (N )-partial-honesty monotonic. We show that
it is partial-honesty monotonic too. For each individual i, let us define the set Ai by Ai = X n
and the correspondence Ti : Θ ! Ai by Ti (θ) = RN (θ) \ S (i), for all θ 2 Θ. Furthermore,for each individual i, for each θ such that x 2 F (θ) and each θ0 , let us define the set
Si (θ0 ; x, θ) by Si (θ0 ; x, θ) = Li (θ, x). Thus, for each individual i, Si (θ0 ; x, θ) \ Ii (θ0 , x) 6= ?,and x 2 Si (θ0 ; x, θ) \ Ii (θ, x) holds for all θ and θ0 with x 2 F (θ).
Fix any H 2 H. Take any θ and θ0 such that x 2 F (θ) \F (θ0 ). Furthermore, let us
suppose that Li (θ, x) ⊆ Li (θ0 , x) for each individual i. Since F is S (N )-partial-honesty
monotonic, it implies that RN (θ) \ S (h) 6= RN (θ0 ) \ S (h) for at least one h 2 H. Thismeans that Th (θ) 6= Th (θ0 ) for at least one h 2 H, as we sought. Thus, F is partial-honesty
monotonic.
Indeed, for any given honesty standard of society summarized in S (N ), the two conditions are equivalent when every individual i’s correspondence Ti is required to be consistent with S (N ) in the following sense: The profile of correspondences (Ti )i2N , specified bypartially-honest monotonicity, is consistent with S (N ) if and only if for any θ and θ0 in Θ,
it holds that
Ti (θ) = Ti (θ0 ) () RN (θ) \ S (i) = RN (θ0 ) \ S (i) , for each i 2 N .

(14)Formally:
Corollary 2 Let the honesty standard of society be summarized in S (N ). Let the profile
of correspondences (Ti )i2N , specified by partially-honest monotonicity, be consistent with
S (N ). Then, partial-honesty monotonicity is equivalent to S (N )-partial-honesty monotonicity.
Proof. By Theorem 3, S (N )-partial-honesty monotonicity implies partial-honesty monotonicity. Therefore, it is su¢cient to show the converse relation. To this end, take any θ and θ0such that x 2 F (θ) \F (θ0 ) and suppose that Li (θ, x) ⊆ Li (θ0 , x) for each individual i. Let
this F satisfy partial-honesty monotoniciy with the requirement that every individual i’scorrespondence Ti is consistent with S (N ). Suppose that F does not satisfy S(N )-partialhonest monotonicity. That is, suppose that, for any i 2 N , RN (θ) \ S(i) = RN (θ0 ) \ S(i).
By (14), it follows that Ti (θ) = Ti (θ0 ) for each i 2 N . Partial-honesty monotonicity
implies that for at least one h 2 H, it holds that Sh (θ0 ; x, θ) \ Ih (θ0 , x) is not empty.
Since Th (θ) = Th (θ0 ), partial-honesty monotonicity also implies that Sh (θ0 ; x, θ) \ Ih (θ, x)
is empty. However, since RN (θ) \ S(h) = RN (θ0 ) \ S(h), requirement (7) implies that15

Rh (θ) = Rh (θ0 ), and so Ih (θ0 , x) = Ih (θ, x). Since Sh (θ0 ; x, θ) \ Ih (θ0 , x) is not empty, itfollows that Sh (θ0 ; x, θ) \ Ih (θ, x) is not empty, which is a contradiction. Thus, F satisfies
S(N )-partial-honest monotonicity.

5. Equivalence result
The classic paper on Nash implementation theory is Maskin (1999), which shows that
where the mechanism designer faces a society involving at least three individuals, a SCR
is Nash implementable if it is Maskin monotonic and satisfies the auxiliary condition of no
veto-power.2
The condition of no veto-power says that if an outcome is at the top of the preferencesof all individuals but possibly one, then it should be chosen irrespective of the preferencesof the remaining individual; that individual cannot veto it. Formally:3
Definition 10 A SCR F : Θ ! X satisfies no veto-power provided that for all θ 2 Θ andall x 2 X, if|{i 2 N |X ⊆ Li (θ, x)}| ≥ n − 1,then x 2 F (θ).
Proposition 1 (Maskin’s Theorem, 1999) If n ≥ 3 and F : Θ ! X is a SCR satisfying
Maskin monotonicity and no veto-power, then it is Nash implementable.
In a general environment such as that considered here, a seminal paper on Nash implementation problems involving partially-honest individuals is Dutta and Sen (2012). It showsthat for Nash implementation problems involving at least three individuals and in which
there is at least one partially-honest individual, the Nash implementability is assured by no
veto-power (Dutta and Sen, 2012; p. 157). From the perspective of this paper, Dutta-Sen’s
notion of truth-telling and their Theorem 1 can be formally restated as follows.
We have already mentioned that our notion of truth-telling encompasses, as a specialcase, that of Dutta and Sen (2012) provided that each individual i’s honesty standard S (i) is
such that Sj (i) \ Rj (θ) = Rj (θ) for every individual j and every state θ. As a generalizationof Dutta and Sen’s (2012) honesty standard, let us consider a specific type of an honesty
2

Moore and Repullo (1990), Dutta and Sen (1991), Sjöström (1991) and Lombardi and Yoshihara (2013)refined Maskin’s theorem by providing necessary and su¢cient conditions for an SCR to be implementable in(pure strategies) Nash equilibrium. For an introduction to the theory of implementation see Jackson (2001),
Maskin and Sjöström (2002) and Serrano (2004).
3
For any finite set S, |S| denotes the cardinality of S.

16

standard S (i) of each individual i such that:( )for any j 2 N , Sj (i) 6= ?j implies Sj (i) \ Rj (θ) = Rj (θ) for every state θ.

Such a type of honesty standard ensures the existence of a subgroup of society, denoted by
S (i), such that j 2 S (i) if and only if Sj (i) \ Rj (θ) = Rj (θ) for every state θ. In thissection, we focus our attention to this type of honesty standards for all individuals. To
ease notation, in what follows we can denote an honesty standard of individual i by S (i).
Thus, given a state θ, RS(i) (θ) is a list of orderings consistent with θ for individuals in
the honesty standard S (i) of individual i. Our interpretation is that participant i concerns
herself with the truth-telling of preferences of individuals in her honesty standard when sheplays a strategy choice. To capture the requirement in (7), our definition endorses the viewthat an individual concerns herself with at least her own self; that is, i 2 S (i).
Furthermore, given that in Dutta-Sen’s Theorem 1 the mechanism designer knows thehonesty standard of society, denoted by S (N ) ≡ (S (i))i2N , we also need the following
information assumption in order to state their result from the perspective of this paper.
Assumption 2 The mechanism designer knows the honesty standard of the society N .
Therefore:
Proposition 2 (Dutta-Sen’s Theorem 1, 2012) Let Assumption 1 and Assumption 2 begiven. Let the honesty standard of society be summarized in S (N ), where S (i) ≡ N for all
i 2 N . If n ≥ 3 and F : Θ ! X is a SCR satisfying S (N )-partial-honesty monotonicity forthe standard S (N ) and no veto-power, then it is partially-honestly Nash implementable.
It follows from Corollary 1 and Corollary 2 that any SCR is S̄ (N )-partial-honesty
monotonic whenever the honesty standard of society is such that every individual considers
truthful only messages that encode the whole truth about preferences of individuals in society,that is, S (i) = N for all i 2 N .
That is a particular kind of honesty standards of individuals but there is no reason to
restrict attention to such standards. Thus, in what follows, we are interested in understanding the kind of honesty standards of individuals which would make it impossible for themechanism designer to circumvent the limitations imposed by Maskin monotonicity. To thisend, let us introduce the following notion of standards of honesty of a society.
Definition 11 Given a society N involving at least two individuals, an honesty standard ofthis society is said to be non-connected if and only if for all i 2 N , i 2/ S (j) for some j 2 N .
Given that the honesty standard of individual i includes the individual herself, by definition of S (i), the honesty standard of society is non-connected whenever every one of its
17

members is excluded from the honesty standard of another member of the society. Simply
put, members of a society do not concern themselves with the same individual.
It is self-evident that the kind of honesty standards in Dutta-Sen’s theorem are notnon-connected because every individual of the society is interested in telling the truth about
the whole society. As another example of honesty standards of a society that are not nonconnected, consider a three-individual society where individual 1 concerns herself with herself
and with individual 2 (that is, S (1) = {1, 2}), individual 2 concerns herself with everyone(that is, S (2) = {1, 2, 3}) and, finally, individual 3 concerns herself with herself and withindividual 1 (that is, S (3) = {1, 3}). The honesty standard of this three-individual society
is not non-connected because everyone concerns themselves with individual 1.
Moreover, it is not necessarily true that every non-connected honesty standard of society
implies that every individual honesty standard be of the form S (i) 6= N , as we demonstratewith the next example. Consider a three-individual society where individual 1 is concerned
only with herself (that is, S (1) = {1}), individual 2 with everyone (that is, S (2) = {1, 2, 3})
and individual 3 with herself and with individual 2 (that is, S (3) = {2, 3}). The honesty
standard of this society is non-connected given that individual 2 and individual 3 are both
excluded from the honesty standard of individual 1 and individual 1 is excluded from thehonesty standard of individual 3.
As is the case here, the above definition is a requirement for the honesty standard of asociety that is su¢cient for S (N )-partial-honesty monotonicity to be equivalent to Maskin
monotonicity when two further assumptions are satisfied. The first assumption requires thatthe family H includes singletons. This requirement is innocuous given that the mechanism
designer cannot exclude any individual from being partially-honest purely on the basis of
Assumption 1.
The second requirement is that the set of states Θ takes the structure of the Cartesian
product of allowable independent characteristics for individuals. More formally, the domain
Θ is said to be independent if it takes the form
Θ=

Y

Θi ,

i2N

where Θi is the domain of allowable independent characteristics for individual i, with θi
as a typical element. A typical example of an independent domain is that each Θi simply
represents the domain of the preference orderings over X of individual i and so the domainof the profiles of all individuals’ preference orderings on X has the structure of the Cartesian
product. In such a case, in a state θ = (θi )i2N , individual i’s preference ordering over X
depends solely on individual i’s independent characteristic θi rather than on the profile θ.
The latter two requirements and the requirement that the honesty standard of society
18needs to be non-connected are jointly su¢cient for S (N )-partial-honesty monotonicity to
imply Maskin monotonicity. This can be seen as follows:
Consider a two-individual society where Θ is the set of states and X is the set of outcomes
available to individuals. Let S (i) be the honesty standard of individual i = 1, 2. Consider
an outcome x and a state θ such that x is an F -optimal outcome at θ. Consider any otherstate θ0 such that individuals’ preferences change in a Maskin monotonic way around x fromθ to θ0 . Maskin monotonicity says that x must continue to be an F -optimal outcome at θ0 .
To avoid trivialities, let us focus on the case that θ 6= θ0 , which means that RN (θ) 6= RN (θ0 ),given that we identify states with preference profiles.
If every individual were concerned with the whole society, we could never invoke (thecontrapositive of) S (N )-partial-honesty monotonicity to conclude that x should remain F optimal at θ0 because RN (θ) 6= RN (θ0 ). Furthermore, consider the case that individual 1
concerns herself with only herself, that is, S (1) = {1}, while individual 2 concerns herself
with the whole society, that is, S (2) = {1, 2}. Reasoning such as the one just used shows that
S (N )-partial-honesty monotonicity cannot be invoked if R1 (θ) 6= R1 (θ0 ). The argument forhonesty standards of the form S (1) = {1, 2} and S (2) = {2} is symmetric. Thus, theonly case left to be considered is the one in which everyone concerns themselves with only
themselves, that is, S (i) = {i} for i = 1, 2. In this situation, the honesty standard of society
is reduced to the non-connected one. Note that the standards considered earlier were notnon-connected.
Suppose that preferences of individual 1 are identical in the two states, that is, R1 (θ) =R1 (θ0 ). To conclude that x should be F -optimal at θ0 by invoking S (N )-partial-honesty
monotonicity we need to find individual 1 in the family H. The argument for the caseR2 (θ) = R2 (θ0 ) is symmetric. Thus, if Ri (θ) = Ri (θ0 ) for one of the individuals, therequirement that the singleton {i} is an element of H is needed for the completion of theargument.
Suppose that preferences of individuals are not the same in the two states, that is,
Ri (θ) 6= Ri (θ0 ) for every individual i, though they have changed in a Maskin monotonic
way around x from the state θ to θ0 . In this case, one cannot directly reach the conclusion of Maskin monotonicity by invoking S (N )-partial-honesty monotonicity. One way tocircumvent the problem is to be able to find a feasible state θ00 with the following properties: i) individuals’ preferences change in a Maskin monotonic way around x from θ to θ00
and Ri (θ) = Ri (θ00 ) for an individual i, and ii) individuals’ preferences change in that way
around x from θ00 to θ0 and Rj (θ0 ) = Rj (θ00 ) for individual j 6= i. A domain Θ that assuresthe existence of such a state is the independent domain.
Even if one were able to find such a state θ00 by requiring an independent productstructure of Θ, one could not invoke S (N )-partial-honesty monotonicity to conclude that x

19

must continue to be an F -optimal outcome at θ0 whenever the family H did not have theappropriate structure. This can be seen as in the following argument.
Suppose that Θ is an independent domain. Then, states take the form of profiles ofindividuals’ characteristics, that is, θ = (θ1 , θ2 ) and θ0 = (θ01 , θ02 ). Moreover, the characteristicof individual i in one state is independent from the characteristic of the other individual.
That is, Ri (θ) = Ri (θi ) and Ri (θ0 ) = Ri (θ0i ) for every individual i. The product structureof Θ assures that the states (θ1 , θ02 ) and (θ01 , θ2 ) are both available and each of them has theproperties summarized above.
Next, suppose that the family H has a structure given by {{1} , {1, 2}}. One can invoke
S (N )-partial-honesty monotonicity for H = {1} to obtain that x is one of the outcomeschosen by the SCR F at (θ1 , θ02 ) when the state changes from θ to (θ1 , θ02 ), but he cannot
conclude that x remains also F -optimal at θ0 when it changes from (θ1 , θ02 ) to θ0 . The reason
is that S (N )-partial-honesty monotonicity cannot be invoked again for the case H = {2}because the structure of the family H does not contemplate such a case. The argument forthe case that H takes the form {{2} , {1, 2}} is symmetric. Thus, each of our requirements
is indispensable, and jointly they lead to the following conclusion:
Theorem 4 Let N be a society involving at least two individuals, Θ be an independent
domain and H include singletons. Suppose that the honesty standard of the society, denoted by S (N ), is non-connected. Then, S (N )-partial-honesty monotonicity is equivalent
to Maskin monotonicity.
Proof. Let n ≥ 2, Θ be an independent domain and H include singletons. Let S (N )be a non-connected honesty standard of N . One can see that Maskin monotonicity implies
S (N )-partial-honesty monotonicity.
For the converse, consider any SCR F : Θ ! X satisfying S (N )-partial-honesty
monotonicity. Consider any x 2 X and any state θ 2 Θ such that x is an F -optimal
outcome at θ. Moreover, consider any state θ0 such that individuals’ preferences change in a
Maskin monotonic way around x from θ to θ0 , that is,for all i 2 N and all x0 2 X : xRi (θ) x0 =) xRi (θ0 ) x0 .
We show that x remains F -optimal at θ0 .
If characteristics of individuals in the honesty standard of individual i 2 N are identicalin the two states, that is, RS(i) (θ) = RS(i) (θ0 ), S (N )-partial-honesty monotonicity for thecase H = {i} assures that x is still F -optimal at θ0 . Thus, let us consider the case RS(i) (θ) 6=
RS(i) (θ0 ) for every individual i 2 N .
To economize notation, for any subset K of N , write KC for the complement of K in
N . Therefore, for any non-empty subset K of N , we can write any non-trivial combination20

$%of the states θ and θ0 as θK , θ0KC , where it is understood that θK is a list of characteristics
of individuals in K at the state θ and θ0KC is a list of characteristics of individuals in KC
at θ0 . Note that any state that results by that combination is available in Θ because of its
product structure.
Given that the honesty standard of society is non-connected, there must be an individualj (1) 2 N who does not concern herself with the whole society, that is, S (j (1)) 6= N .
Consider the state&'θK(1) , θ0K(1)C where K (1) ≡ S (j (1)) ,and call it θ1 . By construction, individuals’ preferences change in a Maskin monotonic way
around x from θ to θ1 and, moreover, θK(1) = θ1K(1) . S (N )-partial-honesty monotonicity forthe case H = {j (1)} assures that the x remains an F -optimal outcome at θ1 .
If there is an individual i 2 N \ {j (1)} who is not concerned with any of the individuals
in the honesty standard of individual j (1), that is, the intersection S (i) \ S (j (1)) is empty,
then S (N )-partial-honesty monotonicity for the case H = {i} assures that x is still F optimal at θ0 . This is because, by construction, individuals’ preferences change in a Maskin
monotonic way around x from θ1 to θ0 and θ1S(i) = θ0S(i) .
Thus, consider any individual j (2) 2 N \ {j (1)}, and denote by K (2) the set of individuals with whom individual j (1) and individual j (2) are jointly concerned according totheir individual honesty standards. Furthermore, consider the state&θK(2) , θ0K(2)C'

where K (2) ≡ K (1) \ S (j (2)) ,and call it θ2 . By construction, individuals’ preferences change in a Maskin monotonic way
around x from θ1 to θ2 and, moreover, θ1S(j(2)) = θ2S(j(2)) . S (N )-partial-honesty monotonicity
for the case H = {j (2)} assures that x remains an F -optimal outcome at θ2 .
If there is an individual i 2 N \ {j (1) , j (2)} who is not concerned with any of theindividuals with whom individuals j (1) and j (2) are jointly concerned, S (N )-partial-honesty
monotonicity for the case H = {i} assures that x is also F -optimal at θ0 . This is because,by construction, individuals’ preferences change in a Maskin monotonic way around x from
θ2 to θ0 and θ2S(i) = θ0S(i) .
Thus, consider any individual j (3) 2 N \ {j (1) , j (2)}, and denote by K (3) the set ofindividuals with whom individuals j (1), j (2) and j (3) are jointly concerned according totheir individual honesty standards. Furthermore, consider the state&θK(3) , θ0K(3)C'

where K (3) ≡ K (2) \ S (j (3)) ,and call it θ3 . By construction, individuals’ preferences change in a Maskin monotonic way
21around x from θ2 to θ3 and, moreover, θ2S(j(3)) = θ3S(j(3)) . S (N )-partial-honesty monotonicity
for the case H = {j (3)} assures that x remains an F -optimal outcome at θ3 .
As above, if there is an individual i 2 N \ {j (1) , j (2) , j (3)} who is not concernedwith any of the individuals with whom individuals j (1), j (2) and j (3) are jointly concerned, S (N )-partial-honesty monotonicity for the case H = {i} assures that x remains
also F -optimal at θ0 , because, by construction, individuals’ preferences change in a Maskin
monotonic way around x from θ3 to θ0 and θ3S(i) = θ0S(i) . And so on.
Since the society N is a finite set and the above iterative reasoning is based on its
cardinality, we are left to show that it must stop at most after n − 1 iterations.
To this end, suppose that we have reached the start of the n − 1th iteration. Thus,
consider any individual j (n − 1) 2 N , with j (n − 1) 6= j (r) for r = 1, · · · , n − 2, and denote
by K (n − 1) the set of individuals with whom individuals j (1), j (2) , · · · , j (n − 2) andj (n − 1) are jointly concerned according to their individual honesty standards. Furthermore,consider the state&θK(n−1) , θ0K(n−1)C'

where K (n − 1) ≡ K (n − 2) \ S (j (n − 1)) ,and call it θn−1 . As above, by construction,individuals’&' preferences change in a Maskinn−20monotonic way around x from θ≡ θK(n−2) , θK(n−2)C to θn−1 and, moreover, θn−2
S(j(n−1)) =θn−1
S(j(n−1)) . S (N )-partial-honesty monotonicity for the case H = {j (n − 1)} assures that x is
an F -optimal outcome at θn−1 .
At this stage there is only one individual in N who is left to be considered. Call her j (n).
Suppose that this individual is concerned with one of the individuals for whom individuals
j (1), j (2) , · · · , j (n − 2) and j (n − 1) are jointly concerned. In other words, suppose thatthe intersection K (n − 1) \ S (j (n)) is non-empty. Then, the whole society concerns itself
with one of its member, and this contradicts the fact that the honesty standard of society
is non-connected. Therefore, it must be the case that individual j (n) is not concernedwith any of the individuals with whom individuals j (1), j (2) , · · · , j (n − 2) and j (n − 1)are jointly concerned according to their individual honesty standards. S (N )-partial-honesty
monotonicity for the case H = {j (n)} assures that x remains also F -optimal at θ0 given
that, by construction, individuals’ preferences change in a Maskin monotonic way around x
0
from θn−1 to θ0 and θn−1
S(j(n)) = θ S(j(n)) .
The iterative reasoning would stop at the rth (< n − 1) iteration if there were an individual i 2 N \ {j (1) , · · · , j (r)} who was not concerned with any of the individuals in K (r),that is, if the intersection S (i) \ K (r) were empty. If that were the case, then the desiredconclusion could be obtained by invoking S (N )-partial-honesty monotonicity for H = {i}because, by construction, it would hold that individuals’ preferences change in a Maskin

22monotonic way around x from θr to θ0 and that θrS(i) = θ0S(i) .
In light of Theorem 2 and Maskin’s theorem, the main implications of Theorem 4 canbe formally stated as follows:
Corollary 3 Let N be a society involving at least two individuals, Θ be an independent
domain and H include singletons. Suppose that the honesty standard S (N ) of the society is
non-connected. Let Assumption 1 be given. Then, a SCR F : Θ ! X is Maskin monotonic
if it is partially-honestly Nash implementable.
Corollary 4 Let N be a society involving at least three individuals, Θ be an independent
domain and H include singletons. Suppose that the honesty standard S (N ) of the society
is non-connected. Let Assumption 1 be given. Then, a SCR F : Θ ! X satisfying noveto-power is partially-honestly Nash implementable if and only if it is Maskin monotonic.
Remark 3 In a related but not identical setting, Kartik and Tercieux (2012) study Nash implementation problems where agents can choose to provide evidence as part of their strategies.
In this setup, they show that any social choice function satisfying a weaker variant of Maskin
monotonicity, called evidence-monotonicity, and no veto-power is Nash implementable. In
an environment where there are partially-honest individuals, they show that even small intrinsic costs of lying create a substantial wedge between evidence-monotonicity and Maskin
monotonicity, in the sense that every social choice function is evidence-monotonic. Under
the assumptions of Theorem 4 and suitable specifications which resemble those of Example
2 in Kartik and Tercieux (2012; p. 333), one can show that this wedge disappears whenparticipants are allowed/forced to produce partial evidence of the true state according to a
non-connected (evidence) standard S(N ).44

To see it, let us suppose that individuals have separable preferences in the sense of Kartik and Tercieux(2012; p. 238). That is, suppose that each agent’s (extended) preference ordering Ri (θ) over the outcomeevidence space X × Ei is represented by a utility function of the form Ui (x, ei , θ) = ui (a, θ) − ci (ei , θ),
where ci (ei , θ) represents agent i’s cost of producing evidence ei . Fix
Q any S (N ) and let the domain Θ beindependent. For each individual i, let the evidence space be Ei =
Θj . Fix any set H. For each h 2 H,
j2S(i)
$ 0%
$ 0%
$
%
let the cost function be ch θ, θ = 0 if $RS(h)% (θ) = RS(h) θ , otherwise, ch θ, θ0 = " > 0, where " can bearbitrarly small. For each i 2/ H, let ci θ, θ0 = 0 for every θ and θ0 . This
structure
implies that the set of()
the least-evidence cost for h 2 H given the pair (x, θ) is Eh` (x, θ) = θ(S(h) whileitis Ei` (x, θ) = Ei for)∗every i 2
/ H. Let the evidence function of invididual h 2 H be eh (θ) = RS(h) (θ) for every θ 2 Θ. Under
these specifications, one can now see from the proof of Theorem 4 that evidence-monotonicity (stated foreach H 2 H) is equivalent to Maskin monotonicity.

23

6. Concluding remarks
The assumption that the mechanism designer knows the honesty standard of society isoften not met in reality, although it may be plausible in societies with a small number ofindividuals in which the mechanism designer knows their sensitivity to honesty. Outside ofcases like those, we view as more plausible the assumption that the mechanism designer only
knows the types of honesty standards shared by individuals. Does the conclusion of Theorem
4 change in this case? The answer is no. After all, if individuals are honesty-sensitive, themechanism designer can test for connectedness of their honesty standards. If the test fails,
it would be in vain for him to attempt to Nash implement any SCR that is not Maskin
monotonic. The reason for it is easy to identify: the fact that he solely knows that thehonesty standard of society is non-connected can only make implementation harder than if
the actual non-connected honesty standards of participants were known.
Theorem 4 is derived on the basis that in every state a strategy choice of an individualis truthful if it encodes information of individuals’ preferences consistent with that state formembers of society in her honesty standard. This implies that if we arrange agents in a
directed circle and ask them to report their own preferences and those of their successors in
the circle, and the honesty standard of every individual includes herself and her successors,5then this ‘simpler’ mechanism would impair the ability of the mechanism designer to escape
the limitations imposed by Maskin monotonicity. Then, a natural question that arises immediately is: Under what conditions would the positive result of Dutta and Sen (2012) berestored? We answer this question in a companion paper (Lombardi and Yoshihara, 2016a)
and it is as follows: The mechanism designer who knows that α(≥ 1) members of society havea taste for honesty can expect to do well if no participant has a veto-power by structuringcommunication with participants in a way that each of them reports her own preference andthose of other n − α successors who are in her honesty standard.
Postlewaite and Schmeidler (1986), Palfrey and Srivastava (1989) and Jackson (1991)
have shown that Maskin’s theorem can be generalized to Bayesian environments. A necessary condition for Bayesian Nash implementation is Bayesian monotonicity. In a Bayesianenvironment involving at least three individuals, Bayesian monotonicity combined with noveto-power is su¢cient for Bayesian Nash implementation provided that a necessary condition called closure and the Bayesian incentive compatibility condition are satisfied (Jackson,
1991). Although the implementation model developed in this paper needs to be modified
to handle Bayesian environments, we believe a similar equivalence result holds in those en5
In an environment in which knowledge is dispersed, how individuals will interact with the mechanism
designer is a natural starting point when it comes to Nash implementing a SCR. A particular kind ofcommunication is, as in Dutta and Sen’s (2012) Theorem 1, to ask participants to report preferences of theentire society. However, there is no reason to restrict attention to such schemes.

24vironments for suitably defined communication schemes (on this point, see Lombardi and
Yoshihara, 2013; section 5). This subject is left for future research.

References
Abreu, D., Sen, A., 1990. Subgame perfect implementation: a necessary and almost su¢cientcondition, J. Econ. Theory 50, 285-299.
Abreu, D., Sen, A., 1991. Virtual implementation in Nash equilibrium, Econometrica 59,
997—1021.
Corchón, L.C., Herrero, C., 2004. A decent proposal, Spanish Econ. Rev. 6, 107—125.
Dutta, B., Sen, A., 1991. A necessary and su¢cient condition for two-person Nash implementation, Rev. Econ. Stud. 58, 121-128.
Dutta, B., Sen, A., 2012. Nash implementation with partially honest individuals, Games
Econ Behav 74, 154-169.
Jackson, M.O., 1991. Bayesian implementation, Econometrica 59, 461-477.
Jackson, M.O., 1992. Implementation in Undominated Strategies: A Look at Bounded Mechanisms, Rev. Econ. Stud. 59, 757-775.
Jackson, M.O., 2001. A crash course in implementation theory, Soc. Choice Welfare 18,655-708.
Kalai, E., Ledyard, J.O., 1998. Repeated Implementation, J. Econ. Theory 83, 308-317.
Kartik, N., Tercieux, O., 2012. Implementation with evidence, Theor. Econ. 7, 323-355.
Kartik, N., Tercieux, O., Holden, R., 2014. Simple mechanism and preference for honesty,
Games Econ. Behav. 83, 284-290.
Lee, J., Sabourian, H., 2011. E¢cient Repeated Implementation, Econometrica 79, 19671994.
Lombardi, M., Yoshihara, N., 2013. A full characterization of Nash implementation withstrategy space reduction, Econ. Theory 54, 131-151.
Lombardi, M., Yoshihara, N., 2016a. Treading a Fine Line: (Im)possibilities for Nash Implementation with Partially-honest Individuals, IER DP series A, n. 651, Hitotsubashi
Univ.
Lombardi, M., Yoshihara, N., 2016b. Natural implementation with semi-responsible agentsin pure exchange economies, forthcoming in International J. Game Theory.

25

Lombardi, M., Yoshihara, N., 2016c. Partially-honest Nash implementation: a full characterization, mimeo.
Maskin, E., 1999. Nash equilibrium and welfare optimality, Rev. Econ. Stud. 66, 23-38.
Maskin, E., Sjöström, T., 2002. Implementation theory, in: K. Arrow, A.K. Sen, K. Suzumura(Eds), Handbook of Social Choice and Welfare, Elsevier Science, Amsterdam, pp.
237—288.
Matsushima, H., 1988. A new approach to the implementation problem, J. Econ. Theory 45,
128—144.
Matsushima, H., 2008a. Behavioral aspects of implementation theory, Econ. Letters 100,
161-164.
Matsushima, H., 2008b. Role of honesty in full implementation, J. Econ. Theory 139, 353359.
Mezzetti, C., Renou, L., 2016. Repeated Nash Implementation. To appear in Theoretical
Economics.
Moore, J., Repullo, R., 1988. Subgame perfect implementation, Econometrica 56, 1191-1220.
Moore, J., Repullo, R., 1990. Nash implementation: A full characterization, Econometrica
58, 1083-1100.
Ortner, J., 2015. Direct implementation with partially honest individuals, Games Econ.
Behav. 90, 1-16.
Palfrey, T., Srivastava, S., 1989. Implementation with incomplete information in exchange
economies, Econometrica 57, 115-134.
Palfrey, T., Srivastava, S., 1991. Nash-implementation using undominated strategies, Econometrica 59, 479-501.
Postlewaite, A., Schmeidler, D., 1986. Implementation in di§erential information economies,
J. Econ. Theory 39, 14-33.
Saporiti, A., 2014. Securely implementable social choice rules with partially honest agents,
J. Econ. Theory 154, 216-228.
Serrano, R., 2004. The theory of implementation of social choice rules, SIAM Review 46,
377-414.
Sjöström, T., 1991. On the necessary and su¢cient conditions for Nash implementation, Soc.
Choice Welfare 8, 333-340.

26