GCOE Discussion Paper Series
Global COE Program

Human Behavior and Socioeconomic Dynamics
Discussion Paper No.245

Secure Implementation in Queueing Problems

Katsuhiko Nishizaki

February 2012; revised August 2012GCOE Secretariat
Graduate School of Economics

OSAKA UNIVERSITY

1-7 Machikaneyama, Toyonaka, Osaka, 560-0043, Japan

Secure Implementation in Queueing Problems ∗Katsuhiko Nishizaki †August 13, 2012

Abstract
This paper studies secure implementability (Saijo, T., T. Sjöström, and T.Yamato (2007) “Secure Implementation,” Theoretical Economics 2, pp.203-229) in queueing problems. Our main resultshows that the social choice function satisfies strategy-proofness and strong non-bossiness (Saijo,
Sjöström, and Yamato, 2007), both of which are necessary for secure implementation, if and only
if it satisfies constancy on the domains that satisfy weak indifference introduced in this paper. This
result implies that only constant social choice functions are securely implementable on weakly indifferent domains in queueing problems. Weak indifference is weaker than minimal richness (Fujinaka,
Y. and T. Wakayama (2008) “Secure Implementation in Economies with Indivisible Objects andMoney,” Economics Letters 100, pp.91-95). Our main result illustrates that secure implementation
is too difficult in queueing problems since many reasonable domains satisfy weak indifference, forexample, convex domains.
Key words: Secure implementation, Dominant strategy implementation, Nash implementation,
Strategy-proofness, Queueing problems.
JEL classification: C44, C72, D61, D71, D82∗ This paper is based on my M.A. thesis presented to the Graduate School of Economics, Osaka University. I would liketo thank Tatsuyoshi Saijo, Masaki Aoyagi, Yuji Fujinaka, Kazuhiko Hashimoto, Shuhei Morimoto, Shinji Ohseto, Shigehiro
Serizawa, Takuma Wakayama, and seminar participants at the 2008 Japanese Economic Association Spring Meeting, Tohoku
University, for their helpful comments. I am especially grateful to Tatsuyoshi Saijo, Yuji Fujinaka, and Takuma Wakayama for
their valuable advices. I also acknowledge for the Global COE program of Osaka University for the financial supports. The
responsibility for any errors that remain is entirely the author.
† Graduate School of Economics, Osaka University, 1-7, Machikaneyama, Toyonaka, Osaka 560-0043, Japan. E-mail:gge008nk@mail2.econ.osaka-u.ac.jp.

1

Introduction

1.1

BackgroundIn this paper, we consider the following situations: agents have to queue up to enjoy a service which cannot be consumed by more than one agent simultaneously. 1 Examples of such situations are the use oflarge-scaled experimental installations, event sites, and so forth. Organ transplantation is another example. In a queue, each agent has to wait her turn; waiting is a cost for her and such a cost can be described
as a unit waiting cost, that is, the cost of waiting for one agent to finish enjoying a service. 2 Therefore,
the total waiting cost for each agent is calculated as follows: the number of agents preceding her times
her unit waiting cost. In this paper, we assume that monetary transfers among agents are allowed. 3 In
fact, each agent has a linear utility function: her utility level is equal to her monetary transfers minus
her total waiting cost. In such environments, we study the problems of allocating positions in a queue toagents with monetary transfers. These problems are called queueing problems.
In allocating positions in a queue to agents with monetary transfers, we adhere to several criteria.
For example, cost minimization is widely accepted. To achieve cost minimization, we need to knoweach agent’s unit waiting cost which is private information to her. To make each agent reveal this private
information, we construct certain mechanisms. Mechanism design theory, especially implementation
theory, has studied which mechanisms are suitable for resolving such allocation problems. 4
When we consider the structure of mechanisms, manipulability of agents is an important problem:
certain agents might manipulate the outcome of the mechanism in their favor. Such a manipulation might
induce a non-optimal outcome. Strategy-proofness is a standard property for non-manipulability. 5 This
property requires that the truthful revelation is a weakly dominant strategy for each agent in the directrevelation mechanism associated with the social choice function. A social choice function is one thatassociates an allocation with agents’ private information. This function characterizes certain optimal
outcome according to the information. A direct revelation mechanism associated with a social choicefunction is a mechanism in which (i) the set of strategy profiles is equivalent to the domain of the functionand (ii) the game form is equivalent to the function.
Strategy-proofness is a desirable property but has a shortcoming: the strategy-proof mechanism
might have a Nash equilibrium which induces a non-optimal outcome. This problem is solved by secure implementation (Saijo, Sjöström, and Yamato, 2007) which requires that there exists a mechanism
in which (i) each dominant strategy equilibrium induces an optimal allocation and (ii) each Nash equilibrium also induces an optimal allocation, that is, double implementation in dominant strategy equilibria
and Nash equilibria. 6 This concept is considered to be a benchmark for constructing mechanisms which
1 Mitra (2005) and Chun and Heo (2008) consider the situations in which there exist several services.
2 Note that it is implicitly assumed that each agent has a constant unit waiting cost. Moreover, we assume that each agent’s

unit waiting cost might be different from other agents.
3 Note that monetary transfers include not only financial transactions between any two agents but also discriminations of theusage fee.
4 Mechanism design theory consists of implementation theory and realization theory. See Jackson (2001, 2003) and Maskin
and Sjöström (2002) for implementation theory and Hurwicz and Reiter (2006) for realization theory.
5 See Barberà (2010) for the relationship between strategy-proofness and implementation theory.
6 See Mizukami and Wakayama (2007) and Saijo, Sjöström, and Yamato (2007) for dominant strategy implementation and
Maskin (1977), Repullo (1987), and Saijo (1988) for Nash implementation.

1

