Discussion Papers In Economics
And Business

Strategy-Proof and Anonymous Rule in
Queueing Problems: A Relationship between
Equity and Efficiency
Kazuhiko Hashimoto

Hiroki Saitoh

Discussion Paper 08-17

Graduate School of Economics andOsaka School of International Public Policy (OSIPP)
Osaka University, Toyonaka, Osaka 560-0043, JAPANStrategy-Proof and Anonymous Rule in
Queueing Problems: A Relationship between
Equity and Efficiency
Kazuhiko Hashimoto

Hiroki Saitoh

Discussion Paper 08-17
April 2008

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

Graduate School of Economics andOsaka School of International Public Policy (OSIPP)
Osaka University, Toyonaka, Osaka 560-0043, JAPANStrategy-Proof and Anonymous Rule in
Queueing Problems: A Relationship between
Equity and Eﬃciency
Kazuhiko Hashimoto∗
Graduate School of Economics, Osaka University
andHiroki Saitoh†
Institute of Social and Economic Research, Osaka University
April, 2008

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

keywords: Queueing Problems, Strategy-Proofness, Anonymity in welfare, Eﬃciency
JEL Classiﬁcation 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†
JSPS Research Fellow. Corresponding address: Institute of Social and Economic
Research, Osaka University, 6-1, Mihogaoka, Ibaraki, Osaka 567-0047, JAPAN. E-mail:hsaito@iser.osaka-u.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 diﬀer 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, eﬃciency has been focused on mainly. A rule is queue-eﬃcient if the total
waiting cost among agents is minimized. While queue-eﬃciency concerns eﬃciency for queues, budget-balance (the sum of transfers is zero) does eﬃciency
for transfers. Queue-eﬃciency combined with budget-balance is equivalent
to Pareto-eﬃciency.
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 deﬁned the rule which assigns
the Shapley value to the agents’ ﬁnal utility. He has characterized the rulewith Pareto-eﬃciency and auxiliary axioms. Chun (2006a) has constructed adiﬀerent transferable utility game, and deﬁned 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 satisﬁes queue-eﬃciency 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) satisﬁes not only strategy-proofnessand queue-eﬃciency but also budget-balance (that is, Pareto-eﬃciency).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 satisﬁes Pareto-eﬃciency, 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 eﬃcient rules mainly.
However, agents may not care about anything but equity. In such environments, an equitable rule is desirable from agents’ point of view, althougheﬃciency 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 eﬃciency, and show that under strategy-proofness, anonymity inwelfare implies queue-eﬃciency. 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 satisﬁes strategy-proofness, anonymity in welfare
and budget-balance.
In an auction model, the Vickrey allocation rule is the only rule thatsatisﬁes 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 diﬀerence 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 = σj for all i, j ∈ N with i = 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-eﬃciency.
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 proﬁle. Let C ≡Rn+ be the set of cost
proﬁles. Let Z ≡ {(σ, t) ≡ (σi , ti )i∈N ∈ X n : (a) σ is a queue and (b)i∈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 ci ,ui (fi (c); ci ) ≥ ui(fi (ci , 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 (ci , cj , c−{i,j}); ci ), where ci = cj and cj = 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 satisﬁes 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 eﬃciency.
Definition 4 A rule f is Pareto-eﬃcient 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-eﬃciency is decomposable into two conditions of eﬃciency: queueeﬃciency (eﬃciency for queues) and budgetbalance (eﬃciencyfor transfers).
A queue σ is an eﬃcient queue for c if i∈N (σi − 1)ci ≤ i∈N (σi − 1)ci
for all queue σ  . Let Q∗ (c) be the set of eﬃcient queues for c. By deﬁnition,
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 = j,ci ≥ cj whenever σi < σj .
Definition 5 A rule f = (σ, t) is queue-eﬃcient if for all c ∈ C, σ(c) ∈ Q∗ (c).
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 eﬃciency.
Theorem 1 If f = (σ, t) is strategy-proof and anonymous in welfare, thenit is queue-eﬃcient.
The proof is in the next section.
Note that strategy-proofness and equal treatment of equals in welfare do
not imply queue-eﬃciency. Forexample, let f = (σ, t) be such that for allc ∈ C, σi (c) = i and ti (c) = − j=i (j − 1)cj . One can easily check that thisrule satisﬁes strategy-proofness and equal treatment of equals but does notsatisfy queue-eﬃciency.6 Thus, anonymity in welfare is crucial in theorem 1.
Kayı and Ramaekers (2007) have characterized the rules satisfying strategyproofness, Pareto-eﬃciency, 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 deﬁned 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) = −





c +

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

1 n − 2 j=i k=i,j



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-eﬃciency. 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 ﬁnal 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 satisﬁes
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 ﬁrst, we give some deﬁnitions (see Figure 1). Given c ∈ C, let
K 1 (c) ≡ {i ∈ N : ci > min cj },
j∈N

2

1

3

2

cj },
K (c) ≡ {i ∈ K (c) : ci > min
1j∈K (c)cj }, and so on.
K (c) ≡ {i ∈ K (c) : ci > min2j∈K (c)That is, K 1 (c) is the set of agents whose unit waiting costs are not minimal
in 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 ci ≡ minj∈N cj andc ≡ (ci , c−i ). Since #K 1 (c ) = k1 − 1, the hypothesis of induction implies
that σh (c ) ≤ k1 − 1 for all h ∈ K 1 (c ). Thus, there exists j ∈ N\K 1 (c ) suchthat σj (c ) = 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 (ci ) and−(k1 − 1)ci + ti (ci ) ≥ −(σi (c) − 1)ci + ti (c).
These two inequalities then imply that
(σi (c) − k1 )(ci − ci ) ≥ 0.
Since ci − ci < 0, we must have σi (c) − k1 ≤ 0. Therefore, σi (c) ≤ k1 .
Case 2. j = i (see Figure 2).
Let cj ≡ ci and c ≡ (ci , cj , c−{i,j} ). Then it holds by anonymity in welfarethatui (fi (c); ci ) = ui (fj (c ); ci ) and ui(fi (c ); ci ) = ui (fj (c ); ci ),that is,−(σi (c) − 1)ci + ti (c) = −(σj (c ) − 1)ci + tj (c ) and−(k1 − 1)ci + tj (c ) = −(σi (c ) − 1)ci + ti (c ).
They are equivalent toti (c) = (σi (c) − σj (c ))ci + tj (c ) andtj (c ) = (k1 − σi (c ))ci + ti (c ).
By strategy-proofness, we also have−(σj (c ) − 1)cj + tj (c ) ≥ −(k1 − 1)cj + tj (c ).

7

(1)
(2)

This is equivalent totj (c ) ≥ (σj (c ) − k1 )cj + tj (c ),= (σj (c ) − k1 )cj + (k1 − σi (c ))ci + ti (c ),(3)where equality comes from (2). Strategy-proofness also implies that−(σi (c ) − 1)ci + ti (c ) ≥ −(σi (c) − 1)ci + ti (c).
This is equivalent to
0 ≥ (σi (c ) − σi (c))ci + ti (c) − ti (c ),= (σi (c ) − σi (c))ci + [(σi (c) − σj (c ))ci + tj (c )] − ti (c ),≥ (σi (c ) − σi (c))ci + (σi (c) − σj (c ))ci
+ [(σj (c ) − k1 )cj + (k1 − σi (c ))ci + ti (c )] − ti (c )= (σi (c) − k1 )(ci − ci ),where the ﬁrst equality comes from (1), the second inequality comes from(3), and the second equality comes from cj = ci . Since ci − ci > 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-eﬃciency. Thus, the remaining
problem to show queue-eﬃciency 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 queueeﬃciency. Thus, the remaining problem to show queue-eﬃciency 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 eﬃciency,
and have shown that strategy-proofness and anonymity in welfare imply
8

queue-eﬃciency. Agents are usually more concerned with equity than efﬁciency, while eﬃciency 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 thatsatisﬁes strategy-proofness, anonymity in welfare, and budget-balance. By
this result, the equally distributed pairwise pivotal rule is the best rule fromnot only an eﬃcient 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 anddiﬀerent serving times. In these researches, eﬃciency 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.
??
[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. ??
[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. ??
[10] Kayı, C., E. Ramaekers, 2007, Eﬃciency, Fairness, and StrategyProofness in Queueing Problems: Characterizations and Impossibility.
??
[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. ??
[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. ??.
[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

c

c
cj

ci

cj

ci

cj

ci

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

12

j

agent