ISSN (Print) 0473-453X

Discussion Paper No. 1120

ISSN (Online) 2435-0982

A CHARACTERIZATION
OF THE VICKERY RULE
IN SLOT ALLOCATION PROBLEMS

Yu Zhou
Youngsub Chun
Shigehiro Serizawa

March 2021

The Institute of Social and Economic Research
Osaka University
6-1 Mihogaoka, Ibaraki, Osaka 567-0047, JapanA characterization of the Vickery rule inslot allocation problems
Yu Zhouy

Youngsub Chunz

Shigehiro Serizawax

March 1, 2021

Abstract
We study the slot allocation problem where agents have quasi-linear
single-peaked preferences over slots and identify the rules satisfying e¢ ciency, strategy-proofness, and individual rationality. Since the quasi-linear
single-peaked domain is not connected, the famous characterization of theVickrey rule in terms of the three properties in Holmström (1979) cannot beapplied. However, we are able to establish that on the quasi-linear singlepeaked domain, the Vickrey rule is still the only rule satisfying e¢ ciency,
strategy-proofness, and individual rationality.
Keywords: Slot allocation problem, single-peakedness, e¢ ciency, strategyproofness, individual rationality, Vickrey rule
JEL Classi…cation: C78, D44, D71

We are very grateful to an anonymous referee for comments. Shigehiro Serizawa and Yu
Zhou gratefully acknowledge …nancial support from the Joint Usage/Research Center at ISER,
Osaka University and Grant-in-aid for Research Activity, Japan Society for the Promotion of
Science (15J01287, 15H03328, 15H05728, 19K13653, 20H05631, 20KK0027). Youngsub Chun is
supported by the National Research Foundation of Korea Grant funded by the Korean Government (NRF-2016S1A3A2924944).
yGraduate
Schoolof
Economics,
Kyoto
University,
Japan.
E-mail:zhouyu_0105@hotmail.com
z
Department of Economics, Seoul National University, Republic of Korea.
E-mail:ychun@snu.ac.kr
xInstitute of Social and Economic Research, Osaka University, Japan.
E-mail:serizawa@iser.osaka-u.ac.jp

1

Introduction

We study the slot allocation problem of deciding how to assign slots to agentsand how much each agent should pay. We focus on the case where agents havequasi-linear single-peaked preferences over slots, represented by the single-peaked
valuations of slots. We allow the possibility that some agent cannot get a slot,
due to the facility capacity. The allocation of time slots in the gym or golf games
matches our settings. For example, each gym member or golfer may have her most
preferred starting time, and the preferred starting time may be di¤erent acrossgym members or golfers. Moreover, the capacity of gym or gold club may not besu¢ cient enough to accommodate all members.
We try to identify the rule satisfying e¢ ciency, strategy-proofness, and individual rationality. An allocation speci…es how slots are assigned to agents andhow much each agent should pay. A rule is a mapping from the domain, i.e., theclass of valuation pro…les, to the set of allocations. An allocation is e¢ cient if
the assignment of slots maximizes the sum of all agents’ valuations. E¢ ciency
describes the property of a rule that for each valuation pro…le, the rule always
selects an e¢ cient allocation. Strategy-proofness states that for each agent andeach valuation pro…le, revealing one’s true valuation is a weakly dominant strategy. Individual rationality states that for each agent and each valuation pro…le,everyone should not be worse o¤ than receiving no slot and paying nothing. This
property guarantees the agents’voluntary participation.
On the quasi-linear domain, the Vickrey rule, originated by Vickrey (1961),
Clarke (1971) and Groves (1973), satis…es the above-mentioned three properties.
Holmström (1979) establishes a stronger result: on the smoothly connected domain, the Vickrey rule is the only rule satisfying those three properties. Since
the quasi-linear domain is smoothly connected, the Holmström’s characterization
holds.
On the other hand, we are interested in the quasi-linear single-peaked domain,i.e., the class of single-peaked valuation pro…les, which is a proper subdomain of
the quasi-linear domain. The smaller a domain is, the weaker the properties ofrules are, such as e¢ ciency and strategy-proofness. Thus, smaller domains imply
the possibility of better rules tailored to our problems. Although the Vickrey
rule is e¢ cient, strategy-proof, and individually rational in the quasi-linear singlepeaked domain, it is not clear whether it is the only rule satisfying the threeproperties. In fact, since the quasi-linear single-peaked domain is not smoothly
connected, the Holmström’s technique cannot be applied in our setting to establish
the characterization.
In this paper, we show that the Holmström’s result still holds on our domain:on the quasi-linear single-peaked domain, the Vickrey rule is the only rule satisfying

