Cost-sharing games in real-time scheduling systems

We apply non-cooperative game theory to analyze the server’s activation cost in real-time scheduling systems. An instance of the game consists of a single server and a set of unit-length jobs. Every job needs to be processed along a specified time interval, defined by the job’s release-time and due-date. Jobs may also have variable weights, which specify the amount of resource they require. We assume that jobs are controlled by selfish agents who act to minimize their own cost, rather than to optimize any global objective. The jobs processed in a specific time-slot cover the server’s activation cost in this slot, with the cost being shared proportionally to the jobs’ weights. Known results on cost-sharing games do not exploit the special interval-structure of the strategy space in our game, and are therefore not tight. We present a complete analysis of equilibrium existence, computation, and inefficiency in real-time scheduling cost-sharing games. Our tight analysis covers various classes of instances, and distinguishes between unilateral and coordinated deviations.