Munich Personal RePEc Archive

Incentives and justice for sequencing

problems.

Mitra, Manipushpak and De, Parikshit

Indian Statistical Institute, Kolkata

March 2015

Online at https://mpra.ub.uni-muenchen.de/65447/

MPRA Paper No. 65447, posted 07 Jul 2015 04:24 UTC



INCENTIVES AND JUSTICE FOR SEQUENCING PROBLEMS

PARIKSHIT DE AND MANIPUSHPAK MITRA

ABSTRACT. We address the mechanism design issue for the sequencing problem. We

identify the just sequencing rule that serves the agents in the non-increasing order of

their waiting costs and prove that it is a Rawlsian rule. We identify all rVCG mech-

anisms that implement the just sequencing rule. The other properties of the just se-

quencing rule that we identify are the following. It is an affine cost minimizer. It can be

implemented with budget balanced rVCG mechanisms. Finally, when waiting cost and

processing time are private information, we identify all generalized rVCG mechanisms

that ex-post implement the just sequencing rule.

JEL Classifications: C72, D63, D82.

Keywords: sequencing, implementation, outcome efficient sequencing rule, just se-

quencing rule, budget balance, ex-post implementation.

1. INTRODUCTION

In this paper we address the mechanism design issue for the sequencing problem

where agents have quasi-linear preferences. The setting comprises of a finite set of

agents each of whom has one job to process using one facility. The facility can only

handle one job at a time. No job can be interrupted once it starts processing. Each job

is characterized by processing time and waiting cost. The latter represents the agent’s

disutility for waiting one unit of time. There is a well established literature in this

direction (see Dolan [10], Duives, Heydenreich, Mishra, Muller and Uetz [11], Hain

and Mitra [13], Mitra [25], Moulin [27] and Suijs [33]).

A well-known and well studied concept is the outcome efficient sequencing rule

that minimizes the aggregate job completion cost of the agents. Outcome efficiency,

as pointed out by Smith [32], requires that the jobs of the agents are processed in the

non-increasing order of their urgency index where urgency index of any agent as the

ratio of his waiting cost and his processing time. It is well-known that, as long as

preferences are ‘smoothly connected’ (see Holmström [15]), outcome efficienct rules

The authors would like to thank Debasis Mishra, Suresh Mutuswami and Arunava Sen for helpful com-
ments and suggestions.

1



2 PARIKSHIT DE AND MANIPUSHPAK MITRA

can be implemented in dominant strategies if and only if the mechanism is a Vickrey-

Clarke-Groves (VCG) mechanism (see Clarke [8], Groves [12] and Vickrey [35]). For

the sequencing problem outcome efficiency was analyzed by Dolan [10], Mitra [25]

and Suijs [33].

The main contribution of this paper is to address the implementability issue of the

Rawlsian sequencing rule which is based on John Rawls’ principle of distributive jus-

tice (see Rawls [30]). The Rawlsian sequencing rule first identifies the maximum agent

specific job completion cost for each order of serving and then picks that order which

minimizes this maximum agent specific job completion cost. We show that a sequenc-

ing rule for which agents are served in the non-increasing order of their waiting costs

is a Rawlsian sequencing rule. We refer to this rule as the just sequencing rule and

show that this Rawlsian rule is implementable in dominant strategies. We identify all

‘rVCG mechanisms’ that implements the just sequencing rule.

Our result on implementation of the just sequencing rule shows compatibility of in-

centives and justice. In the mechanism design literature without transfers where pref-

erences of the agents are defined using distance from the bliss points, Chichilnisky

and Heal [3] argued that Rawlsian rules are “locally dictatorial” and hence imple-

mentable. However, in the mechanism design literature with transfers, this compat-

ibility of incentives and justice is indeed rare. Papers by Deb and Mishra [9] and Lavi,

Mu’alem and Nisan, N. [22] show that the Rawlsian allocation is incompatible with

implementability in dominant strategies. To the best of our knowledge, the only other

paper that shows this compatibility between incentives and justice is by Velez [34] for

the (house) allocation problems.1

In the mechanism design literature a classic contribution is due to Roberts [31] who

proved that, with unrestricted domains, if an allocation rule is implementable in dom-

inant strategies, then it must be an ‘affine maximizer’ allocation rule. For the sequenc-

ing problem the correct adoption of Roberts’ affine maximizer allocation rules is the

‘affine cost minimizer sequencing rules’. It is quite easy to verify that the outcome ef-

ficient sequencing rule is an affine cost minimizer. Interestingly, the just sequencing

rule, in spite of being a Rawlsian sequencing rule, is an affine cost minimizer.

Consider the sequencing problem where the processing time of the agents are iden-

tical. Such situations are referred to as the queueing problem. Queueing problems has

been analyzed extensively from both normative and strategic viewpoints (see Chun

[4], Chun, Mitra and Mutuswami [5], Hashimoto and Saitoh [14], Kayi and Ramaekars

1Velez [34] showed that the Generalized Money Rawlsian Fair solutions implements the no envy solu-
tion in Nash and Strong Nash equilibria.



INCENTIVES AND JUSTICE 3

[20], Maniquet [23], Mitra [24], Mitra and Mutuswami [29] and Mukherjee [28]). For

the queueing problem, the outcome efficient sequencing rule implies that the rule is

also the just sequencing rule. However, for sequencing problems with non-identical

processing time across agents, outcome efficient sequencing rule is different from the

just sequencing rule and hence such sequencing problems brings out the trade-off be-

tween outcome efficient sequencing rule and the just sequencing rule.

The importance of finding balanced VCG mechanisms to implement outcome effi-

ciency for canonical allocation problems was highlighted by Zhou [37]. However, for

many economic environments implementing outcome efficiency with balanced trans-

fers is not possible (see Hurwicz [16], Hurwicz and Walker [17] and Walker [36]). For

sequencing problem it is possible to get budget balanced (or first best) implementa-

tion with the outcome efficiency (see Mitra[25] and Suijs [33]). We show that we can

also find rVCG mechanisms that implements the just sequencing rule with balanced

transfers and identify the set of all such balanced rVCG mechanisms. Again, for the

queueing problem, the set of all balanced rVCG mechanisms coincide with the set of

all balanced VCG mechanisms.2

The just sequencing rule is independent of the processing time of the agents. There-

fore, if we have a two-dimensional incentive problem, where waiting cost and process-

ing time are private information, ex-post implementability of the just sequencing rule is

possible. If processing times are private information, we have mechanism design prob-

lem under interdependent value, as the processing time generates interdependence

across agents. Hence the correct notion of implementation is ex-post implementation.

Specifically we show that the just sequencing rule is ex-post implementable by making

some minor ‘modification’ in the rVCG mechanisms. Moreover, given the earlier re-

sults on implementability of the just sequencing rule with balanced rVCG mechanisms,

it follows that ex-post implementability with balanced transfers is also a possibility.

Jehiel, Meyer-ter-Vehn, Moldovanu, and Zame [18] proved that the only determinis-

tic social choice functions that are ex-post implementable in generic mechanism de-

sign frameworks with multidimensional signals and interdependent valuations are

those rules for which the same alternative is chosen irrespective of agents’ signals,

that is, the outcome should be independent of the interdependent signals. In sequenc-

ing with two-dimensional incentive problem, one dimension is waiting cost which is

the private value and the other dimension is processing time that generates interde-

pendence in terms of cost of completion time. The just sequencing rule is non-trivial

2The literature on balanced VCG mechanisms for the queueing problem includes paper like Chun ,
Mitra and Mutuswami [6], Kayi and Ramaekars [20] and Mitra [24].



4 PARIKSHIT DE AND MANIPUSHPAK MITRA

in terms of the waiting cost or private value dimension and is independent of the in-

terdependence inducing processing time (like the independence of the interdependent

signal required by Jehiel, Meyer-ter-Vehn, Moldovanu, and Zame [18] for ex-post im-

plementability) and hence, the just sequencing rule is a non-trivial rule which is ex-

post implementable. Moreover, for the outcome efficient sequencing rule the profile

contingent order is dependent on the processing time and hence it is not ex-post im-

plementable under this two-dimensional incentive problem.3

The paper is organized in the following way. In Section 2, we provide the framework

of the sequencing problems. In Section 3, we introduce and analyze the just sequencing

rule. In Section 4 we deal with properties of the just sequencing rule. This is followed

by Section 5 which is the conclusion.

2. THE FRAMEWORK

Consider a finite set of agents N = {1, 2, . . . , n} in need of a facility that can be

used sequentially. Using this facility, the agents want to process their jobs. The job

processing time can be different for different agents. Specifically, for each agent i ∈ N,

the job processing time is given by si > 0. Let R++ be the positive orthant of the real

