Strategy-Proof and Anonymous Rule in
Queueing Problems: A Relationship between
Equity and Efficiency
Kazuhiko Hashimoto∗
Graduate School of Economics, Osaka University
andHiroki Saitoh†
Department of Economics, Kyoto Gakuen University
January, 2009

Abstract
In this paper, we consider a relationship between equity and efficiency in queueing problems. We show that under strategy-proofness,anonymity in welfare implies queue-efficiency. Furthermore, we also
give a characterization of the equally distributed pairwise pivotal rule,as the only rule that satisfies strategy-proofness, anonymity in welfare
and budget-balance.

keywords: Queueing Problems, Strategy-Proofness, Anonymity in welfare, Efficiency
JEL Classification numbers: D63, D71∗

Corresponding address:
Graduate School of Economics, Osaka University, 1-7, Machikaneyama, Toyonaka, Osaka 560-0043, JAPAN. E-mail:fge803hk@mail2.econ.osaka-u.ac.jp†
Corresponding address: Department of Economics, Kyoto Gakuen University,
Kameoka, Kyoto 621-8555, Japan. E-mail: saito-h@kyotogakuen.ac.jp1

1

Introduction

We consider the situations as follows. There are one service (banking, postal,phone, web server, etc.) and money. Agents want to use the service, but notwo agents can be served simultaneously. Each agent’s serving time is thesame, and normalized to unity. Each agent has a constant unit waiting costwhich may differ among agents, and his waiting cost is the product of his
waiting times and his unit waiting cost. Although agents must wait theirturns, they have high values for use enough to do so. To compensate thewaiting agents, monetary transfers are possible. The queueing problems areconcerned with what the orders and the monetary transfers we select for each
unit waiting costs of agents.1 A rule is formulated as a function assigning apair of queue and monetary transfers to agents’ unit waiting costs.
In the most previous literature analyzing the queueing problems, efficiency has been focused on mainly. A rule is queue-efficient if the total
waiting cost among agents is minimized. While queue-efficiency concerns efficiency for queues, budget-balance (the sum of transfers is zero) does efficiency
for transfers. Queue-efficiency combined with budget-balance is equivalent
to Pareto-efficiency.
The literature are divided into two groups; one has the cooperative gameapproach and another has the non-cooperative game approach. In the cooperative game approach, Maniquet (2003) has constructed a transferable
utility game from the queueing problem and defined the rule which assigns
the Shapley value to the agents’ final utility. He has characterized the rulewith Pareto-efficiency and auxiliary axioms. Chun (2006a) has constructed adifferent transferable utility game, and defined and characterized the Shapley
value rule corresponding to the game. As literature that have considered therules using other cooperative game solutions, Katta and Sethuraman (mimeo)
and Kar et al. (mimeo) have analyzed the core rule and the prenucleous rule,
respectively.
In the non-cooperative game approach, Dolan (1978) has provided a rulethat satisfies queue-efficiency and strategy-proofness. Strategy-proofness isthe condition that it is a dominant strategy for any agent to report his true
cost, i.e., it prevents agents from manipulating strategically. While Dolan’s(1978) rule does not satisfy budget-balance, the equally distributed pairwise
pivotal rule 2 proposed by Suijs (1996) satisfies not only strategy-proofnessand queue-efficiency but also budget-balance (that is, Pareto-efficiency).31

