Experimental results for stackelberg scheduling strategies

A. C. Kaporis, L. M. Kirousis, E. I. Politopoulou, P. G. Spirakis

Research output: Contribution to journalConference articlepeer-review


In large scale networks users often behave selfishly trying to minimize their routing cost. Modelling this as a noncooperative game, may yield a Nash equilibrium with unboundedly poor network performance. To measure this inefficacy, the Coordination Ratio or Price of Anarchy (PoA) was introduced. It equals the ratio of the cost induced by the worst Nash equilibrium, to the corresponding one induced by the overall optimum assignment of the jobs to the network. On improving the PoA of a given network, a series of papers model this selfish behavior as a Stackelberg or Leader-Followers game. We consider random tuples of machines, with either linear or M/M/1 latency functions, and PoA at least a tuning parameter c. We validate a variant (NLS) of the Largest Latency First (LLF) Leader's strategy on tuples with PoA ≥ c. NLS experimentally improves on LLF for systems with inherently high PoA, where the Leader is constrained to control low portion a of jobs. This suggests even better performance for systems with arbitrary PoA. Also, we bounded experimentally the least Leader's portion α0 needed to induce optimum cost. Unexpectedly, as parameter c increases the corresponding α0 decreases, for M/M/1 latency functions. All these are implemented in an extensive Matlab toolbox.

Original languageEnglish (US)
Pages (from-to)77-88
Number of pages12
JournalLecture Notes in Computer Science
StatePublished - 2005
Event4th International Workshop on Experimental and Efficient Algorithms, WEA 2005 - Santorini Island, Greece
Duration: May 10 2005May 13 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Experimental results for stackelberg scheduling strategies'. Together they form a unique fingerprint.

Cite this