Abstract
We consider decentralized scheduling with precedence constraints (DSwP) games where a set of players are scheduling jobs to complete while a set of hard precedence constraints link the jobs of the players. The impact of these decentralized scheduling efforts can be quantified by examining the price of anarchy (PoA) and the price of stability (PoS), which measure, respectively, the ratio of social costs of the worst and best equilibrium solutions with the optimal (centralized) social costs. We demonstrate that equilibrium solutions do not, in general, exist for this class of games and prove their existence for certain classes of games. Upper bounds for the PoA and the PoS are proven to depend linearly on the sum of the processing times of the jobs across the players and we present an example to demonstrate that this bound cannot be tightened beyond the sum of the processing times divided by two.
This is a preview of subscription content, access via your institution.
References
 1.
Abeliuk, A., Aziz, H., Berbeglia, G., Gaspers, S., Kalina, P., Mattei, N., Peters D., Stursberg, P., Van Hentenryck, P., Walsh, T.: Interdependent scheduling games. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence, New York, NY, 2–9 (2016)
 2.
Abeliuk, A., Berbeglia G., Van Hentenryck, P.: Oneway interdependent games. In: Proceedings of the 2014 International Conference on Autonomous Agents and Multiagent Systems, Paris, France, pp. 1519–1520 (2014)
 3.
Agnetis, A., Briand, C., Ngueveu, S.U., Sucha, P.: Price of anarchy and stability in multiagent project scheduling. Ann. Oper. Res. 285, 97–119 (2020)
 4.
Anshelevich, E., Caskurlu, B.: Price of stability in survivable network design. Theory Comput. Syst. 49(1), 98–138 (2011)
 5.
Briand, C., Ngueveu, S.U., Sucha, P.: Finding an optimal Nash equilibrium to the multiagent project scheduling problem. J. Sched. 20, 475–491 (2017)
 6.
Çelik, M.: Network restoration and recovery in humanitarian operations: framework, literature review, and research directions. Surv. Oper. Res. Manag. Sci. 21(2), 47–61 (2016)
 7.
Cole, R., Correa, J.R., Gkatzelis, V., Mirrokni, V., Olver, N.: Decentralized utilitarian mechanisms for scheduling games. Games Econ. Behav. 92, 306–326 (2015)
 8.
Lee, E.E., Mitchell, J.E., Wallace, W.A.: Restoration of services in interdependent infrastructure systems: a network flows approach. IEEE Trans. Syst. Man Cybern. Part C Appl. Rev. 37(6), 1303–1317 (2007)
 9.
Kaufman, S., Qing, C., Levenson, L., Hanson, M.: Transportation during and after Hurricane Sandy. Technical report, Rudin Center for Transportation, NYU Wagner Graduate School of Public Service (2012)
 10.
Little, R.: Controlling cascading failure: understanding the vulnerabilities of interconnected infrastructures. J. Urban Technol. 9(1), 109–123 (2002)
 11.
Nash, J.F.: Equilibrium points in Nperson games. Proc. Natl. Acad. Sci. 36(1), 48–49 (1950)
 12.
Office of Electricity Delivery (2012) Hurricane Sandy situation reports. United States Department of Energy and Energy Reliability
 13.
Ouyang, M.: Review on modeling and simulation of interdependent critical infrastructure systems. Reliab. Eng. Syst. Saf. 121, 43–60 (2014)
 14.
Peddie, S., Van Savant, W.: Inside LIPA’s chaotic plan for electrical inspections. Newsday, December 8, 2012. https://www.newsday.com/longisland/insidelipaschaoticplanforelectricalinspections1.4309407 (2012). Accessed 5 Feb 2021
 15.
Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems. Springer, New York (2012)
 16.
Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT Press, Boston (2005)
 17.
Sharkey, T.C., Cavdaroglu, B., Nguyen, H., Holman, J., Mitchell, J.E., Wallace, W.A.: Interdependent network restoration: the value of informationsharing. Eur. J. Oper. Res. 244(1), 309–321 (2015)
 18.
Sharkey, T.C., Nurre, S.G., Nguyen, H., Chow, J.H., Mitchell, J.E., Wallace, W.A.: Identification and classification of restoration interdependencies in the wake of Hurricane Sandy. J. Infrastruct. Syst. 22(1), 04015007 (2016)
 19.
Schrage, L.: Letter to the editor—A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16(3), 687–690 (1968)
 20.
Schwirtz, M.: Report cites large release of sewage from Hurricane sandy. The New York Times, April 30, 2013. https://www.nytimes.com/2013/05/01/nyregion/hurricanesandysentbillionsofgallonsofsewageintowaterways.html (2013). Accessed 5 Feb 2021
 21.
Smith, A.M., Gonzalez, A.D., DueñasOsorio, L., D’Souza, R.M.: Interdependent network recovery games. Risk Anal. 40(1), 134–152 (2020)
 22.