In concluding remarks, we will give other problems which have the same structure as
the queueing problems.
2This name has been given by Kayı and Ramaekers (mimeo).
3
Mitra and Mutuswami (mimeo) has characterized the class of rules that satisfy2Moreover, this rule is the only rule that satisfies Pareto-efficiency, strategyproofness, and equal treatment of equals in welfare [Kayı and Ramaekers(mimeo)]. Equal treatment of equals in welfare requires that the rule assign
an allocation for which the welfare levels of agents are equal, as long as theirunit waiting costs are the same.
In both approaches, the authors have analyzed the efficient rules mainly.
However, agents may not care about anything but equity. In such environments, an equitable rule is desirable from agents’ point of view, although
efficiency is a goal of the whole society. Anonymity in welfare is a conditionof equity4 in the sense that the names of the agents do not matter in therule from the viewpoint of welfare level. Anonymity in welfare requires thatwhen the unit waiting costs of two agents are switched, their welfare under
the rule be also switched. In this paper, we consider a relationship between
equity and efficiency, and show that under strategy-proofness, anonymity inwelfare implies queue-efficiency. Therefore, a rule automatically achieves thewhole society’s goal, as long as it pursues agents’ concern. Furthermore, we
also give another characterization of the equally distributed pairwise pivotal
rule, as the only rule that satisfies strategy-proofness, anonymity in welfare
and budget-balance.
In an auction model, the Vickrey allocation rule is the only rule thatsatisfies strategy-proofness, anonymity in welfare, and auxiliary axioms [Serizawa (2006)]. Although queueing model can also be considered as an auction
model, there is a crucial difference between Serizawa (2006) and ours. While
Serizawa (2006) has researched a homogeneous goods model, queueing model
corresponds to a heterogeneous goods model. Thus, both results are independent.
In Section 2, we set up the model and state the results. In Section 3, we
provide proofs. Finally, in Section 4 we make some concluding remarks.

2

The model and the result

Let N = {1, . . . , n} be the set of agents. An n-tuple σ = (σ1 , . . . , σn ) ∈ N n
is a queue if σi 6= σj for all i, j ∈ N with i 6= j. Each agent i ∈ N is assigned
a position σi in a queue σ and a monetary transfer ti ∈ R. Each agent i ∈ N
has quasi-linear preferences on X ≡ N × R, i.e., if agent i’s unit waiting costis ci ∈ R+ , then his preference is represented by ui (σi , ti ; ci ) = −(σi −1)ci +ti .
strategy-proofness and Pareto-efficiency.
4
Envy-freeness is also well-known as a condition of equity. Envy-freeness requires thatno agent should end up with a higher utility by consuming what any other agent consumes.
Chun (2006b) and Kayı and Ramaekers (mimeo) have analyzed the envy-free rules.

3

A list c ≡ (ci )i∈N ∈ Rn+ is a cost profile. Let C ≡Rn+ be the set of costprofiles.
Let Z ≡ {(σ, t) ≡ (σi , ti )i∈N ∈ X n : (a) σ is a queue and (b)Pi∈N ti ≤ 0} be the set of feasible allocations. A rule is a function f from C
to Z.
We consider rules satisfying the following conditions.
Definition 1 A rule f is strategy-proof if for all c ∈ C, all i ∈ N and all c0i ,ui (fi (c); ci ) ≥ ui (fi (c0i , c−i ); ci ).
This is an incentive compatible condition that it is a dominant strategy
for any agent to report his true unit waiting cost.
Next, we introduce two conditions of equity.
Definition 2 A rule f is anonymous in welfare if for all c ∈ C and alli, j ∈ N , ui (fi (c); ci ) = ui (fj (c0i , c0j , c−{i,j} ); ci ), where c0i = cj and c0j = ci .
This condition says that when the unit waiting costs of two agents are
switched, their welfare under the rule are also switched.5 Under this condition, the names of the agents do not matter from the viewpoint of welfare
level.
Definition 3 A rule f satisfies equal treatment of equals in welfare if for allc ∈ C and all i, j ∈ N with ci = cj , ui (fi (c); ci ) = uj (fj (c); cj ).
This condition says that the rule assigns allocations for which the welfare
levels of agents are equal, as long as their unit waiting costs are the same.
Note that anonymity in welfare implies equal treatment of equals in welfare.
Finally, we introduce conditions of efficiency.
Definition 4 A rule f is Pareto-efficient if for all c ∈ C, there is no z ∈ Zsuch that ui (zi ; ci ) ≥ ui (fi (c); ci ) for all i ∈ N and uj (zj ; cj ) > uj (fj (c); cj )for some j ∈ N .
Pareto-efficiency is decomposable into two conditions of efficiency: queueefficiency (efficiency for queues) and budgetP
balance (efficiencyPfor transfers).
A queue σ is an efficient queue for c if i∈N (σi − 1)ci ≤ i∈N (σi0 − 1)ci
for all queue σ 0 . Let Q∗ (c) be the set of efficient queues for c. By definition,
5

