Well-behaved online load balancing against strategic jobs

Abstract

In the online load balancing problem on related machines, we have a set of jobs (with different sizes) arriving online, and the task is to assign each job to a machine immediately upon its arrival, so as to minimize the makespan, i.e., the maximum completion time. In classic mechanism design problems, we assume that the jobs are controlled by selfish agents, with the sizes being their private information. Each job (agent) aims at minimizing its own cost, which is its completion time plus the payment charged by the mechanism. Truthful mechanisms guaranteeing that every job minimizes its cost by reporting its true size have been well studied (Aspnes et al. JACM 44(3):486–504, 1997, Feldman et al. in: EC, 2017). In this paper, we study truthful online load balancing mechanisms that are well-behaved (machine with higher speed has larger workload). Good behavior is important as it guarantees fairness between machines and implies truthfulness in some cases when machines are controlled by selfish agents. Unfortunately, existing truthful online load balancing mechanisms are not well behaved. We first show that to guarantee producing a well-behaved schedule, any online algorithm (even non-truthful) has a competitive ratio at least $\varOmega (\sqrt{m})$, where m is the number of machines. Then, we propose a mechanism that guarantees truthfulness of the online jobs and produces a schedule that is almost well-behaved. We show that our algorithm has a competitive ratio of $O(\log m)$. Moreover, for the case when the sizes of online jobs are bounded, the competitive ratio of our algorithm improves to O(1). Interestingly, we show several cases for which our mechanism is actually truthful against selfish machines.

Appendices

Appendix

A An $O(\sqrt{m})$-competitive algorithm for well-behaved scheduling

In this section, we present a simple algorithm that always produces a well-behaved schedule whose makespan is $\textsf {ALG}= O(\sqrt{m})\cdot \textsf {OPT}$. Assume the machines are ordered by their speeds, i.e., $s_m \ge \ldots \ge s_1$. The algorithm works as follows.

Algorithm. For each online job j, we schedule j on the slowest machine $i < m$ satisfying $C_i(j) + \frac{p_j}{s_i} \le C_{i+1}(j)$. If there is no such machine, j is scheduled on machine m.

In other words, the algorithm schedules each online job to the slowest machine while maintaining the good behavior of the schedule at all time. Hence, it remains to prove the upper bound on the makespan of the schedule.

Lemma 10

We have $\textsf {ALG}\le 4\sqrt{m}\cdot \textsf {OPT}$.

Proof

Suppose otherwise, we have $C_m > 4\sqrt{m}\cdot \textsf {OPT}$. In the following, we show that for each machine i we have

$$\begin{aligned} C_i \ge C_m - 4(m-i)\cdot \textsf {OPT}. \end{aligned}$$

(4)

Note that given the above, we have

$$\begin{aligned} C_i > 4(\sqrt{m} - m + i)\cdot \textsf {OPT}\end{aligned}$$

for every machine i. Hence the total size of jobs is

$$\begin{aligned}&\sum _{i=1}^m C_i\cdot s_i> \ \sum _{i=m-\sqrt{m}+1}^m 4\cdot (\sqrt{m} - m + i)\cdot s_i\cdot \textsf {OPT}\\&\quad > \ \sum _{i=1}^m s_i \cdot \textsf {OPT}, \end{aligned}$$

where the second inequality follows from $s_m\ge \ldots \ge s_1$ and

$$\begin{aligned} \sum _{i=m-\sqrt{m}+1}^m 4\cdot (\sqrt{m} - m + i ) > m. \end{aligned}$$

However, the total workload any schedule can finish within time $\textsf {OPT}$ is upper bounded by $\sum _{i=1}^m s_i \cdot \textsf {OPT}$, which is a contradiction. It remains to prove Inequality (4).

Assume the contrary and let i be the maximum such that $C_i < C_m - 4(m-i)\cdot \textsf {OPT}$. Note that $i \ne m$ and for all $k > i$ we have $C_k \ge C_m - 4(m-k)\cdot \textsf {OPT}$. Similar to the proof of Lemma 4, we let $J'$ be the jobs that contribute to the last $2\cdot \textsf {OPT}$ increase in makespan on machines $\{ i+1,\ldots ,m \}$. Observe that the total size of the jobs in $J'$ is at least $2\cdot \textsf {OPT}\cdot \sum _{l = i+1}^m s_l$, which means that at least one of the jobs in $J'$, say job j, is processed on some machine in $\{ 1,2,\ldots ,i \}$ in the optimal schedule. Consequently, we have $p_j \le \textsf {OPT}\cdot s_i$. Furthermore, the processing time of job j on any machine in $\{ i,i+1,\ldots ,m \}$ is at most $\textsf {OPT}$.

Now consider the time when job j arrives. Recall that job j is scheduled on some machine $k > i$. Moreover, we have

$$\begin{aligned} C_k(j) > C_k - 3\cdot \textsf {OPT}\ge C_m - (4(m-k)+3)\cdot \textsf {OPT}. \end{aligned}$$

Since j is not scheduled on any of the machines $\{ i,i+1,\ldots ,k-1 \}$, we know that the difference in the makespans of any two consecutive machines in $\{ i,\ldots ,k \}$ is less than $\textsf {OPT}$. Therefore, we have

$$\begin{aligned} C_i&\ge C_i(j) > C_k - (k-i)\cdot \textsf {OPT}\\&\ge C_m - (4m-4k+3+ k-i)\cdot \textsf {OPT}\\&= C_m - (4m-4i +3(k-i+1))\cdot \textsf {OPT}\\&\ge C_m - 4(m-i)\cdot \textsf {OPT}, \end{aligned}$$

which is a contradiction. $\square$