Document [original]

Singleton Acyclic Mechanisms and their

Applications to Scheduling Problems?

Janina Brenner and Guido Sch¨afer

Institute of Mathematics, Technical University Berlin, Germany

{brenner,schaefer}@math.tu-berlin.de

Abstract. Mehta, Roughgarden, and Sundararajan recently introduced

a new class of cost sharing mechanisms called acyclic mechanisms. These

mechanisms achieve a slightly weaker notion of truthfulness than the

well-known Moulin mechanisms, but provide additional freedom to im-

prove budget balance and social cost approximation guarantees. In this

paper, we investigate the potential of acyclic mechanisms for combinato-

rial optimization problems. In particular, we study a subclass of acyclic

mechanisms which we term singleton acyclic mechanisms. We show that

every ρ-approximate algorithm whose induced cost function is partially

increasing can be turned into a singleton acyclic mechanism that is

weakly group-strategyproof and ρ-budget balanced. Based on this result,

we develop singleton acyclic mechanisms for parallel machine scheduling

problems with completion time objectives, which perform extremely well

both with respect to budget balance and social cost.

Keywords: cooperative game theory, mechanism design, cost sharing mecha-

nisms, combinatorial optimization, scheduling problems.

1 Introduction

We consider the problem of designing truthful mechanisms for binary demand

cost sharing games. We are given a universe Uof players that are interested in a

common service, and a cost function C: 2U→R+that specifies the cost C(S)

to serve player set S⊆U. We require that the cost function Cis increasing,

i.e., C(T)≤C(S) for every T⊆S⊆U, and satisfies C(∅) = 0. In this paper,

we assume that Cis given implicitly by the cost of an optimal solution to an

underlying combinatorial optimization problem P. Every player i∈Uhas a

private, non-negative valuation viand a non-negative bid bifor receiving the

service.

Acost sharing mechanism Mtakes the bid vector b:= (bi)i∈Uas input,

and computes a binary allocation vector x:= (xi)i∈Uand a payment vector

p:= (pi)i∈U. Let SMbe the subset of players associated with the allocation

?This work was supported by the DFG Research Center Matheon “Mathematics for

key technologies”.

vector x, i.e., i∈SMiff xi= 1. We say that SMis the player set that re-

ceives service. We assume that a cost sharing mechanism complies with the

following two standard assumptions: pi= 0 if i /∈SMand pi≤biif i∈SM

(individual rationality) and pi≥0 for all i∈SM(no positive transfer). In

addition, the mechanism has to compute a (potentially suboptimal) feasible so-

lution to the underlying optimization problem Pon the player set SM. We

denote the cost of the computed solution by ¯

C(SM). Mis β-budget balanced if

C(SM)≤Pi∈SMpi≤β·C(SM).

We assume that players act strategically and each player’s goal is to maximize

his own utility. The utility uiof player iis defined as ui(x,p) := vixi−pi. Since

the outcome (x,p) computed by the mechanism Msolely depends on the bids

bof the players, a player may have an incentive to declare a bid bithat differs

from his valuation vi. We say that Mis strategyproof if bidding truthfully is a

dominant strategy for every player.

In this paper, we consider cooperative cost sharing games, i.e., players are

enabled to form coalitions in order to coordinate their bids. A mechanism is

group-strategyproof if no coordinated bidding of a coalition S⊆Ucan ever

strictly increase the utility of some player in Swithout strictly decreasing the

utility of another player in S.

In recent years, considerable progress has been made in devising truthful

mechanisms for cost sharing games. Most notably, Moulin [13] proposed a gen-

eral framework for designing so-called Moulin mechanisms that are truthful and

(approximately) budget balance. The strength of Moulin’s framework lies in the

fact that the resulting mechanisms achieve one of the strongest notions of truth-

fulness, i.e., group-strategyproofness. Most of the mechanisms for cooperative

cost sharing games that are currently prevailing in literature are Moulin mech-

anisms (e.g., [1, 2, 4, 8, 11, 15, 16]).

Recent negative results [1, 2, 9, 11, 15] show that for several fundamental cost

sharing games, Moulin mechanisms can only achieve a very poor budget balance

factor. This effect is further amplified if approximate social cost is desired as

additional objective. The social cost [15] of a set S⊆Uis defined as Π(S) :=

C(S) + Pi/∈Svi. A mechanism Mis said to be α-approximate if the social cost

of the served set SMsatisfies Π(SM)≤α·Π∗, where Π∗:= minS⊆U(C(S) +

Pi/∈Svi) denotes the optimal social cost.

Very recently, Mehta, Roughgarden, and Sundararajan [12] introduced a

more general framework for designing truthful cost sharing mechanisms termed

acyclic mechanisms. Acyclic mechanisms implement a slightly weaker notion of

truthfulness, called weak group-strategyproofness, but therefore leave more flex-

ibility to improve upon the approximation guarantees with respect to budget