In divisible object models, such as exchange [Barberà and Jackson (1995)] or allotment[Sprumont (1991)] models, anonymity requires that two agents’ outcome are switched when
their preferences are switched. However, in indivisible object models, such as auction,
queueing or public decision models, any rule cannot satisfy this type of anonymity. Thus,
we need to impose the condition in terms of welfare instead of outcome [as Moulin (1986)
and Serizawa (2006)]. To distinguish these two conditions, we call the condition used inthis paper anonymity in welfare.

4σ ∈ Q∗ (c) means that, under σ, the agents are served in decreasing orderwith respect to c, i.e., σ ∈ Q∗ (c) if and only if for each i, j ∈ N with i 6= j,ci ≥ cj whenever σi < σj .
Definition 5 A rule f = (σ, t) is queue-efficient if for all c ∈ C, σ(c) ∈ Q∗ (c).
P
Definition 6 A rule f = (σ, t) is budget-balanced if for all c ∈ C, i∈N ti (c) =0.
The following theorem states the relationship between equity and efficiency.
Theorem 1 If f = (σ, t) is strategy-proof and anonymous in welfare, thenit is queue-efficient.
The proof is in the next section.
Note that strategy-proofness and equal treatment of equals in welfare do
not imply queue-efficiency. For
Pexample, let f = (σ, t) be such that for allc ∈ C, σi (c) = i and ti (c) = − j6=i (j − 1)cj . One can easily check that thisrule satisfies strategy-proofness and equal treatment of equals but does notsatisfy queue-efficiency.6 Thus, anonymity in welfare is crucial in theorem 1.
Kayı and Ramaekers (2007) have characterized the rules satisfying strategyproofness, Pareto-efficiency, and equal treatment of equals in welfare. They
have shown that the only rule satisfying the three axioms is the equally distributed pairwise pivotal rule defined as follows.
Definition 7 A rule f = (σ, t) is the equally distributed pairwise pivotal rule
if for each c ∈ C, σ(c) ∈ Q∗ (c), and for each agent i ∈ N ,ti (c) = −XX

j6=i `∈{i,j}∩Fi (σ(c))

c` +

1 XX
n − 2 j6=i k6=i,j

X

c` ,

`∈{j,k}∩Fj (σ(c))

where Fi (σ(c)) is the set of followers of agent i under σ(c).
We explain this rule with an example used by Kayı and Ramekers (2007).
Example 1 Let N = {1, 2, 3, 4} and c ∈ C be such that c1 > c2 > c3 >c4 . First, agents are served in decreasing order with repect to c, that is
σ(c) = (1, 2, 3, 4). Next, consider each pair of agents, and make each agent
6

This example does not satisfy budget-balance. It is an open question whether or
not strategy-proofness, equal treatment of equals in welfare, and budget-balance imply
queue-efficiency. In an auction model, Ando et al. (2008) have discussed a problem whichcorresponds to it. However, they also do not have a general result.

5

in the pair pay the cost that the agent imposes on another agent, that is, thepredecessor pays the unit waiting cost of the follower and the follower pays
nothing. Then, distribute the sum of these two payments equally among
the others. The final monetary transfer is the sum of all transfers for eachpossible pair. The following table shows how payments are calculated.
12
13
14
23
24
34
sum

1
−c2
−c3
−c4
c3
2
c4
2
c4
2