work well in laboratory experiments. 7 In certain environments, the possibility of secure implementationis studied: voting environments (Saijo, Sjöström, and Yamato, 2007; Berga and Moreno, 2009), public
good economies (Saijo, Sjöström, and Yamato, 2007; Nishizaki, 2011), the problems of providing a divisible and private good with monetary transfers (Saijo, Sjöström, and Yamato, 2007; Kumar, 2009), theproblems of allocating indivisible and private goods with monetary transfers (Fujinaka and Wakayama,2008), Shapley-Scarf housing markets (Fujinaka and Wakayama, 2011), and allotment economies withsingle-peaked preferences (Bochet and Sakai, 2010). 8 These studies illustrate how difficult it is to findsecurely implementable social choice functions with desirable properties.
Queueing problems are special cases of sequencing problems in which certain agents might enjoy
a servicing time which is different from those of other agents. 9 Moreover, sequencing problems are
special cases of quasi-linear environments. In the environments, Groves mechanisms (Groves, 1973) are
well-known for a class of direct revelation mechanisms which satisfy strategy-proofness and decisionefficiency. 10 Decision-efficiency requires that the allocation assigned by the social choice function
maximizes total welfare of the group. It is also well-known that Groves mechanisms are the only directrevelation mechanisms that satisfy strategy-proofness and decision-efficiency on the domains that satisfy
smooth connectedness (Holmström, 1979). 11 Unfortunately, Green and Laffont (1979) show that Groves
mechanisms rarely satisfy budget-balance. 12 Budget-balance requires that the social choice function
assigns an allocation in which there exists no monetary transfer from outside the group or wasted within
the group. 13 Since the combination of decision-efficiency with budget-balance is equivalent to Paretoefficiency in quasi-linear environments, the above results show how difficult it is to construct strategyproof and Pareto-efficient direct revelation mechanisms.
Since queueing problems are special cases of quasi-linear environments, the same results as Holmström (1979) hold in queueing problems. 14 However, there exist strategy-proof and decision-efficientmechanisms which satisfy more desirable properties including budget-balance in queueing problems
than in broader environments. In queueing problems, equally distributed pairwise pivotal rules (Suijs,
7 See Cason, Saijo, Sjöström, and Yamato (2006) for experimental results on secure implementation.
8 See also Saijo, Sjöström, and Yamato (2003) for theoretical results on secure implementation.
9 The constancy of unit waiting costs assumed in queueing problems implies that all agents enjoy the same servicing time.

Scheduling problems are also special cases of sequencing problems. See Mendelson and Whang (1990), Suijs (1996), Mitra(2002), Hain and Mitra (2004), Mishra and Rangarajan (2007), and Chun (2011) for sequencing problems and Moulin (2007,2008) for scheduling problems.
10 The pivotal mechanism (Clarke, 1971) and the second-price auction (Vickrey, 1961) are included in the class. See also
Groves and Loeb (1975) for Groves mechanisms and Tideman and Tullock (1976) and Moulin (1986) for the pivotal mechanism.
11 See also Green and Laffont (1977), Walker (1978), and Suijs (1996) for the uniqueness of Groves mechanisms in term of
domain-richness condition. Moreover, see Hashimoto and Saitoh (2010) for a domain expansion of the pivotal mechanism andSaitoh and Serizawa (2008) and Sakai (2008) for domain expansions of the second-price auction.
12 Similar results are obtained by Groves and Ledyard (1977), Walker (1980), and Hurwicz and Walker (1990) in nonexcludable public good economies, Ohseto (2000) in the problems of allocating an indivisible good, and Schummer (2000)
in the problems of allocating heterogeneous indivisible goods. For domain-richness conditions for the existence of budgetbalanced Groves mechanisms, see Groves and Loeb (1975), Green and Laffont (1979), Laffont and Maskin (1980), Tian
(1996), and Liu and Tian (1999) in non-excludable public good economies and Mitra and Sen (2010) in the problems ofallocating heterogeneous indivisible goods.
13 See Rob (1982) and Mitsui (1983) for the relationship between budget-balance and the number of agents.
14 See also Dolan (1978) for a class of direct revelation mechanisms which satisfy strategy-proofness and decision-efficiency
in queueing problems.

21996), which is a subclass of Groves mechanisms, satisfy budget-balance. 15 Kayı and Ramaekers(2010) show that equally distributed pairwise pivotal rules are the only direct revelation mechanisms thatsatisfy strategy-proofness, decision-efficiency, budget-balance, and equal treatment of equals in queueing problems. 16 Equal treatment of equals requires that any two agents’ utility levels assigned by thesocial choice function should be equal when they have an equal unit waiting cost. Moreover, Hashimotoand Saitoh (2011) show the relationship between decision-efficiency and anonymity which is stronger
than equal treatment of equals in queueing problems. 17 Anonymity requires that any two agents’utility levels assigned by the social choice function should be exchanged when their unit waiting costs
are exchanged. On the other hand, Mitra and Mutuswami (2011) show that the k-pivotal mechanisms(Mitra and Mutuswami, 2011) are the only direct revelation mechanisms that satisfy pairwise strategyproofness, decision-efficiency, equal treatment of equals, and weak linearity in queueing problems. 18
Pairwise strategy-proofness is stronger than strategy-proofness but weaker than weak group strategyproofness. 19 Weak linearity is a linearity property for monetary transfers.

1.2

Motivation

Unfortunately, almost all previous studies show negative results on secure implementation: there rarely
exists a non-trivial securely implementable social choice function. On the basis of these results, investigating which environment has a non-trivial securely implementable social choice function is aninteresting topic. In this paper, we conduct such an investigation into queueing problems.
It is well-known that there rarely exists a social choice function which satisfies strategy-proofness,decision-efficiency, and budget-balance in quasi-linear environments. However, in queueing problems
which are special cases of quasi-linear environments, there exist social choice functions which satisfy theabove properties. 20 This means that strategy-proofness in queueing problems is much weaker than inbroader environments. On the basis of this relationship, we study the possibility of secure implementationin queueing problems since strategy-proofness is necessary for secure implementation.

15 This name is given by Kayı and Ramaekers (2010). See Mitra (2001) for a characterization of a domain-richness condition

for the existence of direct revelation mechanisms that satisfy strategy-proofness, decision-efficiency, and budget-balance inqueueing problems.
16 Kayı and Ramaekers (2010) also study certain properties of social choice correspondences which assign a non-empty setof allocations. See also Maniquet (2003) and Chun (2006a) for studies of social choice correspondences and the Shapley value
in queueing problems. Note that equal treatment of equals can be replaced by symmetry in the result of Kayı and Ramaekers(2010). Symmetry requires that the allocation that is constructed by exchanging the only two consumption bundles for agentswith an identical unit waiting cost in the allocation assigned by the social choice correspondence should be also assigned. By
definition, we know that there exists no social choice function that satisfies symmetry.
17 By the results of Kayı and Ramaekers (2010) and Hashimoto and Saitoh (2011), we have an alternative characterization ofequally distributed pairwise pivotal rules. See Chun (2006b) for the relationship between decision-efficiency and envy-freeness(Foley ,1967) which is stronger than anonymity in queueing problems.
18 The k-pivotal mechanism is equivalent to the pivotal mechanism when k = n, where n is the number of agents.
19 Note that pairwise strategy-proofness is stronger than effective pairwise strategy-proofness (Serizawa, 2006).
20 This fact is due to the linearity of utility functions.

3

1.3

Related LiteratureThis paper is most closely related to the one written by Fujinaka and Wakayama (2008), that studies
the problems of allocating indivisible and private goods with monetary transfers. 21 They show that
only constant social choice functions are securely implementable when the domain satisfies minimalrichness (Fujinaka and Wakayama, 2008). Since queueing problems are special cases of their ones, wehave the same constancy result in queueing problems if the domain satisfies minimal richness by theirresult. However, there exist many reasonable domains that do not satisfy minimal richness in queueing
problems. This implies the possibility of the existence of non-constant securely implementable social
choice functions in queueing problems.

1.4

Our Result

Our main result shows that on many reasonable domains, only constant social choice functions satisfy
strategy-proofness and strong non-bossiness (Saijo, Sjöström, and Yamato, 2007), both of which arenecessary for secure implementation, in queueing problems. In fact, we show a constancy result on
the domains that satisfy weak indifference, a new domain-richness condition introduced in this paper.
Note that weak indifference is weaker than minimal richness which implies a constancy result on secure
implementation in broader environments.
This paper is organized according to the following sections. In Section 2, our model is introduced.
We define properties of social choice functions related to secure implementability in Section 3 anddomain-richness conditions in Section 4. Certain preliminary results on properties of social choice functions are shown in Section 5. In Section 6, we show our main result. Section 7 concludes this paper.
Appendix shows the relationship between weak indifference and certain domain-richness conditions.

2

Model

We study the problems of allocating positions in a queue to agents with monetary transfers. Let I ≡{1, . . . , n} (n ≥ 2) be a set of agents. Let σ ≡ (σi )i∈I ∈ I n be a queue, where, for each i ∈ I, σi is the
position for agent i in the queue σ and for each i, j ∈ I with i 6= j, σi 6= σ j . Note that each position isan indivisible and private good.
Each agent can consume the only one position with a positive or negative amount of money. For eachi ∈ I, let (σi ,ti ) ∈ I × R be a consumption bundle for agent i, where ti is a monetary transfer for agent
i. Let t ≡ (ti )i∈I ∈ Rn be a profile of monetary transfers and (σ ,t ) ∈ I n × Rn be a profile of consumption
bundles, called an allocation. Let()
Z≡(σ ,t ) ∈ I n × Rn σ is a queue and ∑ tk ≤ 0
k∈I

be the set of feasible allocations. 22
21 See Svensson (1983) and Alkan, Demange, and Gale (1991) for the problems of allocating indivisible and private goods

with monetary transfers.
22 In a feasible allocation, the sum of monetary transfers should be non-positive. Our results do not depend on this nonpositivity. This requirement is generically assumed in queueing problems.