line R and let θi Si measure the cost of job completion for agent i ∈ N where Si ∈ R++
is the job completion time for this agent and θi ∈ Θ := R++ denotes his constant

per-period waiting cost. Due to the sequential nature of providing the service, the job

completion time Si for agent i depends not only on his own processing time si but

also on the processing time of the agents who precedes him in the order of service. By

means of an order σ = (σ1, . . . , σn) on N, one can describe the positions of each agent in

the order. Specifically, σi = k indicates that agent i has the k-th position in the order. Let

Σ(N) be the set of n! possible orders on N. We define Pi(σ) = { j ∈ N \ {i} | σj < σi}

to be the predecessor set of i in the order σ, that is, set of agents served before agent

i in the order σ. Similarly, P′i (σ) = { j ∈ N \ {i} | σj > σi} denotes the successor

set of i in the order σ, that is, set of agents served after agent i in the order σ. Let

s = (s1, . . . , sn) ∈ S := R
n
++ denote the vector of processing time of the agents. Given

a vector s = (s1, . . . , sn) ∈ S and an order σ ∈ Σ(N), the cost of job completion for

agent i ∈ N is θi Si(σ), where the job completion time is S j(σ) = ∑ j∈Pi(σ) s j + si. The

agents have quasi-linear utility of the form vi(σ, τi ; mi = (θi , si); s−i) = −θi Si(σ) + τi
where σ is the order, τi ∈ R is the transfer that he receives and the parameters of the

3Ex-post implementability literature includes papers by Bergemann and Morris [1], Bikhchandani [2],
Chung and Ely [7], Jehiel, Meyer-ter-Vehn, Moldovanu and Zame [18], Jehiel and Moldovanu [19], and,
Karsten, Kittsteiner, and Benny Moldovanu [21]). For the sequencing problem with private information
only in processing time, incentive issues were addressed by Hain and Mitra [13] and Moulin [27].



INCENTIVES AND JUSTICE 5

model are agents own parameter mi = (θi , si) that constitutes of the waiting cost θi and

the processing time si, and, more importantly, the processing time of the other agents

that determines agent i’s job completion time Si(σ). Specifically, given a commonly

known job processing time vector s = (s1, . . . , sn) ∈ S and an order σ ∈ Σ(N), the

utility of agent i, with just the waiting cost parameter θi, reduces to

vi(σ, τi ; mi = (θi , si); s−i) := Ui(σ, τi ; θi) = −θi Si(σ) + τi = −θi



si + ∑
j∈Pi(σ)

s j



 + τi .

If we assume that both waiting cost and processing time are private information, then

we have a general sequencing problem for N agents which we denote by ΩN = (Θ
n, S).

In this context we associate the utility function vi(.) for each i ∈ N. If the processing

time vector s ∈ S is given and waiting cost is private information, then we have a

sequencing problem ΩsN = (Θ
n, s) and in that case the utility function reduces to Ui(.)

(from vi(.)) for each i ∈ N. Except for Subsection 4.3, we will deal with Ω
s
N . Hence our

first objective is to design direct revelation mechanisms for any given ΩsN .

For any set X, let |X| denote the cardinality of X. A typical profile of waiting costs

is denoted by θ = (θ1, . . . , θn) ∈ Θ
n, and, for any i ∈ N, θ−i ∈ Θ

|N\{i}| denotes the

profile (θ1 . . . θi−1, θi+1, . . . θn) which is obtained from the profile θ by eliminating i’s

waiting cost. For a given sequencing problem ΩsN , a (direct revelation) mechanism is

(σ, τ) that constitutes of a sequencing rule σ and a transfer rule τ. A sequencing rule

is a function σ : Θn → Σ(N) that specifies for each profile θ ∈ Θn a unique order

σ(θ) = (σ1(θ), . . . , σn(θ)) ∈ Σ(N).
4 A transfer rule is a function τ : Θn → Rn that

specifies for each profile θ ∈ Θn a transfer vector τ(θ) = (τi(θ), . . . , τn(θ)) ∈ R
n.

Specifically, given any sequencing problem ΩsN and given any mechanism (σ, τ), if

(θ′i , θ−i) is the announced profile when the true waiting cost of i is θi, then utility of i is