−c2 − c23

2
0
c3
2
c4
2

−c3
−c4

c4
2
− c23

3

4

c2
2

c2
2
c3
2

0

c4
2

0

0

c4
2

−c4
c2
2

c3
2

0
0
c2
+ c3
2

One can check that the equally distributed pairwise pivotal rule satisfies
anonymity in welfare. Furthermore, since anonymity in welfare implies equal
treatment of equals in welfare, we have the following corollary.
Corollary 1 A rule f is strategy-proof, anonymous in welfare and budgetbalanced if and only if it is the equally distributed pairwise pivotal rule.

3

Proof

At first, we give some definitions (see Figure 1). Given c ∈ C, let
K 1 (c) ≡ {i ∈ N : ci > min cj },
j∈N

2

1

3

2

K (c) ≡ {i ∈ K (c) : ci > mincj },1j∈K (c)K (c) ≡ {i ∈ K (c) : ci > mincj }, and so on.
2j∈K (c)That is, K 1 (c) is the set of agents whose unit waiting costs are not minimalin N , K 2 (c) is the set of agents in K 1 (c) whose unit waiting costs are notminimal in K 1 (c), and so on.
Proof of Theorem. Suppose that f = (σ, t) is strategy-proof and anonymous in welfare. We will show that for all c ∈ C, σ(c) ∈ Q∗ (c), that is, theagents are served decreasing order with respect to c. First, we show that theagents in K 1 (c) are served before the agents in N \K 1 (c).
Claim. For all c ∈ C and for all i ∈ K 1 (c), σi (c) ≤ #K 1 (c).
We prove by induction on the cardinality of K 1 (c) as follows.
6

(A) For all c ∈ C with #K 1 (c) = 0, and for all i ∈ K 1 (c), σi (c) ≤ 0.
(B) If for all c ∈ C with #K 1 (c) = k1 −1, and for all i ∈ K 1 (c), σi (c) ≤ k1 −1,then for all c ∈ C with #K 1 (c) = k1 , and for all i ∈ K 1 (c), σi (c) ≤ k1 .
Since #K 1 (c) = 0 is equivalent to K 1 (c) = ∅, (A) is obviously true. We have
only to show (B).
Let k1 be such that 1 ≤ k1 < n, and suppose that for all c ∈ C with
#K 1 (c) = k1 −1, and for all i ∈ K 1 (c) σi (c) ≤ k1 −1 . Let c = (c1 , . . . , cn ) ∈ C
be such that #K 1 (c) = k1 and let i ∈ K 1 (c) be given. Let c0i ≡ minj∈N cj andc0 ≡ (c0i , c−i ). Since #K 1 (c0 ) = k1 − 1, the hypothesis of induction implies
that σh (c0 ) ≤ k1 − 1 for all h ∈ K 1 (c0 ). Thus, there exists j ∈ N \K 1 (c0 ) suchthat σj (c0 ) = k1 . We divide the argument into two cases.
Case 1. j = i.
Strategy-proofness implies that−(σi (c) − 1)ci + ti (c) ≥ −(k1 − 1)ci + ti (c0i ) and−(k1 − 1)c0i + ti (c0i ) ≥ −(σi (c) − 1)c0i + ti (c).
These two inequalities then imply that
(σi (c) − k1 )(c0i − ci ) ≥ 0.
Since c0i − ci < 0, we must have σi (c) − k1 ≤ 0. Therefore, σi (c) ≤ k1 .
Case 2. j 6= i (see Figure 2).
Let c0j ≡ ci and c00 ≡ (c0i , c0j , c−{i,j} ). Then it holds by anonymity in welfarethatui (fi (c); ci ) = ui (fj (c00 ); ci ) and ui (fi (c0 ); ci ) = ui (fj (c0 ); ci ),that is,−(σi (c) − 1)ci + ti (c) = −(σj (c00 ) − 1)ci + tj (c00 ) and−(k1 − 1)c0i + tj (c0 ) = −(σi (c0 ) − 1)c0i + ti (c0 ).
They are equivalent toti (c) = (σi (c) − σj (c00 ))ci + tj (c00 ) andtj (c0 ) = (k1 − σi (c0 ))c0i + ti (c0 ).
By strategy-proofness, we also have−(σj (c00 ) − 1)c0j + tj (c00 ) ≥ −(k1 − 1)c0j + tj (c0 ).
7

