Efficient Mechanism Design for Online Scheduling (Extended Abstract)

1 Introduction

Online scheduling has been widely studied in the literature [Baruah et al., 1992; 1994; Porter, 2004; Zheng et al., 2006; Ting, 2008], where each job is characterized by a release time, a deadline, a length, and a value for its successful completion by the deadline. Inspired by emerging areas like computational economics and cloud computing [Azar et al., 2013; Lucier et al., 2013; Mashayekhy et al., 2014; Wu et al., 2014], we consider a strategic setting of the online scheduling problem, where each job is owned by a selfinterested agent and she may have the incentive to manipulate the scheduling algorithm in order to be better off [Friedman and Parkes, 2003; Porter, 2004; Hajiaghayi et al., 2005; Parkes, 2007]. To be specific, the agent may deliberately delay the release time of her job, inflate its length, and misreport its value and deadline.

∗This paper is an extended abstract of an article in the Journal of Artificial Intelligence Research [Chen et al., 2016]

Given this situation, a carefully designed online scheduling mechanism is needed to regulate the strategic behaviors of the agents and to (approximately) optimize some system objectives. In this work, we focus on the maximization of social welfare, i.e., the total value of completed jobs. We use competitive analysis [Lavi and Nisan, 2004] to evaluate the performance of such a mechanism, which compares the social welfare implemented by the mechanism (without any knowledge of all future jobs) with that of the optimal offline allocation (with the knowledge of future jobs).

In this work, we consider two scheduling models: the preemption-restart model [Ting, 2008] and the preemptionresume model [Porter, 2004]. Once preempted, jobs in the first model have to restart from the beginning; while jobs in the second model can resume from the break point. Since preemption is always assumed in this work, the two models are also referred to as restart model and resume model, respectively, and their involved jobs are called non-resumable and resumable, respectively.

1.1 ProblemFormulation

We consider online scheduling models with infinite time period T = R≥0. Suppose there is a single machine that processes at most one job at any given time. Jobs come over time, and we use J to denote the set of jobs. Each job j ∈ J is owned by a self-interested agent (which is also denoted as j for simplicity); and it is characterized by a private type θj = (rj, dj, lj, vj) ∈ T × T × R>0 × R>0, where rj is the release time, dj is the deadline, lj is the length (i.e., the processing time), and vj is the value if the job is completed by its deadline.

A resumable job j is completed if and only if it is processed for lj time units in total between its release time rj and deadline dj, while a non-resumable job j is completed if and only if it is processed for lj consecutive time units between its release time rj and deadline dj.

Let κ = maxi,j∈J li lj be the maximum ratio between the lengths of any two jobs. For simplicity, we assume all job lengths are normalized, i.e., lj ∈ [1, κ] for all j ∈ J, and assume κ is known in advance following the practice in the work of Chan et al. (2004) and Ting (2008).

We study direct revelation mechanisms, in which each agent participates by simply declaring the type of her job ˆ θj = (ˆ rj, ˆ dj , ˆlj , ˆ vj) at time ˆ rj. We use ˆ θ to denote the profile of reported types of all the agents. Given the declared types of the agents, a mechanismM is used to schedule/allocate the jobs and determine the payment of each agent. Here we only consider "reasonable" mechanisms which (1) do not schedule a job after its reported deadline and (2) do not schedule a job once it has been processed for a reported length.

Given a certain mechanism M and a job sequence ˆ θ, we use qj(ˆ θ, t) to denote whether job j is completed by time t (if it is completed, qj(ˆ θ, t) = 1; otherwise qj(ˆ θ, t) = 0). Then the value that agent j extracts from the mechanism can be represented by qj(ˆ θ, dj)vj, and the social welfare of the mechanism can be represented by W(M, θ) = ∑j qj(ˆ θ, dj )vj .

Let pj(ˆ θ) denote the amount of money that the mechanism charges agent j. We assume that agents have quasi-linear preferences [Nisan, 2007], i.e., the utility of agent j is uj ( ˆ θ, θj ) = qj (ˆ θ, dj)vj - pj(ˆ θ).

Since agents are self-interested, they may misreport their types in a strategic way. It is easy to see that the misreport of a shorter length is a dominated strategy; otherwise, her job cannot be completed even if it is scheduled by the mechanism (since ˆlj < lj). Therefore, the agents will not underreport the lengths of their jobs. Similar to the work of Porter (2004), we assume that the system will not return a completed job to agent j until ˆ dj. In this way, we restrict the agent's report to be ˆ dj ≤ dj. In addition, we assume that no agent has knowledge about her job before its release time, so we also have ˆ rj ≥ rj.