balance and social cost. A mechanism is weakly group-strategyproof [5, 12] if no

coordinated bidding of a coalition S⊆Ucan ever strictly increase the utility of

every player in S.

Our Results. In this paper, we investigate the potential of acyclic mechanisms

for combinatorial optimization problems, with a particular focus on scheduling

problems. Our contributions are threefold:

1. Singleton Acyclic Mechanisms. We study a subclass of acyclic mechanisms

that we call singleton acylcic mechanisms. We show that a ρ-approximation

algorithm for the underlying optimization problem Pyields a singleton acyclic

mechanism that is ρ-budget balanced and weakly group-strategyproof if the cost

function ¯

Cinduced by the approximation algorithm is increasing. In fact, a

weaker condition suffices, namely that the induced cost function is only partially

increasing (definition will be given in Section 3). Our proof is constructive, i.e.,

we provide a framework that enables to turn any such approximation algorithm

into a corresponding singleton acyclic mechanism. We also provide a means to

prove approximate social cost for singleton mechanisms that fulfill an additional

weak monotonicity property.

A direct consequence of this result is that several lower bounds on the bud-

get balance factor for Moulin mechanisms can be overcome by acyclic mecha-

nisms. For example, Graham’s largest processing time algorithm [7] gives rise to a

4/3-budget balanced acyclic mechanism for P||Cmax, improving upon the lower

bound of essentially 2 for Moulin mechanisms [1]. Moreover, using the shortest

remaining processing time rule, we obtain a 2-budget balanced acyclic mecha-

nism for P|ri,pmtn|PCi[6], and a 1-budget balanced acyclic mechanism for

1|ri,pmtn|PFi[17], both outperforming the lower bounds of Ω(n) for Moulin

mechanisms [2].

2. Singleton Acyclic Mechanisms for Completion Time Scheduling. We develop

acyclic mechanisms for completion time scheduling, both with and without

release dates and preemption. Namely, we achieve 1-budget balance and 2-

approximate social cost for P||PCi, 1.21-budget balance and 2.42-approximate

social cost for P||PwiCi, and 1-budget balance and 4-approximate social cost

for 1|ri,pmtn|PCi. Not only are these the first cost sharing mechanisms to

achieve constant social cost approximation factors, but we also overcome the

strong lower bound of Ω(n) on the budget balance factor of any Moulin mecha-

nism for all completion time related objectives [2].

3. Approximation Algorithms for Scheduling Problems with Rejection. Every

acyclic mechanism that approximates social cost defines an approximation al-

gorithm for the price-collecting variant of the underlying optimization problem.

As a by-product of the results mentioned above, we therefore obtain constant

approximation algorithms for the respective machine scheduling problems with

rejection; a formal definition will be given in Section 2.

Previous and Related Work. In the theoretical computer science literature,

the cost sharing framework of Moulin [13] has been applied to game-theoretic

variants of many classical optimization problems. Recently, the performance of

Moulin mechanisms has also been studied with respect to social cost, e.g. for

Steiner tree and forest, facility location, single-source rent-or-buy network de-

sign and machine scheduling; see [2, 4, 8, 15, 16]. However, there exist strong lower

bounds on the budget balance and social cost approximation factors that are

achievable by Moulin mechanisms [1, 2, 9, 11]. Consequently, Mehta, Roughgar-

den, and Sundararajan introduced a new class of cost sharing mechanisms called

acyclic mechanisms [12], which they studied mainly in relation to primal-dual

algorithms.

Most of the standard parallel machine scheduling settings are well under-

stood. Lenstra [3] proves that the minimum weighted completion time problem

P| |PiwiCiis NP-complete. Graham’s rule [10] approximates the problem by a

factor of 1

2·(1+√2) ≈1.21. For unit processing times or equal weights, Graham’s

rule delivers an optimal solution.

With release dates and preemption, minimizing the sum of completion times

P|ri,pmtn|PiCibecomes NP-hard [14]. Only the single machine case is solved

optimally by the shortest remaining processing time (srpt) algorithm [17]. srpt

is a 2-approximation algorithm for the parallel machine case [6].

2 Preliminaries

2.1 Acyclic Mechanisms

The general mechanism design setting that we consider in this paper has been

described in the introduction. We briefly review the definition of acyclic mech-

anisms introduced by Mehta, Roughgarden, and Sundararajan in this section;

the reader is referred to [12] for a more detailed description.

An acyclic mechanism is defined in terms of a cost sharing method ξand

an offer function τ. A cost sharing method ξ:U×2U→R+specifies for every

subset S⊆Uand every player i∈Sa non-negative cost share ξi(S); we define

ξi(S) := 0 for all i /∈S.ξis β-budget balanced if for every subset S⊆Uwe

have ¯

C(S)≤Pi∈Sξi(S)≤β·C(S). An offer function τdefines for every subset

S⊆Uand every player i∈Sa non-negative time τ(i, S).

The acyclic mechanism M(ξ, τ) induced by ξand τreceives the bid vector b

