Discussion Papers In Economics
And Business

Relationships between Non-Bossiness andNash Implementability
Hideki Mizukami
Takuma Wakayama
Discussion Paper 05-33

Graduate School of Economics andOsaka School of International Public Policy (OSIPP)
Osaka University, Toyonaka, Osaka 560-0043, JAPANRelationships between Non-Bossiness andNash Implementability
Hideki Mizukami
Takuma Wakayama
Discussion Paper 05-33
December 2005

この研究は「大学院経済学研究科・経済学部記念事業」
基金より援助を受けた、記して感謝する。

Graduate School of Economics andOsaka School of International Public Policy (OSIPP)
Osaka University, Toyonaka, Osaka 560-0043, JAPANRelationships between Non-Bossiness andNash Implementability∗
Hideki Mizukami†
Faculty of Economics, University of Toyama
mizukami@eco.toyama-u.ac.jp

andTakuma Wakayama
Graduate School of Economics, Osaka University
wakayama@iser.osaka-u.ac.jp

December 1, 2005∗
We are grateful to Shigehiro Serizawa, Koji Takamiya, and seminar participants at the2005 RIMS Workshop “Mathematics of Optimization: Methods and Practical Solutions” fortheir valuable comments.
†
Correspondent: Faculty of Economics, University of Toyama, 3190 Gofuku, Toyama
930-8555, JAPAN.

1

Abstract
We explore the relationships between non-bossiness and Nash implementability. We provide a new domain-richness condition, weak
monotonic closedness, and prove that on weakly monotonically closed
domains, non-bossiness together with individual monotonicity is equivalent to monotonicity, a necessary condition for Nash implementation. The result shows an impossibility of Nash implementation in all
economies except pure public goods economies, in the sense that it
indicates that in all economies except pure public goods economies, it
is impossible to implement bossy social choice functions in Nash equilibria, which embody the characteristics inherent in those economies.
Keywords: Non-Bossiness, Individual Monotonicity, Monotonicity,
Weak Monotonic Closedness.
JEL Classification Numbers: D51, D71, D78.

2

1 Introduction
The mechanism design literature has dealt with a very large number of
allocation rules (or direct revelation mechanisms). The following is an example of the allocation rules in a private goods economy: an allocation rule
where there is an agent, called a boss, who can change another agent’s consumption bundle by changing her preferences without changing her own
bundle. This type of allocation rule was called bossy by Satterthwaite andSonnenschein (1981); but the idea of the bossy allocation rules had alreadybeen known, since the well-known Vickrey–Clarke–Groves type of allocation rules (Vickrey (1961), Clarke (1971), and Groves (1973)) were bossy. So,
bossy allocation rules can be regarded as acceptable if the Vickrey–Clarke–
Groves type of allocation rules seem attractive.
The standard economic theory tells us that agents are assumed to be
selfish. This means that bosses do not care about consumption bundlesof the other agents; so bosses will not deliberately change another agent’s
consumption bundle by changing her preferences even if her own bundle is
kept unchanged. This is a key to making the Vickrey–Clarke–Groves typeof allocation rules work well.
Nevertheless, Satterthwaite and Sonnenschein (1981) thought of bossy
allocation rules as undesirable at least in terms of simplicity (see Satterthwaite and Sonnenschein (1981) for details). So, they introduced the notionof non-bossiness, which requires that there should be no boss. Non-bossinesshas since been widely used in the literature on strategy-proofness.1
But, almost all of the literature has not explained non-bossiness’s reasonableness and desirability. Non-bossiness has often been imposed for technical convenience with the following exceptions: Barberà and Jackson (1995)
showed that non-bossiness plus strategy-proofness implies weak coalitional strategy-proofness in pure exchange economies, and Pàpai (2000a)and Takamiya (2001) showed that non-bossiness together with strategyproofness is equivalent to coalitional strategy-proofness in the house allocation problem and in the Shapley–Scarf housing market with strict preferences, respectively. These tell us that non-bossiness is desirable in the sensethat when combined with strategy-proofness, it prevents manipulation bycoalitions of agents.
However, coalitional strategy-proofness is too demanding in general,1
A partial list of such literature includes Barberà and Jackson (1995), Ju (2004), and Serizawa (2005) for pure exchange economies; Svensson (1999), Takamiya (2001), Miyagawa(2002), and Pàpai (2003) for the housing market of Shapley and Scarf (1974); Miyagawa(2001) and Svensson and Larsson (2002) for the Shapley–Scarf housing market with compensation; Svensson (1999), Pàpai (2000a), Pàpai (2000b), and Pàpai (2001) for the houseallocation problem; Schummer (2000a) and Svensson and Larsson (2002) for the houseallocation problem with compensation; Klaus (2001) for allotment economies with singledipped preferences; Serizawa (1996) for public good economies; and Dearden and Einolf(2003) for excludable public good economies.