Considering the potential misreport of the agents, we are concerned with incentive compatible and individually rational mechanisms. A mechanism is incentive compatible (IC) if, for any agent j, regardless of the behaviors of other agents, truthful reporting her own type maximizes her utility. A mechanism is individually rational (IR) if for each job j, truthful reporting leads to a non-negative utility. In addition, we would also like the mechanism to (approximately) maximize social welfare. We say a mechanism M is (strictly) c-competitive if there does not exist any job sequence θ such that c · W(M, θ) < W(opt, θ), where opt denotes the optimal offline mechanism. Sometimes we also say that M has a competitive ratio of c.

1.2 Our Results

For the restart and resume model, we first give the lower bounds of the competitive ratio for any online IC mechanism is 5 when κ = 1 and κ lnκ + 1 - o(1) when κ is big. Then we design a simple IC mechanism that have very good performances with respect to the competitive ratios. For the restart model, our mechanism has a competitive ratio of κ+2+(1+ 1κ )κ when κ is small, and ( 1 (1-ϵ)2 +o(1)) · κ ln κ

when κ is large, where 0 < ϵ < 1 is a small constant. For the resume model, our model has a competitive ratio of (κ+ 1)(1 + 1κ )κ + 1 when κ is small, and ( 2 (1-ϵ)2 + o(1)) · κ lnκ when κ is large. Comparing to the lower bounds, the competitive ratios we obtained about our mechanism show that our mechanism is nearly the best possible.

2 Lower bounds

In this section, we give the lower bounds of the competitive ratio for any online IC mechanism of this problem. Detailed proofs can be found in the full version [Chen et al., 2016].

Theorem 2.1. When κ = 1, no deterministic IC mechanism can obtain a competitive ratio less than 5.

Theorem 2.2. When κ is sufficiently large, no deterministic ICmechanism can obtain a competitive ratio less than κ ln κ + 1 - o(1). In particular, no deterministic IC mechanism can obtain a competitive ratio less than κ ln κ + 0.94 for κ ≥ 16.

3 MechanismDesign

In this section, we describe a simple mechanism Γ1 (whose allocation and payment rules are given in Algorithm 1), which works surprisingly well for both the restart and resume models, and handles the settings with different values of κ in a unified framework. In contrast, previous works [D¨urr et al., 2012] need to design separate and very different algorithms to deal with different values of κ.

3.1 The MechanismΓ1

Before introducing our mechanism, we first introduce the concept of the valid active time of an uncompleted job j, until time t, denoted as

(1)

where x(t) is the mechanism's allocation function, which maps each time point to an available job, or to 0 if the machine is idle. And µ(·) is an indicator function that returns 1 if the argument is true, and zero otherwise. Note that ej(·) can also take a vector θ as an argument. For example, ej(θ, t) is shorthand for the ej(t) for the job sequence θ.

It can be seen that in the restart model, at time t, if a job j has received an allocation at time t′ < t and has not been preempted after that, then ej(t) = t-t′ . In the resume model, ej(t) is the accumulated processing time of job j until time t.

We say that a job j is feasible at time t if (1) its reported release time is before t; (2) it has not been completed yet; and (3) it has enough time to be completed before its reported deadline, i.e., ˆ dj -t ≥ ˆlj -ej(t). We use JF (t) to denote the set of all feasible jobs at time t.

According to Algorithm 1, at any time t, Γ1 assigns a priority score, ˆ vj · βˆlj-ej(ˆ θ,t) , to each feasible job j ∈ JF (t), and always processes the feasible job with the highest priority (ties are broken in favor of the job with the smaller ˆ rj). Here β is located in (0, 1) and will be determined later during the competitive analysis. The payment rule of Γ1 is essentially the critical-value payment [Parkes, 2007], which is similar to that of the second-price auction. Hence, the payment is equal to the minimum bid the agents have to make to remain allocated. In the following pseudocode, ˆ θ-j denotes the reported types of all jobs other than j.

Algorithm 1:

Allocation Rule: for all time t do if JF (t) ̸= ∅ then x(t) ← arg maxj∈JF (t)(ˆ vj · βˆlj-ej(ˆ θ,t) ) elsex(t) ← 0 end Payment Rule: for all job j do if qj(ˆ θ, ˆ dj) = 1 then pj ( ˆ θ) = min(v′j |qj (((ˆ rj, ˆ dj, ˆlj, v′j ), ˆ θ-j), ˆ dj ) = 1) elsepj ( ˆ θ) = 0 end

4 Competitive Analysis

In this section, we show that mechanism Γ1 performs quite well in terms of social welfare by comparison with the optimal offline allocation, which has full knowledge of the future jobs at the beginning of the execution.