as input and proceeds as follows:

1. Initialize S:= U.

2. If ξi(S)≤bifor every player i∈S, then halt. Output the characteristic

vector xof Sand payments p:= (ξi(S))i∈U.

3. Among all players in Swith ξi(S)> bi, let i∗be one with minimum τ(i, S)

(breaking ties arbitrarily).

4. Set S:= S\{i∗}and return to Step 2.

For a given subset S⊆Uand a player i∈S, we partition the player set Sinto

three sets with respect to the offer time of i: let L(i, S), E(i, S) and G(i, S) be

the sets of players with offer times τ(·, S) strictly less than, equal to, or strictly

greater than τ(i, S), respectively. The following definition is crucial to achieve

weakly group-strategyproofness.

Definition 1. Let ξand τbe a cost sharing method and an offer function on U.

The offer function τis valid for ξif the following two properties hold for every

subset S⊆Uand player i∈S:

(P1) ξi(S\T) = ξi(S)for every subset T⊆G(i, S);

(P2) ξi(S\T)≥ξi(S)for every subset T⊆G(i, S)∪(E(i, S)\{i}).

We summarize the main result of Mehta, Roughgarden, and Sundarara-

jan [12] in the following theorem:

Theorem 1 ([12]). Let ξbe a β-budget balanced cost sharing method on Uand

let τbe an offer function on Uthat is valid for ξ. Then, the induced acyclic

mechanism M(ξ, τ)is β-budget balanced and weakly group-strategyproof.

2.2 Parallel Machine Scheduling

In a parallel machine scheduling problem, we are given a set Uof njobs that are

to be scheduled on midentical machines. Every job i∈Uhas a non-negative

release date riand a positive processing time pi. The release date rispecifies the

time when job ibecomes available for execution. The processing time describes

the time needed to execute ion one of the machines. We may also associate

a non-negative weight wiwith every job i∈U. Every machine can execute

at most one job at a time. In the preemptive setting, the execution of a job

can be interrupted at any point of time and resumed later; in contrast, in the

non-preemptive setting, job interruption is not allowed.

Given a scheduling algorithm alg, we denote by Calg

i(S) the completion

time of job i∈Sin the schedule for the set of jobs S⊆Uoutput by alg. We

omit the superscript alg if it is clear from the context to which schedule we

refer. Depending on the underlying application, there are different objectives for

machine scheduling problems. Among the most common objectives are the mini-

mization of the total weighted completion time, i.e., PiwiCi, and the makespan,

i.e., maxiCi, over all feasible schedules.

In our game-theoretic view of machine scheduling problems, each job is iden-

tified with a player who wants his job to be processed on one of the mmachines.

Machine Scheduling with Rejection. Consider an arbitrary scheduling prob-

lem Pwith job set Uand objective function C. A natural variant of this problem

is as follows. Suppose every job i∈Uhas a non-negative penalty zi. We now have

the option to either schedule a job i∈Uand pay its respective contribution to

the objective function value, or to not schedule job ian pay its penalty zi. More

formally, the goal is to compute a subset S⊆Uof jobs such that the overall

cost C(S) + Pi∈U\Sziis minimized. We call the resulting problem scheduling

problem with rejection. (Similar variants for network design problems are usually

called price-collecting; in the scheduling context with due dates, these variants

are sometimes called scheduling with penalties.)

It is easy to verify that every cost sharing mechanism that approximates

social cost by a factor of αdefines an α-approximate algorithm for the underlying

optimization problem with rejections.

3 Singleton Acyclic Mechanisms

When thinking about acyclic mechanisms and their offer functions, we like to

think of clusters. By a cluster we mean a maximal set of players that have the

same offer time with respect to a set S, i.e., two players i, j are in the same

cluster iff τ(i, S) = τ(j, S). With this view, it becomes clear to which extent

acyclic mechanisms generalize Moulin mechanisms: To one end, if there is only

one cluster that contains all players, Definition 1 requires cross-monotonicity,

leading to Moulin mechanisms. To the other end, if all clusters are singletons,

i.e., every player has a unique offer time, then (P2) of Definition 1 reduces to (P1)

and once a cost share is announced to a player, it can never be changed again.

Between these two extremes, there is a great range of other acyclic mechanisms.

However, in this section, we concentrate on the subclass of acyclic mecha-

nisms that result from singleton offer functions, i.e., offer functions that induce

singleton clusters. We call these mechanisms singleton acylcic mechanisms, or

simply singleton mechanisms.

Let τbe a singleton offer function. In the following, we assume that the

elements of a subset S⊆Uare ordered according to non-decreasing offer times,

i.e., S=: {i1, . . . , iq}with τ(il, S)< τ(ik, S) for all 1 ≤l < k ≤q. Moreover,

we define Sk:= {i1, . . . , ik} ⊆ Sas the set of the first 1 ≤k≤qelements in S.

