HIAS-E-48

Natural implementation with semi-responsible agentsin pure exchange economies
Michele 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

December 2016

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.

Natural implementation with semi-responsible
agents in pure exchange economies∗
Michele Lombardi† and Naoki Yoshihara‡
December 12, 2016

We study Nash implementation by natural price-quantity mechanisms in pure exchange
economies when agents have intrinsic preferences for responsibility. An agent has an intrinsic
preference for responsibility if she cares about truth-telling that is in line with the goal of themechanism designer besides her material well-being. A semi-responsible agent is an agent
who, given what her opponents do, acts in an irresponsible manner when a responsible
behavior poses obstacles to her material well-being. The class of e¢cient allocation rulesthat are Nash implementable is identified provided that there is at least one agent who issemi-responsible. The Walrasian rule is shown to belong to that class.
JEL classification: C72; D71.
Key-words: Nash equilibrium, exchange economies, intrinsic preferences for responsibility,
boundary problem, price-quantity mechanism.

1

Introduction

In implementation problems in pure exchange markets, as Hurwicz (1978), Otani andSicilian (1982) and Thomson (1984) discuss, the information exchanged in the market typically concerns prices of commodities and the agents’ consumption bundles,
subsequently quantities, at those prices. Therefore, a prominent restriction on mechanisms for implementation problems in pure exchange markets would be represented
by price-quantity mechanisms, henceforth p-q mechanisms: each agent chooses a pricevector p as well as a quantity q as her strategy choice (see also Hurwicz et al., 1995).
∗

We are grateful to an associate editor and two referees of this Journal for their useful comments
and suggestions. They are not responsible for remaining deficiencies.
†
Adam Smith Business School, University of Glasgow, Glasgow, G12 8QQ, United Kingdom,
e-mail: lombardimichele1975@gmail.com.
‡
Department of Economics, University of Massachusetts Amherst, 200 Hicks Way, Amherst, MA
01003, USA; The Institute of Economic Research, Hitotsubashi University, Kunitachi, Tokyo 1860004 Japan; and School of Management, Kochi University of Technology, Kochi 782-8502, Japan.
E-mail: n_yoshihara_1967@yahoo.co.jp

To meet the requirements for an adequate theory of implementation (see as per
Jackson, 1992), Dutta et al. (1995), Sjöström (1996), and Saijo et al. (1996, 1999)
have defined the class of natural mechanisms in economic environments. Within thisclass, mechanisms are typically required a) to ensure each agent always receives aquantity lying in her consumption set; b) to ensure each agent receives, in equilibrium,
what she stated as her own quantity; and c) to ensure each agent has a best strategy
choice for every other agents’ strategy choices.1 We then name any p-q mechanismthat meets these requirements a natural p-q mechanism.
Matsushima (2008a, 2008b) and Dutta and Sen (2012) introduced and studied
implementation problems when agents are partially-honest. In a strategic game, anagent is partially-honest if she tells the truth when truth-telling results in the highest
material payo§ available to her given other agents’ strategy choices.2 Simply put, as
between being truthful and being untruthful, a partially-honest agent prefers to betruthful when that choice of behavior does not hurt her material well-being given her
opponents’ actions. In a general environment, Dutta and Sen (2012) show that for
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.
This line of research is particularly relevant if the task at hand is to achieve social
goals via market like-mechanisms. Indeed, the analysis of this class of implementation
problems typically relies on the assumption that maximization of material gains is the
only intention of agents’ actions. There is therefore a need to develop decentralized
decision making processes that can take into account more sophisticated behavior
than the one that has been analyzed up until this point. This paper studies thee§ect of responsible actions in the design of market like-mechanisms. In fact, simple
reasoning and everyday observation suggest that a concern about responsibility as wellas welfare of the society is an important determinant of behavior. Actual behavior
is often the outcome of a compromise between what society prescribes and what the
pursuit of material gains dictates.
We adopt herein the common view in the literature of resource allocation mechanisms that an agent is responsible when she states the true prices and demands
an a§ordable utility-maximizing quantity at those prices and when her statement
fosters the pursuit of socially valued goals. As an example, think of the Walrasianequilibrium: an agent is responsible if she reports competitive equilibrium prices aswell as a competitive equilibrium quantity at those prices. In line with the notion ofpartially-honest agent introduced by Dutta and Sen (2012), we say that an agent issemi-responsible if she complies with the welfare criterion incorporated into allocation
rule in the absence of opportunistic behavior. Simply put, a semi-responsible agent
dislikes acting in an irresponsibly opportunistic manner when a responsible conduct
is equally e¢cacious.3
1. These requirements are formally defined in section 3 below.
2. There are seminal related works such as Glazer and Rubinstein (1998), Eliaz (2002), Corchónand Herrero (2004) and Kartik and Tercieux (2012).
3. Doğan (2014) studies problems of the fair allocation of indivisible goods by employing a similar1

On this basis, the paper develops a Nash implementation framework with semiresponsible agents where Nash implementation problems in pure exchange economies
are studied, the class of e¢cient allocation rules that are Nash implementable by natural p-q mechanisms is identified and, finally, shows that the Walrasian rule belongs
to this class.
The closest papers to ours are Dutta and Sen (2012) and Kartik et al. (2014),
which are works on implementation with partially-honest agents in separable environments (as per Jackson, 2001). By focussing on social choice functions, these scholars
establish general positive results by devising mechanisms that do not use any sort of“integer games” or “modulo games”. Specifically, when every agent has an intrinsic
preference for honesty, Dutta and Sen (2012) provide a separability condition underwhich any social choice function is implementable in strictly dominant strategies.4
When the mechanism designer knows the identity of at least one partially-honest
agent or when every agent has an intrinsic preference for honesty, Kartik et al. (2014)o§er a condition called separable punishment under which any social choice function
is implementable by a simple mechanism via two rounds of iterated deletion of strictly
dominated strategies. The devised mechanisms share a feature which does not qualify them as a market mechanism: Each agent’s strategy choice includes at least her
preference.
By contrast, we endorse a weaker, and what we consider to be a more reasonable,
informational requirement for the mechanism designer: The designer only knows there
exists at least one semi-responsible agent in the population. More importantly, ouragents do not announce preferences as their strategy choices. In fact, by stating prices
and consumption bundles, an agent transmits simply local information about her
preferences to the mechanism designer. We also abandon the common requirement of
the single-valuedness of allocation rules because it is incompatible, for example, withthe property of many interesting allocation rules such as the multiplicity of Walrasianequilibria. Finally, like Dutta and Sen’s (2012) and Kartik et al.’s (2014) results, ourcharacterization result does not rely on any sort of “tail-chasing” construction.
It is well-known by Hurwicz et al. (1995) that the Walrasian rule does not satisfy
Maskin monotonicity, a necessary condition for Nash implementation. The reason isthat the Walrasian rule also depends on the shape of preferences outside of the set of
feasible allocations. This problem is known as boundary problem and has stimulated
a stream of informative studies.
The way around this problem suggested by Hurwicz et al. (1995) is to focus on
the constrained Walrasian rule, which is the minimal monotonic extension of the Walrasian rule (Thomson, 1999).5 Postlewaite and Wettstein (1989), Dutta et al. (1995),
Saijo et al. (1996) and Tian (1992) show that the constrained Walrasian rule is implementable by a price-allocation mechanism: each agent chooses a price vector as well as
an allocation as her strategy choice. Saijo et al. (1996) also show that the constrained
definition of responsible agents.
4. This informational assumption is used also in other environments; see, e.g., Saporiti (2014).
5. The constrained Walrasian rule is a super-correspondence of the Walrasian rule. The two rules
coincide when agents’ preferences are convex and Walrasian equilibrium allocations are interior.

2Walrasian rule is implementable by a p-q mechanism provided that allocations on theboundary of the feasible set are ruled out. Saijo et al. (1999) focus on the boundary
problem and show that the constrained Walrasian rule cannot be implemented byany natural p-q mechanism in economies with more than two commodities. Lately,
Bochet (2007) provides a thorough study of the boundary problem and shows that
the Walrasian rule cannot be implemented in any of the solution concepts consideredin the implementation literature if Walrasian equilibrium allocations on the boundaryof the feasible set are not ruled out. This paper also takes care of the boundary problem that is prominent in Nash implementation literature and shows that in the casewhere there are at least three agents, the Walrasian rule is Nash implementable bya natural p-q mechanism when at least one agent is semi-responsible and the mechanism designer does not know the identity of the semi-responsible agent(s). It is worth
mentioning that, with respect to Saijo et al. (1999), this paper is built on a definition of natural p-q mechanisms that di§ers from that in Saijo et al. (1999). This isso because we employ a definition of supporting prices that possibly also depend on
the e¢cient allocation rule considered (to be discussed in section 3.1). This choice
is dictated by the consideration that supporting prices are not equally important toevery e¢cient allocation rule (as per Saijo et al., 1999).
Section 2 and section 3 of this paper present the theoretical framework and outline
the basic model, with results presented in section 4. Section 5 concludes. Omitted
proofs can be found in the Appendix.