(1)
(2)

This is equivalent totj (c00 ) ≥ (σj (c00 ) − k1 )c0j + tj (c0 ),= (σj (c00 ) − k1 )c0j + (k1 − σi (c0 ))c0i + ti (c0 ),(3)where equality comes from (2). Strategy-proofness also implies that−(σi (c0 ) − 1)c0i + ti (c0 ) ≥ −(σi (c) − 1)c0i + ti (c).
This is equivalent to
0 ≥ (σi (c0 ) − σi (c))c0i + ti (c) − ti (c0 ),= (σi (c0 ) − σi (c))c0i + [(σi (c) − σj (c00 ))ci + tj (c00 )] − ti (c0 ),≥ (σi (c0 ) − σi (c))c0i + (σi (c) − σj (c00 ))ci
+ [(σj (c00 ) − k1 )c0j + (k1 − σi (c0 ))c0i + ti (c0 )] − ti (c0 )= (σi (c) − k1 )(ci − c0i ),where the first equality comes from (1), the second inequality comes from(3), and the second equality comes from c0j = ci . Since ci − c0i > 0, we musthave σi (c) − k1 ≤ 0. Therefore, σi (c) ≤ k1 . 2
By the claim, each agent in K 1 (c) is served before the agents in N \K 1 (c),in other words, each agent in N \K 1 (c) is served after the agents in K 1 (c).
Since the unit waiting costs of the agents belonging to N \K 1 (c) are the same,the orders of them are arbitrary for queue-efficiency. Thus, the remaining
problem to show queue-efficiency is that for all c ∈ C, the agents in K 1 (c)are served decreasing order with respect to c.
By the same technique as the claim, we can show that for all c ∈ C, eachagent in K 2 (c) is served before the agents in K 1 (c)\K 2 (c), in other words,
each agent in K 1 (c)\K 2 (c) is served after the agents in K 2 (c) (and also before
the agents in N \K 1 (c)). Since the unit waiting costs of the agents belonging
to K 1 (c)\K 2 (c) are the same, the orders of them are arbitrary for queueefficiency. Thus, the remaining problem to show queue-efficiency is that for
all c ∈ C, the agents in K 2 (c) are served decreasing order with respect to c.
By continuing the same argument repeatedly at most n times, we canshow that for all c ∈ C, σ(c) ∈ Q∗ (c).
Q.E.D.

4

Concluding Remarks

In this paper, we have analyzed a relationship between equity and efficiency,
and have shown that strategy-proofness and anonymity in welfare imply
8

queue-efficiency. Agents are usually more concerned with equity than efficiency, while efficiency is the whole society’s goal. From our result, we cansay that a rule automatically achieves the whole society’s goal, as long as it
pursues agents’ concern. Furthermore, we have also given another characterization of the equally distributed pairwise pivotal rule, as the only rule thatsatisfies strategy-proofness, anonymity in welfare, and budget-balance. By
this result, the equally distributed pairwise pivotal rule is the best rule fromnot only an efficient point of view, but also an equitable one.
In this paper, we have researched the queueing models with one service
and the same serving time. Recently, several authors have analyzed extended
models; Mitra (2005) and Chun and Heo (2007) have analyzed models withmultiple services and the same serving time, Mitra (2002), Chun (2004), andMishra and Rangarajan (2005) have analyzed models with one service anddifferent serving times. In these researches, efficiency has been focused on
mainly. It is a further research to analyze rules focused on equity mainly inextended models.
There are many problems that have the same structure as the queueing
problems. Parking area problems and seat reservation problems are examples.
• Parking area problems: There are month-to-month parking spaces
which are in-line as viewed from the exit. Each agent wants to contract
one and only one parking space. The more distant from the exit, themore costs agents have (imagine the cost as the distance or necessary
time from the parking space to the exit). How should we determine
the agents’ parking space and the monetary transfers among them?
• Seat reservation models: There is an event (concert, movie, sports,etc.), and there are seats which are in-line as viewed from the stage.
Each agent wants to reserve one and only one seat. The more distantfrom the stage, more costs agents have (imagine the cost as the disutility). How should we determine the agents’ seats and the monetarytransfers among them?