1e¢ ciency, strategy-proofness, and individual rationality.
On the quasi-linear domain with the identical objects, Ashlagi and Serizawa(2012) characterize the Vickrey rule in terms of strategy-proofness, anonymity inwelfare, and individual rationality. In the task-assignment settings where individual rationality may not be respected, Yengin (2012) characterizes the class ofegalitarian-equivalent Groves mechanisms and studies di¤erent fairness propertiesof the Groves mechanisms. In the queueing setting,1 Chun et al. (2014) characterize the VCG mechanisms in terms of queue e¢ ciency, strategy-proofness, andegalitarian equivalence. Kay¬and Ramaekers (2010) and Chun et al. (2019) focus on the symmetrically balanced Vickrey mechanisms and characterize it byoutcome e¢ ciency, and strategy-proofness, together with some fairness axioms.
Yengin and Chun (2020) characterize some subfamilies of the VCG mechanisms
in terms of no-envy or solidarity properties.
On the non-quasi-linear domain, the minimum price (MP) rule is a naturalextension of the Vickrey rule, which associates each preference pro…le to a MP
equilibrium. Notice that on the quasi-linear domain, the MP equilibrium coincides
with the Vickrey allocation (Leonard, 1983). However, on the non-quasi-linear
domain, the MP equilibrium price in general has no closed-form expression as
the Vickrey payment. In the settings of identical objects, Saitoh and Serizawa(2008) and Sakai (2008) characterize the MP rule by Pareto-e¢ ciency, strategyproofness, individual rationality, and non-negative payments. In the setting ofheterogenous objects, Morimoto and Serizawa (2015) characterize the MP ruleby Pareto-e¢ ciency, strategy-proofness, individual rationality, and no subsidy for
losers. In the generalized queuing settings, i.e., agents have the non-quasi-linear
common-object-ranking preferences, Zhou and Serizawa (2018) characterize theMP rule by using the same axioms as Morimoto and Serizawa (2015).2
It is worth mentioning that Schummer and Vohra (2013), Hougaard et al.
(2014), and Chun and Park (2017) also study the slot allocation problems. Schummer and Vohra (2013) study the reassignment of landing slots without transfers
and focus on the mechanisms with incentive and property rights properties. They
provide a new reassignment mechanism that respects these properties, and discuss the pros and cons between their mechanism and the reassignment algorithm
currently used by the Federal Aviation Administration. Hougaard et al. (2014)
consider the problem of assigning agents to slots on a line where each agent prefers
to be served as close as possible to her target. They consider the aggregate gap
minimizing methods that minimize the total gap between targets and assigned
slots, in terms of both deterministic and probabilistic assignments. Chun and1

Chun (2016) gives a detailed survey of the queueing problem.
In this paper, we do not impose no subsidy or the non-negative payment as an axiom.
Instead, we assume that the payment in an allocation is always non-negative.
2

2

Park (2017) consider a problem of assigning slots to a group of agents with theidentical unit cost. They form such a problem in the setting of bipartite graph,and present a simple way of identifying all e¢ cient assignments. In addition, theyalso introduce the leximin and the leximax rules and discuss their properties.
The remainder is organized as follows: Section 2 de…nes the model. Section
3 de…nes the Vickrey rule. Section 4 shows the characterization result, together
with its proof. Section 5 concludes.

2

The model