To perform the competitive analysis, we need to design virtual charging schemes. Under a certain virtual charging scheme, for every job j completed by the optimal allocation opt, we charge its value (or partial value) to some job f completed by Γ1. If this virtual charging scheme satisfies the property that every job f completed by Γ1 receives a total charge of at most cvf , then we succeed in showing that Γ1 has a competitive ratio of at most c. Designing an ingenious virtual charging scheme is crucial to the competitive analysis. In the following, we will design different virtual charging schemes to obtain the competitive ratio of Γ1 for the restart model and the resume model respectively.

As we use a parameter β in the priority function of mechanism Γ1, we first derive competitive ratios as functions of β. We will specify later (in Section 4.3) how to choose a suitable β (with respect to κ) to optimize the performance of Γ1, and derive competitive ratios in terms of κ.

Here, we introduce some notation which will be used in both Section 4.1 and Section 4.2. Denote by (1, 2, . . . , F ) the sequence of jobs completed by Γ1 over time. For each job f in this sequence, let tf be the time when job f is completed, and for convenience denote t0 = 0. Divide the time into F+1 intervals If = [tf-1, tf ), f = 1, 2, . . . , F , and [tF , +∞).

4.1 Analysis of the Restart Model

We study the restart model first. We assume, without loss of generality, that the optimal allocation opt does not interrupt any allocation, since all interrupted jobs are non-resumable. We have the following theorem.

Theorem 4.1. For the restart model, Γ1 has a competitive ratio of 1 1-β + 1 βκ + 1.

Proof. We introduce the virtual charging scheme as follows. For any completed job j in opt, if it is also completed in mechanism Γ1, then its value is charged to itself.

Otherwise (i.e., job j is not completed by Γ1), we consider the time sj at which j begins execution in opt. Note that opt does not interrupt any allocation, so j is exactly allocated to the time period [sj, sj + lj). Then sj must be in some time interval If (recall If = [tf-1, tf)), and we charge the value of j to f. Define σj := tf - sj to be the time amount between sj and tf . As job j is feasible at time sj, according to Lemma 4.2, we know that the priority jobs j at time sj is at most vfβtf-sj = vfβσj ; in the meanwhile, the priority of j at time sj is vjβlj . We have vjβlj ≤ vfβσj , i,e., vj ≤ vfβσj-lj . We defer the formal statement and the proof of Lemma 4.2 to the end of this subsection.

We now calculate the maximum total value charged to a completed job f in Γ1. In time interval If , denote by (1, 2, . . . ,m), the sequence of jobs in opt whose starting time sj belongs to If and ordered as s1 > s2 > · · · > sm. Remember that σj is the time amount between sj and tf . Then it is clear that we have 0 < σ1 < σ2 < · · · < σm and σj - lj ≥ σj-1 for 2 ≤ j ≤ m, since j is allocated and completed during time interval [sj, sj-1]. Furthermore, as the job lengths are normalized, i.e., 1 ≤ lj ≤ κ, we can deduce that:

Recall that β < 1 and f may also be completed in opt. Therefore the total charge to job f is at most vf + ∑mj=1 vj, which is upper bounded by

This shows that mechanismΓ1 is ( 1

1-β + 1 βκ +1)-competitive.

Actually, the competitive ratio obtained in this way is tight, i.e., the ratio 1 1-β + 1 βκ + 1 is best possible for Γ1. We give an example in the full version to show tightness.

Lemma 4.2. For any time point sj ∈ If , if job j (̸= f) is feasible at time sj, then the priority of j at sj is at most vfβtf-sj . Moreover, the value of j, vj, is at most vf βtf -sj-lj .

Proof. Note that, sj is in time interval If , and according to the definition of If , we know that f is the unique job that is completed in If by Γ1. Now we prove the lemma by enumerating all possible cases.

1. If the executing job at sj is job f, then we know that the priority of job f at time sj is exactly vfβtf-sj (because the priority of job f at time tf is vf ). Clearly, the priority of j at sj is not larger than that of job f, and thus not larger than vf βtf -sj .

(2) If the executing job at sj is not job f, then we assume that Γ1 executes job j1, . . . , jk and f successively 1 in the time period [sj, tf), where k ≥ 1. Since f is the unique job completed in If , we can deduce that: j1 is preempted by j2, j2 is preempted by j3,...,jk is preempted by f, and finally f is completed at time tf . Denote τ1, . . . , τk as the time points at which j1, . . . , jk are preempted respectively. We also denote fj(t) as the priority of job j at time t. We now use backward induction: First, we know that the priority of job jk at τk is not larger than that of job f, i.e., fjk (τk) ≤ vfβtf-τk . Then, since jk-1 is preempted by jk at τk-1, we know that the priority of jk-1 at τk-1 is not larger than that of jk. Hence, we have fjk-1 (τk-1) ≤ fjk (τk-1) = fjk (τk)βτk-τk-1 ≤ vfβtf-τk-1 . And eventually, we can get that fj1 (τ1) ≤ vfβtf-t1 . Since j1 is executed at time sj, we can deduce that fj1 (sj) ≤ vfβtf-sj . Clearly, the priority of j at time sj (i.e., vjβlj ) is not larger than that of j1, thus not larger than vfβtf-sj .