4Each agent has a linear utility function. For each i ∈ I, let ci ∈ R++ ≡ {x ∈ R | x > 0} be a unit
waiting cost for agent i and Ci ⊆ R++ be a set of unit waiting costs for agent i. For each i ∈ I, letu : I × R ×Ci → R be the utility function for agent i such that for each (σi ,ti ) ∈ I × R and each ci ∈ Ci ,u(σi ,ti ; ci ) ≡ −(σi − 1)ci + ti .
Let C ≡ ∏i∈I Ci be the domain and c ≡ (ci )i∈I ∈ C be a profile of unit waiting costs. For each i ∈ I, letc−i ≡ (c j ) j6=i ∈ C−i ≡ ∏ j6=i C j be a profile of unit waiting costs for agents other than agent i.
An allocation is assigned by a social choice function for each profile of unit waiting costs. Let
f : C → Z be a social choice function. For each c ∈ C, let (σ (c),t (c)) ∈ Z be the allocation associatedwith the social choice function f at the profile of unit waiting costs c and (σi (c),ti (c)) ∈ I × R be theconsumption bundle for agent i ∈ I in the allocation (σ (c),t (c)).
Remark 1. Our model is a special case of the one presented by Fujinaka and Wakayama (2008). The
difference from their model is the number of each good and the existence of a “null” good. In our model,
the number of each position is equal to one and each agent necessarily consumes a position. On the other
hand, in their model, the number of each object is equal to or more than one and each agent does notnecessarily consume an object. There exists another difference in utility functions. In our model, eachagent’s valuation of a position decreases in the order and the marginal valuation is constant. On the other
hand, in their model, each agent’s valuation of an object is almost unrestrictive. This difference strongly
affects our results.

3

Properties of Social Choice Functions

Saijo, Sjöström, and Yamato (2007) introduce secure implementation which is identical with double
implementation in dominant strategy equilibria and Nash equilibria. 23 They show that the social choicefunction is securely implementable if and only if it satisfies strategy-proofness, strong non-bossiness,and the outcome-rectangular property (Saijo, Sjöström, and Yamato, 2007). 24 In this paper, we study
securely implementable social choice functions in queueing problems. Especially, we focus on social
choice functions which satisfy strategy-proofness and strong non-bossiness.
Strategy-proofness requires that the truthful revelation is a weakly dominant strategy for each agent
in the direct revelation mechanism associated with the social choice function.
Definition 1. The social choice function f satisfies strategy-proofness if and only if for each c, c0 ∈ C
and each i ∈ I,−(σi (ci , c0−i ) − 1)ci + ti (ci , c0−i ) ≥ −(σi (c0i , c0−i ) − 1)ci + ti (c0i , c0−i ).
23 See Saijo, Sjöström, and Yamato (2007) for the definition of secure implementation.
24 Strong non-bossiness is called non-bossiness in their paper. They characterize securely implementable social choice func-

tions by strategy-proofness and the rectangular property (Saijo, Sjöström, and Yamato, 2007) and show that the rectangularproperty is equivalent to strong non-bossiness and the outcome-rectangular property. See Saijo, Sjöström, and Yamato (2007)
for the definitions of the rectangular property and the outcome-rectangular property and Mizukami and Wakayama (2008) for analternative characterization of securely implementable social choice functions in terms of a stronger version of Maskin monotonicity (Maskin, 1977). See also Berga and Moreno (2009) for an alternative characterization of minmax rules in single-peaked
voting environments in terms of strong non-bossiness.

5Strong non-bossiness requires that each agent cannot change the outcome by her deviation while
maintaining her utility level in the direct revelation mechanism associated with the social choice function.
Definition 2 (Saijo, Sjöström, and Yamato, 2007). The social choice function f satisfies strong nonbossiness if and only if for each c, c0 ∈ C and each i ∈ I, if−(σi (ci , c−i ) − 1)ci + ti (ci , c−i ) = −(σi (c0i , c−i ) − 1)ci + ti (c0i , c−i ),then(σ (ci , c−i ),t (ci , c−i )) = (σ (c0i , c−i ),t (c0i , c−i )).
By definition, strong non-bossiness is stronger than non-bossiness (Satterthwaite and Sonnenschein,
1981). 25 This property is also stronger than quasi-strong non-bossiness (Mizukami and Wakayama,
2007; Saijo, Sjöström, and Yamato, 2007) which is necessary for dominant strategy implementation. 26
Constancy requires that any revelations are not reflected on the outcome in the direct revelation
mechanism associated with the social choice function.
Definition 3. The social choice function f satisfies constancy if and only if for each c, c0 ∈ C,

(σ (c),t (c)) = (σ (c0 ),t (c0 )).

4 Domain-Richness
In the problems of allocating indivisible and private goods with monetary transfers, where each agent has
a quasi-linear utility function, Fujinaka and Wakayama (2008) show that if the domain satisfies minimalrichness, then only constant social choice functions are securely implementable.
Definition 4 (Fujinaka and Wakayama, 2008). The domain C satisfies minimal richness if and only if
for each i ∈ I, each c0i , c00i ∈ Ci , each σi0 , σi00 ∈ I, and each T ∈ R, if(σi00 − σi0 )c00i < T < (σi00 − σi0 )c0i ,then there exists ci ∈ Ci such that(i) (σi00 − σi0 )ci = T ,(ii) (σi00 − σi )ci ≤ (σi00 − σi )c0i for each σi ∈ I \ {σi0 , σi00 }.
Since our model is a special case of the one presented by Fujinaka and Wakayama (2008), only
constant social choice functions are securely implementable in our model if the domain satisfies minimalrichness by their result. However, Example 1 shows that many reasonable domains do not satisfy minimalrichness in our model.
social choice function f satisfies non-bossiness if and only if for each c, c0 ∈ C and each i ∈ I, if(σi (ci , c−i ),ti (ci , c−i )) = (σi (c0i , c−i ),ti (c0i , c−i )), then (σ (ci , c−i ),t (ci , c−i )) = (σ (c0i , c−i ),t (c0i , c−i )).
26 The social choice function f satisfies quasi-strong non-bossiness if and only if for each c, c0 ∈ C and each i ∈ I,
if −(σi (ci , c00−i ) − 1)ci + ti (ci , c00−i ) = −(σi (c0i , c00−i ) − 1)ci + ti (c0i , c00−i ) for each c00−i ∈ C−i , then (σ (ci , c−i ),t (ci , c−i )) =(σ (c0i , c−i ),t (c0i , c−i )). Saijo, Sjöström, and Yamato (2007) call this property weak non-bossiness. Mizukami and Wakayama(2007) and Saijo, Sjöström, and Yamato (2007) independently show that the social choice function is dominant strategy implementable if and only if it satisfies strategy-proofness and quasi-strong non-bossiness.
25 The6

Example 1. Let i ∈ I and Ci = R++ . Moreover, let c0i = 3, c00i = 1, σi0 = 1, σi00 = 2, and T = 2. In thiscase, we have
(σi00 − σi0 )c00i = 1 < T < 3 = (σi00 − σi0 )c0i .
Let ci ∈ Ci be such that (σi00 − σi0 )ci = T , that is, ci = 2. This implies that condition (i) in Definition 4
holds. On the other hand, if ci = 2, then(σi00 − σi )ci = −2 > −3 = (σi00 − σi )c0i
for σi = 3. This implies that condition (ii) in Definition 4 does not hold.
Example 1 implies that there exist the other quasi-linear environments that Fujinaka and Wakayama(2008) do not study, that is, we have the possibility of the existence of non-constant securely implementable social choice functions in certain quasi-linear environments. However, our main result implies
that on many reasonable domains, only constant social choice functions are securely implementable inqueueing problems. In fact, we show that if the domain satisfies the following condition, called weak
indifference, then any social choice function satisfying strategy-proofness and strong non-bossiness alsosatisfies constancy.
Definition 5. The domain C satisfies weak indifference if and only if for each i ∈ I, each c0i , c00i ∈ Ci ,each σi0 , σi00 ∈ I, and each T ∈ R, if(σi00 − σi0 )c00i < T < (σi00 − σi0 )c0i ,then there exists ci ∈ Ci such that