Ui(σ(θ
′
i , θ−i), τi(θ

′
i , θ−i); θi) = −θi Si(σ(θ

′
i , θ−i) + τi(θ

′
i , θ−i).

Definition 1. A mechanism (σ, τ) implements the sequencing rule σ in dominant strate-

gies if the transfer rule τ : Θn → Rn is such that for any i ∈ N, any θi , θ
′
i ∈ Θ and any

θ−i ∈ Θ
|N\{i}|,

(1) Ui(σ(θ), τi(θ); θi) ≥ Ui(σ(θ
′
i , θ−i), τi(θ

′
i , θ−i); θi).

4The sequencing rule is a function and not a correspondence. Hence, we will require tie-breaking rule
to reduce a correspondence to a function which, unless explicitly discussed, will be fixed. We use the
following tie-breaking rule. We fix any linear order ≻ on the set of agents N. For any sequencing rule
σ and any profile θ ∈ Θn with a tie situation between agents i, j ∈ N, we pick the order σ(θ) with
σi(θ) < σj(θ) if and only if i ≻ j.



6 PARIKSHIT DE AND MANIPUSHPAK MITRA

Implementation of a rule σ via a mechanism (σ, τ) requires that the transfer rule τ is

such that truthful reporting for any agent weakly dominates false reporting irrespec-

tive of other agents’ report.

2.1. The outcome efficient sequencing rule.

Definition 2. A sequencing rule σ∗ is outcome efficient if for any θ ∈ Θn, σ∗(θ) ∈

argmin
σ∈Σ(N) ∑i∈N θi Si(σ).

For each profile the outcome efficient sequencing rule selects an order to minimiza-

tion the aggregate cost of completion time. Define ui := θi/si as the urgency index of

agent i which is the ratio of his waiting cost and his processing time. From Smith [32]

we know that for any sequencing problem ΩsN a sequencing rule σ
∗ is outcome efficient

if and only if for any profile θ, the selected order σ∗(θ) satisfies condition (OE): For any

i, j ∈ N, θi/si ≥ θj/s j ⇔ σ
∗
i (θ) ≤ σ

∗
j (θ).

5 Therefore, outcome efficient sequencing rule

requires that the agents are ordered in the non-increasing order of their urgency index.

From (OE) it is clear that if θi/si ≥ θj/s j, then Si(σ
∗(θ)) ≤ S j(σ

∗(θ)). Consider the

outcome efficient sequencing rule σ∗. It is well-known that VCG mechanisms are the

only mechanisms that implement σ∗ (see Holmström [15]).

Definition 3. For the outcome efficient sequencing rule σ∗, a mechanism (σ∗, τ) is a

VCG mechanism if the transfer rule is such that for all θ ∈ Θn and all i ∈ N,

(2) τ∗i (θ) =







hi(θ−i) if P
′
i (σ

∗(θ)) = ∅,

hi(θ−i) − si ∑
j∈P′

i
(σ∗(θ))

θj otherwise.

where the function hi : Θ
|N\{i}| → R is arbitrary.

Given a sequencing problem ΩsN , for any profile θ ∈ Θ
n and any i ∈ N and any

j ∈ N \ {i}, let θjsi be the pivotal cost of agent i on agent j. We call this the pivotal

cost because θjsi is the incremental cost that agent j has to incur if agent i precedes

agent j in any order. The VCG transfer in condition (2) specifies that for any i ∈ N and

any θ−i ∈ Θ
N\{i}, if θi is such that agent i is served last in the outcome efficient order

σ∗(θi , θ−i), that is, if P
′
i (σ

∗(θi , θ−i)) = ∅, then τ
∗
i (θi , θ−i) = hi(θ−i). If, however, θ

′
i is

such that agent i is not served last in the order σ∗(θ′i , θ−i), that is, if P
′
i (σ

∗(θ′i , θ−i) 6= ∅,

then agent i’s transfer τ∗i (θ
′
i , θ−i) not only has hi(θ−i) but he also has to pay the sum of

the pivotal cost that agent i incurs on his followers in the order σ∗(θ′i , θ−i) (that is, the

waiting cost of all the agent(s) served after him times his own processing time).

5Given the tie-breaking rule, this selection is unique.



INCENTIVES AND JUSTICE 7

The VCG transfer τ∗i (θ) (in condition (2)) for which the agent specific constant func-

tions hi(.) are always zero for all agents gives us the pivotal mechanism for implement-

ing the outcome efficient order σ∗. The first work that identified the pivotal mechanism

for any sequencing problem is by Dolan [10]. It must be pointed out that the specifica-

tion (2) of the VCG transfers is the pivotal based representation of the VCG transfers

and is not its standard representation. We show that an appropriate transformation

of the standard VCG transfers gives us (2). The standard way of specifying the VCG

transfers is that for all θ and for all i ∈ N,

(3) τ∗i (θ) = − ∑
j∈N\{i}

S j(σ
∗(θ))θj + gi(θ−i).

6

Consider the outcome efficient order σ∗(θ) for the profile θ ∈ Θn and suppose that

agent i leaves. We define the “induced” order σ∗(θ−i) (of length |N \ {i}|) for the

agents in N \ {i} as follows:

(4) σ∗j (θ−i) =

{

σ∗j (θ) − 1 if j ∈ P
′
i (σ

∗(θ)),

σ∗j (θ) if j ∈ Pi(σ
∗(θ)).

In words, σ∗(θ−i) is the order formed by removing agent i and moving all agents be-

hind him up by one position. Given the same tie-breaking rule for the economy with

N \ {i} agents, it is easy to see that if σ∗(θ) is outcome efficient for the profile θ, then

σ∗(θ−i) is also outcome efficient in N \ {i} for the profile θ−i. Without loss of general-

ity, we can write for all θ and all i ∈ N, (A) gi(θ−i) = ∑ j∈N\{i} S j(σ
∗(θ−i))θj + hi(θ−i).

By substituting (A) in (3) we get

(5) τ∗i (θ) = − ∑
j∈N\{i}

[S j(σ
∗(θ)) − S j(σ

∗(θ−i))]θj + hi(θ−i).

If for a profile θ ∈ Θn, the outcome efficient order is σ∗(θ) and agent i leaves, then the

order σ∗(θ−i) is such that if j ∈ Pi(σ
∗(θ)), then j’s completion time remains unaltered

and if k ∈ P′i (σ
∗(θ)), then k’s completion time reduces by si. Hence

(6) S j(σ
∗(θ)) − S j(σ

∗(θ−i)) =

{

si if j ∈ P
′
i (σ

∗(θ)),

0 if j ∈ Pi(σ
∗(θ)).

By substituting condition (6) in the transformed VCG transfer (5) and then simplifying

it we get the VCG transfer (2).7

6See Mitra [25] and Suijs [33].
7A similar argument for the pivotal based representation of VCG transfers (like condition (2)) for the
queueing problem can be found in Chun, Mitra and Mutuswami [5].



8 PARIKSHIT DE AND MANIPUSHPAK MITRA

3. AN IMPLEMENTABLE RAWLSIAN SEQUENCING RULE

Definition 4. A sequencing rule σ′ is Rawlsian if for each profile θ ∈ Θn, σ′(θ) ∈

min
σ∈Σ(N)

max
j∈N

S j(σ)θj.

Given any profile θ ∈ Θn, for each order σ ∈ Σ(N), let M(σ) = θj S j(σ) ≥ θk Sk(σ)

for all k ∈ N, that is, for the given profile θ and given the order σ, M(σ) is the maximum

value of the cost of completion time among all agents in N. The Rawlsian sequencing

rule picks that order σ′ ∈ Σ(N) for which M(σ′) is minimum, that is M(σ′) ≤ M(σ)

for all σ ∈ Σ(N).

Example 1. Consider the sequencing problem ΩsN such that N = {1, 2, 3} and s =

(s1 = 1, s2 = 2, s3 = 3). Let the waiting cost vector be θ = (θ1 = 100, θ2 = 5, θ3 = 3).

For θ, outcome efficiency uniquely picks the order σ1 = (σ1 = 1, σ2 = 2, σ3 = 3) since

u1 > u2 > u2. However, the Rawlsian selection is not unique. For profile θ we have

the following: M(σ1 = (σ1 = 1, σ2 = 2, σ3 = 3)) = θ1s1 = 100, M(σ
2 = (σ1 = 1, σ2 =

3, σ3 = 2)) = θ1s1 = 100, M(σ
3 = (σ1 = 2, σ2 = 1, σ3 = 3)) = θ1(s2 + s1) = 300,

M(σ4 = (σ1 = 2, σ2 = 3, σ3 = 1)) = θ1(s3 + s1) = 400, M(σ
5 = (σ1 = 3, σ2 =

1, σ3 = 2)) = θ1(s2 + s3 + s1) = 600, and M(σ
6 = (σ1 = 3, σ2 = 2, σ3 = 1)) =

θ1(s3 + s2 + s1) = 600. Therefore, for the profile θ, the Rawlsian rule can either pick

σ1 or σ2 implying that the Rawlsian rule does not guarantee state contingent unique

order selection. Note that the order σ1 also has the property that it serves the agents

in the decreasing (hence non-increasing) order of their waiting cost, that is given θ1 >

θ2 > θ3, agent 1 is served first followed by agent 2 and then by agent 3.

Let the waiting cost vector be θ′ = (θ′1 = 10, θ2 = 5, θ3 = 3). For profile θ
′ we

have the following: M(σ1 = (σ1 = 1, σ2 = 2, σ3 = 3)) = θ3(s1 + s2 + s3) = 18,

M(σ2 = (σ1 = 1, σ2 = 3, σ3 = 2)) = θ2(s1 + s3 + s2) = 30, M(σ
3 = (σ1 = 2, σ2 =

1, σ3 = 3)) = θ
′
1(s2 + s1) = 30, M(σ

4 = (σ1 = 2, σ2 = 3, σ3 = 1)) = θ
′
1(s3 + s1) = 40,

M(σ5 = (σ1 = 3, σ2 = 1, σ3 = 2)) = θ
′
1(s2 + s3 + s1) = 60, and M(σ

6 = (σ1 =

3, σ2 = 2, σ3 = 1)) = θ
′
1(s3 + s2 + s1) = 60. For the profile θ

′, M(σ1) < M(σk) for all

k ∈ {2, . . . , 6} and hence any Rawlsian rule uniquely picks σ1.

The above example suggests that we can have profiles θ for which more than one

order is Rawlsian. It also seems likely that serving the agents in the non-increasing

order of their waiting costs is always Rawlsian. In the next theorem we show that this

is indeed the case.



INCENTIVES AND JUSTICE 9

Definition 5. A sequencing rule σ̃ is just if for each profile θ ∈ Θn, the chosen order

σ̃(θ) satisfies the following property: for any i, j ∈ N such that θi ≥ θj, σ̃i(θ) ≤ σ̃j(θ).
8

Theorem 1. For any ΩsN , the just sequencing rule σ̃ is Rawlsian.

Proof: To prove that the just sequencing rule σ̃ is Rawlsian, consider any profile θ ∈ Θn

and the just order σ̃(θ). Consider that agent i ∈ N for whom the cost of completion

time θi Si(σ̃(θ)) = θi(∑ j∈Pi(σ̃(θ)) s j + si) is maximum under σ̃(θ), that is M(σ̃(θ)) =

θi Si(σ̃(θ)).
9 Define O := Pi(σ̃(θ)) ∪ {i} as the set that includes the set of predecessors

of i under the order σ̃(θ) and that also includes agent i. Observe that from the defini-

tion of just sequencing rule it follows that θj ≥ θi for all j ∈ O. Consider any other

order σ ∈ Σ(N) \ {σ̃(θ)}. For this order σ, there is one agent in O who will be served

last under σ relative to the other members of O, that is, there exists an agent j ∈ O

such that σj > σk for all k ∈ O \ { j}. This means that O ⊆ Pj(σ) ∪ { j}, and hence

S j(σ) ≥ Si(σ̃(θ)), that is the completion time of agent j under the order σ is not less

than the completion time of agent i under the order σ̃(θ). Therefore, the maximum

cost of completion time M(σ) under σ is at least as large as the maximum cost of com-

pletion time M(σ̃(θ)) = θi Si(σ̃(θ)) under σ̃(θ) since M(σ) ≥ θj S j(σ) ≥ θj Si(σ̃(θ)) ≥

θi Si(σ̃(θ)) = M(σ̃(θ)). Since the selection of σ was arbitrary the result follows. �

Remark 1. Consider any sequencing problem Ωs
∗

N with s
∗ = (s∗1 , . . . , s

∗
n) ∈ S and

s∗1 = . . . = s
∗
n so that we have the queueing problem. Then the outcome efficient

sequencing rule implies the just sequencing rule and hence a Rawlsian sequencing

rule. For the queueing problem Ωs
∗

N , for any profile θ ∈ Θ
n, the order of the urgency

indexes and that of the waiting costs are identical and hence this implication.

Definition 6. For the just sequencing rule σ̃, a mechanism (σ̃, τ̃) is an rVCG mechanism

if the transfer rule is such that for all θ ∈ Θn and all i ∈ N,

(7) τ̃i(θ) =







hi(θ−i) if P
′
i (σ̃(θ)) = ∅,

hi(θ−i) − ∑
j∈P′

i
(σ̃(θ))

θjs j otherwise.

where the function hi : Θ
|N\{i}| → R is arbitrary.

Given a sequencing problem ΩsN , for any profile θ ∈ Θ
n and any j ∈ N, let θjs j

be the minimum cost of agent j, that is the cost that agent j would have incurred if

he was served first in any order. Like the VCG transfers (2), the rVCG transfers (7)

8Given the tie-breaking rule, for any profile θ ∈ Θn, this selection σ̃(θ) is unique.
9If there are more than one agent for whom the cost is maximum, pick any one of them arbitrarily.



10 PARIKSHIT DE AND MANIPUSHPAK MITRA

specifies that for any i ∈ N and any θ−i ∈ Θ
N\{i}, if θi is such that agent i is served

last in the just order σ̃(θi , θ−i), then τ̃i(θi , θ−i) = hi(θ−i). If θ
′
i is such that agent i is

not served last in the order σ̃(θ′i , θ−i), then agent i’s transfer τ̃i(θ
′
i , θ−i) not only has

hi(θ−i) but he also has to pay the sum of the minimum cost of his followers in the just

order σ̃(θ′i , θ−i). As long as we are in a sequencing problem Ω
s
N where the processing

time of the agents are not identical, there will be some profile θ and some agent j for

whom the minimum cost θjs j will be different from the pivotal cost θjsi of i on j for

some i ∈ N \ { j}. Hence the payment amounts in the rVCG transfers are qualitatively

different from the payment amounts under the VCG transfers (2) where, recall that,

the payment amount is the sum of the pivotal cost of agent i on all his followers in the

outcome efficient sequencing order. Therefore, it is easy to see that for the queueing

problem Ωs
∗

N we have the following: For any agent j ∈ N, any agent i ∈ N \ {i} and

any profile θ, the minimum cost θjs
∗
j is identical to the pivotal cost θjs

∗
i since s

∗
i = s

∗
j

and, given the same tie-breaking rule, σ∗(θ) = σ̃(θ). Thus, the VCG-mechanisms and

the rVCG mechanisms are identical for the queueing problem Ωs
∗

N .

Theorem 2. The just sequencing rule σ̃ is implementable if and only if the mechanism

(σ̃, τ) that implements it is an rVCG mechanism.

Proof: Consider the just sequencing rule σ̃. We first prove that if a mechanism (σ̃, τ)

implements σ̃, then it is necessarily the rVCG mechanism. Consider any agent i ∈ N

and fix any profile θ−i ∈ Θ
|N\{i}| of all but agent i. By taking any two types θi and θ

′
i

for agent i and applying the two implementation inequalities (1) Ui(σ̃(θ), τi(θ); θi) ≥

Ui(σ̃(θ
′
i , θ−i), τi(θ

′
i , θ−i); θi) and (2) Ui(σ̃(θ), τi(θ); θ

′
i) ≤ Ui(σ̃(θ

′
i , θ−i), τi(θ

′
i , θ−i); θ

′
i). In

general, from inequalities (1) and (2) we get

(8) [Si(σ̃(θ
′
i , θi )) − Si(σ̃(θ))]θi ≥ τi(θ

′
i , θ−i) − τi(θ) ≥ [Si(σ̃(θ

′
i , θi )) − Si(σ̃(θ))]θ

′
i .

If θi and θ
′
i are such that σ̃(θ) = σ̃(θ

′
i , θ−i), then Si(σ̃(θ

′
i , θi )) = Si(σ̃(θ)) and inequal-

ity (8) gives τi(θ) = τi(θ
′
i , θ−i).

Let θ(1) ≥ θ(2) ≥ . . . ≥ θ(n−1) be the decreasing order of the waiting cost for the

fixed profile θ−i. Consider any pair (θ
t+1
i

, θti ) ∈ [θ(t+1), θ(t)] × [θ(t), θ(t−1)]. Using the

just sequencing rule σ̃ and applying the implementability condition (8) when the actual

profile is (θt+1
i

, θ−i) ((θ
t
i , θ−i)) and the misreport of agent i is θ

t
i (θ

t+1
i

) we get

(9) θt+1
i

s(t) ≤ τi(θ
t+1
i

, θ−i) − τi(θ
t
i , θ−i) ≤ θ

t
i s(t).

Since (9) must hold for all (θt+1
i

, θti ) ∈ [θ
(t+1)
i

, θ
(t)
i
] × [θ

(t)
i

, θ
(t−1)
i

], it follows that

(10) τi(θ
t+1
i

, θ−i) − τi(θ
t
i , θ−i) = θ(t)s(t).



INCENTIVES AND JUSTICE 11

Condition (10) must hold for all t ∈ {1, . . . , n − 1}. By setting τi(θ
n
i , θ−i) = hi(θ−i)

for any θni ∈ (0, θ(n−1)) and then solving condition (10) recursively we get the rVCG

transfers (7).

For the converse consider any agent i ∈ N and any profile θ−i. Let θi be the true wait-

ing cost of i and Bi(θ
′
i ; θi) := Ui(σ̃(θ

′
i , θ−i), τi(θ

′
i , θ−i); θi) − Ui(σ̃(θi , θ−i), τi(θi , θ−i); θi)

be the benefit of agent i from a misreport θ′i .

(D1) If θ′i > θi and Pi(σ̃(θi , θ−i)) \ Pi(σ̃(θ
′
i , θ−i)) 6= ∅, then from the just sequencing

rule we get θj ≥ θi for all j ∈ Pi(σ̃(θi , θ−i)) \ Pi(σ̃(θ
′
i , θ−i)). Therefore, using any

rVCG transfer we get Bi(θ
′
i ; θi) = ∑ j∈Pi(σ̃(θi ,θ−i))\Pi(σ̃(θ′i ,θ−i))

(θi −θj)s j ≤ 0.

(D2) If θ′i < θi and Pi(σ̃(θ
′
i , θ−i)) \ Pi(σ̃(θi , θ−i)) 6= ∅, then from the just sequencing

rule we get θj ≤ θi for all j ∈ Pi(σ̃(θ
′
i , θ−i)) \ Pi(σ̃(θi , θ−i)). Hence using any

rVCG transfer we get Bi(θ
′
i ; θi) = ∑ j∈Pi(σ̃(θ′i ,θ−i))\Pi(σ̃(θi ,θ−i))

(θj −θi)s j ≤ 0.

(D3) Finally, if θ′i 6= θi and Pi(σ̃(θ
′
i , θ−i)) = Pi(σ̃(θi , θ−i)), then Bi(θ

′
i ; θi) = 0.

Therefore, cases (D1)-(D3) show that agent i cannot benefit from any deviation. Since

the selection of agent i was arbitrary, the result follows. �

4. PROPERTIES OF THE JUST SEQUENCING RULE

In this section we focus on three nice properties of the just sequencing rule.

4.1. The just sequencing rule as an affine cost minimizer. Roberts [31] defined affine

maximizer allocation rules in a general mechanism design framework with quasi-

linear preferences. However, sequencing problems are cost problems and hence the

appropriate adoption of affine maximizer allocation rule of Roberts to the sequencing

problem is the ‘affine cost minimizer sequencing rules’.

Definition 7. A sequencing rule σw,κ : Θn → Σ(N) is an affine cost minimizer if for each

θ ∈ Θn, σw,κ(θ) ∈ arg minσ∈Σ(N)

{

κ(σ) + ∑ j∈N w jθj S j(σ)
}

, where w j ≥ 0 for all j ∈ N

with at least one w j > 0 and the function κ : Σ(N) → R is arbitrary.

The affine maximizer sequencing rule σ1,0 with κ(σ) = 0 for all σ ∈ Σ(N) and

w j = 1 for all j ∈ N gives the outcome efficient sequencing rule, that is σ
1,0 = σ∗.10 Thus,

the outcome efficient sequencing rule is a affine cost minimizer.

Proposition 1. The just sequencing rule σ̃ is an affine cost maximizer.

10The equality σ1,0 = σ∗ is with the implicit assumption that the tie-breaking rule followed to obtain
σ1,0 is identical to the tie-breaking rule of σ∗.



12 PARIKSHIT DE AND MANIPUSHPAK MITRA

Proof: To prove that the just sequencing rule is a affine cost minimizer, we show that

the affine cost minimizer sequencing rule σw
∗,0 with κ(σ) = 0 for all σ ∈ Σ(N) and

w∗j = 1/(∏r 6= j sr) > 0 for all j ∈ N coincides with the just sequencing rule σ̃.

Consider any profile θ ∈ Θn and any two agents i, j ∈ N with θi ≥ θj. Consider any

order σ such that k = σj = σi + 1 for any given k ∈ {1, . . . , n − 1}. Given our objective

is to minimize ∑ j∈N w
∗
jθj S j(σ), the sum of weighted completion costs of i and j for σ

is

(11)

Ci j(σ) := w
∗
i θi Si(σ) + w

∗
jθj S j(σ) = θi

(

si + ∑k∈Pi(σ) sk

∏r 6=i sr

)

+θj

(

si + s j + ∑k∈Pi(σ) sk

∏r 6= j sr

)

.

Consider the order σ′ obtained from σ by interchanging the positions of i and j only,

that is σ′j = σi , σ
′
i = σj and σ

′
k
= σk for all k ∈ N \ {i, j}. The sum of weighted

completion costs of i and j for σ′ is

(12)

Ci j(σ
′) := w∗i θi Si(σ

′) + w∗jθj S j(σ
′) = θi

(

si + s j ∑k∈Pi(σ) sk

∏r 6=i sr

)

+θj

(

s j + ∑k∈Pi(σ) sk

∏r 6= j sr

)

.

By taking the difference Ci j(σ
′) − Ci j(σ) and using conditions (11) and (12) and making

some obvious simplifications we get

(13) Ci j(σ
′) − Ci j(σ) = (θi −θj)

(

1

∏r∈N\{i, j} sr

)

≥ 0.

In condition (13), the inequality is strict if θi > θj. Condition (13) shows that if

θi ≥ θj, then for any two consecutive positions in an order it is not more costly

to serve agents i before agent j and if θi > θj, then it is less costly to serve agent

i before agent j. Notice that for this conclusion we neither required the profile of

waiting costs of the agents N \ {i, j} nor did we require the positions of the agent

N \ {i, j} in the order. Hence, if for any profile θ ∈ Θn, our objective is to select

σw
∗,0(θ) ∈ arg minσ∈Σ(N)

{

∑ j∈N w
∗
jθj S j(σ)

}

, then σw
∗,0(θ) must follow the following

property: (Aff) For any i, j ∈ N such that θi ≥ θj, σ
w∗,0
i

(θ) ≤ σ
w∗,0
j

(θ). Moreover, since

N \ {i, j} did not matter in condition (13), the converse is also true, that is, given any

profile θ, condition (Aff) gives σw
∗,0(θ) ∈ arg minσ∈Σ(N)

{

∑ j∈N w
∗
jθj S j(σ)

}

. Given the

tie breaking rule, the order obtained by following condition (Aff) is the same as the

order obtained from the just sequencing rule σ̃. Hence the result follows. �

Remark 2. In general, for any affine cost minimizer sequencing rule σw,κ̄ with the prop-

erty that κ(σ) = κ̄ for all σ ∈ Σ(N), urgency index can be replaced by weighted



INCENTIVES AND JUSTICE 13

urgency index uwi = (wiθi)/si to determine the profile contingent order of serving

the agents. Specifically, like Smith’s [32] rule for outcome efficiency, for these affine

cost minimizers σw,κ̄, σw,κ̄(θ) affine cost minimizes {κ̄ + ∑ j∈N w jθj S j(σ)} if and only

if the selected order σw,κ̄(θ) satisfies condition (ACM): For any i, j ∈ N, (wiθi)/si ≥

(w jθj)/s j ⇔ σ
w,κ̄
i

(θ) ≤ σw,κ̄
j

(θ).11 More importantly, the affine cost minimizer se-

quencing rule σw
∗,0 that gives the just sequencing rule σ̃ has w∗j = (1/ ∏k∈N\{ j} sk) as

the agent specific weights and hence weighted urgency index is uw
∗

i = (θi/ ∏k∈N sk).

Therefore, for any θ ∈ Θn and any i, j ∈ N, uw
∗

i ≥ u
w∗

j if and only if θi ≥ θj. That

is, for the affine cost minimizer sequencing rule σw
∗,0 that gives σ̃, comparison of

weighted urgency index across agents reduces to the comparison of the waiting costs

across agents.

4.2. Budget balanced implementability of the just sequencing rule. For implemen-

tation of outcome efficient allocation rules, Zhou [37] provided examples of both public

and private good allocation problems for which no budget balancing VCG mechanisms

exists and for which all VCG mechanisms are inferior to other ‘reasonable’ non-VCG

mechanisms. Zhou [37] concluded that unless one can find a budget balancing VCG

mechanism, one should limit its use. Implementation of outcome efficient rules with

balanced transfers is difficult to get in many economic environments (see, for example,

Hurwicz and Walker [17] and Walker [36]). That implementation of outcome efficiency

is possible with balanced transfers for sequencing and queueing problems was estab-

lished by Mitra [24], [25] and Suijs [33]. Mitra and Sen [26] characterized domains in

a heterogenous objects model with private values where an outcome efficient rule can

be implemented in dominant strategies with balanced transfers. They show that these

domains are non-trivial and are ‘closely’ related to incentive problems in sequencing

and queueing problems studied in Mitra [24], [25] and Suijs [33]. We prove that for

sequencing problems, if we replace outcome efficient sequencing rule with the just se-

quencing rule, we get implementability with balanced transfers provided there are at

least three agents.

Definition 8. A sequencing rule σ is implementable with balanced transfers if the mech-

anism (σ, τ) that implements it has a budget balanced transfer, that is, for all θ ∈ Θn,

∑ j∈N τj(θ) = 0.

Proposition 2. For any sequencing problem Ω
(s1 ,s2)
N={1,2}

with two agents, implementa-

tion of the just sequencing rule σ̃ with balanced transfers is not possible.

11Given the tie-breaking rule, this profile contingent selection σw,κ(θ) is unique.



14 PARIKSHIT DE AND MANIPUSHPAK MITRA

Proof: Fix any processing time vector (s1, s2) and consider the sequencing problem

Ω
s
N={1,2}

. To implement the refined sequencing rule it is necessary that the mechanism

(σ, τ) is an rVCG mechanism (Theorem 2). Pick any rVCG mechanism. Consider the

waiting costs θ1, θ
′
1, θ2, θ

′
2 such that θ1 > θ

′
2 > θ

′
1 > θ2 and θ

′
1s1 6= θ

′
2s2. Budget

balance for the profile (θ1, θ2) gives (B1) h1(θ2) + h2(θ1) − θ2s2 = 0. Budget balance

for (θ1, θ
′
2) gives (B2) h1(θ

′
2) + h2(θ1) −θ

′
2s2 = 0. Budget balance for (θ

′
1, θ2) gives (B3)

h1(θ2) + h2(θ
′
1) − θ2s2 = 0. Finally, budget balance for the profile (θ

′
1, θ

′
2) gives (B4)

h1(θ
′
2) + h2(θ

′
1) −θ

′
1s1 = 0. By adding (B1) and (B4) and subtracting both (B2) and (B3)

from it we get θ′2s2 −θ
′
1s1 = 0 which contradicts the restriction that θ

′
1s1 6= θ

′
2s2. �

Definition 9. Consider any ΩsN with at least three agents. A mechanism (σ̃, τ̃
∗) is a

balanced rVCG mechanism if the transfer rule is such that for all θ ∈ Θn and all i ∈ N,

(14)

τ̃
∗
i (θ) =































∑
j∈N\{i}

(

σ̃j(θ)−1
n−2

)

θjs j + gi(θ−i) if P
′
i (σ̃(θ)) = ∅,

− ∑
j∈N\{i}

(

n−σ̃j(θ)
n−2

)

θjs j + gi(θ−i) if Pi(σ̃(θ)) = ∅,

∑
j∈Pi(σ̃(θ))

(

σ̃j(θ)−1
n−2

)

θjs j − ∑
j∈P′

i
(σ̃(θ))

(

n−σ̃j(θ)
n−2

)

θjs j + gi(θ−i) otherwise.

where gi : Θ
|N\{i}| → R for each i ∈ N is such that for any θ ∈ Θn, ∑i∈N gi(θ−i) = 0.

The balanced rVCG transfer requires that for any profile θ ∈ Θn and given any agent

specific constant transfer gi(θ−i) to agent i, each agent i, in addition, receives as reward

a position specific weighted sum of the minimum cost of all agents served before him

(∑ j∈Pi(σ̃(θ))[(σ̃j(θ) − 1)/(n − 2)]θjs j) under the refined Ralwsian sequencing order σ̃(θ)

(provided Pi(σ̃(θ)) 6= ∅) and agent i also pays a position specific weighted sum of the

minimum cost of all agents served after him (∑ j∈P′
i
(σ̃(θ))[(n −σ̃j(θ))/(n − 2)]θjs j) under

the refined Ralwsian sequencing order σ̃(θ) (provided P′i (σ̃(θ)) 6= ∅). In addition, the

balanced rVCG mechanism also requires that selection of the function gi : Θ
|N\{i}| → R

for each agent i ∈ N must be such that for any θ ∈ Θn, ∑ j∈N g j(θ− j) = 0.

Theorem 3. Let ΩsN be a sequencing problem with at least three agents. The just se-

quencing rule is implementable with balanced transfers if and only if the mechanism

(σ̃, τ) that implements it is a balanced rVCG mechanism.

Proof: We know that the just sequencing rule is implementable if and only if the mech-

anism is an rVCG mechanism (Theorem 2). Therefore, identifying the complete class of



INCENTIVES AND JUSTICE 15

mechanisms that implements the just sequencing rule with balanced transfers reduces

to identifying the complete class of balanced rVCG mechanisms.

Suppose there is the refined Ralwsian order σ̃(θ) for the profile θ ∈ Θn and agent

i leaves. We define the “induced” order σ̃(θ−i) (of length |N \ {i}|) for the agents in

N \ {i} as follows:

(15) σ̃j(θ−i) =

{

σ̃j(θ) − 1 if j ∈ P
′
i (σ̃(θ)),

σ̃j(θ) if j ∈ Pi(σ̃(θ)).

In words, σ̃(θ−i) is the order formed by removing agent i and moving all agents behind

him up by one position. Given the same tie-breaking rule for the economy with N \ {i}

agents, it is easy to see that σ̃(θ−i) is also just in N \ {i} for the profile θ−i if σ̃(θ) is just

for the profile θ.

Given that the sequencing problem ΩsN has at least three agents, without loss of

generality, we redefine the rVCG mechanisms by setting for each agent i ∈ N and each

profile θ−i,

(16) hi(θ−i) = ∑
j∈N\{i}

(

σ̃j(θ−i) − 1

n − 2

)

θjs j + gi(θ−i),

where gi : Θ
|N\{i}| → R is arbitrary. By substituting (16) in the rVCG transfer (7) we

get the following for any i ∈ N and any θ ∈ Θn.

(A) If P′i (σ̃(θ)) = ∅, then σ̃j(θ−i) = σ̃j(θ) for all j ∈ N \ {i} and from (7) we get

τ̃i(θ) = hi(θ−i) = ∑ j∈N\{i}

(

σ̃j(θ)−1
n−2

)

θjs j + gi(θ−i).

(B) If Pi(σ̃(θ)) = ∅, then σ̃j(θ−i) = σ̃j(θ) − 1 for all j ∈ N \ {i} and from (7) we get

τ̃i(θ) = − ∑ j∈N\{i} θjs j + hi(θ−i) = − ∑ j∈N\{i} θjs j + ∑ j∈N\{i}

(

σ̃j(θ)−2
n−2

)

θjs j +

gi(θ−i) = − ∑ j∈N\{i}

(

n−σ̃j(θ)
n−2

)

θjs j + gi(θ−i).

(C) If P′i (σ̃(θ)) 6= ∅ and Pi(σ̃(θ)) 6= ∅, then σ̃j(θ−i) = σ̃j(θ) for all j ∈ Pi(σ̃(θ)) 6= ∅,

σ̃j(θ−i) = σ̃j(θ) − 1 for all j ∈ P
′
i (σ̃(θ)) 6= ∅ and from (7) we get

τ̃i(θ) = − ∑
j∈P′

i
(σ̃(θ))

θjs j + hi(θ−i)

= − ∑
j∈P′

i
(σ̃(θ))

θjs j + ∑
j∈Pi(σ̃(θ))

(

σ̃j(θ)−1
n−2

)

θjs j + ∑
j∈P′

i
(σ̃(θ))

(

σ̃j(θ)−2
n−2

)

θjs j + gi(θ−i)

= ∑
j∈Pi(σ̃(θ))

(

σ̃j(θ)−1
n−2

)

θjs j − ∑
j∈P′

i
(σ̃(θ))

(

n−σ̃j(θ)
n−2

)

θjs j + gi(θ−i).

Conditions (A)-(C) show that when the sequencing problem ΩsN has at least three

agents, then an equivalent representation of the rVCG transfers is that for any i ∈ N

and any θ ∈ Θn,



16 PARIKSHIT DE AND MANIPUSHPAK MITRA

(17)

τ̃
′
i (θ) =































∑
j∈N\{i}

(

σ̃j(θ)−1
n−2

)

θjs j + gi(θ−i) if P
′
i (σ̃(θ)) = ∅,

− ∑
j∈N\{i}

(

n−σ̃j(θ)
n−2

)

θjs j + gi(θ−i) if Pi(σ̃(θ)) = ∅,

∑
j∈Pi(σ̃(θ))

(

σ̃j(θ)−1
n−2

)

θjs j − ∑
j∈P′

i
(σ̃(θ))

(

n−σ̃j(θ)
n−2

)

θjs j + gi(θ−i) otherwise,

where for each i ∈ N, the function gi : Θ
|N\{i}| → R is arbitrary. By taking the repre-

sentation (17) of the rVCG transfer we get for any θ ∈ Θn,

∑
k∈N

τ̃′
k
(θ) = ∑

k∈N

{

∑
j∈Pk(σ̃(θ))

(

σ̃j(θ)−1
n−2

)

θjs j − ∑
j∈P′

k
(σ̃(θ))

(

n−σ̃j(θ)
n−2

)

θjs j

}

+ ∑
k∈N

gk(θ−k)

= ∑
k∈N

∑
j∈Pk(σ̃(θ))

(

σ̃j(θ)−1
n−2

)

θjs j − ∑
k∈N

∑
j∈P′

k
(σ̃(θ))

(

n−σ̃j(θ)
n−2

)

θjs j + ∑
k∈N

gk(θ−k)

= ∑
j∈N

{

|P′j(σ̃j(θ))|
(

σ̃j(θ)−1
n−2

)}

θjs j − ∑
j∈N

{

|Pj(σ̃j(θ))|
(

n−σ̃j(θ)
n−2

)}

θjs j + ∑
k∈N

gk(θ−k)

= ∑
j∈N

{

(n −σ̃j(θ))
(

σ̃j(θ)−1
n−2

)}

θjs j − ∑
j∈N

{

(σ̃j(θ) − 1)
(

n−σ̃j(θ)
n−2

)}

θjs j + ∑
k∈N

gk(θ−k)

= ∑
k∈N

gk(θ−k).

Therefore, by taking the representation (17) of the rVCG transfer we have proved

that for any θ ∈ Θn, ∑
k∈N

τ̃′
k
(θ) = ∑

k∈N
gk(θ−k). Therefore, an rVCG mechanism repre-

sented by (17) is budget balanced if and only if (I) for all θ ∈ Θn, ∑
k∈N

gk(θ−k) = 0.

From the representation (17) of the rVCG transfers and from condition (I), the result

follows. �

Remark 3. There are papers that show that for the family of sequencing problems ΩsN
with three or more agents we can find budget balanced VCG mechanisms and hence

implementation with balanced transfer is also possible with the outcome efficient se-

quencing rule (see Mitra [25] and Suijs [33]). From Remark 1 it follows that for the

queueing problem Ωs
∗

N , the set of all balanced rVCG mechanism coincides with the set

of all VCG mechanisms that first best implements the outcome efficient sequencing

rule.

4.3. Two-dimensional incentives and the just sequencing rule. If we assume that

both waiting cost and the processing time are agent specific private information, then

we have the mechanism design problem for the general sequencing problem ΩN =



INCENTIVES AND JUSTICE 17

(Θn, S). Specifically, we have an interdependent value situation and therefore the cor-

rect notion is ex-post implementability. The type of any agent i ∈ N is mi = (θi , si) ∈

Θ × R++ that constitutes of his waiting cost as well as his processing time. A pro-

file is m = (m1, . . . , mn) ∈ Θ
n × S. For any i ∈ N, let m−i, denote the profile

(m1, . . . , mi−1, mi+1, . . . , mn) ∈ Θ
|N\{i}| × R

|N\{i}|
++ which is obtained from the profile

m by eliminating i’s type. For the general sequencing problem ΩN , a (direct reve-

lation) mechanism is (σ g, τ) that constitutes of a general sequencing rule σ g and a

transfer rule τ. A general sequencing rule is a function σ g : Θn × S → Σ(N) that spec-

ifies for each profile m ∈ Θn × S, a unique order σ g(m) = (σ
g
1 (m), . . . , σ

g
n (m)) ∈

Σ(N). A transfer rule is a function τ : Θn × S → Rn that specifies for each profile

m ∈ Θn × S a transfer vector τ(m) = (τ1(m), . . . , τn(m)) ∈ R
n. Specifically, for

ΩN and given any mechanism (σ
g, τ), if m′i is the announced type of agent i when

his true type is mi and m−i is the true profile for agents N \ {i}, then the utility of i

is given by vi(σ
g(m′i , m−i), τi(m

′
i , m−i); mi ; s−i(m−i)) = −θi

(

si + ∑ j∈Pi(σ g(m′i ,m−i))
s j

)

+

τi(m
′
i , m−i).

Definition 10. A mechanism (σ g, τ) ex-post implements the general sequencing rule σ g

if the transfer rule τ : Θn × S → Rn is such that for any i ∈ N, any mi , m
′
i and any true

profile m−i,

(18) vi(σ
g(m), τi(m); mi ; s−i(m−i)) ≥ vi(σ

g(m′i , m−i), τi(m
′
i , m−i); mi ; s−i(m−i)).

Ex-post implementability requires truth-telling is a Nash equilibrium for any agent

and for every true type profile m.

Definition 11. A mechanism (σ g, τ) ex-post implements with balanced transfers the gen-

eral sequencing rule σ g if the transfer rule τ : Θn × S → Rn satisfies ex-post imple-

mentability condition (18) and is also budget balanced, that is for all m ∈ Θn × S → Rn,

∑ j∈N t j(m) = 0.

Definition 12. A general sequencing rule σ̃ g is just if for each profile m ∈ Θn × S, the

chosen order σ̃ g(m) satisfies the following property: for any i, j ∈ N such that θi ≥ θj,

σ̃
g
i
(m) ≤ σ̃

g
j
(m).12

For any true m = (m1 = (θ1, s1), . . . , mn = (θn, sn)) we say θ is obtained from m if

it is a collection of the first element from m j = (θj, s j) for each j ∈ N and we say

s is obtained from m if it is a collection of the second element from m j = (θj, s j) for

each j ∈ N. Similarly, for any i ∈ N and any true m−i = (m1 = (θ1, s1), . . . , mi−1 =

12The tie-breaking rule guarantees state contingent uniqueness of σ̃ g.



18 PARIKSHIT DE AND MANIPUSHPAK MITRA

(θi−1, si−1), mi+1 = (θi+1, si+1), . . . , mn = (θn, sn)) we say θ−i is obtained from m−i if

it is a collection of the first element from m j = (θj, s j) for each j ∈ N \ {i} and we say

s−i is obtained from m−i if it is a collection of the second element from m j = (θj, s j) for

each j ∈ N \ {i}. For ΩN , the just general sequencing rule satisfies the following: For

any m = (m1, . . . , mn) ∈ Θ
n × S, σ̃ g(m) = σ̃(θ) where θ is obtained from m.

Definition 13. For σ̃ g, a mechanism (σ̃ g, τ̃) is a generalized rVCG mechanism if the trans-

fer rule is such that for all m ∈ Θn × S and all i ∈ N,

(19) τ̃
g
i
(θi , m−i) =







h
g
i
(m−i) if P

′
i (σ̃(θi , θ−i)) = ∅,

h
g
i
(m−i) − ∑

j∈P′
i
(σ̃(θi ,θ−i))

θjs j otherwise.

where θ−i is obtained from m−i and h
g
i

: Θ|N\{i}| × R
|N\{i}|
++ → R is arbitrary.

Proposition 3. The just general sequencing rule σ̃ g is ex-post implementable if and

only if the mechanism (σ̃ g, τ) that implements it is a generalized rVCG mechanism.

Proof: We only prove that if the just general sequencing rule σ̃ g is ex-post imple-

mentable via a mechanism (σ̃ g, τ), then the mechanism is a generalized rVCG mecha-

nism. The other part is easy and hence omitted.

Consider any i ∈ N and fix any true type m−i for all agents other than i. For any true

type mi = (θi , si) of i and any misreport m
′
i = (θ

′
i , s

′
i) by i, ex-post implementabil-

ity of the just general sequencing rule σ̃ g requires vi(σ̃
g(m), τi(m); mi ; s−i(m−i)) ≥

vi(σ̃
g(m′i , m−i), τi(m

′
i , m−i); mi ; s−i(m−i)) which is the same as requiring

(20)

vi(σ̃(θi , θ−i), τi(mi , m−i); mi ; s−i(m−i)) ≥ vi(σ̃(θ
′
i , θ−i), τi(m

′
i , m−i); mi , s−i(m−i)).

Moreover, given the true type m−i of all agents and given any pair of types (m
′
i =

(θ′i , s
′
i), m

′′
i = (θ

′
i , s

′′
i )) for i with the property the waiting cost is identical in m

′
i and m

′′
i ,

σ̃ g(m′i , m−i) = σ̃(θ
′
i , θi) = σ̃

g(m′′i , m−i) since just sequencing rule ignores the process-

ing time. Hence, using ex-post implementability, we get the following inequalities:

(1) −θ′i(s
′
i + ∑

j∈Pi(σ̃(θ
′
i
,θ−i))

s j) + τi(m
′
i , m−i) ≥ −θ

′
i(s

′
i + ∑

j∈Pi(σ̃(θ
′
i
,θ−i))

s j) + τi(m
′′
i , m−i).

(2) −θ′i(s
′′
i + ∑

j∈Pi(σ̃(θ
′
i
,θ−i))

s j) +τi(m
′
i , m−i) ≤ −θ

′
i(s

′′
i + ∑

j∈Pi(σ̃(θ
′
i
,θ−i))

s j) +τi(m
′′
i , m−i).

Inequality (1) gives τi(m
′
i , m−i) ≥ τi(m

′′
i , m−i) and inequality (2) gives τi(m

′
i , m−i) ≤

τi(m
′′
i , m−i) and therefore, τi(m

′
i , m−i) = τi(m

′′
i , m−i). Hence we have

(21) τi(m
′
i , m−i) = τi(m

′′
i , m−i) := τi(θ

′
i , m−i).



INCENTIVES AND JUSTICE 19

Using (21) in (20) we get

(22) vi(σ̃(θi , θ−i), τi(θi , m−i); mi ; s−i(m−i)) ≥ vi(σ̃(θ
′
i , θ−i), τi(θ

′
i , m−i); mi , s−i(m−i)).

As long as the true type m−i of agents N \ {i} is known, the processing time of these

agents s−i obtained from m−i is known and θ−i obtained from m−i is also known and

hence the waiting cost cut-off vector (θµ(1), . . . , θµ(R)) for agent i with the just sequenc-

ing rule σ̃ is also known and the calculation of the transfer for agent i is independent

of the processing time of agent i. Therefore, from inequality (22) we get that for any

given si > 0, the following inequality must be true.

(23) Ui(σ̃(θi , θ−i), τi(θi , m−i); θi) ≥ Ui(σ̃(θ
′
i , θ−i), τi(θ

′
i , m−i); θi).

Note that if inequality (23) holds for some given si > 0 and for all θi ∈ Θ, then for

any other s′i > 0 with the same transfer, inequality (23) holds for any θi ∈ Θ since si
(either actual or misreported) does not enter the calculation of the transfer τi(θi , m−i).

The true processing time si only enters in the calculation of the completion time Si(σ̃).

Inequality (23) is similar to the implementability inequality (1) with τi(θi , θ−i) of

inequality (1) replaced by τi(θi , m−i) in (23) where θ−i is the waiting cost vector ob-

tained from m−i. Moreover, the waiting cost cut-off vector (θµ(1), . . . , θµ(R)) for the

just sequencing rule is same for both m−i and θ−i when θ−i is obtained from m−i.

Hence for any true m−i, true θ−i obtained from m−i and any θi , θ
′
i ∈ Θ, we must have

(B) τi(θi , θ−i) − τi(θ
′
i , θ−i) = τi(θi , m−i) − τi(θ

′
i , m−i). From (B) it follows that for any

θi ∈ Θ, any true m−i and θ−i obtained from m−i, (C) τi(θi , m−i) −τi(θi , θ−i) := gi(m−i).

Recall that implementability of the just sequencing rule σ̃ requires that the transfer

must be an rVCG transfer, that is for any θ−i, and any θi ∈ Θ, the transfer τi(θi , θ−i) in

(C) must be equal to the rVCG transfer τ̃i(θi , θ−i) given by (7). Hence from (C) we get

(24) τi(θi , m−i) =







hi(θ−i) + gi(m−i) if P
′
i (σ̃(θi , θ−i)) = ∅,

hi(θ−i) + gi(m−i) − ∑
j∈P′

i
(σ̃(θi ,θ−i))

θjs j otherwise.

where the functions hi : Θ
|N\{i}| → R and gi : Θ

|N\{i}| × R
|N\{i}|
++ → R are arbi-

trary. Without loss of generality, by setting hi(θ−i) + gi(m−i) = h
g
i
(m−i) in (24) we

get τi(θi , m−i) := τ̃
g
i
(θi , m−i) and the result follows. �

That ex-post implementable with balanced transfers is not possible for ΩN={1,2} with

two agents is a natural extension of the arguments in Proposition 2. By applying ar-

guments similar to that in Theorem 3, it is easy to see that the just general sequencing

rule σ̃ g is ex-post implementable with balanced transfers.



20 PARIKSHIT DE AND MANIPUSHPAK MITRA

Definition 14. Consider the general sequencing problem ΩN with at least three agents.

For σ̃ g, a mechanism (σ̃ g, τ̃ g∗) is a balanced generalized rVCG mechanism if the transfer

rule is such that for all m ∈ Θn × S and all i ∈ N,

(25)

τ̃
g∗
i
(θi , m−i) =



























∑
j∈N\{i}

A j(θi)θjs j + g
g
i
(m−i) if P

′
i = ∅,

− ∑
j∈N\{i}

B j(θi)θjs j + g
g
i
(m−i) if Pi = ∅,

∑
j∈Pi(σ̃(θi ,θ−i))

A j(θi)θjs j − ∑
j∈P′

i
(σ̃(θi ,θ−i))

B j(θi)θjs j + g
g
i
(m−i) otherwise.

where θ−i is obtained from m−i, A j(θi) := (σ̃j(θi , θ−i) − 1)/(n − 2), B j(θi) := (n −

σ̃j(θi , θ−i))/(n − 2) and for any i ∈ N, g
g
i

: Θ|N\{i}| × R
|N\{i}|
++ → R is such that for any

m ∈ Θn × S, ∑i∈N g
g
i
(m−i) = 0.

Proposition 4. Let ΩN be the general sequencing problem with at least three agents.

The just general sequencing rule σ̃ g is ex-post implementable with balanced transfers

if and only if the mechanism (σ̃ g, τ) that implements it is a balanced generalized rVCG

mechanism.

5. CONCLUSIONS

We have argued that the nice properties of the just sequencing rule from a mecha-

nism design perspective are the following.

(1) It is a Rawlsian sequencing rule which is implementable in dominant strategies.

(2) It is an affine cost minimizer.

(3) Its implementation is costless, that is, it is implementable with balanced trans-

fers.

(4) Unlike outcome efficiency, even when both waiting cost and processing time

are private information it is ex-post implementable with balanced transfers.

The cost of selecting the just sequencing rule is the efficiency loss, that is, the profile

contingent difference in aggregate completion cost between the just sequencing rule

and the outcome efficient sequencing rule. When the processing time of the agents are

non-identical, this loss is positive for profiles where the order under the just sequencing

rule is different from that of the outcome efficient sequencing rule.

REFERENCES

[1] Bergemann, D. and Morris, S. (2008). Ex-post implementation. Games and Economic Behavior 63,

527-566.



INCENTIVES AND JUSTICE 21

[2] Bikhchandani, S. (2006). Ex-post implementation in environments with private goods. Theoretical

Economics 1 , 369-393.

[3] Chichilnisky, G. and Heal, G. M. (1997). The geometry of implementation: a necessary and sufficient

condition for straightforward games. Social cHoice and Welfare 14, 259-294.

[4] Chun, Y. (2006). No-envy in queueing problems. Economic Theory 29, 151-162.

[5] Chun, Y., Mitra, M. and Mutuswami, S. (2014). Egalitarian equivalence and strategyproofness in

the queueing problem. Economic Theory 56, 425-442.

[6] Chun, Y., Mitra, M. and Mutuswami, S. (2015). A characterization of the symmetrically bal-

anced VCG rule in the queueing problem. Article in press: Games and Economic Behavior,

doi:10.1016/j.geb.2015.04.001.

[7] Chung, K.-S. and Ely, J. C. (2003). Ex-post incentive compatible mechanism design. Working Paper,

Department of Economics, Northwestern University.

[8] Clarke, E. H., (1971). Multi-part pricing of public goods. Public Choice 11, 17-33.

[9] Deb, R. and Mishra, D. (2014). Implementation with contingent contracts. Econometrica 82, 2371-

2393.

[10] Dolan, R. J. (1978). Incentive mechanisms for priority queuing problems. The Bell Journal of Eco-

nomics 9, 421-436.

[11] Duives, J., Heydenreich, B., Mishra, D., Muller, R. and Uetz, M. (2012). On Optimal Mechanism

Design for a Sequencing Problem. mimeo.

[12] Groves, T. (1973). Incentives in teams. Econometrica 41, 617-631.

[13] Hain, R. and Mitra, M. (2004). Simple sequencing problems with interdependent costs. Games and

Economic Behavior 48, 271-291.

[14] Hashimoto, K., and Saitoh, H. (2012). Strategy-proof and anonymous rule in queueing problems: a

relationship between equity and efficiency. Social Choice and Welfare 38, 473-480.

[15] Holmström, B., (1979). Groves’ schemes on restricted domains. Econometrica 47, 1137-1144.

[16] Hurwicz, L., (1975). On the existence of allocative systems whose manipulative Nash equilibria are

Pareto optimal. Mimeo, University of Minnesota.

[17] Hurwicz, L. and Walker, M. (1990). On the generic non-optimality of dominant strategy allocation

mechanisms: A general theorem that includes pure exchange economies. Econometrica 58, 683-704.

[18] Jehiel, P., Meyer-ter-Vehn, M., Moldovanu, B. and Zame, W. R. (2006). The limits of ex-post imple-

mentation. Econometrica 74, 585-610.

[19] Jehiel, P. and Moldovanu, B. (2001). Efficient design with interdependent valuations. Econometrica,

69, 1237-1259.

[20] Kayi, C. and Ramaekers, E. (2010). Characterizations of Pareto-efficient, fair, and strategy-proof

allocation rules in queueing problems. Games and Economic Behavior 68, 220-232.

[21] Fieseler, K. Kittsteiner, T. and Moldovanu, M. (2003). Partnerships, lemons and efficient trade. Jour-

nal of Economic Theory 113, 223-234.

[22] Lavi, R., Mu’alem, A. and Nisan, N. (2004). Towards a Characterization of Truthful Combinatorial

Auctions. Working paper-School of Engineering and Computer Science, The Hebrew University of

Jerusalem, Israel.

[23] Maniquet, F. (2003). A characterization of the Shapley value in queueing problems. Journal of Eco-

nomic Theory, 109(1), 90-103.



22 PARIKSHIT DE AND MANIPUSHPAK MITRA

[24] Mitra, M., (2001). Mechanism design in queueing problems. Economic Theory 17, 277-305.

[25] Mitra, M., (2002). Achieving the first best in sequencing problems. Review of Economic Design 7,

75-91.

[26] Mitra, M. and Sen, A. (2010). Efficient allocation of heterogenous commodities with balanced trans-

fers. Social Choice Welfare 35, 29-48.

[27] Moulin, H., (2007). On Scheduling Fees to Prevent Merging, Splitting, and Transferring of Jobs.

Mathematics of Operations Research 32, 266-283.

[28] Mukherjee, C. (2013). Weak group strategy-proof and queue-efficient mechanisms for the queueing

problem with multiple machines. International Journal of Game Theory, 42(1), 131-163.

[29] Mitra, M., & Mutuswami, S. (2011). Group strategyproofness in queueing models. Games and Eco-

nomic Behavior, 72(1), 242-254.

[30] Rawls, J. (1972). A theory of Justice. Harvard University Press.

[31] Roberts, K. (1979). The characterization of implementable choice rules. In Jean-Jacques Laffont,

editor, Aggregation and Revelation of Preferences. Papers presented at the first European Summer

Workshop of the Econometric Society, pages 321-349, North-Holland Publications.

[32] Smith, W. (1956). Various optimizers for single stage production. Naval Research Logistics Quar-

terly 3, 59-66.

[33] Suijs, J. (1996). On incentive compatibility and budget balancedness in public decision making.

Economic Design 2, 193-209.

[34] Velez, R. A. (2011). Are incentives against economic justice? Journal of Economic Theory 146, 326-

345.

[35] Vickrey, W. (1961). Counterspeculation, auctions and competitive sealed tenders. Journal of Finance

16, 8-37.

[36] Walker, M. (1980). On the non-existence of dominant strategy mechanisms for making optimal

public decisions. Econometrica 48, 1521-1540.

[37] Zhou, L. (2007). The failure of Groves mechanisms in canonical allocation models. Mimeo, Arizona

State University.

ECONOMIC RESEARCH UNIT, INDIAN STATISTICAL INSTITUTE, KOLKATA, INDIA.

E-mail address: parikshit r@isical.ac.in

ECONOMICS RESEARCH UNIT-INDIAN STATISTICAL INSTITUTE, KOLKATA-700108, INDIA.

E-mail address: mmitra@isical.ac.in