Schedule Situations and their Cooperative Games

We introduce a new problem of cost allocation resulting from a scheduling problem, and we study it by a new class of cooperative games, the schedule situations and the associated games. In a schedule situation several players share a non-rival common-pool infrastructure. Its consumption is possible during several periods. The consumption needs of each player are described by the set of minimal schedules satisfying this player. The use of this infrastructure induces a fixed per-period cost normalized to one unit. Therefore, one objective is to minimize the overall total number of consumption time periods in order to satisfy all players. For this purpose, the schedule game gives for each coalition of players the minimal number of time periods needed to satisfy the consumption needs of all its members. We provide a characterization of the class of schedule games: a game is a schedule game if and only if it is monotonic, sub-additive, integer-valued and all nonempty coalitions have positive worths. Moreover, specific schedule games can be linked to other classes of operational research games: the airport games and the carpool games. We also introduce Equal pooling allocations, which in some cases coincide with the Shapley value. Next we develop a natural sufficient condition to guarantee the non-emptiness of the core of a schedule game. Finally, we provide an application of the the schedule situations and the associated games to the allocation of cost of the mail carrier route in France.