3

because it prevents not only self-enforcing coalitional manipulations but
also non-self-enforcing coalitional manipulations. The standard economic
theory also tells us that in non-cooperative environments, agents can freely
discuss their actions but cannot make binding commitments. This indicatesthat there is no need to rule out coalitional manipulations that are not selfenforcing unless an additional assumption that agents can sign binding
agreements is imposed. So, when coupled with strategy-proofness, nonbossiness appears too strong without the additional assumption.2
Thus, the issue concerning reasonableness and desirability of nonbossiness seems still open. This paper examines the desirability of nonbossiness by exploring the relationships between non-bossiness and Nash
implementability.3
This paper is organized as follows. Section 2 gives notation and definitions. We explore the relationships between non-bossiness and Nash
implementability in Section 3. Section 4 contains a concluding remark.

2 Notation and Definitions
Let N := {1, 2, . . . , n} be the set of agents, where 2 ≤ n < +∞. Let Xi be theconsumption space for agent i ∈ N, where Xi is an arbitrary non-empty set.
Let A ⊆ X1 × X2 × · · · × Xn be the set of feasible allocations. Given a ∈ A, let ai
denote agent i’s consumption bundle.
Each agent i ∈ N has preferences over Xi , which are represented by acomplete and transitive binary relation Ri . The strict preference relation
associated with Ri is denoted by Pi . Let Ri denote the set of possible
preferences for agent i ∈ N. A domain is denoted by R := R1 × R2 × · · · × Rn .
A preference profile is a list R = (R1 , R2 , . . . , Rn ) ∈ R .
Let LCi (a; Ri ) := {b ∈ A | ai Ri bi } be agent i’s lower contour set of a ∈ A atRi ∈ Ri . Let UCi (a; Ri ) := {b ∈ A | bi Ri ai } be agent i’s upper contour set of a ∈ A
at Ri ∈ Ri .
A social choice function is a single-valued function f : R → A that assigns
a feasible allocation a ∈ A to each preference profile R ∈ R . Let fi denote
agent i’s consumption bundle assigned by f .
Now we introduce a domain-richness condition. A domain R is weakly
monotonically closed if, for all i ∈ N, all Ri , R0i ∈ Ri , and all a, b ∈ A with ai = bi ,there exists R̄i ∈ Ri such that LCi (a; Ri ) ⊆ LCi (a; R̄i ) and LCi (b; R0i ) ⊆ LCi (b; R̄i ).
2
It might not be necessary to worry about manipulation by very large coalitions, because
it is difficult to coordinate actions of agents in such coalitions, as pointed out by Schummer(2000b) and Serizawa (2005). So, non-bossiness together with strategy-proofness might stillseem strong, even if the additional assumption is imposed.
3
In the Shapley–Scarf housing market with strict preferences, Takamiya (2001) has already shown that non-bossiness has relationships to Nash implementability. In other environments, however, the relationship of non-bossiness to Nash implementability is not yet
known.

