Randomized mechanism design for decentralized network scheduling. (3rd July 2020)

• Record Type: Journal Article
• Authors: Sun, Jian; Xu, Dachuan; Han, Deren; Hou, Wenjing; Zhang, Xiaoyan
• Is Part Of: Optimization methods and software. Volume 35:Number 4(2020)
• Page Start: 722
• Page End: 740
• Publication Date: 2020-07-03
• Subjects: Network scheduling -- graph approach -- decentralized mechanism design -- myopic Bayes–Nash incentive compatibility -- asymptotic optimality; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1713129
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: In the network scheduling, jobs (tasks) must be scheduled on uniform machines (processors) connected by a complete graph so as to minimize the total weighted completion time. This setting can be applied in distributed multi-processor computing environments and also in operations research. In this paper, we study the design of randomized decentralized mechanism in the setting where a set of non-preemptive jobs select randomly a machine from a set of uniform machines to be processed on, and each machine can process at most one job at a time. We introduce a new concept of myopic Bayes–Nash incentive compatibility which weakens the classical Bayes–Nash incentive compatibility and derive a randomized decentralized mechanism under the assumption that each job is a rational and selfish agent. We show that our mechanism can induce jobs to report truthfully their private information referred to myopic Bayes–Nash implementability by using a graph theoretic interpretation of the incentive compatibility constraints. Furthermore, we prove that the performance of this mechanism is asymptotically optimal.