Wallace, W.A., Mendoça, D., Lee, E.E., Mitchell, J.E., Chow, J.: Managing disruptions to critical interdependent infrastructures in the context of the 2001 World Trade Center attack. In: Beyond September 11th: An Account of Postdisaster Research, pp. 165–198. Elsevier Science, Amsterdam (2003)
Acknowledgements
This research was partially supported by NSF grant number CMMI1254258. The authors appreciate the detailed comments of the review team, especially the anonymous referee that helped to fix a mistake in an the initial submission about the level of the penalty parameter \(\rho \).
Author information
Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix
Example in a tree network of calculating \(w_j^m\)
Figure 5 provides a disrupted tree network. The source (supply) node in this network is node a and all demand nodes are labeled with their demand. The dashed arcs are those that are disrupted. In this case, we have four disrupted arcs. The ‘weight’ or ‘unmet demand’ of each disrupted arc (job) is calculated based on all demand in the subtree rooted at the tail node of the arc that is reachable in the network through nondisrupted arcs. For example, the weight of job (b, d) is equal to 100 which is the demand of node d plus the demand of node i (both reachable from d). Note that this weight does not include the demand of h since it is only reachable through the disrupted arc (d, h). The weights of the jobs are then: (b, d) has a weight 100, (d, h) has a weight of 20, (e, j) has a weight of 50, and then (a, c) has a weight of 550. In terms of precedence constraints, we focus on the situation where all damaged arcs have the same processing time. In this case, we can have a precedence constraint from a job to another job if the latter job appears in the subtree rooted at the tail node of the former job. This is because doing the latter job would not restore any services until the former job is complete and we may not be able to test the repair of an arc without services flowing through it. In this case, there would be a precedence constraint from (b, d) to (d, h) since the subtree rooted at node d includes arc (d, h).
DSwP game in Example 3.2.3 does not have Nash equilibrium
Necessary conditions for stable solution
In order for a schedule \(\mathcal {S}\) to be both feasible and stable, it has to satisfy the following conditions.

NC1
Singlemachine condition: each player process at most one job at a time.

NC2
Processing time condition: each job takes one period of time to be completed.

NC3
Precedence constraints are satisfied: a job can not be started if its predecessor jobs are not completed.

NC4
Nondelay condition: machine would not be idle if there are jobs for which all the precedence constraints are cleared and are available to be processed.
By NC1, NC2 and NC4, the schedule \(\mathcal {S}\) is uniquely determined by the order that the jobs are being processed. As each player has 5 jobs, there are \(5! = 120\) different orders for a player to choose from. So there are in total \(120 \times 120 = 14{,}400\) different possible schedules, without the consideration of precedence constraints. Considering the precedence constraints in Example 3, NC3 further reduce the number of possible feasible schedules to \(30 \times 30 = 900\). Table 1 shows the 30 possible orders that a player can choose to process its 5 jobs.
Best response
A schedule is at equilibrium if both players have best response to the other player’s schedule. Now we use the order notations in Table 1 to represent players’ schedules in Example 3. For instance, player Randy is said to choice schedule (S9) (i.e. 4, 5, 3, 1, 2) if he plans to do job 4R in period 1, job 5R in period 2, job 3R in period 3, job 2R in period 4 and job 2R in period 5. We also add three more schedules as follows:

(S10b) 4, 2, 3, 5, idle, 1: machine idle in period 5 and job 1 is processed in period 6.

(S14b) 3, 4, 5, 2, idle, 1: machine idle in period 5 and job 1 is processed in period 6.

(S15b) 3, 4, 2, 5, idle, 1: machine idle in period 5 and job 1 is processed in period 6.
Table 2 shows the best response of a player given the other’s schedule. The first column “Randy’s schedule” lists Randy’s schedule. The second column “Berkeley’s response 1” is the schedule Berkeley will choose to minimize his TWCT given Randy uses the schedule in the first column. The third column “Randy’s response 1” is the schedule Randy will choose to minimize his TWCT given Berkeley uses the schedule in the second column. And the last column “Berkeley’s response 2” is the schedule Berkeley will choose to minimize his TWCT given Randy uses the schedule in the third column. If a schedule were at Nash equilibrium, Berkeley’s response 1 and Berkeley’s response 2 would the same, as well as Randy’s schedule and Randy’s response 1 would be the same. In Table 2, all the 30 possible schedules are searched but none of them are at equilibrium. This shows that Nash equilibrium does not exists for the DSwP game in Example 3.
Rights and permissions
About this article
Cite this article
Sun, H., Sharkey, T.C. Decentralized scheduling with precedence constraints. Optim Lett 15, 2555–2575 (2021). https://doi.org/10.1007/s11590021017558
Received:
Accepted:
Published:
Issue Date:
Keywords
 Decentralized scheduling
 Price of anarchy
 Game theory