We slightly abuse notation and let for every i∈S,Sirefer to the set Skwith

ik=i. We are particularly interested in singleton offer functions that satisfy the

following consistency property.

Definition 2. A singleton offer function τis called consistent if for all subsets

P⊆S⊆U, ordered as P=: {j1, j2, . . . , jp}and S=: {i1, i2, . . . , iq}, the

following holds: If kis minimal with ik/∈P, then il=jlfor all l < k.

Let alg be a ρ-approximate algorithm for Pand let ¯

Cdenote the cost

function induced by alg, i.e., ¯

C(S) is the cost of the solution computed by

alg for player set S⊆U. We say that ¯

Cis partially increasing with respect to a

singleton offer function τif for every S⊆Uand i∈S, we have ¯

C(Si)≥¯

C(Si−1).

The main result of this section is the following:

Theorem 2. Let alg be a ρ-approximate algorithm for an optimization prob-

lem P. If there exists a consistent singleton offer function with respect to which

the cost function induced by alg is partially increasing, then there is a singleton

acyclic mechanism that is weakly group-strategyproof and ρ-budget balanced.

Truthfulness and Budget Balance. A singleton offer function τcombined

with an approximation algorithm alg whose cost function is partially increasing

with respect to τgive rise to the following natural cost sharing method. Note

that the partial increase property ensures that the cost shares are non-negative.

Definition 3. The cost sharing method ξinduced by alg and a singleton offer

function τis defined as ξi(S) := ¯

C(Si)−¯

C(Si−1)for every S⊆Uand i∈S.

Together with Theorem 1, the following lemma proves Theorem 2.

Lemma 1. Let τbe a singleton offer function and alg be a ρ-approximate

algorithm that is partially increasing with respect to τ. Moreover, let ξbe the

cost sharing method induced by alg and τ. Then the following holds:

1. ξis ρ-budget balanced.

2. If τis consistent, then τis valid for ξ.

Proof. By definition of ξ, we have Pi∈Sξi(S) = Pi∈S(¯

C(Si)−¯

C(Si−1)) =

C(S)−¯

C(∅) = ¯

C(S) for all S⊆U, proving that ξis ρ-budget balanced.

We next show that τis valid for ξ. Fix S⊆Uand i∈S. Since τis a singleton

offer function, E(i, S)\{i}=∅, and so (P2) of Definition 1 reduces to (P1). To

prove (P1), let P:= S\Tfor some subset T⊆G(i, S) and consider the ordered

sets S=: {i1, i2, . . . , iq}and P=: {j1, j2, . . . , jp}. Let kbe minimal with ik/∈P.

Then, by Definition 2, for all l < k,il=jland hence Pl=Sl. Since T⊆G(i, S),

we have τ(i, S)< τ(ik, S). We conclude that ξi(P) = ¯

C(Pi)−¯

C(Pi−1) = ¯

C(Si)−

C(Si−1) = ξi(S). ut

From now on, for a consistent singleton offer function τand an approxima-

tion algorithm alg whose cost function is partially increasing with respect to τ,

we call the mechanism M:= M(ξ, τ) the singleton mechanism induced by alg

and τ. Given an approximation algorithm alg, we remark that the budget bal-

ance factor of Mis independent of the consistent singleton offer function used.

However, the choice of the singleton offer function may very well influence the

social cost of the solution output by the mechanism. Hence, if the cost function

induced by alg is increasing, i.e., C(T)≤C(S) for all T⊆S⊆U, we can

choose τsolely to achieve a good social cost approximation factor. If not, the no

positive transfer property restricts the choice of τto offer functions with respect

to which ¯

Cis partially increasing.

Social Cost. The social cost analysis of singleton mechanisms can be alleviated

if the induced cost sharing method has the following property:

Definition 4. Let ξbe the cost sharing method induced by alg and τ. We call ξ

weakly monotone if for all subsets T⊆S⊆U,Pi∈Tξi(S)≥¯

C(T).

Theorem 3. Let M=M(ξ, τ)be the singleton mechanism induced by alg and

a consistent singleton offer function τ. Suppose that ξis weakly monotone. Then,

Mapproximates social cost by a factor of αif

C(SM∪S∗)

C(S∗) + C(SM\S∗)≤α.

Proof. We need to upper bound the ratio between the social cost of the set SM

chosen by the mechanism and a set S∗:= arg minS⊆U(C(S)+Pi/∈Svi). We have

Π(SM)

Π∗=

C(SM) + Pi∈S∗\SMvi+Pi/∈SM∪S∗vi

C(S∗) + Pi∈SM\S∗vi+Pi/∈SM∪S∗vi≤

C(SM) + Pi∈S∗\SMvi

C(S∗) + Pi∈SM\S∗vi

≤

C(SM) + Pi∈S∗\SMvi

C(S∗) + Pi∈SM\S∗ξi(SM)≤

C(SM) + Pi∈S∗\SMvi

C(S∗) + C(SM\S∗).

