## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 77-88 |

Number of pages | 12 |

Journal | Lecture Notes in Computer Science |

Volume | 3503 |

DOIs | |

State | Published - 2005 |

Event | 4th International Workshop on Experimental and Efficient Algorithms, WEA 2005 - Santorini Island, Greece Duration: May 10 2005 → May 13 2005 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science