There is a non-empty …nite set of agents N and a non-empty …nite set of slots M .
Not getting a slot is called receiving the dummy, denoted by 0. Let L be the setof slots, together with the dummy, i.e., L M [ f0g. Each agent either receivesa slot or the dummy. We denote the slot that agent i 2 N receives by xi 2 L. We
denote the amount that agent i pays by ti 2 R. A generic bundle for agent i is apair zi (xi ; ti ) 2 L R.
Each agent has a quasi-linear preference over L R: There is a valuation
function vi : L ! R+ such that (i) vi (0) = 0, (ii) for each m 2 M , vi (m) > 0, and(iii) for each pair (m; t); (m0 ; t0 ) 2 L R, (m; t) Ri (m0 ; t0 ) if and only if vi (m) tvi (m0 ) t0 . Let Vi be the class of agent i’s valuation functions. Let V
V1
Vn
be the quasi-linear domain. A valuation pro…le is an element v (vi )i2N 2 V .
Given v 2 V and N 0 N , let vN 0 (vi )i2N 0 and v N 0 (vi )i2N nN 0 .
Let m be the cardinality of M . Let( (1); : : : ; (m )) be a permutationof slots in M where (1) denotes the …rst slot, (2) denotes the second slot, andso forth. For each pair m; m0 2 M , m > m0 means that slot m has a higher rank
than slot m0 according to .
De…nition 1: A valuation function vi 2 Vi is single-peaked according to if
there is k 2 M such that(i) for each pair m; m0 2 M such that k > m > m0 , vi (k) > vi (m) > vi (m0 ).
(ii) for each pair m; m0 2 M such that m0 > m > k, vi (k) > vi (m) > vi (m0 ).

Let ViSP ( ) be the class of agent i’s valuation functions satisfying singlepeakedness according to . Let V SP ( ) V1SP ( )VnSP ( ) be the quasilinear single-peaked domain according to . It is easily seen that V SP ( )V . We assume that the slot permutation is exogenously given and commonly
known by all agents, and agents’valuation functions are privately known by themselves.
An assignment is an n-tuple (x1 ; : : : ; xn ) 2 Ln such that for each pair i; j 2 N ,if xi 6= 0 and i 6= j, then xi 6= xj , i.e., each slot is assigned to at most one agent. We
denote the set of assignments by X. An allocation is an n-tuple z (z1 ; : : : ; zn )3

((x1 ; t1 ); : : : ; (xn ; tn )) 2 [L R+ ]n such that (x1 ; : : : ; xn ) 2 X. In an allocation,
the payment for each slot is non-negative. We denote the set of allocations by
Z. Given z 2 Z, we denote its assignment and payment (components) at z byx (x1 ; : : : ; xn ) and t (t1 ; : : : ; tn ), respectively.
A rule on V is a mapping f from V to Z. Given a rule f and v 2 V , we denotethe bundle assigned to agent i by fi (v)(xi (v); ti (v)), where xi (v) denotes theassigned object and ti (v) the associated payment. We writef (v)(fi (v))i2N , x(v)(xi (v))i2N , and t(v)(ti (v))i2N .

We focus on the following three properties of a rule, “e¢ ciency,” “strategyproofness,”and “individual rationality.”First, we de…ne the notion of e¢ ciency. An allocation z 2 Z for v 2 V
is e¢ cient if its assignment maximizes the sum of agents’ valuations, i.e., x 2
P
arg max i2N vi (x0i ).
x0 2XE¢ ciency of a rule states that for each valuation pro…le, the rule chooses ane¢ cient allocation.
E¢ ciency: For each v 2 V , x(v) is e¢ cient for v.

Remark 1: An allocation z 2 Z for v 2 Rn is Pareto-e¢ cient if there is no00
allocation z 0 (x0 ; t0 ) 2 [L R]n such thatX(i) for each
X i 2 N , vi (xi ) ti vi (xi ) ti
with at least one strict relation, and (ii)ti
t0i .3 A rule is Pareto-e¢ cient
i2N

i2N

if for each valuation pro…le, it selects a Pareto-e¢ cient allocation. On the quasilinear domain, e¢ ciency is independent of payments. A rule is e¢ cient if and only
if it is Pareto-e¢ cient.4 This result does not hold if agents have non-quasi-linear
preferences.
3

There are two equivalent ways to de…ne the Pareto-e¢ cient allocation: (1) An allocationz 2 Z for v 2 Rn is Pareto-e¢ cient if there is no allocation z 0 = (x0 ; t0 ) 2 [L X
R]n suchthat (i)X00for each i 2 N , vi (xi ) ti vi (xi ) ti with at least strict inequality, and (ii)ti =t0i ; (2)
i2N

i2N

0
0 0
An allocation z 2 Z for v 2 Rn is Pareto-e¢ cient if there is noX
allocation
Xz = (x ; t ) 2 [Lsuch that (i) for each i 2 N , vi (x0i ) t0i = vi (xi ) ti , and (ii)
ti <
t0i .
i2N

4

R]n

i2N

Let f be a rule on V . First, we show that if f is e¢ cient, then f is Pareto-e¢ cient. By
contradiction, suppose that f is not Pareto-e¢ cient. By (1) in footnote 3, there is a valuation
pro…le v and an allocation z 0 2 Z such that (i) for each i 2 N , vi (x0i ) t0i vi (xi (v)) ti (v), (ii)PP
there is j 2 N such that vj (x0j ) t0j > vj (xj (v)) tj (v), and (iii) i2N t0j = i2N ti (v). If wePP
sum up (i) side-by-side for all the agents, then by (ii) and (iii), i2N vi (x0i ) > i2N vi (xi (v)),
contradicting that f is e¢ cient.
Second, we show that if f is Pareto-e¢ cient, then f is e¢ cient. We prove the contra-positiveargument: If f is not e¢ cient, then f is not Pareto-e¢ cient. If f is not e¢ cient, then there is aPPvaluation pro…le v 2 V and an assignment x 2 X such that i2N vi (xi ) > i2N vi (xi (v)). Letz 0 (x0 ; t0 ) 2 Z be such that for each i 2 N , x0i xi and t0i vi (xi ) vi (xi (v)) + ti (v). Then,PPP
for each i 2 N , vi (xi ) t0i = vi (xi (v)) ti (v). Note that i2N t0i = i2N ti (v) + i2N vi (xi )4Second, we de…ne the incentive property of a rule. Strategy-proofness statesthat no agent ever bene…ts from misrepresenting her valuation function.
Strategy-proofness: For each v 2 V , each i 2 N , and each vi0 2 Vi , vi (xi (v))
ti (v) vi (xi (vi0 ; v i )) ti (vi0 ; v i ).
Individual rationality states that no agent is ever assigned a bundle that makes
her worse o¤ than she would be if she had received the dummy and paid nothing.
Individual rationality: For each v 2 V and each i 2 N , vi (xi (v))

3ti (v)

0.

The Vickrey rule

In this section, we de…ne the “Vickrey rule,”and show the famous characterizationof Vickrey rule in terms of e¢ ciency, strategy-proofness, and individual rationality
by Holmström (1979). In addition, we argue that Holmström’s result cannot beapplied to the quasi-linear single-peaked domain.
De…nition 2: A rule f on V is called a Vickrey rule if
P(i) for each v 2 V , x(v) 2 arg max i2N vi (x0i ).
x0 2X(ii) for each i 2 N , ti (v)i (v)Pand i (v)
j2N nfig vj (xj (v)):

i (v) where

i (v)

max
x2X

P

j2N nfig vj (xj )PRemark 2: Let f and f 0 be two Vickrey rules. Then we have (i) i2N vi (xi (v)) =P00i2N vi (xi (v)), and (ii) for each i 2 N , ti (v) = ti (v). (i) follows from De…nition
2(i) that the Vickrey assignment is e¢ cient. However, it may not be uniquesince two assignments can be welfare-equivalent. On the other hand, the Vickrey
payment t(v) is always unique.
In the following, we de…ne the “smooth connectedness”property of a domain,which is introduced by Holmström (1979).
V is smoothly connected
Vn0
De…nition 3: A domain V 0
V1000
if for each i 2 N , each v i 2 V i , each vi 2 Vi , and each vi0 2 Vi0 , there is
one-dimensional parameterized family Vi (vi ; vi0 )fvi ( ; y) 2 Vi0 : y 2 [0; 1]g ofvaluation functions such that:(i) for each x 2 L, vi (x; 0) = vi (x), and vi (x; 1) = vi0 (x).
(ii) for each x 2 L and each y 2 [0; 1], @vi (x; y)n@y exists.
(iii) for each y 2 [0; 1] and each x
b = (bxi ; xb i ) 2 X (vi ; vi0 ; v i ), there is K 2 (0; +1)
such that j@vi (bx ; y)n@yj
K, where X (vi ; vi0 ; v i )fb
x 2 X : 9y 2 [0; 1] s.t.
P i
P
vi (b
xi ; y) + j2N nfig vj (bxj ) = maxxe2X fvi (exi ; y) + j2N nfig vj (exj )gg.
P

P
P
P
P
Since i2N vi (xi ) > i2N vi (xi (v)), then i2N t0i > i2N ti (v). Thus, by(2) in footnote 3, (x(v); t(v)) is not Pareto-e¢ cient, which implies that f is not Pareto-e¢ cient.
i2N vi (xi (v)).

5

It is not hard to verify that the quasi-linear domain V is smoothly connected.
Although Holmström (1979) studies the public good model, his result implies thatin our model, when each agent has quasi-linear preferences and receives at mostone slot, Theorem H holds.
Theorem H (Holmström, 1979): Let V 0
V be smoothly connected. Then, a0rule f on V satis…es e¢ ciency, strategy-proofness, and individual rationality if
and only if it is a Vickrey rule.
However, the quasi-linear single-peaked domain V SP ( ) is not smoothly connected. The following example details this point.
Example 1. Let N = f1g, M = fm1 ; m2 g, and = ( (1); (2)) = (m1 ; m2 ). Under our assumption on the quasi-linear domain, it holds that V SP ( ) = V1SP ( ) =fv1 ( ) 2 V1 : v1 (0) = 0 and v1 (m1 ); vi (m2 ) > 0 such that v1 (m1 ) 6= v1 (m2 )g.
A domain V 0
V is path connected if for each i 2 N , each v i 2 V 0 i ,0each vi 2 Vi , and each vi0 2 Vi0 , there is one-dimensional parameterized family
Vi (vi ; vi0 ) fvi ( ; y) 2 Vi0 : y 2 [0; 1]g of valuation functions such that (i0 ) Condition (i) of De…nition 3 holds and (ii0 ) for each x 2 L and each y 2 [0; 1], vi (x; y)is continuous with respect to y. It is easy to see that smooth connectedness implies path connectedness. Thus, the violuation of path connectedness implies theviolation of smooth connectedness.
In the following, we show that V SP ( ) is not path connected. By contradiction,
suppose that V SP ( ) is path connected. Now consider two valuation functions
v1 ( ) and v10 ( ) such that v1 (0) = 0, v1 (m1 ) = 2, and v1 (m2 ) = 1; v10 (0) = 0,v10 (m1 ) = 1, and v10 (m2 ) = 2. Then, there is one-dimensional parameterized family
fv1 ( ; y) 2 V SP ( ) : y 2 [0; 1]g of valuation functions satisfying (i0 )V1 (v1 ; v10 )and (ii0 ).
For each y 2 [0; 1], let h(y)v1 (m1 ; y) v1 (m2 ; y). Then, by (ii0 ), h( ) is
continuous. Moreover, by (i0 ), h(0) = 1 and h(1) = 1. Thus, by the intermediatevalue theorem, there is y 2 [0; 1] such that h(y) = v1 (m1 ; y) v1 (m2 ; y) = 0; i.e.,v1 (m1 ; y) = v1 (m2 ; y); contradicting v1 ( ; y) 2 V SP ( ). Thus, V SP ( ) is not pathconnected, and so it is not smoothly connected.
Example 1 implies that on the quasi-linear single-peaked domain, Theorem H
cannot be applied. The next section provides a characterization of the Vickrey
rule on the quasi-linear single-peaked domain. The following remark uses Example
1 to show that Theorem H cannot be applied to the “quasi-linear single-dipped
domain”and “the linear preference domain with two extreme peaks,”either.
Remark 3: (i) A valuation function vi 2 Vi is single-dippedness according to if
there is k 2 M such that (i) for each pair m; m0 2 M such that k > m > m0 ,vi (k) < vi (m) < vi (m0 ), and (ii) for each pair m; m0 2 M such that m0 > m > k,6vi (k) < vi (m) < vi (m0 ). Let ViSD ( ) be the class of agent i’s valuation functions
VnSD ( )satisfying single-dippedness according to . Let V SD ( ) V1SD ( )be the quasi-linear single-dipped domain according to . In Example 1, V SD ( ) =V SP ( ) and so Theorem H cannot be applied to V SD ( ).
(ii) A single-peaked domain V SP ( ) satis…es the two-common-extreme-peakednessof slots according to if for each i 2 N and each vi 2 ViSP ( ), either vi ( (1)) >> vi ( (m )) or vi ( (m )) >> vi ( (1)). That is, the slots (1) and (m)are two peaks across all the agents. Let V L ( ) V SP ( ) be the linear preference
domain with two extreme peaks according to . In Example 1, V L ( ) = V SP ( )and so Theorem H cannot be applied to V L ( ).
We end this section by providing two remarks. The …rst remark illustrates
two proper subdomains of the quasi-linear single-peaked domains that satisfy thesmooth connectedness condition.
Remark 4: (i) A single-peaked domain V SP ( ) satis…es the common-peakednessof slots according to if there is k 2 M such that for each i 2 N , each vi 2 ViSP ( ),and each m 2 M nfkg, vi (k) > vi (m). It means that the “peak” of valuations
over slots is the same across all the agents. The single-peaked domain with thecommon-peakedness satis…es the smooth connectedness condition. Thus Theorem
H can be applied.
(ii) A single-peaked domain V SP ( ) satis…es the common-ranking of slots according
to if for each i 2 N , each vi 2 ViSP ( ), and each pair m; m0 2 M with m > m0 ,vi (m) > vi (m0 ). It means that there is a common ranking of slots across all theagents. The single-peaked domain with the common-ranking property satis…es thesmooth connectedness condition. Thus Theorem H can be applied.
The second remark illustrates a proper superdomain of the quasi-linear singlepeaked domain that satisfy the smooth connectedness condition.
Remark 5: For each pair m; m0 2 M , m
m0 means that slot m is ranked ashigh as slot m0 according to . A valuation function vi 2 Vi is single-plateauedaccording to if there are k; k 0 2 M with k
k 0 such that:0(i) for each m 2 M such that kmk , vi (k) = vi (m) = vi (k 0 ).
(ii) for each m; m0 2 M such that k 0 > m > m0 , vi (k) > vi (m) > vi (m0 ):(ii) for each m; m0 2 M such that m0 > m > k, vi (k) > vi (m) > vi (m0 ):Let ViSP L ( ) be the class of agent i’s valuation functions satisfying singleplateauedness according to . Let V SP L ( )V1SP L ( )VnSP L ( ) be
the quasi-linear single-plateaued domain according to . It is easily seen thatV SP ( ) V SP L ( ). The quasi-linear single-plateaued domain satis…es the smoothconnectedness condition. Thus Theorem H can be applied. We conjecture that
this is the minimal domain that includes the single-peaked domain where Theorem
H can be applied.
7

4

Main result

We are ready establish our main result.
Theorem 1: A rule f on V SP ( ) satis…es e¢ ciency, strategy-proofness, and individual rationality if and only if it is a Vickrey rule.
On the quasi-linear domain, a Vickrey rule satis…es the three properties (Holmström, 1979). Thus the “if”part holds. We only need to show the “only if”part:A rule f on V SP ( ) satisfying e¢ ciency, strategy-proofness, and individual rationality is a Vickrey rule. We borrow the proof technique from Chew and Serizawa(2007) and apply it to our setting. We establish four lemmas to complete theproof.
Lemma 1 follows from individual rationality. It says that an agent who getsthe dummy pays nothing. Lemma 2 follows from e¢ ciency. It says that anye¢ cient rule selects an assignment satisfying De…nition 2(i). Lemma 3 follows fromstrategy-proofness. It says that if an agent truncates her valuations by following
the “zi -favoring transformation,”the new bundle that the agent gets remains thesame as her original bundle. Lemma 4 says that if a rule satis…es e¢ ciency,
strategy-proofness, and individual rationality, then the payment of each agent isequal to the expression given in De…nition 2(ii). In consequence, Lemmas 2 and4 together establish the “only if”part. We relegate the complete proof to Section
4.1.
P
A rule f on V satis…es budget balance if for each v 2 V , i2N ti (v) = 0. In
general a Vickrey rule on the quasi-linear domain does not satisfy budget balance.
It is also easy to see that a Vickrey rule on V SP ( ) does not satisfy budget balanceeither. Therefore, from Theorem 1, we have the following result.
Corollary 1: There is no rule f on V SP ( ) satisfying e¢ ciency, strategy-proofness,
individual rationality, and budget balance.
In the following, we discuss the indispensability of the three axioms. We showthat the “only if”part of Theorem 1 fails if one of the axioms is dropped.
Example 2: (i) (Dropping e¢ ciency) Let f be the “no-trade rule” such thatfor each v 2 V SP ( ), it assigns (0; 0) to each agent. This rule satis…es strategyproofness and individual rationality, but not e¢ ciency.
(ii) (Dropping strategy-proofness) A rule f on V SP ( ) is the zero-payment rule ifPfor each v 2 V SP ( ), x(v) 2 arg max i2N vi (x0i ), and for each i 2 N , ti (v) = 0.
x0 2XThis rule satis…es e¢ ciency and individual rationality, but not strategy-proofness.
N(iii) (Dropping individual rationality) Let n = m + 1 and e = (ei )i2N 2 R++. A
SPrule f on V ( ) is a Vickrey rule with a positive entry fee e if for each v 2 V ,Px(v) 2 arg max i2N vi (x0i ), and for each i 2 N , ti (v)i (v)i (v) + ei . A
x0 2X

8

Vickrey rule with positive entry fee e satis…es e¢ ciency and strategy-proofness.
Since n = m + 1, there is i 2 N such that xi = 0. Since i pays a positive entry fee
ei > 0, then 0 > vi (0) ei = ei , violating individual rationality.

4.1

Proof of Theorem 1

In the following, we state four lemmas and show their proofs to formally establish
the “only if”part of Theorem 1.
Since it is easy to verify that Lemma 1 and Lemma 2 hold, we omit their
proofs.
Lemma 1: Let f satisfy individual rationality. Let v 2 V SP ( ). Then, for eachi 2 N , if xi (v) = 0, then ti (v) = 0.
P
Lemma 2: Let f satisfy e¢ ciency. Let v 2 V SP ( ). Then x(v) 2 arg max i2N vi (x0i ).
x0 2X

Lemma 3 shows the implication of strategy-proofness via “zi -favoring transformation.”

De…nition 4: Given zi = (xi ; ti ) 2 M R+ and vi 2 V SP ( ), vi0 2 V SP ( ) is azi -favoring transformation of vi at zi if for each y 2 M nfxi g, vi0 (xi ) vi0 (y) > ti .
Let I(vi ; zi ) be the set of zi -favoring transformations of vi at zi .
Lemma 3: Let f satisfy strategy-proofness. Let v 2 V SP ( ). Let i 2 N , xi (v) 2
M , and vi0 2 I(vi ; fi (v)). Then fi (vi0 ; v i ) = fi (v).
Proof: Let v 0 = (vi0 ; v i ) and y = xi (v 0 ). Strategy-proofness impliesvi (xi (v))

ti (v)

vi0 (y)0vi (y)ti (v 0 ):vi0 (xi (v))

ti (v )(1)
(2)

ti (v):In the following, we show that xi (v) = y. By contradiction, suppose that xi (v) 6= y.
Sinceti (v)ti (v 0 )vi0 (xi (v))> ti (v)then ti (v 0 ) < 0, contradicting f (v 0 ) 2 Z.
Thus xi (v) = y. Then by (1), ti (v 0 )ti (v) = ti (v 0 ) and so fi (vi0 ; v i ) = fi (v).

vi0 (y)(by (2))(by vi0 2 I(vi ; fi (v)))

ti (v), and by (2), ti (v)ti (v 0 ). Thus
Q.E.D.

Lemma 4: Let f satisfy e¢ ciency, strategy-proofness, and individual rationality.
Let v 2 V SP ( ). Then, for each i 2 N , ti (v) = i (v)i (v).
Proof: Let i 2 N . If xi (v) = 0, by e¢ ciency, it is easy to see thati (v)i (v). By individual rationality and Lemma 1, ti (v) = 0 =9i (v) =

i (v).

Let xi (v) 2 M . To show ti (v) =i (v)i (v), we show the impossibility of
(v)
<
t
(v)
(Case
1)
or
0
t
(v)
<
(v)
i
i
i (v)
i
i (v) (Case 2).
iCase 1:i (v)i (v) < ti (v)By De…nition 2, i (v)0. Let vi0 2 ViSP be such that:i (v)0(1-i) 0i (v)i (v) < vi (xi (v)) < ti (v),5(1-ii) for each y 2 M nfxi (v)g, 0 < vi0 (y) < vi0 (xi (v))
i (v) +
i (v).
Let v 0 = (vi0 ; v i ) and y = xi (v 0 ). In the following, we show that xi (v) = y. By
contradiction, suppose that xi (v) 6= y. We consider two cases.
Case A: y = 0.
PP
In this case, vi0 (y) = 0, and so vi0 (y)+ j2N nfig vj (xj (v 0 )) = j2N nfig vj (xj (v 0 )).
SinceX
vj (xj (v 0 ))(by v i0 = v i)i (v)j2N nfig

0i (v) + vi (xi (v))

<

X

max(
x2X

then vi0 (y) +P0
j2N nfig vj (xj (v ))vj (xj ) + vi0 (xi ));j2N nfigP< max( j2N nfig vj (xj ) + vi0 (xi )), contradicting
x2X

that x(v 0 ) is e¢ cient.
Case B: y 2 M nfxi (v)g.
In this case, we haveX
vi0 (y) +vj (xj (v 0 ))j2N nfig

vi0 (y) +

P

i (v)

< vi0 (xi (v)) + i (v)Xmax(
vj (xj ) + vi0 (xi )):x2X

Thus vi0 (y) +(by (1-i))

P0(
j2N nfig vj (xj (v )) < maxx2X(by (1-ii))

j2N nfig

0
j2N nfig vj (xj ) + vi (xi )), contradictingthat x(v 0 ) is e¢ cient.
Altogether, it holds that xi (v) = y = xi (v 0 ). By individual rationality, ti (v 0 )0vi (xi (v)). By (i), ti (v 0 ) vi0 (xi (v)) < ti (v). Thus vi (y) ti (v 0 ) > vi (xi (v)) ti (v),contradicting strategy-proofness.
Case 2: 0 ti (v) < i (v)i (v)In such a case, there is > 0 such that ti (v) + < i (v)i (v). It is easy0SP
to see that there is vi 2 Vi such that(2-i) vi0 (xi (v)) = ti (v) + ;(2-ii) for each y 2 M nfxi (v)g, 0 < vi0 (y) < .
5Note that by (i), vi0 (xi (v))

i (v) +

i (v) > 0.

10

Thus, for each y 2 M nfxi (v)g, we have vi0 (xi (v)) vi0 (y) > ti (v). Since ti (v)0, vi0 2 I(vi ; fi (v)). By Lemma 3, fi (v) = fi (v 0 ) where v 0 = (vi0 ; v i ).
P
0First, we show thati (v). By contradiction, supj2N nfig vj (xj (v ))P00pose thati (v). Recall that xi (v) = xi (v ). Let x =j2N nfig vj (xj (v )) >(xi (v); x i (v 0 )) 2 X. Then we haveXX
vi (xi ) =vj (xj (v 0 )) + vi (xi (v)) > i (v) + vi (xi (v)),
i2N

j2N nfig

which implies that x(v) 2= arg maxThus we have
X

x0 2X

P

0
i2N vi (xi ), contradicting e¢ ciency.

0i (v) + vi (xi (v))

vj (xj (v 0 )) + vi0 (xi (v))

j2N nfig

<

i (v)

max(
x2X

X

(by (2-i))
vj (xj ) + vi0 (xi ))j2N nfigP
Thus x(v 0 ) 2= arg max( j2N nfig vj (xj ) + vi0 (xi )), contradicting e¢ ciency. Q.E.D.
x2X

5Concluding remarks

We consider the problem of deciding how to assign slots to agents and how mucheach agent should pay, with particular attention to the situation where agents
have single-peaked valuations of slots. We aim at identifying the rules satisfyinge¢ ciency, strategy-proofness, and individual rationality. Holmström (1979) showsthat in the domain satisfying the smooth connectedness condition, the Vickrey
rule is the unique rule that satis…es above-mentioned three properties. Since quasilinear domain is a smoothly connected domain, Holmström’s characterization canbe applied. Nevertheless, the quasi-linear single-peaked domain is not connected.
Therefore it is not clear whether the above characterization still holds. We establish that on the quasi-linear single-peaked domain, the Vickrey rule is still the
only rule satisfying e¢ ciency, strategy-proofness, and individual rationality.
Demange et al. (1986) provide two forms of auctions which implement an
allocation selected by the Vickrey rule in the quasi-linear environment. These
auctions work as well for the quasi-linear single-peaked domain. It is interesting
to see whether the single-peakedness helps design auctions with a simpler form.
Morimoto and Serizawa (2015) show that the minimum price rule is a naturalextension of the Vickrey rule to the non-quasi-linear environment, which can be
implemented by the Serial Vickrey mechanism of Zhou and Serizawa (2020). It is
open to see whether the minimum price rule is still the only rule that satis…es our
three axioms on the non-quasi-linear singled-peaked domain.
11

References[1] Ashlagi, I., Serizawa, S., 2012. Characterizing Vickrey allocation rule byanonymity. Social Choice and Welfare 38(3), 531-542.
[2] Chew, S.H., Serizawa, S., 2007. Characterizing the Vickrey combinatorial
auction by induction. Economic Theory 33(2), 393-406.
[3] Chun, Y., 2016. Fair Queueing. Springer International Publishing.
[4] Chun, Y., Mitra, M., Mutuswami, S., 2014. Egalitarian equivalence and strategyproofness in the queueing problem. Economic Theory 56(2), 425-442.
[5] Chun, Y., Mitra, M., Mutuswami, S., 2019. A characterization of the symmetrically balanced VCG rule in the queueing problem. Games and Economic
Behavior 118, 486-490.
[6] Chun, Y., Park, B., 2017. A graph theoretic approach to the slot allocation
problem. Social Choice and Welfare 48(1), 133-152.
[7] Clarke, E.H., 1971. Multipart pricing of public goods. Public Choice 11(1),
17–33.
[8] Demange, G., Gale, D., Sotomayor, M., 1986. Multi-item auctions. Journalof Political Economy 94(4), 863-872.
[9] Groves, T., 1973. Incentives in teams. Econometrica 41(4), 617–631.
[10] Holmström, B., 1979. Groves’ scheme on restricted domains. Econometrica
47(5), 1137-1144.
[11] Hougaard, J.L., Moreno-Ternero, J.D., ?sterdal, L.P., 2014. Assigning agentsto a line. Games and Economic Behavior 87, 539-553.
[12] Kay¬, C., Ramaekers, E., 2010. Characterizations of Pareto-e¢ cient, fair, andstrategy-proof allocation rules in queueing problems. Games and Economic
Behavior 68(1), 220-232.
[13] Leonard, H.B., 1983. Elicitation of honest preferences for the assignment of
individuals to positions. Journal of Political Economy 91(3), 461-479.
[14] Morimoto, S., Serizawa, S., 2015. Strategy-proofness and e¢ ciency with nonquasi-linear preferences: A characterization of minimum price Walrasian rule.
Theoretical Economics 10(2), 445-487.

12

[15] Saitoh, H., Serizawa, S., 2008. Vickrey allocation rule with income e¤ect.
Economic Theory 35(2), 391–401.
[16] Sakai, T., 2008. Second price auctions on general preference domains: Twocharacterizations. Economic Theory 37(2), 347–356.
[17] Schummer, J., Vohra, R.V., 2013. Assignment of arrival slots. American Economic Journal: Microeconomics 5(2), 164-185.
[18] Vickrey, W., 1961. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance 16(1), 8–37.
[19] Yengin, D., 2012. Egalitarian-equivalent Groves mechanisms in the allocationof heterogenous objects. Social Choice and Welfare 38(1), 137–160.
[20] Yengin, D., Chun, Y., 2020. No-envy, solidarity, and strategy-proofness in thequeueing problem. Journal of Mathematical Economics 88, 87-97.
[21] Zhou, Y., Serizawa, S., 2018. Strategy-proofness and e¢ ciency for non-quasilinear common-tiered-object preferences: Characterization of minimum pricerule. Games and Economic Behavior 109, 327-363.
[22] Zhou, Y., Serizawa, S., 2020. Serial Vickrey Mechanism. Institute of Socialand Economic Research Discussion Papers 1095.

13