(σi00 − σi0 )ci = T .
By definition, weak indifference is weaker than minimal richness. In our model, weak indifferenceis equivalent to convexity. 27 By bringing this relationship together with the result of Holmström (1979),
we know that weak indifference is stronger than smooth connectedness in our model. Moreover, weknow that smooth connectedness is stronger than convexity, that is, smooth connectedness is equivalent
to convexity in our model. 28 This implies that in our model, weak indifference is also equivalent tosmooth connectedness.
Remark 2. Fujinaka and Wakayama (2008) show the possibility of the existence of non-constant securely implementable social choice functions on the domains that satisfy monotonic closedness (Schummer, 2000). 29 In our model, there exists no monotonically closed domain except for the case of n = 2
due to the linearity of utility functions. 30

27 See Appendix for the relationship between weak indifference and convexity.
28 See Appendix for the relationship between smooth connectedness and convexity.
29 In quasi-linear environments, Schummer (2000) shows a constancy result on bribe-proofness (Schummer, 2000) on mono-

tonically closed domains. Bribe-proofness is stronger than strategy-proofness. He also shows that only all-dictatorial (Schummer, 2000) social choice functions satisfy bribe-proofness on smoothly connected domains. All-dictatorship requires that eachagent is actually a dictator on the range of the social choice function.
30 See Appendix for the existence of monotonically closed domains and the relationship between weak indifference andmonotonic closedness in the case of n = 2.

75Preliminary Results

In what follows, we show certain preliminary results on strategy-proofness in our model. Note thatall preliminary results are irrespective of domain-richness conditions. For simplicity of notation, let
σi ≡ σi (ci , c−i ), σi0 ≡ σi (c0i , c−i ), σi00 ≡ σi (c00i , c−i ) and ti ≡ ti (ci , c−i ), ti0 ≡ ti (c0i , c−i ), ti00 ≡ ti (c00i , c−i ) for
each c, c0 ∈ C and each i ∈ I.
Lemma 1 shows that each agent’s monetary transfer depends on her position in the queue if the social
choice function satisfies strategy-proofness.
Lemma 1. Suppose that the social choice function f satisfies strategy-proofness. For each c, c0 ∈ C andeach i ∈ I, if σi = σi0 , then ti = ti0 .
Proof. Suppose, by contradiction, that there exist c, c0 ∈ C and i ∈ I such that σi = σi0 and ti 6= ti0 . If ti < ti0 ,then we have −(σi − 1)ci + ti < −(σi0 − 1)ci + ti0 . This is a contradiction to strategy-proofness. If ti > ti0 ,then we have −(σi − 1)c0i + ti > −(σi0 − 1)c0i + ti0 . This is also a contradiction to strategy-proofness.
Remark 3. Lemma 1 corresponds to Claim 1 in Proposition 1 of Fujinaka and Wakayama (2008).
By Lemma 1, we know that for each c, c0 ∈ C and each i ∈ I, if −(σi − 1)ci + ti 6= −(σi0 − 1)ci + ti0 ,then σi 6= σi0 when the social choice function f satisfies strategy-proofness.
Lemma 2 shows that if there exists a unit waiting cost such that some two different consumption
bundles are indifferent in terms of utility level, then the position associated with the unit waiting cost isin between the two positions if the social choice function satisfies strategy-proofness. In Lemma 2, we
use the following notation: for each i ∈ I, each ci ∈ Ci , each (σi ,ti ) ∈ I × R, and each σi0 ∈ I, letti (σi0 ; (σi ,ti ), ci ) ≡ (σi0 − σi )ci + ti .
This implies −(σi − 1)ci + ti = −(σi0 − 1)ci + ti (σi0 ; (σi ,ti ), ci ), that is, (σi0 , ti (σi0 ; (σi ,ti ), ci )) is indifferent to (σi ,ti ) for agent i with ci .
Lemma 2. Suppose that the social choice function f satisfies strategy-proofness. For each c, c0 ∈ C
and each i ∈ I, if σi < σi0 and there exists c00i ∈ Ci such that −(σi − 1)c00i + ti = −(σi0 − 1)c00i + ti0 , thenσi ≤ σi00 ≤ σi0 .
Proof. Suppose, by contradiction, that there exist c, c0 ∈ C and i ∈ I such that σi < σi0 , −(σi − 1)c00i + ti =−(σi0 − 1)c00i + ti0 for some c00i ∈ Ci , and σi00 < σi or σi0 < σi00 .
We consider the case of σi00 < σi . By the hypothesis, we haveti0 − ti.
σi0 − σi(1)ti (σi0 ; (σi ,ti ), ci ) − ti.
σi0 − σi

(2)c00i =
By the definition of ti , we haveci =By the definition of ti and strategy-proofness, we have −(σi0 −1)ci + ti0 < −(σi0 −1)ci + ti (σi0 ; (σi ,ti ), ci ),that is,ti0 < ti (σi0 ; (σi ,ti ), ci ).31
(3)
If it holds, then we have ci = c00i by (1) and (2). This implies that f should be acorrespondence since we consider the case of σi00 < σi .
31 Note that the equality does not hold.

8

c"i
ci

s 'i

si
s "i
0

ti

t'i

