Well-behaved online load balancing against strategic jobs

DOI10.1007/S10951-022-00770-6MaRDI QIDQ6090218zbMATH OpenOpenAlexFDO

Authors Bo Li, Minming Li, Xiaowei Wu

Publication date 14 November 2023

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.04481

zbMATH Keywords

online schedulingposted pricetruthful mechanism design

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: In the online load balancing problem on related machines, we have a set of jobs (with different sizes) arriving online, and we need 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 1997, Feldman et al. EC 2017]. In this paper, we study truthful online load balancing mechanisms that are well-behaved [Epstein et al., MOR 2016]. Well-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 $Omega(sqrtm)$, 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(logm)$. 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.

Recommendations

• Online and Random-order Load Balancing Simultaneously
• Online vector scheduling and generalized load balancing
• scientific article; zbMATH DE number 1629979
• On-line load balancing of temporary tasks revisited
• Online load balancing on uniform machines with limited migration
• Online load balancing with general reassignment cost
• Online load balancing of temporary tasks
• scientific article; zbMATH DE number 1256657
• Online batch-machine scheduling to maximize total weight of the accepted jobs

Cites work

• scientific article; zbMATH DE number 1670659 (Why is no real title available?)
• A deterministic truthful PTAS for scheduling related machines
• A lower bound for scheduling mechanisms
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• A unified approach to truthful scheduling on related machines
• Algorithmic Game Theory
• Algorithmic mechanism design (extended abstract)
• Algorithms – ESA 2005
• Almost envy-freeness with general valuations
• An optimal online algorithm for scheduling two machines with release times
• Bounds on Multiprocessing Timing Anomalies
• On-Line Load Balancing for Related Machines
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Online makespan minimization: the power of restart
• STACS 2005
• Scheduling on identical machines: How good is LPT in an on-line setting?

Cited in

(4)

• Online load balancing with general reassignment cost
• Online load balancing on uniform machines with limited migration
• On-Line Load Balancing of Temporary Tasks
• Online load balancing of temporary tasks

This page was built for publication: Well-behaved online load balancing against strategic jobs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6090218)