Consider a system M of parallel machines, each with a strictly increasing and differentiable load dependent latency function. The users of such a system are of infinite number and act selfishly, routing their infinitesimally small portion of the total flow r they control, to machines of currently minimum delay. It is well known that such selfishness if modeled by a noncooperative game may yield a Nash Equilibrium on M with cost unboundedly worst than the overall Optimum one. We model such a system as a Stackelberg or Leader-Followers game, and present a simple algorithm that computes the least flow \beta_M (or ?price of optimum?) that must be controlled by a Leader in order to impose the overall optimum cost on M, as well as Leader?s optimum strategy. The efficiency of our algorithm depends on the computation of the optimum and Nash assignment on such systems. Such assignments can be computed efficiently for the classes of latency functions that we are interested in. The open question of computing \beta_M on a arbitrary system M.
In that article systems with M/M/1 latency functions were studied, which are widely met in real world applications. Furthermore, \beta_M(n) was computed explicitly for Stackelberg games with either n = 1 or a finite number n of Followers. It was demonstrated that \beta_M(n) is nondecreasing on n, and as n increases it becomes harder for the Leader to impose the overall optimum. Most notably, it was conjectured that if n goes to infinity then it is not possible for the Leader to impose system?s overall optimum. This comes into contrast to our theoretical results. As a by-product, we present a simple algorithm that computes the Nash Equilibrium for a system M with M/M/1 latency functions.
We should stress here that the model of parallel machines, despite its simplicity, incurs the worst coordination ratio.