Here, the first inequality follows from Fact 1 below. The second inequality holds

because vi≥ξi(SM) for every player i∈SM. The last inequality follows from

weak monotonicity of ξand the fact that ¯

C(S)≥C(S) for every set S.

Without loss of generality, number the players in S∗\SMin the order in

which they were rejected in the course of the mechanism M, i.e., S∗\SM=:

{1, . . . , `}. For every i∈S∗\SM, let Ribe the subset of players in S∗∪SM

that were remaining in the iteration in which iwas removed, i.e., Ri:= SM∪

{i, i + 1, . . . , `}.Since irejected, we have vi< ξi(Ri). Moreover, by definition

of the sets Riand weak monotonicity of ξ, we obtain ¯

C(Ri) = Pj∈Riξj(Ri) =

ξi(Ri) + Pj∈Ri+1 ξj(Ri)≥ξi(Ri) + ¯

C(Ri+1).Summing over all i∈ {1, . . . , `}

yields

i∈S∗\SM

vi≤

i=1 ¯

C(Ri)−¯

C(Ri+1)=¯

C(SM∪S∗)−¯

C(SM).

The proof of Theorem 3 uses the following fact, which we state without proof.

Fact 1 For arbitrary real numbers a≥b > c > 0, we have a

b≤a−c

b−c.

4 Completion Time Scheduling

In this section, we study the performance of singleton mechanisms for total

completion time objectives. We distinguish between the model with weights, in

which all jobs arrive at time zero and no preemption is allowed, and the model

in which jobs have release dates and may be preempted.

4.1 Weighted Completion Time

We consider the problem P||PwiCiof scheduling a set of jobs U:= [n] non-

preemptively on mparallel machines such that the total weighted completion

time is minimized. Even for the unweighted version, i.e. when wi≡1, no Moulin

mechanism can achieve a budget balance factor better than n/2 [2]. However,

using singleton acyclic mechanisms, we can heavily improve upon this.

Let ρgr denote the approximation guarantee achieved by Graham’s rule,

i.e., ordering the jobs by non-increasing weight per processing time wi/pi. For

P||PwiCi, the produced schedule is (1 + √2)/2≈1.21-approximate, which is

best possible [10]. In the case of one machine, ρgr = 1. In the unweighted setting,

Graham’s rule reduces to the shortest processing time policy and also delivers

an optimal schedule.

Let Mwct := M(ξ, τ) be the singleton mechanism induced by Graham’s rule

and the offer function τdefined as follows:

Singleton offer function for Graham’s rule: Let σbe a non-increasing

weight per processing time order on U. If two jobs i, j ∈Usatisfy wi/pi=

wj/pj, we define σ(i)< σ(j) iff i<j. For every subset S⊆U, let τ(·, S) be

the order on Sinduced by σ.

One easily verifies that τis a consistent singleton offer function. We have ξi(S) =

C(Si)−¯

C(Si−1) = wiCi(S), where Ci(S) is the completion time of job iin the

schedule computed by Graham’s rule. Since wiCi(S)≥0, Graham’s rule is

obviously partially increasing with respect to τ.

Theorem 4. The singleton mechanism Mwct =M(ξ, τ)induced by Graham’s

rule and τis weakly group-strategyproof, ρgr-budget balanced and approximates

social cost by a factor of 2ρgr.

Proof. It follows from Theorem 2 that Mwct is weakly group-strategyproof and

ρgr-budget balanced. It remains to be shown that Mwct is 2ρgr-approximate with

respect to social cost. To see that the induced cost sharing method ξis weakly

monotone, note that Ci(S)≥Ci(T) for every i∈T⊆S. Thus, Pi∈Tξi(S)≥

Pi∈Tξi(T) = ¯

C(T).The social cost approximation factor now follows from

Theorem 3 and Lemma 2 given below. ut

Lemma 2. Let alg be an algorithm for P||PwiCiwith cost function ¯

C. Let

Aand Bbe two disjoint sets of jobs. Then, the cost of an optimal schedule for

A∪Bcan be bounded by C(A∪B)≤2·¯

C(A) + ¯

C(B).

Proof. We prove the inequality individually for each machine ˆ

M. Consider the

jobs ˆ

A⊆Aand ˆ

B⊆Bscheduled on ˆ

Min the runs of alg on Aand B,

respectively. We denote by cithe completion time of job iin his respective

schedule, i.e. ci:= ¯

Ci(A) for all i∈ˆ

Aand ci:= ¯

Ci(B) for all i∈ˆ

Consider the schedule which processes all jobs in ˆ

A∪ˆ

Bon ˆ

Maccording to

non-decreasing ci. The completion time of a job i∈ˆ

Ain this schedule is ci+ci∗,

where i∗denotes the last job in ˆ

Bthat is processed before i. Since i∗is processed

before i, we have ci+ci∗≤2ci.By exchanging the roles of Aand B, we can

show the same for the completion time of every job i∈ˆ

Since the cost of an optimal schedule for A∪Bis at most that of the schedule

produced by repeating the above procedure for each machine, we have

C(A∪B)≤X

i∈A∪B

wi·2ci= 2 ·X

i∈A

wici+X

i∈B

wici= 2 ·¯

C(A) + ¯

C(B).

The following example shows that our social cost analysis is tight.

Example 1. Consider an instance of 1|pi= 1|PCion an even number of n

jobs with valuations vi=ifor all i∈[n]. Assume that Mwct orders the jobs

according to increasing valuations (we can always enforce this by perturbing

the processing times appropriately) and thus accepts all jobs. Then, Π(SM) =

C([n]) = n(n+1)/2.. However, if we exclude the first n/2 jobs from the scheduled

set, we obtain a social cost of C([n

2])+Pn/2

i=1 vi=n(n

2+1)/2 = n(n+2)/4≥Π∗,

yielding an approximation ratio of essentially 2.

The following theorem comes directly with the proof of Theorem 4 if we

identify the players’ valuations with the penalties for not scheduling a job.

Theorem 5. Graham’s rule is a 2ρgr-approximate algorithm for the weighted

completion time scheduling problem with rejection.

4.2 Completion Time with Release Dates and Preemption

Now, consider the problem 1|ri,pmtn|PCiof scheduling a set of jobs U:= [n]

on a single machine such that the total completion time is minimized. Each job

i∈Uhas a non-negative release date ri, and preemption of jobs is allowed. The

shortest remaining processing time policy (srpt) delivers an optimal schedule

for this problem [17].

We introduce some more notation in order to give a formal definition of srpt.

Let ei(t) be the amount of time that has been spent on processing job iup to

time t. The remaining processing time xi(t) of job iat time tis xi(t) := pi−ei(t).

We call a job iactive at time tif it has been released but not yet completed at

this time, i.e., ri≤t<Ci. Let A(t) be the set of jobs that are active at time t.

srpt works as follows: At any time t≥0, srpt schedules an active job i∈A(t)

with minimum remaining processing time, i.e. xi(t)≤xk(t) for all k∈A(t). In

the following, we assume that srpt uses a consistent tie breaking rule, e.g., if

xi(t) = xk(t) for two different jobs iand k, then schedule the one with smaller

index. Throughout this section, let Ci(S) := Csrpt

i(S) for all S⊆U.

Let Mpct := M(ξ, τ) be the singleton mechanism induced by srpt and the

following singleton offer function τ:

Singleton offer function for srpt:For a given subset S⊆U, let τ(·, S) be

the order induced by increasing completion times of the jobs in S, i.e.,

τ(i, S)< τ(j, S) iff Ci(S)< Cj(S).

The offer function τis consistent; we defer the proof to the end of this section.

Recall that srpt is an optimal scheduling policy and thus ¯

C(S) = C(S). We thus

have ξi(S) = C(Si)−C(Si−1) = Ci(S), where the latter follows from Lemma 5.

Remark that srpt is partially increasing with respect to τbecause Ci(S)≥0.

Theorem 6. The singleton mechanism Mpct =M(ξ, τ)induced by srpt and τ

is weakly group-strategyproof, budget balanced and approximates social cost by a

factor of 4.

Proof. It follows from Theorem 2 that Mpct is weakly group-strategyproof and

budget balanced. To prove that Mpct approximates social cost, we first show that

ξis weakly monotone. Fix some set Sand let T⊆S. Consider the srpt schedule

for S. If we remove from this schedule all jobs in S\T, we obtain a feasible

schedule for Tof cost at most Pi∈S\TCi(S)≥C(T). Since ξi(S) = Ci(S), we

have weak monotonicity. Now, the bound on the social cost approximation factor

follows from Theorem 3, using Lemma 3 given below. ut

The following lemma is used to prove the social cost approximation factor.

Lemma 3. Let alg be an algorithm for P|ri,pmtn|PCiwith cost function ¯

Let Aand Bbe two disjoint sets of jobs. Then, the cost of an optimal schedule

for A∪Bcan be bounded by C(A∪B)≤4·¯

C(A) + ¯

C(B).

Proof. Phillips et al. [14] prove that any preemptive schedule for P|ri,pmtn|PCi

can be turned into a non-preemptive schedule np with at most twice the cost.

With Lemma 2, we obtain C(A∪B)≤2·Cnp(A)+Cnp(B)≤4·¯

C(A)+ ¯

C(B).

Consistency. In order to prove that τis consistent, we need some more nota-

tion. Consider the srpt schedule for a set S⊆U. Let i, j ∈A(t) be two jobs

that are active at time t. We define i≺tjiff either xi(t)< xj(t) or xi(t) = xj(t)

and i≤j. Note that at any point of time t,srpt schedules the job i∈A(t) with

i≺tjfor all j∈A(t). Thus, if i≺tjfor some t, then i≺t0jfor all t0∈[t, Ci).

We therefore simply write i≺jiff there exists a time twith i≺tj. Let σ(t)

denote the job that is executed at time tin the srpt schedule for S; we define

σ(t) = ∅if A(t) = ∅.

Let j∈Sbe an arbitrary job and consider the time interval [rj, Cj). We

define the set Cjof jobs that are competing with jas

Cj:= {i∈S\{j}: [ri, Ci)∩[rj, Cj)6=∅}.

Note that j /∈ Cj. We partition the jobs in Cjinto a set Wjof winning jobs and a

set Ljof losing jobs with respect to j:Wj:= {i∈ Cj:i≺j}and Lj:= Cj\Wj.

Intuitively, suppose iand jare both active at some time t. If iis a winning

job, then iprevents jfrom being executed by srpt. On the other hand, if iis a

losing job, then jprevents ifrom being executed.

We next investigate the effect of removing a job jfrom S. We use the super-

script Tif we refer to the srpt schedule for T:= S\{j}.

Lemma 4. Consider the two srpt schedules on job sets Sand T:= S\ {j}.

For every job i∈ Cjthat is active at time t∈[rj, Cj),

i(t) = xi(t)if i∈ Wjand xT

i(t)≥xj(t)if i∈ Lj.

Proof. We partition the time interval [rj, Cj) into a sequence of maximal subin-

tervals I1, I2, . . . , Ifsuch that the set of active jobs remains constant within

every subinterval I`:= [s`, e`). We prove by induction over `that the claim

holds for every t∈[rj, e`).