2

Preliminaries

The framework can be described as follows. There are n ≥ 3 agents and ` ≥ 2
commodities, where n and ` are both finite. The set N ≡ {1, ..., n} denotes the setof agents, and the set L ≡ {1, ..., `} denotes the set of commodities.
Agent i’s commodity bundle xi = (xi1 , ..., xi` ) is an `-dimensional vector describing
how much of each commodity agent i consumes, where xil ≥ 0 for all l 2 L. The
commodity space for agent i is denoted by R`+ , where R`+ is the non-negative orthantof the `-dimensional Euclidean space R` . An allocation x = (x1 , ..., xn ) 2 Rn`+ isa profile of commodity bundles. We shall sometimes write (xi , x−i ) for the profile
of commodity bundles, where x−i = (x1 , ..., xi−1 , xi+1 , ..., xn ); the same notational
convention will be followed for any profile of objects.
We assume that each agent i has an initial non-zero endowment of the ` commodities, ! i = (! i1 , ..., ! i` ) 2 R`+ \ {0}. The endowment profile is denoted by ! =n`(! 1 , ..., ! n ) 2 R
P+ . The aggregate endowment of commodity l 2 L, denoted Ωl , is defined by Ωl ≡ i2N ! il and assumed to be strictly positive. The aggregate endowment
profile is denoted by Ω ≡ (Ω1 , ..., Ω` ).
We assume that each agent i has a preference ordering over the commodity spaceR`+ , which is represented by a utility function ui that is continuous, quasi-concaveand strongly monotonic on R`+ . The class of allowable continuous, quasi-concave and3strongly monotonic utility functions for agent i is denoted by Ui .6
Since the set of agents, N , and the endowment profile, !, will remain fixed, an
economic environment, subsequently environment, is described by a profile of utility
functions (ui )i2N , where ui 2 Ui for every i 2 N . The class of allowable environments
is denoted by UN and defined by a subset of the Cartesian product U1 × ... × Un .
A price vector is an `-dimensional vector p = (p1 , ..., p` ), where the price of commodity l 2 L is pl ≥ 0. The value of a commodity bundle xi at prices p is p · xi .
Without loss of generality, we restrict the price spacePto the unit simplex in R` , denoted by P and defined by the set of p’s such that l2L pl = 1 and pl ≥ 0 for any
l 2 L.
P
7
An allocation x 2 Rn`
We denote by A the set of+ is feasible if
i2N xi ≤ Ω.
`(feasible) allocations. A commodity bundle xi 2 R+ is feasible if xi ≤ Ω. We shallrefer to a feasible commodity bundle xi as a quantity. The set of quantities is denoted
by Q.
For any u 2 UN , an allocation x 2 A is (Pareto) e¢cient for u if there is no otherallocation y 2 A such that ui (yi ) ≥ ui (xi ) for all i 2 N with at least one of theseinequalities being strict. We denote by P O (u) the set of e¢cient allocations for u.
In this paper, we are interested in implementing e¢cient allocation rules. Formally:
Definition 1. An e¢cient allocation rule is a multi-valued (non-empty) mapping
F : UN ! A such that for each u 2 UN : (i) F (u) ⊆ P O (u) and (ii) for eachx 2 F (u) and i 2 N , it holds that xi > 0. The class of e¢cient allocation rules isdenoted by F. We shall refer to x 2 F (u) as an F -allocation at u.
Given this notion, any e¢cient allocation rule in F ensures that every agent consumes
a strictly positive amount of at least one commodity. As it will be evident, we use
this requirement in the su¢ciency part in order to be able to devise a natural p-q
mechanism that does not rely on any sort of “integer games” or “modulo games.”A (normal form) mechanism is a pair γ ≡ (M, g), where M ≡ M1 × ... × Mn , Mi is
the strategy space of agent i 2 N , and g : M ! Rn` , the outcome function, assigns toevery strategy profile m 2 M a unique allocation in Rn` . Denote the ith componentof g (m) by gi (m).
In this paper, we focus on price-quantity mechanisms: each agent announces aprice vector, p 2 P , and a quantity, xi 2 Q. Formally:
Definition 2. A mechanism γ is a price-quantity mechanism, or simply a p-q mechanism, if for every i 2 N , the strategy space of agent i is Mi ≡ P × Q, where P
is the price space and Q is the set of quantities.
6. What we do in this paper extends to the case where Ui is the class of allowable utility functions
which are continuous and quasi-concave on R`+ , strongly monotonic on the strictly positive orthantof R` , and satisfy the following boundary condition: the utility of every interior commodity bundle
is strictly higher than the utility of any boundary commodity bundle. The Cobb-Douglas utility
function is an example of such utility functions.
7. We use the following conventions: For all x, y 2 R`+ , x ≥ y if xl ≥ yl for each l 2 L; x > y if
x ≥ y and x 6= y; and x ≫ y if xl > yl for each l 2 L.

4

Our interest in p-q mechanisms stems from the fact that to implement Pareto e¢cient allocation rules in Nash equilibria we need to require agents to send some local
information about their indi§erence curves, such as the common marginal rate of
substitution at an e¢cient allocation, in addition to quantity announcements (Dutta
et al., 1995; Saijo et al., 1996). The price announcement serves this purpose.

3

Nash implementation by natural p-q mechanisms
with semi-responsible agents

Below we provide the notion of Nash implementation by natural p-q mechanisms
when agents have intrinsic preferences for responsibility. We start by providing thedefinitions of supporting prices and of semi-responsible agents.

3.1

Supporting prices

As already noted, the price announcement is a device to obtain from agents information about the common marginal rate of substitution at an e¢cient allocation. If
an e¢cient allocation rule generates only allocations in the interior of the feasible
set A and agents’ utility functions are di§erentiable, the common marginal rate of
substitution at any F -allocation is always unique. In these cases, a supporting pricefor u at the e¢cient allocation x can be taken to be the gradient vector of ui at thequantity xi .
We lose, however, the uniqueness property of the marginal rates of substitution of
agents since we neither assume di§erentiability of utility functions, nor the interiorityof the range of allocation rules. In this case, one can define a supporting price for u
at x as a price vector (or common subgradient) p normal to a hyperplane separating
the weak upper contour sets of any two utility functions in u at the corresponding
quantities in x. Formally:
Definition 3. (Saijo et al., 1999; p. 276) Let u 2 UN and x 2 Qn be given. The
weak upper contour set of ui at xi is V (xi , ui ) ≡ {x0i 2 Q|ui (x0i ) ≥ ui (xi )}. A
price vector p 2 P is said to be a supporting price for u at x if for all i 2 N ,p · x0i ≥ p · xi for all x0i 2 V (xi , ui ). The set of supporting prices for u at x isdenoted by Π (x, u).
According to Definition 3, the supporting prices for u at x are equally important toallocation rules in F. This is, however, not completely satisfactory since a supporting
price in Π (x, u) may be more economically important than others in relation to thee¢cient allocation rule F but less important than others in relation to another e¢cient
allocation rule. Motivated by this, we develop below a definition of supporting pricesthat possibly also depends on the e¢cient allocation rule considered. Our development
starts with the following definition.
Definition 4. Let u 2 UN , x 2 Qn and F 2 F be given. A supporting price p foru at x is said to be a supporting price for u and F at x if there exists u0 2 UN
5such that (i) x is an F -allocation at u0 as well as at u, and (ii) p is the uniquesupporting price for u0 at x. The set of supporting prices for u and F at x isdenoted by ΠF (x, u).
Within a framework that includes linear utility functions, requirement (ii) of Definition 4 is satisfied. More di¢cult, however, is satisfying requirement (i). In order todeal with the non-existence of supporting prices that meets both requirements, oursubsequent approach is to consider the definition of supporting prices in Saijo et al.
(1999) provided that no supporting price for u at x passes the test of Definition 4.
Definition 5. Let u 2 UN , x 2 Qn and F 2 F be given. Define the set of supporting
prices for u and possibly for F at x to be π F (x, u) = ΠF (x, u) if ΠF (x, u) is
non-empty, or else to be π F (x, u) = Π (x, u).

3.2

Semi-responsible agents

A classic postulate of implementation theory in economic environments is that agentsonly care about quantity(ies) obtained from the mechanism. It is not unrealistic,
however, to also assume that agents involved in a mechanism may have intrinsic
preferences for responsibility. There are several ways to model intrinsic preferences
for responsibility within a p-q mechanism. In this paper, we adopt the following
notion of responsible actions.
Definition 6. Let u 2 UN , F 2 F and i 2 N be given. A price vector pi 2 P anda quantity xii 2 Q (announced by i) are said to be responsible for (u, F ) if there
exists a profile of quantities x−i 2 Qn−1 such that (i) (xii , x−i ) is an F -allocation atu and (ii) pi is a supporting price for u and possibly for F at (xii , x−i ). We say thatthe (announced) pair (pi , xii ) is responsible for (u, F ) if pi and xii are responsiblefor (u, F ).
It follows that the price vector announcement and the quantity announcement areboth relevant to our notion of responsibility. As an example, let us consider the
Walrasian rule, denoted by W , that assigns to each profile u the corresponding setof Walrasian equilibrium allocations.8 A price-quantity pair (pi , xii ) is responsible for(u, W ) if there is a profile of quantities x−i 2 Qn−1 such that the allocation (xii , x−i )is a Walrasian equilibrium allocation for u and the price vector pi is the Walrasianequilibrium price vector associated with that allocation.
Although our notion of responsibility is not the weakest notion one could thinkof, casual introspection indicates that it is plausible for an agent to act responsibly
for the benefit of society at large when a lie does not lead to any better outcome,and hence in modeling intrinsic preferences for responsibility we take the view of
Dutta and Sen (2012). Intuitively, for any given pair (u, F ), an agent has an intrinsic
preference for responsibility if she prefers to announce a responsible price-quantity
pair for (u, F ) when a lie does not better serve her material interests, given the
8. For a formal definition see section 4.

6

announcements made by other agents. Operationally, for each pair (u, F ), we need toextend every agent i’s utility function ui to an ordering over the strategy space M ,because the agent i’s preference between being responsible and being not is contingent
upon announcements made by other agents as well as the quantity(ies) obtained fromthem. By following standard conventions of preference orderings, let Riγ [u, F ] denote
agent i’s ordering (extension of ui ) over the strategy space M at the pair (u, F ) fora given p-q mechanism γ. The corresponding strict and indi§erence relations aredenoted by Piγ [u, F ] and Iiγ [u, F ], respectively.
Definition 7. Given a price-quantity mechanism γ = (M, g), agent i 2 N is said tobe semi-responsible if for every (u, F ) 2 UN × F there exists an ordering Riγ [u, F ]over M such that for every m−i 2 M−i and every mi , m0i 2 Mi it holds that:(i) If mi is responsible for (u, F ) and m0i is not responsible for (u, F ) and if
ui (gi (mi , m−i )) ≥ ui (gi (m0i , m−i )), then (mi , m−i ) Piγ [u, F ] (m0i , m−i ).
(ii) In all other cases,ui (gi (mi , m−i )) ≥ ui (gi (m0i , m−i )) if and only if (mi , m−i ) Riγ [u, F ] (m0i , m−i ) .
Intrinsic preferences for responsibility of agent i are captured by the first part ofDefinition 7, in that for every pair (u, F ) agent i strictly prefers the profile (mi , m−i )to (m0i , m−i ) according to Riγ [u, F ] provided that agent i’s true utility at the quantitygi (m0i , m−i ) is not larger than the true utility at gi (mi , m−i ) and provided that her
price-quantity announcement is responsible for (u, F ) in (mi , m−i ) and not responsiblefor (u, F ) in (m0i , m−i ).
If agent i is not semi-responsible, this agent cares about the levels of utility associated with di§erent quantities and nothing else. Then, agent i’s ordering over
M is just the transposition into space M of agent i’s relative ranking of quantities.
Formally:
Definition 8. Given a price-quantity mechanism γ = (M, g), agent i 2 N is said
to be not semi-responsible if for every (u, F ) 2 UN × F there exists an ordering
Riγ [u, F ] over M such that for every m, m0 2 M it holds thatmRiγ [u, F ] m0 if and only if ui (gi (m)) ≥ ui (gi (m0 )) .

3.3

Mechanism designer’s problem

In this subsection, we define and discuss the mechanism designer’s Nash implementation problem with semi-responsible agents as well as the notion of a natural p-q
mechanism. In formalizing the mechanism designer’s problem, we first introduce ourinformational assumptions and discuss their implications for our analysis.
Assumption 1. There is at least one semi-responsible agent in N .

7

Further, we assume that there is complete information among the agents. Then,the set of agents, the endowment profile, the objective of the mechanism designer
represented by F , the true utility functions of agents, their rationality as well as theidentity of semi-responsible agents are informally understood to be common knowledge among the agents.
In our framework, these informational assumptions mean the mechanism designer
knows the set of allocations, as well as the fact that there are semi-responsible agentsamong the agents, but knows neither the true utility functions of agents nor theidentity of the semi-responsible agent (or their identities). Indeed, the mechanism
designer cannot exclude any subset of agents from being semi-responsible purely on
the basis of Assumption 1. Therefore, from the point of view of the mechanism
designer:• A possible state of the world is described by three parameters: an allowable
set of semi-responsible agents, an allocation rule F as well as a profile of utility
functions. We denote by H a typical set of semi-responsible agents in N andby H the class of conceivable sets of semi-responsible agents.
• For any p-q mechanism γ, each possible state (u, F, H) is associated with a profile of agents’ orderings Rγ [u, F, H] ≡ (R1γ [u, F ] , ..., Rnγ [u, F ]), where Riγ [u, F ]is the agent i’s ordering over M as formulated in Definition 7 if agent i is in
H, whereas it is the agent i’s ordering over M as formulated in Definition 8 if
agent i is not in H.
• A p-q mechanism γ and a state (u, F, H) induce a strategic game (γ, Rγ [u, F, H]).
• A (pure strategy) Nash equilibrium of the strategic game (γ, Rγ [u, F, H]) isa message profile m such that for each agent i 2 N , mRiγ [u, F ] (m0i , m−i ) for
every m0i 2 Mi . We denote by N E (γ, Rγ [u, F, H]) the set of Nash equilibrium
message profiles of (γ, Rγ [u, F, H]), whereas N A (γ, Rγ [u, F, H]) is its corresponding set of Nash equilibrium allocations.
In this paper, we also ask the mechanism designer to design a p-q mechanism
satisfying the following properties. Firstly, the allocation of the mechanism is to be
individually feasible. That is,
Individual feasibility For all m 2 M , g (m) 2 Rn`+.
Secondly, the total supply of commodity l to agents cannot exceed its aggregate
endowment Ωl . That is,
Weak balancedness For all l 2 L and m 2 M , g1,l (m) + ... + gn,l (m) ≤ Ωl .
Thirdly, for any strategy profile of other agents m−i , each agent i needs to have abest response strategy. That is,8Best response property (Jackson, Palfrey and Srivastava, 1994) For all i 2 N ,u 2 UN and m−i 2 M−i , there exists mi 2 Mi such that ui (gi (mi , m−i )) ≥ui (gi (m0i , m−i )) for every m0i 2 Mi .
Lastly, in equilibrium, each agent needs to receive the quantity demanded. Thatis,
Forthrightness (Saijo, Tatamitani and Yamato, 1996, 1999) For all (u, F, H), x 2
F (u) and p 2 π F (x, u), "the price-quantity
strategy profile (p, xi )i2N is in#γ
9
N E (γ, R [u, F, H]) and g (p, xi )i2N = x.
We call any p-q mechanism that satisfies the above four properties a natural p-q
mechanism (with free disposal) following the literature on p-q mechanisms.
The following definition represents our formulation of the mechanism designer’s
Nash implementation problem with semi-responsible agents when only natural p-q
mechanisms can be devised.

Definition 9. Let Assumption 1 and F 2 F be given. A natural p-q mechanism γ
semi-responsibly Nash implements F if F (u) = N A (γ, Rγ [u, F, H]) for all u 2 UN
and H 2 H. If such a mechanism exists, F is said to be semi-responsibly Nash
implementable by natural p-q mechanisms.
The objective of the mechanism designer is thus to design a natural p-q mechanism
whose Nash equilibrium allocations, for each environment u as well as each conceivable set of semi-responsible agents H, coincide with F (u). Interestingly, there is no
distinction between the above formulation and the standard Nash implementation
problem as long as Assumption 1 is violated.

4

Results

In this section, we first propose a necessary and su¢cient condition for Nash implementation by a natural p-q mechanism when there exists at least one semi-responsible
agent. Then, we present our characterization result. Finally, we show that the Walrasian rule satisfies our condition and that our condition imposes non-trivial restrictions on the class of e¢cient allocation rules.

4.1

A characterization result

There are two key considerations underpinning our condition. These are presented
from the viewpoint of necessity. To this end, suppose an e¢cient allocation rule F issemi-responsibly Nash implementable by a natural p-q mechanism γ ≡ (M, g).
The first important di¢culty for the mechanism designer is to decide what allocation to assign to a strategy profile when agents announce the same price vector, that
9. See also Dutta, Sen and Vohra (1995). Similar properties are used also in general environments;see, e.g., Tatamitani (2001) and Lombardi and Yoshihara (2013a).

9

is, mi = (p, xi ) for every agent i. Following Saijo,$Tatamitani and %Yamato (1996;
P1999), a clue to this issue is given by the allocation Ω − j6=i xj , x−i , where quantities of agents other than agent i are P
fixed at their announced levels and agent i’squantity is the remainder, xΩ≡Ω−x . If the mechanism designer can find"i Ω
# j6=i jan environment u for which xi , x−i is an F -allocationat" Ω# u and the price vector p
is a supporting price for u and possibly for F at xi , x−i , the designer infers fromthis that agent i is a potential deviator for F at (x1 , ..., xn ). The reason is agent ishould have announced the quantity xΩ
i rather than xi . On the other hand, if nosuch environments exist, the mechanism designer can only conclude that agent i andthe other agents had demanded the wrong quantities. Therefore, agent i cannot be
identified as a potential deviator. Note there" may be# many potential deviators. For
instance, if the announced quantity profile xΩ,
x−i for each i were respectively aniF -allocationat"# u and the price vector p were a supporting price for u and possibly for
F at xΩ,
x−i for each i respectively, then every agent would be a potential deviator.
i
Hence, our condition requires the existence of a feasible and weakly balanced
punishment allocation z (p, x) 2 A when all agents are potential deviators. Agenti’s punishment quantity zi (p, x) is" selected# as follows. SinceF agent"" Ω i is# a potential#
deviator, there exists u such that xΩ
,
x
2
F
(u)
and
p
2
π
xi , x−i ", u . More−ii#over, forthrightness ensures that the strategy profile made up of m0i = p, xΩandim−i ≡ (m1", ..., mi−1#, mi+1 , ..., mn ) is a Nash equilibrium profile at u and g (m0i , m−i )is equal to xΩ
i , x−i . Hence, the attainable set gi (Mi , m−i ) of agent i is contained in
the weak lower contour set of ui at xΩ
i . Since there can be more than one environment
having the features of u and, moreover, the mechanism designer cannot exclude anyof such environments from being the true one, the preceding line of reasoning leads tothe conclusion that the attainable set gi (Mi , m−i ) is contained in the intersection of
agent i’s weak lower contour sets of all such environments at xΩ
i . Agent i’s punishment
quantity can be set equal to gi (mi , m−i ).
Formally, let p 2 P and xi 2 Q for every agent i be given.
P Let x ≡ (x1 , ..., xn )Ωdenote the announced quantity profile and let xi ≡ Ω − j6=i xj denote agent i’s
remainder.
"" ΩThe set# of# environments for" Ωwhich# agent i is a potential deviator"" Ω is defined
# #
−1
F
by F
xi , x−i , p ≡ {u 2 UN | xi , x−i 2 F (u) and p 2 π
xi , x−i , u }.
Forof such environments,
the weak lower contour set of ui at xΩ
i is defined by
" any
#
"
#
Ω
0
Ω
0
L xi , ui ≡ {xi 2 Q|ui xi ≥ ui (xi )}, whereas their intersection is defined by
ΛFi

"" Ω
# #
xi , x−i , p ≡\u2F −1 ((xΩi ,x−i ),p)

"
#
L xΩ
i , ui .

The set of potential
deviatorsforNash implementation is defined by'""# price-quantity#(
I F (p, x) ≡ i 2 N |F −1 xΩ
,
x
,
p
=
6
?
.
Hence:−iiP(i) If I F (p, x) = N , then there
exists #z (p,# x) 2 A, with z (p, x) = x if i2N xi = Ω,""such that zi (p, x) 2 ΛFi xΩ
i , x−i , p for every i 2 N .
As already noted, a semi-responsible agent i’s preference between being responsible
and being not responsible depends on strategies played by other agents as well as the10quantity(ies) obtained from them. The second important di¢culty for the mechanism
designer is to decide what quantity to assign to agent i when the latter plays a
responsible strategy while the other agents’ strategy choices are kept fixed. Hence,
we require the existence of suitable quantities to assign to agent i when agent i playsa responsible strategy mi and every other agent j plays mj = (p, xj ).
Since the existence of a suitable quantity for agent i is ensured by condition (i)when all agents are potential deviators at (mi , m−i ), the following condition (ii) encompasses cases where, instead, not all agents are potential deviators at that profile.10
That is, for any given p 2 P and x 2 Qn :(ii) If 1 ≤ #I F (p, x) ≤ ""n − 1, thenz̄ (p, x) 2 A such that for each# #there exists
F
i 2 N , z̄i (p, x) 2 ΛFi xΩ
,
x
,
p
if
i
2
I
(p,
x) and the announcement (p, xi )−ii∗is responsible for some allowable (u , F ), or else z̄i (p, x) = 0.
Note the above condition assigns the worst possible quantity to agents who are notpotential deviators at (p, x) or play strategies that are not responsible for the entire
economic domain UN . Furthermore, condition (ii) is a necessary condition for implementation. To see this, observe thatthe same arguments used above"" we can# repeat#to obtain that gi (Mi , m−i ) ⊆ ΛFi xΩ
,
x
,
p
for
every
agent i 2 I F (p, x). We can−iithen define agent i’s quantity z̄i (p, x) as follows: If i 2 I F (p, x) and mi = (p, xi )is responsible for some (u∗ , F ), then z̄i (p, x) = gi (m) or else, z̄i (p, x) = 0. The
verification of condition (ii) follows immediately from that definition.
Beside cases in which agents state the same prices, the mechanism designer needs
to support responsibility in cases where agent i reports prices that do not match withthose reported by other agents. In cases like this, the existence of a suitable quantity
for agent i is ensured by condition (iii) below. That is, for any given p 2 P andx 2 Qn :(iii) For any i 2 N , there exists a map zi (·; (p, x−i )) : P × Q ! Q such that forevery (p0 , x0i ),(a) If (p0 , x0i ) is responsible for ""some allowable(u∗ , F ) and i 2 I F (p, (x0i , x−i )), then##00zi ((p0 , x0i ) ; (p, x−i )) 2 ΛFi xΩ
i , x−i , p , with zi ((p , xi ) ; (p, x−i )) = zi (p, x) if
0
F
0
0
0
p = p and I (p, (xi , x−i )) = N , and with zi ((p , xi ) ; (p, x−i )) = z̄i (p, (x0i , x−i ))if p0 = p and 1 ≤ #I F (p, (x0i , x−i )) ≤ n − 1.
(b) Otherwise, zi ((p0 , x0i ) ; (p, x−i )) = 0.
Note that when the premises of condition (i) or (ii) are also met, the quantity selectedby the map zi (·; (p, x−i )) coincides with the quantity assigned to agent i by, respectively, zi (p, x) and z̄i (p, x). Moreover, in the same spirit of condition (ii), condition(iii) assigns the worst possible quantity to agent i when she plays a strategy thatis not responsible for the entire domain. However, unlike the first two conditions,condition (iii) does not require the existence of an allocation.
10. For a set S, we write #S to denote the number of elements in S.

11In light of our discussion on the existence of the punishment
allocationz (p, x) of""# #condition (i), it can be seen that gi ((p0 , x0i ) , m−i ) 2 ΛFi xΩ
,
x
,
p
if
agent
i is a−ii000potential deviator at (p, (xi , x−i )) and, moreover, (p , xi ) is a responsible strategy. We
can then define zi ((p0 , x0i ) ; (p, x−i )) by setting it equal to gi ((p0 , x0i ) , m−i ) if (p0 , x0i ) is
responsible for some allowable (u∗ , F ) and i 2 I F (p, (x0i , x−i )), or else equal to theworst possible quantity. Again, the verification of condition (iii) follows immediatelyfrom that definition. This definition"" Ωalso specifies# # the property of zi0 (·;0(p, x−i )) as sat00F
isfying zi ((p , xi ) ; (p, x−i )) 2 Λi xi , x−i , p for the case that (p , xi ) is responsible
for some allowable (u∗ , F ), i 2 I F (p, (x0i , x−i )), and p0 6= p.
The condition below states that if the punishment allocation z (p, x) of condition(i) is an equilibrium allocation of the strategic game (γ, Rγ [u∗ , F, H]), then it must
be an F -allocation at u∗ . Expressed di§erently, if the punishment allocation z (p, x)of condition (i) is not an F -allocation at u∗ and moreover, no agent j has a material
incentive to unilaterally deviate from zj (p, x), then at least one semi-responsible agent
in H is acting not responsibly and at least one of these agents can switch to a strategy
that is responsible for (u∗ , F ) and gives him/her no material loss. That is, for any
given p 2 P and x 2 Qn :
""
# #
"
#
∗
(iv) For any u∗ 2 UN and H 2 H, if I F (p, x) = N , ΛFj xΩ
j , x−j , p ⊆ L zj (p, x) , uj
for every j 2 N , and z (p, x) 2
/ F (u∗ ), then there is an agent i 2 H such that(a) (p, xi ) is not responsible for (u∗ , F ); and (b) there exists (p0 , x0i ) that is
responsible for (u∗ , F ) such that u∗i (zi ((p0 , x0i ) ; (p, x−i ))) = u∗i (zi (p, x)).
We ""have already# # seen that if mj = (p, xj ) for every agent j, then gj (Mj , m−j ) ⊆FΩΛj xj , x−j , p and z (p, x) = g (m) when all agents are potential deviators at∗
m. To verify condition (iv), suppose u""
is a truez (p, x) is not an F # environment,#∗
F
allocation at u and no quantity in Λj xΩ
,
x
,
p
is
strongly
preferred by agent j−jj
to zj (p, x). Then, no agent has a material incentive to unilaterally deviate from g (m).
By implementability, we then have that for at least one agent i 2 H, the strategy(p, xi ) is not responsible for (u∗ , F ) and the mechanism is such that it makes responsible reporting non-costly for this agent, in the sense that u∗i (gi ((p0 , x0i ) , m−i )) =u∗i (zi (p, x)) for a strategy (p0 , x0i ) responsible for (u∗ , F ). Observe that agent i is apotential deviator at (p, (x0i , x−i )) and so gi ((p0 , x0i ) , m−i ) = zi ((p0 , x0i ) ; (p, x−i )) by
condition (iii).
In summary, if the e¢cient allocation rule F is semi-responsibly Nash implementable by a natural p-q mechanism, then the following condition, which is a variant of the monotonicity condition and of the punishment condition due to Saijo,
Tatamitani and Yamato (1996, 1999), must be satisfied:nCondition M-PQ:
P Let F 2 F be given. Let p 2 P and x 2 Q be given. LetΩxi ≡ Ω − j6=i xj denote agent i’s remainder. Then, (i), (ii), (iii) and (iv) aresatisfied.

Condition M-PQ is not only necessary but is also su¢cient.

12

Theorem 1. Let n ≥ 3. Let Assumption 1 and F 2 F be given. F is semiresponsibly Nash implementable by a natural p-q mechanism if and only if itsatisfies condition M-PQ.
Proof. See Appendix.
In the su¢ciency part of Theorem 1, we constructed a mechanism that resembles
that of Saijo et al. (1996, 1999). However, unlike theirs, ours does not rely on any
sort of “tail-chasing” construction.11 We are able to do so because in our framework
there are semi-responsible agents as well as the allowance of free-disposal.
Remark 1. The devised implementing p-q mechanism is not balanced since out of
equilibrium the total demand is not necessarily equal to the total supply. Lombardi and Yoshihara (2013b) successfully constructed a balanced p-q mechanism,
but this construction relies on the so-called “modulo game”. As is well known, insuch games, mixed strategy Nash equilibria do exist and they are ruled out only by
assumption. To avoid this di¢culty, the so-called “integer game” can be used toconstruct a balanced p-q mechanism. Horeover, since each agent chooses a positive
integer in addition to a price vector p and a quantity q as her strategy choice, thatmechanism would not resemble any real-life mechanism. Sjöström (1996) successfully devised a market mechanism that does not use any sort of “integer game”
or “modulo game”, but his mechanism does not satisfy neither the best response
property nor balancedness. Dutta and Sen (2012) succeeded in constructing afeasible and bounded (in the sense of Jackson, 1992) direct mechanism using neither a “modulo game” nor an “integer game”, but their mechanism is neitherbalanced (out of equilibrium) nor a market mechanism (see Dutta and Sen, 2012;
Remark 4). This latter comment also extends to Kartik et al. (2014)’s mechanism. Therefore, as already noted by Saijo et al. (1996; p. 971), this suggeststhat the property of balancedness may not be compatible with a p-q mechanismthat is not subject to the critiques that are leveled against the mechanisms used
for Nash implementation. However, a definitive answer to this compatibility issue
is still unknown.

4.2

Natural implementation of the Walrasian ruleLet us turn now to a brief discussion of the implications of Theorem 1. As an exampleof e¢cient allocation rules in F satisfying our condition, we focus on the Walrasian
rule which we define next.
Walrasian rule, W : For each u 2 U , W (u) ≡ {x 2 A |there exists p 2 P such thatfor each i 2 N , it holds p · xi = p · ! i and for each yi 2 R`+ , ui (yi ) > ui (xi )implies p · yi > p · ! i }, where U is the class of all profiles of utility functions
that are continuous, quasi-concave and strongly monotonic on R`+ .
11. See Maskin (1999). For the criticism against such construction, see Jackson (1992).

13

We show below that the Walrasian rule satisfies condition M-PQ. We begin withan outline of its proof for the case where the profile x 2 Qn is totally balanced
and all agents are potential deviators for W at (p, x). In that case we can define
the punishment allocation of condition (i) by z (p, x) = x.12 Further, we take any
u 2 W −1 (p, x) and then show (on the basis that W is defined on the ‘unrestricted’domain U ) that the vector p is a supporting price for u and for W . This leads to theconclusion that for any agent i, the set ΛWi (x, p) is agent i’s constrained budget set.
Next, we fix an arbitrary environment u∗ where, for any agent i, the quantity xi
maximizes agent i’s utility u∗i over ΛWi (x, p). For the premises of condition (iv) to
be met, we also assume x is not a Walrasian allocation at u∗ . This means that there
exists an agent k for whom the quantity xk is not a utility maximizing quantity (interms of u∗k ) over the budget set for the given pair (p, ! k ). We then also observethat the price vector p cannot be an equilibrium price for u∗ - simply because any
solution to agent k’s maximization problem over the (unconstrained) budget set givenby the pair (p, ! k ) occurs outside the set Q. This allows us to establish that for every
agent i, the price-quantity pair (p, xi ) cannot be a responsible pair for (u∗ , W ), andso establish part (a) of condition (iv).
To prove part (b) of condition (iv), there are two things to prove: first, thatthe map zi (·; (p, x−i )) meets the requirements of condition (iii) and, second, thatu∗i (zi (p, x)) = u∗i (zi ((p∗ , x∗i ) ; (p, x−i ))) for a pair (p∗ , x∗i ) that is responsible for(u∗ , W ). In the definition of zi (·; (p, x−i )), we use the important insight that noresponsible price-quantity pairs for (u∗ , W ) can encompass the price vector p. In
fact, the key requirement behind its definition is that for agent i’s responsible pricequantity pairs (p0 , x0i ) for (u∗ , W ) the map should be unresponsive, in the sense thatzi ((p0 , x0i ) ; (p, x−i )) = zi (p, x). In turn, the completion of the proof of part (b) follows
directly from that property of the map zi (·; (p, x−i )). We will now summarize this asfollows.
Theorem 2. Let n ≥ 3. Let Assumption 1 be given. Then, the Walrasian rulesatisfies condition M-PQ.
Proof. See Appendix.
Remark 2. It bears mentioning again here that Theorem 2 is built on a definitionof natural p-q mechanisms that di§ers from that in Saijo et al. (1999). This isso because the requirement of forthrightness is based upon a notion of supporting
prices that depends on the e¢cient allocation rule considered. As already noted,
this choice is dictated by the consideration that supporting prices are not equallyimportant to every e¢cient allocation rule. This is particularly true for the Walrasian rule. Indeed, Theorem 2 fails to hold if we focus on the set of supporting
prices of Definition 3 and we base the requirement of forthrightness as well as thenotion of responsible reports upon this set. This can be shown by means of thefollowing example.
12. Where x was not a totally balanced allocation, we could define the punishment allocation of
condition (i) by z (p, x) = 0. In that case condition (iv) is satisfied (vacuously) where I W (p, x) = N .

14

As in Saijo et al. (1999), let us base the condition of forthrightness and the setof environments"" Ω#for #which agent i is a potential deviator, that is, the definition−1of F
xi , x−i , p (see p. 10), on the set of supporting prices of Definition
3. Furthermore, let us use this definition of supporting prices as the basis of
responsible strategies, that is, of Definition 6. With obvious adaptations of theproof of Theorem 1, one can see that (the new) condition M-PQ is a necessary
condition for Nash implementation with semi-responsible agents by a Saijo et al.
(1999)’s natural p-q mechanism. With these preliminaries in place, we are now ina position to show the example we mentioned in the preceding paragraph.
Example 1. For convenience, consider a setting with three agents and three commodities. The initial endowment of commodities is ! i = (1, 1, 1) for every agent
i. Consider the following quantities:
for agent 1 : x1 = (3, 0, 1) ,for agent 2 : x2 = (0, 3, 0) ,for agent 3 : x3 = (0, 0, 2) .
Note that the point x = (x1 , x2 , x3 ) is a boundary (balanced) allocation.
We can find a preference profile u 2 U such that x is a Walrasian allocation
at u with the equilibrium price pW = (1/6, 1/3, 1/2) and such that agent i’spreference ui is not di§erentiable at the quantity xi . This implies that the pricevector p = ((1/6) + (5/3) ", (1/3) − (2/3)", (1/2) − ") is an element of Π (x, u)
where " > 0 is arbitrarily small. Observe that agent i’s budget constraint isviolated at the price vector p, that is, p · xi 6= p · ! i , and so this p is not a
supporting price for u and W at x; that is, p 2/ ΠW (x, u). Also, note that for
any agent i, (p, xi ) is a responsible report for u and W given that x 2 W (u)and p 2 Π (x, u).
In addition, consider the following quantities:
for agent 1 : a1 = x1 , b1 = (2, 0, 0) and c1 = (3, 0, 1/2) ,for agent 2 : a2 = (0, 2, 0) , b2 = x2 and c2 = (0, 3, 1/2) ,for agent 3 : a3 = (0, 1, 2) , b3 = (1, 0, 3) and c3 = x3 .
Note that the points a = (a1 , a2 , a3 ), b = (b1 , b2 , b3 ) and c = (c1 , c2 , c3 ) areboundary (balanced) allocations.
We can find a preference profile u∗ 2 U satisfying the following requirements: (i) for each agent i = 1, 2, agent i’s preference u∗i is not di§erentiable
at the quantity ci ; (ii) agent 3’s preference u∗3 is not di§erentiable at the quantity a3 ; (iii) agent 1’s preference u∗1 is di§erentiable at the quantity a1 ; (iv)the price vector p is a supporting price for u∗ at x, that is, p 2 Π (x, u∗ ), and∗ΛWi (x, p) ⊆ L (xi , ui ) for every agent i; (v) the price vector pa = (1/4, 1/2, 1/4)
is a supporting price for u∗ at a, that is, pa 2 Π (a, u∗ ); (vi) the price vector
pb = (1/2, 1/3, 1/6) is a supporting price for u∗ at b, that is, pb 2 Π (b, u∗ ); and(vii) the price vector pc = (1/4, 1/4, 1/2) is a supporting price for u∗ at c, that15

is, pc 2 Π (c, u∗ ).
First, note that the allocation y is a Walrasian allocation at u∗ with theequilibrium price py for y = a, b, c. Also note that the allocation x is not a
Walrasian allocation at u∗ .13 Moreover, the set of potential deviators at (p, x)
is N , that is, I W (p, x) = N . Therefore, the hypotheses of part (iv) of condition
M-PQ are met. If the Walrasian rule satisfied part (iv) of condition M-PQ,
we would have that for some i, the pair (p, xi ) would not be a responsible
report for (u∗ , W ). However, since for all i, (p, xi ) is a responsible report for(u∗ , W ), this is not the case.
Remark 3. We should point out that even though Theorem 2 has been stated andproved assuming that the Walrasian rule is defined on the domain of all profilesof preferences that are continuous, quasi-concave and strongly monotonic on R`+(that is, on U ), its statement continues to hold for any preference domain UN
that includes the important special class of all profiles of linear preferences. Thischange does not harm the proof of Theorem 2 since the fact that the class of
linear preferences is a subclass of UN su¢ces to complete the important step of
the actual proof that the set of supporting prices for u at the Walrasian allocationx (at u) consists solely of Walrasian prices for u (and W ) at x; that is, π W (x, u) =ΠW (x, u) for every u 2 UN and x 2 W (u).

4.3

On the impossibility of implementing the egalitarianequivalent and e¢cient allocation rule

While the main implication of Theorem 1 is a positive one, as we discussed above,in this subsection we briefly show that condition M-PQ imposes non-trivial restrictions on the class of e¢cient allocation rules that are semi-responsibly Nash implementable by natural p-q mechanisms.
For an example of an allocation rule that fails to satisfy condition M-PQ, we
consider the egalitarian-equivalent and e¢cient rule, which was introduced by Paznerand Schmeidler (1978).
Egalitarian-equivalent and e¢cient rule, EE: For each u 2 U , EE (u) ≡ {x 2
A | there is a maximal number λ 2 (0, 1) such that ui (xi ) = ui (λΩ) for all
i 2 N } \ P (u), where U is the class of all profiles of utility functions that arecontinuous, quasi-concave and strongly monotonic on R`+ .
An allocation is egalitarian-equivalent and e¢cient in an economy u with respect
to a reference bundle if every agent i judges the proposed quantity and a common
quantity that is proportional to the aggregate endowment profile as equally good
13. Indeed, noting that pW is the only Walrasian equilibrium price vector whenever x is a Walrasianequilibrium allocation for some economy, x cannot be a Walrasian allocation at u∗ . "This is #because
x1 fails to maximize the utility of agent 1 over the budget set defined by the pair pW , ! 1 at theeconomy u∗ , due to the fact that u∗1 is di§erentiable at the quantity x1 and its gradient vector at x1
is equal to pa , which is di§erent from pW .

16

according to ui and if the proposed allocation is e¢cient for u. In other words, every
agent obtains the same surplus if we measure the agents’ surplus in terms of thereference bundle.
The next result shows that no natural p-q mechanism semi-responsibly Nash implements the egalitarian-equivalent and e¢cient rule. This is so because this rulefails to satisfy part (iv) of condition M-PQ. Specifically, this rule fails to satisfy our
variant of the monotonicity condition due to Saijo, Tatamitani and Yamato (1996,1999). This result is achieved by restricting the structure of the family H to the following specification: The family H has as elements all singletons of the set N . Thisrequirement is consistent with Assumption 1 since the mechanism designer cannot
exclude any member(s) of the society from being semi-responsible purely on the basisof that assumption.
Claim 1. Let n ≥ 3. Let Assumption 1 be given. Let the family H have as elements
all singletons of the set N . Then, the egalitarian-equivalent and e¢cient rule does
not satisfy condition M-PQ.
Proof. See Appendix.
Remark 4. It is worth emphasizing that the proof of the above negative result isestablished by employing profiles of utility functions that are strictly concave anddi§erentiable. Thus, the above result continues to hold if we define the egalitarianequivalent and e¢cient rule on the class of all profiles of utility functions that arestrictly concave and di§erentiable, which is a proper subset of the class U .

5Concluding remarks

In this paper, Nash implementation problems by natural p-q mechanisms when agentsare semi-responsible are studied. We o§er a condition called M-PQ and show that not
only does this condition fully identify the class of e¢cient rules that are implementable
when at least one agent is semi-responsible, but also that the Walrasian rule satisfies
it.
Similar to the results of Dutta and Sen (2012) and Kartik et al. (2014), freedisposal plays a crucial role for our results. When feasibility constraints are imposedwith an equality, the analysis of implementation problems by natural p-q mechanisms
is more di¢cult, as it requires the construction of an outcome function satisfying
the additional property of strong balancedness: assigned quantities must sum to theaggregate endowment for every agents’ strategy choices. This analysis is undertaken
in Lombardi and Yoshihara (2013b).
In this paper, the mechanism designer knows the individual endowments, but not
the individual’s preference for quantities. Hurwicz et al. (1995) have shown thatthe constrained Walrasian rule can be Nash implemented by a p-q mechanism whenthe mechanism designer knows neither endowments nor preferences. Although theimplementation model developed in this paper needs to be modified to handle this17

case, we believe a similar result holds for the Walrasian rule when the mechanism
designer knows that at least one agent is semi-responsible, but neither endowments
nor preferences. This subject is left for future research.

Appendix
Proof of Theorem 1. Let the premises hold. Fix any F 2 F. The proof thatcondition M-PQ is necessary for semi-responsible Nash implementation of F by anatural p-q mechanism is discussed in the main text and so is omitted here (see theAddendum below for formal arguments). In the following, we prove that condition
M-PQ is also su¢cient for it. We then suppose that F satisfies condition M-PQ.
We first establish some notation and definitions. For any x 2 Qn and any p 2 P ,define the set @ΛFi (x, p) by @ΛFi (x, p) ≡ {yi 2 Q|yi 2 ΛFi (x, p) and @zi 2 ΛFi (x, p)
such that zi ≫ yi }. For each i 2 N , let Mi ≡ P × Q and let mi = (pi , xii ) denote
agent i’s strategy. For any m 2 M , u 2 UN , x 2 Qn and p 2 P , define Nu (m)by Nu (m) ≡ {i 2 N |mi = (pi , xii ) is responsible for (u, F )} and Nu (m; (x, p)) by
Nu (m; (x, p)) ≡ {i 2 Nu (m) |mi = (p, xi ) , x 2 F (u) , p 2 π F (x, u)}. With thesepreliminaries, we define the outcome function g for any m 2 M to be:
Rule 1: If for all j 2 N , mj = (p, xj ), I F (p, x) = N , then g (m) = z (p, x).
Rule 2: If for all j 2 N , mj = (p, xj ) with xj 6= 0, 1 ≤ #I F (p, x) ≤ n − 1, theng (m) = z̄ (p, x).
Rule 3: If for some i 2 N , mj = (p, xj ) for all j 6= i and mi = (pi , xii ), with p 6= pi
and xii 6= 0, i 2 I F (p, x), then:8ii>> (zi ((p , xi ) ; (p, x−i )) , 0−i ) if zi ((p i, xi ) ; (p, x−i )) 6= 0;<
if zi ((p ,""xi ) ; (p, x#−i ))#= 0 and
g (m) =
(xi , 0−i )
F
x
2
Λ
xΩ
>
i
i
i , x−i , p ;>:(x̂i , 0−i )otherwise,""# #T
where {x̂i } ≡ @ΛFi xΩ{yi 2 R`+ |9α 2 R+ , yi = αxi }.
i , x−i , p
Rule 4: Otherwise:

Rule 4.1: If for some i, xii = 0, Nu (m; (x, p)) 6= ? for some (u, x, p),$#Nu (m; (x, p)) ≥%#Nū (m; (x̄, p̄)) for all (ū, x̄, p̄),14 then for each i 2 N , gi (m) = (n+1)−#Nxiu (m;(x,p)) .
Rule 4.2: Otherwise, g (m) = 0.

Note that γ ≡ (M, g) is a natural
Note also that in Rule 3 agent"" Ωp-q mechanism.
# #F
i can realize any element of @Λi xi , x−i , p by a suitable choice of mi = (pi , xii ).
14. If there is more than one of type Nu (m; (x, p)) having the maximal cardinality, fix any one of
them.

18

Let (u∗ , H) be the true state of the world. We show that F (u∗ ) = N A (γ, Rγ [u∗ , F, H]).
Since it is a routine exercise to prove F (u∗ ) ⊆ N A (γ, Rγ [u∗ , F, H]), we shall omit
the proof here. Conversely, fix any m 2 N E (γ, Rγ [u∗ , F, H]). Note, m cannot correspond to Rule 2 nor to Rule 3 nor to Rule 4.15 Suppose therefore m falls into
Rule 1.
Then, g (m)Rule 3 and attain any quan"" = z (p,#x). #Note that each i can induce00tity x̂i 2 @ΛFi xΩ
,
x
,
p
by
suitably
selectingm=(p, x0i ), where""p0 is a boundary
−i
i
i
""
#
#
# #
F
Ω
point of P and x0i 2 Q\ΛFi xΩ
i , x−i , p . Then, we have that @Λi "" xi , x−i# , p# ⊆gi (Mi , m−i ). It follows from m 2 N E (γ, Rγ [u∗ , F, H]) that @ΛFi xΩ
i , x−i"" ,Ωp ⊆# #∗∗`F
L (zi (p, x) , ui ). Since ui is strongly monotonic on R+ , it can be seen that Λi xi , x−i , p ⊆L (zi (p, x) , u∗i ). Note that since i 2 N was arbitrary, the latter set inclusion holds
for any i 2 N .
Further, suppose z (p, x) 2
/ F (u∗ ). Condition M-PQ implies that there exists
i 2 H such that mi is not responsible for (u∗ , F ) and u∗i (zi ((p0 , x0i ) ; (p, x−i ))) =u∗i (zi (p, x)) for a strategy (p0 , x0i ) that is responsible for (u∗ , F ). Agent i can change
mi = (p, xi ) into m0i = (p0 , x0i ). If p = p0 , then she obtains gi (m0i , m−i ) = zi ((p0 , x0i ) ; (p, x−i ))by either Rule 1 or Rule 2. On the other hand, if p 6= p0 , then agent i obtains
gi (m0i , m−i ) = zi ((p0 , x0i ) ; (p, x−i )) by Rule 3. In either case, agent i obtains a profitable deviation, in violation of m 2 N E (γ, Rγ [u∗ , F, H]). We conclude from thisthat z (p, x) 2 F (u∗ ). Since (u∗ , H) was arbitrary, the proof is completed.
Proof of Theorem 2. Let the premises
hold. Recall Definition 4. Fix any p 2 PPnΩand x 2 Q . Recall xi denotes Ω − j6=i xj .
Note that if x 2 W (u) for some u 2 U and p 2 π W (x, u), then p is a supporting
price for x and for W ; that is, p 2 ΠW (x, u) (simply because W is defined on U ).
Further, if x 2 W (u) for some u 2 U and p 2 π W (x, u), then for all i 2 N , wehave ΛWi (x, p) = {yi 2 Q | p · yi ≤ p · ! i }. With these preliminaries, let us first verify
conditions (i), (ii) and (iii).
W
P Suppose that I (p, x) = N . Define
P z (p, x) as follows: (a) z (p, x) = x if
x
=
Ω,
and
(b)
z
(p,
x)
=
0
if
j2N j
j2N xj 6= Ω. Then for all i 2 N , we have"" Ω # #Wzi (p, x) 2 Λixi , x , p . This verifies condition (i).
Suppose that 1 ≤ #I W (p, x) ≤ n − 1. Define z̄ (p, x) to be z̄ (p, x) = 0. Then,condition (ii) is satisfied.
Fix any i 2 N . Define zi (·; (p, x−i )) for any (p0 , x0i ) to be (a) zi ((p0 , x0i ) ; (p, x−i )) =
0
0
0
W
xΩ
(p, (x0i , x−i ));i if (p , xi ) is responsible for some allowable (u, W ), p 6= p and i 2 I0000(b) zi ((p , xi ) ; (p, x−i )) = zi (p, x) if (p , xi ) is responsible for some allowable (u, W ),p0 = p and I W (p, (x0i , x−i )) = N ; (c) zi ((p0 , x0i ) ; (p, x−i )) = z̄i (p, x) if (p0 , x0i ) is responsible for some allowable (u, W ), p0 = p, i 2 I W (p, (x0i , x−i )) and 1 ≤ #I W (p, (x0i , x−i )) ≤n − 1; (d) zi ((p0 , x0i ) ; (p, x−i )) = 0, otherwise. We then have condition (iii)Psatisfied.
Finally, we show that W satisfies condition (iv). Let I W (p, x) = N . If j2N xj 6=Ω,
Therefore, let
P then z (p, x) = 0 and so condition (iv) is vacuously satisfied.
∗x = Ω and so z (p, x) = x. Suppose that for some u 2 U , ΛWj (x, p) ⊆"j2N ∗j #∗−1
L xj , uj for all j 2 N and x 2/ W (u ). Since W (x, p) is non-empty, it follows that
15. Formal arguments can be found in Lombardi and Yoshihara (2014).

19

there is u 2 U such that x 2 W (u) and p 2 π W (x, u), and therefore p 2 ΠW (x, u).
Since x 2
/ W (u∗ ), there is an agent j 2 N such that xj 2
/ arg maxyj 2R`+ :p·yj ≤p·!j u∗j (yj ).
Moreover, since p 2 π W (x, u) and u 2 U imply that p ≫ 0, there exists x∗j such that"#∗x∗j 2 arg maxyj 2R`+ : p·yj ≤p·!j u∗j (yj ). However, by ΛWj (x, p) ⊆ L xj , uj , it follows
that x∗j 2/ Q. We then have that p cannot be a competitive equilibrium price foru∗ and so for all i 2 N , (p, xi ) is not responsible for (u∗ , W ). Let H 2 H andi 2 H be given. Let (p0 , x0i ) be any responsible pair for (u∗ , W ). Then, p0 6= p. By
I W (p, x) = N , it follows that i 2 I W (p, (x0i , x−i )). By definition of zi (·; (p, x−i )), we
have zi ((p0 , x0i ) ; (p, x−i )) = xi . This completes the proof of condition (iv).
Proof of Claim 1. Let the premises hold. Take any profile u 2 U such that ui
is strictly concave and di§erentiable for every agent i 2 N . Furthermore, fix any
interior allocation x 2 EE (u) \ Rn`++ .
Note that there exists a unique supporting price p for u and EE at x, that is,
π EE (x, u) = {p}, and that the set ΛEE(x, p) is a well-defined set for every agent i.
i
By definition of the rule, it follows that for every v 2 EE −1 (x, p) it holds that there
exists a unique real number λv in the open interval (0, 1) such that vi (xi ) = vi (λv Ω)for every agent i.
Write λmin for the solution to the problem:'(min λv |for v 2 EE −1 (x, p) : vi (xi ) = vi (λv Ω) for every i 2 N ,and write @ΛEE
(x, p) for the upper boundary of ΛEE(x, p), that is:
i
i

@ΛEE
(x, p) ≡ {yi 2 Q|yi 2 ΛEE(x, p) and @zi 2 ΛEE(x, p) such that zi ≫ yi }.
iii
By construction, it follows that the common quantity λmin Ω is an element of@ΛEE(x, p) for every agent i. Moreover, for every agent i it also holds that thereiis a proper subset B (xi ) of @ΛEE
(x, p), which constitutes a neighborhood of xi iniEE@Λi (x, p). By taking such an neighborhood su¢ciently small, it follows from thedefinition of @ΛEE
(x, p) that p · yi = p · xi for every quantity yi 2 B (xi ), since xi isi
an interior consumption bundle.
Fix any two distinct agents j and k. Take any profile u∗ 2 U such that u∗i isstrictly concave and di§erentiable for every agent i, that ΛEE(x, p) ⊆ L (xi , u∗i ) forievery agent i and that for a su¢ciently small real number ϵ > 0 and for a real number
λ > λmin it holds that:u∗i (xi )u∗j (xj + (ϵ, 0))u∗k (xk − (ϵ, 0))Du∗j (xj + (ϵ, 0))

=
=
=
=

u∗i (λΩ) for every agent i 6= j, k,u∗j (λΩ) ,u∗k (λΩ) and{p} = Du∗k (xk − (ϵ, 0)) ,where 0 is the ` − 1-th dimensional zero vector and where Du∗j (xj + (ϵ, 0)) andDu∗k (xk − (ϵ, 0)) denote the gradient vector respectively at the quantity xj + (ϵ, 0)and at xk − (ϵ, 0). This profile u∗ exists because of our domain assumption. By
20

the construction of u∗ , B (xi ) ⊆ L (xi , u∗i ) for every agent i, which implies that{p} = Π (x, u∗ ). Thus, x 2 P O (u∗ ).
By the above discussion, there exist a real number λj in the open interval (λmin , λ)and a real number λk > λ such that u∗j (xj ) = u∗j (λj Ω) and that u∗k (xk ) = u∗k (λk Ω).
Therefore, since λk > λ > λj , x is not egalitarian-equivalent at the profile u∗ . Thus,
x 2 P O (u∗ ) \EE (u∗ ). The allocation x∗ , which assigns the quantity x∗i = xi to every
agent i 6= j, k, the quantity x∗j = xj +(ϵ, 0) to agent j and the quantity x∗k = xk −(ϵ, 0)
to agent k, is an egalitarian-equivalent and e¢cient allocation at u∗ and, moreover,the price vector p is a supporting price for u∗ and possibly for EE at this x∗ , that is,p 2 π EE (x∗ , u∗ ).16
Take any agent i 6= j, k. The singleton {i} is an element of the collection H since
this collection has as elements all singletons of the set N and since, moreover, there
are n ≥ 3 agents in N . We have that the pair (p, xi ) is responsible for (u∗ , EE), in
violation of part (iv) of condition M-PQ.

References
Corchón L, Herrero C (2004) A decent proposal. Span Econ Rev 6:107-125
Bochet O (2007) Implementation of the Walrasian Correspondence: the Boundary
Problem. Int J Game Theory 36:301-316 (2007)
Doğan B (2014) Essays on Mechanism Design and Implementation, PhD dissertation,
University of Rochester
Dutta B, Sen A (2012) Nash implementation with partially honest individuals. Games
Econ Behav 74:154-169
Dutta B, Sen A, Vohra R (1995) Nash implementation through elementary mechanisms in economic environments. Econ Des 1:173-204
Eliaz K (2002) Fault-tolerant implementation. Rev Econ Stud 69:589-610
Glazer J, Rubinstein A (1998) Motives and implementation: On the design of mechanisms to elicit opinions. J Econ Theory 79:157-173
Hurwicz L (1978) On the interaction between information and incentives in organizations. In Krippendor§ K (eds) Communication and Control in Society, 123-147.
Scientific Publishers, Inc., New York
Hurwicz L, Maskin E, and Postlewaite A (1995) Feasible Nash implementation ofsocial choice rules when the designer does not know endowments or production sets.
In Ledyard J (eds) The economics of informational decentralization: Complexity, e¢ciency, and stability, Essays in Honor of Stanley Reiter, 367-433. Kluwer, Amsterdam
Jackson MO (1992) Implementation in undominated strategies: A look at boundedmechanisms. Rev Econ Stud 59:757-775
16. Note that since the egalitarian-equivalent and e¢cient rule is essentially single-valued, andsince, moreover, each u∗i is strictly concave, it follows that EE (u∗ ) = {x∗ }. An allocation rule F isessentially single-valued if for every allowable profile u it holds that: x, x0 2 F (u) =) ui (xi ) =ui (x0i ) for every agent i 2 N .

21

Jackson MO (2001) A crash course in implementation theory. Soc Choice Welfare
18:655-708
Kartik N, Tercieux O (2012) Implementation with evidence. Theoretical Econ 7:323355
Kartik N, Tercieux O, Holden R (2014) Simple mechanisms and preferences for honesty. Games Econ Behav 83:284-290
Lombardi M, Yoshihara N (2013a) A full characterization of Nash implementation
with strategy space reduction. Econ. Theory 54:131-151
Lombardi M, Yoshihara N (2013b) Natural implementation with partially honest
agents. IER Discussion Paper Series A, No.561, The Institute of Economic Research,
Hitotsubashi University
Lombardi M, Yoshihara N (2014) Natural implementation with partially-honest agentsin economic environments with free-disposal. IER Discussion Paper Series A, No.616,
The Institute of Economic Research, Hitotsubashi University
Maskin E (1999) Nash equilibrium and welfare optimality. Rev Econ Stud 66:23-38
Matsushima H (2008a) Role of honesty in full implementation. J Econ Theory
139:353-359
Matsushima H (2008b) Behavioral aspects of implementation theory. Econ Lett
100:161-164
Otani Y, Sicilian J (1982) Equilibrium of Walras preference games. J Econ Theory
27:47-68
Pazner E, Schmeidler D (1978) Egalitarian Equivalent Allocations: A New Conceptof Economic Equity. QJ Econ 92:671-686.
Postlewaite A, Wettstein D (1989) Feasible and Continuous Implementation. Rev
Econ Stud 56:603-611
Saijo T, Tatamitani Y, Yamato T (1996) Toward natural implementation. Int Econ
Rev 37:949-980
Saijo T, Tatamitani Y, Yamato T (1999) Characterizing natural implementability:
The fair and Walrasian correspondences. Games Econ Behav 28:271-293
Saporiti A (2014) Securely implementable social choice rules with partially honest
agents. J Econ Theory 154:216-228
Sjöström T (1996) Implementation by demand mechanisms. Econ Des 1:343-354
Tatamitani Y (2001) Implementation by self-relevant mechanisms. J Math Econ
35:427-444
Thomson W (1984) The manipulability of resource allocation mechanisms. Rev Econ
Stud 51:447-460
Thomson W (1999) Monotonic extensions on economic domains. Rev Econ Design
4:13-33
Tian G (1992) Implementation of the Walrasian Correspondence without Continuous,
Convex, and Ordered Preferences. Soc. Choice Welfare 9:117-13022