
doi: 10.1007/11427186_9
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 parameterc. 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 α 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.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