4Note that every rich domain in the sense of Dasgupta et al. (1979) is weakly
monotonically closed, but not vice versa. As shown by Dasgupta et al.
(1979), for example, the domain of all quasi-linear preferences over public
goods and transfers is not rich, but is weakly monotonically closed.
Next we introduce two properties of social choice functions. Nonbossiness (Satterthwaite and Sonnenschein (1981)) requires that if an agent
changes her preferences but her consumption bundle is unchanged, thenthe bundle of each agent should be unchanged.
Definition 1 (Non-Bossiness). A social choice function f satisfies nonbossiness if, for all R ∈ R , all i ∈ N, and all R0i ∈ Ri , if fi (R) = fi (R0i , R−i ), thenf (R) = f (R0i , R−i ).
Monotonicity (Maskin (1999)) is a necessary condition for Nash implementation.
Definition 2 (Monotonicity). A social choice function f satisfies monotonicity if, for all R, R0 ∈ R , if LCi ( f (R); Ri ) ⊆ LCi ( f (R); R0i ) for all i ∈ N, thenf (R0 ) = f (R).

3 Results
In this section, we examine the relationships between non-bossiness andNash implementability. We begin by looking at the relationships between
non-bossiness and monotonicity.
Lemma 1. Suppose that R is weakly monotonically closed. Then, if a social choicefunction f satisfies monotonicity, then it satisfies non-bossiness.
Proof. Pick any R ∈ R , any i ∈ N, and any R0i ∈ Ri such that fi (R) =fi (R0i , R−i ). We want to show f (R) = f (R0i , R−i ).
Since R is weakly monotonically closed, we can choose R̄i ∈ Ri suchthat LCi ( f (R); Ri ) ⊆ LCi ( f (R); R̄i ) and LCi ( f (R0i , R−i ); R0i ) ⊆ LCi ( f (R0i , R−i ); R̄i ).
Since LC j ( f (R); R j ) ⊆ LC j ( f (R); R j ) and LC j ( f (R0i , R−i ); R j ) ⊆ LC j ( f (R0i , R−i ); R j )for all j , i, monotonicity implies f (R̄i , R−i ) = f (R) and f (R̄i , R−i ) = f (R0i , R−i ),respectively. Thus, f (R) = f (R̄i , R−i ) = f (R0i , R−i ).
Lemma 1 says that monotonicity implies non-bossiness. However, nonbossiness alone cannot imply monotonicity; but, as shown in Lemma 2 below, non-bossiness together with individual monotonicity (Takamiya (2001))
can imply monotonicity.
Definition 3 (Individual Monotonicity). A social choice function f satisfies
individual monotonicity if, for all R ∈ R , all i ∈ N, and all R0i ∈ Ri , if
LCi ( f (R); Ri ) ⊆ LCi ( f (R); R0i ), then fi (R0i , R−i ) = fi (R).
5

Remark 1. Individual monotonicity is weaker than monotonicity by definition.
Lemma 2. If a social choice function f satisfies both non-bossiness and individual
monotonicity, then it satisfies monotonicity.
Proof. Pick any R, R0 ∈ R such that LCi ( f (R); Ri ) ⊆ LCi ( f (R); R0i ) for all i ∈ N.
We want to show f (R0 ) = f (R).
Step 1: f (R0i , R−i ) = f (R).

Since LCi ( f (R); Ri ) ⊆ LCi ( f (R); R0i ), individual monotonicity implies fi (R0i , R−i ) =fi (R). So, we have f (R0i , R−i ) = f (R) by non-bossiness.
Step 2: f (R0i , R0j , R−i, j ) = f (R0i , R−i ).

Since f (R) = f (R0i , R−i ) by Step 1, we have LC j ( f (R0i , R−i ); R j ) ⊆ LC j ( f (R0i , R−i ); R0j ).
So, individual monotonicity implies f j (R0i , R0j , R−i, j ) = f j (R0i , R−i ). Therefore,
we obtain f (R0i , R0j , R−i, j ) = f (R0i , R−i ) by non-bossiness.
Iteration of these steps for remaining agents in N yields f (R0 ) = f (R).