References[1] Ando, K., M. Kato, S. Ohseto, 2008, Strategy-Proof and Symmetric
Allocation of an Indivisible Good. Mathematical Social Sciences 55, 1423.
[2] Barberà, S., M. Jackson, 1995, Strategy-Proof Exchange. Econometrica
63, 51-87.
9

[3] Chun, Y., 2004, Consistency and Monotonicity in Sequencing Problems.
mimeo[4] Chun, Y., 2006a, A Pessimistic Approach to the Queueing Problem.
Mathematical Social Sciences 51, 171-181.
[5] Chun, Y., 2006b, No-Envy in Queueing Problems. Economic Theory 29,
151-162.
[6] Chun, Y., E. J. Heo, 2007, Queueing Problems with Two Parallel
Servers. mimeo[7] Dolan, R. J., 1978, Incentive Mechanisms for Priority Queuing Problems. Bell Journal of Economics 9, 421-436.
[8] Hain, R., M. Mitra, 2004, Simple Sequencing Problems with Interdependent Costs. Games and Economic Behavior 48, 271-291.
[9] Katta, A. K., J. Sethuraman, 2006, Cooperation in Queues. mimeo[10] Kayı, C., E. Ramaekers, 2007, Efficiency, Fairness, and StrategyProofness in Queueing Problems: Characterizations and Impossibility.
mimeo[11] Maniquet, F., 2003, A Characterization of the Shapley Value in Queueing Problems. Journal of Economic Theory 109, 90-103.
[12] Mishra, D., B. Rangarajan, 2007, Cost sharing in a job scheduling problem. Social Choice and Welfare 29, 369-382.
[13] Mitra, M., 2001, Mechanism Design in Queueing Problems. Economic
Theory 17, 277-305.
[14] Mitra, M., 2002, Achieving the First Best in Sequencing Problems. Review of Economic Design 7, 75-91.
[15] Mitra, M., 2005, Incomplete Information and Multiple Machine Queueing Problems. European Journal of Operational Research 165, 251-266.
[16] Mitra, M., S. Mutuswami, 2006, Group Strategyproofness in Queueing
Models. mimeo[17] Moulin, H., 1986, Characterizations of the Pivotal Mechanism, Journalof Public Economics 31, 53-78.

10

[18] Serizawa, S., 2006, Strategy-Proof and Anonymous Allocation Rules ofIndivisible Goods. mimeo.
[19] Sprumont, Y., 1991, The Division Problem with Single-Peaked Preferences: A Characterization of the Uniform Allocation Rule. Econometrica
59, 509-519.
[20] Suijs, J., 1996, On Incentive Compatibility and Budget Balancedness in
Public Decision Making. Economic Design 2, 193-209.
cost
c1
c2

c3

c4
c5

1

2

3

5

4

c6

c7

6

7

K 1 (c)K 2 (c)K 3 (c)Figure 1: Illustration of K 1 (c), K 2 (c), and K 3 (c)

11

agent

cost

cost

c

cost

c0

c00
c0j

ci

cj

c0i

cj

c0i

j agent
j agentiiiFigure 2: Illustration of the proof of theorem 1, case 2 of claim

12

j

agent