# Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems +
### Related Work  
The work most closely related to our paper is the one in [6] where the model we study is introduced and various results are obtained for the case of constant (but possibly time-dependent) server costs with respect to the price of anarchy and the related concepts of the strong price of anarchy (inefficiency of equilibria with respect to coordinated deviations) and the price of stability (inefficiency of the best Nash equilibrium as opposed to the worst). Our work also has ties to literature on the price of anarchy of congestion games, cost-sharing in congestion games, and coordination mechanisms, which we discuss below. Congestion games were introduced by [PERSON] [7] as a class of games that guarantee the existence of (pure) Nash equilibria. In a congestion game, there is a set of resources that the participants can use. Each of the participants has a strategy space that allows them to select one of given subsets of resources, something that allows for various expressive models, including routing in networks. The cost of each resource, which is a function of the number of participants using it, is distributed equally among its users. The price of anarchy of a special case of congestion games was first studied by [PERSON] and [PERSON] [11], who first introduced the price of anarchy. A long sequence of follow-up work has given a strong understanding of the price of anarchy in congestion games [8; 10; 12; 13; 14]. Generalizations to weighted models have also been studied [15; 10], albeit with the drawback that, in contrast to standard congestion games, the existence of a (pure) Nash equilibrium is not guaranteed [16]. Cost-sharing aspects in the study of congestion games were brought into the picture to correct for the absence of equilibria in weighted games. [PERSON] and [PERSON] [17] showed how the Shapley value cost-sharing method can be applied to restore pure equilibria, whereas [PERSON] et al. [18] showed that the more general class of generalized weighted Shapley values are the only ones that can guarantee this property. The price of anarchy of the induced games has been the subject of extensive study, with examples including those in [19; 20; 21; 22; 23; 24]. Authors who used cost-sharing to improve the efficiency of equilibria include [PERSON] et al. [25], who focused on the price of stability, and [PERSON] and [PERSON] [26], who provided an approach which requires knowledge of the instance at hand. A more general approach seeking to improve the price of anarchy is that of coordination mechanisms. A coordination mechanism gives the designer more freedom in designing the game. This freedom includes modifying the strategy spaces of the participants or changing how costs are defined on the resources. For example, coordination mechanisms were applied in a multiple machine makespan minimization scheduling setting by [PERSON] et al. [9] by means of introducing different scheduling policies on different machines. Follow up works on coordination mechanisms include those in [27; 28; 29; 30]. Our coordination mechanism is also related to the model of _arbitrary cost sharing_ and _resource buying games_, where each player picks a set of resources and submits a different payment for each one. This setting has been studied comprehensively for network design games. The work in [31] shows that a NE is not guaranteed to exist under arbitrary cost-sharing and that the PoA and PoS are large (almost equal to the number of players \(n\)). For the special case of a common destination node, the PoS is 1 and a NE is guaranteed to exist. An SPoA of \(\Theta(\log n)\) is given in [32]. Other works that study arbitrary cost-sharing in network design games include those in [33; 34; 35; 36; 37; 38]. Arbitrary cost sharing in the presence of convex costs was studied by [PERSON] et al. [39]. Summarizing the results and comparing against fair cost-sharing, we observe that, in the general network design game, arbitrary cost-sharing loses the NE existence property and increases the PoS from logarithmic to linear.