We are now ready to provide the result concerning the relationships between non-bossiness and monotonicity, which follows directly from Lemmas 1 and 2 and Remark 1.
Theorem 1. Suppose that R is weakly monotonically closed. Then, a social choicefunction satisfies monotonicity if and only if it satisfies both non-bossiness andindividual monotonicity.
Remark 2. In classical pure exchange economies with continuous, strictly
monotone, and strictly convex preferences, it is easy to show that Theorem 1
remains true if we replace monotonicity and individual monotonicity withweak monotonicity4 and individual weak monotonicity,5 respectively. So, nonbossiness plus individual weak monotonicity is equivalent to weak monotonicity in pure exchange economies. This improves upon the well-known
result of Barberà and Jackson (1995), which states that non-bossiness together with strategy-proofness6 implies weak monotonicity in pure exchange
economies, because individual weak monotonicity is weaker than strategyproofness in pure exchange economies.
The following is a direct corollary of Theorem 1.
4
A social choice function f satisfies weak monotonicity if, for all R ∈ R , all i ∈ N, and
all R0i ∈ Ri , if (i) UCi ( f (R); R0i ) ⊆ UCi ( f (R); Ri ) and (ii) ai Pi fi (R) for all a ∈ UCi ( f (R); R0i ) withai , fi (R), then f (R0i , R−i ) = f (R).
5
A social choice function f satisfies individual weak monotonicity if, for all R ∈ R , all i ∈ N,
and all R0i ∈ Ri , if (i) UCi ( f (R); R0i ) ⊆ UCi ( f (R); Ri ) and (ii) ai Pi fi (R) for all a ∈ UCi ( f (R); R0i )with ai , fi (R), then fi (R0i , R−i ) = fi (R).
6
A social choice function f satisfies strategy-proofness if, for all R ∈ R and all i ∈ N, there
is no R0i ∈ Ri such that fi (R0i , R−i )Pi fi (R).

6

Corollary 1 (Takamiya (2001)). In the Shapley–Scarf housing market with strict
preferences (Shapley and Scarf (1974)), a social choice function satisfies monotonicity if and only if it satisfies both non-bossiness and individual monotonicity.
When coupled with the well-known results of Maskin (1999), Theorem
1 leads to the following corollaries, too.
Corollary 2. Suppose that R is weakly monotonically closed. Then, if a social
choice function is Nash implementable, then it satisfies both non-bossiness andindividual monotonicity.
Corollary 3. Suppose that n ≥ 3. Then, if a social choice function satisfies
non-bossiness, individual monotonicity, and no veto power,7 then it is Nash implementable.
Corollary 2 implies that every social choice function that violates nonbossiness or individual monotonicity is never Nash implementable, provided that R is weakly monotonically closed. So, bossy social choice functions (e.g., the second-price auction (Vickrey (1961)), the pivotal mechanism(Clarke (1971)), the inversely dictatorial rule (Zhou (1991)), etc.) are neverNash implementable.
Corollaries 2 and 3 together indicate that non-bossiness has close relationships to Nash implementability, in the sense that non-bossiness is anecessary condition for Nash implementation and is part of the sufficientcondition for Nash implementation. These relationships tell us that nonbossiness is desirable from the point of view of Nash implementability. The
desirability of non-bossiness seems important in terms of requiring no additional assumption, which is in contrast to the desirability mentioned in
the Introduction.

4 Conclusion
As pointed out by Satterthwaite and Sonnenschein (1981), non-bossiness is
automatically satisfied in pure public goods economies, i.e., in economies
with non-excludability and non-rivalness. It might show the universality of imposing non-bossiness. At the same time, however, it means thatbossiness is characteristic of economies with excludability or rivalness, suchas private goods economies, excludable public goods economies, and thecommons. So, a negative aspect of imposing non-bossiness is that it rules
out social choice functions inherent in economies with excludability or rivalness to identify such economies with pure public goods economies. In
taking account of these, Corollary 2 shows an impossibility of Nash implementation in economies with excludability or rivalness, in the sense that
A social choice function f satisfies no veto power if, for all R ∈ R , all a ∈ A, and all i ∈ N,
if a j R j b j for all b ∈ A and all j , i, then f (R) = a.
77the corollary indicates that in economies with excludability or rivalness, it
is impossible to implement bossy social choice functions in Nash equilibria,
which embody the characteristics inherent in those economies.

