Cooperative Game Theoretic Analysis of Shared Services

Shared services are increasingly popular among firms and are often modeled as multi-class queuing systems. Several priority scheduling rules are possible to schedule customers from different classes. These scheduling rules can be static, where a class has strict priority over the other class, or can be dynamic based on delay and certain weights for each class. An interesting and important question is how to fairly allocate the waiting cost for shared services.

In this paper, we address the above problem using the solution concepts of cooperative game theory. We first appropriately define worth functions for each player (class), each coalition, and the grand coalition for multi-class M/G/1 queue with non-preemptive priority. It turns out that the worth function of the grand coalition follows Kleinrock’s conservation law. We fully analyze the(2-)class game and obtain the fair waiting cost allocations from several cooperative games’ solution concepts viewpoints. These include Shapley value, the core, and nucleolus. We prove the(2-)class game is convex which implies that the core is non-empty and the Shapley value allocation belongs to the core. Cooperative game-theoretic solutions capture fairness. We characterize the closed-form expression for these scheduling policies as bringing out various fairness aspects amongst scheduling policies. We consider Delay dependent priority (DDP) rule to determine fair scheduling policies from the Shapley value and the core-based allocation. We present extensive numerical experiments by partitioning the stability region for 2-class queues in three sub-regions.