Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-056 | 25th April 2005 00:00

The Price of Optimum in Stackelberg Games


Authors: Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis
Publication: 20th May 2005 23:06
Downloads: 2944


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.

ISSN 1433-8092 | Imprint