UM  > Faculty of Science and Technology
Residential Collegefalse
Status已發表Published
Well-behaved online load balancing against strategic jobs
Li, Bo1; Li, Minming2; Wu, Xiaowei3
2023-10-01
Source PublicationJournal of Scheduling
ABS Journal Level2
ISSN1094-6136
Volume26Issue:5Pages:443-455
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 Ω(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.

KeywordOnline Scheduling Posted Price Truthful Mechanism Design
DOI10.1007/s10951-022-00770-6
URLView the original
Indexed BySCIE
Language英語English
WOS Research AreaEngineering ; Operations Research & Management Science
WOS SubjectEngineering, Manufacturing ; Operations Research & Management Science
WOS IDWOS:000884152700001
Scopus ID2-s2.0-85141984021
Fulltext Access
Citation statistics
Document TypeJournal article
CollectionFaculty of Science and Technology
THE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU)
Corresponding AuthorWu, Xiaowei
Affiliation1.The Hong Kong Polytechnic University, Hong Kong
2.City University of Hong Kong, Hong Kong
3.University of Macau, Macao
Corresponding Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Li, Bo,Li, Minming,Wu, Xiaowei. Well-behaved online load balancing against strategic jobs[J]. Journal of Scheduling, 2023, 26(5), 443-455.
APA Li, Bo., Li, Minming., & Wu, Xiaowei (2023). Well-behaved online load balancing against strategic jobs. Journal of Scheduling, 26(5), 443-455.
MLA Li, Bo,et al."Well-behaved online load balancing against strategic jobs".Journal of Scheduling 26.5(2023):443-455.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Li, Bo]'s Articles
[Li, Minming]'s Articles
[Wu, Xiaowei]'s Articles
Baidu academic
Similar articles in Baidu academic
[Li, Bo]'s Articles
[Li, Minming]'s Articles
[Wu, Xiaowei]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Li, Bo]'s Articles
[Li, Minming]'s Articles
[Wu, Xiaowei]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.