Note that both schedules are identical up to time rj=s1. If σ(s1)6=j, then

both schedules process the same job during I1and the claim follows. Suppose

σ(s1) = j. This implies that A(s1)∩Wj=∅and thus all jobs in A(s1)\{j}=

AT(s1) are losing jobs. If AT(s1) = ∅, the claim follows. Otherwise, let k:=

σT(s1) be the job that is processed in the schedule for T. Since kis a losing job,

we have xT

k(s1) = xk(s1)≥xj(s1). Since kand jreceive the same processing

time during I1in their respective schedules, the claim holds for all t∈[rj, e1).

Now, assume that the claim is true for every t∈[rj, e`−1) for some ` > 1.

We show that it remains true during the time interval I`. By the induction

hypothesis, xT

i(t) = xi(t) for every job i∈ Wjthat is active at time t∈[rj, e`−1).

This implies that a job j∈ Wiis executed at time t∈[rj, e`−1) in the schedule

for Siff it is executed at time tin the schedule for T. We thus have AT(s`)∩Wj=

A(s`)∩Wj. Moreover, xT

i(t)≥xj(t) for every job i∈ Ljthat is active at time

t∈[rj, e`−1). Since xj(t)>0 for every t∈[rj, Cj), every job i∈ Ljthat is

active at time t∈[rj, e`−1) in the schedule for Smust also be active at time t

in the schedule for T. Thus, AT(s`)∩Lj=A(s`)∩Lj. We now distinguish two

cases:

(i) First, assume σ(s`) =: k∈ Wj. Job kthen has smallest remaining pro-