ti (s 'i ; (s i , ti ), ci )ti (s "i ; (s i , ti ), ci ) < ti (s "i ; (s i , ti ), c"i )Figure 1: Proof of Lemma 2

By (1), (2), (3), and σi < σi0 , we have c00i < ci . Since we consider the case of σi00 < σi , this implies(σi00 − σi )c00i + ti > (σi00 − σi )ci + ti , that is,ti (σi00 ; (σi ,ti ), ci ) < ti (σi00 ; (σi ,ti ), c00i ).

(4)

By the definition of ti and strategy-proofness, we have −(σi00 −1)ci + ti00 ≤ −(σi00 −1)ci + ti (σi00 ; (σi ,ti ), ci ),that is,ti00 ≤ ti (σi00 ; (σi ,ti ), ci ).
(5)Moreover, by the definition of ti and strategy-proofness, we have −(σi00 − 1)c00i + ti00 ≥ −(σi00 − 1)c00i +ti (σi00 ; (σi ,ti ), c00i ), that is,(6)
ti (σi00 ; (σi ,ti ), c00i ) ≤ ti00 .
By (5) and (6), we have ti (σi00 ; (σi ,ti ), c00i ) ≤ ti (σi00 ; (σi ,ti ), ci ). This is a contradiction to (4) (see Figure
1).
Similarly, we have a contradiction to strategy-proofness in the case of σi0 < σi00 .
Remark 4. There exists no result of Fujinaka and Wakayama (2008) corresponding to Lemma 2. Lemma
2 strongly depends on the decreasingness of utility functions in positions, which is not assumed in theirmodel.

6

Main Result

By bringing preliminary results on strategy-proofness together with strong non-bossiness and weak indifference, we show our main result. In line with the previous section, for simplicity of notation, let
σi ≡ σi (ci , c−i ), σi0 ≡ σi (c0i , c−i ), σi00 ≡ σi (c00i , c−i ), σi∗ ≡ σi (c∗i , c−i ), σi∗∗ ≡ σi (c∗∗i , c−i ) and ti ≡ ti (ci , c−i ),
0
0
00
00
∗
∗
∗∗
∗∗
0
ti ≡ ti (ci , c−i ), ti ≡ ti (ci , c−i ), ti ≡ ti (ci , c−i ), ti ≡ ti (ci , c−i ) for each c, c ∈ C and each i ∈ I.
Theorem. Suppose that the domain C satisfies weak indifference. The social choice function f satisfies
strategy-proofness and strong non-bossiness if and only if it satisfies constancy.

9

ci

c"i

'i
"i
!
i

i

ti ti!

0

t"i

t'i

Figure 2: Proof of Theorem

Proof. Since the “if” part is obvious, we only prove the “only if” part.
Let c, c0 ∈ C. To prove (σ (c),t (c)) = (σ (c0 ),t (c0 )), we firstly show(σ (ci , c−i ),t (ci , c−i )) = (σ (c0i , c−i ),t (c0i , c−i ))for each i ∈ I. Suppose, by contradiction, that there exists j ∈ I such that (σ (c j , c− j ),t (c j , c− j )) 6=(σ (c0j , c− j ),t (c0j , c− j )). By strong non-bossiness, this implies −(σ j − 1)c j + t j 6= −(σ 0j − 1)c j + t 0j . By
strategy-proofness, this implies−(σ j − 1)c j + t j > −(σ 0j − 1)c j + t 0j .

(7)

By Lemma 1, this implies σ j 6= σ 0j , that is, σ j < σ 0j or σ j > σ 0j . We consider the case of σ j < σ 0j .
Since (σ (c j , c− j ),t (c j , c− j )) 6= (σ (c0j , c− j ),t (c0j , c− j )), by strong non-bossiness, it also implies −(σ j −1)c0j + t j 6= −(σ 0j − 1)c0j + t 0j . By strategy-proofness, this implies−(σ j − 1)c0j + t j < −(σ 0j − 1)c0j + t 0j .

(8)

By (7) and (8), we have (σ 0j − σ j )c0j < t 0j − t j < (σ 0j − σ j )c j . Since C satisfies weak indifference, this
implies that there exists c00j ∈ C j such that (σ 0j − σ j )c00j = t 0j − t j , that is,−(σ j − 1)c00j + t j = −(σ 0j − 1)c00j + t 0j .

(9)Since we consider the case of σ j < σ 0j , by Lemma 2, this implies σ j ≤ σ 00j ≤ σ 0j . If σ 00j = σ j , then, by (9)and strong non-bossiness, we have σ j = σ 0j . This is a contradiction. Similarly, we have a contradiction
if σ 00j = σ 0j . Therefore, we know
σ j < σ 00j < σ 0j .
By applying the above argument to the left inequality repeatedly, we can find c∗j , c∗∗j ∈ C j such that
∗
∗∗
∗
∗∗
∗
σ j < σ j and −(σ j − 1)c j + t j = −(σ j − 1)c j + t j , where there exists no position between σ j and σ ∗jinduced by a unit waiting cost for agent i given c− j since each position is indivisible (see Figure 2). In∗∗∗∗
this case, we have σ ∗∗j = σ j or σ j = σ j . By strong non-bossiness, these imply σ j = σ j . This is acontradiction. Similarly, we have a contradiction in the case of σ j > σ 0j .
Without loss of generality, let i = 1. Therefore, we have(σ (c1 , c−1 ),t (c1 , c−1 )) = (σ (c01 , c−1 ),t (c01 , c−1 )).
10

(10)

By the same argument stated above, we also have(σ (c01 , c2 , c−1,2 ),t (c01 , c2 , c−1,2 )) = (σ (c01 , c02 , c−1,2 ),t (c01 , c02 , c−1,2 )),(11)

where c−1,2 is a profile of unit waiting costs for agents other than agents 1 and 2. By (10) and (11),
we have (σ (c1 , c2 , c−1,2 ),t (c1 , c2 , c−1,2 )) = (σ (c01 , c02 , c−1,2 ),t (c01 , c02 , c−1,2 )). By sequentially replacingc j by c0j for each j 6= 1, 2 in this manner, we finally prove (σ (c),t (c)) = (σ (c0 ),t (c0 )).
Remark 5. Theorem does not depend on the finiteness of the number of positions, which is used toprove Claim 3 in Proposition 1 of Fujinaka and Wakayama (2008). This difference arises from whether
Lemma 2 holds.
The above theorem is tight. Example 2 shows that if the domain does not satisfy weak indifference,then there exist non-constant securely implementable social choice functions. Example 3 shows thatstrategy-proofness is necessary for Theorem and Example 4 shows that strong non-bossiness is necessary
for Theorem.
Example 2. Suppose that I = {1, 2} and Ci = R++ \ {2} for each i ∈ I. In this case, the domain C does
not satisfy weak indifference: if there exist i ∈ I such that c0i = 3, c00i = 1, σi0 = 1, and σi00 = 2 and T = 2,
then we have (σi00 − σi0 )c00i = 1 < T < 3 = (σi00 − σi0 )c0i and (σi00 − σi0 )ci = ci 6= 2 = T for each ci ∈ Ci .
Let f be the social choice function such that for each c ∈ C,((1, −1), (2, 1)) if c > 2,
1((σ1 (c),t1 (c)), (σ2 (c),t2 (c))) =((2, 1), (1, −1)) if c < 2.
1

We consider strategy-proofness. Let c, c0 ∈ C. If c1 > 2, then we have −(σ1 (c1 , c2 ) − 1)c1 +
t1 (c1 , c2 ) = −1 ≥ −(σ1 (c01 , c2 ) − 1)c1 + t1 (c01 , c2 ). If c1 < 2, then we have −(σ1 (c1 , c2 ) − 1)c1 +
t1 (c1 , c2 ) = −c1 + 1 ≥ −(σ1 (c01 , c2 ) − 1)c1 + t1 (c01 , c2 ). Since any allocation associated with f depends
only on agent 1’s unit waiting cost, these imply that f satisfies strategy-proofness (see Figure 3).
We consider strong non-bossiness. By the argument about strategy-proofness, we know that any
allocation associated with f depends only on agent 1’s unit waiting cost and the hypothesis of strong
non-bossiness is realized only when agent 1’s consumption bundle does not change. These imply that fsatisfies strong non-bossiness.
Example 3. Suppose that I = {1, 2} and Ci = R++ for each i ∈ I. In this case, the domain C satisfies
weak indifference since C satisfies convexity which is stronger than weak indifference.
Let f be the social choice function such that for each c ∈ C,((1, 1), (2, −1)) if c ≥ 2,
1((σ1 (c),t1 (c)), (σ2 (c),t2 (c))) =((2, −1), (1, 1)) if c < 2.
1

By the same argument as Example 2, we know that f satisfies strong non-bossiness. We consider
strategy-proofness. Let c, c0 ∈ C be such that c1 < 2 and c01 ≥ 2. In this case, we have −(σ1 (c1 , c02 ) −1)c1 + t1 (c1 , c02 ) = −c1 − 1 < 1 − (σ1 (c01 , c02 ) − 1)c1 + t1 (c01 , c02 ). This implies that f does not satisfy
strategy-proofness (see Figure 3).

11

ci

i

2

ci

2

ci

2

2

1

-1

0

1

ti

Figure 3: Examples 2, 3, and 4

Example 4. Suppose that I = {1, 2} and Ci = R++ for each i ∈ I. By the same argument as Example 3,
we know that the domain C satisfies weak indifference.
Let f be the social choice function such that for each c ∈ C,((1, −1), (2, 1)) if c ≥ 2,
1((σ1 (c),t1 (c)), (σ2 (c),t2 (c))) =((2, 1), (1, −1)) if c < 2.
1

By the same argument as Example 2, we know that f satisfies strategy-proofness. We consider strong
non-bossiness. Let c, c0 ∈ C be such that c1 = 2 and c01 < 2. In this case, we have −(σ1 (c1 , c2 ) − 1)c1 +
t1 (c1 , c2 ) = −1 = −(σ1 (c01 , c2 ) − 1)c1 + t1 (c01 , c2 ) and((σ1 (c1 , c2 ),t1 (c1 , c2 )), (σ2 (c1 , c2 ),t2 (c1 , c2 ))) = ((1, −1), (1, 1))
6= ((2, 1), (1, −1))

= ((σ1 (c01 , c2 ),t1 (c01 , c2 )), (σ2 (c01 , c2 ),t2 (c01 , c2 ))).
This implies that f does not satisfy strong non-bossiness (see Figure 3).
Obviously, constant social choice functions are securely implementable. Therefore, by bringing
Theorem together with a characterization of securely implementable social choice functions by Saijo,
Sjöström, and Yamato (2007), we have the following constancy result on secure implementation.
Corollary 1. Suppose that the domain satisfies weak indifference. The social choice function is securely
implementable if and only if it satisfies constancy.
Remark 6. Example 3 also shows the relationship between strategy-proofness and Maskin monotonicity on weakly indifferent domains: the social choice function defined in Example 3 does not satisfy
strategy-proofness but does satisfy Maskin monotonicity, that is, Maskin monotonicity is not stronger
than strategy-proofness. For each i ∈ I, each ci ∈ Ci , and each (σi ,ti ) ∈ I × R, let L((σi ,ti ), ci ) ≡{(σi0 ,ti0 ) ∈ I × R | − (σi − 1)ci + ti ≥ −(σi0 − 1)ci + ti0 }. The social choice function f satisfies Maskin
monotonicity if and only if for each c, c0 ∈ C, if, for each i ∈ I, L((σi (c),ti (c)), ci ) ⊆ L((σi (c),ti (c)), c0i ),then (σ (c),t (c)) = (σ (c0 ),t (c0 )).
We show that the social choice function f defined in Example 3 satisfies Maskin monotonicity. Let
0c, c ∈ C be such that for each i ∈ I, L((σi (c),ti (c)), ci ) ⊆ L((σi (c),ti (c)), c0i ). Note that in our model,12L((σi ,ti ), ci ) ⊆ L((σi ,ti ), c0i ) implies (i) ci ≤ c0i if σi = 1, (ii) ci = c0i if σi ∈ I \ {1, n}, and (iii) ci ≥ c0i if
σi = n. If c1 ≥ 2, then we have ((σ1 (c),t1 (c)), (σ2 (c),t2 (c))) = ((1, 1), (2, −1)). Since L((1, 1), c1 ) ⊆L((1, 1), c01 ) implies c1 ≤ c01 , we also have ((σ1 (c0 ),t1 (c0 )), (σ2 (c0 ),t2 (c0 ))) = ((1, 1), (2, −1)), that is,(σ (c),t (c)) = (σ (c0 ),t (c0 )). If c1 < 2, then we have ((σ1 (c),t1 (c)), (σ2 (c),t2 (c))) = ((2, −1), (1, 1)).
Since L((2, −1), c1 ) ⊆ L((2, −1), c01 ) implies c1 ≥ c01 , we also have ((σ1 (c0 ),t1 (c0 )), (σ2 (c0 ),t2 (c0 ))) =((2, −1), (1, 1)), that is, (σ (c),t (c)) = (σ (c0 ),t (c0 )). These imply that f satisfies Maskin monotonicity.
By Example 3, we know that Maskin monotonicity is not stronger than strategy-proofness if n = 2.
This relationship holds even if n ≥ 3, that is, our main result is established by secure implementability
but not by Nash implementability.
Remark 7. Saijo (1987) shows the following constancy result on “Nash” implementation: the social
choice function satisfies Maskin monotonicity and dual dominance (Saijo, 1987) if and only if it satisfies
constancy. 32 Obviously, the securely implementable social choice function satisfies dual dominance if
and only if it satisfies constancy. In line with such domination, Fujinaka and Wakayama (2008) show
the following constancy result on “secure” implementation: the securely implementable social choicefunction satisfies non-dominance (Fujinaka and Wakayama, 2008) if and only if it satisfies constancy. 33
Note that non-dominance is weaker than dual dominance. 34 In our model, similar to the relationshipbetween minimal richness and weak indifference, we have a constancy result on secure implementation
by a weaker condition than non-dominance as follows: for each (σ 0 ,t 0 ), (σ 00 ,t 00 ) ∈ f (C ), each c0 , c00 ∈ Csuch that (σ (c0 ),t (c0 )) = (σ 0 ,t 0 ) and (σ (c00 ),t (c00 )) = (σ 00 ,t 00 ), and each i ∈ I, if there exists no c000 ∈ C
00 00
00
00 00
000
such that L((σi0 ,ti0 ), c0i ) ⊆ L((σi0 ,ti0 ), c000i ) and L((σi ,ti ), ci ) ⊆ L((σi ,ti ), ci ), then there exists ci ∈ Ci
such that (σi00 − σi0 )ci = ti00 − ti0 .

7 Conclusion
This paper studies secure implementability in queueing problems. In the problems of allocating indivisible and private goods with monetary transfers, where each agent has a quasi-linear utility function,
Fujinaka and Wakayama (2008) show that if the domain satisfies minimal richness, then only constantsocial choice functions are securely implementable. Since our model is a special case of their one, weknow that only constant social choice functions are securely implementable if the domain satisfies minimal richness by their results. However, many reasonable domains do not satisfy minimal richness in
our model. In this paper, we show that only constant social choice functions satisfy strategy-proofness
and strong non-bossiness, both of which are necessary for secure implementation, on weakly indifferent
domains which are less restrictive than minimally rich domains. Our main result implies that secure im32 The social choice function f satisfies dual dominance if and only if for each (σ 0 ,t 0 ), (σ 00 ,t 00 ) ∈ f (C ), there exist c0 , c00 , c000 ∈C such that (i) (σ (c0 ),t (c0 )) = (σ 0 ,t 0 ) and (σ (c00 ),t (c00 )) = (σ 00 ,t 00 ) and (ii) for each i ∈ I, L((σi0 ,ti0 ), c0i ) ⊆ L((σi0 ,ti0 ), c000i ) andL((σi00 ,ti00 ), c00i ) ⊆ L((σi00 ,ti00 ), c000i ).
33 The social choice function f satisfies non-dominance if and only if for each (σ 0 ,t 0 ), (σ 00 ,t 00 ) ∈ f (C ), each c0 , c00 ∈ C suchthat (σ (c0 ),t (c0 )) = (σ 0 ,t 0 ) and (σ (c00 ),t (c00 )) = (σ 00 ,t 00 ), and each i ∈ I, if there exists no c000 ∈ C such that L((σi0 ,ti0 ), c0i ) ⊆
00 00
00
00 00
000
00
0
00
0
00
L((σi0 ,ti0 ), c000i ) and L((σi ,ti ), ci ) ⊆ L((σi ,ti ), ci ), then there exists ci ∈ Ci such that (i) (σi − σi )ci = ti − ti and (ii) (σi −
0
00
0
00
σi )ci ≤ (σi − σi )ci for each σi ∈ I \ {σi , σi }.
34 See the supplementary note provided by Fujinaka and Wakayama (2008) for the relationship among dual dominance, nondominance, and secure implementability in the problems of allocating indivisible and private goods with monetary transfers.
This note is available online at: http://www.iser.osaka-u.ac.jp/library/dp/2007/DP0699N.pdf.

13

plementation is too difficult in queueing problems since many reasonable domains satisfy weak indifference, for example, convex domains. Moreover, by applying the observations of Cason, Saijo, Sjöström,
and Yamato (2006), our main result suggests that almost all strategy-proof direct revelation mechanisms
do not work well in queueing problems.
Our main result shows certain domain-richness conditions for the constancy of securely implementable social choice functions. On the other hand, it remains to show domain-richness conditions
for the existence of non-constant securely implementable social choice functions. However, our main
result implies that it is difficult to find such conditions that are reasonable in the economic sense.

Appendix: Relationship between Weak Indifference and Certain DomainRichness Conditions
In this paper, we introduce a new domain-richness condition, called weak indifference. By definition,
this condition is weaker than minimal richness. In what follows, we show a relationship among weak
indifference and certain domain-richness conditions other than minimal richness: convexity, smoothconnectedness, and monotonic closedness.
First, we consider the relationship between weak indifference and convexity.
Definition 6. The domain C satisfies convexity if and only if for each i ∈ I, each c0i , c00i ∈ Ci , and eachλ ∈ [0, 1], there exists ci ∈ Ci such thatci = λ c0i + (1 − λ )c00i .
Fact 1 shows that convexity is stronger than weak indifference in our model. Since this fact isobvious, the proof is omitted.
Fact 1. If the domain C satisfies convexity, then it satisfies weak indifference.
Fact 2 shows that weak indifference is stronger than convexity in our model.
Fact 2. If the domain C satisfies weak indifference, then it satisfies convexity.
Proof. Let i ∈ I, c0i , c00i ∈ Ci , and λ ∈ [0, 1]. We consider the following two cases: λ = 0 or 1 and λ ∈(0, 1). If λ = 0 or 1, then we have λ c0i + (1 − λ )c00i ∈ Ci since c0i , c00i ∈ Ci . If λ ∈ (0, 1), then we consider
the following three subcases: c0i = c00i , c0i < c00i , and c0i > c00i . If c0i = c00i , then we also have λ c0i + (1− λ )c00i ∈Ci since c0i , c00i ∈ Ci . In what follows, we consider the subcases of c0i < c00i and c0i > c00i when λ ∈ (0, 1).
Let σi0 , σi00 ∈ I and T ∈ R be such that σi0 < σi00 and (σi00 − σi0 ){λ c0i + (1− λ )c00i } = T . Since λ ∈ (0, 1),
if c0i < c00i , then we have

(σi00 − σi0 )c0i = T

c00i
c0i
<T <T 0= (σi00 − σi0 )c00i .
000
λ ci + (1 − λ )ci
λ ci + (1 − λ )c00i

Since C satisfies weak indifference, there exists ci ∈ Ci such that (σi00 − σi0 )ci = T and ci = λ c0i + (1 −λ )c00i . Similarly, we can show that there exists ci ∈ Ci such that ci = λ c0i + (1 − λ )c00i if c0i > c00i .
By Facts 1 and 2, we know that weak indifference is equivalent to convexity in our model. Next, weconsider the relationship between smooth connectedness and convexity.
14

Definition 7. The domain C satisfies smooth connectedness if and only if for each i ∈ I and eachc0i , c00i ∈ Ci , there exists v : I × [0, 1] → R such that for each σi ∈ I,(i) there exists cθi ∈ Ci such that v(σi ; θ ) = −(σi − 1)cθi for each θ ∈ [0, 1],(ii) v(σi ; 0) = −(σi − 1)c0i and v(σi ; 1) = −(σi − 1)c00i ,(iii) v(σi ; ·) is differentiable on [0, 1], 35(iv) there exists K ∈ R++ such that |∂ v(σi ; θ )/∂ θ | ≤ K for each θ ∈ [0, 1].
Holmström (1979) shows that convexity is stronger than smooth connectedness in quasi-linear environments. Since our model is one of quasi-linear environments, this relationship also holds in our model.
Moreover, Fact 3 shows that smooth connectedness is stronger than convexity in our model.
Fact 3. If the domain C satisfies smooth connectedness, then it satisfies convexity.
Proof. Let i ∈ I, c0i , c00i ∈ Ci , and λ ∈ [0, 1]. Since C satisfies smooth connectedness, there exists v : I ×[0, 1] → R such that for each σi ∈ I, (i) there exists cθi ∈ Ci such that v(σi ; θ ) = −(σi − 1)cθi for eachθ ∈ [0, 1], (ii) v(σi ; 0) = −(σi − 1)c0i and v(σi ; 1) = −(σi − 1)c00i , and (iii) v(σi ; ·) is differentiable on[0, 1]. Without loss of generality, we assume v(σi ; 0) ≤ v(σi ; 1). Let σi ∈ I. By (ii), we have

λ v(σi ; 0) + (1 − λ )v(σi ; 1) = −(σi − 1){λ c0i + (1 − λ )c00i }.

(12)

By (iii), we know that v(σi ; ·) is continuous on [0, 1]. This implies that[v(σi ; 0), v(σi ; 1)] ⊆ v(σi ; [0, 1]).

(13)

By (12) and (13), there exists θ ∈ [0, 1] such thatv(σi ; θ ) = −(σi − 1){λ c0i + (1 − λ )c00i }.

(14)

By (i), there exists cθi ∈ Ci such thatv(σi ; θ ) = −(σi − 1)cθi .

(15)

By (14) and (15), we have cθi = λ c0i + (1 − λ )c00i .
By Fact 3 and the result of Holmström (1979), we know that smooth connectedness is equivalent toconvexity in our model. According to the relationships stated above, we have the following corollary in
our model.
Corollary 2. The following statements are equivalent: (i) the domain satisfies weak indifference, (ii)the domain satisfies smooth connectedness, and (iii) the domain satisfies convexity.
Finally, we consider the relationship between weak indifference and monotonic closedness.
Definition 8. The domain C satisfies monotonic closedness if and only if for each i ∈ I, each c0i ∈ Ci ,and each σi0 ∈ I, there exists ci ∈ Ci such that

(σi0 − σi )ci < (σi0 − σi )c0i for each σi ∈ I \ {σi0 }.
35 The existence of one-sided derivatives is assumed only at the endpoints.

15

If n ≥ 3, then many reasonable domains do not satisfy monotonic closedness in our model. Let i ∈ I
and Ci = R++ . Moreover, let c0i ∈ Ci and σi0 = 2. In this case, for each ci ∈ Ci with ci ≥ c0i , there exists
σi ∈ I \ {2} such that (2 − σi )ci ≥ (2 − σi )c0i , that is, σi = 1. On the other hand, for each ci ∈ Ci withci < c0i , there exists σi ∈ I \ {2} such that (2 − σi )ci ≥ (2 − σi )c0i , for example, σi = 3. In fact, Fact 4
shows that there exists no domain that satisfies monotonic closedness in our model when n ≥ 3. 36 Since
the proof of this fact is similar to the above argument, it is omitted.
Fact 4. Suppose n ≥ 3. There exists no domain that satisfies monotonic closedness.
Fact 4 implies that monotonic closedness is stronger than weak indifference in our model when n ≥ 3.
Moreover, this fact implies that weak indifference is not stronger than monotonic closedness in our model
when n ≥ 3. If n = 2, then many reasonable domains satisfy monotonic closedness in our model, forexample, C = R2++ . However, since such convex domains also satisfy weak indifference, only constantsocial choice functions are securely implementable on the domains by Corollary 1.

References
Alkan, A., G. Demange, and D. Gale (1991) “Fair Allocation of Indivisible Goods and Criteria of Justice,” Econometrica 59, pp.1023-1039.
Barberà, S. (2010) “Strategy-Proof Social Choice,” Barcelona Economics Working Paper Series 420,
Universitat Autònoma de Barcelona.
Berga, D. and B. Moreno (2009) “Strategic Requirements with Indifference: Single-Peaked versus
Single-Plateaued Preferences,” Social Choice and Welfare 32, pp.275-298.
Bochet, O. and T. Sakai (2010) “Secure Implementation in Allotment Economies,” Games and Economic
Behavior 68, pp.35-49.
Cason, T., T. Saijo, T. Sjöström, and T.Yamato (2006) “Secure Implementation Experiments: Do
Strategy-Proof Mechanisms Really Work?” Games and Economic Behavior 57, pp.206-235.
Chun, Y. (2006a) “A Pessimistic Approach to the Queueing Problem,” Mathematical Social Sciences 51,
pp.171-181.
Chun, Y. (2006b) “No-Envy in Queueing Problems,” Economic Theory 29, pp.151-162.
Chun, Y. (2011) “Consistency and Monotonicity in Sequencing Problems,” International Journal ofGame Theory 40, pp.29-41.
Chun, Y. and E. J. Heo (2008) “Queueing Problems with Two Parallel Servers,” International Journal of
Economic Theory 4, pp.299-315.
Clarke, E. H. (1971) “Multipart Pricing of Public Goods,” Public Choice 11, pp.17-33.
Dolan, R. J. (1978) “Incentive Mechanisms for Priority Queuing Problems,” Bell Journal of Economics
9, pp.421-436.
36 Fact 4 depends on the linearity of utility functions strongly.

16

Foley, D. (1967) “Resource Allocation and the Public Sector,” Yale Economic Essays 7, pp.45-98.
Fujinaka, Y. and T. Wakayama (2008) “Secure Implementation in Economies with Indivisible Objects
and Money,” Economics Letters 100, pp.91-95.
Fujinaka, Y. and T. Wakayama (2011) “Secure Implementation in Shapley-Scarf Housing Markets,”
Economic Theory 48, pp.147-169.
Green, J. and J. J. Laffont (1979) Incentives in Public Decision Making, North Holland.
Groves, T. (1973) “Incentives in Teams,” Econometrica 41, pp.617-631.
Groves, T. and J. Ledyard (1977) “Some Limitations of Demand Revealing Processes,” Public Choice
29, pp.107-124.
Groves, T. and M. Loeb (1975) “Incentives and Public Inputs,” Journal of Public Economics 4, pp.211226.
Hain, R. and M. Mitra (2004) “Simple Sequencing Problems with Interdependent Costs,” Games andEconomic Behavior 48, pp.271-291.
Hashimoto, K. and H. Saitoh (2010) “Domain Expansion of the Pivotal Mechanism,” Social Choice andWelfare 34, pp.455-470.
Hashimoto, K. and H. Saitoh (2011) “Strategy-Proof and Anonymous Rule in Queueing Problems: A
Relationship between Equity and Efficiency,” Social Choice and Welfare, available online at http://www.springerlink.com/content/th704g5706407n7h/.
Holmström, B. (1979) “Groves’ Scheme on Restricted Domains,” Econometrica 47, pp.1137-1144.
Hurwicz, L. and M. Walker (1990) “On the Generic Nonoptimality of Dominant-Strategy Allocation
Mechanisms: A General Theorem That Includes Pure Exchange Economies,” Econometrica 58,
pp.683-704.
Hurwicz, L. and S. Reiter (2006) Designing Economic Mechanisms, Cambridge University Press.
Jackson, M. O. (2001) “A Crash Course in Implementation Theory,” Social Choice and Welfare 18,
pp.655-708.
Jackson, M. O. (2003) “Mechanism Theory,” in Encyclopedia of Life Support Systems, edited by U.
Derigs, EOLSS Publishers.
Kayı, C,. and E. Ramaekers (2010) “Characterizations of Pareto-Efficient, Fair, and Strategy-Proof Allocation Rules in Queueing Problems,” Games and Economic Behavior 68, pp.220-232.
Kumar, R. (2009) “Secure Implementation in Production Economies,” mimeo.
Laffont, J. J. and E. Maskin (1980) “A Differential Approach to Dominant Strategy,” Econometrica 48,
pp.1507-1520.

17

Liu, L. and G. Tian (1999) “A Characterization of the Existence of Optimal Dominant Strategy Mechanisms,” Review of Economic Design 4, pp.205-218.
Maniquet, F. (2003) “A Characterization of the Shapley Value in Queueing Problems,” Journal of Economic Theory 109, pp.90-103.
Maskin, E. (1977) “Nash Equilibrium and Welfare Optimality,” mimeo, the revised version appeared in
Review of Economic Studies 66 (1999) pp.23-38.
Maskin, E. and T. Sjöström (2002) “Implementation Theory,” in Handbook of Social Choice and Welfare,edited by K. Arrow, A. Sen, and K. Suzumura, North Holland.
Mendelson, H. and S. Whang (1990) “Optimal incentive compatible priority pricing for M/M/1 queue,”
Operations Research 38, pp.870-883.
Mishra, D. and B. Rangarajan (2007) “Cost Sharing in a Job Scheduling Problem,” Social Choice andWelfare 29, pp.369-382.
Mitra, M. (2001) “Mechanism Design in Queueing Problems,” Economic Theory 17, pp.277-305.
Mitra, M. (2002) “Achieving the First Best in Sequencing Problems,” Review of Economic Design 7,
pp.75-91.
Mitra, M. (2005) “Incomplete Information and Multiple Machine Queueing Problems,” European Journal of Operational Research 165, pp.251-266.
Mitra, M. and A. Sen (2010) “Efficient Allocation of heterogeneous Commodities with Balanced Transfers,” Social Choice and Welfare 35, pp.29-48.
Mitra, M. and S. Mutuswami (2011) “Group Strategyproofness in Queueing Models,” Games and Economic Behavior 72, pp.242-254.
Mitsui, T. (1983) “Asymptotic Efficiency of the Pivotal Mechanism with General Project Space,” Journalof Economic Theory, 31, pp.318-331.
Mizukami, H. and T. Wakayama (2007) “Dominant Strategy Implementation in Economic Environments,” Games and Economic Behavior 60, pp.307-325.
Mizukami, H. and T. Wakayama (2008) “Secure Implementation: An Alternative Characterization,”
Working Paper No. 238, University of Toyama.
Moulin, H. (1986) “Characterization of the Pivotal Mechanism,” Journal of Public Economics 31, pp.5378.
Moulin, H. (2007) “On Scheduling Fees to Prevent Merging, Splitting and Transferring of Jobs,” Mathematics of Operations Research 32, pp.266-283.
Moulin, H. (2008) “Proportional Scheduling, Split-Proofness, and Merge-Proofness,” Games and Economic Behavior 63, pp.567-587.
18

Nishizaki, K. (2011) “Secure Implementation in Discrete and Excludable Public Good Economies,”
Osaka Economic Papers 61, pp.48-56.
Ohseto, S. (2000) “Strategy-Proof and Efficient Allocation of an Indivisible Good on Finitely Restricted
Preference Domains,” International Journal of Game Theory 29, pp.365-374.
Repullo, R. (1987) “A Simple Proof of Maskin’s Theorem on Nash-Implementation,” Social Choice andWelfare 4, pp.39-41.
Rob, R. (1982) “Asymptotic Efficiency of the Demand Revealing Mechanism,” Journal of Economic
Theory 28, pp.207-220.
Saijo, T. (1987) “On Constant Maskin Monotonic Social Choice Functions,” Journal of Economic Theory42, pp.382-386.
Saijo, T. (1988) “Strategy Space Reduction in Maskin’s Theorem: Sufficient Conditions for Nash Implementation,” Econometrica 56, pp.693-700.
Saijo, T., T. Sjöström, and T.Yamato (2003) “Secure Implementation: Strategy-Proof Mechanisms Reconsidered,” RIETI Discussion Paper 03-E-019.
Saijo, T., T. Sjöström, and T.Yamato (2007) “Secure Implementation,” Theoretical Economics 2, pp.203229.
Saitoh, H. and S. Serizawa (2008) “Vickrey Allocation Rule with Income Effect,” Economic Theory 35,
pp.391-401.
Sakai, T. (2008) “Second Price Auctions on General Preference Domains: Two Characterizations,” Economic Theory 37, pp.347-356.
Satterthwaite, M. A. and H. Sonnenschein (1981) “Strategy-Proof Allocation Mechanisms at Differentiable Points,” Review of Economic Studies 48, pp.587-597.
Schummer, J. (2000) “Manipulation through Bribes,” Journal of Economic Theory 91, pp.180-198.
Serizawa, S. (2006) “Pairwise Strategy-Proofness and Self-Enforcing Manipulation,” Social Choice andWelfare 26, pp.305-331.
Suijs, J. (1996) “On Incentive Compatibility and Budget Balancedness in Public Decision Making,”
Economic Design 2, pp.193-209.
Svensson, L. G. (1983) “Large Indivisibles: An Analysis with Respect to Price Equilibrium and Fairness,” Econometrica 51, pp.939-954.
Tian, G. (1996) “On the Existence of Optimal Truth-Telling Dominant Mechanisms,” Economics Letters
53, pp.17-24.
Tideman, T. N. and G. Tullock (1976) “A New and Superior Process for Making Social Choices,” Journalof Political Economy 84, pp.1145-1159.
19

Vickrey, W. (1961) “Counterspeculation, Auctions, and Competitive Sealed Tenders,” Journal of Finance
16, pp.8-37.
Walker, M. (1978) “A Note on the Characterization of Mechanisms for the Revelation of Preferences,”
Econometrica 46, pp.147-152.
Walker, M. (1980) “On the Nonexistence of a Dominant Strategy Mechanism for Making Optimal Public
Decisions,” Econometrica 48, pp.1521-1540.

20