Well-behaved Online Load Balancing Against Strategic Jobs

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019)
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1243-1251
Number of pages9
ISBN (Print)978-1-4503-6309-9
Publication statusPublished - May 2019

Conference

Title18th International Conference on Autonomous Agents and MultiAgent Systems
Location
PlaceCanada
CityMontreal
Period13 - 17 May 2019

Abstract

In the online load balancing problem on related machines, we havea set of jobs (with different sizes) arriving online, and we need toassign each job to a machine immediately upon its arrival, so asto minimize the makespan, i.e., the maximum completion time. Inclassic mechanism design problems, we assume that the jobs arecontrolled by selfish agents, with the sizes being their private information. Each job (agent) aims at minimizing its own cost, whichis its completion time plus the payment charged by the mechanism.Truthful mechanisms guaranteeing that every job minimizes itscost 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]. Wellbehavior is important as it guarantees fairness between machines,and implies truthfulness in some cases when machines are controlled by selfish agents. Unfortunately, existing truthful onlineload balancing mechanisms are not well-behaved. We first showthat 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 mechanismthat guarantees truthfulness of the online jobs, and produces aschedule that is almost well-behaved. We show that our algorithmhas a competitive ratio of O (log m). Moreover, for the case whenthe sizes of online jobs are bounded, the competitive ratio of ouralgorithm improves to O (1). Interestingly, we show several cases forwhich our mechanism is actually truthful against selfish machines. 

Research Area(s)

  • Online load balancing, Truthful mechanism, Well-behaved

Citation Format(s)

Well-behaved Online Load Balancing Against Strategic Jobs. / Li, Bo; Li, Minming; Wu, Xiaowei.

Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2019. p. 1243-1251.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)