cessing time, i.e., xk(s`)≤xi(s`) for all i∈A(s`). We conclude that

k(s`) = xk(s`)≤xi(s`) = xT

i(s`)∀i∈A(s`)∩Wj=AT(s`)∩Wj

k(s`) = xk(s`)≤xj(s`)≤xT

i(s`)∀i∈A(s`)∩Lj=AT(s`)∩Lj.

Since we assume that srpt uses a consistent tie breaking rule, this implies that

σT(s`) = kand the claim follows.

(ii) Now, suppose σ(s`) = j. (Note that σ(s`)∈ Ljis impossible.) Then

xj(s`)≤xi(s`) for every i∈A(s`) and A(s`)∩ Wj=∅. But then we also

have AT(s`)∩Wj=∅and thus AT(s`)⊆ Lj. If AT(s`) = ∅, the claim follows.

Otherwise, let k:= σT(s`)∈ Ljbe the job that is executed at time s`in the

schedule for T. Since xT

k(s`)≥xj(s`) and the remaining processing times of k

and jin their respective schedules reduce by the same amount during I`, the

claim follows. ut

Lemma 5. Let T⊆S⊆Uand consider the srpt schedule for S\T. We have:

1. Ci(S\T) = Ci(S)for every job i∈S\Twith Ci(S)< Cj(S)for all j∈T.

2. C`(S\T)≥minj∈TCj(S)for every job `∈S\Twith C`(S)> Cj(S)for

some j∈T.

Proof. Consider the srpt schedule for Sand fix two jobs i, ` ∈S\Tsuch that

ifulfills Ci(S)< Cj(S) for all j∈T, and `does not. Let jbe the job in Twith

largest completion time among all jobs in T. Remove jfrom Sand consider the

resulting srpt schedule for S\{j}.

By Lemma 4, the completion times of iand all jobs in T\{j}in this schedule

remain the same, since none of these jobs lose against jby choice of j. We can

repeat this argument until all jobs in Tare removed from S.

Now, consider the completion time of job `during the same procedure. As

long as Cj(S)> C`(S) for the job jthat is currently removed, the completion

time of `remains equal. As soon as a job jwith Cj(S)< C`(S) is removed, the

completion time of `may change, but, again by Lemma 4, it stays greater or

equal to Cj(S). Hence, we have C`(S\T)≥minj∈TCj(S). ut

Lemma 6. The singleton offer function τis consistent.

Proof. Consider two sets P⊆S⊆U, ordered by τas P=: {j1, j2, . . . , jp}and

S=: {i1, i2, . . . , iq}. Let kbe minimal with ik/∈P. Then, for all l < k, we

have il∈Pby minimality of k, and Cil(S)< Cik(S) by definition of τ. Also by

minimality of k, for all other i /∈P, we have Cil(S)< Cik(S)< Ci(S). Hence,

Lemma 5 proves that Cil(S) = Cil(P) for all l < k.

For all other jobs j∈P, we have Cj(S)> Ck(S) and thus by Lemma 5,

Cj(P)≥Ck(S)> Ck−1(S) = Ck−1(P). Hence, we have il=jlfor all l < k.ut

Treating the players’ valuations as penalties for not scheduling a job gives

the following theorem.

Theorem 7. srpt is a 4-approximate algorithm for the completion time schedul-

ing problem 1|ri,pmtn|PCiwith rejection.

References

1. Y. Bleischwitz and B. Monien. Fair cost-sharing methods for scheduling jobs on

parallel machines. In Proc. of the 6th Int. Conf. on Algorithms and Complexity,

volume 3998 of Lecture Notes in Comput. Sci., pages 175–186. Springer, 2006.

2. J. Brenner and G. Sch¨afer. Cost sharing methods for makespan and completion

time scheduling. In Proc. of the 24th Int. Sympos. on Theoretical Aspects of Com-

puter Science, pages 670–681, 2007.

3. P. Brucker. Scheduling Algorithms. Springer, New York, USA, 1998.

4. S. Chawla, T. Roughgarden, and M. Sundararajan. Optimal cost-sharing mecha-

nisms for Steiner forest problems. In Proc. of the 2nd Int. Workshop on Internet

and Network Economics, pages 112–123. Springer, 2006.

5. N. Devanur, M. Mihail, and V. Vazirani. Strategyproof cost-sharing mechanisms

for set cover and facility location games. In Proc. of the ACM Conference on

Electronic Commerce. ACM Press, 2003.

6. J. Du, J. Y. T. Leung, and G. H. Young. Minimizing mean flow time with release

time constraint. Theoretical Computer Science, 75(3):347–355, 1990.

7. R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on

Applied Mathematics, 17(2):416–429, 1969.

8. A. Gupta, J. K¨onemann, S. Leonardi, R. Ravi, and G. Sch¨afer. An efficient cost-

sharing mechanism for the prize-collecting Steiner forest problem. In Proc. of the

18th ACM-SIAM Sympos. on Discrete Algorithms. ACM Press, 2007.

9. N. Immorlica, M. Mahdian, and V. S. Mirrokni. Limitations of cross-monotonic cost

sharing schemes. In Proc. of the16th ACM-SIAM Sympos. on Discrete Algorithms,

pages 602–611. ACM Press, 2005.

10. T. Kawaguchi and S. Kyan. Worst case bound of an LRF schedule for the mean

weighted flow time problem. SIAM Journal on Computing, 15(4):1119–1129, 1986.

11. J. K¨onemann, S. Leonardi, G. Sch¨afer, and S. van Zwam. From primal-dual to

cost shares and back: a stronger LP relaxation for the Steiner forest problem. In

Automata, Languages and Programming, volume 3580 of Lecture Notes in Com-

put. Sci., pages 930–942. Springer, 2005.

12. A. Mehta, T. Roughgarden, and M. Sundararajan. Beyond Moulin mechanisms.

In Proc. of the ACM Conference on Electronic Commerce, 2007.

13. H. Moulin. Incremental cost sharing: Characterization by coalition strategy-

proofness. Social Choice and Welfare, 16:279–320, 1999.

14. C. Phillips, C. Stein, and J. Wein. Minimizing average completion time in the

presence of release dates. Math. Program., 82:199 – 223, 1998.

15. T. Roughgarden and M. Sundararajan. New trade-offs in cost-sharing mechanisms.

In Proc. of the 38th ACM Sympos. on Theory of Computing, pages 79–88, 2006.

16. T. Roughgarden and M. Sundararajan. Approximately efficient cost-sharing mech-

anisms. arXiv report, http://www.arxiv.org/pdf/cs.GT/0606127, June 2006.

17. L. Schrage. A proof of the optimality of the shortest remaining processing time

discipline. Operations Research, 16:687 – 690, 1968.