WSEAS Transactions on Mathematics
Print ISSN: 1109-2769, E-ISSN: 2224-2880
Volume 12, 2013
A Lazy Bureaucrat Scheduling Game
Authors: ,
Abstract: In this paper we consider the game theoretical issue of the lazy bureaucrat scheduling problem. There are two players working on a pool of tasks, each of them can select a subset of the tasks to execute and spend the corresponding cost. The common choice would introduce the increasing of the task’s cost. Each player has his own budget for these tasks and if the total cost of selected tasks are less than his budget, he can keep the difference part as his “additional” profit. The objective of the players is to make wise selection such that the cost that he spents on the tasks is minimized, while both of them have to obey an assumption called “busy requirement” that as long as there are tasks can be executed by some player (the left budget is more than the cost needed), he must select it to execute. The noncooperative nature and potential interactions between the two players make the problem dynamic and complicated. We prove that Nash equilibrium solutions exist under certain conditions where both players are satisfied with their selection and would not change their mind unilaterally. We also find the method by which we can obtain the Nash equilibrium no matter the player has a single machine or multiple machines to execute on the tasks. Furthermore, we adopt the concept of “price of anarchy” to compare the cost of the worst Nash equilibrium with the social optimum.