Well-behaved online load balancing against strategic jobs

Bo Li (), Minming Li () and Xiaowei Wu ()
Additional contact information
Bo Li: The Hong Kong Polytechnic University
Minming Li: City University of Hong Kong
Xiaowei Wu: University of Macau

Journal of Scheduling, 2023, vol. 26, issue 5, No 4, 443-455

Abstract: 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})$$ Ω ( 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)$$ 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.

Keywords: Online scheduling; Truthful mechanism design; Posted price (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00770-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:26:y:2023:i:5:d:10.1007_s10951-022-00770-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00770-6

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().