Randomized mechanism design for decentralized network scheduling

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.

Keywords:

• Network scheduling
• graph approach
• decentralized mechanism design
• myopic Bayes–Nash incentive compatibility
• asymptotic optimality

Acknowledgements

We thank two reviewers for their detailed comments that have helped improve this paper substantially.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The first author and fifth author are partially supported by Natural Science Foundation of China [grant number 11871280], the second author is supported by Natural Science Foundation of China [grant number 11531014], the third author is supported by Natural Science Foundation of China [grant numbers 11625105, 11926358] and the fifth author is also partially supported by Natural Science Foundation of China [grant number 11971349] and Qinglan Project.