By arranging vjβlj-ej(sj) ≤ vfβtf-sj , we can get vj ≤ vfβtf-sj-lj+ej(sj) ≤ vfβtf-sj-lj , where ej(sj) ≥ 0 is the valid active time of job j at time sj.

Some remarks on Lemma 4.2: (1) Because f is the unique job completed by Γ1 in the time interval If , the priorities of the executing jobs monotonically increase during If . (2) Lemma 4.2 applies in both the restart model and resume model. (3) Lemma 4.2 provides a useful tool to relate the priority of a feasible job (j) at some time point (sj ∈ If ) to the completed job f.

4.2 Analysis of the Resume Model

Compared with the restart model, the competitive analysis for the resume model is much more complicated, because in the resume model, a job can be executed in several disjointed time intervals.

To analyze the competitive ratio of Γ1 for the resume model, we propose two new virtual charging schemes (referred to as integral charging scheme and segmental charging scheme, respectively). In the integral charging scheme, we charge the whole value of job j in the optimal allocation opt to some job completed by mechanism Γ1; while in the segmental charging scheme, we charge the value of j by segment, and different segments of the same job may be charged to different jobs completed by mechanism Γ1. By using these two schemes, in Theorem 4.3 we upper bound the competitive ratio of mechanism Γ1 by β-κ 1-β + 1 and 1 βκ + -2 β lnβ + 1 respectively. As discussed in Section 4.3, the two ratios work for situations with different κ values, i.e., the first one works well for small κ and the second one works well for large κ. The detailed information about the two charging schemes and its relevant proofs can be found in the full version of this work [Chen et al., 2016]. Here we just list the main theorem.

1 Here, j1 can be job j, which does not affect the analysis.

Theorem 4.3. For the resume model, the competitive ratio of Γ1 is at most β-κ 1-β + 1. In particular, if β satisfies κβκ ≥ β, the competitive ratio of Γ1 is at most min{ β-κ 1-β + 1, 1 βκ + -2 β ln β + 1}.

4.3 Discussions

An advantage of our mechanism is that it can handle the settings with different values of κ in a unified framework. We only need to set parameter β to different values in Theorem 4.1 and Theorem 4.3 so as to adapt to different settings of job lengths (as shown in the following corollaries).

Corollary 4.4. By setting β = 1 - (1 - ϵ)2 · lnκ κ , where ϵ > 0 is an arbitrary small constant, mechanism Γ1 achieves a competitive ratio ( 1 (1-ϵ)2 +o(1)) · κ lnκ for the restart model and a competitive ratio ( 2 (1-ϵ)2 + o(1)) · κ lnκ for the resume model.

As for Corollary 4.4, we have the following discussions:

1. For the restart model, mechanism Γ1 achieves a competitive ratio of ( 1 (1-ϵ)2 +o(1)) · κ ln κ , which improves upon the best-known algorithmic result 6κ log κ + O(κ 56 ) [Ting, 2008] for the standard online scheduling without strategic behavior.
2. For the resume model, when κ is large, mechanism Γ1 achieves a competitive ratio of ( 2 (1-ϵ)2 + o(1)) · κ ln κ , which is slightly worse than the result obtained for the restart model (within a factor of 2). Asymptotically speaking, Γ1 is near optimal, since its competitive ratio has the same order (w.r.t. κ) as the lower bound shown in Theorem 2.2. Furthermore, our analysis generalizes the results obtained by Durr et al. (2012) to the continuous value of time and the strategic setting.
3. When κ is relatively small, the ratios given in Corollary 4.4 will become loose. In particular, when κ approaches 1, the above ratios will approach infinity since lnκ approaches 0. In this case, we need a different setting of β (see Corollary 4.5).

Corollary 4.5. By choosing β = κ κ+1 , the competitive ratio of mechanism Γ1 is κ + 2 + (1 + 1κ )κ < κ + 2 + e for the restart model and (κ+1)(1+ 1κ )κ +1 for the resume model.

Similarly, we have the following discussions:

1. The competitive ratio of Γ1 is linear in κ, since (1+ 1κ )κ is bounded by e.
2. In particular, when κ = 1, the ratios in the above corollary become 5 for both the restart and resume model, which matches the lower bound given in Theorem 2.1. In this regard, we say that Γ1 is optimal. On the other hand, this also shows that the lower bound of 5 in Theorem 2.1 is tight.