8ReferencesB̀, S.  M. O. J (1995): “Strategy-Proof Exchange,” Econometrica, 63, 51–87.
C, E. H. (1971): “Multipart Pricing of Public Goods,” Public Choice, 11,
17–33.
D, P., P. J. H,  E. M (1979): “The Implementation ofSocial Choice Rules: Some General Results on Incentive Compatibility,”
Review of Economic Studies, 46, 185–216.
D, J.-A.  K. E (2003): “Strategy-Proof Allocation of Fixed
Costs,” Review of Economic Design, 8, 185–204.
G, T. (1973): “Incentives in Teams,” Econometrica, 41, 617–631.
J, B.-G. (2004): “Continuous Selections from the Pareto Correspondence
and Non-Manipulability in Exchange Economies,” Journal of Mathematical
Economics, 40, 573–592.
K, B. (2001): “Population-Monotonicity and Separability for Economies
with Single-Dipped Preferences and the Assignments of an Indivisible
Object,” Economic Theory, 17, 675–692.
M, E. (1999): “Nash Equilibrium and Welfare Optimality,” Review of
Economic Studies, 66, 23–38.
M, E. (2001): “House Allocation with Transfers,” Journal of Economic
Theory, 100, 329–355.
——— (2002): “Strategy-Proofness and the Core in House Allocation Problems,” Games and Economic Behavior, 38, 347–361.
P̀, S. (2000a): “Strategyproof Assignment by Hierarchical Exchange,”
Econometrica, 68, 1403–1433.
——— (2000b): “Strategyproof Multiple Assignment Using Quotas,” Review of Economic Design, 5, 91–105.
——— (2001): “Strategyproof and Nonbossy Multiple Assignments,” Journal of Public Economic Theory, 3, 257–271.
——— (2003): “Strategyproof Exchange of Indivisible Goods,” Journal of
Mathematical Economics, 39, 931–959.
S, M. A.  H. S (1981): “Strategy-Proof Allocation Mechanisms at Differentiable Points,” Review of Economic Studies,48, 587–597.
9S, J. (2000a): “Eliciting Preferences to Assign Positions and Compensation,” Games and Economic Behavior, 30, 293–318.
——— (2000b): “Manipulation through Bribes,” Journal of Economic Theory,91, 180–198.
S, S. (1996): “Strategy-Proof and Individually Rational Social Choice
Functions for Public Good Economies,” Economic Theory, 7, 501–512.
——— (2005): “Pairwise Strategy-Proofness and Self-Enforcing Manipulation,” ISER Discussion Papers 629, Osaka University.
S, L. S.  H. S (1974): “On Cores and Indivisibility,” Journal of
Mathematical Economics, 1, 23–37.
S, L.-G. (1999): “Strategy-Proof Allocation of Indivisible Goods,”
Social Choice and Welfare, 16, 557–567.
S, L.-G.  B. L (2002): “Strategy-Proof and Nonbossy
Allocation of Indivisible Goods and Money,” Economic Theory, 20, 483–
502.
T, K. (2001): “Coalition Strategy-Proofness and Monotonicity in
Shapley-Scarf Housing Markets,” Mathematical Social Sciences, 41, 201–
213.
V, W. (1961): “Counterspeculation, Auctions, and Competitive Sealed
Tenders,” Journal of Finance, 16, 8–37.
Z, L. (1991): “Inefficiency of Strategy-Proof Allocation Mechanisms inPure Exchange Economies,” Social Choice and Welfare, 8, 247–254.

10